数据结构与算法全套教学课件

数据结构与算法全套可编辑PPT课件课程内容第1章数据结构概述第2章线性表第3章栈和队列第4章串第5章数组第6章树和二叉树第7章图第8章查找第9章排序第1章数据结构概述数据结构课程主要讨论数据的表示（数据的结构）和数据处理的基本方法（算法）。要想成为一个优秀的程序设计人员，至少需要以下三个条件：①

能够熟练地选择和设计各种数据结构和算法。

②至少要能够熟练地掌握一门程序设计语言。

③熟知所涉及的相关应用领域的知识。3【本章重点】①数据结构及相关概念；②数据的逻辑结构和存储结构，二者的关系；③算法及特性；④算法的时间复杂度和空间复杂度的概念。4【本章难点】①抽象数据类型的理解和使用；②描述算法的工具；③算法的时间复杂度分析与计算。5【本章内容】数据结构的基本概念算法习题161.1数据结构的基本概念软件开发的三个阶段（1）分析阶段：对问题进行分析，抽象出数据模型，形成求解问题的基本思路，确定解决问题的方案；（2）设计阶段：将数据以及数据之间的关系存储到计算机的内存中，设计数据处理的算法；（3）实现阶段：将算法转换为用某种程序设计语言编写的程序，并进行测试、修改，直到得到问题的解答。7关于数据结构的基本术语数据是信息的载体，它是描述客观事物的数字、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。例如，一个代数方程的求解程序中所用的数据是整数和实数；一个编译程序或文本编辑程序中所使用的数据是字符串。随着计算机应用领域的扩大，数据的含义更为广泛，如图像、声音等都可以通过编码而属于数据的范畴。数据元素是数据的基本单位。有些情况下，数据元素也称为元素、结点、顶点、记录。数据项是具有独立含义的，不可再分割的最小标识单位。一个数据元素可以由若干个数据项组成，8数据结构（DataStructure）是数据元素之间的相互关系，即数据的组织形式。一般来说，数据结构所研究的主要内容包括以下三个方面：（1）数据的逻辑结构——数据元素之间的逻辑关系。（2）数据的存储结构——数据元素及其关系在计算机中的存储方式，数据的存储结构又称为数据的物理结构。（3）数据的运算——对数据施加的操作，即数据的运算。9数据的逻辑结构（1）集合：数据元素之间只是“属于同一集合”的关系。（2）线性结构：数据元素之间存在“一对一”的前后顺序关系，除第一个元素和最后一个元素之外，其余元素都有唯一的一个直接前驱元素和唯一的一个直接后继元素。（3）树形结构：数据元素之间存在“一对多”的层次关系，除最顶层的元素之外，其余元素都有若干个直接给后继元素。（4）图结构：数据元素之间存在“多对多”的任意关系，每个元素都有若干个直接前驱元素和若干个直接后继元素。10数据的存储结构（1）顺序存储结构

元素之间的逻辑关系由存储单元的邻接关系来体现。通常顺序存储结构是借助于程序语言的数组（又称为向量）来描述的。

该方法主要应用于线性数据结构，非线性的数据结构也可以通过某种线性化的方法来实现顺序存储。（2）链式存储结构

通过元素存储地址的指针表示数据元素之间的逻辑关系，即逻辑上相邻的元素在物理位置上不一定相邻。通常要借助于程序语言的指针类型来描述它。（3）索引存储结构

在存储数据元素的同时，还需要有索引表，索引表中的每一项称为索引项，其一般形式是（关键字，地址），关键字是能够唯一标识一个元素的那些数据项。（4）散列存储结构

根据数据元素的关键字计算出该元素的存储地址。又称为计算寻址的方式。111.2算法算法的定义

算法是对特定问题求解步骤的描述，是指令的有限序列。算法的性质（1）输入性：0至多个输入。（2）输出性：1至多个输出。（3）有穷性:对于合法的输入值，算法在执行有穷步之后结束。（4）确定性:对于相同的输入执行相同的路径，即对于相同的输入只能得出相同的输出。（5）可行性:用于描述算法的操作都是足够基本的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。12（1）自然语言

优点：容易理解；缺点：不够严谨，容易出现二义性。（2）流程图

优点：直观易懂；缺点：严密性不如程序设计语言，灵活性不如自然语言。（3）程序设计语言

优点：描述算法能够由计算机执行；缺点：抽象性差，设计者在设计算法时过于受到程序设计语言的语法规则限制，往往忽视了算法的正确性和逻辑性。（4）伪代码

伪代码是介于自然语言和高级语言之间的方法，例如用类C语言来描述算法。优点：重点给出算法的逻辑，并且不受语言的语法规则限制。【例】（P8）用伪代码描述求两个正整数的最大公约数。13描述算法的工具对算法的评价标准

通常从正确性、易读性、健壮性和高效性等四个方面评价算法的质量。算法的高效性

算法的高效性包括时间特性和空间特性。时间特性是指执行算法所需要的计算时间长短。空间特性则是执行算法所需要的辅助存储空间大小。（1）算法时间特性的分析

一个算法所需的计算时间，应当是该算法中每条语句的执行时间之和，而每条语句的执行时间是该语句的执行次数（称为频度）与该语句执行一次所需时间的乘积。

我们通过算法的时间复杂度来衡量算法的时间特性。14算法时间复杂度的计算【例1.2】求两个n阶方阵的乘积C＝A×B，其算法如下：＃definen自然数voidMatrixmlt(intA[n][n],intB[n][n],intC[n][n]){ inti,j,k;

语句频度

for(i=0;i<n;i++) //语句①

n+1

for(j=0；j<n;j++){ //语句②

n(n+1)

C[i][j]=0; //语句③

n2

for(k=0;k<n;k++)//语句④

n2(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j];//语句⑤

n3 }}

算法中所有语句的频度之和为T(n)=2n3+3n2+2n+1。算法的语句频度之和T(n)是矩阵阶数n的函数，n是算法求解方阵乘积问题的规模。15

一般情况下，算法中基本操作重复执行的时间是问题规模n的某个函数f(n)，算法的时间复杂度记为T(n)=O(f(n))它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，f(n)一般是算法中频度最大的语句频度。例如，算法Matrixmlt的时间复杂度是T(n)=O(n3)，这里的f(n)=n3是该算法中语句⑤的频度。由此可见，当有循环嵌套时，算法的时间复杂度是由最内层语句的频度f(n)决定的。

计算算法的时间复杂度要考虑问题的规模。16【例1.3】交换a和b的值。temp=a;a=b;b=temp;

以上三条单个语句的频度都为1，该算法的执行时间是一个与问题规模n无关的常数，时间复杂度记作T(n)=O(1)。事实上，只要算法的执行时间不随着问题的规模增加而增长，即使算法中有成百上千条语句，其时间复杂度也只是O(1)。17【例】在一维数组A[n]中顺序查找值为k的元素，顺序查找算法如下：intFind(intA[],intn,intk){ for(i=0;i<n;i++) if(A[i]==k)break; returni;}

算法从A[0]开始查找，如果A[0]的值就等于k，那么比较一次就查找到了，这是最好情况；如果A[n-1]的值等于k，则需要比较n次才能查找到，这是最坏情况；平均情况下需要比较(n+1)/2次。

计算算法的时间复杂度要考虑最坏情况。1819【例1.4】判断n是否为素数。voidprime(intn){ inti=2;

while((n%i)!=0&&i<sqrt(n))

i++;

if(i>=sqrt(n))printf("%d是素数",n);

elseprintf("%d不是素数",n);}设语句i++；的频度为f(n)，由i<sqrt(n)可知f(n)<sqrt(n)。时间复杂度应考虑最坏的情况，所以20【例1.5】变量计数。 i=1；1 while(i<=n)i=i*2;f(n)

由于2f(n)≤n，即f(n)≤log2n，取最大值f(n)=log2n，T(n)=O(f(n))=O(log2n)常见的时间复杂度按数量级递增排列：常量阶O(1)<对数阶O(log2n)<线性阶O(n)<线性对数阶O(nlog2n)<平方阶O(n2)<立方阶O(n3)<…<k次方阶O(nk)<指数阶O(2n)算法的空间复杂度算法的空间复杂度是指在算法执行过程中所需要的辅助存储空间数量。辅助存储空间是除算法本身和输入输出数据所占存储空间之外，算法运行时临时开辟的存储空间，记为：S(n)=O(f(n))

其中n为问题的规模，分析方法与算法的时间复杂度类似。21算法的易读性

一个高质量的算法除了正确和运行效率高之外，还对算法的易读性有一定的要求。算法的易读性主要体现在算法的结构、代码的书写格式以及注释等方面。（1）算法的结构

解决某个较为复杂问题的算法通常也是由一个个模块组成的，而每个模块的功能相对独立。尽可能做到高内聚、低耦合。（2）代码书写格式

采用缩进的方式突出分支、循环、嵌套等结构，这样可以清晰地体现算法的视觉组织。（3）注释

注释就是对算法进行必要的说明，帮助我们理解算法。注释分为序言性注释和功能性注释。2223

习题1作业

习题1中的第一、二、三题写在教材上，尽可能都做，会在上课时抽查。习题1中的第四题写在作业本上，作业本要交。四、简答题（1）、（2）、（3）、（4）、（5）第2章线性表

线性表是一种典型的线性结构，是简单而且常用的数据结构。线性表的顺序和链式存储结构以及基本运算的实现又是后面各章的基础。24【本章重点】①线性表的定义和线性表的基本运算；②顺序存储和链式存储的基本思想；③基于顺序表和单链表基本运算的实现；④基于顺序表和单链表基本运算的时间特性和空间特性。⑤顺序表和链表之间的比较。25【本章难点】①关于顺序表、单链表、循环链表和双向链表的算法设计及应用；②模块之间参数传递的问题。26【本章内容】线性表的逻辑结构线性表的顺序存储结构线性表的链式存储结构顺序表与链表的比较习题2272.1线性表的逻辑结构线性表的定义

线性表是由n（n≥0）个元素组成的有限序列，n为线性表的长度。当n=0时称为空表，当n>0时称为非空表，记为L=(a1,…,ai-1,ai,ai+1,…,an)需要注意的几点（1）线性表中各元素具有相同的特性（2）i是元素ai在线性表中的位序，即位置序号，位序从1开始（3）对于一个非空线性表，有且仅有一个开始结点a1；有且仅有一个终端结点an；除第一个结点外，其余结点ai（2≤i≤n)均有且仅有一个直接前驱ai-1；除最后一个结点外，其余结点ai（1≤i≤n-1)均有且仅有一个直接后继ai+128线性表的基本运算（1）InitList(&L)线性表初始化

初始条件：线性表L不存在。

运算结果：构造一个空的线性表。（2）SetNull(L)置空表，

初始条件：线性表L已存在。

运算结果：将表L置为空表。（3）Length(L)求表长度

初始条件：线性表L已存在。

运算结果：返回表L中的数据元素个数。29每一种数据的逻辑结构，对应一组基本运算。这里只是给出抽象的运算，而运算的具体实现，只有在确定了数据的存储结构之后才能够考虑。（4）Get(L,i)取元素值

初始条件：线性表L已存在。

运算结果：返回表L中第i个数据元素ai的值或元素的位置信息。（5）Locate(L,x)定位，按值查找

初始条件：线性表L已存在。

运算结果：若表L中存在一个或多个值为x的元素，返回第一个查找到的数据元素的位序，否则返回一个特殊值。（6）Insert(L,x,i)插入

初始条件：线性表L已存在。

运算结果：在表L中第i个位置上插入值为x的元素，若插入成功，表长加1。（7）Delete(L,i)删除

初始条件：线性表L已存在。

运算结果：删除表L中第i个数据元素，若删除成功，表长减1。30函数的参数L是指向线性表结构体的指针。对线性表的基本运算可以分为三类，所对应的函数参数是不同的。（1）线性表初始化运算使得线性表从不存在到存在，显然指针L的指向发生了变化；（2）置空表、插入和删除运算使得线性表的内容发生了变化，但指针的指向并不会发生变化；（3）求表长度、取元素值和定位运算对于指针L和表的内容都没有发生变化。基本运算应用的举例【例2.1】将线性表A按元素值奇、偶数拆分成两个表，A表存放奇数，B表存放偶数。voidseparate(Linear_list*La,Linear_list*Lb)//已有线性表La和空线性表Lb{

inti=1,j=1,x; while(i<=Length(La)) { x=Get(La,i);//取ai

if(x%2==0) { Insert(Lb,x,j); j++; Delete(La,i);

}//ai是偶数，插入到B表末尾，并从A表中删除

elsei++;//ai是奇数，仍放在A表中

}}说明: （1）将偶数插入到B表，A表只保留奇数

（2）时间复杂度是O(Length(La))312.2线性表的顺序存储结构线性表的顺序存储结构又称为顺序表，是把线性表的元素按逻辑顺序依次存放在一组地址连续的存储单元里。顺序表中元素地址的计算

假设顺序表中每个元素占用c个存储单元，其中的第一个单元的存储地址则是该元素的存储地址，顺序表中开始元素a1的存储地址是Loc(a1)，那么元素ai的存储地址Loc(ai)可通过下式计算：Loc(ai)=Loc(a1)+(i-1)*c（1≤i≤n）

其中Loc(a1)是顺序表的第一个元素a1的存储地址，称为顺序表的起始地址或基地址。可以对顺序表顺序存取或随机存取。32顺序表的结构类型定义#definemaxsize1024typedefintdatatype;typedefstruct{ datatypedata[maxsize];//采用一维数组存储线性表 intlast;//顺序表当前的长度}sequenlist;33线性表顺序存储的两种方式

由于线性表结点的位序从1开始，而C语言中数组的下标从0开始，关于线性表中数据元素的位序（逻辑位置）和存放它的数组下标（物理位置）之间的关系通常有两种处理方式。（1）从下标为0的数组元素开始存放，则结点的位序等于数组元素的下标加一。（2）从下标为1的数组元素开始使用，这样结点的位序和数组的下标是相等的，使用起来会更简单自然一些，下标为0的元素不用或用作其它用途。这里我们约定采用第一种方式。34位序=下标+1，下标=位序-1位序=下标若L是指向顺序表的指针，则a1~an分别存储在L->data[0]~L->data[L->last-1]中。L->data[i-1]是元素ai；L->last表示线性表当前的长度。基本运算在顺序表上的实现1、顺序表的初始化

在函数中建立一个空顺序表L，指针L从没有指向顺序表变为指向一个空表，显然指针L的指向发生了变化。如何将这一变化的结果带回到主调函数，我们给出以下三种方式，并进行比较。【算法2.1】通过函数返回值将结果带回到主调函数。sequenlist*InitList(){ sequenlist*L=(sequenlist*)malloc(sizeof(sequenlist));//分配顺序表的动态存储空间 L->last=0;//将表的长度置为0 returnL;}//时间复杂度为O(1)35在函数中定义的指针指向顺序表，指针作为函数的返回值。【算法2.2】采用指向指针的指针作为函数参数，通过函数的参数将结果带回到主调函数。voidInitList(sequenlist**L){ *L=(sequenlist*)malloc(sizeof(sequenlist));//第二级指针*L指向顺序表 *L->last=0;//将*L所指向的顺序表长度置0}//时间复杂度为O(1)36第一级指针L指向第二级指针*L，L的指向没有改变，而*L的指向发生了变化，函数运行结束，将*L的指向带回到主调函数。【算法2.3】采用指针的引用作为函数参数，通过函数的参数将结果带回到主调函数。voidInitList(sequenlist*&L)//指针的引用作为参数{ L=(sequenlist*)malloc(sizeof(sequenlist)); L->last=0;}//时间复杂度为O(1)37参数的类型使用了C++语言中的指针类型的引用，从而可以将指针所指向的结构体动态存储带回到主调函数。2、在顺序表中插入一个元素

在线性表的第i（1≤i≤n+1）个位置上插入一个新结点x，并且使表的长度加一，即使 (a1,…,ai-1,ai,…an)变为长度是n+1的线性表 (a1,…,ai-1,x,ai,…an)38【算法2.4】在顺序表的第i个位置上插入一个新结点x。intInsert(sequenlist*L,datatypex,inti)//将新结点插入顺序表的第i个位置。插入成功，返回1；不成功，返回0{ if(L->last==maxsize){print("表已满");return0;} elseif(i<1||i>L->last+1){print("非法插入位置");return0;} else{ for(j=L->last;j>=i;j--)L->data[j]=L->data[j-1];//结点后移 L->data[i-1]=x;//插入到L->data[i-1]中 L->last++;//表长度加1 return1;}}39

3、在顺序表中删除一个元素

将表的第i（1≤i≤n）个结点删去，并且使表的长度减一。即使 (a1,…,ai-1,ai,ai+1,…an)变成长度为n-1的线性表 (a1,…,ai-1,ai+1,…an)40【算法2.5】删除顺序表的第i个结点。intDelete(sequenlist*L,inti)//删除顺序表的第i个结点。删除成功，返回1；不成功，返回0{ intj; if((i<1)||(i>L->last)){print("非法删除位置");return0;} else{

for(j=i;j<=L->last-1;j++)L->data[j-1]=L->data[j];//结点前移

L->last--;//表长度减1

return1； }}41

【例2.2】有顺序表A和B，其表中元素按由小到大的顺序排列。编写一个算法将它们合并为顺序表C，并且表C中的元素也按由小到大的顺序排列。voidmerge(sequenlist*A,sequenlist*B,sequenlist*&C){//在函数中产生顺序表C，为了将C的指向带回到主调函数，参数采用指针的引用 if(A->last+B->last>maxsize)rintf("Error!\n"); else{ C=(sequenlist*)malloc(sizeof(sequenlist)); i=0; j=0; k=0; while(i<A->last&&j<B->last) if(A->data[i]<B->data[j]) C->data[k++]=A->data[i++]; else C->data[k++]=B->data[j++]; while(i<A->last) C->data[k++]=A->data[i++]; //将表A的剩余元素复制完 while(j<B->last) C->data[k++]=B->data[j++]; //将表B的剩余元素复制完 C->last=k; }}42顺序表的应用实例——一个完整的程序

问题的描述：首先建立一个顺序存储结构的线性表，然后删除顺序表中所有值为x的结点。432.3线性表的链式存储结构顺序存储结构的线性表具有顺序存取和随机存取表中元素的优点，同时，它也存在下列缺点：（1）插入、删除操作时需要移动大量元素，效率较低；（2）最大表长难以估计，太大了浪费空间，太小了容易溢出。链式存储结构的线性表可以克服上述缺点，但是只能顺序存取不能随机存取。链表分为单链表、双向链表和循环链表。44

线性表采用单链表来表示，在内存中用一组连续的或不连续的存储单元来存储线性表的数据元素，每个元素含有数据域（data）和一个指针域（next），这两部分信息组成了单链表中的一个结点。45单链表单链表的结点类型定义typedef结点数据域类型datatype;typedefstructnode{ datatypedata; structnode*next;}linklist;linklist*head,*p; //head为头指针，p为工作指针指针所指向的结点存储空间是在程序执行过程中生成和释放的，故称为动态存储空间。在C语言中，通过下面两个标准函数生成或释放结点。

生成结点：p=(linklist*)malloc(sizeof(linklist));

释放结点：free(p);必须通过指针来访问结点，即用*p表示结点。用p->data和p->next，或者(*p).data和(*p).next表示结点的数据域和指针域。46关于链表的头结点

单链表以及后面所讨论的循环链表和双向链表均可以带头结点或者不带头结点。47单链表的基本运算1、建立单链表

假设单链表结点的数据域类型是字符型，我们逐个输入字符，并以换行符“\n”作为输入结束标志。动态建立单链表通常有以下两种方法。（1）头插法建表

从空表开始，每次将输入的字符作为新结点插入到表头，链表中结点的次序与输入字符的顺序相反。用伪代码描述单链表的建立过程：

481 建立只有头结点的空表2 循环读取字符，若不是换行符，则执行循环体；若是换行符，则结束循环

2_1 产生新结点

2_2 将新结点插入到表头，即作为单链表当前的第一个结点3 返回单链表的头指针【算法2.6】头插法建立单链表linklist*CreateListF()//带头结点的头插法，返回单链表的头指针{ linklist*head,*p;charch;head=(linklist*)malloc(sizeof(linklist));//产生头结点①head->next=NULL; while((ch=getchar())!='\n')//输入abc{p=(linklist*)malloc(sizeof(linklist));//生成新结点②p->data=ch;//对结点的数据域赋值③p->next=head->next;//新结点的指针域指向原第一个结点④head->next=p;//修改头结点的指针域⑤}returnhead;}49（2）尾插法建表【算法2.7】尾插法建立单链表linklist*CreateListR()//带头结点的尾插法，返回单链表的头指针{ linklist*head,*p,*r;charch; head=(linklist*)malloc(sizeof(linklist)); //生成头结点① head->next=NULL;//建立空表 r=head;//r指针指向头结点

while((ch=getchar())!='\n')//输入abc { p=(linklist*)malloc(sizeof(linklist));//生成新结点② p->data=ch;//将输入的字符赋给新结点的数据域 r->next=p; //新结点插入表尾③ r=p; //r指针指向到表尾④ } r->next=NULL;//表尾结点的指针域置空⑤ returnhead;}//时间复杂度为O(n)502、单链表查找对单链表的查找只能从表头开始顺序查找。

（1）按序号查找

单链表的第一个结点的序号为1，第二个结点的序号为2，以此类推。

设单链表的长度为n，并且规定头结点的位序为0，要查找第i个结点，仅当1≤i≤n时，才能查找到；否则查找不到，返回NULL。

（2）按值查找

在单链表中查找是否存在给定查找值key的结点，若存在，则返回该结点的地址；否则返回NULL。513、单链表的插入

在单链表中插入结点，只需要修改指针的指向，不需要移动结点。

单链表只能做“后插”，不能做“前插”。算法2.11是在单链表的第i个结点之前插入一个新结点，必须先找到第i-1个结点并插入，即将“前插”变为“后插”。【例2.3】将值为x的新结点插入到递增有序单链表中，使插入后该链表仍然有序。

先查找插入位置，然后插入新结点。在查找过程中，若遇到某个结点的元素值大于等于x，则在该结点之前插入新结点。在单链表中必须利用前驱指针将“前插操作”变为“后插操作”。524、单链表的删除

在单链表中删除一个结点，必须先查找到该结点的直接前驱结点，然后删除该结点。【算法2.12】单链表的删除voidDelete(linklist*L,inti)//在带头结点的单链表中删除第i个结点{ p=Get(L,i-1);//调用算法2.9，找第i-1个结点① if(p!=NULL&&p->next!=NULL)//第i-1个结点和第i个结点均存在 { r=p->next;//r指向*p的后继结点② p->next=r->next;//删除结点*r③ free(r);//释放结点*r所占的存储空间 } elseprintf("第i个结点不存在");}53循环链表

循环链表的一种形式是单循环链表。其特点是单链表中最后一个结点的指针域指向头结点或开始结点，整个链表形成一个环，从表中任一结点出发均可找到表中其他结点。54【例2.4】在单循环链表上实现将两个线性表（a1,a2,…,am）和（b1,b2,…,bn）合并为一个循环链表（a1,…,am,b1,…,bn）的运算。（1）采用尾指针，为指针指向终端结点，在算法中没有循环，算法的时间复杂度为O(1)。（2）采用头指针，分别需要找到La表和Lb表的终端结点，需要两个循环的并列，算法的时间复杂度为O(Length(La)+Length(Lb))。55双向链表（双向循环链表）

双向链表结点的结构体类型定义：typedefstructdnode{datatypedata; //data为结点的数据域structdnode*prior,*next;//prior和next分别是结点的前驱和后继指针域}dlinklist;dlinklist*head;56双向链表将头结点和终端结点链接起来，构成顺时针和逆时针的两个环。

双向链表可以“后插”，也可以“前插”。【算法2.13】双向链表的后插voidDInsertAfter(dlinklist*p,datatypex){//在带头结点的非空双向链表中,将值为x的新结点插入*p之后

dlinklist*s=(dlinklist*)malloc(sizeof(dlinklist));//生成新结点① s->data=x;

s->prior=p; //*s的前驱指针域指向*p②

s->next=p->next; //*s的后继指针域指向*p的后继结点③

p->next->prior=s; //*p的后继结点的前驱指针域指向*s④

p->next=s; //*p的后继指针域指向*s⑤}//时间复杂度为O(1)57【算法2.14】双向链表的前插voidDInsertBefore(dlinklist*p,datatypex){//在带头结点的非空双向链表中,将值为x的新结点插入*p之前

dlinklist*s=(dlinklist*)malloc(sizeof(dlinklist));//生成新结点① s->data=x;

s->prior=p->prior; //*s的前驱指针域指向*p的前驱结点②

s->next=p; //*s的后继指针域指向*p③

p->prior->next=s; //*p的前驱结点的后继指针域指向*s④ p->prior=s; //*p的前驱指针域指向*s⑤}//时间复杂度为O(1)58

在双向链表中删除一个结点也是比较灵活的。【算法2.15】双向链表的删除voidDDelete(dlinklist*p){//在带头结点的非空双向链表中,删除结点*p,设*p为非终端结点 p->prior->next=p->next;//*p的前驱结点的后继指针域指向*p的后继结点①

p->next->prior=p->prior;//*p的后继结点的前驱指针域指向*p的前驱结点②

free(p);//释放结点*p}//时间复杂度为O(1)592.4顺序表与链表的比较

6061

习题2（第2章作业）

习题2中的第一、二、三题写在教材上，尽可能都做，在上课时会抽查。习题2中的第四题写在作业本上，作业本要交。四、简答及算法设计1、2、6、9第3章栈和队列栈和队列也属于线性结构，它们的逻辑结构和线性表相同。存储方式有顺序和链式两种存储结构，只是其运算规则较线性表有更多的限制，因此，可以称为操作受限的线性表。62【本章重点】①栈和队列的操作特性；②基于顺序栈和链栈的基本运算的实现；③基于循环队列和链队列的基本运算的实现。63【本章难点】①多个栈共享空间的算法设计；②循环队列的组织及队空和队满的判定条件；③基于栈、队列的算法设计及应用。64【本章内容】栈队列栈和队列的应用举例习题3653.1栈栈的定义：栈是限定仅在表的一端进行插入或删除操作的线性表。插入、删除的一端称为栈顶（Top），另一端称为栈底（Bottom）。栈是一种后进先出的（LastInFirstOut）的线性表。栈可以是空栈或非空栈。对于非空栈S=(a1,a2,…,an),a1是栈底元素,an是栈顶元素。如果进栈的顺序是a1,a2,…,an，n个元素全部进栈后再出栈，其顺序正好相反。66栈的常用基本运算（1）InitStack(&S)栈初始化，操作结果是构造一个空栈S。（2）SetNull(S)置空栈，栈S已存在，将栈S清为空栈。（3）Empty(S)判断栈空，若栈S为空则返回“真”值；否则返回“假”值。（4）Push(S，x)进栈，若栈S不满，将数据元素x插入栈顶，并返回入栈是否成功的状态信息。入栈操作会改变栈的内容。（5）Pop(S,&x)出栈，若栈S非空，删除栈顶数据元素，通过参数x带回栈顶元素，并返回出栈是否成功的状态信息。出栈操作会使栈的内容发生变化。（6）GetTop(S,&x)取栈顶元素，若栈S非空，通过参数x带回栈顶元素，并返回取栈顶元素是否成功的状态信息。该操作完成后，栈的内容不变。67栈的基本运算应用举例【例3.1】将一个非负的十进制整数转换为其它进制数（二、八、十六进制），利用栈来实现。voidConversion(intn,intbase)//以十进制数和基数作为参数{ Stack*S;intbit; InitStack(S);//建立空栈

while(n!=0)

{ Push(S,n%base);//余数入栈

n=n/base; //整除基数

}

while(!EmptyStack(S))

{ bit=Pop(S);//余数出栈

if(bit>9)printf("%c",bit+55);//将余数转为字符输出

elseprintf("%c",bit+48); }

printf("\n");}68采用除基数取余的算法，例如将十进制数123转换为八进制数173，采用栈存放余数，入栈顺序是3、7、1，出栈顺序是1、7、3。栈的顺序存储结构和基本运算的实现1、栈的顺序存储结构——顺序栈

栈的顺序存储结构简称顺序栈。顺序栈采用一维数组来存储，并且用一个称为栈顶指针的整型量Top指示当前栈顶的位置。

顺序栈的类型定义如下： typedefstruct {

datatypedata[maxsize]; //栈中元素存储空间

intTop; //栈顶指针 }SeqStack;69如果把数组中下标为0的一端作为栈底，那么S->data[0]是栈底元素，S->data[S->Top]是栈顶元素。当S->Top=-1时为空栈，满栈时S->Top=maxsize-1。对于顺序栈，入栈时要先判断栈是否已满，栈满简称为“上溢”；出栈时需判断栈是否为空，栈空简称为“下溢”。入栈操作S->Top加一，出栈操作S->Top减一。2、顺序栈基本运算的实现（1）栈初始化 voidInitStack(SeqStack*&S) //构造一个空栈S {S=(SeqStack*)malloc(sizeof(SeqStack));//生成顺序栈空间

S->Top=-1; //栈顶指针置为-1 }（2）置空栈 voidSetNull(SeqStack*S) //将栈S置为空栈 {S->Top=-1; //栈顶指针置为-1 }70（3）判断栈空 intEmpty(SeqStack*S) //若栈S为空栈，返回1；否则返回0 { if(S->Top==-1)return1; elsereturn0; }（4）入栈 intPush(SeqStack*S,datatypex) //若栈S未满，则将元素x插入栈顶，并返回1，表示入栈成功；否则返回0，表示入栈不成功 { if(S->Top==maxsize-1) {printf("栈上溢"); return0; }//上溢 else {S->data[++S->Top]=x; return1; } }71（5）出栈

intPop(SeqStack*S,datatype&x)//若栈不空，则删除栈顶元素，由参数x带回栈顶元素，并返回1，表示出栈成功；否则返回0，表示出栈失败 {if(Empty(S))//判断栈是否为空

{printf("栈下溢");

return0;

}//下溢

else

{x=S->data[S->Top--];

return1;

} }72（6）取栈顶元素 intGetTop(SeqStack*S,datatype&x) //若栈不空，则删除栈顶元素，由x带回栈顶元素，并返回1，表示取栈顶元素成功；否则返回0，表示取栈顶元素失败 {if(EmptyS(S))//调用算法4.3，判断栈是否为空

{printf("栈下溢");

return0;

}//下溢

else

{x=S->data[S->Top];

return1;

} }73两个顺序栈共享连续空间，降低溢出的概率进栈操作的算法：voidpush(SeqStack*S,datatypex,inti)//将元素x插入i号栈{if(S->Top1+1==S->Top2)printf("数组空间已占满，发生上溢");elseif(i==1){S->Top1++;S->v[S->Top1]=x;} //入1号栈else{S->Top2--;S->v[S->Top2]=x;} //入2号栈}74出栈操作的算法：datatypepop(SeqStack*S,inti)//i号栈的栈顶元素出栈{datatypex;if(i==1)

if(S->Top1==-1)printf(“1号栈下溢”);

else{x=S->v[S->Top1];S->Top1--;}//1号栈出栈else

if(S->top2==maxsize)printf(“2号栈下溢”);

else{x=S->v[S->Top2];S->Top2++;}//2号栈出栈returnx;//返回出栈元素的值}75【例3.2】检查表达式中的括号是否匹配。

以表达式((1+2)*3-4)/5为例。表达式作为字符串存储在字符数组ex中，charex[]="((1+2)*3-4)/5";

在检查过程中，对字符数组进行扫描，当遇到“(”时入栈，遇到“)”时出栈。当整个表达式扫描完毕时，若栈为空，则表达式中的括号是匹配的；否则不匹配。voidcorrent(charex[]){ SeqStack*S; InitStack(S); i=0; while(i<length) { ch=ex[i]; switch(ch) { case'(':Push(S,ch);

break; case')':if(Empty(S)||Pop(S)!='(')

return"期望("; } i++; } if(!Empty(S)) return"期望)"; elsereturn"OK";}76栈的链式存储结构和基本运算的实现1、栈的链式存储结构栈的链接存储结构（链栈）用单链表来表示。链栈的结点结构类型定义如下：typedefstructnone{datatypedata; //data为结点的数据信息structnode*next; //next为后继结点的指针}StackNode; //链栈结点类型typedefstruct{StackNode*Top; //指向栈顶结点的指针}LinkStack;//含有栈顶指针Top的链栈结构体类型77将单链表的表头作为栈顶，由于只能在栈顶进行入栈和出栈操作，所以只能在单链表的表头进行插入和删除。78S是LinkStack类型的指针，指向链栈，可以看作是栈的接口。Top是栈顶指针，指向栈顶结点，当Top等于NULL时，为空栈。2、链栈基本运算的实现链栈的入栈和出栈都是在栈顶（单链表的表头）进行，所以算法的时间复杂度均为O(1)。79【算法3.7】建立空链栈。voidInitStack(LinkStack*&S)//构造一个空栈S{S=(LinkStack*)malloc(sizeof(LinkStack));S->Top=NULL;}【算法3.8】链栈置空。voidSetNull(LinkStack*S)//将栈S置为空栈{S->Top=NULL;}【算法3.9】链栈入栈。voidPush(LinkStack*S,datatypex)//将元素x入栈{StackNode*p=(StackNode*)malloc(sizeof(StackNode));

p->data=x;p->next=S->Top;//将新结点*p插入栈顶 S->Top=p;}80由于链栈不存在上溢的问题，所以在入栈时不需要判断栈满的情况81【算法3.10】链栈栈顶元素出栈。intPop(LinkStack*S,datatype&x)//若栈非空，则删除栈顶元素，由x带回栈顶元素，并返回1；否则返回0{StackNode*p=S->Top;//指针p指向栈顶结点if(Empty(S))//判断栈是否为空{printf("栈下溢");return0;}//下溢else{ x=p->data;

S->Top=p->next;//将栈顶结点*p从链上摘下

free(p);//释放原栈顶结点空间

return1;}}82【算法3.11】取链栈的栈顶元素。intGetTop(LinkStack*S,datatype&x)//若栈非空，则取栈顶元素，由x带回栈顶元素，并返回1；否则返回0{StackNode*p=S->Top;//指针p指向栈顶结点if(Empty(S))//判断栈是否为空{printf("栈下溢");return0;}//下溢else{ x=p->data;

return1;}}在链栈中取栈顶元素与出栈是类似的，只是没有下面两条语句：S->Top=p->next;//将栈顶结点*p从链上摘下free(p);//释放原栈顶结点空间3.2队列1、队列的定义及基本运算队列也是一种运算受限的线性表。它只允许在表的一端进行插入，该端称为队尾（Rear）；在表的另一端进行删除，该端称为队头（Front)。队列亦称作先进先出（FirstInFirstOut）的线性表，简称为FIFO表。当队列中没有元素时称为空队列。83队列的主要基本运算（1）InitQueue(&Q)队列初始化。构造一个空队列Q。（2）SetNull(Q)置空队。将队列Q清空。（3）Length(Q)求队列长度。返回队列中元素的个数。（4）Empty(Q)判空队。若队列Q为空队列，返回“真”值；否则返回“假”值。（5）EnQueue(Q,x)入队。若队列Q非满，将元素X插入Q的队尾。（6）DeQueue(Q)出队。若队列Q非空，删除队头元素，返回Q的队头元素。（7）GetFront(Q)取队头元素。若队列Q非空，返回Q的队头元素。Q中元素保持不变。84队列的基本运算应用【例】利用队列Q将栈S中的元素逆置。voidreverseS(Stack*S){InitQueue(&Q);while(!EmptyStack(S))EnQueue(Q,Pop(S));while(!Empty(Q))Push(S,DeQueue(Q));}851、队列的顺序存储结构——顺序队列队列的顺序存储结构称为顺序队列，采用数组存储队列中的元素。我们约定，在非空队列中队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素的位置。（也可以约定，队头指针front指向队头元素的位置，队尾指针rear指向队尾元素的后一个位置）如果是空队，队头、队尾指针相等。队尾指针减去对头指针就是队列的长度。顺序队列的结构类型定义如下：typedefstruct{datatypedata[maxsize];intfront;intrear;}SeQueue;SeQueue*sq=(SeQueue*)malloc(sizeof(SeQueue));86队列的顺序存储结构和基本运算的实现循环队列

顺序队列中可能出现“上溢”和“下溢”情况，并且还存在“假上溢”现象，例如在教材中图3.6中的（c）或（d）的情况下，再进行入队操作，则出现“假上溢”。

循环队列可以解决“假上溢”问题。87sq->rear=(sq->rear+1)%maxsize;sq->front=(sq->front+1)%maxsize;在循环队列中区分空队和满队的方法在循环队列中，由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，在队空和队满时都有sq->front等于sq->rear，无法区分空队和满队。如果在循环队列中少用一个元素空间，则可以区分空队和满队。判断空队的条件：sq->rear==sq->front判断满队的条件：sq->front==(sq->rear+1)%maxsize882、循环队列基本运算的实现89【算法3.12】生成空循环队列。voidInitQueue(SeQueue*&sq)//建立空循环队列sq{ sq=(SeQueue*)malloc(sizeof(SeQueue));

sq->front=sq->rear=0;/*对于循环队列来说，只要队头和队尾指针相等即为空队，所以这里置为0~maxsize-1之间的任何一个值都可以，但一般置为0*/}【算法3.13】循环队列置空。voidSetNull(SeQueue*sq)//置队列sq为空队{sq->front=sq->rear=0;}90【算法3.14】求循环队列长度intLength(SeQueue*sq){return(sq->rear-sq->front+maxsize)%maxsize;}【算法3.15】循环队列入队。intEnqueue(sequeue*sq,datatypex)//将新元素x插入队列*sq的队尾，入队成功返回1，不成功返回0{ if(sq->front==(sq->rear+1)％maxsize) {printf("队列上溢");return(0);} else{sq->rear=(sq->rear+1)％maxsize;sq->data[sq->rear]=x;return(1); }}91【算法3.16】循环队列出队intDequeue(SeQueue*sq,datatype&x)//通过参数x带回该元素值，出队成功返回1，不成功返回0{ if(sq->rear==sq->front) {printf("队列下溢");return(0);} else{sq->front=(sq->front+1)％maxsize;x=sq->data[sq->front];return(1); }}92【算法3.17】取循环队列的队头元素intGetFront(SeQueue*sq,datatype&x)//通过参数x带回该元素值，取队头元素成功返回1，不成功返回0{if(sq->rear==sq->front){

printf("队列下溢");return(0);}

else{

x=sq->data[(sq->front+1)%maxsize];

return(1);

}}93【例】如果循环队列只有头指针front和队列长度len，实现队列的基本运算。结构类型定义如下：typedefstruct{datatypedata[maxsize];intfront,len;}sequeue;sequeue*sq;说明：由于可以区分空队和满队，所以不需要少用一个存储单元。空队：sq->len==0成立满队：sq->len==maxsize成立94（1）队列初始化voidinit(sequeue*&sq){sq=(sequeue*)malloc(sizeof(sequeue));sq->front=maxsize-1;sq->len=0;}（2）置空队voidsetnull(sequeue*sq){sq->len=0;}95（3）判队空intempty(sequeue*sq){if(sq->len==0)return(1);elsereturn(0);}（4）入队intenter(sequeue*sq,datatypex){if(sq->len==maxsize){printf(“queueisfull”);return(0);}//队列中最多可容纳maxsize个元素

else{sq->len++;sq->data[(sq->front+sq->len)%maxsize]=x;return(1);}}入队时队尾指针的操作，相当于：sq->len++;(sq->front+sq->len)%maxsize96（5）出队intdel(sequeue*sq,datatype&x){if(empty(sq)){printf(“queueisempty”);return(0);}else{sq->front=(sq->front+1)%maxsize;sq->len--;x=sq->data[sq->front];return(1);}}（6）取队头元素intget(sequeue*sq,datatype&x){if(empty(sq){printf(“queueisempty”);return(0);}else{x=sq->data[(sq->front+1)%maxsize];return(1);}}队列的链式存储结构和基本运算的实现链队列的结构类型定义：typedefstructnode{datatypedata;structnode*next;}QueueNode;//链队列的结点类型typedefstruct{QueueNode*front,*rear;}LinkQueue;//队头、队尾指针的结构体类型LinkQueue*q;将链队列的头指针和尾指针封装在一起，作为一个结构体类型q为LinkQueue类型的指针97链队列基本运算的实现98算法3.18生成空链队列。voidInitQueue(LinkQueue*&q){q=(LinkQueue*)malloc(sizeof(LinkQueue));//产生队头、队尾指针结构体q->front=q->rear=(QueueNode*)malloc(sizeof(QueueNode));//产生头结点q->front->next=NULL;//头结点指针域置空}算法3.19链队列置空。voidSetNull(LinkQueue*q){q->rear=q->front; //尾指针也指向头结点q->front->next=NULL; //头结点指针域置空}算法3.20链队列判空队。intEmpty(LinkQueue*q){if(q->front==q->rear)return(1);elsereturn(0);}99算法3.21链队列入队。voidEnQueue(LinkQueue*q,datatypex)//将新元素x加入链队列*q{q->rear->next=(QueueNode*)malloc(sizeof(QueueNode));//新结点插入队尾q->rear=q->rear->next;//尾指针指向新结点q->rear->data=x;//给新结点赋值q->rear->next=NULL;//队尾结点的指针域置空}//链队列不会出现“上溢”的情况，入队时不需要判断队满100算法3.22链队列出队。intDeQueue(LinkQueue*q,datatype&x)//通过参数x带回该元素值，出队成功返回1，不成功返回0{QueueNode*s;if(Empty(q)){printf("队列下溢");return(0);}else{s=q->front->next;//s指向被删除的队头结点

if(s->next==NULL){//当前链队列的长度等于1，出队后为空队

q->front->next=NULL;q->rear=q->front;//置为空队

}

elseq->front->next=s->next;//队列的长度大于1，修改头结点的指针域

x=s->data;

free(s);//释放被删除的结点空间

return(1);

}}101算法3.23取链队列的队头元素。intGetFront(LinkQueue*q,datatype&x)//通过参数x带回队头元素值，取队头元素成功返回1，不成功返回0{if(Empty(q)){printf("队列下溢");return(0);}else{x=q->front->next->data;return(1);}}例4.3用带有头结点的循环链表表示队列，并且只设队尾指针rear，编写入队和出队算法。可以将rear->next->next看作队头指针。根据队列长度的不同，出队操作需考虑出队之前队列为空队、长度等于1和大于1三种不同的情况。如果出队之前队列长度为1，那么出队之后就是空队了。（1）入队算法102voidEnQueue(QueueNode*&rear,datatypex){QueueNode*p;p=(QueueNode*)malloc(sizeof(QueueNode));p->data=x; p->next=rear->next; rear->next=p; rear=p;}（2）出队算法103intDelQueue(QueueNode*&rear,datatype&x){QueueNode*p;if(rear==rear->next){printf("队列下溢");return(0);}else{ p=rear->next->next;x=p->data;