数据结构——考研笔记（三）线性表之单链表

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;
}