基本概念
链式存储定义：
为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息。
表头结点：
链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息。
数据结点：
链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息。
尾结点：
链表中的最后一个数据结点，其下一元素指针为空，表示无后继。
链表技术领域推演
链表链式存储_api实现分析：
在C语言中可以用结构体来定义链表中的指针域，链表中的表头结点也可以用结构体实现；
带头结点、位置从0的单链表；
返回链表中第3个位置处，元素的值。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
LinkListNode* LinkList_Get(LinkList* list, int pos) { if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) { return NULL; } TLinkList *tList = NULL; tList = (TLinkList *)list; LinkListNode *cur = NULL; cur = &(tList->header); for (int i = 0; i < pos; ++i) { cur = cur->next; } return cur->next; } |
返回第三个位置的。
移动pos次以后，当前指针指向哪里？
答案：指向位置2，所以需要返回 ret = current->next。
备注：循环遍历时
遍历第1次，指向位置0；
遍历第2次，指向位置1；
遍历第3次，指向位置2；
遍历第n次，指向位置n-1。
删除元素：
代码实例：
linklist.h
|
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
|
#ifndef _MYLINKLIST_H_ #define _MYLINKLIST_H_ typedef void LinkList; typedef struct _tag_LinkListNode { struct _tag_LinkListNode* next; }LinkListNode; LinkList* LinkList_Create(); void LinkList_Destroy(LinkList* list); void LinkList_Clear(LinkList* list); int LinkList_Length(LinkList* list); int LinkList_Insert(LinkList* list, LinkListNode* node, int pos); LinkListNode* LinkList_Get(LinkList* list, int pos); LinkListNode* LinkList_Delete(LinkList* list, int pos); #endif |
linklist.cpp
|
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
#include <iostream> #include <cstdio> #include "linklist.h" using namespace std; typedef void LinkList; typedef struct _tag_LinkList { LinkListNode header; int length; }TLinkList; LinkList* LinkList_Create() { TLinkList *tmp = NULL; tmp = (TLinkList *)malloc(sizeof(TLinkList)); if (tmp == NULL) { printf("function LinkList_Create() err.\n"); return NULL; } memset(tmp, 0, sizeof(TLinkList)); // 初始化为空链表 return tmp; } void LinkList_Destroy(LinkList* list) { if (list == NULL) { return; } free(list); return; } void LinkList_Clear(LinkList* list) { if (list == NULL) { return; } TLinkList *tList = NULL; tList = (TLinkList *)list; tList->header.next = NULL; tList->length = 0; return; } int LinkList_Length(LinkList* list) { if (list == NULL) { return -1; } TLinkList *tList = NULL; tList = (TLinkList *)list; return tList->length; } int LinkList_Insert(LinkList* list, LinkListNode* node, int pos) { if (list == NULL || node == NULL || pos < 0) { return -1; } TLinkList *tList = NULL; tList = (TLinkList *)list; LinkListNode *cur = NULL; cur = &(tList->header); // 对pos的容错处理，如果pos过大，改为最后面 if (pos > LinkList_Length(list)) { pos = LinkList_Length(list); } // 移动到需要插入的位置 for (int i = 0; i < pos; ++i) { cur = cur->next; } // 插入 node->next = cur->next; cur->next = node; ++tList->length; return 0; } LinkListNode* LinkList_Get(LinkList* list, int pos) { if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) { return NULL; } TLinkList *tList = NULL; tList = (TLinkList *)list; LinkListNode *cur = NULL; cur = &(tList->header); for (int i = 0; i < pos; ++i) { cur = cur->next; } return cur->next; } LinkListNode* LinkList_Delete(LinkList* list, int pos) { if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) { return NULL; } TLinkList *tList = NULL; tList = (TLinkList *)list; LinkListNode *cur = NULL; cur = &(tList->header); for (int i = 0; i < pos; ++i) { cur = cur->next; } LinkListNode *ret = NULL; ret = cur->next; // 删除结点 cur->next = ret->next; --tList->length; return ret; } |
main.cpp
|
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
|
#include <iostream> #include <cstdio> #include "linklist.h" using namespace std; typedef struct _Student { LinkListNode node; char name[32]; int age; }Student; int main() { Student s1, s2, s3, s4, s5, s6; s1.age = 21; s2.age = 22; s3.age = 23; s4.age = 24; s5.age = 25; s6.age = 26; // 创建链表 Student *list = (Student *)LinkList_Create(); // 插入结点 LinkList_Insert(list, (LinkListNode *)&s1, 0); LinkList_Insert(list, (LinkListNode *)&s2, 0); LinkList_Insert(list, (LinkListNode *)&s3, 0); LinkList_Insert(list, (LinkListNode *)&s4, 0); LinkList_Insert(list, (LinkListNode *)&s5, 0); LinkList_Insert(list, (LinkListNode *)&s6, 3); // 遍历链表 for (int i = 0; i < LinkList_Length(list); ++i) { Student *tmp = (Student *)LinkList_Get(list, i); if (tmp == NULL) { return 0; } printf("age: %d\n", tmp->age); } // 删除链表结点 while (LinkList_Length(list)) { Student *tmp = (Student *)LinkList_Delete(list, 0); if (tmp == NULL) { return 0; } printf("age: %d\n", tmp->age); } LinkList_Destroy(list); return 0; } |
优点：
- 无需一次性定制链表的容量；
- 插入和删除操作无需移动数据元素。
缺点：
- 数据元素必须保存后继元素的位置信息；
- 获取指定数据的元素操作需要顺序访问之前的元素。
工程详情：Github
