脚踏实地《数据结构第二章》第三节：单链表

2023-10-25 14:13:22

一：定义与本节概览

二：用代码定义单链表

代码定义：

typedef struct LNode{//定义单链表结点类型
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一个节点
}LNode,*LinkList;

上面定义的代码等价于下面的代码：

struct LNode{//定义单链表结点类型
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一个节点
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;

举例：

typedef struct LNode{//定义单链表结点类型
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一个节点
}LNode,*LinkList;
LNode * GetElem(LinkList L, int i){
	int j=1;
	LNode *p = L->next;
	if(i==0)
		return L;
	if(i<1)
		return NULL;
	while(p!=NULL && j<i){
		p=p->next;
		j++;
	}
	return p;
}

强调这是一个单链表 ——使用LinkList 强调这是一个结点 ―—使用LNode *

2.1 不带头结点的单链表

typedef struct LNode{//定义单链表结点类型
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一个节点
}LNode,*LinkList;
//初始化一个空的链表
bool InitList(LinkList &L){
	L = NULL;//空表，暂时还没有任何结点(防止脏数据)
	return true;
}
void test(){
	LinkList L;//声明一个指向单链表的指针，在这个地方并没有创建一个结点
	//初始化一个空表
	InitList(L);5
	// ......后续代码......
}
//判断单链表是否为空
bool Empty(LinkList L){
	if(L == NULL)
		return true;
	else
		return false;
}
//或者是
bool Empty(LinkList L){
	return (L==NULL);
}

2.2 带头结点的单链表

typedef struct LNode{//定义单链表结点类型
	ElemType 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;
}
void test(){
	LinkList L;//声明一个指向单链表的指针，在这个地方并没有创建一个结点
	//初始化一个空表
	InitList(L);5
	// ......后续代码......
}
//判断单链表是否为空(带头节点)
bool Empty(LinkList L){
	if(L->next == NULL)
		return true;
	else
		return false;
}

2.3 对比

分析：

不带头结点的话，头指针所指向的下一个结点，这个结点就是用于实际存放数据的结点
带头结点的话，头指针所指向的下一个结点（头结点），这个结点（头结点）是不存放实际的数据元素的，只有这个头结点之后的下一个结点才会用于存放数据

三：知识回顾重要考点

typedef关键字――数据类型重命名

四：单链表的插入

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

找到第i-1个结点,将新结点插入其后

4.1 按位序插入（带头结点）

4.1.1 实现代码

typedef struct LNode{//定义单链表结点类型
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一个节点
}LNode,*LinkList;

//在第i 个位置插插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
	if(i<0)//因为是位序（从1开始），如果小于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值不合法，当i的值大于链表的长度时
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next=p->next;//这一端和代码和下一行的代码不能颠倒，颠倒后s的next会指向自己
	p->next=s;//将结点s连到p之后
	return true;//插入成功
}

4.1.2 时间复杂度

最好时间复杂度：O(1)
最坏时间复杂度：O(n)
平均时间复杂度：O(n)

4.2 按位序插入（不带头结点）

4.2.1 实现代码

typedef struct LNode{//定义单链表结点类型
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一个节点
}LNode,*LinkList;

//在第i 个位置插插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
	if(i<1)
		return false;
	//如果不带头结点,则插入、删除第1个元素时，需要更改头指针L
	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){
		p=p->next;
		j++;
	}
	if(p==NULL)//i值不合法，当i的值大于链表的长度时
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next=p->next;//这一端和代码和下一行的代码不能颠倒，颠倒后s的next会指向自己
	p->next=s;//将结点s连到p之后
	return true;//插入成功
}

结论:不带头结点写代码更不方便，推荐用带头结点注意:考试中带头、不带头都有可能考察，注意审题

4.2.2 时间复杂度

4.3 指定结点的后插操作

4.3.1 实现代码

typedef struct LNode{//定义单链表结点类型
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一个节点
}LNode,*LinkList;

//后插操作:在p结点之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){
	if(p==NULL)//i值不合法，当i的值大于链表的长度时
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s==NULL)//内存分配失败
		return false;
	s->data = e;
	s->next=p->next;//这一端和代码和下一行的代码不能颠倒，颠倒后s的next会指向自己
	p->next=s;//将结点s连到p之后
	return true;//插入成功
}

4.3.2 时间复杂度

时间复杂度：O(1)

4.3.3 简化4.2.2和4.2.1之中的代码

4.4 指定结点的前插操作

4.4.1 实现代码

typedef struct LNode{//定义单链表结点类型
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一个节点
}LNode,*LinkList;

//前插操作:在p结点之前插入结点s
bool InsertPriorNode (LNode *p, LNode *s){
	if(p==NULL !! s==NULL)
		return false;
	s->next=p->next;
	p-next=s;//s连到p之后
	ElemType temp=p->data;//交换数据域部分
	p->data=s->data;
	s->data=temp;
	return true;
}

4.4.2 时间复杂度

时间复杂度：O(1)

五：单链表的删除

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

5.1 按位序删除（带头结点)

5.1.1 实现代码

typedef struct LNode{//定义单链表结点类型
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一个节点
}LNode,*LinkList;

//将删除的元素的内容存放到e中，因为e是引用数据类型
bool ListDelete(LinkList &L, int i, ElemType &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;//删除成功

}

5.2.2 时间复杂度

最坏、平均时间复杂度:O(n)
最好时间复杂度:O(1)

5.2 删除指定结点

5.2.1 实现代码

typedef struct LNode{//定义单链表结点类型
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一个节点
}LNode,*LinkList;


//删除指定结点p
bool DeleteNode(LNode *p){
	if(p->next ==NULL)//第i-1个结点之后已无其他结点
		return false;
	LNode *q = p->next;//令q指向被删除结点
	p->data=p->next->data;//和后继结点交换数据域
	p->next = q->next;//将*q结点从链中“断开”
	free(q);//释放结点的存储空间
	return true;//删除成功
}

问题：如果要删除的结点是最后的一个结点，那么就会出现问题，因为p->data=p->next-data会出错

5.2.2 时间复杂度

时间复杂度：O(1)

六：知识回顾与重要考点

七：单链表的查找(带头结点)

7.1 按位查找

7.1.1 实现代码

typedef struct LNode{//定义单链表结点类型
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一个节点
}LNode,*LinkList;



//按位查找，返回第i 个元素（带头结点)
LNode * GetElem(LinkList L, int i){
	if(i<0)
		return NULL;
	LNode *p;//指针p指向当前扫描到的结点
	p = L;//当前p指向的是第几个结点
	int j=0;//L指向头结点，头结点是第0个结点(不存数据)
	while(p!=NULL && j<i){//循环找到第i 个结点
		p=p->next;
		j++;
	}
	return p;
}

7.1.2 时间复杂度

平均时间复杂度：O(n)

7.1.3 对之前的删除插入代码进行封装

7.2 按值查找

7.2.1 实现代码

typedef struct LNode{//定义单链表结点类型
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一个节点
}LNode,*LinkList;



//按值查找，找到数据域==e 的结点
LNode * LocateElem(LinkList L, ElemType e){
	LNode *p = L->next;
	while(p != NULL && p->data != e)//从第1个结点开始查找数据域为e的结点
		p = p->next;
	return p;//找到后返回该结点指针，否则返回NULL
}

7.2.2 时间复杂度

平均时间复杂度：O(n)

7.3 求表的长度

7.2.1 实现代码

typedef struct LNode{//定义单链表结点类型
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一个节点
}LNode,*LinkList;



//求表的长度
int Length(LinkList L){
	int len = 0;//统计表的长度
	LNode *p = L;
	while(p->next != NULL){
		p = p->next;
		len++;
	}
	return len;
}

7.2.2 时间复杂度

平均时间复杂度：O(n)

八：知识回顾与重要考点

九：单链表的建立

9.0 初始化带头结点的单链表

typedef struct LNode{//定义单链表结点类型
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一个节点
}LNode,*LinkList;

//初始化一个单链表(带头结点)
bool InitList(LinkList &L){
	L = (LNode *)malloc(sieof(LNode));//分配一个头结点
	if(L==NULL)//内存不足，分配失败
		return false;
	L->next = NULL;//头结点之后暂时还没有节点
	return true;
}
void test(){
	LinkList L;//声明一个指向单链表的指针
	//初始化一个空表InitList(L);
	InitList(L);
	//......后续代码......
}

9.1 尾插法

9.1.1 方法一实现

//在第i个位置插插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, ElemType 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;//插入成功
}

时间复杂度
平均时间复杂度：O(n^2)

9.1.2 方法二实现

//后插操作:在p结点之后插入元素e

//后插操作:在p结点之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){
	if(p==NULL)//i值不合法，当i的值大于链表的长度时
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s==NULL)//内存分配失败
		return false;
	s->data = e;
	s->next=p->next;//这一端和代码和下一行的代码不能颠倒，颠倒后s的next会指向自己
	p->next=s;//将结点s连到p之后
	return true;//插入成功
}

9.1.3 方法三实现（实际核心代码）

LinkList List_TailInsert(LinkList &L){//正向建立单链表
	int x;//设ElemType为整型
	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;
}

时间复杂度
平均时间复杂度：O(n)

9.2 头插法

9.2.1 实现方式二后插操作

typedef struct LNode{//定义单链表结点类型
	ElemType data;//每个节点存放一个数据元素
	struct LNode *next;//指针指向下一个节点
}LNode,*LinkList;

//后插操作:在p结点之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){
	if(p==NULL)//i值不合法，当i的值大于链表的长度时
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s==NULL)//内存分配失败
		return false;
	s->data = e;
	s->next=p->next;//这一端和代码和下一行的代码不能颠倒，颠倒后s的next会指向自己
	p->next=s;//将结点s连到p之后
	return true;//插入成功
}

9.2.2 实现代码方式一（实际核心代码）

LinkList List_HeadInsert(LinkList &L){//逆向建立单链表
	LNode *s;
	int x;
	L=(LinkList)malloc(sizeof(LNode));//建立头结点
	L->next=NULL;//初始为空链表，如果不执行这段代码的话，L就可能会指向内存其他的区域
	scanf("%d",&x);//输入结点的值
	while(x!=9999){//输入9999表示结束
		s=(LNode *)malloc(sizeof(LNode));//创建新结点
		s->data=x;
		s->next=L->next;
		L->next=s;//将新结点插入表中，L为头指针
		scanf("%d",&x);
	}
	return L;
}

在尾插法中，最好也将其初始为空链表

十：知识回顾与考点

重要考点：链表的逆置

码农公寓

一：定义与本节概览

二：用代码定义单链表

2.1 不带头结点的单链表

2.2 带头结点的单链表

2.3 对比

三：知识回顾重要考点

四：单链表的插入

4.1 按位序插入（带头结点）

4.1.1 实现代码

4.1.2 时间复杂度

4.2 按位序插入（不带头结点）

4.2.1 实现代码

4.2.2 时间复杂度

4.3 指定结点的后插操作

4.3.1 实现代码

4.3.2 时间复杂度

4.3.3 简化4.2.2和4.2.1之中的代码

4.4 指定结点的前插操作

4.4.1 实现代码

4.4.2 时间复杂度

五：单链表的删除

5.1 按位序删除（带头结点)

5.1.1 实现代码

5.2.2 时间复杂度

5.2 删除指定结点

5.2.1 实现代码

5.2.2 时间复杂度

六：知识回顾与重要考点

七：单链表的查找(带头结点)

7.1 按位查找

7.1.1 实现代码

7.1.2 时间复杂度

7.1.3 对之前的删除插入代码进行封装

7.2 按值查找

7.2.1 实现代码

7.2.2 时间复杂度

7.3 求表的长度

7.2.1 实现代码

7.2.2 时间复杂度

八：知识回顾与重要考点

九：单链表的建立

9.0 初始化带头结点的单链表

9.1 尾插法

9.1.1 方法一实现

9.1.2 方法二实现

9.1.3 方法三实现（实际核心代码）

9.2 头插法

9.2.1 实现方式二后插操作

9.2.2 实现代码方式一（实际核心代码）

十：知识回顾与考点

相关文章