Ds2.线性表
发表于：2022-10-01 | 分类： 数据结构

Ds2.线性表

线性表

一.线性表的定义和基本操作

1.线性表的定义

线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为

image-20221002131331902

相同:每个数据元素所占空间一样大

有限序列:有次序

几个概念：

$a_i$是线性表中的“第i个”元素线性表中的位序

注意:位序从1开始 数组下标从0开始

a1是表头元素；an是表尾元素。

除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅 有一个直接后继

2.线性表的特点

  • 表中元素的个数有限。
  • 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
  • 表中元素都是数据元素，每个元素都是单个元素。
  • 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间
  • 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混滑。

3.线性表的基本操作

3.1.基本操作

InitList(&L): 初始化表。构造一个空的线性表,分配内存空间。DestroyList(&L): 销毁操作。销毁线性表，并释放线性表L所占用的内存空间

ListInsert**(&L**,i,e): 插入操作。在表L中的第i个位置上插入指定元素e。ListDelete(&L,i,&e): 删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

LocateElem(L,e): 按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。

其他常用操作

Length(L): 求表长。返回线性表L的长度，即工中数据元素的个数。
PrintList(L): 输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L): 判空操作。若工为空表，则返回true,否则返回false。

Tips:

①对数据的操作（记忆思路） —— 创销、增删改查
②C语言函数的定义 —— <返回值类型> 函数名 (<参数1类型> 参数1，<参数2类型> 参数2，……)
③实际开发中，可根据实际需求定义其他的基本操作
④函数名和参数的形式、命名都可改变（Reference：严蔚敏版《数据结构》）
⑤什么时候要传入引用“&” —— 对参数的修改结果需要“带回来”

Summary:

image-20221002142403024

习题

选择

1.线性表是具有n个（C)的有限序列.
A.数据表
B.字符
C.数据元素
D.数据项

1
>线性表是由具有相同数据类型的有限数据元素组成的，数据元素是由数据项组成的。

2.以下（B)是一个线性表。
A.由n个实数组成的集合
B.由100个字符组成的序列
C.所有整数组成的序列
D.邻接表

1
>线性表定义的要求为：相同数据类型、有限序列。选项C的元素个数是无穷个，错误：选项A集合中的元素没有前后驱关系，错误；选项D属于存储结构，线性表是一种逻辑结构，不要将二者混为一谈。只有选项B符合线性表定义的要求。

3.在线性表中，除开始元素外，每个元素（A)。
A.只有唯一的前趋元素
B.只有唯一的后继元素
C.有多个前趋元素
D.有多个后继元素

1
>线性表中除最后一个(或第一个)元素外，每个元素都只有一个后继（或前驱）元素。

二.顺序表

image-20221003111833912

优点：可随机存取，存储密度高

缺点：要求大片连续空间，改变容量不方便

1.定义

线性表的顺序存储又称顺序表。

用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

1
2
3
4
typedef struct {
	int num; //号数
	int people; //人数
} Customer;

image-20221002162719515

2.顺序表的实现

2.1静态分配
1
2
3
4
5
#define MaxSize 10 			//定义最大长度
typedef struct{
	ElemType data[MaxSize]; //用静态的“数组”存放数据元素
	int length; 			//顺序表的当前长度
}SqList; 					//顺序表的类型定义（静态分配方式）

image-20221002163226543

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#define MaxSize 10   	//定义最大长度
typedef struct{
	int data[MaxSize];  //用静态的"数组"存放数据元素
	int length;  		//顺序表当前长度
}SqList;  				//顺序表的类型定义

//基本操作--初始化一个顺序表
void InitList(SqList &L){
	for(int i = 0;i<MaxSize;i++)
		L.data[i] = 0;  //将所有元素设置为默认初始值
	L.length = 0;  		//顺序表初始长度为0
}

int main(){
	SqList L;	  		//声明一个顺序表
	InitList(L); 		//初始化顺序表
	//.....未完待续,后续操作
	return 0;
}

image-20221002164011641

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*不初始化数据元素,内存不刷0*/
#include <stdio.h>
#define MaxSize 10     	//定义最大长度
typedef struct{
	int data[MaxSize];  //用静态的"数组"存放数据元素
	int length;  		//顺序表当前长度
}SqList;  				//顺序表的类型定义

//基本操作--初始化一个顺序表
void InitList(SqList &L){
	L.length = 0;  		//顺序表初始长度为0
}

int main(){
	SqList L;	  		//声明一个顺序表
	InitList(L); 		//初始化顺序表
	//尝试"违规"打印整个 data 数组
	for(int i = 0; i<MaxSize; i++)
		printf("data[%d]=%d\n",i,L.data[i]);
       return 0;
}

违规打印后会出现数据错乱的现象

image-20221002165101190

image-20221002165310638

2.2动态分配
1
2
3
4
5
6
#define Initsize 10    	//顺序表的初始长度
typedef struct{
	ElemType *data;  	//指示动态分配数组的指针
	int MaxSize;		//顺序表的最大容量
    int length;   	  	//顺序表的当前长度
}SeqList;     			//顺序表的类型定义（动态分配方式）

image-20221002170115089

在内存开辟了一整片连续的空间

image-20221002170229514

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
33
#include<stdlib.h>
#define Initsize 10    	//顺序表的初始长度
typedef struct{
	ElemType *data;  	//指示动态分配数组的指针
	int MaxSize;		//顺序表的最大容量
    int length;   	  	//顺序表的当前长度
}SeqList;     			

void InitList(SeqList &L){
	//用malloc 函数申请一片连续的存储空间
	L.data = (int*)malloc(InitSize*sizeof(int));
	L.length = 0;
	L.MaxSize = InitSize;
}

//增加动态数组的长度
void IncreaseSize(SeqList &	L, int len){
	int *p = L.data;
    L.data = (int *)malloc((L.MaxSize+len)*sizeof(int));
    for(int i = 0;i<L.length;i++){
    	L.data[i] = p[i];		//将数据复制到新区域
    }
    L.MaxSize = L.MaxSize+len;	//数组最大长度增加 len
    free(p);					//释放原来内存空间
}

int main(){
	SeqList L;  	//声明一个顺序表
	InitList(L);	//初始化顺序表
	//...往顺序表中随便插入几个元素...
	IncreaseSize(L,5);
	return 0;
}

image-20221002181256522

3.顺序表的特点

①随机访问，即可以在 O(1) 时间内找到第 i 个元素。

代码实现：data[i-1]; 静态分配、动态分配都一样

②存储密度高，每个节点只存储数据元素

③拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）

④插入、删除操作不方便，需要移动大量元素

image-20221002181944386

image-20221002181959824

Summary:

image-20221002182029430

三.顺序表的插入和删除

1.插入

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

image-20221003082608844

image-20221003082635222

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define Maxsize 10		//定义最大长度
typedef struct{
	int data[MaxSize];	//用静态的"数组"存放数据元素
	int length;			//顺序表的当前长度
}SqList;				//顺序表的类型定义

void ListInsert(SqList &L,int i,int e){
	for(intj=L.length;j>=i;j--) //将第i个元素及之后的元素后移
		L.data[j]=L.data[j-1];
	L.data[i-1]=e;				//在位置i处放入e
	L.length++;					//长度加1
}
int main(){
	SqList L;			//声明一个顺序表
	InitList(L);		//初始化顺序表
	//..,此处省略一些代码，插入几个元素
	ListInsert(L,3,3);
	return 0;
}

前提是数组里已经插入了5个元素,length = 5

1
ListInsert(L,9,3)；

此时,插入的不合法,插入方法改进

1
2
3
4
5
6
7
8
9
10
11
bool ListInsert(SqList &L,int i,int e){
    if(i<1||i>L.length+1)		//判断i的范围是否有效
        return false;
    if(L.length>=MaxSize)    	//当前存储空间已满，不能插入
        return false;
    for(intj=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.1插入操作的时间复杂度
1
L.data[j]=L.data[j-1];

​ 关注最深层循环语句的执行
​ 次数与问题规模n的关系

​ 问题规模n=L.length(表长)

最好情况：新元素插入到表尾，不需要移动元素
i=n+1,循环0次；最好时间复杂度=O(1)

最坏情况：新元素插入到表头，需要将原有的个元素全都向后移动
i=1,循环n次；最坏时间复杂度=On;

平均情况：假设新元素插入到任何一个位置的概率相同，即i=1,23,,enth+1的概 率都是p=1/(n+1)
i=1,循环n次；i=2时，循环n-1次；i3,循环n-2次…i=n+1时，循环0 次

image-20221003085942569

2.删除

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

image-20221003095536438

image-20221003095552940

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool ListDelete(SqList &L,int i,int &e){
	if(i<1||i>L.length		//判断的范围是否有效
		return false;
	e=L.data[i-1];  	 		//将被删除的元素赋值给e
	for(intj=i;j<L.length;j++)	//将第i个位置后的元素前移
		L.data[j-1]=L.data[j];
	L.length--;    				//线性表长度减1
	return  true;
}
int main(){
	SqList L;    				//声明一个顺序表
	InitList(L);	 			//初始化顺序表
	//.·,此处省略一些代码，插入几个元素
	int e =-1;    				//用变量e把删除的元素"带回来"
	if (ListDelete(L,3,e))
		printf("已删除第3个元素，删除元素值为=%d\n",e);
	else
		printf("位序i不合法，删除失败\n");
return 0;
}
2.1 删除操作的时间复杂度
1
L.data[j-1]=L.data[j];

​ 关注最深层循环语句的执行
​ 次数与问题规模n的关系

​ 问题规模n=L.length(表长)

最好情况：删除表尾元素，不需要移动其他元素
i=n，循环0次；最好时间复杂度=O(1)

最坏情况：删除表头元素，需要将后续的-1个元素全都向前移动
i=1,循环n-1次；最坏时间复杂度=O(n);

平均情况：假设删除任何一个元素的概率相同，即i=12,3,…,length的概率都是 p=1/n
i=1,循环n-1次；i=2时，循环n-2次；i=3,循环n-3次i=n时，循环0次

image-20221003094544853

Summary:

顺序表的基本操作

习题:

选择

1.下述(A)是顺序存储结构的优点。
A.存储密度大
B.插入运算方便
C.删除运算方便
D.方便地运用于各种逻辑结构的存储表示

1
>顺序表不像链表那样要在结点中存放指针域，因此存储密度较大，A正确。B和C是链表的优点。D是错误的，比如对于树形结构，顺序表显然不如链表表示起来方便。

2.线性表的顺序存储结构是一种(A).
A.随机存取的存储结构
B.顺序存取的存储结构
C.索引存取的存储结构
D.散列存取的存储结构

1
>本题易误选B。注意，存取方式是指读写方式。顺序表是一种支持随机存取的存储结构，根据起始地址加上元素的序号，可以很方便地访问任意一个元素，这就是随机存取的概念。

3.一个顺序表所占用的存储空间大小与（B)无关。
A.表的长度
B.元素的存放顺序
C.元素的类型
D.元素中各字段的类型

1
>顺序表所占的存储空间=表长×sizeof（元素的类型)，元素的类型显然会影响存储空间的大小。对于同一元素类型的顺序表，表越长，所占存储空间就越大。

4.若线性表最常用的操作是存取第个元素及其前驱和后继元素的值，为了提高效率，应采用（D)的存储方式。
A.单链表
B.双向链表
C.单循环链表
D.顺序表

1
>题干实际要求能最快存取第i一1、i和i+1个元素值。A、B、C都只能从头结点依次顺序查找，时间复杂度为O(n):只有顺序表可以按序号随机存取，时间复杂度为O(1)。

5.一个线性表最常用的操作是存取任一指定序号的元素并在最后进行插入、删除操作，则利用（A)存储方式可以节省时间。
A.顺序表
B.双链表
C.带头结点的双循环链表
D.单循环链表

1
>只有顺序表可以按序号随机存取，且在最后进行插入和删除操作时不需要移动任何元素。

6.在n个元素的线性表的数组表示中，时间复杂度为O(1)的操作是(C)
I.访问第i（1≤i≤n)个结，点和求第i（2≤i≤n)个结点的直接前驱
II.在最后一个结，点后插入一个新的结点
III.删除第1个结点
IV.在第i(1≤i≤n)个结点后插入一个结点
A.I
B.II、III
C.I、II
D.I、II、III

1
>I解析略;II中，在最后位置插入新结点不需要移动元素，时间复杂度为O(1)；III中，被删结点后的结点需依次前移，时间复杂度为O(n):IV中，需要后移n一i个结点，时间复杂度为O(n)。

7.设线性表有”个元素，严格说来，以下操作中，(C)在顺序表上实现要比在链表上实现的效率高。
I.揄出第i(1≤i≤n)个元素值
II.交换第3个元素与第4个元素的值
III.顺序输出这n个元素的值
A.I
B.I、III
C.I、II
D.II、III

1
>对于Ⅱ，顺序表仅需3次交换操作；链表则需要分别找到两个结点前驱，第4个结点断链后再插入到第2个结点后，效率较低。对于III，需依次顺序访问每个元素，时间复杂度相同。

8.在一个长度为n的顺序表中删除第i(1≤i≤n)个元素时，需向前移动(C)个元素.
A.n
B.i-1
C.n-i
D.n-i+i

1
>需要将a_I+1~a_n元素前移一位，共移动n一(i+1)+1=n-i个元素。

9.对于顺序表，访问第个位置的元素和在第1个位置插入一个元素的时问复杂度为（C)。
A.O(n),O(n)
B.O(n),O(1)
C.O(1),0(n)
D.O(1),O(1)

1
>在第i个位置插入一个元素，需要移动n一i+1个元素，时间复杂度为O(n)。

10.若长度为的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，则i的合法值应该是（B)
A.l≤i≤n
B.1≤i≤n+1
C.0≤i≤n-l
D.0≤i≤n

1
>线性表元素的序号是从1开始，而在第n+1个位置插入相当于在表尾追加。

11.顺序表的插入算法中，当n个空间已满时，可再中请增加分配m个空间，若中请失败，则说明系统没有(D）可分配的存储空间。
A.m个
B.m个连续
C.n+m个
D.n+m个连续

1
>顺序存储需要连续的存储空间，在申请时需申请n+m个连续的存储空间，然后将线性表原来的n个元素复制到新申请的n+m个连续的存储空间的前n个单元。

简答

1.从顺序表中删除具有最小值的元素（假设唯一)并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。

算法思想：搜索整个顺序表，查找最小值元素并记住其位置，搜索结束后用最后一个元素填补空出的原最小值元素的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
>>bool Del_Min(sqList &L,ElemType &value){
>>//删除顺序表L中最小值元素结点，并通过引用型参数value返回其值
>>//若删除成功，则返回true:否则返回false
if(L.length==0)
	return false;	//表空，中止操作返回
value=L.data[0];
int pos=0;			//假定0号元素的值最小
for(int i=1;i<L.length;i++)
					//循环，寻找具有最小值的元素
	if(L.data[i]<value){
	//让value记忆当前具有最小值的元素
		value=L.data[i];
		pos=i;
	}
L.data(pos]=L.data[L.length-1];
					//空出的位置由最后一个元素填补
L.length--;
return true;		//此时，va1ue即为最小值
>>}

注意：本题也可用函数返回值返回，两者的区别是：函数返回值只能返回一个值，而参数返回（引用传参)可以返回多个值。

2.设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。

算法思想：扫描顺序表L的前半部分元素，对于元素L.datai,将其与后半部分的对应元素L.data[L.length-i-1]进行交换。

1
2
3
4
5
6
7
8
>>void Reverse(Sqlist &L){
   Elemtype temp;    		//辅助变量
   for(i=0;i<L.length/2;i++){
   	temp=L.data [i];    //交换L.data[i]与L.data[L.length-i-1]
   	L.data[i]=L.data[L.length-i-1];
   	L.data[L.length-i-1]=temp;
   	}
   }

3.对长度为n的顺序表L,编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。

解法一：

用k记录顺序表L中不等于x的元素个数（即需要保存的元素个数），边扫描L边统计k,并将不等于x的元素向前移动k个位置，最后修改L的长度。

1
2
3
4
5
6
7
8
9
10
>>void del_x_1(Sqlist &L,Elemtype x){
>>//本算法实现删除顺序表工中所有值为×的数据元素
   int k=0;		//记录值不等于×的元素个数
   for(i=0;i<L.length;i++)
   	if(L.data.[i]！=x)f
   		L.data[k]=L.data[i];
   		k++;	//不等于×的元素增1
   	}
   L.length=k;		//顺序表工的长度等于k
>>}

解法二：

用k记录顺序表L中等于x的元素个数，边扫描L边统计k,并将不等于x的元素前移k个位置，最后修改L的长度。

1
2
3
4
5
6
7
8
9
10
11
>>void del_x_2(Sqlist &L,Elemtype x)(
   int k=0,i=0;				//k记录值等于×的元素个数
   while(i<L.1 ength){
   	if(L.data[i]==x)
  			k++;
   	else
   		L.data[i-k]=L.data[i];//当前元素前移k个位置
   	i++;
   }
   L.length=L.length-k;		//颗序表L的长度递减
>>}

此外，本题还可以考虑设头、尾两个指针(i=1,j=n),从两端向中间移动，在遇到最左端值x的元素时，直接将最右端值非x的元素左移至值为x的数据元素位置，直到两指针相遇。但这种方法会改变原表中元素的相对位置。

4.从有序顺序表中删除其值在给定值s与t之间（要求s<t)的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。

​ 注意：本题与上一题存在区别。因为是有序表，所以删除的元素必然是相连的整体。
​ 算法思想：先寻找值大于等于5的第一个元素（第一个删除的元素），然后寻找值大于1的第一个元素（最后一个删除的元素的下一个元素），要将这段元素删除，只需直接将后面的元素
前移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>bool Del_s_t2(SqList &L,ElemType.s,ElemType t){
>>//删除有序顺序表L中值在给定值s与飞之间的所有元素
   int i,j;
   if (s>=t||L.length==0)
   	return false;
   for(i=0:i<L.length&&L.data[i]<s;i++);	//寻找值大于等于s的第一个元素
   if(i>=L.length)
   	return false;			//所有元素值均小于s,返回
   for(j=i;j<L.length&&L.data[j]<=t;j++);	//寻找值大于t的第一个元素
   for (;j<L.length;i++,j++)
   	L.data[i]=L.data[j];	//前移，填补被删元素位置
   L.length=i;
   return true;
>>}

5.从顺序表中删除其值在给定值s与1之间（包含s和t,要求s<t)的所有元素，若S或t不合理或顺序表为空，则显示出错信息并退出运行。

算法思想：从前向后扫描顺序表L,用k记录下元素值在s到t之间元素的个数（初始时k=0)。对于当前扫描的元素，若其值不在s到t之间，则前移k个位置：否则执行k++。由于这样每个不在s到t之间的元素仅移动一次，因此算法效率高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>bool Del_s_t(SqList &L,ElemType s,ElemType t){
>>//删除顺序表L中值在给定值s与七（要求s<t)之间的所有元素
   int i,k=0;
   if(L.length==0||s>=t)
   	return false;	//线性表为空或s、七不合法，返回
   for(i=0;i<L.length;i++)(
   	if(L.data〔i]>=s&&L.data[i]<=t)
   		k++;
   	else
   	L.data[i-k]=L.data[i];		//当前元紫前移k个位置
   }//for
   L.length-=k;				    //长度减小
   return true;
>>}

注意：本题也可从后向前扫描顺序表，.每遇到一个值在s到t之间的元素，则删除该元素，其后的所有元素全部前移。但移动次数远大于前者，效率不够高。

6.从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

算法思想：注意是有序顺序表，值相同的元一定在连续的位置上，用类似于直接插入排序的思想，初始时将第一个元素视为非重复的有序表。之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同，若相同，则继续向后判断，若不同，则插入前面的非重复有序表的最后，直至判断到表尾为止。

1
2
3
4
5
6
7
8
9
10
>>bool Delete_Same(SeqList&L){
if(L,length==0）
	return false;
int i,j;		//i存储第-一个不相同的元素，方为工作指针
for(i=0,j=1;<L.length;j++)
	if(L.data[i]!=L.data(j])	//查找下一个与上个元素值不同的元紫
		L.data[++i]Ldata[j];	//找到后，将元紫前移
L.length=i+1;
return true;
>>}

对于本题的算法，请读者用序列1,2,2,2,2,3,3,3,4,4,5来手动模拟算法的执行过程，在模拟过程中要标注i和j所指示的元素。

7.将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

算法思想：首先，按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后，看哪个表还有剩余，将剩下的部分加到新的顺序表后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
>>bool Merge(SeqList A,SeqList B,SeqList &C){
>>//将有序顺序表A与B合并为一个新的有序顺序表C
if(A.length+B.length>C.maxsize)//大于顺序表的最大长度
	return false;
int i=0,j=0,k=0:
   while(i<A.length&&j<B.length){        //循环，两两比较，小者存入结果表
   	if(A.data[i]<=B.data[j])
           C.data[k++]=A.data [i++];
       else
           C.data[k++]=B.data[j++];
   }
   while(i<A.length)    //还剩一个没有比较完的顺序表
       C.data[k++]=A.data[i++];
   while(j<B.length)
       C.data[k++]=B.data[j++];
   C.length=k;
   return true;
>>}

注意：本算法的方法非常典型，需牢固掌握。

image-20221003112915653

image-20221003121747653

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef int DataType;
void Reverse(DataType A[],int left,int right,int arraysize){
//逆转(a1eft,aleft+1,aleft+2…,aright)为(aright,aright-1,…,a1eft)
	if(left>=right||right>=arraySize)
		return;
	int mid=(left+right)/2;
	for(int i=0;i<=mid-left;i++)(
		Datatype temp=A[left+i];
		A[left+i]=A[right-i];
		A[right-i]=temp;;
void Exchange(DataType A[],int m,int n,int arraysize)[
/*数组A[m+n]中，从0到m-1存放顺序表(al,a2,a3,....,am),从m到m+n-1存放顺序表
(b1,b2,b3,...,bn),算法将这两个表的位置互换*/
	Reverse(A,0,m+n-1,arraySize);
	Reverse(A,0,n-1,arraySize);
	Reverse(A,n,m+n-1,arraySize);
}

image-20221003112934880

算法思想：顺序存储的线性表递增有序，可以顺序查找，也可以折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void SearchExchangeInsert (ElemType A[],ElemType x)(
	int low=0,high=n-1,mid;		 	//1ow和high指向顺序表下界和上界的下标
	while(low<=high){
        mid=(low+high)/2;        	//找中间位置
        if(A[mid]==x) break;     	//找到x,退出whi1e循环
        else if(A[mid]<x) 1ow=mid+1;//到中点mid的右半部去查
        else high=mid-1;        	//到中点mid的左半部去查
     }	//下面两个iE语句只会执行一个
	if (A[mid]==x&&mid!=n-1){//若最后一个元素与×相等，则不存在与其后继交换的操作
		t=A[mid];A[mid]=A(mid+1];A[mid+1]=t;
     }
	if(1ow>high){							//查找失败，插入数据元素×
		for(i=n-1;i>high;i--) A[i+1]=A[i];	//后移元素
		A[i+1]=x;							//插入x
    }										//结束插入
}

本题的算法也可写成三个函数：查找函数、交换后继函数与插入函数。写成三个函数的优点是逻辑清晰、易读。

image-20221003112951095

image-20221003122959771

image-20221003123016473

image-20221003123030773

另解，借助辅助数组来实现。算法思想：创建大小为p的辅助数组S,将R中p个整数依次暂存在S中，同时将R中后n-p个整数左移，然后将S中暂存的p个数依次放回到R中的后续单元。时间复杂度为O(),空间复杂度为Op)。

四.顺序表的基本操作

1.按位查找

GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。

1
2
3
4
5
6
7
8
9
   #define MaxSize 10    	//定义最大长度
   typedef struct{
   	ElemType data[MaxSize];  	//用静态的“数组”存放数据元素
       int length;   	  	//顺序表的当前长度
   }SeqList;     			//顺序表的类型定义（静态分配方式）

ElemType GetElem(SqList L,int i){
       return L.data[i-1];
   }
1
2
3
4
5
6
7
8
9
10
   #define InitSize 10		//顺序表的初始长度
   typedef struct{
       ElemType *data;		//指示动态分配数组的指针
       int MaxSize;		//顺序表的最大容量
       int length;			//顺序表的当前长度
   }SeqList;				//顺序表的类型定义（动态分配方式）

ElemType GetElem(SqList L,int i){
       return L.data[i-1];
   }

image-20221003101850038

1.1时间复杂度

O(1)

由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第ⅰ个元素一一“随机存取”特性

2.按值查找

LocateElem(L,e): 按值查找操作。在表L中查找具有给定关键字值的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   #define InitSize 10		//顺序表的初始长度
   typedef struct{
       ElemType *data;		//指示动态分配数组的指针
       int MaxSize;		//顺序表的最大容量
       int length;			//顺序表的当前长度
   }SeqList;				//顺序表的类型定义（动态分配方式）

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
   int LocateElem(SeqList L,ElemType e){
       for(int i=0;i<L.length;i++)
       	if(L.data [i]==e)
       		return i+1;     //数组下标为i的元素值等于e,返回其位序i+1
   	return  0;    			//退出循环，说明查找失败
   }
2.1结构类型的比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef struct{
       int num;
       int people;
   }Customer;
   
   void test (){
       Customer a;
       a.num 1;
       a.people 1;
       Customer b;
       b.num 1;
       b.people 1;
       if(a≡=b){  	//Invalid operands to binary expression ('Customer'and 'Customer')
       	printf("相等")；
       }else{
           printf("不相等")；
       }
   }	
1
2
3
4
5
6
7
   if (a.num ==b.num &a.people =b.people){
   	printf("相等")；
   }else{
   	printf("不相等")；
   }
   //需要依次对比各个分量来
//判断两个结构体是否相等
2.2时间复杂度
1
if(L.data [i]==e)

​ 关注最深层循环语句的执行
​ 次数与问题规模n的关系

​ 问题规模n=L.length(表长)

最好情况：目标元素在表头
循环1次；最好时间复杂度=0(1)
最坏情况：目标元素在表尾
循环n次；最坏时间复杂度=O(0:

平均情况：假设目标元素出现在任何一个位置的概率相同，都是1/n
目标元素在第1位，循环1次：在第2位，循环2次；…；在第n位循 环n次

image-20221003111504281

Summary:

image-20221003111536079

五.单链表

image-20221003111737936

优点：不要求大片连续空间，改变容量方便

缺点：不可随机存取，要耗费一定空间存放指针

1.定义

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

struct LNode *p =(struct LNode*)malloc(sizeof(struct LNode));
增加一个新的结点：在内存中申请一个结点所需空间，并用指针p指向这个结点

image-20221003130917537

image-20221003130929779

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

要表示一个单链表时，只需声明一个头指针L,指向单链表的第一个结点

​ LNode*L; //声明一个指向单链表第一个结点的指针
或：LinkList L; //声明一个指向单链表第一个结点的指针

例:

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

1.1使用头插法建立一个单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
LinkList List_HeadInsert (LinkList &L){//逆问建立单链表
    LNode *s;int x;
    L=(LinkList)malloc(sizeof(LNode));	//创建头结点
    L->next=NULL;                 	    //初始为空链表
    scanf("%d",&x);					   	//输入结点的值
    whi1e(x!=9999){					   	//输入9999表示结束
    	s(LNode*)malloc(sizeof(LNode)); //创建新结点or
    	s->data=x;
    	s->next=L->next;
    	L->next=s;    					//将新结点插入表中，工为头指针
    	scanf("号d",&x);
    }
    return L;
}
1.2不带头结点的单链表
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
typedef struct LNode{		//定义单链表结点类型
    ElemType data;			//每个节点存放一个数据元素
    struct LNode *next;		//指针指向下一个节点
}LNode,*LinkList

//初始化一个空的单链表
bool InitList(LinkList &L){
	L NULL;					//空表，暂时还没有任何结点
	return true;
}
void test(){
    LinkList L;    //声明一个指向单链表的指针
    //初始化一个空表
    InitList(L);
    //.,,后续代码.
}

//判断单链表是否为空
bool Empty(LinkList L){
    if (L == NULL)
    	return true;
    else
    	return false;
    }
或：
bool Empty(LinkList L){
    return (L==NULL);
}

image-20221003133933686

1.3带头节点的单链表
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
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);
    //.,,后续代码.
}
//判断单链表是否为空（带头结点）
bool Empty(LinkList L){
	if (L->hext ==NULL)
		return true;
	else
		return false;
}

image-20221003134113542

1.4不带头节点VS带头结点

不带头结点

写代码更麻烦 对第一个数据结点和后续数据结点的 处理需要用不同的代码逻辑 对空表和非空表的处理需要用不同的 代码逻辑

带头结点

写代码更方便，用过都说好

Summary:

image-20221003134436844

2.基本操作

2.1插入
  • 按位序插入(带头结点)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//在第i个位置插插入元素e(带头节点)
bool LinkInsert(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)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = s;	//不能与下面的代码颠倒
	p->next = s;	//将节点s连到p之后
	return true;	//插入成功
}
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

分析

①如果i=1(插在表头) 最好时间复杂度O(1)

②如果ⅰ=3（插在表中）

③如果ⅰ=5（插在表尾）最坏时间复杂度：O(n)

④如果i=6(i>Lengh)

  • 按位序插入(不带头结点)

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

不存在”第0个”节点,因此i=1时需要特殊处理

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
//在第i个位置插插入元素e(带头节点)
bool LinkInsert(LinkList &L,int i,ElemType e){
	if(i<1)
		return false;
	if(i==1){//插入第1个结点的操作与其他结点操作不同
		LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = s;	
        L = s;			//头指针指向新节点
        return true;	
	}
	LNode *p;		//指针p指向当前扫描的节点
	int j = 0;		//当前p指向的是第几个节点
	p = L;			//L指向第1个节点(注意:不是头节点)
	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;	
	return true;	//插入成功
}
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
  • 指定结点的后插操作
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
//在第i个位置插插入元素e(带头节点)
bool LinkInsert(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++;
	}
	return InsertNextNode(p,e);
}
//后插操作：在p结点之后插入元素e
    bool InsertNextNode (LNode *p,ElemType e){
        if (p==NULL)
        	return false;
        LNode *s (LNode *)malloc(sizeof(LNode));
        if (s==NULL)        //内存分配失败
        	return false;
        s->data =e;        	//用结点s保存数据元素e
        s->next=p->next;
        p->next=s;        	//将结点s连到p之后
    return true;
}

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
  • 指定结点的前插操作
1
2
3
4
5
6
7
8
9
10
11
//前插操作：在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;
}
2.2删除
  • 按位序删除(带头结点)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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）  //第1-1个结点之后已无其他结点
    	return false;
    LNode *q=p->next;	 //令q指向被删除结点
    e q->data;			 //用e返回元素的值
    p->next=q->next;	 //将*q结点从链中“断开”
    free(q);		 	 //释放结点的存储空间
    return true;		 //删除成功
}
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

分析:

如果i = 4
最坏、平均时间复杂度：O(n)
最好时间复杂度：O(1)

  • 指定节点的删除
1
2
3
4
5
6
7
8
9
10
//删除指定结点p
bool DeleteNode (LNode *p){
    if (p==NULL)
        return false;
    LNode*q=p->next;	//令g指向*p的后继结点
    p->datap->next-tata	//和后继结点交换数据域
    p->next=q->next;	//将*g结点从链中“断开”
    free(q);			//释放后继结点的存储空间
    return true;
}

如果p是最后一个结点

只能从表头开始依
次寻找p的前驱，
时间复杂度o(n)

单链表的局限性无法逆向检索，有时候不太方便

数据结构
下一篇:
Ch3.数据链路层
本文目录
本文目录
    •

    Copyright © 2019 - 2020 yuang01 | Powered by Hexo | Theme Bamboo

    本站总访问量： 次 |