循环队列的6个基本操作https://haokan.baidu.com/v?vid=4145113523493725579&pd=bjh&fr=bjhauthor&type=video
出队：Q.front=(Q.front+1)%MAXSIZE
入队：Q.rear=(Q.rear+1)%MAXSIZE
队列初始化：Q.front=Q.rear=NULL
队空：Q.rear=Q.front
队满：(Q.rear+1)%MAXSIZE=Q.front
个数：(Q.rear-Q.front+MAXSIZE)%MAXSIZE
归并排序(https://haokan.baidu.com/v?vid=9368202192256111816&pd=bjh&fr=bjhauthor&type=video)
1 /*归并排序*/
2 void Merge_Sort(int* arr, int* temparr, int start, int mid, int end)
3 {
4 int left_start = start;
5 int left_end = mid;
6
7 int right_start = mid + 1;
8 int right_end = end;
9
10 int index = start;
11
12 while (left_start <= left_end && right_start <= right_end)
13 {
14 if (arr[left_start] > arr[right_start])
15 temparr[index++] = arr[right_start++];
16 else
17 temparr[index++] = arr[left_start++];
18 }
19
20 while (left_start <= left_end)
21 temparr[index++] = arr[left_start++];
22
23 while (right_start <= right_end)
24 temparr[index++] = arr[right_start++];
25
26 for (index = start; index <= end; ++index)
27 arr[index] = temparr[index];
28 }
29 void Sort_Message(int* arr, int* temparr, int start, int end)
30 {
31 if (start < end)
32 {
33 int mid = (start + end) / 2;
34 Sort_Message(arr, temparr, start, mid);
35 Sort_Message(arr, temparr, mid + 1, end);
36 Merge_Sort(arr, temparr, start, mid, end);
37 }
38 }
39
40 int main()
41 {
42 int a[] = { 9,2,5,3,7,4,8,0 };
43 int n = sizeof(a) / sizeof(a[0]);
44 int i, temp[8];
45
46 printf("原序列为:");
47 for (i = 0; i < n; ++i)
48 printf("%d ", a[i]);
49 printf("\n");
50
51 Sort_Message(a, temp, 0, n - 1);
52
53 printf("\n排后序列:");
54 for (i = 0; i < n; ++i)
55 printf("%d ", a[i]);
56 printf("\n");
57 return 0;
58 }
View Code
冒泡排序
1 #include <stdio.h>
2 #define N 7
3
4 void Bubble(int a[],int n)
5 {
6 int i, j = 0;
7 int temp;
8 for(i=0;i<n-1;i++)
9 for(j=0;j<n-1-i;j++)
10 if (a[j] > a[j+1])
11 {
12 temp = a[j];
13 a[j] = a[j+1];
14 a[j+1] = temp;
15 }
16 }
17
18 void main()
19 {
20 int a[] = { 2,9,7,8,6,5,3};
21 int i;
22 void Bubble(int a[], int);
23 printf("排序前:\n");
24 for (i = 0; i < N; i++)
25 printf("%d ", a[i]);
26 Bubble(a, N);
27 printf("\n\n\n排序后:\n");
28 for (i = 0; i < N; i++)
29 printf("%d ", a[i]);
30 }
View Code
希尔排序
1 //希尔排序
2 #include <stdio.h>
3 #include <stdlib.h>
4 int test_tab[] = { 0,4,9,5,7,1,3,9,6,4,5,6,7,7,8,8,1,0,3,2 };
5
6 void Shell_Sort(int* dat, int len)
7 {
8 int i, j, k, t;
9 int n = 0;
10
11 k = len / 2;
12
13 while (k > 0)
14 {
15 for (i = k; i < len; i++)
16 {
17 t = dat[i];
18 j = i - k;
19 while ((j >= 0) && (t < dat[j]))
20 {
21 dat[j + k] = dat[j];
22 j = j - k;
23 n++;
24 }
25
26 dat[j + k] = t;
27 }
28
29 k /= 2;
30 }
31 printf("循环的次数是：%d \r\n", n);
32 }
33 int main(int argc, char* argv[])
34 {
35 int i = 0;
36 int len = sizeof(test_tab) / sizeof(test_tab[0]);
37
38 Shell_Sort(test_tab, sizeof(test_tab) / sizeof(test_tab[0]));
39 for (i = 0; i < len; i++)
40 printf("%d ", test_tab[i]);
41 system("PAUSE");
42 return 0;
43 }
View Code
快速排序
1 #include<stdio.h>
2
3
4
5 void quicksort(int a[], int n) {
6
7 int i, j;
8
9 int pivot = a[0]; //设置基准值
10
11 i = 0;
12
13 j = n - 1;
14
15 while (i < j) {
16
17 //大于基准值者保持在原位置
18
19 while (i < j && a[j] > pivot) { j--; }
20
21 if (i < j) {
22
23 a[i] = a[j];
24
25 i++;
26
27 }
28
29 //不大于基准值者保持在原位置
30
31 while (i < j && a[i] <= pivot) { i++; }
32
33 if (i < j) {
34
35 a[j] = a[i];
36
37 j--;
38
39 }
40
41 }
42
43 a[i] = pivot; //基准元素归位
44
45 if (i > 1) {
46
47 //递归地对左子序列 进行快速排序
48
49 quicksort(a, i);
50
51 }
52
53 if (n - i - 1 > 1) {
54
55 quicksort(a + i + 1, n - i - 1);
56
57 }
58
59 }
60
61
62
63 int main() {
64
65 int i, arr[] = { 23,56,9,75,18,42,11,67 };
66
67 quicksort(arr, 8);
68
69 for (i = 0; i < sizeof(arr) / sizeof(int); i++)
70
71 printf("%d\t", arr[i]);
72
73 return 0;
74
75 }
View Code
插入排序
1 #include<stdio.h>
2 int number[100000000]; //在外面定义数组
3 void insertion_sort(int* number, int n) //定义一个插入函数"insertion_sort"
4 {
5 int i = 0, ii = 0, temp = 0;
6 for (i = 1; i < n; i++) //循环遍历
7 {
8 temp = number[i]; //将temp每一次赋值为number[i]
9 ii = i - 1;
10 while (ii >= 0 && temp < number[ii]) //这里改顺序 (temp后的)"<"为小到大，">"为大到小 ！！！
11 {
12 number[ii + 1] = number[ii]; //将大的元素往前放
13 ii--;
14 }
15 number[ii + 1] = temp; //与"number[ii+1]=number[ii];"一起意为
16 } //如果插入的数比之前的大,将number[ii]与number[ii+1]互换
17 }
18 int main()
19 {
20 int i = 0, n;
21 printf("输入数字个数：\n");
22 scanf("%d", &n); //输入要排序的数字的个数
23 printf("输入%d个数:\n", n);
24 for (int j = 0; j < n; j++) //将所有数全放入number数组中
25 scanf("%d", &number[j]);
26 insertion_sort(number, n); //引用插入函数
27 for (i = 0; i < n - 1; i++) //循环输出
28 printf("%d ", number[i]); //格式需要
29 printf("%d\n", number[i]);
30 return 0;
31 }
View Code
选择排序
1 #include<stdio.h>
2 int number[100000000]; //在主函数外定义数组可以更长多了
3 void select_sort(int R[], int n) //定义选择排序函数"select_sort"
4 {
5 int i, j, k, index; //定义变量
6 for (i = 0; i < n - 1; i++) //遍历
7 {
8 k = i;
9 for (j = i + 1; j < n; j++) //j初始不为0，冒泡初始为0，所以选排比冒泡快，但不稳定
10 {
11 if (R[j] < R[k]) //顺序从这里改顺序 小到大"<",大到小">" ！！！
12 k = j; //这里是区分冒泡排序与选择排序的地方，冒泡没这句
13 }
14 if (k != j) //为了严谨，去掉也行
15 {
16 index = R[i]; //交换R[i]与R[k]中的数
17 R[i] = R[k]; //简单的交换c=a,a=b,b=c
18 R[k] = index;
19 }
20 }
21 }
22
23 int main() //主程序
24 {
25 int i, n;
26 printf("输入数字个数：\n");
27 scanf("%d", &n); //输入要排序的数字的个数
28 printf("输入%d个数:\n", n);
29 for (int j = 0; j < n; j++) //将所有数全放入number数组中
30 scanf("%d", &number[j]);
31 select_sort(number, n); //引用选择排序select_sort的函数
32 for (i = 0; i < n - 1; i++) //用for循环输出排完排完序的数组
33 printf("%d ", number[i]); //这样写是为了格式（最后一个数后面不能有空格）
34 printf("%d\n", number[i]);
35 return 0; //好习惯
36 }
37 //ENDING
View Code
堆排序
1 #include <stdio.h>
2 #define NA -1
3 void swap(int *a,int *b)//该函数用于交换两个变量的值
4 {
5 int temp=*a;
6 *a=*b;
7 *b=temp;
8 }
9 void HeapAdjust(int H[],int start,int end)//堆调整，将start和end之间的元素调整为最大堆
10 {
11 int temp=H[start];
12 int parent=start,child;
13 while(2*parent<=end)
14 {
15 child=2*parent;
16 if(child!=end&&H[child]<H[child+1])++child;
17 if(temp>H[child])break;
18 else H[parent]=H[child];
19 parent=child;
20 }
21 H[parent]=temp;
22 }
23 void HeapSort(int H[],int L,int R)
24 {
25 for(int i=(R-L+1)/2;i>=L;--i)//调整整个二叉树为最大堆
26 HeapAdjust(H,i,R);
27 for(int i=R;i>=L;--i)
28 {
29 swap(&H[L],&H[i]);
30 HeapAdjust(H,L,i-1);
31 }
32 }
33
34 int main(){
35 int A[]={NA,1,3,63,5,78,9,12,52,8};//从1开始存入数据
36 printf("Previous Arrary:");
37 for(int i=1;i<=9;++i)
38 printf(" %d",A[i]);
39 HeapSort(A,1,9);
40 printf("\nSorted Arrary:");
41 for(int i=1;i<=9;++i)
42 printf(" %d",A[i]);
43 printf("\n");
44 return 0;
45 }
46
47 //原文链接：https://blog.csdn.net/gl486546/article/details/54707307
View Code
顺序队列
1 //队列
2
3 #include<stdio.h>
4 #include<stdlib.h>
5 #include<malloc.h>
6 #define MAXSIZE 10
7
8 typedef struct Queue {
9
10 int* queue;
11 int front;//队头
12 int rear;//队尾
13 int count;//计数
14 }QUEUE,*LPQUEUE;
15
16 void CreateQueue(LPQUEUE Q)
17 {
18 Q->queue = (int*)malloc(sizeof(int) * MAXSIZE);
19 Q->front = Q->rear = Q->count = 0;
20 }
21
22 int IsEmptyQueue(LPQUEUE Q)
23 {
24 if (Q->count == 0)
25 return 1;
26 return 0;
27 }
28
29 void push(LPQUEUE Q, int theElement)
30 {
31 if (Q->count == MAXSIZE)
32 {
33 printf("队列满无法入队\n");
34 return;
35 }
36 Q->queue[Q->rear++] = theElement;
37 Q->count++;
38 }
39 void pop(LPQUEUE Q)
40 {
41 if (IsEmptyQueue(Q))
42 {
43 printf("队列为空\n");
44 }
45 Q->queue[Q->front++];
46 Q->count--;
47 }
48
49 int getfront(LPQUEUE Q)
50 {
51 return Q->queue[Q->front];
52 }
53
54
55
56 int main()
57 {
58 LPQUEUE Q = (LPQUEUE)malloc(sizeof(QUEUE));
59 CreateQueue(Q);
60 push(Q, 1);
61 push(Q, 2);
62 push(Q, 3);
63 while (!IsEmptyQueue(Q))
64 {
65 printf("%d", getfront(Q));
66 pop(Q);
67 }
68 system("pause");
69 return 0;
70 }
View Code
链式队列
1 //链式队列
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<malloc.h>
5
6 typedef struct SingleList
7 {
8 int data;
9 struct SingleList * next;
10
11 }LIST,*LPLIST;
12 LPLIST CreateNode(int data)
13 {
14 LPLIST Node = (LPLIST)malloc(sizeof(LIST));
15 Node->data = data;
16 Node->next = NULL;
17 return Node;
18 }
19 typedef struct queue
20 {
21 LPLIST front;
22 LPLIST rear;
23 int queueSize;
24 }QUEUE,*LPQUEUE;
25 void CreateQueue(LPQUEUE Q) {
26 Q->front = Q->rear = NULL;
27 Q->queueSize = 0;
28 }
29
30 int IsEmptyQueue(LPQUEUE Q)
31 {
32 if (Q->queueSize == 0)
33 return 1;
34 return 0;
35 }
36 //入队列
37 void push(LPQUEUE Q, int theElement)
38 {
39
40
41 LPLIST newNode = CreateNode(theElement);
42 if (Q->front == NULL)
43 {
44 Q->front = newNode;//队列为空时， newNode 成为队头
45 }
46 else
47 {
48 Q->rear->next = newNode;
49 }
50 Q->rear = newNode;
51 Q->queueSize++;
52 }
53
54 int getfront(LPQUEUE Q)
55 {
56 if (IsEmptyQueue(Q))
57 {
58 printf("无法获取队头元素，队为空\n");
59 return -1;
60 }
61
62 return Q->front->data;
63 }
64 void pop(LPQUEUE Q)
65 {
66 if (IsEmptyQueue(Q))
67 {
68 printf("无法出兑，队为空");
69 return;
70 }
71 LPLIST nextNode = Q->front->next;
72 free(Q->front);
73 Q->front = nextNode;
74 Q->queueSize--;
75 }
76
77 int main()
78 {
79 LPQUEUE Q = (LPQUEUE)malloc(sizeof(QUEUE));
80 CreateQueue(Q);
81 push(Q, 1);
82 push(Q, 2);
83 push(Q, 3);
84 while (!IsEmptyQueue(Q))
85 {
86 printf("%d", getfront(Q));
87 pop(Q);
88 }
89 system("pause");
90
91 }
View Code
栈
1 //数组实现栈
2 #include <stdio.h>
3 #include<stdlib.h>
4 #include<malloc.h>
5
6 #define MAXSIZE 10
7
8 typedef struct arraystack {
9
10 int* stack;
11 int top;
12 }STACK,*LPSTACK;
13 //创建过程--初始化基本数据成员
14 void CreateStack(LPSTACK S)
15 {
16 S->stack = (int*)malloc(sizeof(int) * MAXSIZE);
17 if (S->stack == NULL)
18 {
19 printf("创建失败\n");
20 }
21 S->top = -1;
22 }
23
24 //判断是否为空；
25
26 int IsEmptyStack(LPSTACK S)
27 {
28 if (S->top == -1)
29 return 1;
30 return 0;
31 }
32 //入栈
33 void push(LPSTACK S, int theElement) {
34
35 if (S->top == MAXSIZE - 1)
36 {
37 printf("栈满无法入栈\n");
38 exit(0);
39 }
40 S->stack[++S->top] = theElement;
41 }
42
43 void pop(LPSTACK S)
44 {
45 if (IsEmptyStack(S))
46 {
47 printf("无法出栈，栈为空\n");
48 }
49 S->stack[--S->top];
50 }
51 int getTop(LPSTACK S)
52 {
53 if (IsEmptyStack(S))
54 {
55
56 printf("无法出栈，栈为空\n");
57 return -1;
58 }
59
60 return S->stack[S->top];
61
62 }
63
64 int main()
65 {
66 LPSTACK S = (LPSTACK)malloc(sizeof(STACK));
67 CreateStack(S);
68 push(S, 1);
69 push(S, 2);
70 push(S, 3);
71 while (!IsEmptyStack(S))
72 {
73 printf("%d", getTop(S));
74 pop(S);
75 }
76 return 0;
77 }
View Code
单链表创建，打印，删除以及插入
1 //单向链表创建
2
3
4 #include <stdio.h>
5 #include <stdlib.h>
6
7 struct link* AppendNode(struct link* head);
8 void DisplyNode(struct link* head);
9 void DeletMemory(struct link* head);
10
11 struct link
12 {
13 int data;
14 struct link* next;
15 };
16
17 int main(void)
18 {
19 int i = 0;
20 char c;
21 struct link* head = NULL; //链表头指针
22 printf("Do you want to append a new node(Y/N)?");
23 scanf_s(" %c", &c);
24 while (c == 'Y' || c == 'y')
25 {
26 head = AppendNode(head);//向head为头指针的链表末尾添加节点
27 DisplyNode(head); //显示当前链表中的各节点的信息
28 printf("Do your want to append a new node(Y/N)");
29 scanf_s(" %c", &c);
30 i++;
31 }
32 printf("%d new nodes have been apended", i);
33 DeletMemory(head); //释放所有动态分配的内存
34
35 return 0;
36 }
37 /* 函数功能：新建一个节点并添加到链表末尾，返回添加节点后的链表的头指针 */
38 struct link* AppendNode(struct link* head)
39 {
40 struct link* p = NULL, * pr = head;
41 int data;
42 p = (struct link*)malloc(sizeof(struct link));//让p指向新建的节点
43 if (p == NULL) //若新建节点申请内存失败，则退出程序
44 {
45 printf("No enough memory to allocate\n");
46 exit(0);
47 }
48 if (head == NULL) //若原链表为空表
49 {
50 head = p; //将新建节点置为头节点
51 }
52 else //若原链表为非空，则将新建节点添加到表尾
53 {
54 while (pr->next != NULL)//若未到表尾，则移动pr直到pr指向表尾
55 {
56 pr = pr->next; //让pr指向下一个节点
57 }
58 pr->next = p; //让末节点的指针指向新建的节点
59 }
60 printf("Input node data\n");
61 scanf_s("%d", &data); //输入节点数据
62 p->data = data; //将新建节点的数据域赋值为输入的节点数据值
63 p->next = NULL; //将新建的节点置为表尾
64 return head; //返回添加节点后的链表的头指针
65 }
66 /* 函数的功能：显示链表中所有节点的节点号和该节点中的数据项的内容*/
67 void DisplyNode(struct link* head)
68 {
69 struct link* p = head;
70 int j = 1;
71 while (p != NULL) //若不是表尾，则循环打印节点的数值
72 {
73 printf("%5d%10d\n", j, p->data);//打印第j个节点数据
74 p = p->next; //让p指向下一个节点
75 j++;
76 }
77 }
78 //函数的功能：释放head所指向的链表中所有节点占用的内存
79 void DeletMemory(struct link* head)
80 {
81 struct link* p = head, * pr = NULL;
82 while (p != NULL) //若不是表尾，则释放节点占用的内存
83 {
84 pr = p; //在pr中保存当前节点的指针
85 p = p->next;//让p指向下一个节点
86 free(pr); //释放pr指向的当前节点占用的内存
87 }
88 }
89 //单向链表的删除操作实现
90 struct link* DeleteNode(struct link* head, int nodeData)
91 {
92 struct link* p = head, * pr = head;
93
94 if (head == NULL)
95 {
96 printf("Linked table is empty!\n");
97 return 0;
98 }
99 while (nodeData != p->data && p->next != NULL)
100 {
101 pr = p; /* pr保存当前节点 */
102 p = p->next; /* p指向当前节点的下一节点 */
103 }
104 if (nodeData == p->data)
105 {
106 if (p == head) /* 如果待删除为头节点 （注意头指针和头结点的区别）*/
107 {
108 head = p->next;
109 }
110 else /* 如果待删除不是头节点 */
111 {
112 pr->next = p->next;
113 }
114 free(p); /* 释放已删除节点的内存 */
115 }
116 else /* 未发现节点值为nodeData的节点 */
117 {
118 printf("This Node has not been found");
119 }
120
121 return head;
122 }
123
124 /* 函数功能：向单向链表中插入数据 按升序排列*/
125 struct link* InsertNode(struct link* head, int nodeData)
126 {
127 struct link* p = head, * pr = head, * temp = NULL;
128
129 p = (struct link*)malloc(sizeof(struct link));
130 if (p == NULL)
131 {
132 printf("No enough meomory!\n");
133 exit(0);
134 }
135 p->next = NULL; /* 待插入节点指针域赋值为空指针 */
136 p->data = nodeData;
137
138 if (head == NULL) /* 若原链表为空 */
139 {
140 head = p; /* 插入节点作头结点 */
141 }
142 else /* 原链表不为空 */
143 {
144 while (pr->data < nodeData && pr->next != NULL)
145 {
146 temp = pr; /* 保存当前节点的指针 */
147 pr = pr->next; /* pr指向当前节点的下一节点 */
148 }
149 if (pr->data >= nodeData)
150 {
151 if (pr == head) /* 在头节点前插入新节点 */
152 {
153 p->next = head; /* 新节点指针域指向原链表头结点 */
154 head = p; /* 头指针指向新节点 */
155 }
156 else
157 {
158 pr = temp;
159 p->next = pr->next; /* 新节点指针域指向下一节点 */
160 pr->next = p; /* 让前一节点指针域指向新节点 */
161 }
162 }
163 else /* 若在表尾插入新节点 */
164 {
165 pr->next = p; /* 末节点指针域指向新节点*/
166 }
167 }
168
169 return head;
170 }
171
172
173 //有表头结点
174 #include <stdio.h>
175 #include <stdlib.h>
176
177 struct link* AppendNode(struct link* head);
178 void DisplyNode(struct link* head);
179 void DeletMemory(struct link* head);
180 struct link* init(struct link* head);
181
182 struct link
183 {
184 int data;
185 struct link* next;
186 };
187 int main(void)
188 {
189 int i = 0;
190 char c;
191 struct link* head = NULL; //链表头指针
192
193 head = init(head); /* 初始化队列 */
194 printf("Do you want to append a new node(Y/N)?");
195 scanf_s(" %c", &c); //%c前有一个空格
196 while (c == 'Y' || c == 'y')
197 {
198 head = AppendNode(head);//向head为头指针的链表末尾添加节点
199 DisplyNode(head); //显示当前链表中的各节点的信息
200 printf("Do your want to append a new node(Y/N)");
201 scanf_s(" %c", &c); //%c前有一个空格
202 i++;
203 }
204 printf("%d new nodes have been apended", i);
205 DeletMemory(head); //释放所有动态分配的内存
206
207 return 0;
208 }
209
210 //函数功能：初始化链表，即新建一个头结点（此处头结点不放数据，原则上不放，实际还是可以放数据）
211 struct link* init(struct link* head)
212 {
213 struct link* p = NULL;
214
215 p = (struct link*)malloc(sizeof(struct link));
216 if (p == NULL)
217 {
218 printf("初始化链表失败\n");
219 exit(0);
220 }
221 head = p;
222 p->next = NULL;
223
224 return head;
225 }
226
227 //函数功能：新建一个节点并添加到链表末尾，返回添加节点后的链表的头指针
228 struct link* AppendNode(struct link* head)
229 {
230 struct link* p = NULL, * pr = head;
231 int data;
232 p = (struct link*)malloc(sizeof(struct link));//让p指向新建的节点
233 if (p == NULL) //若新建节点申请内存失败，则退出程序
234 {
235 printf("No enough memory to allocate\n");
236 exit(0);
237 }
238 if (head->next == NULL) //若原链表为空表（只有头节点，头节点不存储数据为空表）
239 {
240 printf("Input node data");
241 scanf_s("%d", &data);
242 head->next = p; /* 让头结点的指针指向新建节点 */
243 p->data = data;
244 p->next = NULL; /* 新建结点置为表尾 */
245 return head;
246 }
247 else //若原链表为非空，则将新建节点添加到表尾
248 {
249 while (pr->next != NULL)//若未到表尾，则移动pr直到pr指向表尾
250 {
251 pr = pr->next; //让pr指向下一个节点
252 }
253 pr->next = p; //让末节点的指针指向新建的节点
254
255 printf("Input node data");
256 scanf_s("%d", &data); //输入节点数据
257 p->data = data; //将新建节点的数据域赋值为输入的节点数据值
258 p->next = NULL;//将新建的节点置为表尾
259 return head; //返回添加节点后的链表的头指针
260 }
261 }
262 //函数的功能：显示链表中所有节点的节点号和该节点中的数据项的内容
263 void DisplyNode(struct link* head)
264 {
265 struct link* p = head;
266 int j = 1;
267
268 p = p->next;
269 while (p != NULL) //若不是表尾，则循环打印节点的数值
270 {
271 printf("%5d%10d\n", j, p->data);//打印第j个节点数据
272 p = p->next; //让p指向下一个节点
273 j++;
274 }
275 }
276 //函数的功能：释放head所指向的链表中所有节点占用的内存
277 void DeletMemory(struct link* head)
278 {
279 struct link* p = head, * pr = NULL;
280 while (p != NULL) //若不是表尾，则释放节点占用的内存
281 {
282 pr = p; //在pr中保存当前节点的指针
283 p = p->next;//让p指向下一个节点
284 free(pr); //释放pr指向的当前节点占用的内存
285 }
286 }
View Code
双向循环链表
1 #include <stdio.h>
2 #include <stdlib.h>
3 //代码量
4 struct doubleList
5 {
6 int data;
7 struct doubleList* front;
8 struct doubleList* tail;
9 };
10
11 struct doubleList* createList()
12 {
13 //环
14 struct doubleList* headNode = (struct doubleList*)malloc(sizeof(struct doubleList));
15 headNode->front = headNode->tail = headNode;
16 return headNode;
17 }
18 struct doubleList* createNode(int data)
19 {
20 struct doubleList* newNode = (struct doubleList*)malloc(sizeof(struct doubleList));
21 //创建过程--->描述最初状态--->初始化结构变量中的成员
22 newNode->data = data;
23 newNode->front = NULL;
24 newNode->tail = NULL;
25 return newNode;
26 }
27
28 void insertNodeByHeadOrTail(struct doubleList* headNode, int data)
29 {
30 struct doubleList* newNode = createNode(data);
31 //采用表尾插入
32 struct doubleList* tailNode = headNode->front;
33 tailNode->tail = newNode;
34 newNode->front = tailNode;
35 headNode->front = newNode;
36 newNode->tail = headNode;
37 }
38 void printList(struct doubleList* headNode)
39 {
40 struct doubleList* pMove = headNode->tail;
41 while (pMove->front != headNode->front)
42 {
43 printf("%d->", pMove->data);
44 pMove = pMove->tail;
45 }
46 printf("\n");
47 }
48
49 void deleteListTailNode(struct doubleList * headNode)
50 {
51 //一定要判断是否为空
52 struct doubleList* tailNode = headNode->front;
53 //上一个结点是：tailNode->front;
54 tailNode->front->tail = headNode;
55 headNode->front = tailNode->front;
56 free(tailNode);
57 }
58
59
60 int main()
61 {
62 struct doubleList* list = createList();
63 insertNodeByHeadOrTail(list, 1);
64 insertNodeByHeadOrTail(list, 2);
65 insertNodeByHeadOrTail(list, 3);
66 printList(list);
67 deleteListTailNode(list);
68 printList(list);
69 deleteListTailNode(list);
70 printList(list);
71 deleteListTailNode(list);
72 printList(list);
73 system("pause");
74 return 0;
75 }
View Code
链式栈
1 #include <stdio.h>
2 #include <stdlib.h>
3 #define Empty 0 /* 栈空 */
4 #define Avail 1 /* 栈可用 */
5
6 typedef struct SNode
7 {
8 int data;
9 struct SNode *next;
10 }StackNode;
11 typedef struct LStack
12 {
13 StackNode *top; /* 栈顶指针 */
14 StackNode *bottom; /* 栈底指针 */
15 int height; /* 链式栈高度 */
16 }LinkStack;
17
18 LinkStack InitStack (LinkStack pStack); /* 栈顶指针、栈底指针、栈高度初始化*/
19 LinkStack Push (LinkStack pStack); /* 入栈 */
20 LinkStack Pop (LinkStack pStack); /* 出栈 */
21 int StackEmpty (LinkStack pStack); /* 判断栈是否为空 */
22 LinkStack DeletStack (LinkStack pStack);/* 清空栈 */
23 void DisplyStack (LinkStack pStack); /* 遍历栈----自顶至底*/
24
25 int main()
26 {
27 LinkStack p;
28 char ch;
29
30 p.height = 0; /* 栈高度初始化为零 */
31 p = InitStack (p); /* 栈初始化 */
32 printf("Do you want to push stack(Y/N)?");
33 scanf(" %c", &ch);
34 while (ch == 'Y' || ch == 'y')
35 {
36 p = Push(p); /* 入栈 */
37 DisplyStack(p); /* 遍历栈 */
38 printf("Do you want to push stack(Y/N)?");
39 scanf(" %c", &ch);
40 }
41 printf("Do you want to pop stack(Y/N)?");
42 scanf(" %c", &ch);
43 while (ch == 'Y' || ch == 'y')
44 {
45 p = Pop(p); /* 出栈 */
46 DisplyStack(p); /* 遍历栈 */
47 printf("Do you want to pop stack(Y/N)?");
48 scanf(" %c", &ch);
49 }
50
51 return 0;
52 }
53 /* Function: 初始化栈顶、栈底、栈高度*/
54 LinkStack InitStack (LinkStack pStack)
55 {
56 pStack.top = pStack.bottom = NULL;
57 pStack.height = 0;
58
59 return pStack;
60 }
61
62 /* Function: 判断栈是否为空 */
63 int StackEmpty (LinkStack pStack)
64 {
65 if (pStack.top == NULL && pStack.bottom == NULL)
66 {
67 return Empty;
68 }
69 else
70 {
71 return Avail;
72 }
73 }
74
75 /* Function: 入栈 */
76 LinkStack Push (LinkStack pStack)
77 {
78 int data;
79 StackNode *temp;
80
81 if ((temp = (StackNode *)malloc(sizeof(StackNode))) == NULL)
82 {
83 printf("内存空间不足\n");
84 return pStack;
85 }
86 if (StackEmpty(pStack) == Empty) /* 如果栈为空 */
87 {
88 pStack.top = pStack.bottom = temp; /* 栈顶、栈底指针都指向新建节点 */
89 temp->next = NULL; /* 节点指针域为空 */
90 printf("Please input data");
91 scanf("%d", &data);
92 pStack.top->data = data;
93 pStack.height++;
94
95 return pStack;
96 }
97 else /* 栈不为空 */
98 {
99 temp->next = pStack.top;/* 新建节点指向原来的栈顶 */
100 pStack.top = temp; /* 栈顶指针指向新建节点 */
101 printf("Please input data");
102 scanf("%d", &data);
103 pStack.top->data = data;
104 pStack.height++;
105
106 return pStack;
107 }
108 }
109
110 /* Function: 出栈 */
111 LinkStack Pop (LinkStack pStack)
112 {
113 StackNode *Second;
114
115
116 if (StackEmpty(pStack) == Empty) /* 判断栈是否为空 */
117 {
118 printf("栈为空，无法出栈\n");
119 return pStack;
120 }
121 if (pStack.top == pStack.bottom) /* 如果出栈的元素为最后一个元素 */
122 {
123 printf("出栈元素为%d\n", pStack.top->data);
124 free(pStack.top);
125 pStack.top = pStack.bottom = NULL; /* 栈顶、栈底都指针都置为空 */
126 pStack.height--;
127
128 return pStack;
129 }
130 printf("出栈元素为%d\n", pStack.top->data);
131 Second = pStack.top->next; /* 指向栈顶的前一个元素*/
132
133 free(pStack.top); /* 释放栈顶节点 */
134 pStack.top = Second;/* 将头指针移动到新的栈顶节点 */
135 pStack.height--;
136
137 return pStack;
138 }
139
140 /* Function: 遍历栈 自顶到底*/
141 void DisplyStack (LinkStack pStack)
142 {
143 if (StackEmpty(pStack) == Empty)
144 {
145 printf("栈为空，无法遍历\n");
146 return ;
147 }
148 printf("栈中元素[");
149 while (pStack.top != NULL)
150 {
151 printf("%d->", pStack.top->data);
152 pStack.top = pStack.top->next;
153 }
154 printf("]\n");
155 }
156
157 /* Function: 清空栈 */
158 LinkStack DeletStack (LinkStack pStack)
159 {
160 StackNode *del;
161
162 while (pStack.top != NULL)
163 {
164 del = pStack.top->next; /* 栈顶节点的前一个节点 */
165 free(pStack.top); /* 释放节点 */
166 pStack.top = del; /* 栈顶指针移动到新栈顶 */
167 }
168
169 return pStack;
170 }
View Code