能判斷是否還有剩餘空間的靜態鏈表

　　第一次系統的學習數據結構是在半年前，看小甲魚的數據結構與演算法視頻，自學的話有許多不懂得地方，什麼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 }