数据结构学习笔记

错题

  • 【栈和队列】栈和队列的共同特点是只允许在端点插入和删除元素。
  • 【循环队列】数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为:（rear-front)%n （rear-front+n）%n 。
    • 虽然数学上没错，但负整数求模结果可能因为编译器环境不同而不同。
  • 【KMP】设目标串为s=“abcabababaab”，模式串为p=“babab”，则KMP模式匹配算法的next数组为[-1,0,1,2] [-1,0,0,1,2] 。
    • next数组是看当前元素的前面的子串，如p[0]是b，记-1；p[1]为a，前面是b，无相同前后缀，记0；p[2]是b，前面是ba也记0，以此类推。
  • 算法分析的目的是分析算法的效率以求改进

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
31
32
33
34
35
36
37
38
39
40
41
//插入算法 
template <typename DataType>
void LinkList<DataType>::Insert(int i,DataType x){
	Node<T>*p=first->next;
	Node<T>*s=nullptr;
	int count=0;
	while(p!=nullptr&&count<i-1){
		p=p->next;
		count++; 
	}
	if(p==nullptr) throw "插入位置错误！";
	else{
		//插入操作 
		s=new Node<T>;
		s->data=x;
		s->next=p->next;
		p->next=s;
	}
}
//删除算法
 template <typename DataType>
DataType LinkList<DataType>::Delete(int i){
	Node<DataType>*p=first;
	Node<DataType>*s=nullptr;
	DataType x;
	int count=0;
	while(p!=nullptr&&count<i-1){
		p=p->next;
		count++; 
	}
	if(p==nullptr||p->next==nullptr) throw "删除位置错误！";
	else{
		//删除操作
		s=p->next;
		x=p->data;
		p->next=s->next;
		delete s;
		return x;	 
	}
}

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
29
//头插法
template <typename T>
LinkList<T>::LinkList(T a[],int n){
	first=new Node<T>;
	first->next=nullptr;//初始化
	for(int i=0;i<n;i++){
		Node<T>* s=nullptr;
		s=new Node<T>;
		s->data=a[i];
		s->next=first->next;
		first->next=s;
	}
}

//尾插法
template <typename T>
LinkList<T>::LinkList(T a[],int n){
	first=new Node<T>;
	Node<T>*r=first,*s=nullptr;
	for(int i=0;i<n;i++){
		//遍历数组赋值
		s=new Node<T>;
		s->data=a[i];
		r->next=s;
		r=s; 
	}
	r->next=nullptr;
}

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
//注意元素编号和存储位置的关系
//插入
template <typename T>
void Seqlist::Insert(int i,T x){
	if(length==MaxSize) throw "上溢"; 
	if(i>length+1||i<1) throw "插入位置有误！";
	for(int j=length;j>=i;j++){
		data[j]=data[j-1];
	}
	data[i-1]=x;
	length++;
}//删除 
 template <typename T>
T SeqList<T>::Delete(int n){
	if(length==0) throw “下溢”;
	if(n>Length||n<1) throw "删除位置有误";
	T x=data[n];
	for(int i=n;i<Length;i++){
		data[i-1]=data[i];
	}
	Length--;
	return x;
}

4.请写出链队列的入队和出队算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//入队 从尾入
template <typename T>
void LinkQueue::EnQueue(T x){
	Node<T>*s=nullptr;
	s=new Node<T>;
	s->data=x;
	s->next=nullptr;
	rear->next=s;
	rear=s;
}
//出队 从头出
template <typename T>
T LinkQueue<T>::DeQueue(){
	T x;
	Node<T>*p=nullptr;
	if(rear==front) throw "下溢";
	p=front->next;
	x=p->data;
	front->next=p->next;//摘链
	if(p->next==nullptr) rear==front;//判空
	delete p;
	return x;
}

绪论

  • 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
  • 数据项是数据的最小单位，数据元素是讨论数据结构时涉及的最小数据单位。
  • 从逻辑关系上讲，数据结构主要分为集合、线性结构、树结构和图结构。
  • 数据的存储结构主要有顺序存储结构和链接存储结构两种基本方法，所有存储结构都要存储两方面内容：数据元素和数据元素之间的关系
  • 数据元素之间的逻辑关系在顺序存储结构中由存储位置表示，在链接存储结构中由指针表示。
  • 算法具有五个特性，分别是①有零个或多个输入②有一个或多个输出③有穷性④确定性⑤可行性
  • 算法的可行性是描述算法的每一条指令可以转换为某种程序设计语言对应的语句，并在计算机上可以执行。
  • 算法的描述方法通常有自然语言，程序设计语言，流程图和伪代码四种。伪代码被称为算法语言。

算法

什么是算法？

· 算法是对特定问题求解步骤的一种描述，是指令的有限序列

算法的三个基本特性

  • 有穷性

    • 一个算法必须总是在执行有穷步后结束，且每一步都在有穷时间内完成

  • 确定性

    • 算法中的每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相同的输入只能得到相同的输出

  • 可行性

    • 描述算法的每一条指令可以转换为某种程序设计语言对应的语句，并在计算机上可以运行

算法有零个或多个输入(算法可以没有输入)，但是必须要有输出，而且输入与输出之间有着某种特定的关系

算法分析–算法效率的度量

时间复杂度

• 用算法中基本语句的执行次数来度量算法的工作量

• 基本语句可以理解为整个算法中执行次数最多的语句

• 考察方式：只考察当问题规模充分大，算法中基本语句的执行次数在渐近意义下的阶，称为时间复杂度，用大O表示。关注的是增长趋势

• O(1)<O(log_2 n)<O(n)<O(nlog_2 n)<O(n^2)<O(n^3)<…<O(2^n)<O(n!)

空间复杂度

• 是指算法在执行过程中需要的辅助空间数量，即除算法本身和输入输出数据所占的空间外，算法临时开辟的存储空间

• S(n)=O(f(n))

• 如，用到一个临时存储temp，则空间复杂度为O(n);用到一个n个元素的临时存储的数组，则为O(n)

算法分析–举例

非递归算法

• ①直接看循环重数

• ②多重求和，分析每次循环都是加1的情况

• ③每次循环为二倍，用等比数列，求多少项，一般是取对数，结果为对数阶

递归算法

• 根据递归过程建立递推关系式并求解（求和表达式）

最好、最坏、平均情况

• 最好情况：不能代表算法的效率，当出现概率较大时分析

• 最坏情况：最坏能坏到什么程序，实时系统需要分析

• 平均情况：已知输入数据分布情况，通常假设等概率分布

举例：一维数组顺序查找

• 最好：一次找到，O(1)

• 最坏：最后才找到，O(n)

• 平均：n/2，O(n)

• 如果算法的时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况

数据结构

数据结构是相互之间存在一定关系的数据元素的集合

根据视点(是否基于内存)的不同分为

逻辑结构

• 数据元素之间逻辑关系的整体，如关联方式或邻接关系，取决于实际问题

四类

• 集合 数据元素之间没有关系

• 线性结构 数据元素之间是一对一的线性关系

• 树结构 数据元素之间是一对多的层次关系

• 图结构 数据元素之间多对多的任意关系

存储结构

• 数据及其逻辑结构在计算机(内存)中的表示，包括数据元素及其逻辑关系

两种

• 顺序存储结构 用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置(下标)表示

• 链接存储结构 用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针(地址)表示

抽象数据类型(ADT)

线性表

线性表的逻辑结构

线性表简称表，是n(n≥0)个数据元素的有限序列，线性表中数据元素的个数称为线性表的长度。当n=0时称为空表。

  • 一个非空表记为：L=(a1,a2,…,an) 。a1称为表头元素，an称为表尾元素。
  • ak-1称为ak的前驱，ak称为ak-1的后继。除了表头元素和表尾元素，其他元素有且仅有一个前驱和一个后继。

线性表的顺序存储结构及实现

顺序表的顺序存储结构

  • 物理位置相邻表示逻辑关系。逻辑上和物理上相邻
  • 任一元素均可随机存取

存储位置的计算：

每个元素占l个存储单元

递推式：
$$
Loc(a_{i+1})=Loc(a_i)+l
$$
更通用的：
$$
Loc(a_i)=Loc(a_1)+(i-1)\times{l}
$$
注意是i-1，举例就知道了

实现

查找

按位查找 O(1)

1
2
3
4
5
template <typename DataType>
DataType SeqList<DataType>::Get(int i){
    if(i<1||i>length) throw "查找位置非法"; //注意要先判断
    else return data[i-1];//注意序号是1开始，而存储是从0开始
}

**按值查找 **O(n)

1
2
3
4
5
6
template <typename DataType>
DataType SeqList<DataType>::Locate(DataType x){
    for(int i=0;i<length;i++)
        if(data[i]==x) return i+1;//注意返回序号i+1
    return 0;//查找失败
}

插入 O(n)

注意先判断满足条件①表是否已满，即length==MaxSize ②未满，则插入位置是否越界

1
2
3
4
5
6
7
8
9
template <typename DataType>
void SeqList<DataType>::Insert(int i,DataType x){
    if(length==MaxSize) throw "上溢";
    if(i<1||i>length+1) throw "插入位置错误";//i最大到length，最小到1
    for(int j=length;j>=i;j--)
        data[j]=data[j-1];//从第length-1个后移到下一个，第length个数组元素是空的
    data[i-1]=x;//序号i存在数组下标为i-1的位置
    length++;//长度加一，别忘了
}

平均移动 $\frac{n}{2}$ 次

删除 O(n)

如插入类似，同样先判定①表是否为空 ②表不空，删除位置是否越界 返回删除元素的值

1
2
3
4
5
6
7
8
9
10
11
template <typename DataType>
DataType SeqList<DataType>::Delete(int i){
    DataType x;
    if(length==0) throw "下溢";
    if(i<1||i>length+1) throw "删除位置错误";
    x=data[i-1];//i在下标为i-1上，取出位置i的元素
    for(int j=i;j<length;j++)
        data[j-1]=data[j];//从第i个位置往前移，覆盖掉i-1的位置，到length-1移动后结束
    length--;//长度减1
    return x;
}

平均移动 $\frac{n-1}{2}$ 次

线性表的链式存储结构及实现

链表

实现

1
2
3
4
5
6
7
8
9
//成员变量只有一个 头结点
Node<DataType> * first

//结点结构包含一个数据域和一个指针域
template <typename DataType>
struct Node{
    DataType data;//数据域
    Node<DataType> *next;//指针域
}

遍历

1
2
3
4
5
6
7
8
9
template <typename DataType>
void LinkList<DataType>::PrintList(){
    Node<DataType>*p=first->next;//工作指针初始化
    while(p!=nullptr){
        cout<<p->data<<"\t";
        p=p->next;//工作指针p后移，注意不能写成p++
    }
    cout<<endl;
}

求长度

工作指针从first->next开始，first不算长度

1
2
3
4
5
6
7
8
9
10
template <typename DataType>
int LinkList<DataType>::Length(){
    Node *p=first->next;
    int count=0;
    while(p!=nullptr){
        count++;
        p=p->next;
    }
    return count;
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename DataType>
void LinkList<DataType>::Insert(int i,DataType x){
    Node<DataTpe> *p=first,*s=nullptr;//指针初始化
    int count=0;//记录遍历位置
    while(p!=nullptr&&count<i-1){//查找i-1位置，插入在其后面就成了第i个元素
        p=p->next;//工作指针后移
        count++;
    }
    if(p==nullptr) throw "插入位置错误";//没有找到第i-1个
    else{//找到
        s=new Node<DataType>;//申请结点s，数据域为x
        s->data=x;
        s->next=p->next;//将原本第i个插在s后面
        p->next=s;//将s插入到p之后
    }
}

删除

和插入类似，都是找到后对下一个位置进行操作，但是当对象为表尾，此时，可插但不可删，因此判断位置除了p==nullptr还多了p->next==nullptr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename DataType>
DataType LinkList<DataType>::Delete(int i){
    DataType x;
    int count=0;
    Node<DataType> *p=first,*q=nullptr;//工作指针指向头结点
    while(p!=nullptr&&count<i-1){
        p=p->next;
        count++;
    }
    if(p==nullptr||p->next==nullptr) throw "删除位置错误";
    else{
        q=p->next;//暂存被删结点
        x=q->data;
        p->next=q->next;//摘链
        delete q;
        return x;
    }
}

建立

头插法

初始化

1
2
3
4
5
6
7
8
9
10
11
12
template <typename DataType>
LinkList<DataType>::LinkList(DataType a[],int n){
    first=new Node<DataType>;
    first->next=nullptr;//初始化一个空链表
    for(int i=0;i<n;i++){
        Node<DataType> *s=nullptr;
        s->data=a[i];
        s->next=first->next;//插在头结点后
        first->next=s;
    }
}

尾插法

初始化；需要一个尾指针；建立完毕，终端指针指针域用空指针收尾

1
2
3
4
5
6
7
8
9
10
11
12
template <typename DataType>
LinkList<DataType>::LinkList(DataType a[],int n){
    first=new Node<DataType>;
    Node<DataType> *r=first,*s=nullprt;//尾指针初始化
    for(int i=0;i<n;i++){
        s=new Node<DataType>;
        s->data=a[i];
        r->next=s;//插在尾指针后
        r=s;//尾指针后移
    }
    r->next=nullptr;//建立完毕，空指针收尾
}

单链表实现就地逆序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class T>
void Reverse(Node<T> *f){
	//头插法,再复制 
	Node<T> *p=new Node<T>;
	Node<T> *u=new Node<T>;
	p=f->next;
	f->next=nullptr;
	while(p!=NULL){
		u=p->next;//存放后继结点
		p->next=f->next;//插入头结点下一个节点之前 
		f->next=p;//头插
		p=u;		 
	}
}

就地逆序，首先将原链表断开，从第一个结点开始重新头插法，每次插入前要保存后继结点，插完后工作指针指向后保存的后继结点

删除有序链表的一个区间上的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename T>
void deleteBet(Node<T> *first,int mink,int maxk){
    Node<T> *p=nullptr;
	Node<T> *q=nullptr;
    p=first;
    while(p->next!nullptr&&p->next->data<=mink)
        p=p->next;
    //结束循环时，p的下一个是大于mink的
    if(p->next!=nullptr){
        q=p->next;
        while(q->data<maxk){
            Node<T> *u=q->next;//记录下一个
            p->next=q->next;
            delete q;
            q=u;//q移到下一个
        }
    }
}

首先判断p的下一个是大于的，然后再申请一个指针q来记录接下来的结点，判断q是否小于maxk是的话要删除q；删除结点需要一个指针u来先记录q后面的结点，将q摘链删除后，让q指向保存好的下一个结点

循环链表

两种存储结构的选择

按值查找：

  • 顺序表是O(1)，随机存取
  • 链表是O(n)，顺序存取

插入和删除

  • 顺序表O(n)
  • 链表O(1)
存储结构 链表 顺序表
空间上 元素个数变化较大或为止时选择 事先知道线性表的大致长度，使用顺序表空间效率更高
时间上 频繁插入和删除时选择 频繁查找很少插入删除；或操作和元素在表中的位置密切相关

栈和队列

队列

初始：front=rear=0

入队：base[rear]=x;rear++;

出队：x=base[front];front++

空队标志：front==rear;

数组大小为MAXSIZE时，当rear==MAXSIZE发生溢出：

  • 若front=0，rear==MAXSIZE，再入队真溢出
  • 若front≠0，rear==MAXSIZE，再入队假溢出(前面还有位置其实)

循环队列

front处不存值，rear存值

插入元素：

1
2
3
if((rear+1)%MAXSIZE==front) throw "上溢";
rear=(rear+1)%MAXSIZE;
data[rear]=x;//插入元素

删除元素：

1
2
3
if(front==rear) throw "下溢";
front=(front+1)%MAXSIZE;
return data[front];//返回出队前的队头元素,front本来是不存值的，放到front相当于出队

注意是(指针+1)%MAXSIZE，不能指针%MAXSIZE，因为要包括移动到下一位，不能停留在MAXSIZE，直接一步到位

队满条件：(rear+1)%MAXSIZE==front;

字符串

  • 字符串简称“串”
  • 任意个连续的字符组成的子序列称为该串的子串
  • 包含子串的串称为主串

KMP

看子串即可，当在对比模式串和目标串时，通过模式串可以反应目标串的一些信息

next[j]定义：
$$
next[j]=
\begin{cases}
-1& \text{j=0}\
最长公共前后缀的长度& \text{集合非空}\
0& \text{其他情况}
\end{cases}
$$

注意找子串前后缀是j之前的，不包括j位置的字符；next[0]=-1

设目标串为s=“abcabababaab”，模式串为p=“babab”，则KMP模式匹配算法的next数组为 [-1,0,0,1,2]

矩阵的压缩存储

特殊矩阵

对称矩阵

原本需要n×n，现在只用n×(n+1)/2

存一半+主对角线

三角矩阵

上(下)三角，主对角线以下(上)为均为常数c，和对称矩阵类似，但是要多存一个c

现在只有n×(n+1)/2+1

存一半+主对角线+一个常数

对角矩阵

所有非零元素都集中在以对角线为中心的带状区域，除了主对角线和若干条次对角线的元素外，所有其他元素都为零。

只存非0

树和二叉树

  • 注意树的定义，是有且仅有一个根节点且其余结点配分成互不相交的集合(不能构成回路)。

  • 某结点拥有的子树的个数称为该结点的度；树中各结点度的最大值称为该树的度。

  • 线性结构：前驱->后继 树的结构：双亲->孩子

image.png

重点：对于一棵n结点的树，其所有结点的度之和为n-1。

理解：把结点上面的边与它关联，那么除了根节点上面没有边，总共的边数(即度数和)就等于所有结点数-1，因此所有结点的度数和就是总结点数-1即n-1。因此有结点数n=分支数+1

习题

  • 已知一颗度为4的树中，度为i(i>=1)的结点个数有i个，问该树中有 个叶子结点。

    A. 19 B. 21 C. 23 D. 25

解析：设i度结点数为ni个，则本题树的度为4，总结点数n=n0+n1+n2+n3+n4,由公式结点数n=分支数+1,且度为i(i>=1)的结点个数有i个，那么总的分支数为1+n1+2n2+3n3+4n4，联立两式可得叶子节点数n0=1+n2+2n3+3n4=21

  • 已知一棵度为3的数，度为1的结点有2个，度为2的结点有3个，度为3的结点有4个，问有多少叶子结点。

解析：同理n=n0+n1+n2+n3+n4=2n1+3n2+4n3+1，解的n0=1+n2+2n3=12

此类给度数k和一些结点数，求叶子结点的题一般做法都是

1.设i度结点数为ni个，总结点数就是n=n0+n1+..+nk

2.利用结点数=分支数+1，i度结点有i个分支，因此分支数为∑i×ni求和，所以得n=∑i×n+1

3.联立12，带入题目给的相应结点数即可得到结点数n0

二叉树

image.png

二叉树的逻辑结构

注意，二叉树和树是两种不同的树结构，二叉树不是度为2的树，也不能说是度小于等于2的树

对于前者，当是一个只有两个结点的斜树时，度为1，只有一个结点时度为0，它们度都不是2，但都是二叉树。

对于后者，树的孩子还必须要有左右之分，及时只有一个结点，也要区分它是左孩子还是右孩子。例如下图，假设是二叉树，则它们是两课不同的二叉树；假设是树，则它们是同一棵树。

![image-20221214165114732]([JJuprising/JJuprising.github.io](Joel Station (jjuprising.github.io)

满二叉树

在一棵二叉树中，所有分支结点都存在于左子树和右子树，，并且所有叶子结点都在同一层，这样的二叉树称为满二叉树。

特点：

  1. 叶子只出现在最下一层
  2. 只有度为0和度为2的结点
  3. 在同样深度的二叉树中，满二叉树结点最多，叶子节点最多。

完全二叉树

一棵满二叉树必定是一棵完全二叉树。

完全二叉树，是在满二叉树中，从最后一个结点(最右)连续去掉任意个结点(全去掉就是满二叉树)，得到的二叉树。

特点：

  1. 深度为k的完全二叉树在k-1层是满二叉树。
  2. 叶子结点只能出现在最下两层，且最下层的叶子结点都集中在左侧连续的位置。
  3. 如果有度为1的结点，只可能有一个，且该结点只有左孩子。
  4. 在结点数相同的情况下，构成的所有二叉树中完全二叉树的深度最小。

二叉树的五个性质

对于二叉树

  • 在一棵二叉树中，如果叶子结点的个数为n0,度为2的结点个数为n2，则n0=n2+1，即叶子结点数等于度为2的结点数加一。

    • 证明：结点数n=分支数+1=n1+2*n2+1,n=n0+n1+n2，联立得n0=n2+1

  • 二叉树的第i层上最多有2i-1个结点(i≥1)

    • 等比数列，首项为1，公比为2，第i层满则有2i-1个

  • 在一棵深度为k的二叉树中，最多有2k-1个结点。

    • 由上面结论深度一定时，满二叉树的结点数是最多的，满二叉树每层的结点数为1,2,4,8…是个公比为2的等比数列，到第k层有2k-1个结点，求和公式1*(1-2k)/1-2得2k-1，这也是一个等比数列的性质，即第n项的值减一等于前n-1项的和

对于完全二叉树

  • 具有n个结点的完全二叉树的深度为⌊log2n⌋+1。

    • 由完全二叉树的定义，是由满二叉树从最后一个结点连续去掉任意结点得到，因此一个深度为k的完全二叉树结点数最多是当它是深度为k的满二叉树，最少是当它是深度为k-1的满二叉树，结合上求和公式可得
      $$
      2^{k-1}≤n<2^k
      $$
      （这里假设深度为k，因此它不为k-1的满二叉树，左边取等或者取大于2k-1-1，右边就是小于等于2k-1）

  • 对于一棵具有n个结点的完全二叉树从1开始按层序编号，则对于编号为i的结点，双亲和孩子编号之间的关系为：

    • 双亲编号为$⌊i/2⌋$
    • 左孩子编号为$2i$，右孩子编号为$2i+1$

二叉树的遍历

遍历操作

前序：根左右

中序：左根右

后序：左右根

例题：

image-20221213203357221

解析：前序：ABDGCEHF；中序：DGBAEHCF；后序：GDBHEFCA

确定二叉树

先序加中序或中序加后序可以确定一棵二叉树，但是先序加后序不可以。

前序开头确定根，中序确定左右子树

如先序：A B C D E F G H I 中序：C D B F E A IHGJ

左子树 先序：BDFEF 中序：CDBFE

再左子树类推，右子树同理

后序尾部确定根，中序确定左右子树

二叉链表

前序、中序、后序、层序遍历，数据类型默认为char，注意初始化的方式，递归构造

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
#include <iostream>
using namespace std;
int count1 = 0;

struct BiNode   //二叉树的结点结构
{
	char data;       //数据类型默认为char
	BiNode *lchild, *rchild;
};

class BiTree
{
public:
	BiTree( ){root = Creat(root);}			//构造函数，建立一棵二叉树
	~BiTree( ){Release(root);}				//析构函数，释放各结点的存储空间
	void PreOrder( ){PreOrder(root);}		//前序遍历二叉树
	void InOrder( ){InOrder(root);}			//中序遍历二叉树
	void PostOrder( ){PostOrder(root);}		//后序遍历二叉树
	void LeverOrder( );						//层序遍历二叉树
	void CountLeaf1( ){CountLeaf1(root);}
	void CountLeaf2( ){cout<<CountLeaf2(root)<<endl;}
private:
	BiNode *root;                           //指向根结点的头指针
	BiNode *Creat(BiNode *bt);				//构造函数调用
	void Release(BiNode *bt);				//析构函数调用
	void PreOrder(BiNode *bt);              //前序遍历函数调用
	void InOrder(BiNode *bt);               //中序遍历函数调用
	void PostOrder(BiNode *bt);             //后序遍历函数调用
	void CountLeaf1(BiNode *bt);
	int CountLeaf2(BiNode *bt);
};

前序遍历

递归 O(n)

1
2
3
4
5
6
7
8
9
void BiTree::PreOrder(BiNode *bt)
{
	if(bt==NULL)  return;
	else {		
		cout<<bt->data<<" ";
        PreOrder(bt->lchild);
		PreOrder(bt->rchild);
	}
}

中序遍历

1
2
3
4
5
6
7
8
9
void BiTree::InOrder(BiNode *bt)
{
	if (bt==NULL)  return;      //递归调用的结束条件	          
    else {	
        InOrder(bt->lchild);    //中序递归遍历root的左子树
        cout<<bt->data<<" ";    //访问根结点的数据域
        InOrder(bt->rchild);    //中序递归遍历root的右子树
	}
}

后序遍历

1
2
3
4
5
6
7
8
9
void BiTree::PostOrder(BiNode *bt)
{
	if (bt==NULL)  return;       //递归调用的结束条件
    else {	
        PostOrder(bt->lchild);    //后序递归遍历root的左子树
        PostOrder(bt->rchild);    //后序递归遍历root的右子树
        cout<<bt->data<<" ";      //访问根结点的数据域
	}
}

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BiTree::LeverOrder( )
{
	const int MaxSize=100;
	int front=-1, rear=-1;  //采用顺序队列，并假定不会发生上溢
	BiNode *Q[MaxSize], *q;
	if (root==NULL) return;
	else {
		Q[rear++]=root;
		while (front!=rear)
		{
			q=Q[front++];
     		cout<<q->data<<" "; 		
    		if (q->lchild!=NULL)  Q[rear++]=q->lchild;		
			if (q->rchild!=NULL)  Q[rear++]=q->rchild;
		}
	}
}

构造函数——建立二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
BiNode *BiTree::Creat(BiNode *bt)
{
	char ch;
	cout<<"请输入创建一棵二叉树的结点数据"<<endl;
	cin>>ch;
    if (ch=='#') return NULL;
    else{ 
	     bt = new BiNode;       //生成一个结点
         bt->data=ch;
         bt->lchild = Creat(bt->lchild);    //递归建立左子树
         bt->rchild = Creat(bt->rchild);    //递归建立右子树
    } 
    return bt;

}

析构函数——销毁二叉树

1
2
3
4
5
6
7
8
9
void BiTree::Release(BiNode *bt)
{
	if (bt != NULL){                  
	     Release(bt->lchild);   //释放左子树
         Release(bt->rchild);   //释放右子树
         delete bt;
	}  

}

遍历算法应用

递归调用深入下一层，返回后还要继续执行

复制
  • 如果是空树，递归结束；
  • 否则，申请新结点，复制根节点
    • 递归复制左子树
    • 递归复制右子树
1
2
3
4
5
6
7
8
9
10
11
12
void BiTree::Copy(BiTree T,BiTree &NewT){
    if(T==NULL){
        NewT=NULL;//置为空
        return 0;
    }else{
        NewT=new BiNode;//申请空间
        NewT->data=T->data;//数据域
        Copy(T->lchild,NewT->lchild);//通过传递NewT->lchild将它们连接起来
        Copy(T->rchild,NewT->rchild);//递归结束后，栈的特点返回上一层
    }
        
}
计算深度
  • 如果是空树，则深度为0
  • 否则，递归计算左子树的深度记为m，递归计算右子树深度为n，深度取m和n较大者加1
1
2
3
4
5
6
7
8
9
10
11
12
int BiTree::Depth(BiTree T){
    int m,n;
    if(T==NULL) return 0;//如果是空树返回0
    else{
        m=Depth(T->lchild);//递归计算左子树的深度
        n=Depth(T->rchild);//递归计算右子树的深度
        if(m>n)//取左右子树深度大的那一个
            return (m+1);//加上当前的根节点
        else
            return (n+1);
    }
}
计算结点总数
  • 如果是空树，则结点个数为0
  • 否则，结点个数为左子树的结点个数+右子树的结点个数再+1
1
2
3
4
5
6
int BiTree:NodeCount(BiTree T){
    if(T==NULL)
        return 0;
    else
        return NodeCount(T->lchild)+NodeCount(T->lchild)+1;//+1即每轮的根结点
}

基本情况：如果是一个叶子结点，左右子树都为空，返回0，那么就是0+0+1就是1，返回到上一层，假设它没有右子树，那么当前的结点数就是1+0+1就是2，正确，返回上一层，再去递归右子树…;这个1加的就是每一轮的根节点

或者

1
2
3
4
5
6
7
8
template <class T>
void Count(BiNode<T> *br){
    if(br!=nullptr){
        Count(br->lchild);
        count++;
        Count(br->rchild);
    }
}
计算叶子

递归

  • 如果是空树，则叶子结点个数为0
  • 否则，为左子树叶子结点+右子树的叶子结点
1
2
3
4
5
6
7
8
9
10
void BiTree::CountLeaf1(BiNode *bt)
{
	if (bt!=NULL){
		if(bt->lchild==NULL && bt->rchild==NULL)//叶子左右孩子都为空
			count1++;
		CountLeaf1(bt->lchild);//不是叶子就继续递归左子树
		CountLeaf1(bt->rchild);//右子树
	}
    return;
}
1
2
3
4
5
6
7
8
int BiTree::LeadCount(BiTree *T){
    if(T==NULL) return 0;
    else{
        if(T->lchild==NULL&&T->rchild==NULL)
            return 1;//是叶子结点返回
        else return LeafCount(T->lchild)+LeafCount(T->rchild);
    }
}

前序顺序打印叶子(根左右)

1
2
3
4
5
6
7
8
9
10
void PreOrderPrint(BiNode *br){
	if(bt==nullptr) return;
	else{
		if(bt->lchild==nullptr&&bt->rchild==nullptr)
			cout<<br->data;
		PreOrderPrint(br->lchild);
		PreOrderPrint(br->rchild);
		
	}
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int BiTree::CountLeaf2(BiNode *bt)
{
	const int MaxSize=100;
	BiNode *S[MaxSize];//利用队列
	int top=-1; int count=0;
	while(bt!=NULL||top!=-1)
	{
		while(bt!=NULL)
		{
			if(bt->lchild==NULL && bt->rchild==NULL)
				count++;
			S[++top]=bt;//入队
			bt=bt->lchild;
		}
		if(top!=-1) {
			bt=S[top--];//出队
			bt=bt->rchild;
		}
	}
	return count;
}
找结点x的双亲
1
2
3
4
5
6
7
8
9
10
11
template<class T>
 void BiNode<T>::Parent(BiNode<T> *root,T x){
 	if(root!=nullptr){
 		if(root->data==x) return p;
 		else{
 			p=root;//存双亲
			Parent(root->lchild,x);
			Parent(root->rchild,x); 
		 }
	 }
 }
删除以x为根结点的子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 template<class T>
 void release(BiNde<T> T){
 	if(T!=nullptr){
 		release(T->lchild);
 		release(T->rchild);
 		delete T;
	 }
 } 
template<class T>
void DelBotmTree(BiNde<T> *root,T x){
	if(root==nullptr) return;
	if(root->data==n){
		//找到，删除
		release(root);
		root=nullptr;//标记为空，不要了 
	}
	if(root!=nullptr){
		DelBotmTree(root->lchild,x);
		DelBotmTree(root->rchild,x);
	}
}
交换左右子树

后序遍历的方法进行交换

1
2
3
4
5
6
7
8
9
10
11
12
13
template<class T>
void exchange(BiNode<T> *root){
    BiNode<T> *t;
    if(root==nullptr) return;
    else{
        exchange(root->lchild);
        exchange(root->rchild);
        //交换左右子树
        t=root->lchild;
        root->lchild=root->rchild;
        root->rchild=t;
    }
}

左右根，化简为最基本的情况就是左右结点的交换

森林

森林是$m(m≥0)$棵互不相交的树的集合。

注意区分树和森林。树删去根节点–>森林；森林增加一个根节点，将森林每一棵树的根节点作为这个根节点的子树–>一棵树

树与二叉树相互转换

树的兄弟关系<–>二叉树的双亲与右孩子

树的双亲与长子<–>二叉树的双亲与左孩子

方法：

  1. 加“兄弟”线，所有相邻兄弟之间加一条线(兄弟关系变为双亲和右孩子的关系)；
  2. 去”孩子“线，去掉结点与其他孩子的线，保留和长子的线(双亲与长子变为双亲与左孩子，和其他兄弟也没“关系”了)；
  3. 调整，以根节点为轴顺时针旋转调整，使层次分明。

image-20221214171816832

当二叉树根节点的右子树为空，说明树的根节点是单独的，没有兄弟

树的前序遍历就是二叉树的前序遍历

树的后序遍历就是二叉树的中序遍历

后序是左右根，中序是左根右。原本树的兄弟之间是左右，在二叉树变成了双亲与右孩子，因此是根右

森林转换为二叉树

方法：

  1. 将森林每棵树转换为二叉树
  2. 每棵树根结点视为兄弟相连
  3. 调整层次关系

其实由森林和树的定义也可推得方法类似，在第一步完成后，将几颗树的根节点作为兄弟，然后调整，将右兄弟作为右孩子。

image-20221214171747422

树、森林与二叉树的转换

方法：

  1. 加”孩子“线，将结点y与他的左孩子的右孩子、右孩子的右孩子。。。用线连起来
  2. 去线，删去所有双亲与右孩子的连线
  3. 层次调整

image-20221214180843999

最优二叉树

哈夫曼树不存在度为1的结点

哈夫曼树度只能为0或2，不存在度为1。至少：考虑每层2个结点（除了根结点），则至少为2h-1个

至多：考虑满二叉树，则至多为 (2^h) -1

图

图逻辑结构

邻接图

通过边数的多寡可以将图分为稀疏图和稠密图，稀疏图即边数很少的图

邻接、依附

无向图中，两个顶点相连，互为邻接点，称边依附于这两个顶点

有向图中，a指向b，称顶点a邻接到b，顶点b邻接自a，弧依附这两个点。有向边成为弧

完全图

无向完全图，任意两个顶点之间都存在边。

n个顶点的无向完全图有 $\frac{n×(n-1)}{2}$ 条边

每个顶点和其他顶点(n-1个)都有边，算多了一遍结果除2

有向完全图，任意两个顶点都存在方向相反的两条弧。

n个顶点的有向完全图有 $n×(n-1)$ 条弧

任意两点有两条，区分方向，不用除2

度、入度、出度

无向图，度

有向图，入度：进入该顶点的弧的数(以该顶点为弧头)；出度，出去的弧的数(以该顶点为弧尾)

性质：

无向图，各顶点的度数和等于边数之和两倍，度数算了两遍的边

有向图，各顶点的入度和等于出度和等于边数之和，有出必有入，有如必有出，一条边提供一个出度一个入度，入度和等于出度和，加和等于边数的2倍，各自就是等于边数和

路径、回路

  • 简单路径：序列中顶点不重复出现的路径

  • 简单回路(简单环)：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路

  • 路径长度：

    • 带权图：路径上边的权值之和
    • 非带权图：路径上边的个数

连通图

  • 无向图中，如果两顶点之间有路径，则称两顶点是连通的
  • 无向图中，如果任意两顶点都是连通的，则称该无向图是连通图

强连通图

  • 强连通顶点，在有向图中，如果a到b和b到a均有路径，则称a和b是强连通的
  • 强连通图，在有向图中，如果任意两个顶点是强连通的，则称有向图是强连通图
  • 强连通分量：非强连通图的极大连通子图**(极大强连通子图就是指一个强连通子图，再加入任何额外的节点都无法保证这个新的图是一个强连通图)**

image-20221217153730696

遍历操作

算法：BFTraverse

输入：顶点的编号 v

输出：无

  1. 队列Q初始化

  2. 访问顶点v；修改标志visti[v]=1;顶点v入队列Q；

  3. while(队列Q非空)

    3.1 v=队列Q的队头元素出队；

    3.2 w=顶点v的第一个邻接点；

    3.3 while(w存在)

    ​ 3.1.1 如果w未被访问，则访问它；修改标志vistied[w]=1;顶点w入队列Q；

    ​ 3.1.2 w=顶点v的下一个邻接点；

图的存储结构及实现

邻接矩阵

注意到自己是0，主对角线为0

空间复杂度为O(n2)

image-20221217164904968

网图的邻接矩阵可定义为：用权值代替1，主对角都是0，不可达是∞

实现

1
2
3
4
5
6
7
8
9
const int MaxSize=10;
template <typename DataType>
class MGraph{
    ...
private:
    DataType vertex[MaxSize];//存放图中顶点的数组
    int edge[MaxSize][MaxSize];//存放图中边的数组
    int vertexNum,edgeNum;//图的顶点和边数
}
构造函数——图的建立
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename DataType>
MGraph<DataType>::MGraph(DataType a[],int n,int e){
    int i,j,k;
    vertexNum=n;edgeNum=e;
    for(i=0;i<vertexNum;i++)
        vertex[i]=a[i];//存储顶点
    for(i=0;i<vertexNum;i++)//初始化矩阵
        for(j=0;j<vertexNum;j++)
            edge[i][j]=0;
    for(k=0;k<edgeNum;k++){
        cin>>i>>j;//输入边依附两个顶点的编号
        edge[i][j]=edge[j][i];//置有边标志
    }
}
深度优先遍历

递归栈；按行访问

1
2
3
4
5
6
7
template <typename DataType>
void MGraph<DataType>::DFTraverse(int v){
    cout<<vertex[v]<<" ";
    visited[v]=1;//一个全局遍历，访问置为1
    for(int j=0;j<vertexNum;j++)
        if(vertex[v][j]==1&&visited[j]==0) DFTraver(j);//满足条件：邻接同时未访问过
}
广度优先遍历

队列；font指向队头元素的前一个位置，rear指向队尾元素的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename DataType>
void MGraph<DataType>::BFTraverse(int v){
    int w;//记录出队
    int j;//序号
    int Q[MaxSize];//队列
    int front=-1,rear=-1;//初始化队列
    cout<<vertex[v];visited[v]=1;//记录已访问
    Q[++rear]=v;//被访问顶点入队
    while(font!=rear){//当队列非空
        w=Q[++font];//将队头元素出队
        for(j=0;j<vertexNum;j++)
            if(eage[w][j]==1&&visited[j]==0){
                Q[++rear]=j;//入队
                cout<<vertex[j]<<" ";
                visited[j]=1;//访问过，记录
            }
    }
}

邻接表

如果采用邻接矩阵存储稀疏图，会出现什么情况？–>稀疏矩阵

image-20221217170424730

边表中的结点表示什么？–>对应图中的一条边(边表)

设图有n个顶点e条边，邻接表的空间复杂度是：O(n+e)

基础准备：

1
2
3
4
5
6
7
8
9
struct EdgeNode{//定义边表结点。一个结点！
    int adjvex;//邻接点域
    EdgeNode * next;
}
template <typename DataType>
struct VertexNode{//定义顶点表结点
	DataType vertex;
    EdgeNode * firstEdge;
};

实现

1
2
3
4
5
6
7
8
const int MaxSize=10;
template <typename DataType>
class ALGraph{
    ...
private:
    VertexNode<DataType> adjlist[MaxSize];//存放顶点表的数组
    int vertexNum,edgeNum;//图的顶点数和边数
}
构造函数——图的建立

头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename DataType>
ALGraph<DataType>::ALGraph(DataType a[],int n,int e){
    int i,j,k;
    EdgeNode * s=nullptr;
    vertexNum=n;
    edgeNum=e;
    for(i=0;i<vertexNum;i++){//输入顶点信息，初始化顶点表
        adjlist[i].vertex=a[i];
        adjlist[i].firstEdge=nullptr;
    }
    for(k=0;k<edgeNum;k++){
        cin>>i>>j;//输入边依附的两个顶点的编号
        s=new EdgeNode;
        s->adjvex=j;
        s->next=adjlist[i].firstEdge;//头插法
        adjlist[i].firstEdge=s;//类似头指针，要指向第一个
    }
}
广度优先遍历算法

队列，链表，外层是队列判空，内层是工作指针判空

不能理解为把边表一条一条输出，广度有限有顺序规律的，还是要用队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <typename DataType>
void ALGraph<DataType>::BFTraverse(int v){
    int w;//存出队元素
    int j,Q[MaxSize];//顺序队列
    int font=-1,rear=-1;//初始化队列
    EdgeNode * p=nullptr;//工作指针
    cout<<adjlist[v].vertex;visit[v]=1;
    Q[++rear]=v;//入队
    while(font!=rear){//当队列非空
    	w=Q[++rear];
        p=adjlist[w].firstEdge;//工作指针p指向顶点v的边表
        while(p!=nullptr){
            j=p->adjvex;
            if(visit[j]==0){
                cout<<adjlist[j].vertex;
                visited[j]=1;
                Q[++rear]=j;
            }
            p=p->next;
        }
    }
}

最小生成树

生成树：连通图的生成树是包含全部顶点的一个极小连通子图

生成树的代价：在无向连通网中，生成树上各边的权值之和

最小生成树：在无向连通网中，代价最小的生成树

Prim算法

重复指向操作：在所有$i∈U$、$j∈V-U$的边中找一条代价最小的边$(i,j)$并入集合$TE$，同时$J$并入$U$，直至$U=V$为止，此时TE中有$n-1$条边，$T$是一棵最小生成树。

在已存在生成树集合中所有顶点找集合外边的边，取代价最小的那一条，把对应的那个点加入到生成树集合中，直到所有顶点都加入

“把团队成员之外最容易拉到的入伙”

算法：Prim
输入：无向连通网G=(V，E)
输出：最小生成树T=(U，TE)

  1. 初始化：U = {v}； TE={ }；
  2. 重复下述操作直到U = V：
    2.1 在E中寻找最短边(i，j)，且满足i∈U，j∈V-U；
    2.2 U = U + {j}；
    2.3 TE = TE + {(i，j)}；

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Prim(int v){
    int i,j,k;
    int adjvex[MaxSize];//记录每个成员最短边的邻接点
    int lowcost[MaxSize];//记录到所有顶点的最短值
    for(i=0;i<vertexNum;i++){//初始化辅助数组
        lowcost[i]=edge[v][i];
        adjvex[i]=v;//邻接
    }
    lowcost[v]=0;//已经在团队里的点置为0
    for(k=1;k<vertexNum;k++){//迭代n-1
    	j=MinEdge(lowcost,vertexNum);//这一步就是找到团队外的最短边，即找数组的最小值，注意判0
        cout<<"("<<j<<","<<adjvex[j]<<")"<<lowcost[i]<<endl;
        lowcost[j]=0;//将顶点j加入集合U
        for(i=0;i<vertexNum;i++)
            if(edge[i][j]<lowcost[i]){
                lowcost[i]=edge[i][j];
                adjvex[i]=j;//根据新加入的来更新最短的
            }
    }
}

完整代码：

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
34
35
36
int MinEdge(int lowcost[],int num){
	int min=100;
    int minNum;
	for(int i=0;i<num;i++){
		if(lowcost[i]!=0&&lowcost[i]<min){
            min=lowcost[i];
            minNum=i;   
        }
			
	}
	return minNum;
}

void Prim(int v){
	int i,j,k;
	int adjvex[MaxSize],lowcost[MaxSize];
	for(i=0;i<vertexNum;i++){
		lowcost[i]=arc[v][i];
        //在初始化的过程中对于不可达的点如果不做操作，默认是0，这里的0值就有了两种意义，一种表示是自己到自己，一种是不可达，注意区分
        if(lowcost[i]==0&&i!=v)
            lowcost[i]=10000;//记为无穷大
		adjvex[i]=v;
	}
	lowcost[v]=0;
	for(k=1;k<vertexNum;k++){
		j=MinEdge(lowcost,vertexNum);//寻找最短边的邻接点j
		cout<<j<<adjvex[j]<<lowcost[j]<<endl;
		lowcost[j]=0;
		for(i=0;i<vertexNum;i++){
			if(arc[i][j]<lowcost[i]&&arc[i][j]!=0){//说明是不可达的点，此时要判断
				lowcost[i]=arc[i][j];
				adjvex[i]=j; 
			}
		} 
	}
}
  1. 首先将adjvex全置为v，lowcost[i]表示编号为i的点到v的距离，不可达为正无穷。
  2. 然后遍历lowcost找到最小的（不包含0，0表示本身），当找到编号j到v的距离最小，那么把编号j的点到其他点的距离和lowcost比较，如果对应的值要小，那么更新lowcost对应值，同时将adjvex改为j。例如设v=0，第一轮lowcost[5]是最小的为19（表示编号v到编号5的权值是目前v到所有的邻接点中最小的），那么看邻接矩阵第五列（邻接矩阵的第五列从上到下表示编号5到编号0、编号5到编号1…的权值）从上到下对应的与lowcost的比较，如邻接[1][5]和lowcost[1]比，邻接[2][5]和lowcost[2]比等等，更新lowcost和adjvex）
  3. 重复步骤2vertexNum-1次

是一种贪心策略。

image.png

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//图完整代码，包含BFD、DFS、Prim，注意默认是6个顶点9条边，且顶点从0-6
#include <iostream>
using namespace std;

const int MaxSize = 10;           //图中最多顶点个数
int visited[MaxSize]={0};

struct element
{
	int lowcost, adjvex;
};
int MinEdge(int lowcost[],int num){
	int min=100;
	int minNum; 
	for(int i=0;i<num;i++){
		if(lowcost[i]!=0&&lowcost[i]<min){
			min=lowcost[i];
			minNum=i; 
		}
			
	}
	return minNum;
}
template <class DataType>
class MGraph
{
public:
	MGraph(DataType a[ ], int n, int e);    //构造函数，建立具有n个顶点e条边的图
	~MGraph( ) { }                     //析构函数为空
	void DFSTraverse(int v);              //深度优先遍历图
	void BFSTraverse(int v);               //广度优先遍历图
	template <class T>
	friend void Prim(MGraph<T> mg);
private:
    DataType vertex[MaxSize];          //存放图中顶点的数组
    int arc[MaxSize][MaxSize];          //存放图中边的数组
    int vertexNum, arcNum;             //图的顶点数和边数
};

template <class DataType>
MGraph<DataType>::MGraph(DataType a[ ], int n, int e)
{
	int i, j, w=0;
	vertexNum=n; arcNum=e;
	for (i=0; i<vertexNum; i++)
		vertex[i]=a[i];
	for (i=0; i<vertexNum; i++)
        for (j=0; j<vertexNum; j++)
			arc[i][j]=0;
		for (int k=0; k<arcNum; k++)
		{
			cout<<"请输入边的两个顶点的序号：";
			cin>>i;
			cin>>j;
			cout<<"请输入边的权值：";
			cin>>w;
			arc[i][j]=w; arc[j][i]=w;	
		}
}

template <class DataType>
void MGraph<DataType>::DFSTraverse(int v)
{
	cout << vertex[v]; visited[v] = 1;
	for (int j = 0; j < vertexNum; j++)
		if (arc[v][j] >=1  && visited[j]==0) 
			DFSTraverse(j);
}

template <class DataType>
void MGraph<DataType>::BFSTraverse(int v)
{
	int Q[MaxSize];
	int front = -1, rear = -1;   //初始化队列,假设队列采用顺序存储且不会发生溢出
	cout << vertex[v]; visited[v] = 1;  Q[++rear] = v;   //被访问顶点入队
	while (front != rear)                   //当队列非空时
	{
		v = Q[++front];                   //将队头元素出队并送到v中
		for (int j = 0; j < vertexNum; j++)
			if (arc[v][j]  >=1 && visited[j] == 0 ) {
				cout << vertex[j]; 
				visited[j] = 1; 
				Q[++rear] = j;
			}
	}
}
template <class DataType>
void Prim(MGraph<DataType> mg){
	int i,j,k;
	int adjvex[MaxSize],lowcost[MaxSize];
	int v=0;
	int vertexNum=mg.vertexNum;
	for(i=0;i<vertexNum;i++){
		lowcost[i]=mg.arc[v][i];
		if(lowcost[i]==0&&i!=v)
            lowcost[i]=10000;//记为无穷大
		adjvex[i]=v;
	}
	lowcost[v]=0;
	for(k=1;k<vertexNum;k++){
		j=MinEdge(lowcost,mg.vertexNum);//寻找最短边的邻接点j
		cout<<"("<<j<<","<<adjvex[j]<<")"<<lowcost[j]<<endl;
		lowcost[j]=0;
		for(i=0;i<vertexNum;i++){
			if(mg.arc[i][j]<lowcost[i]&&mg.arc[i][j]!=0){
				lowcost[i]=mg.arc[i][j];
				adjvex[i]=j; 
			}
		} 
	}
} 
int main()
{
	char ch[]={'A','B','C','D','E','F'};
	MGraph<char> MG(ch, 6, 9);
	for (int i=0; i<MaxSize; i++)
		visited[i]=0;
	cout<<"深度优先遍历序列是：";
	MG.DFSTraverse(0);
	cout<<endl;
	for (int i=0; i<MaxSize; i++)
		visited[i]=0;
    cout<<"广度优先遍历序列是：";
	MG.BFSTraverse(0);
	cout<<endl;
    cout<<"最小生成树的生成过程为："<<endl;
    Prim(MG);
	cout<<endl;
    system("pause");
    return 0;
}

Kruskal算法

按边的权值排序

初始所有顶点都在集合里，找最短的边加进来，加之前判断是否形成环，是则舍弃选取下一个，直到集合所有顶点都在统一连通分量上(都连通，n-1条边)

最小生成树可能不唯一，比如当有相同的权值边又不至形成环的时候，就可能构造出不同的最小生成树

两种算法比较

算法名 普利姆算法 克鲁斯卡尔算法
算法思想 选择点 选择边
时间复杂度 O(n2) n为顶点数 O(eloge) (e为边数)
适应范围 稠密图 (边多) 稀疏图 (边少)

时间复杂度：普利姆算法每一个顶点都要找其他顶点判断；克鲁斯卡尔选择边，与顶点数无关，边排序

最短路径

Dijkstra算法

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
//图 DFS BFS Dijkstra 完整代码
#include <iostream>
using namespace std;

#include<string>

const int MaxSize = 10;           //图中最多顶点个数
int visited[MaxSize]={0};

struct element
{
	int lowcost, adjvex;
};
int Min(int dist[],int ver){
	int min=255,minNum=0;
	for(int i=0;i<ver;i++){
		if(dist[i]<min&&dist[i]>0){
			min=dist[i];
			minNum=i;
		}
	}
	return minNum;
}
template <class DataType>
class MGraph
{
public:
	MGraph(DataType a[ ], int n, int e);    //构造函数，建立具有n个顶点e条边的图
	~MGraph( ) { }                     //析构函数为空
	void DFSTraverse(int v);              //深度优先遍历图
	void BFSTraverse(int v);               //广度优先遍历图
	template <class T>
	friend void Dijkstra(MGraph<T> MG,int v);
private:
    DataType vertex[MaxSize];          //存放图中顶点的数组
    int arc[MaxSize][MaxSize];          //存放图中边的数组
    int vertexNum, arcNum;             //图的顶点数和边数
};

template <class DataType>
MGraph<DataType>::MGraph(DataType a[ ], int n, int e)
{
	int i, j, w=0;
	vertexNum=n; arcNum=e;
	for (i=0; i<vertexNum; i++)
		vertex[i]=a[i];
	for (i=0; i<vertexNum; i++)
        for (j=0; j<vertexNum; j++)
			arc[i][j]=255; // 假设极大值为255，表示两个顶点不邻接
		for (int k=0; k<arcNum; k++)
		{
			cout<<"请输入边的两个顶点的序号：";
			cin>>i;
			cin>>j;
//			arc[i][j]=1; arc[j][i]=1;	
			cout<<"请输入边的权值：";
			cin>>w;
			arc[i][j]=w; 
			arc[j][i]=w;	
		}
}

template <class DataType>
void MGraph<DataType>::DFSTraverse(int v)
{
	cout << vertex[v]; visited[v] = 1;
	for (int j = 0; j < vertexNum; j++)
		if (arc[v][j] <255  && visited[j]==0) 
			DFSTraverse(j);
}

template <class DataType>
void MGraph<DataType>::BFSTraverse(int v)
{
	int Q[MaxSize];
	int front = -1, rear = -1;   //初始化队列,假设队列采用顺序存储且不会发生溢出
	cout << vertex[v]; visited[v] = 1;  Q[++rear] = v;   //被访问顶点入队
	while (front != rear)                   //当队列非空时
	{
		v = Q[++front];                   //将队头元素出队并送到v中
		for (int j = 0; j < vertexNum; j++)
			if (arc[v][j] <255  && visited[j] == 0 ) {
				cout << vertex[j]; 
				visited[j] = 1; 
				Q[++rear] = j;
			}
	}
}
template <class DataType>
void Dijkstra(MGraph<DataType> MG,int v){
	int i,k,num,dist[MaxSize];
	string path[MaxSize];
	for(int i=0;i<MG.vertexNum;i++){
		dist[i]=MG.arc[v][i];
		if(dist[i]!=255){
			// path[i]=MG.vertex[v]+MG.vertex[i] char直接赋值给string这是不行的
			path[i].push_back(MG.vertex[v]);//要用push_back
			path[i].push_back(MG.vertex[i]);
		}	
		else path[i]="";
		cout<<"|"<<i<<" "<<path[i]<<"|"<<" ";
	}
	cout<<endl;
	for(num=1;num<MG.vertexNum;num++){
		k=Min(dist,MG.vertexNum);
		cout<<"path"<<k<<" "<<path[k]<<","<<dist[k]<<";";
		for(i=0;i<MG.vertexNum;i++){
			if(dist[i]>dist[k]+MG.arc[k][i]&&i!=v){//i!=v不做到达初始点的判断
			dist[i]=dist[k]+MG.arc[k][i];
			path[i]=path[k]+MG.vertex[i];
		}
		}	
		dist[k]=0;
		cout<<endl;
	}
}
int main()
{
	char ch[]={'A','B','C','D','E'};
	MGraph<char> MG(ch, 5, 7);
	for (int i=0; i<MaxSize; i++)
		visited[i]=0;
	cout<<"深度优先遍历序列是：";
	MG.DFSTraverse(0);
	cout<<endl;
	for (int i=0; i<MaxSize; i++)
		visited[i]=0;
    cout<<"广度优先遍历序列是：";
	MG.BFSTraverse(0);
	cout<<endl;
    cout<<"从顶点"<<ch[0]<<"到各终点的最短路径分别是："<<endl;
    Dijkstra(MG,0);
	cout<<endl;
    system("pause");
    return 0;
}

有向无环图及其应用

概念

AOV网（顶点表示活动的网）：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系

AOV网中出现回路意味着活动之间的优先关系是矛盾的

拓扑序列：顶点序列包含所有的点，要满足当且仅当有向图中a到b有一条路径，在顶点序列中a必在b之前。

得AOV网中所有应该存在的前驱和后继关系都能得到满足；拓扑序列不唯一；意义：工程中各个活动必须按照拓扑序列中的顺序进行才是可行的

拓扑排序：对一个有向图构造拓扑序列的过程

image-20221218195618867

这里注意，拓扑序列需要满足当a到b存在路径时a得在b之前即可，不需要序列所有前边的到后边的都得有路径，如这里v0到v1就没有。是一个充分条件

拓扑排序实现

  • 图：带入度的邻接图
  • 栈：入度为0的顶点入栈

算法：TopSort
输入：有向图G=(V，E)
输出：拓扑序列

  1. 栈 S 初始化；累加器 count 初始化；
  2. 扫描顶点表，将入度为 0 的顶点压栈；
    1. 当栈 S 非空时循环
      3.1 j = 栈顶元素出栈；输出顶点 j；count++；
      3.2 对顶点 j 的每一个邻接点 k 执行下述操作(扫描链表)：
      3.2.1 将顶点 k 的入度减 1；
      3.2.2 如果顶点 k 的入度为 0，则将顶点 k 入栈；
    2. if (count<vertexNum) 输出有回路信息；
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
//结点结构
template <class DataType>
struct VertexNode
{
     int in;//邻接表增加入度域，方便对入度的操作
     DataType vertex;//存顶点
     EdgeNode *firstEdge;
};
void ALGraph<DataType>::TopSort(){
    int i,j;
    int k;//存放邻接点编号
    int count=0;//累加器，最后判断是否成环
    int S[MaxSize],top=-1;//采用顺序栈并初始化
    EdgeNode *p=nullptr;//工作指针
    for(i=0;i<vertexNum;i++)//扫描顶点表
        if(adjlist[i].in==0) S[++top]=i;//将入度为0的顶点压栈
    while(top!=-1){//栈不空
        j=S[top--];//入度为0出栈
        cout<<adjlist[j].vertex;
        count++;
        p=adjlist[j].firstEdge;//工作指针初始化
        while(p!=nullptr){
            k=p->adjvex;//为编号
            adjlist[k].in--;//邻接点入度都-1
            if(adjlist[k].in==0) S[top++]=k;//入读为0的顶点入栈
            p=p->next;//后移
        }
        if(count<vertexNum) cout<<"有回路";//拓扑排序一定是有所有点的
    }
}

如果满足拓扑序列，那么不用担心已出栈的会重复进栈，假设重复进栈，那么就会形成环。

时间复杂度O(n+e)

关键路径

AOE网（边表示活动的网）：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间

AOE网的性质(存在的约束条件)：

  • 只有在进入某顶点的各活动都已经结束，该顶点所代表的事件才能发生
  • 只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始

注意活动是可以同时进行的！

最晚开始时间-最早开始时间就是时间余量，在时间余量做不相干的事也不影响工程进度

关键路径：AOE网中从源点到终点的最长路径。**(也可能不唯一)**

关键活动：关键路径上的活动，即时间余量为0的活动

不按期完成关键活动就会影响整个工程的进度，换言之，要缩短整个工期，必须加快关键活动的进度；

为什么是最长呢？因为最长的都完成了，其他的也肯定完成了，整项工程也就完成了

  • 如何求关键路径呢？–>求关键活动
  • 如何求关键活动呢？关键活动为什么是关键的？关键活动的开始时间不能推迟–>其最早开始时间和最晚开始时间相等

事件(顶点)的最早和最迟

如何求ve(j)和vl(j)？

  1. 最早发生时间从ve(1)=0开始向后递推，相当于找到这个事件的最长路径
  2. 最迟发生时间从vl(n)=ve(n)开始向前递推

image-20221223153541781

最早发生时间从前往后推，完成后可以立马开始的那一条。例如左图中Vu到Vj完成了但是下边的还没有完成，Vj不能开始，而当最长的Vx到Vj完成了前面肯定都完成了，可以开始Vj因此最早为88。前边加求最大

最迟发生时间从后往前推，必须开始的时间，晚于这个时间就不能按时完成后边的.如右图，顶点上的数为各事件的最晚发生时间，减去前边活动天数就是允许拖延的事件。Vx的5-2最小为3，说明只允许拖三天就必须要开始了，再晚点开始耗费两天的话就超过Vx的最迟发生时间了，因此Vj最迟时间为3。后边减求最小

活动(边)的最早和最迟

最早发生时间等于弧尾事件的最早发生时间

最迟发生时间等于弧头事件的最晚发生时间减去这条弧的长度

问题

  1. n个顶点的无向图，采用邻接表存储：

统计出度为0的顶点个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int SunZero(MGraph mg){
	int count;//统计有多少个
	for(int i=0;i<mg.vertexNum;i++){
		int tag=0;//标记 
		for(int j=0;i<mg.vertexNum;j++){
			if(edge[i][j]!=0){
				tag=1;
				break;
			}
			
		} 
		if(tag==0) count++;
	} 
	return count;
}

查找技术

关键码：可以标识一个记录的某个数据项

如何评价查找算法的效率呢？：和关键码的比较次数

平均查找长度：查找算法进行的关键码比较次数的数学期望值

线性表的查找技术

顺序查找(线性查找)

思想：从表的一端到另一端，逐个比较

以下代码默认待查表索引0处不存值。

1
2
3
4
5
6
int SeqSearch(int r[],int n,int k){
    int i=n;
    while(i>0&&r[i]!=k)
        i--;
    return i;//若没查到返回值是0
}

从后往前，注意判断是否越界

改进版：尽头设置哨兵，免去判越界

1
2
3
4
5
6
7
int LineSearch::SeqSearch2(int k){
    int i=n;
    data[0]=k;//设置哨兵
    while(data[i]!=k)//免去判越界
        i--;
    return i;//同样查不到返回的是0
}
算法 顺序查找
优点 算法简单、使用面广。对存储(线或链)、有序性无要求
缺点 查找效率低，特别是元素多的时候

折半查找(对半查找、二分查找)

思想：如其名

先排好序！

非递归

1
2
3
4
5
6
7
8
9
10
int LineSearch::BinSearch1(int k){
    int mid,low=1,high=n;//1开始记录的
    while(low<=high){//如果没找到，low会超过high，结束循环
        mid=(high+low)/2;
        if(k<data[mid]) high=mid-1;
        else if(k>data[mid]) low=mid+1;
        else return mid;//查找成功，返回元素序号
    }
    return 0;//查找失败，返回0
}

递归

1
2
3
4
5
6
7
8
9
10
int LineSearch::BinSearch2(int low,int high,int k){
    int mid;
    if(low>high) return 0;//递归的边界条件
    else{
        mid=(low+high)/2;
        if(k>data[mid]) BinSearch2(mid+1,high,k);
        else if(k<data[mid]) BinSearch2(low,mid-1,k);
        else return mid;//查找成功返回序号
    }
}

树表的查找技术

二叉排序树

定义

  • 一棵空的二叉树
  • 或者满足：
    • 若它的左子树不空，则左子树上所有结点的值均小于根结点的值
    • 若它的右子树不空，则右子树上所有结点的值均小于根结点的值
    • 它的左右子树都是而二叉排序树

二叉排序树的中序序列即是升序序列

存储：二叉链表

二叉树排序树的实现

1
2
3
4
5
6
7
8
9
class BiSortTree{
public:
    ...
private:
    BiNode<int> *InsertBST(BiNode<int> *bt , int x); 
    BiNode<int> *SearchBST(BiNode<int> *bt, int k);   
    void Release(BiNode<DataType> *bt);     
    BiNode<int> *root;    
}
查找
  • 找不到的情况
  • 找到的情况
  • 比当前小的情况
  • 比当前大的情况
1
2
3
4
5
6
BiNode<int> * BiSortTree::SearchBST(BiNode<int>* bt,int k){//k是查找值
    if(bt==nullptr) return nullptr;
    if(bt->data==k) return bt;//找到了
    if(bt>data>k) return SearchBST(bt->lchild,k);//大于查找值，查左树
    else return SearchBST(bt->rchild,k);//小于查找值，查右s
}
插入

思路：

  • 若二叉排序树为空树，则新插入的结点为新的根结点；
  • 否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。
  • 比当前结点小，则插入它的左子树；否则插入右子树

核心：

  • 递归
  • 链表插入结点
1
2
3
4
5
6
7
8
9
10
11
BiNode<int>* BiSortTree::InsertBST(BiNode<int> *bt,int x){
    if(bt==nullptr){
        //为空插入
        BiNode<int> *s=new BiNode<int>;
        s->data=x;
        s->lchild=s->rchild=nullptr;
        bt=s;//新结点上树
        return bt;
    }else if(bt->data>x) bt->lchild=InsertBST(bt->lchild,x);
    else bt->rchild=InsertBST(bt->rchild,x);//注意这里不是单纯的递归函数就可以了，需要赋值的，因为会插入结点改变树
}

注意有返回值，返回值为新结点，赋值给传入树的左/右子树

构造

建立在插入的基础上

（1）每次插入的新结点都是二叉排序树上新的叶子结点;
（2）找到插入位置后，不必移动其它结点，仅需修改某个结点的指针；
（3）在左子树/右子树的查找过程与在整棵树上查找过程相同；
（4）新插入的结点没有破坏原有结点之间的关系。

1
2
3
4
5
BiSortTree::BiSortTree(int a[],int n){
    root=nullptr;
    for(int i=0;i<n;i++)
        root=InsertBST(root,a[i]);
}
删除
  • 删除后仍要保持二叉排序树的特性
  • 当删除分支节点就破坏了原有的链接关系，需要重新修改指针

分三种情况：

  1. 被删除的结点是叶子结点

    则将它的双亲结点相应的指针域值置为空，比如p是f的左孩子，现在删除p则f->lchild=nullptr;

  2. 被删除的结点只有左子树或者只有右子树

    把删除结点的左(右)子树代替它的位置即可，比如p是f的左孩子，而p不是叶子，它有右子树，这是删除p，则f->lchile=p->rchild

    这里不管是怎么样，有左子树还是右子树，都是代替它的位置，因为由性质可知左子树所有元素都小于根节点，右子树都大于它，因此代替后不会影响它的有序性

  3. 被删除的结点既有左子树，又有右子树

    分两种情况：当p是f的左孩子，删p时则以f的左子树中的最大值结点替换之，最大值就在左子树的最右下；当p是f的有孩子，则以f右子树的最小值替换它，在最左下

    这样保证了我的左子树都小于我，右子树都大于我，因此选左边的最大或右边的最小

    注意特殊情况，当最大/最小就是被删除结点的孩子时

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
//注意，下面默认p是f的左孩子，右孩子同理不失一般性，但是要另写
template <typename DataType>
void BiSortTree::DeleteBST(BiNode<int> *p,BiNode<int> *f){
    if((p->lchild==nullptr)&&(p-rchild==nullptr)){
        //p为叶子
        f->lchild=NULL;//先置为空
        delete p;//再删除
        return;
    }
    if(p->rchild==nullptr){
        //p只有左子树
        f->lchild=p->lchild;
        delete p;
        returnl
    }
    if(p->lchild==nullptr){
        //p只有右子树
        f->lchild=p->rchild;
        delete p;
        return;
    }
    //找左子树最大的，找最右下
    BiNode<int> *par=p,*s=p->lchild;
    while(s->rchild!=nullptr){
        par=s;//工作指针
        s=s->rchild;
    }
    p->data=s->data;//修改值
    if(par==p) par->rchild=s->lchild;
    else par->lchild=s->lchild;//挂到par
    delete s;
}
给定结点的深度
1
2
3
4
5
6
void Level(BiNode *root,BiNode *p){
    if(root==nullptr) return 0;
    if(p==root) return 1;
    else if(p->data<root->data) return Level(root->lchild,p)+1;//每递归一次说明多了一层
    else return Level(root->rchild,p)+1;
}

平均查找长度

查找成功的平均查找长度为：∑（本层高度*本层元素个数）/节点总数

查找不成功的平均查找长度：∑（本层高度*本层补上的叶子个数）/补上的叶子总数

平衡二叉树

  • 平衡因子：该结点的左子树的深度减去右子树的深度
  • 平衡二叉树：
    • 一棵空的二叉排序树，或者同时满足：
    • 根结点的左子树和右子树的深度最多相差1
    • 根结点的左子树和右子树都是平衡二叉树

插入一个结点会影响哪些结点的平衡因子？

  • 最小不平衡子树：以距离插入结点最近的、且平衡因子的绝对值大于 1 的结点为根的子树

且入且判断，一旦失衡立即调整；只调整最小不平衡子树，并且不影响其他结点；充分利用二叉排序树的性质来作调整

LL型

  • B结点带左子树一起上升
  • A成为B的右孩子(因为A大于B)
  • B结点原来的右子树作为A的左子树

image-20221220165706645

RR型

  • B结点带右子树一起上升

  • A结点成为B的左孩子

  • 原来B的左子树做A的右子树

image-20221220165423429

LR型

  • C结点穿过A、B结点上升
  • B结点成为C的左孩子，A结点成为C的右孩子(因为B是小于C的，而A是大于C的)
  • 原来C结点的左子树作为B的右子树，C结点的右子树作为A的左子树

image-20221220164736781

RL型

image-20221220165952142

一个原则，上升后根据二叉排序树的性质进行调整

散列表的查找技术

  • 散列表：采用散列技术存储查找集合的连续存储空间。

  • 散列函数：将关键码映射为散列表中适当存储位置的函数

  • 散列地址：由散列函数所得的存储地址

  • 散列函数的设计：

    • 计算简单。不应太大计算量，降低茶轴效率
    • 函数值(即散列地址)分布均匀，相同概率散列到散列表中，减少冲突

    两个方面是矛盾的，根据具体情况选择一个合理的方案

image-20221220171726174

常见的散列函数

散列函数 直接定址法 平方取中法 除留余数法
形式 H(key)=a×key+b 对关键码平方后，按散列表大小，取中间的若干位作为散列地址。 H(key)=key mod p
例子 关键码集合为{10, 30, 50, 70, 80, 90}，选取的散列函数为H(key)=key/10，则10存在下标为1，30在2… 要求散列地址为 2 位，则(1234)2＝1522756，(1235)2＝1525225，分别取27，52 散列表长为15，设计H(key)= key mod 13
适用 事先知道关键码，关键码集合不是很大且连续性较好 事先不知道关键码的分布且关键码的位数不是很大 最简单、最常用，不要求事先知道关键码的分布

以下关于哈希查找的叙述中错误的是（A ）。

A. 用拉链法解决冲突易引起堆积现象

B. 用线性探测法解决冲突易引起堆积现象

C. 哈希函数选得好可以减少冲突现象

D. 哈希函数H(k)=k MOD p，p通常取小于等于表长的素数

处理冲突的方法

开放寻址法

  • 闭散列表：用开放定址法处理冲突得到的散列表

原理：

1）计算散列地址：j = H(key)

2）如果地址 j 的存储单元没有存储记录，则存储key对应的记录；

3）如果在地址 j 发生冲突，则寻找一个空的散列地址，存储key对应的记录；

如何寻找一个空的散列地址？

  • 线性探测法
  • 二次探测法
  • 随机探测法等
线性探测法

当发生冲突时，寻找空散列表地址的公式为：Hi=(H(key)＋di) % m （di=1，2，…，m-1)

这个di是设定的，比如设定为1，那么当冲突时就往后试探一位，再冲突再试探，直到有空位

堆积：非同义词对同一个散列地址争夺的现象

算法：Search
输入：闭散列表ht[ ]，待查值k
输出：如果查找成功，则返回记录的存储位置，否则返回查找失败的标志-1
1. 计算散列地址 j；
2. 探测下标i初始化：i = j；
1. 执行下述操作，直到 ht[i] 为空：
2.3.1 若 ht[i] 等于 k，则查找成功，返回记录在散列表中的下标；
3.2 否则，i 指向下一单元；
4. 查找失败，返回失败标志-1；

1
2
3
4
5
6
7
8
9
int HashTabel::Search(int k){
    int i,j=H(k);//计算散列地址
    i=j;//设置比较的起始位置
    while(ht[i]!=0){
        if(ht[i]==k) return i;//查找成功
        else i=(i+1)%m;//向后探测一个位置
    }
    return -1;//查找失败
}
二次探测法

以冲突位置为中心，跳跃式寻找空的散列地址。

Hi=(H(key)＋di) % m （di = 12,-12,,22,,-22,,… , q2,,-q2,(q≤m/2)）

拉链法

开散列表：用拉链法处理冲突得到的散列表

同义词子表：所有散列地址相同的记录构成的单链表。(拉链一样链起来)

对于给定的关键码key执行下述操作：

（1）计算散列地址：j = H(key)

（2）将key对应的记录插入(头插法)到同义词子表 j 中；

1
2
3
4
5
6
7
8
9
10
11
12
13
//用拉链法处理冲突，散列表的构造过程如下
j=H(k);
Node<int> *p=ht[i];
while(p!=nullptr){
    if(p->data==k) break;
    else p=p->next;
}
if(p==null){
    q=new Node<int>;
    q->data=k;
    q->next=ht[j];
    ht[j]=q;
}

image-20221220195949858

排序技术

  • 稳定性：原序列中，a=b且a在b之前，排序后a仍在b之前，称排序算法稳定；否则称为不稳定
  • 趟：排序过程中，将待排序的记录序列扫描一遍称为一趟

插入排序

直接插入排序

代码

1
2
3
4
5
6
7
8
9
10
void Sort::InsertSort(){
    int i,j,temp;
    for(i=1;i<length;i++){//⭐排序进行length-1趟
        temp=data[i];//暂存每一轮的目标记录
        for(j=i-1;j>=0&&temp<data[j];j--){
            data[j+1]=data[j];
        }
        data[j+1]=temp;//每一轮退出上述循环时，j会--，即只有j+1个位置是空的，故插入位置为j+1
    }
}

情况分析

最好情况：

  • 待排序序列都是正序。
  • 每趟只需与有序序列最后一个记录比较一次，移动两次记录。

比较次数：$n-1$ ，移动次数：$2(n-1)$

最坏情况：

  • 待排序记录为逆序
  • 第i个记录要和前面i-1个记录比较，每次执行一次移动

比较次数：$\frac{n(n-1)}{2}$ ， 移动次数： $\frac{(n+4)(n-1)}{2}$

平均情况：

  • 各种可能
  • 插入第i个记录需要比较有序区中全部记录的一半

比较次数：$\frac{n(n-1)}{4}$， 移动次数：$\frac{(n+4)(n-1)}{4}$

⭐希尔排序

改进点

①当待排序记录基本有序，直接插入排序的效率很高（怎么使得排序记录基本有序）

②直接插入排序简单，在记录个数少时效率也很高（怎么使得排序的记录少）

③让元素跨度大一些以更早地到达最终位置

关键问题

①如何分割待排序记录，使得基本有序:不能是逐段分割，而是将相距某个增量的记录组成一个子序列

②子序列内怎么进行直接插入排序

1
2
3
4
5
6
temp = r[i];  j = i - d; 	
while (j > 0 && temp < data[j]) 
{
    data[j + d] = data[j];  j = j - d;
}
data[j + d] = temp;

image-20221221113526097

代码

1
2
3
4
5
6
7
8
9
10
11
12
void Sort::ShellSort(){
    int i,j,temp;//暂存
    for(d=length/2;d>0;d--){//增量为d进行直接插入排序
        for(i=d;i<length;i++){//进行一趟希尔排序
            temp=data[i];
            for(j=i-d;j>0&&data[j]>temp;j=j-d)//至关重要的
                data[j+d]=data[j];//记录后移d个单位
            data[j+d]=temp;
        }
        
    }
}

一趟希尔排序就是在增量d的情况下把所有子序列都拍好的结果

交换排序

⭐起泡排序

每轮冒出一个最大(小)的

基本思路

  • 两两比较记录，如果反序则交换，直到没有反序的记录为止

关键问题

①在一趟排序中，多个记录位于最终位置时如何记载？

• 用exchange标记每次交换的位置，则最终exchange之后所有记录都是有序

②如何确定有序区的范围

• 用bound记录，每一轮bound等于上一轮最终的exchange

③如何判别起泡排序结束？

• 当exchange为0

④进入循环之前exchange初值为？

• [0-length-1]时，exchange=length-1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Sort::BubbleSort(){
    int j;//位置
    int exchange;//记录每次交换的位置
    int bound;//记录有序区范围
    int temp;//暂存
    exchange=length-1;//先记下范围，后面赋值给bound
    while(exchange!=0){//结束条件exchange=0，全有序了
        bound=exchange;
        exchange=0;
        for(j=0;j<bound;j++)
            if(data[j]>data[j+1]){
                temp=data[j];
                data[j]=data[j+1];
                data[j+1]=temp;
                exchange=j;//记录每次交换的位置
            }
    }
}

⭐快速排序

基本思想

选一个轴值，将待排序记录划分成两部分，左侧记录均小于或等于轴值，右侧记录均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。

关键问题

①如何选择轴值？

  • 多种，最简单选第一个记录

②在待排序序列中如何进行划分

③如何处理划分得到的两个待排序子序列

④如何判别快排结束

  • 对序列进行一次划分，再分别对左右两个子序列进行快排，再对…快排

  • 直到每个分区只有一个记录

image-20221221115949199

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
//一次划分
int Sort::Parttition(int first,int last){
    int i=first;//左侧
    int j=last;//右侧
    int temp;
    while(i<j){
        while(i<j&&data[j]>=data[i]) j--;
        if(i<j){
            temp=data[i];
            data[i]=data[j];
            data[j]=temp;
            i++;//注意这里
        }
        while(i<j&&data[i]<=data[j]) i++;
        if(i<j){
            temp=data[i];
            data[i]=data[j];
            data[j]=temp;
            j--;
        }
    }
    return i;//返回轴值最终位置
}

//递归
void Sort::QuickSort(int first,int last){
    if(first>=last) return;//区间长度为1，递归结束
    else{
        int pivot=Partition(first,last);//一次划分
        QuickSort(first,pivot-1);//左侧快排
        QuickSort(pivot+1,last);//右侧快排
    }
}

选择排序

简单选择排序

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Sort::SelectSort(){
    int index,i,temp;
    for(int i=0;i<length;i++){//进行length-1趟简单选择排序
        index=i;
        for(int j=i+1;j<length){//在无序区中选取最小记录
            if(data[j]<data[index]) index=j;
        }
        if(index!=i){
            temp=data[i];
            data[i]=data[index];
            data[index]=temp;
        }
    }
}

⭐堆排序

堆的实质满是足如下性质的完全二叉树：二叉树中任一非叶子结点均小于(大于)它的孩子结点

大根堆：ki≥k2i且ki≥k2i+1

从最后一个非叶子结点开始调整，即从 n/2开始，n/2-1…到1

堆存储数组是层序遍历形式

堆调整中左孩子是什么表示的$2×i+1$：存储从data[0]开始，所以左孩子是$2×i+1$，右孩子是$2×i+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
29
//堆调整 仅是对一个元素进行调整，堆排序需要反复调用推调整
void Sort::Sift(int k,int last){
    int i,j,temp;
    i=k;//i是被调整结点
    j=2*i+1;//j是i的左孩子
    while(j<=last){
        if(j<last&&data[j+1]>data[j]) j++;//j指向左右孩子的较大者
        if(data[i]>data[j]) break;//说明已经是堆
        else{
            temp=data[j];
            data[j]=data[i];
            data[i]=temp;
            i=j;j=2*i+1;//被调整结点位于结点J的位置
        }
    }
}
//堆排序
void Sort::HeapSort(){
    int i,temp;
    for(i=ceil(length/2)-1;i>=0;i--)
        //从最后一个分支结点(即最后一个非叶子结点)至根结点调整
        Sift(i,length-1);
    for(i=1;i<length;i++){
        temp=data[0];
        data[0]=data[length-1];
        data[length-1]=temp;
        Sift(0,length-i-1);//重建堆
    }
}

当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
//堆排序
//堆调整
void Sift(int k,int r[],int n){
	int i,j,temp;
	i=k;j=2*i;//去+1
	while(j<=n){//还没到叶子
		if(j<n&&r[j]<r[j+1]) j++;//j指向左右孩子的较大者
		if(r[i]>r[j]) break;//已经是堆
		else{
			temp=r[i];
			r[i]=r[j];
			r[j]=temp;
			i=j;j=2*i;//去+1
		} 
	}
} 
void HeapSort(int r[],int n){
	int i,temp;
	for(i=n/2;i>=1;i--)//去eil
	//从最后一个分支结点至根结点调整
		Sift(i,r,n);
	for(i=1;i<n;i++){//1
		temp=r[1];r[1]=r[n-i+1];r[n-i+1]=temp;//n-i+1 1
		Sift(1,r,n-i);//重建堆 1 
	}

各种排序的比较

image-20221209142457790

排序方法 平均情况 最好情况 最坏情况
直接插入排序 O(n2) O(n) O(n2)
希尔排序 O(nlog2n)~O(n2) O(n1.3) O(n2)
起泡排序 O(n2) O(n) O(n2)
快速排序 O(nlog2n) O(nlog2n) O(n2)
简单选择排序 O(n2) O(n2) O(n2)
堆排序 O(nlog2n) O(nlog2n) O(nlog2n)
归并排序 O(nlog2n) O(nlog2n) O(nlog2n)

image-20221221183614599

image-20221209142555586

image-20221209142741177

image-20221209142925247

image-20221209143059040