数据结构笔记
数据结构
第1章 数据结构绪论
1.1 基本概念和术语
数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别并输入给计算机处理的符号集合
数据元素:是组成数据的、有一定意义的基本单位,在计算机中通常作为整体处理.也被称为记录.
数据项:一个数据元素可以由若干个数据项组成
数据项是数据不可分割的最小单位
数据对象:是性质相同的数据元素的集合,是数据的子集
- 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合
1.2 逻辑结构与物理结构
1.2.1 逻辑结构
逻辑结构:是指数据对象中数据元素之间的相互关系
- 1.集合结构:集合结构中的集合元素除了同属于一个集合外,它们之间没有其他关系
- 2.线性结构:线性结构中的数据元素之间是一对一的关系
- 3.树形结构:树形结构中的数据元素存在一种一对多的层次关系
- 4.图形结构:图形结构的数据元素是多对多的关系
1.2.2 物理结构
物理结构:是指数据的逻辑结构在计算机中的存储形式
- 1.顺序存储结构:是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的(数组就是这样的顺序存储结构)
- 2.链式存储结构:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的(因为链式存储结构的数据元素之间没有逻辑关系,因此需要用一个指针存放数据元素的地址,这样通过地址可以找到相关联的数据元素的位置)
1.3 抽象数据类型
1.3.1 数据类型
数据类型:是指一组性质相同的值的集合及定义在此集合上的一些操作的总称
C语言中数据类型可以分两类
- 原子类型:不可以再分解的基本类型,包括int、double、char等
- 结构类型:由若干个原子类型组合而成,是可以再分解的,例如int数组可以分解成若干个int数据、结构体struct可以根据定义情况分解成若干个int、double、char等
抽象是指抽取出事物具有的普遍性的本质
1.3.2 抽象数据类型
- 抽象数据类型(ADT):是指一个数学模型及定义在该模型上的一组操作
- 抽象的意义在于数据类型的数学抽象特性:尽管抽象数据类型在不同计算机,不同编程语言中实现方法上可能不一样,但由于其定义的数学特性相同,我们抽象的看,它们都是相同的
- 抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性
第2章 算法
2.1 算法定义
- 算法:是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作
2.2 算法的特性
算法具有五个基本特性:输入、输出、有穷性、确定性和可行性
2.2.1 输入输出
- 算法具有零个或多个输入
- 算法至少有一个或多个输出
2.2.2 有穷性
- 有穷性:指算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成
2.2.3 确定性
- 确定性:算法的每一步骤都具有确定的含义,不会出现二义性
2.2.4 可行性
- 可行性:算法的每一步都必须是可行的,也就是说,每一步都能够通过执行有限次数完成
2.3 算法设计的要求
好的算法,应该具有正确性、读性、健壮性、高效率和低存储量的特征
2.3.1 正确性
- 正确性:算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案
2.3.2 可读性
- 可读性:算法设计的另一目的是为了便于阅读、理解和交流
2.3.3 健壮性
- 健壮性:当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果
2.3.4 时间效率高和存储量低
- 设计算法应该尽量满足时间效率高和存储量低的需求(最好花最短的时间,用最少的存储空间办成同样的事)
2.4 算法效率的度量方法
2.4.1 事后统计方法
- 事后统计方法:这种方法主要是通过设计好的测试程序和数据,利用计算机计时器对不同算法编制的程序的运行时间进行比较,从而确定算法效率的高低(缺陷大,正常不使用)
2.4.2 事前分析估算方法
- 事前分析估算方法:在计算机程序编制前,依据统计方法对算法进行估算
- 一个程序的运行时间,依赖于算法的好坏和问题的输入规模.所谓问题输入规模是指输入量的多少
- 而最终在分析程序的运行时间时,最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤
2.5 函数的渐近增长
- 函数的渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么,我们说f(n)的增长渐近快于g(n)
- 在估算算法的效率时可以忽略:
- 加法常数
- 与最高次项相乘的常数
- 而最高次项的指数大的,函数随着n的增长,结果也会变得增长特别快
- 在估算算法的效率时可以忽略:
- 判断一个算法的效率时,函数中的常数和其他次要项常常可以忽略,而更应该关注主项(最高阶项)的阶数
- 某个算法,随着n的增大,它会越来越优于另一算法,或者越来越差于另一算法,所以我们可以通过算法时间复杂度来估算算法时间效率
2.6 算法时间复杂度
2.6.1 算法时间复杂度定义
- 算法的时间复杂度:表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度.其中f(n)是问题规模n的某个函数.记作T(n)=O(f(n)). (称之为大O记法)
2.6.2 推导大O阶方法
- 用常数1取代运行时间中的所有加法常数
- 在修改后的运行次数函数中,只保留最高阶项
- 如果最高阶项存在且不是1,则去除与这个项相乘的常数
例如某个算法I的运行时间为2n²+3n+1,则首先保留最高阶项为2n²,由于最高阶项存在且不是1,所以去除与n²相乘的常数2,得到这个算法的时间复杂度为n²
2.6.3 常数阶
- 如果算法的运行时间与问题大小(也即n的多少)无关,则直接记作O(1)(又叫常数阶)
2.6.4 线性阶
int i;
for(i=0;i<n;i++)
{
//时间复杂度为O(1)的程序步骤序列
}
//因此整个循环结构运行次数为n次,即时间复杂度为O(n) - 分析算法的复杂度,关键就是要分析循环结构的运行情况(分析for循环,while循环的判断条件,什么时候退出循环)
2.6.5 对数阶
int count =1; while(count<n) { count=count*2; //时间复杂度为O(1)的程序步骤序列 } //由于每次count乘以2之后,就距离循环退出条件n更近了一分 //由2ᕽ=n得到x=log₂n,因此整个循环的时间复杂度为O(logn)
2.6.6 平方阶
int i,j; for(i=0;i<n;i++) { for(j=0;j<n;j++) { //时间复杂度为O(1)的程序步骤序列 } } /*这是一个循环嵌套的例子,他的内循环在上面已经分析过,时间复杂度为O(n) 而对于外层的循环,不过是内部这个时间复杂度为O(n)的语句再循环n次,所以这段代码的时间复杂度为O(n²)*/int i,j; for(i=0;i<m;i++) { for(j=0;j<n;j++) { //时间复杂度为O(1)的程序步骤序列 } } //如果外循环的循环次数改成m,时间复杂度就变为O(M×N)通过以上两个例子总结,循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数
方法调用同理,只不过是将代码语句封装进了方法中
2.7 常见的时间复杂度
- 常用的时间复杂度所耗费的时间从小到大依次是
O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)
2.8 最坏情况与平均情况
- 平均运行时间是所有情况中最有意义的,因为他是期望的运行时间
- 最坏运行时间是一种保证,那就是运行时间将不会再坏了.在应用中,这是一种最重要的需求,通常,除非特别指定,我们提到的运行时间都是最坏情况的运行时间
- 一般在没有特殊说明的情况下,都是指最坏时间复杂度
2.9 算法空间复杂度
- 算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作S(n)=O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数
第3章 线性表
3.1 线性表的定义
- 线性表(List):零个或多个数据元素的 有限 序列(强调有限和有顺序)
- 若将上图看做线性表,则表中a领先于b,b领先于c,称a是b的直接前驱元素,c是b的直接后继元素.除表头与表尾外,每个元素的直接前驱和直接后继元素有且仅有一个
- 线性表元素的个数n(n≥0)定义为线性表的长度,当n=0时,称为空表
- 在较复杂的线性表中,一个数据元素可以由若干个数据项组成
例
红框部分为一个数据元素,而"张三"为一个数据项
3.2 线性表的抽象数据类型
/* ADT 线性表(List) Data 线性表的数据对象集合为{a₁,a₂,……,aₙ},每个元素的类型均为DataType.其中,除第一个元素a₁外,每一个元素有且只有直接前驱元素,除了最后一个元素aₙ外,每一个元素有且只有一个直接后继元素.数据元素之间的关系是一对一的关系 */ Operation InitList(*L): //初始化操作,建立一个空的线性表L ListEmpty(L): //若线性表为空,返回true,否则返回false ClearList(*L): //将线性表清空。 GetElem(L,i,*e): //将线性表L中的第i个位置元素值返回给e。 LocateElem(L,e): //在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。 ListInsert(*L,i,e): //在线性表L中的第i个位置插入新元素e。 ListDelete(*L,i,*e): //删除线性表L中第i个位置元素，并用e返回其值。 ListLength(L): //返回线性表L的元素个数。 endADT
- 对于实际问题中涉及到的关于线性表的更复杂操作,完全可以用这些基本操作的组合来实现
3.3 线性表的顺序存储结构
3.3.1 顺序存储定义
- 线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素
3.3.2 顺序存储方式
可以利用C语言的一维数组来实现顺序存储结构
#define MAXSIZE 20 //存储空间初始分配量 typedef int ElemType; //ElemType类型根据实际情况而定,这里我们用C语言的typedef关键字,假设ElemType为int typedef struct { ElemType data[MAXSIZE]; //数组存储数据元素,最大值为MAXSIZE int length; //用该变量记录线性表当前长度 }SqList;通过上述代码,可以发现描述顺序存储结构需要三个属性:
- 存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置
- 线性表的最大存储容量:数组长度MaxSize
- 线性表的当前长度:length
我们通过C语言的结构体关键字struct将其构造成一种类型,由上述三个成员组成
3.3.3 数据长度与线性表长度区别
- 数组的长度:是存放线性表的存储空间的长度,存储分配后这个量一般是不变的
- 线性表的长度:是线性表中数据元素的个数,随着线性表插入和删除操作的进行.这个量是变化的
- 在任意时刻,线性表的长度应该小于等于这个数组的长度
3.3.4 地址计算方法
- 系统的存储器中的每个存储单元都有自己的编号,这个编号称为地址
- 假设表中的一个数据元素占用c个存储单元,那么对于第i个数据元素a
i的存储位置可以由a1推算得出: LOC(ai)=LOC(a1)+(i-1)*c,通过这个公式可以随时算出任意位置的地址
例如:一个int数组(int类型占4个字节)下标为0的数据元素的地址为11,则其下标为4的数据元素的地址为11+4*4=27
3.4 顺序存储结构的插入与删除
3.4.1 获得元素操作
直接上C语言代码
#define OK 1 #define ERROR 0 typedef int Status; /*Status是数据结构中抽象出来的函数的类型,其值是函数结果的状态代码,如OK等*/ /*初始条件:顺序线性表L已存在,1≤i≤ListLength(L)*/ /*操作结果:用e返回L中第i个数据元素的值*/ Status GetElem(SqList L,int i,ElemType *e) { if(L.length==0||i<1||i>L.length) //如果该顺序线性表为空表或传入的i值不在正常范围中 return ERROR; *e=L.data[i-1]; return OK; }Status是一个抽象的函数返回值类型,我们在C语言中将其定义为int.程序可以通过Status的返回值来判断算法执行的正确与否,返回OK代表1,ERROR代表0.之后的代码中不再定义
3.4.2 插入操作
- 实现过程如下图
插入算法的思路:
- 如果插入位置不合理,抛出异常;
- 如果线性表长度大于等于数组长度,则抛出异常或动态增加容量;
- 从最后一个元素开始向前遍历到第i个位置,分别将他们都向后移动一个位置;
- 将要插入元素填入位置i处
- 表长加1
代码如下
/*初始条件:顺序线性表L已存在,1≤i≤ListLength(L)*/ /*操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1*/ Status ListInsert(SqList *L,int i,ElemType e) { int k; if(L->length==MAXSIZE) //顺序表满 return ERROR; if(i<1||i<L->length+1) //当i不在范围内时 return ERROR; if(i<=L->length) //若插入数据位置不在表尾 { for(k=L->length-1;k>=i-1;k--) //将要插入的位置后面的数据元素都向后移动一位 L->data[k+1]=L->data[k]; } L->data[i-1]=e; //将新元素插入 L->length++; //表长加1 return OK; }
3.4.3 删除操作
- 实现过程如下图
删除算法的思路:
- 如果删除位置不合理,抛出异常;
- 取出删除元素
- 从删除元素位置开始遍历到最后一个元素位置,分别将他们都向前移动一个位置;
- 表长减1
代码如下
/*初始条件:顺序线性表L已存在,1≤i≤ListLength(L)*/ /*操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1*/ Status ListDelete(SqList *L,int i,ElemType *e) { int k; if(L->length==0) //线性表为空 return ERROR; if(i<1||i>L->length) //删除位置不正确 return ERROR; *e=L->data[i-1]; //将要删除的元素值赋给e if(i<L->length) //如果删除不是最后位置 { for(k=i;i<L->length;k++) //将删除位置后继元素前移 L->data[k-1]=L->data[k]; } L->length--; //表长减1 return OK; }线性表插入和删除的时间复杂度都为O(n)
3.4.5 线性表顺序存储结构的优缺点
- 优点:
- 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
- 可以快速地存取表中任一位置的元素
- 缺点:
- 插入和删除操作需要移动大量元素
- 当线性表长度变化较大时,难以确定存储空间的容量
- 造成存储空间的"碎片"
3.5线性表的链式存储结构
3.5.1 线性表链式存储结构定义
- 为了表示每个数据元素a
i与其直接后继数据元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置).我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域.指针域中存储的信息称作指针或链.这两部分信息组成数据元素ai的存储映像,称为结点
n个结点(a
i的存储映像)链结成一个链表,即为线性表(a1,a2,…,an)的链式存储结构,因为此链表的每个结点中只包含一个指针域,所以叫做单链表链表中第一个结点的存储位置叫做头指针,整个链表的存取必须是从头指针开始进行
链表中最后一个结点的指针域为"空"(通常用NULL或符号"^"表示)
3.5.2 头指针与头结点的异同
- 头指针:
- 头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针
- 头指针具有标识作用,所以常用头指针冠以链表的名字
- 无论链表是否为空,头指针均不为空.头指针是链表的必要元素
- 头结点:
- 头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义
- 有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其他结点的操作就统一了
- 头结点不一定是链表的必须要素
3.5.3 线性表链式存储结构代码描述
//线性表的单链表存储结构 typedef struct Node { int data; struct Node* next; }Node; //定义结点结构 typedef struct Node* LinkList; //定义LinkList,某种意义上也即链表的头指针从代码中的结构定义可知:结点由存放数据的数据域、存放后继结点地址的指针域组成
3.6 单链表的读取
获得链表第i个数据的算法思路:
- 声明一个结点p指向链表第一个结点,初始化j从1开始;
- 当j<1时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1;
- 若到链表末尾p为空,则说明第i个元素不存在
- 否则查找成功,返回结点p的数据
实现代码算法如下:
/*初始条件:顺序线性表L已存在,1≤i≤ListLength(L)*/ /*操作结果:用e返回L中第i个数据元素的值*/ Status GetElem(LinkList L, int i, int* e) { int j; //声明计数器j LinkList p; //声明一结点p p = L->next; //让p指向链表的第一个节点 j = 1; while (p && j < i) //p不为空或者计数器j还没有等于i时，循环继续 { p = p->next; //p指向下一个节点 ++j; } if (!p || j > 1) return ERROR; //第一个元素不存在 *e = p->data; //取第i个元素的数据 return OK; }单链表的读取时间复杂度为O(n)
主要核心思想:运用"工作指针后移"来控制循环
3.7 单链表的插入与删除
3.7.1 单链表的插入
核心代码: s->next=p->next; p->next=s; 顺序不能更改!!!
单链表第i个数据插入结点的算法思路:
- 1.声明一结点p指向链表第一个结点,初始化j从1开始;
- 2.当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1;
- 3.若到链表末尾p为空,则说明第i个元素不存在;
- 4.否则查找成功,在系统中生成一个空结点s;
- 5.将数据元素e赋值给s->data;
- 6.单链表的标准插入语句 s->next=p->next; p->next=s;
- 7.返回成功状态
实现代码算法如下:
/*初始条件:顺序线性表L已存在,1≤i≤ListLength(L)*/ /*操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1*/ Status GetElem(LinkList *L, int i, int e) { int j; LinkList p,s; p = *L; j = 1; while (p&&j<1) //寻找第i个结点 { p = p->next; ++j; } if (!p || j > i) return ERROR; //第i个元素不存在 s = (LinkList)malloc(sizeof(Node)); //生成新结点 s->data = e; s->next = p->next; //将p的后继结点赋给s的后继 p->next = s; //将s赋值给p的后继 return OK; }C语言的标准函数malloc作用:生成一个新的结点,其类型与Node是一样的,其实质就是在内存中找了一小块空地,准备用来存放s结点
3.7.2 单链表的删除
核心代码: q=p->next; p->next=q->next;
单链表第i个数据删除结点的算法思路:
- 1.声明一结点p指向链表第一个结点,初始化计数器j从1开始;
- 2.当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1;
- 3.若到链表末尾p为空,则说明第i个元素不存在;
- 4.否则查找成功,将欲删除的结点p->next赋值给q;
- 5.单链表的删除标准语句 q=p->next; p->next=q->next;
- 6.将q结点中的数据赋值给e,作为返回
- 7.释放q结点;
- 8.返回成功
实现代码算法如下:
/*初始条件:顺序线性表L已存在,1≤i≤ListLength(L)*/ /*操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1*/ Status ListDelete(LinkList* L, int i, int* e) { int j; LinkList p, q; p = *L; j = 1; while (p->next&&j<i) { p = p->next; ++j; } if (!(p->next) || j > i) { return ERROR; //第i个元素不存在 } q = p->next; p->next = q->next; //将q的后继赋值给p的后继 *e = q->data; //将q结点中的数据给e free(q); //让系统回收此结点，释放内存 return OK; }C语言的标准函数free作用:让系统回收一个Node结点,释放内存
单链表的插入和删除的时间复杂度都是O(n)
3.8 单链表的整表创建
单链表整表创建的算法思路:
- 1.声明一结点p和计数器变量i;
- 2.初始化一空链表L;
- 3.让L的头结点的指针指向NULL,即建立一个带头结点的单链表;
- 4.循环:
- 生成一新结点赋值给p;
- 随机生成一数字赋值给p的数据域p->data(这一部分随数据存储需要更改)
- 将p插入到头结点与前一新结点之间
实现代码算法如下:
/*随机产生n个元素的值,建立带表头结点的单链线性表L(头插法)*/ void CreateListHead(LinkList* L, int n) { LinkList p; int i; srand(time(0)); //初始化随机数种子 *L = (LinkList)malloc(sizeof(Node));//链表头空间 (*L)->next = NULL; //建立一个带头结点的单链表 for (i = 0; i < n; i++) { p = (LinkList)malloc(sizeof(Node)); //生成新结点 p->data = rand() % 100 + 1; //随机生成100以内的数字 p->next = (*L)->next; (*L)->next = p; //插入到表头 } }/*随机产生n个元素的值,建立带表头结点的单链线性表L(尾插法)*/ void CreateListTail(LinkList* L, int n) { LinkList p, r; int i; srand(time(0)); //初始化随机数种子 *L = (LinkList)malloc(sizeof(Node)); //为整个线性表 r = *L; //r为指向尾部的结点 for (i = 0; i < n; i++) { p = (Node*)malloc(sizeof(Node)); //生成新结点 p->data = rand() % 100 + 1; //随机生成100以内的数字 r->next = p; //将表尾终端结点的指针指向新结点 r = p; //将当前的新结点定义为表尾终端结点 } r->next = NULL; //尾结点的指针域置空 }
3.9 单链表的整表删除
单链表整表删除的算法思路如下:
- 1.声明一结点p和q;
- 2.将第一个结点赋值给p
- 3.循环
- 将下一结点赋值给q;
- 释放p
- 将q赋值给p
实现代码算法如下:
/*初始条件:顺序线性表L已存在,操作结果:将L重置为空表*/ Status ClearList(LinkList* L) { LinkList p, q; p = (*L)->next; //p指向第一个结点 while (p) //没到表尾 { q = p->next; free(p); p = q; } (*L)->next = NULL; //头结点指针域为空 return OK; }
3.10 单链表结构与顺序存储结构优缺点
- 存储分配方式:
- 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
- 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素
- 时间性能:
- 查找:
- 顺序存储结构O(1)
- 单链表O(n)
- 插入和删除
- 顺序存储结构需要平均移动表长一半的元素,时间为O(n)
- 单链表在找出某位置的指针后,插入和删除时间仅为O(1)
- 空间性能
- 顺序存储结构需要预分配存储空间,分大了浪费,分小了易发生数组上界溢出
- 单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制
- 查找:
- 结论:
- 若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构.若需要频繁插入和删除时,宜采用单链表结构
- 当线性表中的元素个数变化较大或者根本不知道有多大时,最好用单链表结构.而如果事先知道线性表的大致长度,用顺序存储结构效率会高很多
3.11 循环链表
- 针对单链表无法找到前驱结点的缺点,把单链表的最后一个结点的指针域由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表成为单循环链表,简称循环链表
- 循环链表可以从当中任意一个结点出发,访问到链表的全部结点
- 循环链表带有头结点的空链表如图所示
- 非空的循环链表如图所示
3.12 双向链表
双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域
再将双向链表优化一下,使其成为双向循环链表
/*线性表的双向链表存储结构*/ typedef struct DulNode { int data; struct DuLNode* prior; //直接前驱指针 struct DuLNode* next; //直接后继指针 }DulNode, *DuLinkList;双向链表的一个结点如图所示
- 每个结点的后继的前驱、前驱的后继都是结点本身
- 在插入和删除时,双向链表的操作与单链表有些许不同,需要更改两个指针变量
插入
s->prior=p; //把p赋值给s的前驱,如图中1 s->next=p->next; //把p->next赋值给s的后继,如图中2 p->next->prior=s; //把s赋值给p->next的前驱,如图中3 p->next=s; //把s赋值给p的后继,如图中4
删除
p->prior->next=p->next; //把p->next赋值给p->prior的后继,如图中1 p->next->prior=p->prior;//把p->prior赋值给p->next的前驱,如图中2 free(p); //释放结点p
第4章 栈与队列
4.1 栈的定义
4.1.1 栈的定义
- 栈(stack):是限定仅在表尾进行插入和删除操作的线性表
- 栈允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的栈称为空栈.栈又称为后进先出的线性表
- 栈的插入操作,叫作进栈(pop),也称压栈、入栈.
- 栈的删除操作,叫作出栈(push),也有的叫做弹栈
4.1.2 进栈出栈变化形式
在不是所有元素都进栈的情况下,事先进去的元素也可以出栈,只要保证是栈顶元素出栈就可以
规律:
- 1.在入栈序列中顺序比出栈元素小的，必须是逆序
- 2.在入栈序列中顺序比出栈元素大的，顺序无所谓
4.2 栈的抽象数据类型
ADT 栈(stack)
data
同线性表.元素具有相同的类型,相邻元素具有前驱和后继关系
Operation
InitStack(*S):初始化操作,建立一个空栈S
DestroyStack(*S):若栈存在,则销毁它
ClearStack(*S):将栈清空
StackEmpty(S):若栈为空,返回true,否则返回false
GetTop(S,*e):若栈存在且非空,用e返回S的栈顶元素
Push(*S,*e):若栈S存在,插入新元素e到栈S中并成为栈顶元素
Pop(*S,*e):删除栈S中栈顶元素,并用e返回其值
StackLength(S):返回栈S的元素个数
endADT 4.3 栈的顺序存储结构及实现
4.3.1 栈的顺序存储结构
- 栈的结构定义
typedef int SElemType; //SElemType类型根据实际情况而定,这里假设为int
typedef struct
{
SElemType data[MAXSIZE];
int top; //用于栈顶指针
}SqStack 
4.3.2 栈的顺序存储结构——进栈操作
对于进栈操作push,代码如下
/*插入元素e为新的栈顶元素*/ Status Push(SqStack* S, SElemType e) { if (S->top == MAXSIZE - 1) //栈满 { return ERROR; } S->top++; //栈顶指针增加一 S->data[S->top] = e; //将新插入元素赋值给栈顶空间 return OK; }
4.3.3 栈的顺序存储结构——出栈操作
对于出栈操作pop,代码如下
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR Status Pop(SqStack* S, SElemType *e) { if (S->top == 0) { return ERROR; } *e = S->data[S->top]; S->top--; return OK; }顺序栈的进栈和出栈操作的*时间复杂度均是O(1)
4.4 栈的链式存储结构及实现
4.4.1 栈的链式存储结构
链栈的结构代码如下
typedef struct StackNode { SElemType data; struct StackNode* next; }StackNode,*LinkStackPtr; typedef struct LinkStack { LinkStackPtr top; int count; }LinkStack;
4.4.2 栈的链式存储结构——进栈结构
假设元素值为e的新结点是s,top为栈顶指针,进栈代码如下
//插入元素e为新的栈顶元素 Status Push(LinkStack* S, SElemType e) { LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode)); s->data = e; s->next = S->top; //把当前的栈顶元素赋值给新结点的直接后继 S->top = s; //将新的结点s赋值给栈顶指针 S->count++; return OK; }
4.4.3 栈的链式存储结构——出栈操作
出栈操作:假设变量p用来存储要删除的栈顶结点,将栈顶指针下移一位,最后释放p即可
//若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR Status Pop(LinkStack* S, SElemType* e) { LinkStackPtr p; if (StackEmpty(*S)) return ERROR; *e = S->top->data; p = S->top; S->top = S->top->next; free(p); S->count--; return OK; }
链栈的进栈和出栈操作时间复杂度均为O(1)
如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈
4.5 栈的应用——递归
4.5.1 以斐波那契数列实现为例
如果用常规的迭代方法(假设打印前40位)
int main() { int i; int a[40]; a[0]=0; a[1]=1; printf("%d",a[0]); printf("%d",a[1]); for(i=2;i<40;i++) { a[i]=a[i-1]+a[i-2]; printf("%d",a[i]); } return 0; }而如果用递归来实现
//斐波那契的递归函数 int Fbi(int i) { if(i<2) return i==0?0:1; return Fbi(i-1)+Fbi(i-2); //这里Fbi就是函数自己,它在调用自己 } int main() { int i; for(int i=0;i<40;i++) printf("%d",Fbi(i)); return 0; }图示
4.5.2 递归定义
- 我们把一个直接调用自己或通过一系列的调用语句间接的调用自己的函数,称做递归函数
- 每个递归定义必须至少有一个条件,满足时递归不再进行,即不再引用自身而是返回值退出
4.6 队列的定义
- 队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表
- 队列是一种先进先出的线性表,允许插入的一端称为队尾,允许删除的一端称为队头
4.7 队列的抽象数据类型
ADT 队列(Queue)
Data
同线性表.元素具有相同的类型,相邻元素具有前驱和后继关系
Operation
InitQueue(*Q):初始化操作,建立一个空队列Q
DestroyQueue(*Q):若队列Q存在,则销毁它
ClearQueue(*Q):将队列Q清空
QueueEmpty(Q):若队列Q为空,返回true,否则返回false
GetHead(Q,*e):若队列Q存在且非空,用e返回队列Q的队头元素
EnQueue(*Q,e):若队列Q存在,插入新元素e到队列Q中并成为队尾元素
DeQueue(*Q,*e):删除队列Q中队头元素,并用e返回其值
QueueLength(Q):返回队列Q的元素个数
endADT 4.8 循环队列
4.8.1 队列顺序存储的不足
- 单纯的顺序队列有"假溢出"的问题(根据rear指针看起来队列满了,队列的实际可用空间并未占满)
4.8.2 循环队列定义
我们将队列头尾相接,变为一个环状的空间,称为循环队列
循环队列解决了"假溢出",但没有解决真溢出(空间溢出)
在这种情况下,有两种区别队满还是队空的方法
- 1.设置一个标志变量flag,当front==rear,且flag=0时为队列空,当front==rear,且flag=1时为队列满
- 2.当队列空时,条件就是front=rear,当队列满时,我们修改其条件,保留一个元素空间,即队列空间大小为m时,有m-1个元素就认为是队满.这样判断队空的条件不变,即当头尾指针的值相同时,则认为队空;而当尾指针在循环意义上加1后是等于头指针,则认为队满,即条件为(rear+1)%QueueSize==front。
如图所示,我们就认为此队列已经满了
循环队列的顺序存储结构代码如下
//循环队列的顺序存储结构 typedef struct { QElemType data[MAXSIZE]; int front; //头指针 int rear; //尾指针，若队列不空，指向队列尾元素的下一个位置 }SqQueue;循环队列的初始化代码如下
//初始化空队列Q Status InitQueue(SqQueue* Q) { Q->front = 0; Q->rear = 0; return OK; }循环队列求队列长度代码如下
//返回Q的元素个数，也就是队列的当前长度 int QueueLength(SqQueue Q) { return (Q.rear - Q.front + MAXSIZE) % MAXSIZE; }循环队列的入队列操作代码如下
//若队列未满，则插入元素e为Q的新队元素 Status EnQueue(SqQueue* Q, QElemType e) { if ((Q->rear + 1) % MAXSIZE == Q->front) //队列满的判断 return ERROR; Q->data[Q->rear] = e; //将元素e赋值给队尾 Q->rear = (Q->rear + 1) % MAXSIZE; //rear指针向后移一位置 //若到最后则转到数组头部 return OK; }循环队列的出队列操作代码如下
Status DeQueue(SqQueue* Q, QElemType* e) { if (Q->front == Q->rear) //队列空的判断 return ERROR; *e = Q->data[Q->front]; //将队头元素赋值给e Q->front = (Q->front + 1) % MAXSIZE; //front指针向后移一位置 //若到最后则转到数组头部 return OK; }
4.9 队列的链式存储结构及实现
4.9.1 队列的链式存储结构定义
队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列
空队列时
//队列的链结构 typedef int QElemType; //QElemType类型根据实际情况而定,这里假设为int typedef struct QNode //结点结构 { QElemType data; struct QNode* next; }QNode,*QueuePtr; typedef struct //队列的链表结构 { QueuePtr front, rear; //队头，队尾指针 }LinkQueue;
4.9.2 队列的链式存储结构——入队操作
//插入元素e为Q的新的队尾元素 Status EnQueue(LinkQueue* Q, QElemType e) { QueuePtr s = (QueuePtr)malloc(sizeof(QNode)); if (!s) exit(OVERFLOW); //exit是c++程序的退出函数 //OVERFLOW为math.h的一个宏定义，其值为3 //含义为运算过程中出现了上溢，即运算结果 //超出了运算变量所能存储的范围 s->data = e; s->next = NULL; Q->rear->next = s; //把拥有元素e的新结点s赋值给原队尾结点的后继 Q->rear = s; //把当前的s设置为队尾结点，rear指向s return OK; }
4.9.3 队列的链式存储结构——出队操作
//若队列不空，删除Q的队头元素，用e返回其值，并返回0,否则返回-1 Status DeQueue(LinkQueue* Q, QElemType* e) { QueuePtr p; if (Q->front == Q->rear) return ERROR; p = Q->front->next; //将欲删除的队头结点暂存给p *e = p->data; //将欲删除的队头结点的值赋值给e Q->front->next = p->next; //将原队头结点后继p->next赋值给头结点后继 if (Q->rear == p) //若队头是队尾，则删除后将rear指向头结点 Q->rear = Q->front; free(p); return OK; }循环队列与链队列的时间复杂度均为O(1),但链队列每次申请和释放结点会多存在一些时间开销
在空间上,循环队列可能有存储元素个数和空间浪费的问题,而链队列不存在这个问题
第5章 串,数组和广义表
5.1 串的定义
- 串又名字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。
- 串是内容受限的线性表,它限定了表中的元素为字符
- 串长：串中字符个数（n≥0）. n=0 时称为空串
- 空白串：由一个或多个空格符组成的串
- 子串：串S中任意个连续的字符序列叫S的子串; S叫主串
- 当两个串的长度相等，并且各个对应位置的字符都相等时，才称这两个串相等
5.2 串的类型定义、存储存储结构及其运算
5.2.1 串的抽象类型定义
ADT 串(string)
Data
串中元素仅由一个字符组成,相邻元素具有前驱和后继关系
Operation
StrAssign(T,*chars):生成一个其值等于字符串常量chars的串T
StrCopy(T,S):串S存在,由串S复制得串T
ClearString(S):串S存在,将串清空
StringEmpty(S):若串S为空,返回true,否则返回false
StrLength(S):返回串S的元素个数,即串的长度
StrCompare(S,T):若S>T,返回值>0,若S=T,返回0,若S<T,返回值<0
Concat(T,S1,S2):用T返回由S1和S2联接而成的新串
SubString(Sub,S,pos,len):串S存在,1≤pos≤StrLength(S),且0≤len≤StrLength(S)-pos+1,用Sub返回串S的第pos个字符起长度为len的子串
Index(S,T,pos):串S和T存在,T是非空串,1≤pos≤StrLength(S).若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置,否则返回0
Replace(S,T,V):串S、T和V存在,T是非空串.用V替换主串S中出现的所有与T相等的不重叠的子串
StrInsert(S,pos,T):串S和T存在,1≤pos≤StrLength(S)+1.在串S的第pos个字符之前插入串T.
StrDelete(S,pos,len):串S存在,1≤pos≤StrLength(S)-len+1.从串S中删除第pos个字符起长度为len的子串.
endADT 5.2.2 串的存储结构
- 定长顺序存储:用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。
- 堆分配存储:仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态按需分配而得
- 链式存储:用链表来存储串值,存在一个"结点大小"的问题,存储量大、操作复杂
5.3 串的BF模式匹配算法
举例:在一篇文章中寻找一个单词.这种子串的定位操作通常称作串的模式匹配
假设要从主串S="goodgoogle"中找到T="google"这个子串的位置.
- 1.主串S第一位开始,S和T前三个字母都匹配成功,但S第四个字母是d而T的是g.第一位匹配失败
- 2.主串S第二位开始,主串S首字母是o,要匹配的T首字母是g,匹配失败
- 3.主串S第三位开始,主串S首字母是o,要匹配的T首字母是g,匹配失败
- 4.主串S第四位开始,主串S首字母是d,要匹配的T首字母是g,匹配失败
- 5.主串S第五位开始,S与T,6个字母全匹配,匹配成功
代码实现如下
//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0 //T非空，1≤pos≤StrLength(S) int Index(string S, string T, int pos) { int i = pos; //i用于主串S中当前位置下标，若pos不为1 //则从pos位置开始匹配 int j = 1; //j用于子串T中当前位置下标值 while (i <= S[0] && j <= T[0]) //若i小于S长度且j小于T的长度时循环 { if (S[i] == T[j]) //两字母相等则继续 { ++i; ++j; } else //指针后退重新开始匹配 { i = i - j + 2; //i退回到上次匹配首位的下一位 j = 1; //j退回到子串T的首位 } } if (j > T[0]) { return i - T[0]; } else return 0; }BF算法较为低效
5.4 串的KMP模式匹配算法——好马不吃回头草
5.4.1 KMP模式匹配算法简述
- 为了改变BF算法的低效,科学家发表了一种新的模式匹配算法,可以大大避免重复遍历的情况,简称KMP算法
- BF算法中,一遇到不匹配,匹配串则需要回溯.但KMP算法减少了一些不必要的回溯,j有时候不需要回溯到1的位置
- 「天勤公开课」KMP算法易懂版_哔哩哔哩_bilibili 建议直接看视频易懂
- KMP算法的时间复杂度为O(m+n)(m为主串长度,n为子串长度)
5.4.2 KMP模式匹配算法实现
- 略
5.5 数组
5.5.1 数组的定义
- 数组是线性表的推广,特点是结构中的元素本身可以是具有某种结构的数据,但属于同一数据类型
5.5.2 一维数组
- 一维数组可看成是一个线性表或一个向量,存储在一块连续的存储单元中,适合于随机查找.一维数组记为A[n]或A=(a
0，a1，…ai，…，an-1) ,一维数组中ai的存储地址LOC(ai)可由下式求出:
LOC(ai)=LOC(a0)+i*L (0≤i<n)
5.5.3二维数组
- 二维数组,又称矩阵(matrix).每个元素又是一个定长的线性表(一维数组),都要受到两个关系即行关系和列关系的约束,也就是每个元素都同属于两个线性表.
- 一个二维数组可以看作是每个数据元素类型都相同的一维数组.以此类推,任何多维数组都可以看作一个线性表,这时线性表中的每个数据元素也是一个线性表.多维数组是特殊的线性表,是线性表的推广.
5.6 广义表
- 广义表是线性表的推广,也称为列表
- 广义表是n(n≥0)个元素的一个序列,表中的元素可以是称为原子的单个元素,也可以是一个子表,若n=0时则称为空表.设a
i为广义表的第i个元素,则广义表的一般表示与线性表相同,LS=(a1,a2,…,ai,…,an),其中n表示广义表的长度,n≥0.ai可以是单个元素，也可以是广义表. - 如果a
i是单个数据元素，则ai是广义表LS的原子；如果ai是一个广义表，则ai是广义表LS的子表 - 广义表的长度（广度）：广义表中所包含的数据元素的个数
- 广义表的深度，可以通过观察该表中所包含括号的层数间接得到。
- 广义表的三个重要结论:
- 广义表的元素可以是子表,而子表的元素还可以是子表
- 广义表可以被其他广义表所共享
- 广义表可以是一个递归的表
第6章 树和二叉树
6.1 树和二叉树的定义
6.1.1 树的定义
树(Tree)是n(n≥0)个结点的有限集.n=0时称为空树.在任意一棵非空树中:
- (1) 有且仅有一个特定的、没有前驱的结点称为根结点(Root)
- (2) 当n>1时,其余结点可分为m(m>0)个互不相交的有限集 T
1、T2、……、Tm, 其中每一个集合本身又是一棵树,并且称为根的子树(SubTree) - (3) 每个子节点只有一个父节点
- (4) 每个结点具有0个或多个子节点
树结构:
- 根结点:无双亲,唯一
- 叶结点:无孩子,可以多个
- 中间结点:一个双亲多个孩子
6.1.2 树的基本术语
- 结点的度:结点拥有的子树数量称为结点的度
- 树的度:树内各结点度的最大值
- 叶子:度为0的结点称为叶子或终端结点
- 结点的层次和树的深度:结点的层次从根开始定义起,根为第一层,根的孩子为第二层,以此类推.树的深度(Depth)或高度是树中结点的最大层次
- 森林:m棵互不相交的树的集合
6.1.3 结点间关系
- 结点的子树的根称为该结点的孩子,相应的,该结点称为孩子的双亲
- 同一个双亲的孩子之间互称兄弟
- 结点的祖先是指从根到该结点所经分支上的所有结点,反之,以某结点为根的子树中的任一结点都称为该结点的子孙
6.2 树的抽象数据类型
ADT 树(tree) Data 树是由一个根结点和若干颗子树构成.树中结点具有相同数据类型及层次关系 Operation InitTree(*T):构造空树T DestroyTree(*T):销毁树T CreateTree(*T,definition):按definition中给出的树的定义来构造树 ClearTree(*T):若树T存在,则将树T清为空树 TreeEmpty(T):若T为空树,返回true,否则返回false TreeDepth(T):返回T的深度 Root(T):返回T的根结点 Value(T,cur_e):cur_e是树T中的一个结点,返回此结点的值 Assign(T,cur_e,value):给树T的结点cur_e赋值为value Parent(T,cur_e):若cur_e是树T的非根结点,则返回他的双亲,否则返回空 LeftChild(T,cur_e):若cur_e是树T的非叶结点,则返回他的最左孩子,否则返回空 RightSibling(T,cur_e):若cur_e有右兄弟,则返回他的右兄弟,否则返回空 InsertChild(*T,*p,i,c):其中p指向树T的某个结点,i为所指结点p的度加上1,非空树c与T不相交,操作结果为插入c为树T中p指结点的第i颗子树 DeleteChild(*T,*p,i):其中p指向树T的某个结点,i为所指结点p的度,操作结果为删除T中p所指结点的第i棵子树 endADT
6.3 树的存储结构
6.3.1 双亲表示法
每个树的结点除了存储本身数据外,附设一个指示器指示其双亲结点到链表中的位置,如图所示
其中data是数据域,存储结点的数据信息.而parent是指针域,存储该结点的双亲在数组中的下标
/* 树的双亲表示法结点结构定义 */ #define MAX_TREE_SIZE 100 typedef int TElemType; //树结点的数据类型,目前暂定为整型 typedef struct PTNode //结点结构 { TElemType data; //结点数据 int parent; //双亲位置 }PTNode; typedef struct //树结构 { PTNode nodes[MAX_TREE_SIZE];//结点数组 int r,n; //根的位置和结点数 }PTree;由于根结点是没有双亲的,所以我们约定根结点的位置域设置为-1
树结构和树双亲表示所示如图
)
双亲表示法查找双亲结点的时间复杂度为O(1),查找结点的孩子则需要遍历整个结构
6.3.2 孩子表示法
由于树中每个结点可能有多颗子树,可以考虑用多重链表,即每个结点有多个指针域,其中每个指针指向一棵子树的根结点,我们把这种方法叫做多重链表表示法.
此时链表中的结点有两种表示方案
1.指针域的个数就等于树的度(浪费空间)
其中data是数据域,child1到childd是指针域,用来指向该结点的孩子结点
2.每个节点指针域的个数等于该结点的度,专门取一个位置来存储结点指针域的个数(虽能节约存储空间,但操作不方便)
其中data是数据域,degree为度域,也就是存储该结点的孩子结点的个数,child1到childd为指针域,指向该结点的各个孩子的结点
另外一种办法:把每个结点的孩子结点排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空.然后n个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中,如图所示
再将双亲表示法和孩子表示法综合一下,称之为双亲孩子表示法
6.3.3 孩子兄弟表示法
任意一棵树,他的结点的第一个孩子如果存在就是唯一的,他的右兄弟如果存在也是唯一的.因此,我们设置两个指针,分别指向该结点的第一个孩子和此节点的右兄弟
结点结构如图所示
其中data是数据域,firstchild为指针域,存储该结点的第一个孩子结点的存储地址,rightsib是指针域,存储该结点的右兄弟结点的存储地址
结构定义代码如下
/* 树的孩子兄弟表示法结构定义 */ typedef struct CSNode { TElemType data; struct CSNode *firstchild,*rightsib; }CSNode,*CSTree;好处:将一棵复杂的树变成了一棵二叉树
6.3 二叉树的定义
- 二叉树(Binary Tree)是n(n≥0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成
6.5.1 二叉树的特点
- 二叉树的特点有:
- 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点.注意不是只有两棵子树,而是最多有.没有子树或者有一棵子树都是可以的
- 左子树和右子树是有顺序的,次序不能任意颠倒
- 即使树中某结点只有一棵子树,也要区分它是左子树还是右子树
- 二叉树具有五种基本形态:
- 1.空二叉树
- 2.只有一个根结点
- 3.根结点只有左子树
- 4.根结点只有右子树
- 5.根结点既有左子树又有右子树
6.5.2 特殊二叉树
- 1.满二叉树:在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树,如图
- 满二叉树的特点有:
- (1) 叶子只能出现在最下一层.出现在其它层就不可能达成平衡
- (2) 非叶子结点的深度一定是2
- (3) 在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多
- 2.完全二叉树:对一棵具有n个结点的二叉树按程序编号,如果编号为i(1≤i≤n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树,如图
- 完全二叉树的特点:
- (1) 叶子结点只能出现在最下两层
- (2) 最下层的叶子一定集中在左部连续位置
- (3) 倒数第二层如果有叶子结点,一定都在右边连续的位置
- (4) 如果结点度为1,则该结点只有左孩子,即不存在只有右子树的情况
- (5) 同样结点数的二叉树,完全二叉树的深度最小
6.4 二叉树的性质
- 性质1:在二叉树的第i层上至多有2^i-1^个结点(i≥1)
- 性质2:深度为k的二叉树至多有2^k^-1个结点(k≥1)
- 性质3:对任何一棵二叉树T,如果其终端结点数为n
0,度为2的结点数为n2,则n0=n2+1 - 性质4:具有n个结点的完全二叉树的深度为[log
2n]+1([x]表示不大于x的最大整数) - 性质5:如果对一棵有n个结点的完全二叉树(其深度为[log
2n]+1)的结点按层序编号(从第1层到第[log2n]+1层,每层从左到右),对任一结点i(1≤i≤n)有:- 1.如果i=1,则结点i是二叉树的根,无双亲;如果i＞1,则其双亲是结点[i/2]
- 2.如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i
- 3.如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1
结合图片理解
6.5 二叉树的存储结构
6.5.1 二叉树顺序存储结构
- 完全二叉树的顺序存储结构,直接用其序号对应相应的下标,如图所示
- 对于一般的二叉树,在完全二叉树序号的基础上编号,只不过把不存在的结点设置为"^"
- 顺序存储结构一般只用于完全二叉树
6.5.2 二叉链表
二叉树每个结点最多有两个孩子,所以我们为他设计一个数据域和两个指针域,称这样的链表叫做二叉链表
其中data是数据域,lchild和rchild都是指针域,分别存放指向左孩子和右孩子的指针
二叉链表结点结构定义代码
/* 二叉树的二叉链表结点结构定义 */ typedef struct BiTNode //结点结构 { TElemType data; //结点数据 struct BiTNode *lchild,*rchild; //左右孩子指针 }BiTNode,*BiTree;结构示意图如图所示
6.6 遍历二叉树
6.6.1 二叉树遍历原理
- 二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次
6.6.2 二叉树遍历方法
1.前序遍历
- 规则是若二叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树
- 2.中序遍历
- 规则是若树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结点),中序遍历根结点的左子树,然后是访问根结点,最后中序遍历右子树
- 规则是若树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结点),中序遍历根结点的左子树,然后是访问根结点,最后中序遍历右子树
- 3.后序遍历
- 规则是若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后访问根结点
- 4.层序遍历
- 规则是若树为空,则空操作返回,否则从树的第一层,也就是根结点开始访问,从上而下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问.
6.6.3 前序遍历算法
/* 二叉树的前序遍历算法 */ void PreOrderTraverse(BiTree T) { if(T==NULL) return; printf("%c",T->data); //显示结点数据,可以更改为对其他结点操作 PreOrderTraverse(T->lchild); //再先序遍历左子树 PreOrderTraverse(T->rchild); //最后先序遍历右子树 }6.6.4 中序遍历算法
/* 二叉树的中序遍历算法 */ void InOrderTraverse(BiTree T) { if(T==NULL) return; InOrderTraverse(T->lchild); //中序遍历左子树 printf("%c",T->data); //显示结点数据,可以更改为对其他结点操作 InOrderTraverse(T->child); //最后中序遍历右子树 }6.6.5 后序遍历算法
/* 二叉树的后序遍历算法 */ void PostOrderTraverse(BiTree T) { if(T==NULL) return; PostOrderTraverse(T->lchild); //先后序遍历左子树 PostOrderTraverse() }6.6.6 推导遍历结果
- 已知前序遍历序列和中序遍历序列,可以唯一确定一棵二叉树
- 已知后序遍历序列和中序遍历序列,可以唯一确定一棵二叉树
- 已知前序和后序遍历,是不能确定一棵二叉树的
- 规则是若二叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树
6.7 二叉树的建立
为了能让每个结点确认是否有左右孩子,将二叉树中每个结点的空指针引出一个虚节点,其值为一特定值,比如"#".我们称这种处理后的二叉树为原二叉树的扩展二叉树.
假设二叉树的结点均为一个字符.把刚才前序遍历序列AB#D##C##用键盘挨个输入.实现的算法如下
/* 按前序输入二叉树中结点的值(一个字符)*/ /* #表示空树,构造二叉链表表示二叉树T*/ void CreateBiTree(BiTree *T) { TElemType ch; scanf("%c",&ch); if(ch=='#') *T=NULL; else { *T=(BiTree)malloc(sizeof(BiTNode)); if(!*T) exit(OVERFLOW); (*T)->data=ch; //生成根结点 CreateBiTree(&(*T)->lchild); //构造左子树 CreateBiTree(&(*T)->rchild); //构造右子树 } }
6.8 线索二叉树
6.8.1 线索二叉树原理
对于n个结点的二叉树，则在二叉链存储结构中就会有n+1个空链域;对于一个有 n 个结点的二叉链表，每个结点指向左右孩子的两个指针域，故共有 2n 个指针域，而 n 个结点的二叉树共有 n-1 条分支，即存在 2n-(n-1) = n+1 个空链域
如果一个结点左孩子为空,则指向它的前驱结点,如果一个结点右孩子为空,则指向他的后继
这种指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树就称为线索二叉树
对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化
但此时无法区分child指向的是前驱还是孩子,就需要一个区分标志,因此需要在每个结点再增设两个标志域,如图所示
其中:
- ltag为0时指向该结点的左孩子,为1时指向该结点的前驱
- rtag为0时指向该结点的右孩子,为1时指向该结点的后继
6.8.2 线索二叉树结构实现
- 二叉树的线索结构定义代码如下:
/* 二叉树的二叉线索存储结构定义 */
typedef enum{Link,Thread}PointerTag; //Link==0 表示指向左右孩子指针
//Thread==1 表示指向前驱或后继的线索
typedef struct BiThrNode //二叉线索存储结点结构
{
TElemType data; //结点数据
struct BiThrNode *lchild,*rchild; //左右孩子指针
PointerTag LTag;
PointerTag RTag; //左右标志
}BiThrNode,*BiTherTree; - 中序遍历线索化的递归函数代码如下:
BiThrTree pre; //全局变量,始终指向刚刚访问过的结点
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p)
{
if(p)
{
InThreading(p->lchild); //递归左子树线索化
if(!p->lchild) //没有左孩子
{
p->LTag=Thread; //前驱线索
p->lchild=pre; //左孩子指针指向前驱
}
if(!pre->rchild) //前驱没有右孩子
{
pre->RTag=Thread; //后继线索
pre->rchild=p; //前驱右孩子指针指向后继(当前结点p)
}
pre=p; //保持pre指向p的前驱
InThreading(p->rchild); //递归右子树线索化
}
} 有了线索二叉树,对其遍历时其实就等于操作一个双向链表结构
遍历的代码如下:
/* T指向头结点,头结点左链lchild指向根结点,头结点右链rchild指向中序遍历的最后一个结点.中序遍历二叉线索链表表示的二叉树T */ Status InOrderTraverse_Thr(BiThrTree T) { BiThrTree p; p=T->lchild; // p指向根结点 while(p!=T) //空树或遍历结束时,p==T { while(p->LTag==Link) //当LTag==0时循环到中序序列第一个结点 p=p->lchild; printf("%c",p->data); //显示结点数据,可以更改为对其他结点操作 while(p->RTag==Thread&&p->rchild!=T) { p=p->rchild; printf("%c",p->data); } p=p->rchld; //p进至其右子树根 } return OK; }如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继,那么采用线索二叉链表的存储结构就是非常不错的选择
6.9 树和森林
- 树的孩子兄弟表示法可以将一棵树用二叉链表进行存储,所以借助二叉链表,树和二叉树可以相互进行转换
6.9.1 树转化为二叉树
- 将树转换为二叉树的步骤如下
- 1.加线.在所有兄弟结点之间加一条连线
- 2.去线.对树中每个结点,只保留他与第一个孩子结点的连线,删除它与其他孩子结点之间的连线
- 3.层次调整.以树的根结点为轴心,将整棵树顺时针旋转一定的角度,使之结构层次分明.注意第一个孩子是二叉树结点的左孩子,兄弟转换过来的孩子是结点的右孩子
6.9.2 森林转换为二叉树
- 1.把每个树转换为二叉树
- 2.第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子,用线连接起来.当所有的二叉树连接起来后就得到了由森林转换来的二叉树
6.9.3 二叉树转换为树
- 1.加线,若某结点的左孩子结点存在,将左孩子的n个右孩子结点都作为此结点的孩子.将该结点与这些右孩子结点用线连接起来
- 2.去线.删除原二叉树中所有结点与其右孩子结点的连线
- 3.层次调整.使之结构层次分明
6.9.4 二叉树转换为森林
1.从根结点开始,若右孩子存在,则把与右孩子结点的连线删除,再查看分离后的二叉树,若右孩子存在,则连线删除,知道所有右孩子连线都删除为止,得到分离的二叉树
2.再将每棵分离后的二叉树转换为树即可
判断一棵二叉树能够转换成一棵树还是森林,只要看这棵二叉树的根结点有没有右孩子
6.10 哈夫曼树
6.10.1 哈夫曼树的基本概念
- 哈夫曼树又被称为最优树
- 路径：从一个结点到另一个结点之间的分支序列
- 路径长度：从一个结点到另一个结点所经过的分支数目
- 结点的权：根据应用的需要可以给树的结点赋权值
- 带权路径长度：从根到该结点的路径长度与该结点权的乘积
- 树的带权路径长度：树中所有叶子结点的带权路径之和
- 哈夫曼树：由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树
- 哈夫曼树不存在度为 1 的结点。
- n个叶子结点的哈弗曼树有 2n-1 个结点
6.10.2 哈夫曼树的构造算法
- 1.初始化:根据给定的n个权值,构造n棵只有一个根结点的二叉树,这n棵二叉树构成森林F
- 2.找最小树:在F中选取两棵根结点树值最小的树作为左、右子树,构造一棵新的二叉树,置新二叉树根的权值为左、右子树根结点权值之和
- 3.删除与加入:从F中删除这两棵树,并将新树加入F
- 4.判断:重复2、3步骤,直到F中只含一棵树为止,此时得到的这棵二叉树就是哈夫曼树
6.10.3 哈夫曼编码
- 前缀码：如果在一个编码系统中，任一个编码都不是其他任何编码的前缀，则称该编码系统中的编码是前缀码。例如，一组编码01,001,010,100,110就不是前缀码，因为01是010的前缀，若去掉01或010就是前缀码
- 哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的通路上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码
- 哈夫曼编码是最优前缀码
第7章 图
7.1 图的定义
- 图(Graph):图是由顶点的有穷非空集合和顶点之间的边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合.
- 在图中的数据元素称之为顶点
- 在图结构中不允许没有顶点.在定义中,若V是顶点的集合,则强调了顶点集合V有穷非空
- 图中任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以为空
7.1.1各种图定义
- 无向边:若顶点v
i到Vj之间的边没有方向,则称这条边为无向边,用无序偶对(vi,vj)来表示.如果图中任意两个顶点之间的边都是无向边,则称该图为无向图.
- 有向边:若从顶点v
i到vj的边有方向,则称这条边为有向边,也称为弧.用有序偶对<vi,vj>来表示,vi,称为弧尾,vj称为弧头.如果图中任意两个顶点之间的边都是有向边,则称该图为有向图.如图就是一个有向图,连接顶点A到D的有向边就是弧,A是弧尾,D是弧头,<A,D>表示弧,注意不能写成<D,A>
- 注意:无向边用小括号"()"表示,而有向边则是用尖括号"<>"表示
- 在图中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图
- 在无向图中.如果任意两个顶点之间都存在边,则称该图为无向完全图
- 在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图
- 边数小于 nlogn 的称为稀疏图,反之称为稠密图
- 有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做权.这些权可以表示从一个顶点到另一个顶点的距离或耗费.这种带权的图通常称为网
- 假设有两个图G(V,{E})和G'=(V',{E'}),如果V' ⊆V且E'⊆E,则称G'为G的子图.如下图带底纹的图均为左侧无向图和有向图的子图
7.1.2 图的顶点与边间关系
- 对于无向图G=(V,{E}),如果边(v,v')∈E,则称顶点v和v'互为邻接点,即v和v'相邻接.边(v,v')依附于顶点v和v',或者说(v,v')与顶点v和v'相关联.顶点v的度是和v相关联的边的数目,记为TD(v).度数之和是顶点边数的两倍
- 对于有向图G=(V,{E}),如果弧<v,v'>∈E,则称顶点v邻接到顶点v',顶点v'邻接自顶点v.弧<v,v'>和顶点v,v'相关联,以顶点v为头的弧的数目称为v的入度,记为ID(v);以v为尾的弧的数目称为v的出度,记为OD(v);顶点v的度为TD(v)=ID(v)+OD(v).全部顶点入度之和等于出度之和且等于边数.顶点的度等于入度与出度之和.
- 路径的长度是路径上的边或弧的数目
- 第一个顶点到最后一个顶点相同的路径称为回路或环.序列中顶点不重复出现的路径称为简单路径.除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环.
7.1.3 连通图相关术语
- 在无向图G中,如果从顶点v到顶点v'有路径,则称v和v'是连通的.如果对于图中任意两个顶点v
i、vj∈E,vi和vj都是连通的,则称G是连通图. - 无向图中的极大连通子图称为连通分量.连通分量强调:
- 要是子图
- 子图要是连通的
- 连通子图含有极大顶点数
- 具有极大顶点数的连通子图包含依附于这些顶点的所有边
- 在有向图G中,如果对于每一对v
i、vj∈V、vi≠vj,从vi到vj和vj到vi都存在路径,则称G是强连通图.有向图的极大强连通子图称作有向图的强连通分量
图2就是图1的强连通分量 - 连通图的生成树:连通图的生成树是包含图中全部顶点的一个极小连通子图，若图中有n个顶点，则生成树有n-1条边，仅有足以构成一颗树的 n-1 条边
- 如果一个有向图恰有一个顶点的入度为0,其余顶点的入度均为1,则是一棵有向树.一个有向图的生成森林由若干棵有向树组成,含有图中全部顶点,但只有足以构成若干棵不相交的有向树的弧.
7.1.4 图的定义与术语总结
- 图按照有无方向分为无向图和有向图.无向图由顶点和边构成,有向图由顶点和弧构成.弧有弧头和弧尾之分
- 图按照边或弧的多少分稀疏图和稠密图.如果任意两个顶点之间都存在边叫完全图,有向的叫有向完全图.若无重复的边或顶点到自身的边则叫简单图
- 图中顶点之间有邻接点、依附的概念.无向图顶点的边数叫做度,有向图顶点分为入度和出度.
- 图上的边或弧上带权则成为网
- 图中顶点间存在路径,两顶点存在路径则说明是连通的,如果路径最终回到起始点则成为环,当中不重复叫简单路径.若任意两顶点都是连通的,则图就是连通图,有向则称强连通图.图中有子图,若子图极大连通则就是连通分量,有向的则称强连通分量.
- 无向图中连通且n个顶点n-1条边叫生成树.有向图中一顶点入度为0其余顶点入度为1的叫有向树.一个有向图由若干个有向树构成生成森林
7.2 图的抽象数据类型
ADT 图(Graph)
Data
顶点的有穷非空集合和边的集合
Operation
CreateGraph(*G,V,VR):按照顶点集V和边弧集VR的定义构造图G
DestroyGraph(*G):图G存在则销毁
LocateVex(G,u):若图中存在顶点u,则返回图中的位置
GetVex(G,v):返回图G中顶点v的值
PutVex(G,v,value):将图G中顶点v赋值value
FirstAdjVex(G,*v):返回顶点v的一个邻接顶点,若顶点在G中无邻接顶点返回空
NextAdjVex(G,v,*w):返回顶点v相对于顶点w的下一个邻接顶点,若w是v的最后一个邻接点则返回空
InsertVex(*G,v):在图G中增添新顶点v
DeleteVex(*G,v):删除图G中顶点v及其相关的弧
InsertArc(*G,v,w):在图G中增添弧<v,w>,若G是无向图,还需要增添对称弧<w,v>
DeleteArc(*G,v,w):在图G中删除弧<v,w>,若G是无向图,则还需要删除对称弧<w,v>
DFSTraverse(G):对图G中进行深度优先遍历,在遍历过程对每个顶点调用
HFSTraverse(G):对图G中进行广度优先遍历,在遍历过程对每个顶点调用
endADT 7.3 图的存储结构
7.3.1 邻接矩阵
图的邻接矩阵:图的邻接矩阵存储方式是用两个数组来表示图.一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息
无向图的邻接矩阵:
arc[i] [j]=1表示从v
i到vj的边存在由图也可知无向图的边数组是一个对称矩阵,主对角线上的值为0
某个顶点的度也就是这个顶点v
i在邻接矩阵中第i行(或第i列)的元素之和.比如顶点v1的度就是1+0+1+0=2求某个顶点v
i的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i] [j]为1就是邻接点
有向图的邻接矩阵:
- 有向图的边数组不是一个对称矩阵,但主对角线上的值依然为0
- 某个顶点v
i的入度是第vi列各数之和.出度是第vi行各数之和 - arc[i] [j]=1表示从v
i到vj的弧存在 - 求某个顶点v
i的所有邻接点同样也是将矩阵中第i行元素扫描一遍,arc[i] [j]为1就是邻接点
网图的邻接矩阵
- ∞表示一个计算机允许的、大于所有边上权值的值
图的邻接矩阵存储的结构代码
typedef char VertexType; //顶点类型应由用户定义 typedef int EdgeType; //边上的权值类型应由用户定义 #define MAXVEX 100 //最大顶点数,应由用户定义 #define INFINITY 65535 //用65535来代表∞ typedef struct { VertexType vexs[MAXVEX]; //顶点表 EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵,可看作边表 int numVertexes,numEdges; //图中当前的顶点数和边数 }MGraph;无向网图的创建代码
/* 建立无向网图的邻接矩阵表示 */ void CreateMGraph(MGraph *G) { int i,j,k,w; printf("输入顶点数和边数:\n"); scanf("%d,%d,&G->numVertexes,&G->numEdges"); //输入顶点数和边数 for(i=0;i<G->numVertexes;i++) //读入顶点信息,建立顶点表 scanf(&G->vexs[i]); for(i=0;i<G->numVertexes;i++) for(j=0lj<G->numVertexes;j++) G->arc[i][j]=INFINITY; //邻接矩阵初始化 } for(k=0;k<G->numEdges;k++) //读入numEdges条边,建立邻接矩阵 { printf("输入边(vi,vj)上的下标i,下标j和权w:\n"); scanf("%d,%d,%d",&i,&j,&w); G->arc[i][j]=w; G->arc[j][i]=G->arc[i][j]; //因为是无向图,矩阵对称 }
7.3.2 邻接表
在图的存储中,我们把数组和链表相结合的存储方法称为邻接表
顶点按编号顺序将顶点数据存储在一维数组中
关联同一顶点的边(以顶点为尾的弧)用线性链表存储
无向图
- 特点:
- 邻接表不唯一
- 若无向图中有n个顶点、e条边,则其邻接表需n个头结点和2e个表结点.适合存储稀疏图
- 特点:
有向图
为了方便确定顶点的入度或以顶点为弧头的弧,我们可以建立一个有向图的逆邻接表,即对每个顶点v
i都建立一个链接为vi为弧头的表
/* 关于结点定义的代码 */ typedef char VertexType; //顶点类型应由用户定义 typedef int EdgeType; //边上的权值类型应由用户定义 typedef struct EdgeNode //边表结点 { int adjvex; //邻接点域,存储该顶点对应的下标 EdgeType weight; //用于存储权值,对于非网图可以不需要 struct EdgeNode *next; //链域,指向下一个邻接点 }EdgeNode; typedef struct VertexNode //顶点表结点 { VertexType data; //顶点域,存储顶点信息 EdgeNode *firstedge; //边表头指针 }VertexNode,AdjList[MAXVEX]; typedef struct { AdjList adjList; int numVertexes,numEdges; //图中当前顶点数和边数 }GraphAdjList;/* 建立图的邻接表结构 */ void CreateALGraph(GraphAdjList *G) { int i,j,k; EdgeNode *e; printf("输入顶点数和边数:\n"); scanf("%d,%d",&G->numVertexes,&G->numEdges); //输入顶点数和边数 for(i=0;i<G->numVertexes;i++) //读入顶点信息,建立顶点表 { scanf(&G->adjList[i].data); //输入顶点信息 G->adjList[i].firstedge=NULL; //将边表置为空表 } for(k=0;k<G->numEdges;k++) //建立边表 { printf("输入边(vi,vj)上的顶点序号:\n"); scanf("%d,%d",&i,&j); //输入边上的顶点序号 e=(EdgeNode *)malloc(sizeof(EdgeNode)); //向内存申请空间生成边表结点 e->adjvex=j; //邻接序号为j e->next=G->adjList[i].firstedge; //将e指针指向当前顶点指向的顶点 G->adjList[i].firstedge=e; //将当前顶点的指针指向e e=(EdgeNode *)malloc(sizeof(EdgeNode)); //向内存申请空间生成边表结点 e->adjvex=i; //邻接序号为i e->next=G->adjList[j].firstedge; //将e指针指向当前顶点指向的结点 G->adjList[j].firstedge=e; //将当前顶点的指针指向e } }对于n个顶点e条边来说,时间复杂度为O(n+e)
7.3.3 十字链表
- 十字链表是有向图的另一种链式存储结构
- 有向图中的每一条弧对应十字链表中的一个弧结点,同时有向图中的每个顶点在十字链表中对应有一个结点,叫做顶点结点
7.3.4 邻接多重表
- 邻接多重表是无向图的另一种链式存储结构
7.4 图的遍历
- 从图中某一顶点出发访编图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历
7.4.1 深度优先遍历
深度优先遍历(Depth_First_Search),也称为深度优先搜索,简称为DFS
深度优先遍历是从图中某个顶点v出发,访问此顶点,然后从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到.若图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止
邻接矩阵结构代码如下
typedef int Boolean; //Boolean是布尔类型,其值是TRUE或FALSE Boolean visited[MAX]; //访问标志的数组 /* 邻接矩阵的深度优先递归算法 */ void DFS(MGraph G,int i) { int j; visited[i]=TRUE; printf("%c",G.vexs[i]); //打印顶点,也可以其他操作 for(j=0;j<G.numVertexes;j++) if(G.arc[i][j]==1&&!Visited[j]) DFS(G,j); //对未访问的邻接顶点递归调用 } /* 邻接矩阵的深度遍历操作 */ void DFSTraverse(MGraph G) { int i; for(i=0;i<G.numVertexes;i++) visited[i]=FALSE; //初始所有顶点状态都是未访问过状态 for(i=0;i<G.numVertexes;i++) if(!visited[i]) //对未访问过的结点调用DFS,若是连通图,只会执行一次 DFS(G,i); }邻接表结构代码如下
/* 邻接表的深度优先递归算法 */ void DFS(GraphAdjList GL,int i) { EdgeNode *p; visited[i]=TRUE; printf("%c",GL->adjList[i].data); //打印顶点,也可以其他操作 p=GL->adjList[i].firstedge; while(p) { if(!visited[p->adjvex]) DFS(GL,p->adjvex); //对未访问的邻接顶点递归调用 p=p->next; } } /* 邻接表的深度遍历操作 */ void DFSTraverse(GraphAdjList GL) { int i; for(i=0;i<GL->numVertexes;i++) visited[i]=FALSE; //初始所有顶点状态都是未访问过状态 for(i=0;i<GL->numVertexes;i++) if(!visited[i]) //对未访问过的顶点调用DFS,若是连通图,只会执行一次 DFS(GL,i); }对于n个顶点e条边的图来说,邻接矩阵时间复杂度O(n²),邻接表时间复杂度O(n+e)
7.4.2 广度优先遍历
广度优先遍历(Breadth_First_Search),又称为广度优先搜索,简称BFS.
广度优先遍历是从图的某一结点出发,首先依次访问该结点的所有邻接顶点vi
1,vi2,...vin再按这些顶点被访问的先后次序依次访问与他们相邻接的所有未被访问的顶点,重复此过程直至所有顶点均被访问为止/* 邻接矩阵的广度遍历算法 */ void BFSTraverse(MGraph.G) { int i,j; Queue Q; for(i=0;i<G.numVertexes;i++) visited[i]=FALSE; InitQueue(&Q); //初始化一辅助用的队列 for(i=0;i<G.numVertexes;i++) //对每一个顶点做循环 { if(!visited[i]) //若是未访问过就处理 { visited[i]=TRUE; //设置当前顶点访问过 printf("%c",G.Vexs[i]); //打印顶点,也可以其他操作 EnQueue(&Q,i); //将此顶点入队列 while(!QueueEmpty(Q)) //若当前队列不为空 { DeQueue(&Q,&i); //将队中元素出队列,赋值给i for(j=0;j<G.numVertexes;j++) { //判断其他顶点若与当前顶点存在边且未访问过 if(G.arc[i][j]==1&&!visited[j]) { visited[j]=TRUE; //将找到的此顶点标记为已访问 printf("%c",G.vexs[j]); //打印顶点 EnQueue(&Q,j); //将找到的此顶点入队列 } } } } } }/* 邻接表的广度遍历算法 */ void BFSTraverse(GraphAdjList GL) { int i; EdgeNode *p; Queue Q; for(i=0;i<GL->numVertexes;i++) visited[i]=FALSE; InitQueue(&Q); for(i=0;i<GL->numVertexes;i++) { if(!visited[i]) { visited[i]=TRUE; printf("%c",GL->adjList[i].data); //打印顶点,也可以其他操作 EnQueue(&Q,i); while(!QueueEmpty(Q)) { DeQueue(&Q,&i); p=GL->adjList[i].firstedge; //找到当前顶点边表链表头指针 while(p) { if(!visited[p->adjvex]) //若此顶点未被访问 { visited[p->adjvex]=TRUE; printf("%c",GL->adjList[p->adjvex].data); EnQueue(&Q,p->adjvex); //将此顶点入队列 } p=p->next; //指针指向下一个邻接点 } } } } }
7.5 最小生成树
- 生成树:所有顶点均由边连接在一起,但不存在回路的图
- 构造连通网的最小代价生成树称为最小生成树
7.5.1 普里姆算法
首先随意找一个顶点，一般都是v1，然后找到与v1相连的权值最小的边（若有多条，则随机选取一条），然后找与这两个点相连的有最小权值的边，然后与找这三个点相连权值最小的边，一直重复，直到有n-1条边，并且连接完所有的顶点，注意，不能形成环。
算法时间复杂度为O(n²),更适合稠密图
7.5.2 克鲁斯卡尔算法
基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。
时间复杂度为：O（eloge） 边数e越大，所耗费时间越长，则适合稀疏图
7.6 最短路径
- 对于网图来说,最短路径,是指两顶点之间经过的边上权值之和最少的路径,并且我们称路径上的第一个顶点是源点,最后一个顶点是终点
7.6.1 迪杰斯特拉算法
算法思想:
- 1.初始化:先找出从源点v
0到各终点vk的直达路径(v0,vk),即通过一条弧到达的路径 - 2.选择:从这些路径中找出一条长度最短的路径(v
0,u). - 3.更新:然后对其余各条路径进行适当调整:
- 若在图中存在弧(u,v
k),且(v0,u)+(u,vk)<(v0,vk),则以路径(u,vk)代替(v0,vk)
- 若在图中存在弧(u,v
- 1.初始化:先找出从源点v
时间复杂度O(n³)
7.6.2 弗洛伊德算法
第8章 查找
8.1 查找概论
- 查找表是由同一类型的数据元素(或记录)构成的集合.
- 关键字是数据元素中某个数据项的值
- 若此关键字可以唯一地标识一个记录,则称此关键字为主关键字
- 可以识别多个数据元素(或记录)的关键字,我们称为次关键字
- 查找就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)
- 查找表按照操作方式可以分为静态查找表和动态查找表
8.2 顺序表查找
- 顺序查找又叫线性查找,是最基本的查找技术
8.2.1 顺序表查找语法
/* 顺序查找,a为数组,n为要查找的数组个数,key为要查找的关键字 */
int Sequential_Search(int *a,int n,int key)
{
int i;
for(i=1;i<=n;i++)
{
if(a[i]==key)
return i;
}
return 0;
} 8.2.2 顺序表查找优化
/* 有哨兵顺序查找 */
int Sequential_Search2(int *a,int n,int key)
{
int i;
a[0]=key; //设置a[0]为关键字值,我们称之为哨兵
i=n; //循环从数组尾部开始
while(a[i]!=key)
{
i--;
}
return i; //返回0则说明查找失败
} - 放置哨兵免去了在查找过程中每一次比较后都要判断查找位置是否越界,提高了效率
8.3 有序表查找
8.3.1 折半查找
折半查找又称为二分查找.它的前提是线性表中的记录必须是关键码有序(通常是从小到大有序),线性表必须采用顺序存储.折半查找的基本思想是:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找.不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止.
/* 折半查找 */ int Binary_Search(int *a,int n,int key) { int low,high,mid; low=1; //定义最低下标为记录首位 high=n; //定义最高下标为记录末位 while(low<=high) { mid=(low+high)/2; //折半 if(key<a[mid]) //若查找值比中值小 high=mid-1; //最高下标调整到中位下标小一位 else if(key>a[mid]) //若查找值比中值大 low=mid+1; //最低下标调整到中位下标大一位 else return mid; //若相等则说明mid即为查找到的位置 } return 0; }折半算法的时间复杂度为O(logn),但前提条件是需要有序表顺序存储
折半查找在查找不成功和给定值进行比较的关键字个数最多为[log
2n]+1
8.4 线性索引查找
8.4.1 分块查找
分块查找又称为索引顺序查找，这是一种性能介于顺序查找和折半查找之间的一种查找方法
分块查找，又称为索引顺序查找，吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找
基本思想：将查找表分为若干个子块，块内元素可以无序，块间元素有序
块间有序含义： 若a<b，则第 b 块中所有记录的关键字均大于第 a 块中的最大关键字
建立“索引表”，每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序
优缺点：
- 优点：插入和删除比较容易，无需进行大量的移动。
- 缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算。
- 适用情况：如果线性表既要快速查找又经常动态变化，则可采用分块查找
8.5 树表的查找
- 顺序查找、二分(折半)查找和索引查找都是静态查找表，其中二分查找的效率最高。静态查找表的缺点是当表的插入或删除操作频繁时,为维护表的有序性，需要移动表中很多记录。这种由移动记录引起的额外时间开销，就会抵消二分查找的优点（二分查找和分块查找只适用于静态查找表）。若要对动态查找表进行高效率的查找，可以使用树表。以二叉树或树作为表的组织形式，称为树表。
8.5.1 二叉排序树
二叉排序树:二叉排序树又称二叉查找树,它具有以下性质:
- (1) 若它的左子树不为空,则左子树所有节点的值小于根结点
- (2) 若它的右子树不为空,则根结点的值小于所有右子树结点的值
- (3) 它的左右子树分别为二叉排序树
8.5.2 二叉排序树查找操作
/* 二叉树的二叉链表结点结构定义 */ typedef struct BiTNode //结点结构 { int data; //结点数据 struct BiTNode *lchild,*rchild; //左右孩子指针 }BiTNode,*BiTree;/* 递归查找二叉排序树T中是否存在key, 指针f指向T的双亲,其初始调用值为NULL 若查找成功,则指针p指向该数据元素结点,并返回TRUE 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */ Status SearchBST(BiTree T,int key,BiTree f,BiTree *p) { if(!T) //查找不成功 { *p=f; return FALSE; } else if(key==T->data) //查找成功 { *p=T; return TRUE; } else if(key<T->data) { return SearchBST(T->lchild,key,T,p); //在左子树继续查找 } else return SearchBST(T->rchild,key,T,p); //在右子树继续查找 }- 时间复杂度O(log
2n)
8.6 平衡二叉树(AVL树)
平衡二叉树是一种二叉排序树,其中每一个结点的左子树和右子树的高度差至多等于1
它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树节点的平衡因子BF定义为该节点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有节点的平衡因子只可能为-1,0,1.
只要二叉树上有一个节点的平衡因子的绝对值大于1，那么这颗平衡二叉树就失去了平衡。
8.7 散列表
- 散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key).
- 只需要通过某个函数f,使得存储位置=f(关键字),把这种函数称为散列函数,又称为哈希(Hash)函数.采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表
- 散列技术既是一种存储方法,也是一种查找方法
- 散列技术最适合的求解问题是查找与给定值相等的记录
- 在散列函数中有可能碰到两个关键字key
1≠key2,但是却有f(key1)=f(key2),这种现象我们称为冲突,并把key1和key2称为这个散列函数的同义词
8.7.1 散列函数的构造方法
- 一个好的散列函数通常具有:
- 1.计算简单
- 2.散列地址分布均匀
- 构造方法:
- 1.数字分析法
- 2.平方取中法
- 3.折叠法
- 4.除留余数法:H(key) = key%p 最常用
- 处理冲突的方法
- 1.开放地址法
- ①线性探测法
- ②二次探测法
- ③伪随机探测法
- 2.链地址法:将所有关键字为同义词的记录存储在一个单链表中
- 1.开放地址法
8.7.2 散列表的查找
- 算法步骤:
- 1.给定待查找的关键字key,根据造表时设定的散列函数计算H
0=H(key) - 2.若单元H
0为空,则所查元素不存在 - 3.若单元H
0中元素的关键字为key,则查找成功 - 4.否则重复下述解决冲突的过程:
- 按处理冲突的方法,计算下一个散列地址H
i - 若单元H
0为空,则所查元素不存在 - 若单元H
0中元素的关键字为key,则查找成功
- 按处理冲突的方法,计算下一个散列地址H
- 散列表的装填因子α定义为:α=表中填入的记录数/散列表的长度
- 1.给定待查找的关键字key,根据造表时设定的散列函数计算H
第9章 排序
9.1 排序的基本概念与分类
9.1.1 排序的基本概念
- 排序 ：就是一系列数据，按照某个关键字（例如：销量，价格），进行递增或者递减的顺序排列起来
- 排序的稳定性 ：能保证两个关键字相等的数，经过排序之后，其在序列的前后位置顺序不变。（A1=A2，排序前A1在A2前面，排序后A1还在A2前面），则称这种排序是稳定的。反之，若排序后前后位置顺序变化，则称这种排序是不稳定的
- 内部排序和外部排序 ：待排序记录全部存放在计算机内存中进行排序的过程称为内部排序；在排序过程中需对外存进行访问的排序过程
9.1.2 内部排序方法的分类
- 内部排序可以分为以下几类
- (1) 插入类
- (2) 交换类
- (3) 选择类
- (4) 归并类
- (5) 分配类
9.1.3 待排序记录的分配方式
- 顺序表：实现排序需要移动记录
- 链表：实现排序不需要移动记录，仅需修改指针即可。这种排序方式称为链表排序
- 地址排序：在排序过程中不移动记录本身，而移动地址向量这些记录的“地址”，在排序结束之后再按照地址向量中的值调整记录的存储位置
9.2 插入排序
9.2.1 直接插入排序
直接插入排序是一种最简单的排序方法,其基本操作是将一条记录插入到已排好序的有序表中.从而得到一个新的、记录数量增1的有序表
/* 对顺序表做直接插入排序 */ void InsertSort(SqList *L) { int i,j; for(i=2;i<=L->length;i++) { if(L->r[i]<L->r[i-1]) //需将L->r[i]插入有序子表 { L->r[0]=L->r[i]; //设置哨兵 for(j=i-1;L->r[j]>L->r[0];j--) L->r[j+1]=L->r[j]; //记录后移 L->r[j+1]=L->r[0]; //插入到正确位置 } } }时间复杂度O(n²),空间复杂度O(1)
特点:
- 1.稳定性:稳定
- 2.也适用于链式存储结构,只是在单链表上无需移动记录,只需修改相应的指针
- 3.更适用于初始化基本有序的情况
9.2.2 折半插入排序
- 原理：折半插入算法是对直接插入排序算法的改进,排序原理同直接插入算法
- 区别：以从小到大排序为例,首先用key存储需要排序的数据
- 第一步：折半查找——用low、mid、high划分两个区域【low，mid-1】和【mid+1，high】
- 第二步：判断——如果key值小于序列的中间值【mid】,则代表key值应该插入左边的区域【low，mid-1】,然后对【low，mid-1】再重复划分区域，直到low>high为止
- 第三步：插入——最后的插入位置应该是high+1,我们只需要先将high之后位置的数据整体后移,然后将key赋值给【mid+1】,即完成插入。
- 稳定性:稳定
- 因为要进行折半查找,所以只能用于顺序结构,不能用于链式结构
- 适合初始记录无序、n较大的时候
9.2.3 希尔排序
- 时间复杂度：n(log
2n)² - 空间复杂度：也是只需要一个辅助空间 r[0] ,所以空间复杂度为O(1)
- 特点：
- 稳定性：因为记录跳跃式地移动,所以不稳定
- 只适用于顺序结构,不能用于链式结构
- 适用于初始记录无序、n较大的情况
9.3 交换排序
9.3.1 冒泡排序
/* 对顺序表L做冒泡排序 */ void BubbleSort(SqList *L) { int i,j; for(i=1;i<L->length;i++) { for(j=L->length-1;j>=i;j--) //注意j是从后往前循环 { if(L->r[j]>L->r[j+1]) //若前者大于后者 { swap(L,j,j+1); //交换L->r[j]与L->r[j+1]的值 } } } }/* 对顺序表L作改进冒泡算法 */ void BubbleSort2(SqList *L) { int i,j; Status flag=TRUE; //flag用来作为标记 for(i=1;i<L->length&&flag;i++) //若flag为true则退出循环 { flag=FALSE; //初始为false for(j=L->length-1;j>=i;j--) { if(L->r[j]>L->r[j+1]) { swap(L,j,j+1); //交换L->r[j]与L->r[j+1]的值 flag=TRUE; //如果有数据交换,则flag为true } } } } /* 可以避免因已经有序的情况下的无意义循环判断 */- 时间复杂度O(n²),空间复杂度O(1)
9.3.2 快速排序
- 时间复杂度：O(nlog
2n),空间复杂度：最好情况下的空间复杂度为：O(log2n)，最坏情况下为O(n) - 特点：
- 记录非顺次的移动导致排序方法是不稳定的
- 排序过程中需要定位表的下界和上界，所以适合用于顺序结构，很难用于链式结构
- 当n较大时，在平均情况下快速排序是所有内部排序方法中速度最快的一种，所以其适合初始记录无序、n较大时的情况
9.4 选择排序
9.4.1 简单选择排序
简单选择排序法就是通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1≤i≤n)个记录交换之
/* 对顺序表L作简单选择排序 */ void SelectSort(SqList *L) { int i,j,min; for(i=1;i<L->length;i++) { min=i; //将当前下标定义为最小值下标 for(j=i+1;j<=L->length;j++) //循环之后的数据 { if(L->r[min]>L->r[j]) //如果有小于当前最小值的关键字 min=j; //将此关键字的下标赋值给min } if(i!=min) //若min不等于i,说明找到最小值,交换 swap(L,i,min); //交换L->r[i]与L->r[min]的值 } }时间复杂度：O(n²),空间复杂度:O(1)
特点：
- 稳定性：就选择排序方法来讲是稳定的，但教程中实现的方法是不稳定的
- 可用于链式存储结构
- 移动记录次数较少，当每一记录占用的空间较多时，此方法比直接插入排序快
9.4.2 树形选择排序
- 树形选择排序，又称锦标赛排序,从两个节点中选出最小值作为他们的父节点形成树
- 缺点： 1、与“∞”的比较多余； 2、辅助空间使用多。于是产生了堆排序
9.4.3 堆排序
- 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大根堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小根堆。
- 堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列
9.5 归并排序
- 归并排序就是利用归并的思想实现的排序方法.它的原理是假设初始序列含有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到[n/2] ([x]表示不小于x的最小整数)个长度为2或1的有序子序列;再两两归并,……,如此重复,直至得到一个长度为n的有序序列为止,这种排序方法称为2路归并排序
- 时间复杂度O(nlog
2n),空间复杂度O(n) - 特点:
- 是稳定排序
- 可用于链式结构
9.6 基数排序
基数排序是从最低位（个位）开始进行，按关键字的不同收集，然后按第二低位（十位）开始进行，按关键字的不同收集，若有些数没有更低位，则按0收集
特点:
- 是稳定排序
- 顺序结构和链式结构均可用
- 基数排序需要知道各级关键字的取值范围
9.7 排序算法对比
查看16道真题和解析
投递荣耀等公司9个岗位