數據結構——考研筆記（三）線性表之單鏈表

文章目錄

- - 2.3 單鏈表
  - - 2.3.1 知識總覽
    - 2.3.2 什么是單鏈表
    - 2.3.3 不帶頭結點的單鏈表
    - 2.3.4 帶頭結點的單鏈表
    - 2.3.5 不帶頭結點 VS 帶頭結點
    - 2.3.6 知識回顧與重要考點
    - 2.3.7 單鏈表的插入和刪除
    - - 2.3.7.1 按位序插入（帶頭結點）
      - 2.3.7.2 按位序插入（不帶頭結點）
      - 2.3.7.3 指定結點的后插操作
      - 2.3.7.4 指定結點的前插操作
      - 2.3.7.5 按位序刪除（帶頭結點）
      - 2.3.7.6 知識回顧與重要考點
    - 2.3.8 單鏈表的查找
    - - 2.3.8.1 按位查找
      - 2.3.8.2 按值查找
      - 2.3.8.3 知識回顧與重要考點
    - 2.3.9 單鏈表的建立
    - - 2.3.9.1 尾插法
      - 2.3.9.2 頭插法

2.3 單鏈表

2.3.1 知識總覽

2.3.2 什么是單鏈表

順序表：
- 優點：可隨機存取，存儲密度高
- 缺點：要求大片連續空間，改變容量不方便
單鏈表：
- 優點：不要求大片連續空間，改變容量方便
- 缺點：不可隨機存取，要消耗一定空間存放指針
用代碼實現單鏈表

typedef struct LNode{			//定義單鏈表結點類型ElemType data;		//每個節點存放一個數據元素struct LNode* next;  //指針指向下一個節點
}LNode,*LinkList;

2.3.3 不帶頭結點的單鏈表

#include <stdlib.h>typedef struct LNode {	//定義單鏈表結點類型int data;			//每個節點存放一個數據元素struct LNode* next; //指針指向下一個節點
}LNode,*LinkList;//初始化一個空的單鏈表
bool InitList(LinkList& L) {L = NULL;	//空表，暫時還沒有任何結點return true;
}//判斷單鏈表是否為空
bool Empty(LinkList L) {if (L == NULL)return true;elsereturn false;
}void test() {LinkList L;	//聲明一個指向單鏈表的指針//初始化一個空表InitList(L);//……后續代碼……
}

2.3.4 帶頭結點的單鏈表

#include <stdlib.h>typedef struct LNode {	//定義單鏈表結點類型int data;			//每個節點存放一個數據元素struct LNode* next; //指針指向下一個節點
}LNode, * LinkList;//初始化一個空的單鏈表
bool InitList(LinkList& L) {L = (LNode*)malloc(sizeof(LNode));	//分配一個頭節點if (L == NULL)			//內存不足，分配失敗return false;L->next = NULL;			//頭結點之后暫時還沒有節點return true;
}//判斷單鏈表是否為空
bool Empty(LinkList L) {if (L->next == NULL)return true;elsereturn false;
}void test() {LinkList L;	//聲明一個指向單鏈表的指針//初始化一個空表InitList(L);//……后續代碼……
}

2.3.5 不帶頭結點 VS 帶頭結點

不帶頭結點：寫代碼更麻煩對第一個數據結點和后續數據結點的處理需要用不同的代碼邏輯對空表和非空表的處理需要用到不同的代碼邏輯
帶頭結點：寫代碼更方便。

2.3.6 知識回顧與重要考點

2.3.7 單鏈表的插入和刪除

2.3.7.1 按位序插入（帶頭結點）

ListInsert(&L,i,e)：插入操作。在表L中的第i個位置上插入指定元素e。

代碼展示

#include <stdlib.h>typedef struct LNode {	//定義單鏈表結點類型int data;			//每個節點存放一個數據元素struct LNode* next; //指針指向下一個節點
}LNode, * LinkList;//初始化一個空的單鏈表
bool InitList(LinkList& L) {L = (LNode*)malloc(sizeof(LNode));	//分配一個頭節點if (L == NULL)			//內存不足，分配失敗return false;L->next = NULL;			//頭結點之后暫時還沒有節點return true;
}//判斷單鏈表是否為空
bool Empty(LinkList L) {if (L == NULL)return true;elsereturn false;
}//在第i個位置插入元素e(帶頭結點)
bool ListInsert(LinkList& L, int i, int e) {if (i < 1)return false;LNode* p;	//指針p指向當前掃描到的結點int j = 0;	//當前p指向的是第幾個結點p = L;		//L指向頭結點，頭結點是第0個結點（不存數據）while (p != NULL && j < i - 1) {	//循環找到第i-1個結點p = p->next;j++;}if (p == NULL)	//i值不合法return false;LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;	//將結點s連到p之后return true;	//插入成功
}void main() {LinkList L;	//聲明一個指向單鏈表的指針//初始化一個空表InitList(L);//……后續代碼……
}

2.3.7.2 按位序插入（不帶頭結點）

代碼展示

#include <stdlib.h>typedef struct LNode {	//定義單鏈表結點類型int data;			//每個節點存放一個數據元素struct LNode* next; //指針指向下一個節點
}LNode, * LinkList;//初始化一個空的單鏈表
bool InitList(LinkList& L) {L = (LNode*)malloc(sizeof(LNode));	//分配一個頭節點if (L == NULL)			//內存不足，分配失敗return false;L->next = NULL;			//頭結點之后暫時還沒有節點return true;
}//判斷單鏈表是否為空
bool Empty(LinkList L) {if (L == NULL)return true;elsereturn false;
}//在第i個位置插入元素e(帶頭結點)
bool ListInsert(LinkList& L, int i, int e) {if (i < 1)return false;if (i = 1) {	//插入第1個結點的操作與其它結點的操作不同LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;s->next = L;L = s;		//頭指針指向新節點return true;}LNode* p;	//指針p指向當前掃描到的結點int j = 1;	//當前p指向的是第幾個結點p = L;		//L指向頭結點，頭結點是第0個結點（不存數據）while (p != NULL && j < i - 1) {	//循環找到第i-1個結點p = p->next;j++;}if (p == NULL)	//i值不合法return false;LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;	//將結點s連到p之后return true;	//插入成功
}void main() {LinkList L;	//聲明一個指向單鏈表的指針//初始化一個空表InitList(L);//……后續代碼……
}

2.3.7.3 指定結點的后插操作

//后插操作：在p結點之后插入元素e
bool InsertNextNode(LNode* p, int e) {if (p == NULL)return false;LNode* s = (LNode*)malloc(sizeof(LNode));if (s == NULL)	//內存分配失敗return false;s->data = e;	//用結點s保存數據元素es->next = p->next;p->next = s;	//將結點s連到p之后return true;
}

2.3.7.4 指定結點的前插操作

代碼展示

//前插操作：在p結點之前插入元素e
bool InsertPriorNode(LNode* p, int e) {if (p == NULL)		//內存分配失敗return false;LNode* s = (LNode*)malloc(sizeof(LNode));s->next = p->next;p->next = s;		//新結點s連到p之后s->data = p->data;	//將p中元素復制到s中p->data = e;		//p中元素覆蓋為ereturn true;
}

2.3.7.5 按位序刪除（帶頭結點）

ListDelete(&L,i,&e)：刪除操作。刪除表L中第i個位置的元素，并用e返回刪除元素的值。

代碼展示

//刪除表中第i個元素
bool ListDelete(LinkList& L, int i, int& e) {if (i < 1)return false;LNode* p;		//指針p指向當前掃描到的結點int j = 0;		//當前p指向的是第幾個結點p = L;			//L指向頭結點，頭結點是第0個結點（不存數據）while (p != NULL && j < i - 1) {	//循環找到第i-1個結點p = p->next;j++;}if (p == NULL)	//i值不合法return false;if (p->next == NULL)	//第i-1個結點之后無其他結點return false;LNode* q = p->next;		//令q指向被刪除結點e = q->data;			//用e返回元素的值p->next = q->next;		//將*q結點從鏈中“斷開”free(q);				//釋放結點的存儲空間return true;			//刪除成功
}

2.3.7.6 知識回顧與重要考點

2.3.8 單鏈表的查找

GetElem(L,i)：按位查找操作。獲取表L中第i個位置的元素的值。
LocalteElem(L,e)：按值查找。在表L中查找具有給定關鍵字值的元素。

2.3.8.1 按位查找

代碼展示

//按位查找，返回第i個元素（帶頭結點）
LNode* GetElem(LinkList L, int i) {if (i < 0)return false;LNode* p;		//指針p指向當前掃描到的結點int j = 0;		//當前p指向的是第幾個結點p = L;			//L指向頭節點，頭結點是第0個結點（不存數據）while (p != NULL && j < i) {	//循環找到第i個結點p = p->next;j++;}return p;
}

2.3.8.2 按值查找

代碼展示

//按值查找，找到數據域==e的結點
LNode* LocateElem(LinkList L, int e) {LNode* p = L->next;//從第1個結點開始查找數據域為e的結點while (p != NULL && p->data != e)p = p->next;return p;	//找到后返回該結點指針，否則返回NULL
}

2.3.8.3 知識回顧與重要考點

2.3.9 單鏈表的建立

如果給你很多個數據元素（ElemType），要把它們存到一個單鏈表里邊，怎么辦呢？

step1：初始化一個單鏈表

step2：每次取一個數據元素，插入到表尾/表頭

2.3.9.1 尾插法

代碼展示

//尾插法
LinkList List_TailInsert(LinkList& L) {	//正向建立單鏈表int x;								L = (LinkList)malloc(sizeof(LNode));//建立頭結點LNode* s, * r = L;					//r為表尾指針scanf("%d", &x);					//輸入結點的值while (x != 9999) {					//輸入9999表示結束s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;							//r指向新的表尾結點scanf("%d", &x);}r->next = NULL;						//尾結點指針置空return L;
}

2.3.9.2 頭插法

代碼展示

//頭插法
LinkList List_HeadInsert(LinkList& L) {LNode* s;int x;L = (LNode*)malloc(sizeof(LNode));	//建立頭結點L->next = NULL;						//初始化空鏈表scanf_s("%d", &x);					//輸入結點的值while (x != 9999) {					//輸入9999表示結束s = (LNode*)malloc(sizeof(LNode));//創建新結點s->data = x;s->next = L->next;L->next = s;					//將新結點插入表中，L為頭指針scanf_s("%d", &x);}return L;
}