在学习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 }