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

一：定义与本节概览

二：用代码定义单链表

代码定义：

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

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

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

举例：

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

强调这是一个单链表 ——使用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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2.3 对比

分析：

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

三：知识回顾重要考点

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

四：单链表的插入

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

1. 找到第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;//插入成功
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;//插入成功
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

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;//插入成功
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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;//删除成功

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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;//删除成功
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

问题：如果要删除的结点是最后的一个结点，那么就会出现问题，因为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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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);
	//......后续代码......
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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;//插入成功
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度
平均时间复杂度：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;//插入成功
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度
平均时间复杂度：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;//插入成功
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

十：知识回顾与考点

重要考点：链表的逆置