在學習c語言提高-資料結構總結了筆記，并分享出來。有問題請及時聯系部落客：Alliswell_WP，轉載請注明出處。
03-c提高08day_資料結構
目錄：
1、資料結構理論
（1）資料結構概念
（2）算法的概念
2、線性表
（1）線性表基本概念
（2）線性表的順序存儲
練習1：
動态數組（+初始化、+插入、+周遊）
動态數組（+删除、+銷毀）
動态數組（分檔案實作）
練習2：
單向連結清單（版本一）——（+初始化、+插入、+周遊）
單向連結清單（版本一）——（+值删除、+位置删除、+大小、+清空、+銷毀）
練習3：
單向連結清單（版本二）
1、資料結構理論
（1）資料結構概念
資料結構是計算機存儲、組織資料的方式。資料結構是指互相之間存在一種或多種特定關系的資料元素的集合，通常情況下，精心選擇的資料結構可以帶來更高的運作或者存儲效率。資料結構往往同高效的檢索算法和索引技術有關。
資料結構是計算機存儲、組織資料的方式。
（2）算法的概念
算法是特定問題求解步驟的描述，在計算機中表現為指令的有限序列，算法是獨立存在的一種解決問題的方法和思想。
對于算法而言，語言并不重要，重要的是思想。
2、線性表
（1）線性表基本概念
線性結構是一種最簡單且常用的資料結構。線性結構的基本特點是節點之間滿足線性關系。本章讨論的動态數組、連結清單、棧、隊列都屈于線性結構。他們的共同之處，是節點中有且隻有一個開始節點和終端節點。按這種關系，可以把它們的所有節點排列成一個線性序列。但是，他們分别屈于幾種不同的抽象資料類型實作，它們之間的差別，主要就是操作的不同。
線性表是零個或者多個資料元素的有限序列，資料元素之問是有順序的，資料元素個數是有限的，資料元素的類型必須相同。
（2）線性表的順序存儲
通常線性表可以采用順序存儲和鍊式存儲。這節課我們主要探讨順序存儲結構以及對應的運算算法的實作。
采用順序存儲是表示線性表最簡單的方法，具體做法是：将線性表中的元素一個接一個的存儲在一塊連續的存儲區域中，這種順序表示的線性表也稱為順序表。
練習1：
動态數組（+初始化、+插入、+周遊）
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5
6 1.先把所需要的資料資訊結構定義下來
7 struct DynamicArray
8 {
9 //數組存儲元素的空間的首位址
10 void** addr;
11 //存儲資料的記憶體中最大能夠容納多少元素
12 int capacity;//容量
13 //目前存儲資料的記憶體中有多少個元素
14 int size;//大小
15 };
16
17 //初始化數組
18 struct DynamicArray* Init_DynamicArray(int capacity)
19 {
20 if(capacity <= 0)
21 {
22 return NULL;
23 }
24 struct DynamicArray* arr = malloc(sizeof(struct DynamicArray));
25 if(NULL == arr)
26 {
27 return NULL;
28 }
29 arr->capacity = capacity;
30 arr->addr = malloc(sizeof(void*) * arr->capacity);
31 arr->size = 0;
32
33 return arr;
34 }
35 //插入元素
36 void Insert_DynamicArray(struct DynamicArray* arr, int pos, void* data)
37 {
38 if(NULL == arr)
39 {
40 return;
41 }
42 if(NULL == data)
43 {
44 return;
45 }
46 if(pos < 0 || pos > arr->size)//檢查插入位置的合法性
47 {
48 pos = arr->size;
49 }
50 if(arr->size >= arr->capacity)
51 {
52 //1.申請一塊更大的記憶體空間
53 int newcapacity = arr->capacity * 2;
54 void** newspace = malloc(sizeof(void*) * newcapacity);
55
56 //2.将原來空間的資料拷貝到新空間
57 memcpy(newspace, arr->addr, sizeof(void*) * arr->capacity);
58
59 //3.釋放原來空間的記憶體
60 free(arr->addr);
61
62 //4.更新addr指向
63 arr->addr = newspace;
64 arr->capacity = newcapacity;
65 }
66
67 //移動元素，給pos位置空出位置來
68 for(int i = arr->size - 1; i >= pos; --i)
69 {
70 arr->addr[i + 1] = addr->addr[i];
71 }
72
73 //将新元素插入到pos位置
74 arr->addr[pos] = data;
75 arr->size++;
76 }
77 //周遊
78 void Foreach_DynamicArray(struct DynamicArray* arr, void(*_callback)(void*))
79 {
80 if(NULL == arr)
81 {
82 return;
83 }
84 if(NULL == _callback)
85 {
86 return;
87 }
88 for(int i = 0; i < arr->size; ++i)
89 {
90 _callback(arr->addr[i]);
91 }
92 }
93
94 //初始化數組
95 struct DynamicArray* Init_DynamicArray(int capacity);
96 //插入元素
97 void Insert_DynamicArray(struct DynamicArray* arr, int pos, void* data);
98 //周遊
99 void Foreach_DynamicArray(struct DynamicArray* arr, void(*_callback)(void*));
100
101
102 struct Person
103 {
104 char name[64];
105 int age;
106 };
107
108 void myPrint(void* data)
109 {
110 struct Person* person = (struct Person*)data;
111 printf("Name:%s Age:%d\n", person->name, person->age);
112 }
113
114 void test()
115 {
116 //建立動态數組
117 struct DynamicArray* da = Init_DynamicArray(5);
118 //動态數組添加元素
119 struct Person p1 = {"aaa", 10};
120 struct Person p2 = {"bbb", 20};
121 struct Person p3 = {"ccc", 30};
122 struct Person p4 = {"ddd", 40};
123 struct Person p5 = {"eee", 50};
124 struct Person p6 = {"fff", 60};
125
126 Insert_DynamicArray(da, 100, &p1);
127 Insert_DynamicArray(da, 100, &p2);
128 Insert_DynamicArray(da, 100, &p3);
129 Insert_DynamicArray(da, 100, &p4);
130 Insert_DynamicArray(da, 100, &p5);
131
132 printf("capacity:%d\n", da->capacity);//列印容量
133 Insert_DynamicArray(da, 100, &p6);//超出空間容量，擴大一倍
134 printf("capacity:%d\n", da->capacity);//列印容量
135
136 Foreach_DynamicArray(data, myPrint);
137 }
138
139 int main(){
140
141 test();
142
143 system("pause");
144 return EXIT_SUCCESS;
145 } 動态數組（+删除、+銷毀）
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5
6 1.先把所需要的資料資訊結構定義下來
7 struct DynamicArray
8 {
9 //數組存儲元素的空間的首位址
10 void** addr;
11 //存儲資料的記憶體中最大能夠容納多少元素
12 int capacity;//容量
13 //目前存儲資料的記憶體中有多少個元素
14 int size;//大小
15 };
16
17 //初始化數組
18 struct DynamicArray* Init_DynamicArray(int capacity)
19 {
20 if(capacity <= 0)
21 {
22 return NULL;
23 }
24 struct DynamicArray* arr = malloc(sizeof(struct DynamicArray));
25 if(NULL == arr)
26 {
27 return NULL;
28 }
29 arr->capacity = capacity;
30 arr->addr = malloc(sizeof(void*) * arr->capacity);
31 arr->size = 0;
32
33 return arr;
34 }
35 //插入元素
36 void Insert_DynamicArray(struct DynamicArray* arr, int pos, void* data)
37 {
38 if(NULL == arr)
39 {
40 return;
41 }
42 if(NULL == data)
43 {
44 return;
45 }
46 if(pos < 0 || pos > arr->size)//檢查插入位置的合法性
47 {
48 pos = arr->size;
49 }
50
51 //判斷空間是否足夠
52 if(arr->size >= arr->capacity)
53 {
54 //1.申請一塊更大的記憶體空間
55 int newcapacity = arr->capacity * 2;
56 void** newspace = malloc(sizeof(void*) * newcapacity);
57
58 //2.将原來空間的資料拷貝到新空間
59 memcpy(newspace, arr->addr, sizeof(void*) * arr->capacity);
60
61 //3.釋放原來空間的記憶體
62 free(arr->addr);
63
64 //4.更新addr指向
65 arr->addr = newspace;
66 arr->capacity = newcapacity;
67 }
68
69 //移動元素，給pos位置空出位置來
70 for(int i = arr->size - 1; i >= pos; --i)
71 {
72 arr->addr[i + 1] = addr->addr[i];
73 }
74
75 //将新元素插入到pos位置
76 arr->addr[pos] = data;
77 arr->size++;
78 }
79 //周遊
80 void Foreach_DynamicArray(struct DynamicArray* arr, void(*_callback)(void*))
81 {
82 if(NULL == arr)
83 {
84 return;
85 }
86 if(NULL == _callback)
87 {
88 return;
89 }
90 for(int i = 0; i < arr->size; ++i)
91 {
92 _callback(arr->addr[i]);
93 }
94 }
95
96 //位置删除
97 void RemoveByPos_DynamicArray(struct DynamicArray* arr, int pos)
98 {
99 if(NULL == arr)
100 {
101 return;
102 }
103 if(pos < 0 || pos > arr->size - 1)
104 {
105 return;
106 }
107
108 for(int i = pos; i < arr->size -1; ++i)
109 {
110 arr->addr[i] = arr->addr[i + 1];
111 }
112 arr->size--;
113 }
114
115 //按值删除
116 void RemoveByValue(struct DynamicArray* arr, void* data, int(*compare)(void*, void*))
117 {
118 if(NULL == arr)
119 {
120 return;
121 }
122 if(NULL == data)
123 {
124 return;
125 }
126 if(NULL == compare)
127 {
128 return;
129 }
130
131 for(int i = 0; i < arr->size; ++i)
132 {
133 if(compare(arr->addr[i], data))
134 {
135 RemoveByPos_DynamicArray(arr, i);
136 break;
137 }
138 }
139
140 }
141
142 //銷毀數組
143 void Destroy_DynamicArray(struct DynamicArray* arr)
144 {
145 if(NULL == arr)
146 {
147 return;
148 }
149 if(arr->addr != arr)
150 {
151 free(arr->addr);
152 arr->addr = NULL;
153 }
154 free(arr);
155 arr = NULL;
156 }
157
158 //初始化數組
159 struct DynamicArray* Init_DynamicArray(int capacity);
160 //插入元素
161 void Insert_DynamicArray(struct DynamicArray* arr, int pos, void* data);
162 //周遊
163 void Foreach_DynamicArray(struct DynamicArray* arr, void(*_callback)(void*));
164
165
166 struct Person
167 {
168 char name[64];
169 int age;
170 };
171
172 void myPrint(void* data)
173 {
174 struct Person* person = (struct Person*)data;
175 printf("Name:%s Age:%d\n", person->name, person->age);
176 }
177
178 int myCompare(void* d1, void* d2)
179 {
180 struct person* p1 = (struct Person*)d1;
181 struct person* p2 = (struct Person*)d2;
182
183 return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;
184 }
185
186
187 void test()
188 {
189 //建立動态數組
190 struct DynamicArray* da = Init_DynamicArray(5);
191 //動态數組添加元素
192 struct Person p1 = {"aaa", 10};
193 struct Person p2 = {"bbb", 20};
194 struct Person p3 = {"ccc", 30};
195 struct Person p4 = {"ddd", 40};
196 struct Person p5 = {"eee", 50};
197 struct Person p6 = {"fff", 60};
198
199 Insert_DynamicArray(da, 0, &p1);
200 Insert_DynamicArray(da, 0, &p2);
201 Insert_DynamicArray(da, 0, &p3);
202 Insert_DynamicArray(da, 1, &p4);
203 Insert_DynamicArray(da, 1, &p5);
204
205 printf("capacity:%d\n", da->capacity);//列印容量
206 Insert_DynamicArray(da, 100, &p6);//超出空間容量，擴大一倍3 5 4 2 1 6
207 printf("capacity:%d\n", da->capacity);//列印容量
208
209 Foreach_DynamicArray(data, myPrint);
210
211 printf("-----------------\n");
212 RemoveByPos_DynamicArray(data, 2);//3 5 2 1 6
213 Foreach_DynamicArray(data, myPrint);
214
215 printf("-----------------\n");
216 struct Person pDel = {"aaa", 10};
217 RemoveByValue(da, &pDel, myCompare);
218 Foreach_DynamicArray(data, myPrint);
219
220 //銷毀
221 Destroy_DynamicArray(da);
222 }
223
224 int main(){
225
226 test();
227
228 system("pause");
229 return EXIT_SUCCESS;
230 } 動态數組（分檔案實作）
動态數組.c
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5 #inlcude"DynamicArray.h"
6
7
8 struct Person
9 {
10 char name[64];
11 int age;
12 };
13
14 void myPrint(void* data)
15 {
16 struct Person* person = (struct Person*)data;
17 printf("Name:%s Age:%d\n", person->name, person->age);
18 }
19
20 int myCompare(void* d1, void* d2)
21 {
22 struct person* p1 = (struct Person*)d1;
23 struct person* p2 = (struct Person*)d2;
24
25 return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;
26 }
27
28
29 void test()
30 {
31 //建立動态數組
32 struct DynamicArray* da = Init_DynamicArray(5);
33 //動态數組添加元素
34 struct Person p1 = {"aaa", 10};
35 struct Person p2 = {"bbb", 20};
36 struct Person p3 = {"ccc", 30};
37 struct Person p4 = {"ddd", 40};
38 struct Person p5 = {"eee", 50};
39 struct Person p6 = {"fff", 60};
40
41 Insert_DynamicArray(da, 0, &p1);
42 Insert_DynamicArray(da, 0, &p2);
43 Insert_DynamicArray(da, 0, &p3);
44 Insert_DynamicArray(da, 1, &p4);
45 Insert_DynamicArray(da, 1, &p5);
46
47 printf("capacity:%d\n", da->capacity);//列印容量
48 Insert_DynamicArray(da, 100, &p6);//超出空間容量，擴大一倍3 5 4 2 1 6
49 printf("capacity:%d\n", da->capacity);//列印容量
50
51 Foreach_DynamicArray(data, myPrint);
52
53 printf("-----------------\n");
54 RemoveByPos_DynamicArray(data, 2);//3 5 2 1 6
55 Foreach_DynamicArray(data, myPrint);
56
57 printf("-----------------\n");
58 struct Person pDel = {"aaa", 10};
59 RemoveByValue(da, &pDel, myCompare);
60 Foreach_DynamicArray(data, myPrint);
61
62 //銷毀
63 Destroy_DynamicArray(da);
64 }
65
66 int main(){
67
68 test();
69
70 system("pause");
71 return EXIT_SUCCESS;
72 } DynamicArray.h
1 #pragma once
2
3 #include<stdlib.h>
4 #include<stdio.h>
5 #include<string.h>
6
7 #ifdef __cplusplus
8 extern "C"{
9
10 1.先把所需要的資料資訊結構定義下來
11 struct DynamicArray
12 {
13 //數組存儲元素的空間的首位址
14 void** addr;
15 //存儲資料的記憶體中最大能夠容納多少元素
16 int capacity;//容量
17 //目前存儲資料的記憶體中有多少個元素
18 int size;//大小
19 };
20
21 //初始化數組
22 struct DynamicArray* Init_DynamicArray(int capacity);
23 //插入元素
24 void Insert_DynamicArray(struct DynamicArray* arr, int pos, void* data);
25 //周遊
26 void Foreach_DynamicArray(struct DynamicArray* arr, void(*_callback)(void*));
27 //位置删除
28 void RemoveByPos_DynamicArray(struct DynamicArray* arr, int pos);
29 //按值删除
30 void RemoveByValue(struct DynamicArray* arr, void* data, int(*compare)(void*, void*));
31 //銷毀數組
32 void Destroy_DynamicArray(struct DynamicArray* arr);
33
34 #ifdef __cplusplus
35 }
36 #endif DynamicArray.c
1 #inlcude"DynamicArray.h"
2
3 1.先把所需要的資料資訊結構定義下來
4 struct DynamicArray
5 {
6 //數組存儲元素的空間的首位址
7 void** addr;
8 //存儲資料的記憶體中最大能夠容納多少元素
9 int capacity;//容量
10 //目前存儲資料的記憶體中有多少個元素
11 int size;//大小
12 };
13
14 //初始化數組
15 struct DynamicArray* Init_DynamicArray(int capacity)
16 {
17 if(capacity <= 0)
18 {
19 return NULL;
20 }
21 struct DynamicArray* arr = malloc(sizeof(struct DynamicArray));
22 if(NULL == arr)
23 {
24 return NULL;
25 }
26 arr->capacity = capacity;
27 arr->addr = malloc(sizeof(void*) * arr->capacity);
28 arr->size = 0;
29
30 return arr;
31 }
32 //插入元素
33 void Insert_DynamicArray(struct DynamicArray* arr, int pos, void* data)
34 {
35 if(NULL == arr)
36 {
37 return;
38 }
39 if(NULL == data)
40 {
41 return;
42 }
43 if(pos < 0 || pos > arr->size)//檢查插入位置的合法性
44 {
45 pos = arr->size;
46 }
47
48 //判斷空間是否足夠
49 if(arr->size >= arr->capacity)
50 {
51 //1.申請一塊更大的記憶體空間
52 int newcapacity = arr->capacity * 2;
53 void** newspace = malloc(sizeof(void*) * newcapacity);
54
55 //2.将原來空間的資料拷貝到新空間
56 memcpy(newspace, arr->addr, sizeof(void*) * arr->capacity);
57
58 //3.釋放原來空間的記憶體
59 free(arr->addr);
60
61 //4.更新addr指向
62 arr->addr = newspace;
63 arr->capacity = newcapacity;
64 }
65
66 //移動元素，給pos位置空出位置來
67 for(int i = arr->size - 1; i >= pos; --i)
68 {
69 arr->addr[i + 1] = addr->addr[i];
70 }
71
72 //将新元素插入到pos位置
73 arr->addr[pos] = data;
74 arr->size++;
75 }
76 //周遊
77 void Foreach_DynamicArray(struct DynamicArray* arr, void(*_callback)(void*))
78 {
79 if(NULL == arr)
80 {
81 return;
82 }
83 if(NULL == _callback)
84 {
85 return;
86 }
87 for(int i = 0; i < arr->size; ++i)
88 {
89 _callback(arr->addr[i]);
90 }
91 }
92
93 //位置删除
94 void RemoveByPos_DynamicArray(struct DynamicArray* arr, int pos)
95 {
96 if(NULL == arr)
97 {
98 return;
99 }
100 if(pos < 0 || pos > arr->size - 1)
101 {
102 return;
103 }
104
105 for(int i = pos; i < arr->size -1; ++i)
106 {
107 arr->addr[i] = arr->addr[i + 1];
108 }
109 arr->size--;
110 }
111
112 //按值删除
113 void RemoveByValue(struct DynamicArray* arr, void* data, int(*compare)(void*, void*))
114 {
115 if(NULL == arr)
116 {
117 return;
118 }
119 if(NULL == data)
120 {
121 return;
122 }
123 if(NULL == compare)
124 {
125 return;
126 }
127
128 for(int i = 0; i < arr->size; ++i)
129 {
130 if(compare(arr->addr[i], data))
131 {
132 RemoveByPos_DynamicArray(arr, i);
133 break;
134 }
135 }
136
137 }
138
139 //銷毀數組
140 void Destroy_DynamicArray(struct DynamicArray* arr)
141 {
142 if(NULL == arr)
143 {
144 return;
145 }
146 if(arr->addr != arr)
147 {
148 free(arr->addr);
149 arr->addr = NULL;
150 }
151 free(arr);
152 arr = NULL;
153 } 練習2：單向連結清單（版本一）——（+初始化、+插入、+周遊）
記憶體模型圖如下：
單向連結清單（版本一）.c
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5 #include"LinkList.h"
6
7 struct Person
8 {
9 char name[64];
10 int age;
11 };
12
13 void myPrint(void* data)
14 {
15 struct Person* person = (struct Person*)data;
16 printf("Name:%s Age:%d\n", person->name, person->age);
17 }
18
19 void test()
20 {
21 //建立連結清單
22 LinkList list = Init_LinkList();
23
24 //建立資料
25 struct Person p1 = {"aaa", 10};
26 struct Person p2 = {"bbb", 20};
27 struct Person p3 = {"ccc", 30};
28 struct Person p4 = {"ddd", 40};
29 struct Person p5 = {"eee", 50};
30 struct Person p6 = {"fff", 60};
31 struct Person p7 = {"ggg", 70};
32
33 //插入資料
34 Insert_LinkList(list, 0, &p1);
35 Insert_LinkList(list, 0, &p2);
36 Insert_LinkList(list, 1, &p3);//2 3 1
37 Insert_LinkList(list, 2, &p4);//2 3 4 1
38 Insert_LinkList(list, 20, &p5);//2 3 4 1 5
39 Insert_LinkList(list, 3, &p6);//2 3 6 4 1 5
40 Insert_LinkList(list, 6, &p7);//2 3 6 4 1 7 5
41
42 Foreach_LinkList(list, myPrint);
43 }
44
45 int main(){
46
47 test();
48
49 system("pause");
50 return EXIT_SUCCESS;
51 } LinkList.h
1 #pragma once
2
3 #include<stdlib.h>
4 #include<string.h>
5 #include<stdio.h>
6
7 #ifdef __cpluscplus
8 extern "C"{
9 #endif
10
11
12
13 typedef void* LinkList;
14 typedef void(*FOREACH)(void*);
15
16 //初始化連結清單
17 LinkList Init_LinkList();
18 //插入結點
19 void Insert_LinkList(LinkList list, int pos, void* data);
20 //周遊連結清單
21 void Foreach_LinkList(LinkList list, FOREACH myforeach);
22
23
24 #ifdef __cpluscplus
25 }
26 #endif LinkList.c
1 #include"LinkList.h"
2
3 //連結清單結點資料類型
4 struct LinkNode
5 {
6 void* data;
7 struct LinkNode* next;
8 };
9
10 //連結清單資料類型
11 struct LList
12 {
13 struct LinkNode header;
14 int size;
15 };
16
17 //初始化連結清單
18 LinkList Init_LinkList()
19 {
20 struct LList* list = malloc(sizeof(struct LList));
21 if(NULL == list)
22 {
23 return NULL;
24 }
25 list->header.data = NULL;
26 list->header.next = NULL;
27 list->size = 0;
28
29 return list;
30 }
31 //插入結點
32 void Insert_LinkList(LinkList list, int pos, void* data)
33 {
34 if(NULL == list)
35 {
36 return;
37 }
38 if(NULL == data)
39 {
40 return;
41 }
42
43 struct LList* mylist = (struct LList*)list;
44
45 if(pos < 0 || pos > mylist->size)
46 {
47 pos = mylist->size;
48 }
49
50 //查找插入位置
51 struct LinkNode* pCurrent = &(mylist->header);
52 for(int i = 0; i < pos; ++i)
53 {
54 pCurrent = pCurrent->next;
55 }
56
57 //建立新結點
58 struct LinkNode* newnode = malloc(sizeof(struct LinkNode));
59 newnode->data = data;
60 newnode->next = NULL;
61
62 //新結點插入到連結清單中
63 newnode->next = pCurrent->next;
64 pCurrent->next = newnode;
65
66 mylist->size++;
67 }
68 //周遊連結清單
69 void Foreach_LinkList(LinkList list, FOREACH myforeach)//回調函數
70 {
71 if(NULL == list)
72 {
73 return;
74 }
75 if(NULL == myforeach)
76 {
77 return;
78 }
79
80 struct LList* mylist = (struct LList*)list;
81
82 struct LinkNode* pCurrent = mylist->header.next;
83
84 while(pCurrent != NULL)
85 {
86 myforeach(pCurrent->data);
87 pCurrent = pCurrent->next;
88 }
89
90 } 單向連結清單（版本一）——（+值删除、+位置删除、+大小、+清空、+銷毀）
單向連結清單（版本一）.c
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5 #include"LinkList.h"
6
7 struct Person
8 {
9 char name[64];
10 int age;
11 };
12
13 void myPrint(void* data)
14 {
15 struct Person* person = (struct Person*)data;
16 printf("Name:%s Age:%d\n", person->name, person->age);
17 }
18
19 int myCompare(void* d1, void* d2)
20 {
21 struct Person* p1 = (struct Person*)d1;
22 struct Person* p2 = (struct Person*)d2;
23
24 #if 0
25 if(strcmp(p1->name, p2->name) == 0 && p1->age == p2->age)
26 {
27 return 1;
28 }
29 return 0;
30 #endif
31 return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;
32 }
33
34 void test()
35 {
36 //建立連結清單
37 LinkList list = Init_LinkList();
38
39 //建立資料
40 struct Person p1 = {"aaa", 10};
41 struct Person p2 = {"bbb", 20};
42 struct Person p3 = {"ccc", 30};
43 struct Person p4 = {"ddd", 40};
44 struct Person p5 = {"eee", 50};
45 struct Person p6 = {"fff", 60};
46 struct Person p7 = {"ggg", 70};
47
48 //插入資料
49 Insert_LinkList(list, 0, &p1);
50 Insert_LinkList(list, 0, &p2);
51 Insert_LinkList(list, 1, &p3);//2 3 1
52 Insert_LinkList(list, 2, &p4);//2 3 4 1
53 Insert_LinkList(list, 20, &p5);//2 3 4 1 5
54 Insert_LinkList(list, 3, &p6);//2 3 6 4 1 5
55 Insert_LinkList(list, 6, &p7);//2 3 6 4 1 7 5
56
57 Foreach_LinkList(list, myPrint);
58
59 printf("----------\n");
60 printf("List Size:%d\n", Size_LinkList(list));
61 RemoveByPos_LinkList(list, 3);
62 printf("----------\n");
63 Foreach_LinkList(list, myPrint);
64
65 struct Person pDelPerson = {"ggg", 70};
66 RemoveByVal_LinkList(list, &pDelPerson, myCompare);
67 printf("----------\n");
68 Foreach_LinkList(list, myPrint);
69
70 //清空連結清單
71 Clear_LinkList(list);
72 printf("----------\n");
73 Foreach_LinkList(list, myPrint);
74
75 //銷毀連結清單
76 Destroy_LinkList(list);
77 }
78
79 int main(){
80
81 test();
82
83 system("pause");
84 return EXIT_SUCCESS;
85 } LinkList.h
1 #pragma once
2
3 #include<stdlib.h>
4 #include<string.h>
5 #include<stdio.h>
6
7 #ifdef __cpluscplus
8 extern "C"{
9 #endif
10
11
12
13 typedef void* LinkList;
14 typedef void(*FOREACH)(void*);
15 typedef int*(*COMPARE)(void*, void*);
16
17 //初始化連結清單
18 LinkList Init_LinkList();
19 //插入結點
20 void Insert_LinkList(LinkList list, int pos, void* data);
21 //周遊連結清單
22 void Foreach_LinkList(LinkList list, FOREACH myforeach);
23 //按位置删除
24 void RemoveByPos_LinkList(LinkList list, int pos);
25 //按值删除
26 void RemoveByVal_LinkList(LinkList list, void* data, COMPARE compare);
27 //清空連結清單
28 void Clear_LinkList(LinkList list);
29 //大小
30 int Size_LinkList(LinkList list);
31 //銷毀連結清單
32 void Destroy_LinkList(LinkList list);
33
34 #ifdef __cpluscplus
35 }
36 #endif LinkList.c
1 #include"LinkList.h"
2
3 //連結清單結點資料類型
4 struct LinkNode
5 {
6 void* data;
7 struct LinkNode* next;
8 };
9
10 //連結清單資料類型
11 struct LList
12 {
13 struct LinkNode header;
14 int size;
15 };
16
17 //初始化連結清單
18 LinkList Init_LinkList()
19 {
20 struct LList* list = malloc(sizeof(struct LList));
21 if(NULL == list)
22 {
23 return NULL;
24 }
25 list->header.data = NULL;
26 list->header.next = NULL;
27 list->size = 0;
28
29 return list;
30 }
31 //插入結點
32 void Insert_LinkList(LinkList list, int pos, void* data)
33 {
34 if(NULL == list)
35 {
36 return;
37 }
38 if(NULL == data)
39 {
40 return;
41 }
42
43 struct LList* mylist = (struct LList*)list;
44
45 if(pos < 0 || pos > mylist->size)
46 {
47 pos = mylist->size;
48 }
49
50 //查找插入位置
51 struct LinkNode* pCurrent = &(mylist->header);
52 for(int i = 0; i < pos; ++i)
53 {
54 pCurrent = pCurrent->next;
55 }
56
57 //建立新結點
58 struct LinkNode* newnode = malloc(sizeof(struct LinkNode));
59 newnode->data = data;
60 newnode->next = NULL;
61
62 //新結點插入到連結清單中
63 newnode->next = pCurrent->next;
64 pCurrent->next = newnode;
65
66 mylist->size++;
67 }
68 //周遊連結清單
69 void Foreach_LinkList(LinkList list, FOREACH myforeach)//回調函數
70 {
71 if(NULL == list)
72 {
73 return;
74 }
75 if(NULL == myforeach)
76 {
77 return;
78 }
79
80 struct LList* mylist = (struct LList*)list;
81
82 struct LinkNode* pCurrent = mylist->header.next;
83
84 while(pCurrent != NULL)
85 {
86 myforeach(pCurrent->data);
87 pCurrent = pCurrent->next;
88 }
89
90 }
91
92 //按位置删除
93 void RemoveByPos_LinkList(LinkList list, int pos)
94 {
95 if(NULL == list)
96 {
97 return;
98 }
99 struct LList* mylist = (struct LList*)list;
100
101 if(pos < 0 || pos > mylist->size - 1)
102 {
103 return;
104 }
105 //找位置
106 struct LinkNode* pCurrent = &(mylist->header);
107 for(int i = 0; i < pos; ++i)
108 {
109 pCurrent = pCurrent->next;
110 }
111
112 //先儲存待删除結點
113 struct LinkNode* pDel = pCurrent->next;
114 //重建立立待删除結點的前驅和後繼結點關系
115 pCurrent->next = pDel->next;
116 //釋放删除結點記憶體
117 free(pDel);
118 pDel = NULL;
119
120 mylist->size--;
121 }
122 //按值删除
123 void RemoveByVal_LinkList(LinkList list, void* data, COMPARE compare)
124 {
125 if(NULL == list)
126 {
127 return;
128 }
129 if(NULL == data)
130 {
131 return;
132 }
133 if(NULL == compare)
134 {
135 return;
136 }
137
138 struct LList* mylist = (struct LList*)list;
139 //輔助指針變量
140 struct LinkNode* pPrev = &(mylist->header);
141 struct LinkNode* pCurrent = pPrev->next;
142 while(pCurrent != NULL)
143 {
144 if(compare(pCurrent->data, data))
145 {
146 //找到了
147 pPrev->next = pCurrent->next;
148 //釋放删除結點記憶體
149 free(pCurrent);
150 pCurrent = NULL;
151 mylist->size--;
152 break;
153 }
154
155 pPrev = pCurrent;
156 pCurrent = pCurrent->next;
157 }
158 }
159 //清空連結清單
160 void Clear_LinkList(LinkList list)
161 {
162 if(NULL == list)
163 {
164 return;
165 }
166 struct LList* mylist = (struct LList*)list;
167
168 //輔助指針變量
169 struct LinkNode* pCurrent = mylist->header.next;
170
171 while(pCurrent != NULL)
172 {
173 //先緩存下一個結點的位址
174 struct LinkNode* pNext = pCurrent->next;
175 //釋放目前結點記憶體
176 free(pCurrent);
177
178 pCurrent = pNext;
179 }
180 mylist->header.next = NULL;
181 //把size更新
182 mylist->size = 0;
183
184 }
185 //大小
186 int Size_LinkList(LinkList list)
187 {
188 if(NULL == list)
189 {
190 return -1;
191 }
192 struct LList* mylist = (struct LList*)list;
193
194 return mylist->size;
195 }
196 //銷毀連結清單
197 void Destroy_LinkList(LinkList list)
198 {
199 if(NULL == list)
200 {
201 return;
202 }
203
204 //清空連結清單
205 Clear_LinkList(list);
206 free(list);
207 list = NULL;
208 } 練習3：單向連結清單（版本二）
記憶體模型圖如下：
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5
6 struct LinkNode
7 {
8 struct LinkNode* next;
9 };
10
11 struct Person
12 {
13 struct LinkNode node;//給四個位元組存位址
14 char name[64];
15 int age;
16 };
17
18 void test()
19 {
20 struct Person p1 = {NULL, "aaa", 10};
21 struct Person p2 = {NULL, "bbb", 20};
22 struct Person p3 = {NULL, "ccc", 30};
23 struct Person p4 = {NULL, "ddd", 40};
24 struct Person p5 = {NULL, "eee", 50};
25
26 struct LinkNode* pp1 = (struct LinkNode*)&p1;
27 struct LinkNode* pp2 = (struct LinkNode*)&p2;
28 struct LinkNode* pp3 = (struct LinkNode*)&p3;
29 struct LinkNode* pp4 = (struct LinkNode*)&p4;
30 struct LinkNode* pp5 = (struct LinkNode*)&p5;
31
32 pp1->next = pp2;
33 pp2->next = pp3;
34 pp3->next = pp4;
35 pp4->next = pp5;
36 pp5->next = NULL;
37
38 struct LinkNode* pCurrent = pp1;
39 while(pCurrent != NULL)
40 {
41 struct Person* person = (struct Person*)pCurrent;
42 printf("Name:%s Age:%d\n", person->name, person->age);
43
44 pCurrent = pCurrent->next;
45 }
46
47 }
48
49 int main(){
50
51 test();
52
53 system("pause");
54 return EXIT_SUCCESS;
55 }