這篇文章主要是根據《數據結構與算法分析--C語言描述》一書的鏈表章節內容所寫，該書作者給出了鏈表ADT的一些方法，但是并沒有給出所有方法的實現。在學習的過程中將練習的代碼記錄在文章中，并添加了一些在測試中需要的函數，因此可能看起來會有點亂。。。

　　首先，鏈表作為一種簡單的線性數據結構，主要特征就是“節點”，每個節點包含兩個信息，一個是數據域，另外一個是指針域。數據是我們在程序中需要用到的數據，數據類型可以變化，根據需要設定即可，但是指針域就是一個指針，主要作用是指向下一個節點，就是依靠這些指針才將一個一個的節點串起來，就像串辣椒一樣，只要提起一串辣椒的頭部，那么這一串辣椒中的每一個就都可以按照順序找到。理解鏈表的最好的方式就是用圖形的方式，其實大部分數據結構教材都是利用圖形的方法來講解大部分數據結構的，人的大腦對圖形的理解明顯比文字要更好一些。啥都不說了，打開AUTOCAD，畫個圖。

上圖就是一個鏈表結構，其中A1到A5 是我們要用到的數據，Ptr是指針的名字，箭頭指向被指針指向的節點。最左邊有一個被稱之為頭節點的節點，這是一個沒有數據，只有指向第一個真正存儲數據的節點的節點，有的人在鏈表中不使用頭節點。

下面看看鏈表的一些操作，首先分析一下，鏈表需要 一個創建程序，就是創建一個鏈表，可以叫做CreateList()，還需要判斷鏈表是否為空的，叫做IsEmpty()，還有需要向鏈表中插入元素，可以叫做Insert()，同樣需要刪除元素 Delete()。這是最主要的幾個操作。

上面提到的書的作者給出了幾種方法：

1 #ifndef _LIST_H_ 2 #define _LIST_H_ 3 4 typedef int ElementType; 5 struct Node; 6 typedef struct Node *PtrToNode; 7 typedef PtrToNode List; 8 typedef PtrToNode Position; 9 10 List CreateList(); 11 List Makeempty(List L); 12 13 int IsEmpty(List L); 14 int IsLast(Position P, List L); 15 Position Find(ElementType X,List L); 16 void Delete(ElementType X,List L); 17 Position FindPrevious(ElementType X,List L); 18 void Insert(ElementType X,List L,Position P); 19 void DeleteList(List L); 20 Position Header(List L); 21 Position First(List L); 22 Position Advance(Position P); 23 ElementType Retrieve(Position P); 24 25 #endif

比較多，但是都比較簡單，來看看作者的實現

1 #include"linkedlist.h" 2 #include<stdlib.h> 3 4 typedef int ElementType; 5 struct Node 6 { 7 ElementType Element; 8 Position Next; 9 }; 10 11 void PrintList(List L) 12 { 13 Position P; 14 P = L->Next; 15 while(P != NULL) 16 { 17 printf("%d ",P->Element); 18 P = P->Next; 19 } 20 } 21 22 List CreateList() 23 { 24 List L ; 25 L = malloc(sizeof(struct Node)); 26 L->Next = NULL; 27 return L; 28 } 29 30 31 32 List MakeEmpty(List L) 33 { 34 Position P,Tmp; 35 P = L->Next; 36 L->Next = NULL; 37 while(P != NULL) 38 { 39 Tmp = P->Next; 40 free(P); 41 P = Tmp; 42 } 43 return L; 44 } 45 void Printlist(List L) 46 { 47 Position P; 48 P = L->Next; 49 while(P != NULL) 50 { 51 printf("%d",P->Element); 52 P = P->Next; 53 } 54 } 55 56 int IsEmpty(List L) 57 { 58 return L->Next == NULL; 59 } 60 61 int IsLast(Position P,List L) 62 { 63 return P->Next == NULL; 64 } 65 66 Position Find(ElementType X,List L) 67 { 68 Position P; 69 P = L->Next; 70 while(P != NULL && P->Element != X) 71 P = P->Next; 72 return P; 73 } 74 75 void Delete(ElementType X,List L) 76 { 77 Position P, TemCell; 78 P = FindPrevious(X,L); 79 if(!IsLast(P,L)) 80 { 81 TemCell = P->Next; 82 P->Next = TemCell->Next; 83 free(TemCell); 84 } 85 } 86 87 Position FindPrevious(ElementType X,List L) 88 { 89 Position P; 90 P = L; 91 while(P->Next != NULL && P->Next->Element != X) 92 P = P->Next; 93 return P; 94 } 95 96 97 void Insert(ElementType X ,List L,Position P) 98 { 99 Position TmpCell ; 100 TmpCell = malloc (sizeof(struct Node)); 101 102 TmpCell->Element = X; 103 TmpCell->Next = P->Next; 104 P->Next = TmpCell; 105 }

?

轉載于:https://www.cnblogs.com/wangxiaoyong/p/6789155.html

總結

以上是生活随笔為你收集整理的数据结构入门之链表（C语言实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。