第 12 章 使用结构和指针
# 第 12 章 使用结构和指针
书本内容
# 12.1 链表
书本内容
# 12.2 单链表
书本内容
# 12.2.1 在单链表中插入
书本内容
# 调试插入函数
书本内容
提示
- 可能需要修改
root
的值, 因此传参时将root
的地址作为参数传入- 形参选为
Node **rootp
- 形参选为
# 优化插入函数
书本内容
笔记
linkp
并不指向节点本身, 而是指向前一个节点内部的link
字段, 这是简化插入函数的关键所在
# 12.2.2 其他链表操作
书本内容
# 12.3 双链表
书本内容
# 12.3.1 在双链表中插入
书本内容
# 简化插入函数
书本内容
# 12.3.2 其它链表操作
书本内容
# 12.4 总结
书本内容
# 12.7 问题
#
问题 1
答案
代码如下
#include <stdlib.h> #include <stdio.h> #include "sll_node.h" #define FALSE 0 #define TRUE 1 int sll_insert(Node **linkp, int new_value) { Node *new; /* ** Look for the right place by walking down the list ** until we reach a node whose value is greater than ** or equal to the new value. */ while (*linkp != NULL && (*linkp)->value < new_value) linkp = &(*linkp)->link; /* ** Allocate a new node and store the new value into it. ** In this event, we return FALSE. */ new = (Node *)malloc(sizeof(Node)); if (new == NULL) return FALSE; new->value = new_value; /* ** Insert the new node into the list, and return TRUE. */ new->link = *linkp; *linkp = new; return TRUE; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35虽然减少了一个变量,但是会增加 3 个额外的间接引用(涉及到更多的内存操作),会使得程序变慢
程序的可读性也变得更差
提示
- 需要注意间接访问操作符
*
的优先级要低于访问结构指针成员操作符->
#
问题 2
答案
- 和不用处理任何特殊情况的的代码
sll_insert
函数相比, 这种使用头结点的技巧没有任何优越之处 - 这个节点会浪费额外的内存
- 创建链表时, 必须要创建哑节点; 而且其它操纵链表的函数也必须要跳过这个哑节点
#
问题 3
答案
- 会插到重复值之前
- 修改后, 会插到重复值之后
#
问题 4
答案
如果节点是动态分配的, 则可以通过只为节点的一部分分配内存来达到目的
Node *root; root = malloc(sizeof(Node) - sizeof(ValueType))
1
2更通用的方法是声明一个只包含指针的结构
struct DLL_NODE; struct DLL_POINTERS { struct DLL_NODE *fwd; struct DLL_NODE *bwd; } struct DLL_NODE { struct DLL_POINTERS pointers; int value; }
1
2
3
4
5
6
7
8
9
10
11
12
13两个结构之间存在相互信赖的情况, 需要通过其中一个结构标签的不完整声明来解决
#
问题 5
答案
- 当插入的节点重复时, 可能会存在内存泄漏
#
问题 6
答案
- 能够实现
- 一种方法是依次取出单链表中的所有结点, 然后再将这些结点插入到一个新的有序单链表中
#
问题 7
答案
- 在多个链表中进行查找的效率要比在单个链表中进行查找的效率高很多
- 如果每个字母开头的单词出现的频率相同, 则多个链表方案的效率几乎可是提高 26 倍
# 12.8 编程练习
#
编程练习 1
答案
需要知道节点的内部结构信息
如果函数被调用时, 传递给它的是指向链表中间某个位置的指针, 那么它会对这个节点以及这个节点以后的节点进行计数
代码
#include <stdio.h> #include <sll_node.h> int sll_count_nodes(Node *first) { int count; for (count = 0; first != NULL; first = first->link) count++; return count; }
1
2
3
4
5
6
7
8
9
10
11
12
#
编程练习 2
答案
在无序的链表中进行查找的代码如下
#include <stdio.h> #include <sll_node.h> Node *sll_find(Node *root, int desired_value) { for (; root != NULL; root = root->link) if (root->value == desired_value) return root; return NULL; }
1
2
3
4
5
6
7
8
9
10
11不需要进行修改, 也可让上述函数适用于有序的单链表, 不过可以修改其循环的判断条件, 以让其更高效
#include <stdio.h> #include <sll_node.h> Node *sll_find(Node *root, int desired_value) { for (; root != NULL && root->value <= desired_value; root = root->link) if (root->value == desired_value) return root; return NULL; }
1
2
3
4
5
6
7
8
9
10
11
#
编程练习 3
答案
采用与单链表插入时相同的方法,可以避免将插入到链表的起始位置当做一种特殊情况处理
- 程序中的
Node **linkedp
指向的是前一个节点的link
字段
- 程序中的
插入到链表的尾部,仍然需要当做一种特殊情况进行处理
代码
#include <stdlib.h> #include <stdio.h> #include "dll_node.h" int dll_insert(Node **head, Node **tail, int value) { Node **linkedp; Node *current; Node *newnode; linkedp = head; while ((current = *linkedp) != NULL) { if (current->value == value) return 0; if (current->value > value) break; linkedp = ¤t->fwd; } newnode = (Node *)malloc(sizeof(Node)); if (newnode == NULL) return -1; newnode->value = value; /* ** Add the new node to the list. */ newnode->fwd = current; *linkedp = newnode; if (current == NULL) { newnode->bwd = *tail; *tail = newnode; } else { newnode->bwd = current->bwd; current->bwd = newnode; } return 1; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#
编程练习 4
答案
代码
#include <stdio.h> #include <stdlib.h> #include "sll_node.h" Node *sll_reverse(Node *first) { Node *previous; Node *next; Node *current; for (previous = NULL, current = first; current != NULL; previous = current, current = next) { next = current->link; current->link = previous; } return previous; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#
编程练习 5
- 把一个指向欲移除的节点的指针而不是欲移除节点的值作为参数传送给函数的优点如下
- 不需要知道节点内部的结构, 这样对于不同的链表, 只需修改
.h
文件即可 - 如果有多个节点具有相同的值, 传递指针移除的节点更加明确
- 不需要知道节点内部的结构, 这样对于不同的链表, 只需修改
- 注意此函数只适合于动态分配节点的链表
- 还有一种方案是由调用者负责释放内存空间. 但是可能会造成内存泄漏
答案
代码
#include <assert.h> #include <stdio.h> #include <stdlib.h> #include "sll_node.h" #define True 1 #define False 0 int sll_remove(Node **rootp, Node *node) { Node *current; assert(node != NULL); while ((current = *rootp) != NULL) { if (current == node) { *rootp = current->link; free(current); return True; } rootp = ¤t->link; } return False; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
提示
- 使用
assert
的原因是, 如果移除的参数传递的是空指针, 如果返回False
, 其含义是NULL
节点不在链表中, 不太合逻辑. 所以, 直接报错
#
编程练习 6
答案
代码
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include "dll_node.h" #define True 1 #define False 0 int dll_remove(Node *rootp, Node *node) { Node *current; assert(node != NULL); assert(rootp != NULL); current = rootp->fwd; while (current != NULL && current != node) current = current->fwd; if (current == NULL) return False; else { if (current->bwd == NULL) rootp->fwd = current->fwd; else current->bwd->fwd = current->fwd; if (current->fwd == NULL) rootp->bwd = current->bwd; else current->fwd->bwd = current->bwd; free(current); return True; } }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#
编程练习 7
答案
代码
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include "list_word.h" #define True 1 #define False 0 int concordance_insert(List **list, char *word) { List *listp; List *current_list; List *new_list; Word **wordp; Word *current_word; Word *new_word; int comparsion; if (!islower(*word)) return False; comparsion = 1; while ((current_list = *list) != NULL && current_list->letter < *word) list = ¤t_list->next; if (current_list == NULL || current_list->letter != *word) { new_list = malloc(sizeof(List)); if (new_list == NULL) return False; new_list->letter = *word; new_list->word_list = NULL; new_list->next = current_list; *list = new_list; current_list = new_list; } wordp = ¤t_list->word_list; comparsion = 1; while ((current_word = *wordp) != NULL) { comparsion = strcmp(current_word->str, word); if (comparsion >= 0) break; wordp = ¤t_word->next; } if (current_word != NULL && comparsion == 0) return False; new_word = malloc(sizeof(Word)); if (new_word == NULL) return False; new_word->str = malloc((strlen(word) + 1) * sizeof(char)); if (new_word->str == NULL) return False; strcpy(new_word->str, word); new_word->next = current_word; *wordp = new_word; return True; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
编辑 (opens new window)
上次更新: 2022/02/19, 13:02:00