【2022---计算机考研】数据结构之线性表总结（超详细适合背诵）_CSDN

线性表的定义：

线性表是具有相同数据类型的n个数据元素的有限序列，其中n为表长，当n=0时线性表是空表。

线性表的特点：
1、表中元素的个数有限
2、表中元素具有逻辑上的顺序性，表中元素具有其先后次序。
3、表中元素都是数据元素，每个元素都是单个元素。
4、每个元素占有相同的存储空间。
注意：
1、线性表是一种逻辑结构，表示元素之间一对一的相邻关系。
2、顺序表和链表是指存储结构。

线性表的基本操作：

// 考试时尽量用以下函数名称，方便老师阅卷！！！
1、InitList(&L) :初始化表,构造一个空的线性表
2、Length (L) :求表长,返回线性表L的长度,即L中数据元素的个
3、LocateElem(L,e) :按值查找操作,在表L中查找具有给定关键字值的元素
4、GetElem(L,i) :按位查找操作获取表L中第i个位置的元素的值
5、ListInsert (&L,i,e):插入操作。在表L中的第i个位置上插入指定元素
6、ListDelete(&L, i, &e);:删除操作,删除表L中第i个位置的元素,并用e返回删除元素的值
7、PrintList (L):输出操作按前后顺序输出线性表L的所有元素值
8、Empty (L):判空操作，若L为空表,则返回true,否则返回false
9、DestroyList(&L):销毁操作销毁线性表,并释放线性表L所占用的内存空间

1
2
3
4
5
6
7
8
9
10
11

一、顺序表

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
线性表的特点：

• 随机访问,即通过首地址和元素序号可在时间O(1)内找到指定的元素
• 存储密度高,每个结点只存储数据元素
• 与链表形成对比逻辑上相邻的元素物理上也相邻,当执行插入和删除操作时,需要移动大量元素

（一）、数据类型定义

定义一个顺序表: SqList L;
//戴敏版《数据结构》
# define MaxSize 100	//假设线性表可能的最大容量,假设为100
typedef int Elemtype	//每个元素的数据类型Elemtype可为任何类型,假设为int
typedef struct SqList{
	Elemtype data[ MaxSize ]
	int length;			//线性表长度
};		//顺序表数据类型为SqList

// 建议用以下语句
//王道《数据结构考研复习指导》：
假定线性表的元素类型为ElemType,则线性表的顺序存储类型描述为
#define MaxSize 50   //定义线性表的最大长度
typedef  struct{
	ElemType data [MaxSize]；  //顺序表的元素
	int length;	//顺序表的当前长度
	}SqList;	//顺序表的类型定义;

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

（二）、插入操作

在顺序表上完成插人运算要通过以下步骤进行:

1）判断插人位置i是否合理，若不合理提示错误，并中止程序运行。

2）检查顺序表的存储空间是否已满，若满则提示用户不能再做插人。
3）为保持顺序表的存储特点，必须先将表中a。~a;元素从原存储单元依次后移-一个存 储单元(向表尾方向移动)，为新元素让出位置。
4）将x置人空出的第i个位置。
5）修改表的长度，使长度加1。
代码：

boo1 ListInsert (SqList &L, int i, ElemType e) {
	if(i<1lli>L. length+1) //判断i的范围是否有效
		return false;
	if (L.1ength>=MaxSize)  //当前存储空间已满，不能插入
		return false;
	for (int j=L. length;j>=i;j--)//将第i个元素及之后的元素后移
	L.data[j]=L.data[j-1];
	L.data[i-1]=e; //在位置i处放入e”
	L. length++ ; //线性表长度加1
return true;
1
2
3
4
5
6
7
8
9
10

1、最好情况:在表尾插入(即i=n+ 1),元素后移语句将不执行，时间复杂度为0(1)。

2、 最坏情况:在表头插入(即i=> 1),元素后移语句将执行n次，时间复杂度为0(n).
3、线性表插入算法的平均时间复杂度为O(n)。

（三）、删除操作

在顺序表上完成删除运算的基本步骤为:
1)检查删除位置i是否合理，若不合理提示错误，并中止程序运行。
2)将表中a;.1 ~a。元素从原存储单元依次前移一个存储单元(向表头方向移动)。
3)修改表的长度，使长度减1。
代码（C）

bool ListDelete (SqList &L,int i, Elemtype &e} {
	if(i<1||li>L.length) //判断i的范围是否有效
		return false;
	e=L.data{i-1] ;//将被删除的元素赋值给e
	for(int j=i;j<L.length;j++)//将第i个位置后的元素前移
		L.data[j-1]=L.data[j] ;
	L.1ength--; //线性表长度减1
	return true ;
}
1
2
3
4
5
6
7
8
9

线性表删除的时间复杂度分析

1、最好情况:删除表尾元素(即i=n)，无须移动元素，时间复杂度为0(1).
2、最坏情况:删除表头元素(即i=1),需移动除表头元素外的所有元素，时间复杂度为O(m).
3、平均情况:假设p; (p;= 1/n)是删除第i个位置上结点的概率，则在长度为n的线性表中删除一个结点时，所需移动结点的平均次数为

因此，线性表删除算法的平均时间复杂度为0(m).

（四）、按值查找

按值查找分析：

线性表中的按值查找是指在线性表中查找与给定值x相等的数据元素。
在顺序表中完成该运算最简单的方法是:从第一个元素a起依次和x比较，直到找到一个与x相等的数据元素，则返回它在顺序表中的存储下标;或者查遍整个表都没有找到与x相等的元素，表明查找失败，返回-1。

实现代码（C）

int LocateElem_ Sq( SqList * L, Elemtype x){	
//在顺序表中查找值为x的元素,查找成功,返回元素存储位置，否则返回-1.
	int i=l;
	while(i<=L> length && L> data[i-1]! =x)
		i++;
	if(i>L-> length)
		return- 1 ;
	else 
		return i; /*返回的是存储位置,不是元素序号,两者差1 */
1
2
3
4
5
6
7
8
9

顺序表的合并操作

二、单链表

（一）、数据类型定义：

单链表中结点类型的描述如下:

typedef struct LNode{	//定义单链表结点类型
	ElemType data; 	//数据域
	struct LNode *next;	//指针域
}LNode, * LinkList;

变量定义：

LinkList L;
LNode *p,*s;
1
2
3
4
5
6
7
8
9
10
11

（二）、建立单链表

1、头插法建立不带头结点的单链表

2、头插法建立带头结点的单链表：

下图为用头插人法建立链表(36 ,44,25,87 ,53)的过程。因为是在链表的头部插人，读人数据的顺序和线性表中的逻辑顺序是相反的。

C 代码实现：

LinkList List_Headinsert(LinkList &L) //逆向建立单链表
	L=(linkList)malloc(seizeof(LNode))//创建头结点
	L->next = NULL; //初始为空链表
//输入结点的值
	While(x1-9999){ //输入9999表示结束
		s=(LNode*)malloc(sizeof(LNode));	//创建新结点
		s->data=x;
		s->next=l->next;
		L->next=s;
		scanf("%%d",&x);
	}
	return  L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

单链表头插法时间复杂度分析：

1、 采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的。
2、每个结点插入的时间为0(1),设单链表长为n,则总时间复杂度为0(m)。

2、尾插法建立单链表

若希望次序一致，则用尾插人的方法。
算法的基本思想是:
从空链表开始，每读入一个数据元素申请一个新节点，将读人的数据存到新节点的数据域中，然后把新节点插入到当前链表的尾节点之后，重复上述过程，直至输人结束标志0为止。因为每次要将新节点插入到单链表的尾部，所以需加人一个指针r用来始终指向单链表中的尾节点，以便能够将新节点插人到单链表的尾部。

下图展现了在单链表的尾部插人节点建立链表的过程。

代码实现：

Linklist List_tailInsert(LinkList &L){  //正向建立单链表
	int L;	//设置元素类型为整形
	L=(LinkList)malloc(sizeof(LNode));
	LNode *s; *r=L; //r为表尾指针.
	scanf("%%d",&x) ; 	//输入结点的值
	.while(x!=9999) {
	/ /输入9999表示结束
	g= (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
16

（三）、查找操作

1、按序号查找

在单链表中从第一-个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止,否则返回最后一个结点指针域NULL。

实现代码：

按序号查找结点值的算法如下:
LNode *GetE1em (LinkList L,int i) { 
	int j=1;  //计数:初始为1326
	LNode *p=L ->next;  //头结点指针赋给P ;
	if(i==0)
		return L;       //若i等于o，则返回头结点
	if(1<1)
		return	NULL;	//若土无效，则返回 NULL
	while (p&&j<i) {	//从第1个结点开始找，查找第1个结点，
		p=p->next;
		j++;
	}
	return. P;	//返回第土个结点的指针，若上大于表长，则返回NULL
}

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

按序号查找操作的时间复杂度为0(n)。

2、按值查找

代码实现：

按值查找表结点的算法如下:
LNode * LocateE1em (LinkList L,ElemTyne,e (
	LNode *p=L->next;
	while (P !=NULL&&p->data！=e ) // 从第1个结点开始查找dat。域为e的结点
		p=p->next ;		
	return  p;
}
1
2
3
4
5
6
7

按值查找操作的时间复杂度为O(n).

（四）、插入运算

1、前插

实现插入结点的代码片段如下:
①p=GetE1em(L;i-1) ;
//查找插入位置的前驱结点;
②s->next=p->next ;
//图2.7中操作步骤1
③p->next=s;
//图2.7中操作步骤2.
1
2
3
4
5
6
7

2、后插

可采用另一种方式将其转化为后插操作来实现，设待插入结点为s，将s插入到p的前面。我们仍然将s插入到*p的后面，然后将p->data与s->data交换，这样既满足了逻辑关系，又能使得时间复杂度为0(1)。算法的代码片段如下:

//将*s结点插入到*p之前的主要代码片段
	S- >next=p->next;   //修改指针域，不能颠倒
	P->next=s;
	temp=p- >data; 	//交换数据域部分
	p->dataeS: >data ;
	s->datastemp;
	
1
2
3
4
5
6
7

（五）、删除运算

1、第一种删除算法操作

查找到要删除节点的前驱结点，再删除该节点

	//删除结点*p
	p=GetElem(L, i-1) ;   //查找删除位置的前驱结点
	q=p->next;   		   //令q指向被删除结点
	p->next=q->next        //将*q结点从链中“断开”
	free (q) ;             //释放结点的存储空间”
1
2
3
4
5

单链表的删除操作算法的时间复杂度为O(n）

2、第二种删除算法操作

【第二种删除算法操作】
1、其实，删除结点p的操作可用删除p的后继结点操作来实现，实质就是将其后继结点的值赋予其自身，然后删除后继结点，也能使得时间复杂度为0(1)。

实现.上述操作的代码片段如下:
q=p->next;    	//令q指向*p的后继结点
p->data=p->next->data; 	//和后继结点交换数据域
p- >next=q->next;		//将*q结点从链中“断开”
free (q) ;				//释放后继结点的存储空间
1
2
3
4
5
6

三、双向链表

双向链表节点定义如下

	
	typedef struct DNode {   //定义双链表结点类型
		ElemType data;		//数据域
		struct DNode *prior, *next;	 //前驱和后继指针
	} DNode,* DLinklist ;
	
1
2
3
4
5
6

双向链表和双向循环链表比较：

（一）、插入运算

注意，顺序不唯一，但是①必须放在④的前面完成

//双向链表插入运算
①s-> prior = p-> prior;
②p-> prior-> next= s;
③s->next=p;.
④p-> prior=s;
1
2
3
4
5

（二）、删除运算

	① p-> prior-> next = p-> next;
	② p-> next-> prior = p-> prior;
1
2

四、顺序表与链表的比较

1、顺序表

顺序表的优点：

(1) 方法简单，各种高级语言中都有数组，容易实现。
(2) 不用为表示结点间的逻辑关系而增加额外的存储开销。
(3) 顺序表具有按元素序号随机访问的特点。

顺序表的缺点：

(1) 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。
(2) 需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。

2、链表

链表的优点：

1、解决顺序表需要大量连续存储单元的特点
2、

链表的缺点

1、单链表附加指针域，浪费存储空间
2、查找某个特定的结点，需要从表头开始遍历，依次查找。
3、需要进行指针操作，方法复杂。
4、 需要为表示结点间的逻辑关系（指针变量）而增加额外的存储开销。
5、只能通过遍历找到某个节点，不能使用下标直接定位节点。

3、从以下几个方面对比：

1、存取方式：

顺序表可以顺序存取，也可以随机存取
链表只能从表头顺序存取元素

2、逻辑结构与物理结构

顺序存储:逻辑上相邻的元素,对应的物理存储位置也相邻
链式存储:逻辑上相邻的元素,物理存储位置则不一-定相邻 ,对应的逻辑关系是通过指针链接来表示的

3、查找、插入和删除操作

1、按值查找
顺序表有序:可采用折半查找,此时的时间复杂度为O(log2n )
顺序表无序时:两者的时间复杂度均为O(n )
2、对于按序号查找
顺序表支持随机访问,时间复杂度仅为0(1)
链表的平均时间复杂度为O ( n )
3、插入、删除操作
顺序表:平均需要移动半个表长的元素
链表:只需修改相关结点的指针域

4、空间分配

1、顺序存储
静态分配：存储空间满则无法进行扩充会出现内存溢出
动态分配：对空间进行扩充的时候需要进行数据移动,效率低下
2、连式存储
空间分配非常灵活

4、选取存储结构

1、基于存储的考虑：

（1）难以估计线性表的长度或存储规模时,不宜采用顺序表
（2）链表不用事先估计存储规模,但链表的存储密度较低

2、基于运算的考虑：

（1）按序号访问数据元素---------顺序表优于链表
（2）进行插入、删除等操作------链表优于顺序表

3、基于环境的考虑：

1、顺序表基于数组更容易实现
2、链表基于指针,在某些编程语言中不适合实现

五、经典考题分析

1、两个链表归并问题

1、 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

算法思想:

两个链表已经按元素值递增次序排序,将其合并时,均从第-一个结点起进行比较，将小的结点链入链表中，同时后移工作指针。该问题要求结果链表按元素值递减次序排列，故新链表的建立应该采用头插法。比较结束后，可能会有一一个链表非空，此时用头插法将剩下的结点依次插入新链表中即可。动态分配对空间进行扩充的时候需要进行数据移动,效率低下连式存储空间分配非常灵活链表:只需修改相关结点的指针域

代码实现：

void MergeList (LinkList &La, LinkList &Lb) {
//合并两个递增有序链表(带头结点)，并使合并后的链表递减排列
	LNode *r, *pa=la->next, *pb=Lb->next; //分别是表 La和Lb的工作指针
	La->next= =NULL;   	//La作为结果链表的头指针，先将结果链表初始化为空
	while (pa&&pb)		//当两链表均不为空时，循环
		if (pa->data<=pb- >data) {
			r=pa- >next;	//r暂存pa的后继结点指针
			pa ->next=La->next;
			La->next=pa;	//将pa结点链于结果表中，同时逆置(头插法)
			paer=r;		//恢复pa为当前待比较结点
		}
		else{
			r=pb->next;		//r暂存pb的后继结点指针
			pb->next∞La ->next;
			La->next=pb;	//将pb结点链于结果表中,同时逆置(头插法)
			pb=r;			//恢复pb为当前待比较结点
		}
	f(pa)
		pb-pa;		//通常情况下会剩一个链表非空，处理剩下的部分
	whiie(pb){		//处理剩下的一个非空链表1
		r=pb->next;	//依次插入到La中(头插法)
		pb->next=La->next;	
		La->next=pb;
		pb=r;
	}
		free(Lb);
}

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、使用链表逆置

试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为0(1).

算法思路：

解法一:将头结点摘下，然后从第- -结点开始，依次插入到头结点的后面(头插法建立单链
表)，直到最后一个结点为止，这样就实现了链表的逆置，如下图所示。

算法实现：

LinkList ; Reverse_ 1 (LinkList L) {	//是带头结点的单链表，本算法将L就地逆堂小老研。
	LNode. *p, *r;	//p为工作指针，r为p的后继，以防断链
	p=L->next ;		//从第-一个元素结点开始
	L->next=NULL;	//先将头结点L的next域置为NULL
	while (p! =NULL) {//依次将元素结点摘下
		r=p->next;	//暂存p的后继
		p->next=L->next;//将p结点插入到头结点之后
		L->next=p;
		p=r;
	}
	return L;
}
1
2
3
4
5
6
7
8
9
10
11
12