[数据结构与算法]408数据结构——线性表

线性表

考纲内容

• • 线性表的定义和操作
• • 线性表的实现

要求内容

• • 会线性表及链表的基本操作
• • 多种方法分析设计并比较复杂度，熟悉代码思路

• 思维导图索引
  

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

1.1 线性表的定义

• 线性表是具有相同数据类型的n个数据元素的有限序列 ，当表长 $n$ 为 的时候，为空表。

• 除第一个元素外，每个元素有且只有一个直接前驱。
• 除最后一个元素外，每个元素有且只有一个直接后续。

1.2 线性表的基本操作

创销增删改查

InitList（&L）创建一个空表
Length（L） 求表长
LocateElem（L,e）按值查找，查找给定的关键字值元素
GetElem（L,i）按位查找，获取表L中第i个位置元素的值
ListInsert（&L,i,e）在表中的第i个位置插入指定的元素e
ListDelete（&L,i,&e）删除表中的第i个位置的值并用e返回删除元素的值

注意
对参数修改结果要带回来这要写上引用 &

2.线性表的顺序表示

2.1 顺序表的定义

• 线性表的顺序存储。
• 是用一组地址连续的存储单元依次存储线性表中的元素。
• 逻辑上相邻的两个元素在物理位置上也相邻

假设线性表 $L$ 存储的起始位置为LOC(A),sizeof(ElemType)是每个元素所占存储空间的大小，这对应存储结构如下：

注意

线性表中元素的位序是从 $1$ 开始的，而数组中的元素下标是从 $0$ 开始的，这个非常重要，应用时需区分清楚。

2.2静态/分配的描述

假定 线性表 的元素为 ElemType

#define	MaxSize 50    //定义线性表的最大长度
typedef	struct{
	ElemType data[MaxSize];	//顺序表的元素
	int	length;	//当前表的长度
}Sqlist;	//类型定义

• 静态分配的时候，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会溢出，导致程序崩溃
• 采用动态分配，一旦空间占满，就会另外开辟一块更大的内存空间

#define	MaxSize 100    //定义表长
typedef	struct{
	ElemType *data;	//动态分配数祖的指针
	int	MaxSize,length;	//数组最大容量和当前个数
}Sqlist;	//类型定义

C的初始动态分配语句

L.data = (ElemType*) malloc (sizeof(ElemType))

2.3 顺序表的操作

插入、删除、按值查找
（1）插入操作

• 在顺序表 $L$ 的第 $i$ (1<=i<=L.length+1)个位置上插入新元素 $e$
• 判断 $i$ 的位置是否合法
• 第 $i$ 个元素及气候依次从后移动一个位置
• 顺序表长度 加1

bool ListInsert(SqList &L,int i,ElemType e){
	if( i<1||i>L.length+1 )  //判断i的范围是否有效
		return false;
		
	if(L.length>=MaxSize)	//存储空间已满，不能再继续存入
		return false;
		
	for(int j=L.lenght;i>=i;j--)  
		L.data[j]=L.data[j-1];	//将第i个元素及之后的元素向后移动
		
	L.data[i-1] = e;	//在位置i处插入e
	L.lenght++;		//线性表长度 +1
	return true;
}

• 此处以位序的方式进行插入，范围一定是在第1位至第L.length+1的位置上插入
• $i$ 和 $j$ 表示的是位序，而数组的范围从0开始到L.length,则插入位置应该是从数组下标开始，则是从L.data[i-1]的位置上插入e

插入操作的复杂度分析

（2）删除操作

• 删除顺序表 $L$ 中的第 $i$（1<=i<=L.length） 个位置,用引用变量 $e$ 返回
• 判断 $i$ 的位置是否合法，否则返回false

• 合法则将被删除元素赋予引用变量 e,把i+1个元素及其后的所有元素往前移动一个位置，返回true

bool ListDelete(SqList &L,int i,ElemType &e){
	if(i<1||i>L.length)
	return false;
	
	e=L.data[i-1];	//将被删除的元素赋予e
	
	for(int j=i;j<L.length;j++)
		L.data[j-1]=L.data[j];
	
	L.length--;
	return true;

删除操作的复杂度分析

插入和删除示意图

（3）按值查找（顺序查找）

• 在顺序表 $L$ 中查找第一个元素值等于e的元素，并返回其位序

bool LocateElem(SqList L,ElemType e){
	int i;
	for(i=0;i<L.length;i++)
		if(L.data[i]==e)
			return i+1;	//数组下标为e的元素,其位序为  i+1
	return 0;
}

按值查找复杂度的分析

3.线性表的链式表示

• 链式存储线性表时，不需要地址连续的存储单元，不要求逻辑上相邻的元素在物理位置上也相邻
• 通过 “链” 建立数据之间的逻辑关系，插入和删除不需要移动大量元素，只需，修改指针
• 会失去随机存取的优点

3.1 单链表的定义

除了存放自身信息外，还需要存放一个指向其后继的指针

单链表的节点描述如下

typedef struct LNode{	//节点类型
	ElemType data;	//数据域
	Struct LNode *next;	//指针域
}LNode;

3.1.1单链表的基本操作

(1)头插法建立单链表

• 采用头插法建立单链表时，读入数据的顺序与生成的链表的元素顺序是相反的
  
• 从一个空表开始，通过头插法建立单链表的结点，以插入S所指的结点为例
• ① 先将 S 所指结点的next指针，指向 L 所指的头结点的next指针,保存了头结点的后继结点的地址
• ② 然后将L所指的头结点的next指针指向S所指的结点

LinkList List_HeadInsert(LinkList &L)	//逆向建立单链表
	LNode *s;int x;
	L=(Linklist)malloc(sizeof(LNode));	//创建头结点
	L->next=NULL；	//初始为空链表
	
	scanf("%d",&x);	//输入结点的值
	while(x!=10){	//输入10表示结束
		s=(LNode*)malloc(sizeof(LNode));	//创建新结点
		s->data=x;
		s->next=L->next;
		L->next=s;	//将新结点插入表中，L为头指针
		scanf("%d",&x);
	}
	return L;
}	

• 每个结点的插入时间为 $O(1)$ ，设单链表长为 $n$ ，则总时间复杂度为 $O(n)$

(2)尾插法建立单链表

• 采用尾插法建立单链表时，读入数据的顺序与生成的链表的元素顺序是相同的
  
• 从一个空表开始，通过尾插法建立单链表的结点，以插入S所指的结点为例
• ①为了将新结点每次都插入当前链表的表尾，需要增加一个尾指针r,一开始在头结点，最后始终会指向链表的尾结点
• ② 然后将 r 所指的头结点的next指针指向S所指的结点
• ③然后r指针指向s，代替s成为新的指向尾结点的指针，然后把尾结点next指针置空

LinkList List_HeadInsert(LinkList &L)	//逆向建立单链表
	int x;
	L=(Linklist)malloc(sizeof(LNode));	//创建头结点
	LNode *s,*r=L;
	
	scanf("%d",&x);	//输入结点的值
	while(x!=10){	//输入10表示结束
		s=(LNode*)malloc(sizeof(LNode));	//创建新结点
		s->data=x;
		r->next=s;
		r=s;	//r指向新的表尾指针
		scanf("%d",&x);
	}
	r->next=NULL;	//尾结点指针置空
	return L;

• 每个结点的插入时间为 $O(1)$ ，设单链表长为 $n$ ，则总时间复杂度为 $O(n)$

(3)按序号查找

• 在单链表从第一个节点出发，顺指针next逐个往后遍历，直到找到序号为第 i 个结点为止，否则返回NULL指针域
• 时间复杂度为 $O(n)$

LNode *	GetElem(LinkList L,int i){
	if(i<0) 	
		return L;	//返回NULL
	LNode *p;
	int j=0;
	p=L; 	//指向头结点
	while(p!=NULL&&j<i){	循环找打第i个结点
		p=p->next;
		j++;
	}
	return p;
}

(4)按值查找

• 从单链表的第一个节点开始，从前往后依次比较各结点数据域的值，若有等于给定值e的节点，则返回该节点的指针，若是没有这个结点，返回NULL
• 时间复杂度为 $O(n)$

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

(5)插入结点操作

• 将值为 x 的新结点插入到单链表的第 i 个位置，先检查i的位置是否合法
• 然后找到待插入位置的前驱结点，即数组下标 第i-1 个结点

①按序号查找算法GetElem(L,i-1)，令 p 所指结点的next指针，指向 p 所指的结点的next指针指的位置

②然后让p的next指向要插入的s指针所指的结点

复杂度为$O(n)$，若在给定的结点插入新结点，时间复杂度仅为 $O(1)$

P=GetElem(L,i-1);
s->next=p->next;
p->next=s;

扩展：对某一结点进行前插操作

• 将 *s 插到 *p 的后面
• 将p->data 与s->data互换
• 时间复杂度为 $O(1)$

s->next=p->next;
p->next=s;
temp=p->data;	//交换数据域部分
p->data=s->data;
s->data=temp;

(6)删除结点操作

• 将单链表第i个结点删除，先检查删除位置是否合法
• 找到第i-1个结点，即前驱结点p，
• 将*p的next指针指向*q的下一个节点

扩展：对某一结点进行删除操作

• 将 *p 的后继结点 *q 的值赋予 p，然后删除后继结点
• 将p->data 与p->next->data互换
• 释放掉 *q 节点
• 时间复杂度为 $O(1)$

q=p->next;
p->data=p->next->data;
p->next=q->next;
free(q);

3.2 双链表

双链表有两个指针prior和next，分别指向前驱结点和后继结点

• 插入、删除时间复杂度为 $O(1)$

typedef struct DNode{	//定义双链表类型
	ElemType data;	//数据域
	struct DNode *prior,*next;	//前驱指针和后继指针
}DNode;

(1)双链表的插入

①s->next=p->next;
②p->next->prior=s;
③s->prior=p;
④p->next=s;

• ※第 ① 步和第 ② 步必需在第四步之前，否则 *p 的后继结点的指针会丢失，导致插入失败

(2)双链表的删除

①p->next=q->next;
②q->next->prior=p;
free (q);

3.3 循环链表

(1)循环单链表
循环单链表和单链表区别在于最后一个结点的指针不是NULL而是指向头结点，形成一个环的双链表

对循环单链表设置尾指针r,对表头和表尾进行操作只需要 $O(1)$ 的时间复杂

(2)循环双链表

3.4 静态链表

①静态链表借助数组描述线性表的链式存储结构
②结点也有数据域data和指针域next，不过这里的指针指的是结点的相对地址（数组下标）
③静态链表也要预先分配一块连续的内存空间

#define MaxSize 50	//静态链表的最大长度
typedef struct{	//静态链表结构类型的定义
	ElemType data;	//存储数据元素
	int next;	//下一个元素的数组下标
}SLinkList[MaxSize];

• 静态链表以next ==-1作为结束标志
• 插入、删除操作与动态链表相同，只需要修改指针，不需要移动元素

4.顺序表和链表的比较

1.存取方式

顺序表：顺序存取，随机存取
链表：从头顺序存取
比如从第i个位置执行存或取的操作，顺序表仅需访问一次，链表需要从表头开始访问i次

2.逻辑结构与物理结构

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

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

对于按值查找，顺序表无序时，两者的时间复杂度均为O(n),顺序表有序时采用折半查找，
时间复杂度为O(logn)

对于按序号查找，顺序表支持随机访问,时间复杂度仅为O(1),链表的平均复杂度为O(n)

顺序表的插入、删除操作，平均需要移动半个表长的元素，链表的插入删除只需修改相关指针域
由于链表的每个结点带有指针域，故存储密度<1

4.空间分配

顺序存储:
①一旦存储空间装满就不能扩充，若加入新元素，会发生内存溢出，也因此需要预先分配足够大的存储空间
②预先分配过大，浪费内存，预先分配过小，内存溢出
③动态分配内存虽然存储空间可以扩充，但是需要移动大量元素，导致操作效率低
④若是内存没有更大块的连续存储空间，会导致分配失败

链式存储
只在需要时分配结点空间，只要内存有空间就可以分配，操作灵活，高效