學習鏈式線性表

來自專欄 前端數據結構與演算法

這是專欄的第二篇文章啦~今天從c語言和javascript兩個方向來看鏈式線性表~

在上一篇學習順序線性表中提到了線性表，其實就是由同類型數據元素構成有序序列的線性結構，順序線性表呢就是在內存中連續存儲的線性表，而鏈式線性表則是通過指向下一項的指針來對元素進行連接，對於每一個元素都可以通過next指針知道它的下一個元素是誰，所以如果要知道鏈式線性表的長度則需要對每一個元素進行遍歷，但是插入刪除只需要改變next指針的指向，所以有利也有弊嘛...

定義結構體

typedef struct Node{ ElementType Data; struct Node *Next;}List;

這裡和上次的順序線性表不同，這裡的結構體的第二個元素是自定的Node類型的指針，負責指向下一個元素，不過使用倒是類似，例如：

List *PtrL;PtrL -> Next;

建立空表

List *MakeEmpty(List *PtrL) { PtrL = (List *)malloc(sizeof(List)); PtrL -> Next = NULL; return PtrL;}

這裡的建立空表唯一要注意的就是PtrL->Next=NULL，意思是空表的next指針為null，在接下來在表尾插入一個節點時也要注意把它的next指針設為null，這樣求表長的時候就可以通過next指針是否為null來判斷鏈表是否結束。

還有就是malloc函數分配完地址之後返回首節點的問題~

求表長（時間複雜度為O(n)）

int Length(List *PtrL) { List *p = PtrL;// p目前指向的是第一個節點，PtrL始終指向第一個節點 int j = -1;// 建立空表的時候多建了一個空節點，所以j從-1開始 while (p) { p = p -> Next;// 更換p的指向 j++; } return j;}

這裡要注意是注釋的部分，關於j的起始值可以在實例測試的時候再行思考。

按序號查找（時間複雜度為O(n)）

List *FindKth(int K, List *PtrL) { List *p = PtrL; int i = 1; while (p != NULL && i < K) { p = p -> Next; i++; } if (i == K) return p; else return NULL;}

按值查找（時間複雜度為O(n)）

List *Find(ElementType X, List *PtrL) { List *p = PtrL; while (p != NULL && p -> Data != X) p = p -> Next; return p;}

由於在內存分布上不均勻所以查找自然就是與表長有關的啦！

插入（時間複雜度為O(n)）

List *Insert(ElementType X, int i, List *PtrL) { List *p, *s; if (i == 1) { s = (List *)malloc(sizeof(List)); s -> Data = X; s -> Next = PtrL; return s; } p = FindKth(i - 1, PtrL); if (p == NULL) { printf("參數i錯誤"); return NULL; } else { s = (List *)malloc(sizeof(List)); s -> Data = X; s -> Next = p -> Next; p -> Next = s; return PtrL; }}

插入才是重頭戲啊！

首先對於一個節點要先分配空間出來，然後如果要將它插在第一個，則原來的頭結點PtrL則成為當前要插入節點的next節點，首節點插入就完成了。

而如果是要插到中間，這時就會發現按序號查找返回指針p的行為是多麼的機智了，將要插入節點的next指針指向找到的p的下一個節點，再將p的next指針指向插入的節點，插入就是這麼簡單。

刪除（時間複雜度為O(n)）

List *Delete(int i, List *PtrL) { List *p, *s; if (i == 1) { s = PtrL; PtrL = PtrL -> Next; free(s); return PtrL; } p = FindKth(i - 1, PtrL); if (p = NULL) { printf("第%d個結點不存在", i - 1); return NULL; } else if (p -> Next == NULL) { printf("第%d個結點不存在", i); return NULL; } else { s = p -> Next; p ->Next = s -> Next; free(s); return PtrL; }}

刪除其實和插入套路相似，如果要刪除第一個節點則將指向第一個節點的指針越過第一個節點，指向其next節點。

不是第一個的話則要先找到要刪除的節點的位置，然後再越過該節點，將前一個元素的next指向該元素的next，再將該元素釋放掉~

具體的main函數代碼可以看github中該repo的第二個issue

接下來是友善的部分

來看一下在javascript中鏈式線性表是怎樣實現的：

function LinkedList() { // 表示要加入鏈表的節點類型，類似於c的結構體 var Node = function(element) { this.element = element; this.next = null; } var length = 0; var head = null;// 指向鏈表第一個元素，類似於c中的PtrL // 向鏈表尾部添加一個新的項 this.append = function(element) { var node = new Node(element), current; if (head === null) {// 沒有第一個元素，那麼當前元素就是第一個 head = node; } else { current = head;// 需要從第一個元素開始往下 while (current.next) { current = current.next; } current.next = node; } length++;// 更新列表長度，就不用專門遍歷求長度了，直接返回length就好 }; // 向鏈表的特定位置插入一個新的項，可以看出並沒有分配空間這一步 this.insert = function(position, element) { if (position >= 0 && position <= length) { var node = new Node(element), current = head, previous, index = 0; if (position === 0) { head = node; node.next = current; } else { while (index++ < position) { previous = current; current = current.next; } previous.next = node; node.next = current; } length++; return true; } else { return false; } }; // 從鏈表特定位置移除一項，並返回被刪除的一項 this.removeAt = function(position) { if (position > -1 && position < length) { var current = head, previous, index = 0; // 移除第一項 if (position === 0) { head = current.next; } else { while (index++ < position) { previous = current; current = current.next; } previous.next = current.next; } length--; return current.element; } else { return null; } }; // 移除鏈表中的某一項 this.remove = function(element) { var index = this.indexOf(element); return this.removeAt(index); }; // 返回鏈表中某一項的下標 this.indexOf = function(element) { var current = head, index = -1; while (current) { if (element === current.element) { return index; } index++; current = current.next; } return -1; }; // 若鏈表為空則返回true this.isEmpty = function() { return length === 0; }; // 返回鏈表長度（元素個數） this.size = function() { return length; }; // 輸出元素的值 this.toString = function() { var current = head, str = , string = ; while (current) { string += current.element + str; current = current.next; } return string; }; // 輸出鏈表 this.print = function() { console.log(this.toString()); }; // 獲得首元素 this.getHead = function() { return head; }}

具體的代碼看這裡，js的部分相信大家很好懂啊~

推薦閱讀：