單鏈表

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<malloc.h>
  4 
  5 typedef int Elemtype;
  6 
  7 typedef struct Node{
  8     int data;
  9     struct Node* next;
 10 }Node;
 11 
 12 typedef struct Node* LinkList;
 13 
 14 void InitLinkList(LinkList *L);
 15 void DestoryList(LinkList* L);
 16 void ClearList(LinkList *L);
 17 void HeadCreateList(LinkList*,int);
 18 void TailCreateList(LinkList*,int);
 19 void DisplayList(LinkList);
 20 
 21 //void InitLinkList(Node** L){
 22 //    *L = (LinkList)malloc(sizeof(struct Node));
 23 //    (*L)->next = NULL;
 24 //    //alternation 
 25 //}
 26 void InitList(LinkList *L){
 27     *L = (LinkList)malloc(sizeof(struct Node));
 28     (*L)->next = NULL;
 29 }
 30 void DestoryList(LinkList* L){
 31 /*
 32     LinkList p = *L,q;
 33     printf("%d %d\n",p,*L); //p == *L == 7279912
 34     while(p){
 35         q = p->next;
 36         free(p);
 37         p = q;           //last step p = NULL
 38     }
 39     printf("%d %d",p,*L);  //p = 0;*L = 7279912
 40     free(*L);
 41     printf("%d ",*L);      //*L = 7279912
 42 analise the reason for error by the result of "printf"
 43 free(p) is release the block of memory pointed by P,
 44 dose not change pointer p itself.  NULL == 0
 45 */
 46     LinkList q;
 47     while(*L){
 48         q = (*L)->next;
 49         free(*L);
 50         *L = q;
 51     }
 52 }
 53 void ClearList(LinkList *L){
 54     //ClearList(&L);
 55 //    LinkList p = *L;
 56 //    LinkList q;
 57 //
 58 //    TailCreateList(&L,4);
 59 //    DisplayList(L);
 60 //    ClearList(&L);
 61 //    TailCreateList(&L,4);
 62 
 63     LinkList p = (*L)->next;
 64     LinkList q;
 65     while(p){
 66         q = p -> next;
 67         free(p);
 68         p = q;
 69     }
 70     (*L)->next = NULL;
 71     printf("LinkList has been clear!\n");
 72 }
 73 void ListEmpty(LinkList L){
 74     if(L->next == NULL)
 75         printf("List empty!\n");
 76     else 
 77         printf("Exit Element in List\n");
 78 }
 79 int ListLength(LinkList L){
 80     LinkList p = L->next;
 81     int count = 0;
 82     while(p){
 83         count+=1;
 84         p = p->next;
 85     }
 86     return count;
 87 }
 88 int GetElem(LinkList L,int index,int *r){
 89     int length = ListLength(L);
 90     if(index < 1 || index > length){
 91         return 0; //failed
 92     }else{
 93         int j = 0;
 94         while(j<index){
 95             L = L->next;
 96             j++;
 97         }
 98         *r = L->data;
 99         return 1;
100     }
101 }
102 void GetPriorElem(LinkList L,int current_elem,int *priorElement){
103 /*
104     LinkList p = L->next;
105     LinkList q;
106     if(p == NULL){
107         printf("List is Empty!\n");
108         exit(1);
109     }
110     if(p->data == current_elem){
111         printf("the current element is first!\n");
112         exit(1);
113     }
114     q = p->next;
115     while(q && q->data != current_elem){
116         p = q;q = q->next;
117     }
118     if(q == NULL){
119         printf("there is no current in List!\n");
120         exit(1);
121     }
122     else
123         *priorElement = p->data;
124 */
125 /*
126 the promise of the following code is that the 
127 current_element is not the first element of the
128 list and does not consider the case of the list
129 for NULL
130 */
131     LinkList p = L->next; //p point first node
132     LinkList q;
133     while(p->next){
134         q = p->next;
135         if(q->data == current_elem){
136             *priorElement = p->data;
137             break;
138         }
139         p = q;
140     }
141     if(p->next == NULL)
142         printf("there is no current_element in List\n");
143 }
144 void GetNextElem(LinkList L,int current_elem,int* next_elem){
145     LinkList p = L->next;
146     LinkList q;
147     if(p == NULL){
148         printf("List is Empty!\n");
149         exit(1);
150     }
151     while(p->next){
152         q = p->next;
153         if(p->data == current_elem){
154             *next_elem = q->data;
155             return;
156         }
157         p = q;
158     }
159     printf("GetNextElement is Failed!\n");
160 }
161 void HeadCreateList(LinkList* L,int n){
162     LinkList s;
163     int i;
164     int e;
165     for(i = 1;i <= n; i++){
166         printf("enter %d integer: ",i);
167         scanf("%d",&e);
168         s = (LinkList)malloc(sizeof(struct Node));
169         s->data = e;
170         s->next = (*L)->next;
171         (*L)->next = s;
172     }
173     printf("\n");
174 }
175 void TailCreateList(LinkList* L,int n){
176     LinkList tail = *L;
177     LinkList s;
178     int i;
179     int e;
180     for(i = 1;i <= n; i++){
181         printf("enter %d integer: ",i);
182         scanf("%d",&e);
183         s = (LinkList)malloc(sizeof(struct Node));
184         s->data = e;
185         tail->next = s;
186         s->next = NULL;
187         tail = s;
188     }
189     printf("\n");
190 }
191 void ListInsert(LinkList* L,int index,int e){
192 /*
193 //insert element before index
194     LinkList q;
195     LinkList p = *L;
196     LinkList s;
197     int count = 0;
198     while(p->next){
199         q = p->next;
200         count += 1;
201         if(count == index){
202             s = (LinkList)malloc(sizeof(struct Node));
203             s -> data = e;
204             p->next = s;
205             s->next = q;
206             break;
207         }
208         p = q;
209     }
210     if(p->next == NULL){
211         printf("InsertList Index Error!\n");
212     }
213 */
214 //options
215     LinkList p = *L;
216     LinkList s;
217     int count = 0;
218     while(p && count<index-1){
219         p = p->next;
220         count += 1;
221     }
222     if(p){
223         s = (LinkList)malloc(sizeof(struct Node));
224         s->data = e;
225         s->next = p->next;
226         p->next = s;
227     }
228     if(p == NULL){
229         printf("InsertList Index Error!\n");
230     }
231 }
232 void ListDelete(LinkList *L,int index,int* e){
233     LinkList p = *L;
234     int count = 0;
235     while(p && count < index - 1){
236         p = p->next;
237         count += 1;
238     }
239     if(p){
240         if(p->next){
241             *e = p->next->data;
242             p->next = p->next->next;
243         }
244         else
245             printf("DeleteList Index Error\n");
246     }
247     if(p == NULL)
248         printf("DeleteList Index Error\n");
249 }
250 void DisplayList(LinkList L){
251     if(L == NULL){
252         printf("List has been destory!\n");
253     }else
254     {
255         LinkList p = L;
256         while(p -> next){
257             printf("%d ",p->next->data);
258             p = p->next;
259         }
260         printf("\n********displayList executed!\n");
261     }
262 }
263 void main(){
264 //    Node L;
265 //    LinkList L1 = &L;
266 //    InitLinkList(&L1);
267 
268     LinkList L;
269     InitList(&L);
270     TailCreateList(&L,4);
271     DisplayList(L);
272     ClearList(&L);
273     ListEmpty(L);
274     DisplayList(L);
275     DestoryList(&L);
276     DisplayList(L);
277 
278     InitList(&L);
279     TailCreateList(&L,5);
280     printf("Length of List is: %d\n",ListLength(L));
281     DisplayList(L);
282 
283     int r0;
284     if(GetElem(L,5,&r0)){
285         printf("getelement index=5 is : %d\n",r0);
286     }
287     else
288         printf("getelement index=5 is Failed\n");
289 
290     if(GetElem(L,6,&r0)){
291         printf("getelement index=6 is : %d\n",r0);
292     }
293     else
294         printf("getelement index=6 is Failed\n");
295 
296     int r1;
297     GetPriorElem(L,3,&r1);
298     printf("the result of GetPriorElement(3) is: %d\n",r1);
299 
300     int r2;
301     GetNextElem(L,3,&r2);
302     printf("the result of GetNextElement(3) is: %d\n",r2);
303     ListInsert(&L,5,999);
304     DisplayList(L);
305 
306     int r3;
307     ListDelete(&L,2,&r3);
308     DisplayList(L);
309     printf("execute ListDelete index=2 is %d\n",r3);
310 }