第一次系統的學習數據結構是在半年前，看小甲魚的數據結構與算法視頻，自學的話有許多不懂得地方，什麼AVL樹，紅黑樹，圖的最短路徑，最小生成樹...但總歸對數據結構與算法有一個大體的印象，到現在隨著不斷寫代碼，做OJ題，愈發認識到數據結構與算法的重要性，打算再看一遍，現在看著：大話數據結構（程傑著），數據結構（C語言版嚴蔚敏著），不推薦新手使用 數據結構與算法分析（Mark Allen Weiss 著）這本書真的很難懂。
回歸正題，我看了許多書有關靜態鏈表的描述和代碼發現都沒有判斷是否還有剩余空間，自己琢磨了一個晚上把代碼弄好了。
1 #include <stdio.h> //Anjaxs
2 #include <stdbool.h>
3
4 #define MAXSIZE 7
5 typedef int ElemType;
6
7 typedef struct{
8 ElemType data;
9 int cur;
10 }StaticList;
11
12 int Malloc_SL(StaticList * space);
13 void Free_SL(StaticList * space, int k);
14 void InitList(StaticList * space);
15 bool ListInsert(StaticList * L, int i, ElemType e);
16 bool ListDelete(StaticList * L, int i);
17 int ListLength(StaticList * L);
18 void show(StaticList * L);
19
20 int main()
21 {
22 int i;
23 int choice;
24 StaticList L[MAXSIZE];
25 InitList(L);
26 printf("1:插入 2:刪除 3:輸出 0:退出\n");
27 while (scanf("%d",&choice) && choice!=0)
28 {
29 int x;
30 int pos;
31 switch (choice)
32 {
33 case 1:
34 printf("輸入要插入的數字和位置\n");
35 scanf("%d %d", &x, &pos);
36 ListInsert(L, pos, x);
37 break;
38 case 2:
39 printf("輸入要刪除的位置\n");
40 scanf("%d",&pos);
41 ListDelete(L, pos);
42 break;
43 case 3:
44 show(L);
45 break;
46 default:
47 printf("請輸入1-3.\n");
48 break;
49 }
50 printf("1:插入 2:刪除 3:輸出 0:退出\n");
51 }
52
53 return 0;
54 }
55
56
57 void InitList(StaticList *space)
58 {
59 int i;
60 //space[0].cur為指向第一個空閒位置的指針
61 //space[MAXSIZE-1].cur為頭指針
62 for (i = 0; i < MAXSIZE-1; ++i){
63 space[i].data = 0;
64 space[i].cur = i+1;
65 }
66 //目前靜態鏈表為空，最後一個元素的cur為0
67 space[MAXSIZE-1].cur = 0;
68 space[MAXSIZE-1].data = 0;
69 }
70
71 bool ListInsert(StaticList *L, int i, ElemType e)
72 {
73 int j, k, l;
74 k = MAXSIZE-1;
75 if (i < 1 || i > ListLength(L)+1){
76 printf("請輸入合法的位置。\n");
77 return false;
78 }
79 if (ListLength(L) >= MAXSIZE-2)
80 {
81 printf("沒有空閒空間了。\n");
82 return false;
83 }
84 j = Malloc_SL(L);
85 if (j)
86 {
87 L[j].data = e;
88 for (l = 1; l <= i-1; ++l)
89 k = L[k].cur;
90 L[j].cur = L[k].cur;
91 L[k].cur = j;
92 return true;
93 }
94
95 return false;
96 }
97
98 bool ListDelete(StaticList * L, int i)
99 {
100 int j, k;
101 if (i < 1 || i > ListLength(L)){
102 printf("請輸入合法的位置。\n");
103 return false;
104 }
105
106 k = MAXSIZE-1;
107 for (j = 1; j <= i-1; ++j)
108 k = L[k].cur;
109 j = L[k].cur;
110 L[k].cur = L[j].cur;
111 Free_SL(L,j);
112 return true;
113 }
114
115 int ListLength(StaticList * L)
116 {
117 int j = 0;
118 int i = L[MAXSIZE-1].cur;
119 while (i)
120 {
121 i = L[i].cur;
122 j++;
123 }
124
125 return j;
126 }
127
128 int Malloc_SL(StaticList * space)
129 {
130 //返回第一個備用空閒的下標
131 int i = space[0].cur;
132
133 if (space[0].cur)
134 space[0].cur = space[i].cur;
135
136 return i;
137 }
138
139 void Free_SL(StaticList * space, int k)
140 {
141 space[k].cur = space[0].cur;
142 space[0].cur = k;
143 }
144
145 void show(StaticList * L)
146 {
147 int i;
148 printf("%30s\n","靜態鏈表");
149 printf("%8s","index:");
150 for (i=0 ; i<MAXSIZE ; ++i)
151 {
152 printf("%5d ",i);
153 }
154 printf("\n%8s","data:");
155 for (i=0 ; i<MAXSIZE ; ++i)
156 {
157 printf("%5d ",L[i].data);
158 }
159 printf("\n%8s","cur:");
160 for (i=0 ; i<MAXSIZE ; ++i)
161 {
162 printf("%5d ",L[i].cur);
163 }
164 printf("\n\n");
165 i = L[MAXSIZE-1].cur;
166 while (i)
167 {
168 printf("%d->", L[i].data);
169 i = L[i].cur;
170 }
171 printf("^\n\n");
172 }
