线性表的链式存储

  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 = %dn", ListLength(L));
222     ElemType e;
223     GetElem(L, 4, e);
224     printf("fourth number = %dn", e);
225     printf("%d is located at %dn", 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 }