在學習c語言提高-資料結構總結了筆記，并分享出來。有問題請及時聯系部落客：Alliswell_WP，轉載請注明出處。
03-c提高09day_資料結構
目錄：
1、單向連結清單
練習1：單向連結清單（版本二）——（+初始化、+插入、+周遊）
練習2：單向連結清單（版本二）——（+删除、+銷毀）
2、受限線性表——棧（Stack)
（1）棧的基本概念
（2）棧的順序存儲
練習1：棧的順序存儲
（3）棧的鍊式存儲
練習2：棧的鍊式存儲
（4）棧的應用（案例：就近比對）
練習：棧的應用：就近比對
1、單向連結清單
（推薦版本二：代碼少）
練習1：單向連結清單（版本二）——（+初始化、+插入、+周遊）
記憶體模型圖如下：
單向連結清單(版本二).c
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5
6 //連結清單結點資料結構
7 struct LinkNode
8 {
9 struct LinkNode* next;
10 };
11
12 //連結清單結構體
13 struct LList
14 {
15 struct LinkNode header;//頭結點給四個位元組存位址
16 int size;
17 };
18
19 typedef void* LinkList;
20
21 //初始化連結清單
22 LinkList Init_LinkList()
23 {
24 struct LList* list = malloc(sizeof(struct LList));
25 if(NULL = list)
26 {
27 return NULL;
28 }
29 list->header.next = NULL;
30 list->size = 0;
31
32 return list;
33 }
34 //插入
35 void Insert_LinkList(LinkList list, int position, void* data)
36 {
37 if(NULL = list)
38 {
39 return;
40 }
41 if(NULL = data)
42 {
43 return;
44 }
45 struct LList* mylist = (struct LList*)list;
46 struct LinkNode* mynode = (struct LinNode*)data;
47
48 if(position < 0 || position > mylist->size)
49 {
50 position = mylist->size;
51 }
52
53 //找位置（找到position位置的前一個位置）
54 struct LinkNode* pCurrent = &(mylist->header);
55 for(int i = 0; i < position; ++i)
56 {
57 pCurrent = pCurrent->next;
58 }
59 //資料傳入連結表
60 mynode->next = pCurrent->next;
61 pCurrent->next = mynode;
62
63 mylist->size++;
64 }
65 //周遊
66 void Foreach_LinkList(LinkList list, void(*foreach)(void*))
67 {
68 if(NULL = list)
69 {
70 return;
71 }
72 if(NULL = foreach)
73 {
74 return;
75 }
76
77 struct LList* mylist = (struct LList*)list;
78 struct LinkNode* pCurrent = &(mylist->header.next);
79
80 while(pCurrent != NULL)
81 {
82 myforeach(pCurrent);
83 pCurrent = pCurrent->next;
84 }
85
86 }
87
88 struct Person
89 {
90 struct LinkNode node;//此處不能用指針，雙連結清單會出問題，位址的位置
91 char name[64];
92 int age;
93 };
94
95 void myPrint(void* data)
96 {
97 struct Person* person = (struct Person*)data;
98 printf("Name:%s Age:%d\n", person->name, person->age);
99 }
100
101 void test()
102 {
103 //初始化連結清單
104 LinkList list = Init_LinkList();
105 //建立資料
106 struct Person p1 = { NULL, "aaa", 10};
107 struct Person p2 = { NULL, "bbb", 20};
108 struct Person p3 = { NULL, "ccc", 30};
109 struct Person p4 = { NULL, "ddd", 40};
110 struct Person p5 = { NULL, "eee", 50};
111 struct Person p6 = { NULL, "fff", 60};
112
113 //插入資料
114 Insert_LinkList(list, 0, &p1);
115 Insert_LinkList(list, 0, &p2);
116 Insert_LinkList(list, 0, &p3;
117 Insert_LinkList(list, 0, &p4);
118 Insert_LinkList(list, 0, &p5);
119 Insert_LinkList(list, 0, &p6);
120
121 //周遊
122 Foreach_LinkList(list, myPrint);
123 }
124
125 int main(){
126
127 test();
128
129 system("pause");
130 return EXIT_SUCCESS;
131 } 練習2：單向連結清單（版本二）——（+删除、+銷毀）
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5
6 //連結清單結點資料結構
7 struct LinkNode
8 {
9 struct LinkNode* next;
10 };
11
12 //連結清單結構體
13 struct LList
14 {
15 struct LinkNode header;//頭結點給四個位元組存位址
16 int size;
17 };
18
19 typedef void* LinkList;
20
21 //初始化連結清單
22 LinkList Init_LinkList()
23 {
24 struct LList* list = malloc(sizeof(struct LList));
25 if(NULL = list)
26 {
27 return NULL;
28 }
29 list->header.next = NULL;
30 list->size = 0;
31
32 return list;
33 }
34 //插入
35 void Insert_LinkList(LinkList list, int position, void* data)
36 {
37 if(NULL = list)
38 {
39 return;
40 }
41 if(NULL = data)
42 {
43 return;
44 }
45 struct LList* mylist = (struct LList*)list;
46 struct LinkNode* mynode = (struct LinNode*)data;
47
48 if(position < 0 || position > mylist->size)
49 {
50 position = mylist->size;
51 }
52
53 //找位置（找到position位置的前一個位置）
54 struct LinkNode* pCurrent = &(mylist->header);
55 for(int i = 0; i < position; ++i)
56 {
57 pCurrent = pCurrent->next;
58 }
59 //資料傳入連結表
60 mynode->next = pCurrent->next;
61 pCurrent->next = mynode;
62
63 mylist->size++;
64 }
65 //周遊
66 void Foreach_LinkList(LinkList list, void(*foreach)(void*))
67 {
68 if(NULL = list)
69 {
70 return;
71 }
72 if(NULL = foreach)
73 {
74 return;
75 }
76
77 struct LList* mylist = (struct LList*)list;
78 struct LinkNode* pCurrent = &(mylist->header.next);
79
80 while(pCurrent != NULL)
81 {
82 struct LinkNode* pNext = pCurrent->next;
83 myforeach(pCurrent);
84 pCurrent = pNext;
85 }
86
87 }
88
89 //删除結點
90 void RemoveByPos_LinkList(LinkList List, int position)
91 {
92 if(NULL == list)
93 {
94 return;
95 }
96
97 struct LList* mylist = (struct LList*)list;
98
99 if(position < 0 || position > mylist->size - 1)
100 {
101 return;
102 }
103
104 //輔助指針
105 struct LinkNode* pCurrent = &(mylist->header);
106 for(int i = 0; i < position; ++i)
107 {
108 pCurrent = pCurrent->next;
109 }
110
111 //緩存下待删除結點
112 struct LinkNode* pDel = pCurrent->next;
113
114 //重建立立待删除結點的前驅和後繼結點關系
115 pCurrent->next = pDel->next;
116
117 mylist->size--;
118 }
119 //銷毀
120 void Destroy_LinkList(LinkList list)
121 {
122 if(NULL == list)
123 {
124 return;
125 }
126
127 free(list);
128 list = NULL;
129 }
130
131 struct Person
132 {
133 struct LinkNode node;//此處不能用指針，雙連結清單會出問題，位址的位置！
134 char name[64];
135 int age;
136 };
137
138 void myPrint(void* data)
139 {
140 struct Person* person = (struct Person*)data;
141 printf("Name:%s Age:%d\n", person->name, person->age);
142 }
143
144 void test()
145 {
146 //初始化連結清單
147 LinkList list = Init_LinkList();
148 //建立資料（缺點：不能插入重複資料，會出問題！）
149 struct Person p1 = { NULL, "aaa", 10};
150 struct Person p2 = { NULL, "bbb", 20};
151 struct Person p3 = { NULL, "ccc", 30};
152 struct Person p4 = { NULL, "ddd", 40};
153 struct Person p5 = { NULL, "eee", 50};
154 struct Person p6 = { NULL, "fff", 60};
155
156 //插入資料
157 Insert_LinkList(list, 0, &p1);
158 Insert_LinkList(list, 0, &p2);
159 Insert_LinkList(list, 0, &p3;
160 Insert_LinkList(list, 0, &p4);
161 Insert_LinkList(list, 0, &p5);
162 Insert_LinkList(list, 0, &p6);
163
164 //周遊
165 Foreach_LinkList(list, myPrint);
166
167 //删除
168 RemoveByPos_LinkList(list, 3);
169 printf("---------------\n");
170
171 //周遊
172 Foreach_LinkList(list, myPrint);
173
174 //銷毀
175 Destroy_LinkList(list);
176 }
177
178 int main(){
179
180 test();
181
182 system("pause");
183 return EXIT_SUCCESS;
184 } 2、受限線性表——棧（Stack)
（1）棧的基本概念
>概念：
首先它是一個線性表，也就是說，棧元素具有線性關系，即前驅後繼關系。隻不過它是一種特殊的線性表而已。定義中說是線上性表的表尾進行插入和删除操作，這裡表尾是指棧頂，而不是棧底。
>特性
它的特殊之處在于限制了這個線性表的插入和删除的位置，它始終隻在棧頂進行。這也就使得：棧應是固定的，最先進棧的隻能在棧底。（不支援随機存取）
>操作
■棧的插入操作，叫做進棧，也稱壓棧。類似子彈入彈夾。
■棧的湖除操作，叫做出棧，也有的叫做貓棧，退棧。如同彈夾中的子彈出夾。
（2）棧的順序存儲
>基本概念
棧的順序存儲結構簡稱順序棧，它是運算受限制的順序表。順序棧的存儲結構是：利用一組位址連續的的存儲單元依次存放自棧底到棧頂的資料元素，同時附設指針 top隻是棧頂元素在順序表中的位置。
>設計與實作
因為棧是一種特殊的線性表，是以棧的順序存儲可以通過順序線性表來實作。
練習1：棧的順序存儲
棧的順序存儲.c
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5 #include"SeqStack.h"
6 struct Person
7 {
8 char name[64];
9 int age;
10 };
11
12 void test()
13 {
14 //初始化棧
15 SeqStack stack = Init_SeqStack();
16
17 //建立資料
18 struct Person p1 = { "aaa", 10};
19 struct Person p2 = { "bbb", 20};
20 struct Person p3 = { "ccc", 30};
21 struct Person p4 = { "ddd", 40};
22 struct Person p5 = { "eee", 50};
23 struct Person p6 = { "fff", 60};
24
25 //資料入棧
26 Push_SeqStack(stack, &p1);
27 Push_SeqStack(stack, &p2);
28 Push_SeqStack(stack, &p3);
29 Push_SeqStack(stack, &p4);
30 Push_SeqStack(stack, &p5);
31 Push_SeqStack(stack, &p6);
32
33 //輸出棧中所有元素
34 while(Size_SeqStack(stack) > 0)
35 {
36 //獲得棧頂元素
37 struct Person* person = (struct Person*)Top_SeqStack(stack);
38 //列印
39 printf("Name:%s Age:%d\n", person->name, person->age);
40 //彈出棧頂元素
41 Pop_SeqStack(stack);
42 }
43
44 printf("Size:%d\n", Size_SeqStack(stack));
45
46 //銷毀棧
47 Destroy_SeqStack(stack);
48 stack = NULL;
49 }
50
51 int main(){
52
53 test();
54
55 system("pause");
56 return EXIT_SUCCESS;
57 } SeqStack.h
1 #pragma once
2
3 #include<stdlib.h>
4 #include<string.h>//memset
5
6 #ifdef __cplusplus
7 extern "C"{
8 #endif
9
10
11 #define MAX 1024
12
13 //順序棧資料結構
14 struct SStack
15 {
16 void* data[MAX];//存放資料的數組
17 int size;//棧中元素的個數
18 }
19
20 //數組高下标的位置當做棧頂，因為不需要移動數組中的元素在插入和删除中
21
22 //初始化
23 SeqStack Init_SeqStack();
24 //入棧
25 void Push_SeqStack(SeqStack stack, void* data);
26 //出棧
27 void Pop_SeqStack(SeqStack stack);
28 //獲得棧頂元素
29 void* Top_SeqStack(SeqStack stack);
30 //獲得棧的大小
31 int Size_SeqStack(SeqStack stack);
32 //銷毀棧
33 void Destroy_SeqStack(SeqStack stack);
34
35 #ifdef __cplusplus
36 }
37 #endif SeqStack.c
1 #include"SeqStack.h"
2
3 //初始化
4 SeqStack Init_SeqStack()
5 {
6 struct SStack* stack = malloc(sizeof(struct SStack));
7 if(NULL == stack)
8 {
9 return NULL;
10 }
11
12 memset(stack, 0, sizeof(struct SStack));
13 stack->size = 0;
14
15 return stack;
16 }
17 //入棧
18 void Push_SeqStack(SeqStack stack, void* data)
19 {
20 if(NULL == stack)
21 {
22 return;
23 }
24 if(NULL == data)
25 {
26 return;
27 }
28
29 struct SStack* s = (struct SStack*)stack;
30
31 s->data[s->size] = data;
32 s->size++;
33 }
34 //出棧
35 void Pop_SeqStack(SeqStack stack)
36 {
37 if(NULL == stack)
38 {
39 return;
40 }
41 struct SStack* s = (struct SStack*)stack;
42
43 if(s->size == 0)
44 {
45 return;
46 }
47
48 s->data[s->size-1] = NULL;//此句可有可無，有資料會把這塊記憶體覆寫
49 s->size--;
50 }
51 //獲得棧頂元素
52 void* Top_SeqStack(SeqStack stack)
53 {
54 if(NULL == stack)
55 {
56 return NULL;
57 }
58
59 struct SStack* s = (struct SStack*)stack;
60
61 if(s->size == 0)
62 {
63 return NULL;
64 }
65
66 return s->data[s->size-1];
67 }
68 //獲得棧的大小
69 int Size_SeqStack(SeqStack stack)
70 {
71 if(NULL == stack)
72 {
73 return -1;
74 }
75
76 struct SStack* s = (struct SStack*)stack;
77 return s->size;
78 }
79 //銷毀棧
80 void Destroy_SeqStack(SeqStack stack)
81 {
82 if(NULL == stack)
83 {
84 return;
85 }
86 free(stack);
87
88 } （3）棧的鍊式存儲
>基本概念
棧的鍊式存儲結構簡稱鍊棧，
練習2：棧的鍊式存儲
棧的鍊式存儲.c
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5 #include"LinkStack.h"
6 struct Person
7 {
8 struct StackNode node;
9 char name[64];
10 int age;
11 };
12
13 void test()
14 {
15 //初始化棧
16 LinkStack stack = Init_LinkStack();
17
18 //建立資料
19 struct Person p1 = { NULL, "aaa", 10};
20 struct Person p2 = { NULL, "bbb", 20};
21 struct Person p3 = { NULL, "ccc", 30};
22 struct Person p4 = { NULL, "ddd", 40};
23 struct Person p5 = { NULL, "eee", 50};
24 struct Person p6 = { NULL, "fff", 60};
25
26 //資料入棧
27 Push_LinkStack(stack, &p1);
28 Push_LinkStack(stack, &p2);
29 Push_LinkStack(stack, &p3);
30 Push_LinkStack(stack, &p4);
31 Push_LinkStack(stack, &p5);
32 Push_LinkStack(stack, &p6);
33
34 //輸出棧中所有元素
35 while(Size_LinkStack(stack) > 0)
36 {
37 //獲得棧頂元素
38 struct Person* person = (struct Person*)Top_LinkStack(stack);
39 //列印
40 printf("Name:%s Age:%d\n", person->name, person->age);
41 //彈出棧頂元素
42 Pop_LinkStack(stack);
43 }
44
45 printf("Size:%d\n", Size_LinkStack(stack));
46
47 //銷毀棧
48 Destroy_LinkStack(stack);
49 stack = NULL;
50 }
51
52 int main(){
53
54 test();
55
56 system("pause");
57 return EXIT_SUCCESS;
58 } LinkStack.h
1 #pragma once
2
3 #include<stdlib.h>
4
5 #ifdef __cplusplus
6 extern "C"{
7 #endif
8
9 struct StackNode
10 {
11 struct StackNode* next;
12 };
13
14 struct LStack
15 {
16 struct StackNode header;//頭結點，也可以沒有
17 int size;
18 };
19
20 typedef void* LinkStack;
21
22 //初始化
23 LinkStack Init_LinkStack();
24 //入棧
25 void Push_LinkStack(LinkStack stack, void* data);
26 //出棧
27 void Pop_LinkStack(LinkStack stack);
28 //獲得棧頂元素
29 void* Top_LinkStack(LinkStack stack);
30 //獲得大小
31 int Size_LinkStack(LinkStack stack);
32 //銷毀棧
33 void Destroy_LinkStack(LinkStack stack);
34
35
36 #ifdef __cplusplus
37 }
38 #endif LinkStack.c
1 #include"LinkStack.h"
2
3 //初始化
4 LinkStack Init_LinkStack()
5 {
6 struct LStack* stack = malloc(sizeof(struct LStack));
7 if(NULL == stack)
8 {
9 return NULL;
10 }
11 stack->header.next = NULL;
12 stack->size = 0;
13
14 return stack;
15 }
16 //入棧
17 void Push_LinkStack(LinkStack stack, void* data)
18 {
19 if(NULL == stack)
20 {
21 return;
22 }
23 if(NULL == data)
24 {
25 return;
26 }
27
28 struct LStack* ls = (struct LStack*)stack;
29 struct StackNode* node = (struct StackNode*)data;
30
31 node->next = ls->header.next;//新結點的next指向ls的頭結點的下一個結點
32 ls->header.next = node;//ls頭結點的下一個結點指向新結點
33
34 ++(ls->size);
35 }
36 //出棧
37 void Pop_LinkStack(LinkStack stack)
38 {
39 if(NULL == stack)
40 {
41 return;
42 }
43
44 struct LStack* ls = (struct LStack*)stack;
45
46 if(ls->size == 0)
47 {
48 return;
49 }
50
51 //緩存第一個結點
52 struct StackNode* pFirst = ls->header.next;
53
54 ls->header.next = pFirst->next;
55
56 ls->size--;
57 }
58 //獲得棧頂元素
59 void* Top_LinkStack(LinkStack stack)
60 {
61 if(NULL == stack)
62 {
63 return;
64 }
65
66 struct LStack* ls = (struct LStack*)stack;
67
68 if(ls->size == 0)
69 {
70 return;
71 }
72
73 return ls->header.next;
74 }
75 //獲得大小
76 int Size_LinkStack(LinkStack stack)
77 {
78 if(NULL == stack)
79 {
80 return -1;
81 }
82
83 struct LStack* ls = (struct LStack*)stack;
84
85 return ls->size;
86 }
87 //銷毀棧
88 void Destroy_LinkStack(LinkStack stack)
89 {
90 if(NULL == stack)
91 {
92 return;
93 }
94
95 free(stack);
96 stack = NULL;
97 } （4）棧的應用（案例：就近比對）
幾乎所有的編譯器都具有檢測括号是否比對的能力，那麼如何實作編譯器中的符号成對檢測?如下字元串：
5+5*(6)+9/3*1)-(1+3(
>算法思路
■從第一個字元開始掃描
■當遇見普通字元時忽略，
■當遇見左符号時壓入棧中
■當遇見右符号時從棧中彈出棧頂符号，并進行比對
■比對成功：繼續讀入下一個字元
■比對失敗：立即停止，并報錯
■結束；
■成功；所有字元掃描完畢，且棧為空
練習：棧的應用：就近比對
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5 #include"SeqStack.h"
6
7 int IsLeft(char ch)
8 {
9 return ch == "(";
10 }
11
12 int IsRight(char ch)
13 {
14 return ch == ")";
15 }
16
17 void printError(const char* str, char* errMsg, char *pos)
18 {
19 printError("錯誤資訊：%s\n", errMsg);
20 printf("%s\n", str);
21 int dis = pos - str;
22 for(int i = 0; i < dis; ++i)
23 {
24 printf(" ");
25 }
26 printf("A\n");
27 }
28
29 void test()
30 {
31 const char* str = "5+5*(6)+9/3*1)-(1+3(";
32 char* p = (char*)str;
33
34 //初始化棧
35 SeqStack stack = Init_SeqStack();
36
37 while(*p != '\0')
38 {
39 //判斷目前字元是否是左括号
40 if(IsLeft(*p))
41 {
42 Push_SeqStack(stack, p);
43 }
44 //判斷目前字元是否是右括号
45 if(IsRight(*p))
46 {
47 if(Size_SeqStack(stack) > 0)
48 {
49 //彈出棧頂元素
50 Pop_SeqStack(stack);
51 }
52 else
53 {
54 printError(str, "右括号沒有比對的左括号！", p);
55 }
56 }
57
58 p++;
59 }
60 while(Size_SeqStack(stack) > 0)
61 {
62 printError(str, "沒有比對的右括号！", Top_SeqStack(stack));
63 //彈出棧頂元素
64 Pop_SeqStack(stack);
65 }
66
67 //銷毀棧
68 Destroy_SeqStack(stack);
69 stack = NULL;
70 }
71
72 int main(){
73
74 test();
75
76 system("pause");
77 return EXIT_SUCCESS;
78 }