知识卡片
类型别名不收紧底层接口
typedef List Stack给List增加一个别名,并未建立具有独立表示或受限访问的新C类型。stack_push/pop选择链表头插/头删来提供LIFO语义,但同一对象仍可交给List操作,调用者能够绕过基本栈接口。
结构图:
classDiagram
class List {
int size
ListElmt* head
ListElmt* tail
}
class Stack["Stack(List的typedef别名)"]
class API["栈公开函数组(非类型)"] {
stack_push(Stack* stack, const void* data) int
stack_pop(Stack* stack, void** data) int
}
Stack ..> List : 同一类型的另一个名字,非继承
API ..> Stack : 以头部操作提供栈语义
图仅列相关List字段,实际还有match/destroy回调;Stack没有额外字段。头文件把init/destroy/size宏映射到底层对应入口。
用list_head/list_next可不弹出地遍历;只用栈接口也可搬到临时栈再搬回,但会改变中间状态并增加工作。本例所谓“多态”是表示共享的使用便利,不是C语言新增类继承或动态分派。
82明确初始化宏映射,固定字段赋值按O(1)模型理解;不是运行时在两个不同对象间复制或构造继承关系。
89文字的typedef方向按91的实际typedef List Queue理解:Queue为List的另一名称,不是List继承Queue。它允许使用底层链表操作,也意味着FIFO约束主要通过所选接口维持。
90与02774头文件的宏映射一致,初始化固定字段步骤为O(1);它不清理先前已存在且尚未销毁的节点。
91的02774-02775完整queue.h及93的02776 queue.c给出另一别名与薄封装:
结构图:
classDiagram
class List
class Queue["Queue(List的typedef别名)"]
class API["队列公开函数组(非类型)"] {
queue_enqueue(Queue* queue, const void* data) int
queue_dequeue(Queue* queue, void** data) int
}
Queue ..> List : 同一类型的另一个名字,非继承
API ..> Queue : 尾插与头删提供FIFO
init/destroy/size分别宏映射到List对应入口,peek直接读head数据。图不表示Queue包含一个List成员;本版确实是别名,问答中的嵌入方案是另一种设计选择。
96给独立结构与嵌入List的替代。作者偏好别名不意味着嵌入设计不合法;嵌入可有更明确的包装边界,但需显式转发底层操作。一般多态关注共同能力下的替代使用,本例typedef只让同一类型有另一名称,不能拿它证明已有多种独立实现的动态分派。缺少stack_next/queue_next是接口选择,底层list_next仍可被调用。
97给多态的广义用途定义,可按共同能力替代使用;但具体C别名方案不能被升级为语言本身支持继承或动态分派。
104的02791完整set.h使用typedef List Set,未新增任何成员;别名允许调用list_next遍历或按已知前驱直接删除,也允许绕过set_insert把重复成员插入,因此类型别名本身不强制集合不变量。
结构图:
classDiagram
class List
class Set["Set(List的typedef别名)"]
class SetAPI["集合公开函数组(非类型)"] {
set_init(Set* set, match, destroy) void
set_insert(Set* set, const void* data) int
set_remove(Set* set, void** data) int
set_union(Set* out, const Set* a, const Set* b) int
set_intersection(Set* out, const Set* a, const Set* b) int
set_difference(Set* out, const Set* a, const Set* b) int
set_is_member(const Set* set, const void* data) int
set_is_subset(const Set* a, const Set* b) int
set_is_equal(const Set* a, const Set* b) int
}
Set ..> List : 同一类型另名,非继承
SetAPI ..> Set : 按判等规则维护唯一性
图中match简写实际int (match)(const void,const void*),destroy简写void (destroy)(void);它们不是新字段。set_destroy宏映射list_destroy,set_size宏读size。表示复用带来可直接遍历的便利,也让语义约束依赖接口使用纪律。
161实际typedef BiTree BisTree。基本操作仍能被调用,但其data为AvlNode包装而非用户对象,任意底层变更可破坏键序、因子和清理语义;别名带来复用不等于接口自动安全替代。
181的02910实际为typedef Heap PQueue,不是正文方向相反的typedef PQueue Heap。
结构图:
classDiagram
class Heap
class PQueue["PQueue(Heap的typedef别名)"]
class PQueueAPI["优先队列函数/宏组(非类型)"] {
pqueue_insert(PQueue* queue, const void* data) int
pqueue_extract(PQueue* queue, void** data) int
pqueue_peek(PQueue* queue) void*
}
PQueue ..> Heap : 同一类型另名,非继承
PQueueAPI ..> PQueue : 插入提取映射堆操作
init/destroy/size也直接宏映射,peek检查tree指针NULL后读tree[0]。它不额外存排序数组或稳定序号,亦不会在销毁时逐次extract;底层heap_destroy如何清理就是实际行为。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 类型别名不收紧底层接口
- · stack_init
- · 队列的实现与分析
- · queue_init
- · queue_destroy
- · 问与答
- · 相关主题
- · 集合抽象数据类型的实现和分析
- · AVL树的旋转
- · 优先队列的实现与分析
原书出处 · 10 处
- · 查看原书依据
typedef Stack to List这种简单的方法来做到这一点(见示例6-1)。这种方法不仅简单,而且可以使栈具有多态的特性。通俗地讲,多态通常是面向对象语言的一种特性,它允许某种类型的对象(变量)在使用时用其他类型的对象(变量)代替。这意味着,除了使用栈本身的操作外,还可以使用链表中的操作,
- · 查看原书依据
将stack_init定义成list_init。 stack_init的运行时复杂度与list_init相同,都是O(1)。
- · 查看原书依据
typedef Queue List来定义它。
- · 查看原书依据
将queue_init定义成list_init。 queue_init的运行时复杂度与list_init相同,都是O(1)。
- · 查看原书依据
队列抽象数据类型的头文件
- · 查看原书依据
将链表结构放到每个栈或队列结构中,这样栈或队列就可以继续使用链表中的操作。但这样表示并不贴切,因为栈和队列本身就是链表的一种,而并不是包含在链表中。 问:为什么栈中没有stack_next宏?同样,为什么队列中没有queue_next宏?这两种宏可以分别用来遍历栈和队列。 答:通过typedef L
- · 查看原书依据
多态是面向对象语言的重要组成部分。然而,在一些内在并不支持多态的语言中,我们在某种程度上仍然可以通过使用一些特殊技术来提供这种多态的特性。 双向队列 通常简称为deque(发音同"decks")。双向队列操作更加灵活,它能够在队列的头部和尾部都进行插入和删除操作。 循环队列 循环队列类似于循环链表。
- · 查看原书依据
重命名为Set(见示例7-1)。除了保持简洁性之外,使用typedef还使得Set具有了一些多态的特性,如同在栈和队列中描述的那样(见第6章)。因此,由于set实际上就是一个链表,因此当需要将set表现为一个链表的时候就可以对set施行属于链表的操作。使用这种方法的最大的好处就是可以使用list_n
- · 查看原书依据
typedef方式将BisTree实现为BisTree的别名(见示例9-4)。这么做除了简洁之外,采用typedef的方法使得二叉搜索树具有了某种程度的多态能力,如同前面介绍过的栈和队列一样(见第6章)。这意味着除了专属于二叉搜索树的操作外,还可以在其之上执行属于二叉树的操作。 由于要保持一棵二叉搜
- · 查看原书依据
优先队列的头文件