文章目錄

• 鏈表（Linked Table）
• • 1.單鏈表（singly linked list）
  • • 元素的構成
    • 鏈表的基本操作
    • • 鏈表的創建
      • 遍歷操作
      • 查找操作
      • 插入操作
      • 刪除操作

鏈表（Linked Table）

線性表的鏈式存儲結構生成的表，稱作“鏈表”。

鏈表分為單向鏈表和雙向鏈表。

1.單鏈表（singly linked list）

單鏈表（singly linked list）是用一組任意的存儲單元存放的線性表元素，這組存儲單元可以連續也可以不連續，甚至可以零散分布在內存中的任意位置。為了能夠體現出數據元素之間的邏輯關系，每個存儲單元在在存儲數據元素的同時，還必須存儲其后繼元素所在的地址信息，這個地址信息稱為指針，這兩部分組成了數據元素的存儲映像，稱為結點（node）。

鏈表的簡單原理圖如圖：

結點結構如圖所示：

元素的構成

每個元素本身由兩部分組成：

data 稱為“數據域”，用來存放數據元素（可以是一個成員，或多個成員）；

next 稱為“指針域”，用來存放該結點的后繼結點的地址。

單鏈表正是通過每個結點的指針域將線性表的數據元素按其邏輯次序鏈接在一起，由于每個結點只有一個指針域，故稱為單鏈表。

單鏈表中每個結點的存儲地址存放在其前驅結點的next域中，而第一個元素無前驅，所以設頭指針（head pointer）指向第一個元素所在結點（稱為開始結點），整個單鏈表的存取必須從頭指針開始進行，因而頭指針具有標識一個單鏈表的作用；同時，由于最后一個元素無后繼，故最后一個元素所在結點（稱為終端結點）的指針域為空，即NULL。

指向第一個結點（開始結點）的指針必須保存，否則該鏈表將會消失。通常在單鏈表的開始結點之前附設一個類型相同的結點，稱為頭結點（head node）。加上頭結點之后，無論單鏈表是否為空，頭指針始終指向頭結點。

鏈表結點中包含一個指針變量，用于存放下一個Node結構結點的地址，所以該指針必須是與結構體相同的數據類型。

typedef int ElementType; struct Node {ElementType data; //ElementType是date的數據類型struct Node *Next; //指向直接后繼元素的指針 };

鏈表的基本操作

在構建鏈表時，需要逐個創建結點，并且把生成的每個結點加入到鏈表中。創建結點包括3個步驟：

為結點分配內存單元；

把數據存儲到結點中；

把結點插入到鏈表中。

鏈表的創建

創建一個僅含頭結點的空鏈表：

typedef struct Node *List; int iCount = 0; //記錄鏈表長度的全局變量 List InitList() {struct Node *pHead = (struct Node*)malloc(sizeof(struct Node)); //為頭結點分配內存空間pHead->Next = NULL;iCount = 0;return pHead; }

鏈表還可以使用頭指針創建

List InitList() {List pHead = NULL; //頭指針為空return pHead; }

遍歷操作

遍歷打印鏈表元素

void PrintList(List L) {List p = L->Next; //工作指針p初始化while(p != NULL){printf("%d\n",p->data);p = p->Next;} }

求線性表長度

int Length(List L) {List p = L->Next; //工作指針p初始化int count = 0; //累加器count初始化while(p != NULL){p = p->Next;count++;}return count; }

查找操作

按位查找：從頭結點出發順Next域逐個結點向下搜索，當工作指針p指向某個結點時判斷是否為第 i 個結點，若是，則查找成功；否則，將工作指針后移。對每個結點依次執行上述操作，知道p為NULL時查找失敗。

ElementType GetData(List L, int i) {List p = L->Next; //工作指針p初始化，指向頭結點后的第一個元素int count = 1; //累加器count初始化while(p != NULL && count < i){p = p->Next;count++;}if(p == NULL) {printf("The input position exceeds the length of the linked list");}elsereturn p->data; }

按值查找：對鏈表中的元素依次進行比較，如果查找成功，返回元素的序號，如果查找不成功，則返回0表示查找失敗。

int Locate(List L, ElementType element) {List p = L->Next; //工作指針p初始化，指向頭結點后的第一個元素int count = 1; //累加器count初始化while(p != NULL){if(p->data == element)return count; //查找成功，結束函數并返回序號p = p->Next;count++;}return 0; //表示查找失敗，返回0 }

插入操作

每次加入一個結點，使用循環可創建一個含有n個結點的單鏈表

頭插法：

頭插法是每次將新申請的結點插在頭結點的后面，其執行過程如圖所示。

void ListHeadInsert(List L) {char c;List pHead = L;char flag;List pNew;do{iCount++;pNew = (struct Node *)malloc(sizeof(struct Node));printf("Please enter the Number\n");scanf("%d",&pNew->data);pNew->Next = pHead->Next; //新結點的指針指向頭結點原指向的位置pHead->Next = pNew; //頭結點指針指向新結點printf("Do you want to continue typing?(y/n)\n");while((c = getchar()) != '\n' && c != EOF);//不停地使用getchar()獲取緩沖中字符，直到獲取的c是“\n”或文件結尾符EOF為止scanf("%c",&flag);}while('y' == flag); }

尾插法：

尾插法就是每次將新申請的結點插在終端結點的后面，其執行過程如圖所示。

void ListEndInsert(List L) {char c;List pHead = L;char flag;List pNew, pEnd;pEnd = pHead; //尾指針初始化，指向頭結點do{iCount++;pNew = (struct Node *)malloc(sizeof(struct Node));printf("Please enter the Number\n");scanf("%d",&pNew->data);pEnd->Next = pNew; //尾指針指向新結點pEnd = pNew; //pEnd指向新結點printf("Do you want to continue typing?(y/n)\n");while((c = getchar()) != '\n' && c != EOF);//不停地使用getchar()獲取緩沖中字符，直到獲取的c是“\n”或文件結尾符EOF為止scanf("%c",&flag);}while('y' == flag);pEnd->Next = NULL; }

和前面的創建初始化寫在一起可以創建一個含N個元素的鏈表。

向鏈表中任意位置插入結點，插入到第 i 個位置，即插入到鏈表 i-1 與 i 之間。必須先掃描鏈表找到 i-1 的存儲地址 p ，然后生成一個新的結點 pNew，將 pNew 的Next域指向第 i 個結點，將結點 p 的Next域指向新結點。

void Insert(List L, int i, ElementType element) {List pNew;List p = L; //工作指針p初始化，指向頭結點int count = 0; //累加器count初始化while(p != NULL && count < i-1) //查找第 i-1 個結點{p = p->Next; //工作指針后移count++;}if(p == NULL) {printf("The input position exceeds the length of the linked list");}else{pNew = (struct Node *)malloc(sizeof(struct Node));pNew->data = element;pNew->Next = p->Next;p->Next = pNew; //將新結點插入到結點p之后iCount++; //鏈表長度加1} }

刪除操作

將單鏈表的第 i 個結點刪去，首先要找到 i-1 個結點的存儲地址p，然后令p的Next域指向 i 的后繼結點，釋放結點 i 的存儲空間。被刪結點的的前驅結點p存在且不是終端結點時，才能確定被刪結點存在。

void Delete(List L, int i) {List pTemp;List p = L; //工作指針p初始化，指向頭結點int count = 0; //累加器count初始化while(p != NULL && count < i-1) //查找第 i-1 個結點{p = p->Next; //工作指針后移count++;}if(p == NULL || p->Next == NULL) {printf("The input position exceeds the length of the linked list");}else{pTemp = p->Next; //暫存被刪結點p->Next = pTemp->Next; //摘鏈free(pTemp);iCount--; //鏈表長度減1} }

刪除整個鏈表

void DeleteList(List L) {List p, pTemp;p = L->Next;L->Next = NULL;while(p != NULL){pTemp = p->Next;free(p);p = pTemp;iCount--;} }

總結

以上是生活随笔為你收集整理的线性表（二）——链表的全部內容，希望文章能夠幫你解決所遇到的問題。

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