第 17 章 经典抽象数据类型
# 第 17 章 经典抽象数据类型
书本内容
# 17.1 内存分配
书本内容
# 17.2 堆栈
书本内容
# 17.2.1 堆栈接口
书本内容
# 17.2.2 实现堆栈
书本内容
# 数组堆栈
书本内容
# 动态数组堆栈
书本内容
# 链式堆栈
书本内容
# 17.3 队列
书本内容
# 17.3.1 队列接口
书本内容
# 17.3.2 实现队列
书本内容
笔记
- 循环数组通过始终保留一个空元素,来方便判定队列是否为空或已满,相应的不变量为下
- 队列为空时的条件
(rear + 1) % QUEUE_SIZE == front
- 队列已“满” 时的条件
(rear + 2) % QUEUE_SIZE == front
- 队列为空时的条件
# 17.4 树
书本内容
# 17.4.1 在二叉搜索树中插入
书本内容
# 17.4.2 在二叉搜索树中删除节点
书本内容
# 17.4.3 在二叉搜索树中查找
书本内容
# 17.4.4 树的遍历
书本内容
# 17.4.5 二叉搜索树接口
书本内容
# 17.4.6 实现二叉搜索树
书本内容
# 17.5 实现的改进
书本内容
# 17.5.1 拥有超过一个堆栈
书本内容
# 17.5.2 拥有超过一种类型
书本内容
# 17.5.3 名字冲突
书本内容
# 17.5.4 标准函数库的 ADT
书本内容
# 17.6 总结
书本内容
# 17.9 问题
#
问题 1
答案
- 使用堆栈,堆栈是 LIFO
#
问题 2
答案
- 使用队列,队列是 FIFO,可以确保牛奶不会过期
#
问题 3
答案
- 新定义一个
top
接口,返回栈顶元素但不实际移除它; 而pop
函数删除栈顶元素并返回它 - 如果想使用传统的堆栈接口,则直接使用
pop
函数即可 - 如果使用替代方案,则可又使用
top
函数来获取栈顶元素的值;用pop
函数来删除栈顶元素,并忽略其返回值
#
问题 4
答案
不会使用功能变得更加强大,因为借助现有的接口函数,也能实现这个功能
while(!is_empty()) pop();
1
2不过,根据堆栈实际实现的数据结构,有可能更加高效的实现这个功能
例如,当堆栈是用数组实现时,其高效实现如下
void empty(void) { top_element = -1; }
1
2
3
4
5
#
问题 5
答案
- 次序弄反,则跟数据结构的预期操作不吻合
- 为了达到堆栈接口的效果,需要将
top_element
的初始值设置为 0- 但是需要修改相应的
top
函数return stack[top_element - 1]
- 但是如此修改后,
top
函数的效率有些许降低
- 但是需要修改相应的
#
问题 6
答案
- 客户端可能
push
过多的值,从而溢出数组,这可能会修改其它有用的数据,甚至会导致错误 - 客户端也可能
pop
过多的值,从而可以访问数组外的数据。使得程序的隔离性变差
#
问题 7
答案
- 由于链表式堆栈中的每个元素都是由
malloc
函数单独分配的,逐个将它们弹出可以保证每个元素均被释放 - 由于释放节点的代码在
pop
函数中已经存在,所以直接调用相应的函数进行复用即可
#
问题 8
答案
- 不可省略,如果省略,则释放头部节点
stack
后,无法继续让stack
指向新的头部结点 - 这样会破坏堆栈结构的不变量
#
问题 9
- 题目翻译有误,堆栈应翻译为数组
- 注意此题题意是没有通过保证数组中的一个元素为始终为空来确定队列是否已满
答案
- 设数组的大小为
,当 front
确定时,则rear
共有种可能的取值 - 但是队列元素的数量取值范围为
,其有 中可能 - 由鸽巢原理可知,
front
和rear
必定有一种取值会表示两种状态,即满和空时,front
和rear
的取值是相同的
- 由鸽巢原理可知,
#
问题 10
答案
- 两种方法均能达到预期的效果
- 使用第 2 种方法,会增加
insert
和delete
函数的复杂性,因为在这两个函数中,需要维持size
的属性 - 使用第 1 种方法,会有一个数组元素始终处于空置状态。当数组元素占用的空间较大时,会造成空间的浪费
#
问题 11
- 此题是在 17.3.2 现有代码的基础上进行相应的修改
答案
if (front <= rear)
n_values = rear - front + 1;
else
n_values = (queue_size - (front - rear + 1 - 2)) % QUEUE_SIZE
1
2
3
4
2
3
4
取余操作,是为了应对队列为空时的情况
#
问题 12
答案
- 如果有一个指向链表尾部的指针,用单链表即可实现队列的功能
- 没有必要使用双链表,队列只需在尾部插入,在头部删除即可,不需要从后向前遍历。双链表会浪费一个链字段的开销
#
问题 13
答案
#
问题 14
答案
- 此时二叉树相当于是一个单向链表,搜索的时间复杂度为
#
问题 15
答案
- 前序遍历的次序为: 54, 36, 22, 16, 25, 41, 40, 51, 72, 61, 80, 73
- 中序遍历的次序为: 16, 22, 25, 36, 40, 41, 51, 54, 61, 72, 73, 80
- 后序遍历的次序为: 16, 25, 22, 40, 51, 41, 36, 61, 73, 80, 72, 54
- 层次遍历的次序为: 54, 36, 72, 22, 41, 61, 80, 16, 25, 40, 51, 73
#
问题 16
答案
代码
static void do_in_order_traverse( int current, void (*callback)( TREE_TYPE value ) ) { if( current < ARRAY_SIZE && tree[ current ] != 0 ){ do_in_order_traverse( left_child( current ), callback ); callback( tree[ current ] ); do_in_order_traverse( right_child( current ), callback ); } } /* ** in_order_traverse */ void in_order_traverse( void (*callback)( TREE_TYPE value ) ) { do_in_order_traverse( 1, callback ); }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#
问题 17
答案
代码
static void do_post_order_traverse( int current, void (*callback)( TREE_TYPE value ) ) { if( current < ARRAY_SIZE && tree[ current ] != 0 ){ do_post_order_traverse( left_child( current ), callback ); do_post_order_traverse( right_child( current ), callback ); callback( tree[ current ] ); } } /* ** post_order_traverse */ void post_order_traverse( void (*callback)( TREE_TYPE value ) ) { do_post_order_traverse( 1, callback ); }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#
问题 18
答案
- 中序遍历可以通过升序来遍历树中所有的节点
- 没有预设的遍历方法可以按照降序来依次访问树中的节点,但是可以修改中序遍历,使其先遍历右子树来实现这个目的
#
问题 19
答案
- 后序遍历最为合适,因为其先删除当前节点所有的子节点后,最后才删除当前结点
# 17.10 编程练习
#
编程练习 1
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 2
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 3
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 4
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 5
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 6
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 7
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 8
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 9
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 10
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 11
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 12
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 13
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 14
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 15
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 16
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 17
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 18
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
#
编程练习 19
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { return EXIT_SUCCESS; }
1
2
3
4
5
6
7
8
提示
编辑 (opens new window)
上次更新: 2022/01/26, 21:01:00