【408資料結構與算法】—單連結清單（五）

一、什麼是單連結清單

• 單連結清單：每個結點隻有一個指針域
• 雙連結清單：每個結點有兩個指針域
• 循環連結清單：連結清單結點首尾相接

二、帶頭結點的單連結清單

單連結清單是由表頭唯一确定的，是以單連結清單可以用頭指針的名字來命名若頭指針名是L，則連結清單稱為表L

🎊單連結清單的存儲結構

定義連結清單L：​

​LinkList；​

​​ 定義結點指針p:​

​LNode *p<=>LinkList p;​

​

例如：存儲學生學号，姓名，成績的單連結清單結點類型定義如下：

typedef Struct student{
  char num[8];
  char name[8];
  int score;
  struct  student *next;
}Lnode,*LinkList;      

為了統一連結清單的操作，通常這樣定義：

typedef Struct student{
  char num[8];
  char name[8];
  int score;
}ElemType;

typedef struct Lnode{
  ElemType data;
  struct Lnode *next;
  struct Lnode *next;
}Lnode,*LinkList      

三、單連結清單的基本操作

1️⃣單連結清單的初始化

算法的步驟：

• 生成新結點作為頭結點，用頭指針L指向頭結點
• 将頭結點的指針域置空

補充算法1：判斷連結清單是否為空

空表：連結清單中無元素，稱為空連結清單（頭指針和頭結點仍然存在）

補充算法2：單連結清單的銷毀：連結清單銷毀後不存在

算法思路：從頭指針開始，依次釋放所有結點

銷毀單連結清單的算法

補充算法3：單連結清單的清空：連結清單仍然存在，但連結清單中無元素，稱為空連結清單（頭指針和頭結點仍然存在）

算法思路：依次釋放所有的結點，并将頭結點指針域設定為空

補充算法4：求單連結清單的表長

算法思路：從首元結點開始，依次計數所有結點