線性表的鏈式存儲

線性表的鏈式存儲

鏈式結構存儲密度小，存儲空間利用率低

只能順序存儲(其中指針域用來表明節點間的關係)

插入和刪除操作方便

1. 初始化線性表 InitList(L)
2. 銷毀線性表 DestoryList(L)
3. 判斷線性表是否為空 ListEmpty(L)
4. 求線性表的長度 ListLength(L)
5. 輸出線性表 DispList(L)
6. 求線性表中某個數據元素值 GetElem(L, i, e)
7. 按元素值查找 LocateElem(L, e)
8. 插入數據元素 ListInsert(L, i, e)
9. 刪除數據元素 ListDelete(L, i, e)

代碼如下：

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 typedef int ElemType;
  4 
  5 typedef struct LNode {
  6     ElemType data;
  7     struct LNode *next;
  8 } LinkList;
  9 
 10 /*建立單鏈表*/
 11 /*頭插法*/
 12 void CreateListF(LinkList* &L, ElemType a[], int n) {
 13     L = (LinkList *)malloc(sizeof(LinkList));
 14     L -> next = NULL;
 15 
 16     int i;
 17     LinkList *s;
 18     for(i = 0; i < n; i++) {
 19         s = (LinkList *)malloc(sizeof(LinkList));
 20         s -> data = a[i];
 21         s -> next = L -> next;
 22         L -> next = s;
 23     }
 24 }
 25 
 26 /*尾插法*/
 27 void CreateListR(LinkList* &L, ElemType a[], int n) {
 28     L = (LinkList *)malloc(sizeof(LinkList));
 29     L -> next = NULL;
 30 
 31     LinkList *p;//指針 p 來進行操作
 32     p = L;
 33 
 34     LinkList *s;
 35     int i;
 36     for(i = 0; i < n; i++) {
 37         s = (LinkList *)malloc(sizeof(LinkList));
 38         s -> data = a[i];
 39         p -> next = s;
 40         p = s;
 41     }
 42     p -> next = NULL;
 43 }
 44 
 45 /*基本運算*/
 46 /*初始化線性表 InitList(L)*/
 47 void InitList(LinkList* &L) {
 48     L = (LinkList *)malloc(sizeof(LinkList));
 49     L -> next = NULL;
 50 }
 51 
 52 /*銷毀線性表 DestoryList(L)*/
 53 void DestoryList(LinkList* &L) {
 54     LinkList *pre = L;
 55     LinkList *p = L -> next;
 56 
 57     while(p != NULL) {
 58         free(pre);
 59         pre = p;
 60         p = p -> next;
 61     }
 62 
 63     free(pre);
 64 }
 65 
 66 /*判斷線性表是否為空 ListEmpty(L)*/
 67 bool ListEmpty(LinkList* L) {
 68     return L -> next == NULL;
 69 }
 70 
 71 /*求線性表的長度 ListLength(L)*/
 72 int ListLength(LinkList* L) {
 73     LinkList *p = L;
 74     int i = 0;
 75 
 76     while(p -> next != NULL) {
 77         p = p -> next;
 78         i++;
 79     }
 80 
 81     return i;
 82 }
 83 
 84 /*輸出線性表 DispList(L)*/
 85 void DispList(LinkList* L) {
 86     LinkList *p = L -> next;
 87 
 88     while(p != NULL) {
 89         printf("%d ", p -> data);
 90         p = p -> next;
 91     }
 92 
 93     printf("\n");
 94 }
 95 
 96 /*求線性表中某個數據元素值 GetElem(L, i, e)*/
 97 bool GetElem(LinkList* L, int i, ElemType &e) {
 98     LinkList *p = L;
 99 
100     int k = 0;
101     while(k < i && p != NULL) {
102         k++;
103         p = p ->next;
104     }
105 
106     if (p == NULL) {
107         return false;
108     } else {
109         e = p -> data;
110         return true;
111     }
112 }
113 
114 /*按元素值查找 LocateElem(L, e)*/
115 int LocateElem_wq(LinkList* L, ElemType e) {
116     LinkList *p = L;
117 
118     int k = 0;
119     while(p != NULL) {
120         if (e == p -> data) {
121             return k;
122         }
123         p = p -> next;
124         k++;
125     }
126 
127     return 0;
128 }
129 
130 int LocateElem(LinkList* L, ElemType e) {
131     LinkList *p = L -> next;
132 
133     int k = 1;
134     while(p != NULL && e != p -> data) {
135         p = p -> next;
136         k++;
137     }
138 
139     if (p == NULL) {
140         return 0;
141     } else {
142         return k;
143     }
144 }
145 
146 /*插入數據元素 ListInsert(L, i, e)*/
147 bool ListInsert(LinkList* &L, int i, ElemType e) {
148     LinkList *p = L;
149 
150     int k = 0;
151     while(k < i - 1 && p != NULL) {//找到前驅節點
152         p = p -> next;
153         k++;
154     }
155 
156     if (p == NULL) {
157         return false;
158     } else {
159         LinkList *s;
160         s = (LinkList *)malloc(sizeof(LinkList));
161         s -> data = e;
162         s -> next = p -> next;
163         p -> next = s;
164         return true;
165     }
166 }
167 
168 /*刪除數據元素 ListDelete(L, i, e)*/
169 bool ListDelete_wq(LinkList* &L, int i, ElemType &e) {
170     LinkList *pre = L;//保存第 i 個指針的前驅
171     LinkList *p = L -> next;//保存第 i 個指針的位置
172 
173     int k = 1;
174     while(k < i && p != NULL) {
175         pre = pre -> next;
176         p = p -> next;
177         k++;
178     }
179 
180     if (p == NULL) {
181         return false;
182     } else {
183         e = p ->data;
184         pre -> next = p -> next;
185         free(p);
186         return true;
187     }
188 }
189 
190 bool ListDelete(LinkList* &L, int i, ElemType &e) {
191     LinkList *pre = L;//保存第 i 個指針的前驅
192 
193     int k = 0;
194     while(k < i - 1 && pre != NULL) {
195         pre = pre -> next;
196         k++;
197     }
198 
199     if (pre == NULL) {
200         return false;
201     } else {
202         LinkList *p;
203         p = pre -> next;
204         if (p == NULL) {
205             return false;
206         }
207         e = p -> data;
208         pre -> next = p -> next;
209         free(p);
210         return true;
211     }
212 }
213 
214 int main(int argc, char const *argv[]) {
215     int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
216     LinkList *L;
217     InitList(L);
218     //CreateListR(L, a, 9);
219     CreateListF(L, a, 9);
220     DispList(L);
221     printf("length = %d\n", ListLength(L));
222     ElemType e;
223     GetElem(L, 4, e);
224     printf("fourth number = %d\n", e);
225     printf("%d is located at %d\n", e, LocateElem_wq(L, 6));
226     ListInsert(L, 2, 10);
227     DispList(L);
228     ListDelete_wq(L, 2, e);
229     DispList(L);
230     return 0;
231 }

這兒是運行結果哦：

9 8 7 6 5 4 3 2 1
length = 9
fourth number = 6
6 is located at 4
9 10 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1