數據結構與算法筆記 cp2-2：線性表

2019 年 11 月 7 日
筆記

線性表的鏈式存儲結構 / 鏈表

1.1 定義：

線性表的鏈式存儲結構不限制數據元素的物理存儲狀態，也就是說，其數據元素的物理位置是隨機的。

對於每一個元素來說，它需要存儲自身信息在數據域中，還需要存儲直接後繼的位置信息在指針域中，這兩部分信息共同構成一個結點（Node）。n 個結點就鏈結成一個鏈表，如果每一個結點只有一個指針域，那麼它就是單鏈表。

頭指針：頭指針保存第一個結點（首元結點）的存儲位置，因為最後一個結點沒有後繼結點，所以它的指針域為空(NULL / ^)。

頭結點：有時候，首元結點前還會設置一個頭結點，有頭結點的時候，頭指針保存的是頭結點的存儲位置。對於頭結點，其數據域不一定要包含信息，其指針域則保存的是首元結點的存儲位置。如下圖所示：

Tip: 設計頭結點是為了操作的統一。

鏈表並不是隨機存取結構，並不能根據一個給定元素就能馬上找到另一個目標元素，而是只能從頭指針開始順鏈查找，這稱為順序存取結構。

1.2 單鏈表：

在開始之前，我們還是先定義單鏈表中每個結點的結構：

typedef struct Link{      char elem; // 數據域      struct Link * next; // 指針域  }link; // link為結點名，每個結點都是一個 link 結構體

Tip：因為指針也是指向一個結點，這裡尤其要注意將指針類型聲明為 struct Link

(1) 初始化空表：

link * initLink(){      link * p=(link*)malloc(sizeof(link));// 創建一個頭結點      link * temp=p;// 聲明頭指針並指向頭結點      temp->next=NULL; // 頭結點的指針域置空      return p;  }

(2) 整表創建：

例如，創建一個存儲 {1,2,3,4} 且無頭結點的鏈表：

link * initLink(){      link * temp = (link*)malloc(sizeof(link));// 創建首元結點      link * p = temp;// 創建頭指針並指向首元結點        // 首元節點先初始化      temp->elem = 1;      temp->next = NULL;        // 從第二個節點開始創建      for (int i=2; i<5; i++) {       // 創建一個新節點並初始化          link *a=(link*)malloc(sizeof(link));          a->elem=i;          a->next=NULL;          // 將temp節點與新建立的a節點建立邏輯關係          temp->next=a;          // 指針temp每次都指向新鏈表的最後一個節點          temp=temp->next;      }      //返回建立的節點，只返回頭指針 p 即可，通過頭指針即可找到整個鏈表      return p;  }

(3) 查找元素：

p 為原鏈表，elem 表示被查找的元素  int selectElem(link * p,int elem){      // 新建一個指針，直接指向首元結點      link * t = p->next;      while(t && t->elem!= elem){          t=t->next;      }      return p;  }

因為存在頭結點，所以這裡首先獲取首元結點，然後從首元結點開始依次往後面遍歷，查找是否有符合的元素。如果查找成功，返回的 p 是元素的地址，查找失敗則返回 NULL。

(4) 修改元素：

// add 表示更改結點在鏈表中的位置，newElem 為新的數據域的值  link *amendElem(link * p,int add,int newElem){      link * temp=p->next;      // 遍歷到被刪除結點      for (int i=1; i<add; i++) {          temp=temp->next;      }      temp->elem=newElem;      return p;  }

(5) 刪除元素： 包括兩步，一個是摘除結點並改變連接，一個是釋放被摘除結點的內存。關鍵代碼是：

temp->next=temp->next->next;

如下圖所示：

具體實現代碼是：

//p為原鏈表，add為要刪除元素的值  link * delElem(link * p,int add){      // temp 首先指向首元結點      link * temp=p;      // 先尋找被刪除結點的上一個結點      for (int i=1; i<add-1; i++) {          temp=temp->next;      }      link * del=temp->next;// 單獨設置一個指針指向被刪除結點，後面方便釋放其內存      temp->next=temp->next->next;      free(del);// 手動釋放該結點，防止內存泄漏      return p;  }

注意這是沒有頭結點的情況，如果有頭結點，循環判斷應該是 i<add，因為這時候的 temp 指向的是頭結點。

(6) 插入元素： 包括兩步，一個是將插入位置後的結點作為新結點的 next，一個是將新結點作為插入位置前的結點的 next，也就是關鍵代碼：

new->next=temp->next;  temp->next=new;

如下圖所示：

注意：這裡順序不能顛倒，如果是先確定插入位置前結點和新結點的連接，那麼插入位置後結點將無法獲取，因為其獲取是依賴於插入位置前結點的next的，而這個next已經被覆蓋。

具體代碼為：

// p為原鏈表，elem表示新數據元素，add表示新元素插入的位置  link * insertElem(link * p,int elem,int add){      link * temp=p;// 創建指向頭結點的指針      // 遍歷尋找插入位置前的結點      for(int i=1;i<add;i++){          if(temp==NULL){              printf("插入位置無效n");              return p;          }          temp=temp->next;      }      // 創建新結點並初始化      link * c=(link*)malloc(sizeof(link));      c->elem=elem;      // 改變連接關係      c->next=temp->next;      temp->next=c;      return p;  }

if 語句用來判斷 add 是否合法，因為如果 add 過大，那麼一直遍歷下去會得到一個 next 為 NULL 的temp，之後報錯。

1.3 循環鏈表：

當單鏈表中最後一個結點的指針域不為空，而是指向頭結點的時候，就形成一個環，這叫循環鏈表。循環鏈表進行元素遍歷的時候，循環終止條件不再是 p->next=NULL，而是 p->next=L。

如果使用尾指針，那麼可以用O(1)的時間找到尾結點和首元結點，而且可以簡化合併兩個循環鏈表的過程：

對於上面這兩個循環鏈表，合併的思路大概是：A表尾連B表頭。所以這裡要改變 rearA->next，事先要先保存一開始的 rearA->next，即A表的頭結點，之後將B表的首元結點給 rearA->next；之後我們要將一開始保留的A表頭結點作為 rearB->next，事先要先保存一開始的 rearA->next，即B表的頭結點，方便最後釋放內存。

用圖片表示的思路是：

用代碼表示的思路是：

p=rearA->next;  rearA->next=rearB->next->next;  reerB->next=p;  free(p);

1.4 雙向鏈表

單鏈表的每一個結點中，額外多出一個指向前驅結點的指針域，這時候就成了雙向鏈表。雙向鏈表的尾結點指針域指向頭結點時，就成了雙向循環鏈表，如下圖：

插入操作

插入操作一定要注意順序，我們可以先處理新結點的前驅和後繼，之後再依次處理後結點、前結點。

// 新結點的前驅後繼  s->prior = p;  s->next = p->next;  // 後結點  p->next->prior = s;  // 前結點  p->next = s;

刪除操作

刪除很簡單，如下圖把中間的p刪除，那麼對於後結點，我們要修復它的前驅指針；對於前結點，我們要修復它的後繼指針，最後一步是釋放被刪除結點的內存

p->prior->next = p->next;  p->next-prior = p->prior;