雙向連結清單
2015-04-04 Lover雪兒
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 #define OK 1
5 #define ERROR 0
6 #define TRUE 1
7 #define FALSE 0
8
9 typedef char ElemType;
10 typedef int Status;
11
12 //雙向連結清單結構體定義
13 typedef struct DualNode
14 {
15 ElemType data;
16 struct DualNode *prior;
17 struct DualNode *next;
18 }DualNode, *DuLinkList;
19
20 /**************************************************
21 初始化連結清單
22 **************************************************/
23 Status Init_List(DuLinkList *L)
24 {
25 DualNode *p, *q;
26 int i;
27 //生成 頭結點
28 *L = (DuLinkList)malloc(sizeof(DualNode));
29 if( !(*L) ){
30 return ERROR;
31 }
32 (*L)->next = (*L)->prior = (*L);
33 p = (*L); //頭結點
34
35 //生成連結清單
36 for(i = 0; i<26; i++){
37 q = (DualNode *)malloc(sizeof(DualNode));
38 if(!q){
39 return ERROR;
40 }
41 q->data = 'A' + i; //依次給連結清單指派 字元表
42
43 q->prior = p;
44 p->next = q;
45 q->next = (*L)->next;
46
47 p = q;
48 }
49 p->next = (*L)->next; //讓尾結點的後向指針指向頭結點指向的位址，即第一個單元
50 (*L)->next->prior = p; //讓頭結點的前向指針指向尾節點
51 return OK;
52 }
53 /**************************************************
54 判斷空連結清單
55 **************************************************/
56 Status List_Empty(DuLinkList *L){
57 if((*L)->next == (*L) && (*L)->prior == (*L))
58 return TRUE;
59 else
60 return FALSE;
61 }
62 /**************************************************
63 計算L中的個數
64 **************************************************/
65 int List_Length(DuLinkList *L){
66 int i = 0;
67 DuLinkList p = (*L)->next;
68 while(p != (*L)) //檢測是否已經循環了一遍
69 {
70 p = p->next;
71 ++i;
72 }
73 i ++;
74 return i;
75 }
76
77 /**************************************************
78 排序算法，連結清單前後/後向移動i個結點
79 **************************************************/
80 void Caesar(DuLinkList *L, int i){
81 if(i > 0){
82 do{
83 (*L) = (*L)->next;
84 }while(--i);
85 }
86 if(i < 0){
87 do{
88 (*L) = (*L)->prior;
89 }while(++i);
90 }
91 }
92
93 /**************************************************
94 循環列印連結清單中的資料
95 **************************************************/
96 void printf_list(DuLinkList *L){
97 DuLinkList p = (*L)->next;
98 printf("%c ",(*L)->data);
99 while(p != (*L)){
100 printf("%c ",p->data);
101 p = p->next;
102 }
103 printf("\n\n");
104 }
105
106 /**************************************************
107 向連結清單中插入資料
108 **************************************************/
109 Status List_Insert(DuLinkList *L,int i,ElemType dat){
110 DuLinkList q, p = (*L),tmp;
111 if(i < 1 || i>List_Length(L))
112 return ERROR;
113 while(--i){
114 p = p->next;
115 }
116 q = (DuLinkList)malloc(sizeof(DualNode));
117 q->data = dat;
118
119 tmp = p->next;
120 p->next = q;
121 q->prior = p;
122 q->next = tmp;
123 tmp->prior = q;
124 return OK;
125 }
126
127 /**************************************************
128 從連結清單中删除資料
129 **************************************************/
130 Status List_delete(DuLinkList *L,int i){
131 DuLinkList p = (*L);
132 if(i < 1 || i>List_Length(L))
133 return ERROR;
134 if(i == 1){
135 Caesar(L, 1); //排序
136 //printf_list(L);
137 i = List_Length(L) + 1;
138 }
139 //printf_list(L);
140 while(--i){
141 p = p->next;
142 }
143 p->next->prior = p->prior;
144 p->prior->next = p->next;
145 free(p);
146
147 return OK;
148 }
149
150 /**************************************************
151 清空連結清單
152 **************************************************/
153 void Clear_List(DuLinkList *L){
154 DuLinkList q, p=(*L)->next;
155 while(p != (*L)){
156 q = p->next;
157 free(p);
158 p = q;
159 }
160 (*L)->prior = (*L)->next = *L;
161 printf("\n成功清空雙向連結清單!\n");
162 }
163
164 /**************************************************
165 删除連結清單
166 **************************************************/
167 void Destroy_List(DuLinkList *L){
168 DuLinkList q, p=(*L)->next;
169 while(p != (*L)->next){
170 q = p->next;
171 free(p);
172 p = q;
173 }
174 free(*L);
175 *L = NULL;
176 printf("\n成功銷毀雙向連結清單!\n");
177 }
178 /**************************************************
179 主循環
180 **************************************************/
181 int main(void)
182 {
183 DuLinkList L,p;
184 int n , m ;
185 char k;
186
187 Init_List(&L); //初始化連結清單
188 p = L->next;
189
190 printf("雙向連結清單總共有%d個元素:\n",List_Length(&p));
191 printf_list(&p); //循環列印連結清單元素
192
193 while(1){
194 printf("0:退出并銷毀連結清單\n1:列印出目前連結清單\n2:插入/删除結點\n3:連結清單有序移動\n\n");
195 scanf("%d",&n);
196 if(n == 0){
197 break;
198 }else if(n == 1){
199 printf_list(&p); //循環列印連結清單元素
200 }else if(n == 2){
201 printf_list(&p); //循環列印連結清單元素
202 while(1){
203 printf("0:退出\n1:插入資料\n2:删除資料\n");
204 scanf("%d",&n);
205 if(n == 0){
206 break;
207 }else if(n == 1){
208 printf("請輸入要插入的位置、資料,格式:m k\n");
209 scanf("%d %c",&m,&k);
210 List_Insert(&p,m,k);
211 printf_list(&p); //循環列印連結清單元素
212 }else if(n == 2){
213 printf("請輸入要删除的位置\n");
214 scanf("%d",&m);
215 List_delete(&p,m);
216 printf_list(&p); //循環列印連結清單元素
217 }else{
218 printf("請正确輸入指令，謝謝!!!\n");
219 }
220 }
221 }else if(n == 3){
222 while(1){
223 printf("請輸入一個整數[正數(前向移動)/負數(後向移動)/0(退出)]：\n");
224 scanf("%d",&n);
225 if(n == 0)
226 break;
227 Caesar(&p, n); //排序
228 printf_list(&p); //循環列印連結清單元素
229 }
230 }else{
231 printf("請正确輸入指令，謝謝!!!\n");
232 }
233 }
234 printf_list(&(L->next)); //循環列印連結清單元素
235 Destroy_List(&L);
236 return 0;
237 } 
![詳解STM32單片機的堆棧[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)