数据结构学习--第2章_数据结构第二章

一、线性表的定义

线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列。
相同：各数据元素所占空间一样大。
有序序列：有先后次序

线性表和顺序表、链表关系：
线性表：是一种逻辑结构，表示元素之间一对一相邻的关系。
顺序表、链表：是指存储结构。

位序与数组下标的区别：
位序：从1开始
数据下标：从0开始

二、线性表的顺序表示

顺序表的顺序存储又称顺序表。（用顺序存储方式实现的线性表）
顺序存储：逻辑上相邻的两个元素在物理位置上也相邻（逻辑顺序与物理顺序相同）

顺序表的特点：

1. 顺序表支持随机存取 O(1) ，通常用数组来描述线性表的顺序存储结构。
2. 存储密度高
3. 扩展容量不方便
4. 插入、删除不方便

静态分配与动态分配

静态分配：
数组大小和空间事先固定。

#define MaxSize 50 //静态分配下的顺序表最大长度
typedef struct {
	int data[MaxSize]; //静态数组存放元素
	int lenght; //当前长度
}SqList; //顺序表定的类型定义
1
2
3
4
5

动态分配：
存储数组的空间是在程序执行过程中通过动态分配语句分配的，可扩展存储空间

#define InitSize 50 //动态分配下的顺序表初始长度
typedef struct {
	int *data; //动态分配数组的指针
	int MaxSize，lenght; //最大容量和当前长度
}SqList; //顺序表定的类型定义
1
2
3
4
5

初始化动态分配语句

L.data = (int*)malloc(sizeof(int) * InitSize);
1

malloc：申请存储空间
free： 释放存储空间

插入操作

按位序插入

bool ListInsert(SqList &L,int i,int e){//i--位序，e--元素
//将e插入在第i个位置
	if(i<1||i>l.length+1) return false;
	
	if(L.length>=MaxSize) return false;
	
	for(int j = L.length;j>=i;j--){
		L.data[j] = L.data[j-1];
		//最后一次循环：j==i 将data[i-1]放到data[i]
	}
	L.data[i-1] = e;
	L.length++;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度关注深层循环语句循环次数：移动元素
最好情况：
在表尾插入：（i=length+1）O(1)
最坏情况：
在表头插入： （i==1）O(n)
平均情况：
p_i=1/(n+1)
移动的平均次数：n*p+(n-1)*p+(n-2)p+…+1p+0p=n/2
O(n)=2/n

删除操作

按位序删除

bool ListDelete(SqList &L,int i,int &e){
	//将第i个元素删除，并返回删除元素e
	if(i<1||i>L.length) return false;//i范围是否有效
	
	e = L.data[i-1];
	
	for(int j = i;j<length;j++){//从下标为i的元素依次往前挪
		data[j-1] = data[j];
	}
	L.length--;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

最好情况：
在表尾删除：（i=length）O(1)
最坏情况：
在表头删除： （i==1）O(n-1)=O(n)
平均情况：
p_i=1/n
移动的平均次数：(n-1)*p+(n-2)*p+(n-3)p+…+1p+0p=(n-1)/2
O(n)=(n-1)/2

查找

按位查找

查找第一个元素值等于e的元素，并返回位序

int LocateElem(SqList L,int e){//不用加&
	for(int i = 0;i<L.length;i++){
		if(L.data[i]==e) return i+1;
	}
	return 0;
}
1
2
3
4
5
6

复杂度：比较元素
最好情况：
在表头：比较一次 O(1)
最坏情况：
在表尾（不存在）：比较length次 O(n)
平均情况：
p_i=1/n
比较的平均次数：n*p+(n-1)*p+(n-2)*p+…+1p=(n+1)/2
O(n)=(n+1)/2

按位查找

int GetElem(SqList L,int i){//不用加&
	return L.data[i];
}
1
2
3

时间复杂度：O(1)

三、线性表的链式表示

线性表的链式存储又称单链表 （不需要使用地址连续的存储单元）
链表节点内容：
①元素自身信息
②指向后续的指针

单链表表的特点：

1. 不支持随机存取（非随机存储）
2. 删除、插入不需要移动元素，只需修改指针
3. 不需要大量连续的存储空间，但是链表附加指针域，存在浪费存储空间的缺点。

单链表

节点类型描述

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;
//*LinkList 指向节点的指针
1
2
3
4
5

扩展： typedef <数据类型><别名>
强调是单链表：LinkList
强调是节点：LNode *
（LNode * L 和 LinkList L等价，声明了指向单链表的第一个节点的指针）

判空条件：
①不带头节点：
L == Null
②带头结点：
L->next == Null

建立（带头结点）

头插法（单链表的逆置）

新节点插入到单链表表头

LinkList List_HeadInsert(LinkList &L){
	LNode *s;int x;
	L = (LinkList)malloc(sizeof(LNode));//创建头节点
	L->next = NULL;//避免指向脏数据

	scanf("%d",&x);
	while(x!=9999){
		s = (LinkList)malloc(sizeof(LNode));
		//系统生成一个LNode的节点，并将节点起始位置赋值给s
		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
14
15
16

重要应用：链表的逆置
每插入一个新节点时间复杂度为：O(1)
总时间复杂度为：O(n)

尾插法(带头结点)

新节点插入到单链表表尾
添加了一个链尾指针

LinkList List_HeadInsert(LinkList &L){
	int x;
	LNode *s,*r=L;
	L = (LinkList)malloc(sizeof(LNode));//创建头节点
	L->next = NULL;//避免指向脏数据

	scanf("%d",&x);
	while(x!=9999){
		s = (LinkList)malloc(sizeof(LNode));
		//系统生成一个LNode的节点，并将节点起始位置赋值给s
		
		s->data = x;
		s->next = r->next;
		r->next = s;
		r=s;//跟随队尾移动
		scanf("%d",&x); 
	}
	r->next = NULL;
	return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

每插入一个新节点时间复杂度为：O(1)
总时间复杂度为：O(n)

查找

按序号查找

位序查找

LNode *GetElem(LinkList L,int i){
	int j = 1; // 计数，初值为1

	LNode *p = L->next ;
	
	if(i<1) return NULL;

	while(p&&j<i){//从第1个节点开始找，找第i个
	//结束循环是j=i
		p = p->next;
		j++;
	}
	return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

按序号查找：时间平均复杂度 O(n)

按值查找表节点

LNode *LocateElem(LinkList L,int e){
	//查找数据域等于e的节点并，返回该节点
	LNode *p = L->next;
	while(p!=NULL&&p->data!=e){//注意p判空在前
		p = p->next;
	}
	return p;
	//寻找失败返回NULL
}
1
2
3
4
5
6
7
8
9

按值查找：时间平均复杂度 O(n)

插入节点

按位序插入

插入结点将值为x的新节点插入到单链表的第i个位置上。
关键key：找到第i-1个结点

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

时间开销在查找第i-1个元素，时间复杂度为O(n)；
（ 若在给定结点后插入元素，O(1) ）

bool ListInsert(LinkList &L,int i,int e){
	if(i<1) return false;
	LNode *p;//指向当前扫描到的结点
	int j;//当前是第几个结点
	p=L；
	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 = p->next;
	p->next = s->next;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

前插插操作（扩展）

在某一结点前插入一个新的节点

1. 遍历实现：
   从头节点开始顺序查找到其前驱节点，时间复杂度O(n)
2. 非遍历：
   仍然将s插入到p后面
   将p->data和s->data交换，时间复杂度O(1)

s->next = p->next;
p->next = s->next;//修改指针域

temp = s->data;
s->data = p->data;
p->data = temp;//修改数据域
1
2
3
4
5
6

位序插入 （不带头节点）

bool ListInsert(LinkLst &L ,int i,int e){
	if(i<1) return false;
	
	if(i==1){//特殊处理
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->data = e;
		s->next = L->next;
		L=s;
		return true;
	}
	LNode p = L;
	int j=1;
	while(p!=NULL&&j<i-1){
		p=p->next;
		j++;
	}
	if(p==NULL){return false;}
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	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

删除

按位序删除

关键：找到第i-1个结点，既被删除结点的前驱结点

p = GetElem(L,i-1);
q = p->next;
p->next = q->next;
free(q);
1
2
3
4

时间耗费在查找上，时间复杂度：O(n)

删除指定结点*p

1. 从链表头节点开始顺序找到p的前驱节点，然后执行删除操作。
   时间复杂度：O(n)
2. 将后续结点值赋给自身，再删除p的后续结点

q=p->next;
p->data =q-data;
p->next = q->next;
free(q);
1
2
3
4

时间复杂度：O(1)

求表长

时间复杂度：O(n)

int getSize(LinkList &L){
	LinkList p=L;
	int j=0;
	while(p->next!=NULL){
		j++;
		p=p->next;
	}
	return j;
}
1
2
3
4
5
6
7
8
9

双链表

1. 双链表结点中有两个指针prior(前驱节点)和next(后续结点)。
2. 不支持随机存取

结点类型描述

typedef struct DNode{
	int data;
	struct LNode *prior,*next;
}DNode,*DLinkList;
1
2
3
4

查找

其按值查找和按位查找与单链表一致
只能遍历实现；O(n)

插入

在p结点之后插入*s

s->next = p->next;
if(p->next!=NULL)p->next->piror = s;//若p为最后一个结点跳过
p->next = s;
s->piror = p;

1
2
3
4
5

在p结点之前插入*s

s->next = p;
s->piror = p->piror;
if(p->piror!=NULL)p->piror->next = s;
p->piror = s;
1
2
3
4

删除

删除结点*p的后续结点 *q

p->next = q->next;
if(q->next!=NULL)q->next->prior = p;
free(q);
1
2
3

删除结点*p的前驱结点 *q

p->piror = q->piror;
if(q->prior!=NULL)q->piror->next = p;
free(q);
1
2
3

循环链表

1. 表中最后一个结点指向头节点
   （初始化：L->next = L）
2. 表中没有指针域为空的指针
   （判空： L->next==L。是否到队尾：p->next == L）
3. 循环双链表在任何一个地方删除和插入操作都是等价的，不用判断是否是表尾
4. 双链表可以从表中任意一个结点开始遍历整个链表
5. 若常对表头、表尾进行操作；可以对循环单链表不设头指针，设尾指针r。(r->next 既头指针)
6. 此时对头尾操作时间复杂度：O(1)；若只设头指针，对队尾操作时间复杂度：O(n)

循环双链表

1. 头结点的prior指针指向表尾结点，表尾结点的next指针指向头节点
   (初始化：L->prior=L;L-next = L;)
2. 当循环链表为空表时，其头结点piror和next都等于L。
3. 插入与删除与双链表相同，不会出现NULL报错。

静态链表

定义：

1. 借组数组来描述线性表的链式存储结构。
2. 结点有data数据域和next指针域（结点的相对地址-数组下标(游标)）。
3. 与顺序表一样，需要事先分配一块连续的内存空间

0号结点充当头指针，-1表示表尾，游标充当指针。

不支持随机存取，容量固定不变

扩展：
应用：放置在索引块的FAT（文件配置表）。
FAT支持随机访问（指不用依次访存），文件扩展也易实现。

结构类型描述

#define MaxSize 50
typedef struct{
	int data;
	int next;
}SLinkList[MaxSise];//可以用SLinkList来定义一个长为maxSize的数组
//struct Node a[maxSize] ~SLinkList a;
1
2
3
4
5
6

操作

1. 初始化：a[0].next = -1;
2. 按位序查找：从头结点开始依次遍历：O(n)
3. 插入位序为i的结点：（与单链表类是）
   ①、找到一个为空的结点，存入数据
   ②、找到第i-1个结点
   ③、修改新结点的next值
   ④、修改i-1结点的next值

四、顺序表与链表的比较

都是线性结构

存取方式

1. 顺序表可以顺序存取和随机存取~O(1)
2. 链表只能从头顺序存取~O(n)

结构

1. 顺序表：
   逻辑上相邻，物理存储位置上也相邻。(大片连续空间，存储密度高)
2. 链表：
   逻辑上相邻，物理存储位置不一定相邻。（离散小空间）

操作

1. 按值查找和，顺序表无序：O(1);有序时（折半）：O(log₂n)
2. 顺序表插入和删除，平均移动半个表长的元素（移动元素）：O(n)。
   链表的插入删除、删除修改相关指针域即可（查找目标元素）：O(n)

空间分配

1. 顺序表：
   需预先分配足够大的存储空间。扩充效率低。
2. 链式节点空间只在需要时申请分配。