1、数据结构 与 算法复习与习题解析(第1-5讲）第一讲 绪论p了解数据结构有关概念的含义，特别是数据的了解数据结构有关概念的含义，特别是数据的逻辑结构和存储结构之间的关系；（逻辑结构和存储结构之间的关系；（重点重点）p熟悉类熟悉类C C语言的书写规范；语言的书写规范；p了解计算算法时间复杂度的方法。（了解计算算法时间复杂度的方法。（难点难点）11/1/20222数据结构的定义 按某种逻辑关系按某种逻辑关系组织起来的一批数据（或称组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言带结构的数据元素的集合）应用计算机语言并并按一定的存储表示方式按一定的存储表示方式把它们存储在计算把它们存储
2、在计算机的存储器中，并机的存储器中，并在其上定义了一个运算的在其上定义了一个运算的集合集合。基本概念和术语p【数据】是对信息的一种符号表示。是是对信息的一种符号表示。是可以输入可以输入计算机中，计算机中，能被计算机能被计算机识别处理和输出的识别处理和输出的一切一切符号集合。符号集合。p【数据元素】是数据的是数据的基本单位基本单位，在计算机中通常作为一个，在计算机中通常作为一个 整体进行考虑和处理。也称为整体进行考虑和处理。也称为记录记录。p【数据项】一个数据元素可由若干个数据项组成。是数据不一个数据元素可由若干个数据项组成。是数据不可分割的可分割的最小单位最小单位。p【数据对象】是是性质相同性
3、质相同的数据元素的集合。是数据的一个的数据元素的集合。是数据的一个 子集子集。11/1/20224p【数据结构】相互之间存在一种或多种相互之间存在一种或多种特定关系特定关系的数据的数据 元素的集合元素的集合计算机如何解决问题11/1/20225问题问题机外表示机外表示处理要求处理要求逻辑结构逻辑结构基本运算基本运算数学模型数学模型存储结构存储结构编程实现编程实现实现实现建模建模求精求精研究数据结构是为了帮计算机解决问题！研究数据结构是为了帮计算机解决问题！数据结构的研究内容11/1/20226【数据结构的三个方面研究内容】具体来说，数据结构包具体来说，数据结构包含三个方面的内容，即含三个方面的
4、内容，即数据的逻辑结构数据的逻辑结构，数据的存储结构数据的存储结构和和对数据所施加的运算对数据所施加的运算（操作）。（操作）。数据的逻辑结构数据的逻辑结构（面向人类）（面向人类）数据的存储结构数据的存储结构（面向计算机）（面向计算机）数据的运算（操作）：检索、排序、插入、删除、修改等数据的运算（操作）：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构顺序存储顺序存储链式存储链式存储 线性表线性表栈栈队列队列树形结构树形结构图形结构图形结构散列存储散列存储索引存储索引存储串及数组串及数组四种基本逻辑结构11/1/20227【集合】数据元素间除了“同属于一个集合”外，无其他关
5、系。【线性结构】1对1的关系比如线性表、栈、队列。【树形结构】1对多的关系比如树。【图形结构】多对多的关系比如图。算法与数据结构p算法与数据结构关系密切p选择的数据结构是否恰当直接影响算法的效率；选择的数据结构是否恰当直接影响算法的效率；而数据结构的优劣由算法的执行来体现。而数据结构的优劣由算法的执行来体现。p“算法算法 +数据结构数据结构 =程序程序”p算法!=程序p算法是算法是供人阅读供人阅读的，程序是的，程序是让机器执行让机器执行的的p算法用算法用计算机语言实现计算机语言实现时就是程序时就是程序p程序不具有算法的程序不具有算法的有穷性有穷性算法的概念v算法是解决某个特定问题的求解算法是解
6、决某个特定问题的求解步骤步骤的描述。的描述。v算法在计算机中表现为指令的算法在计算机中表现为指令的有限有限序列，每条指令表示一序列，每条指令表示一个或多个操作。个或多个操作。v计算机对数据的操作可以分为计算机对数据的操作可以分为数值性数值性和和非数值性非数值性两种类型两种类型。在数值性操作中主要进行的是算术运算；而在非数值性。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。操作中主要进行的是检索、排序、插入、删除等等。v程序程序不等于不等于算法：计算机程序是算法的具体实现。算法：计算机程序是算法的具体实现。11/1/20229（1）有穷性：一个算法
7、必须在执行有穷步之后结束。：一个算法必须在执行有穷步之后结束。（2）确定性：算法中的每一步，必须有确切的含义，在他：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。人理解时不会产生二义性。（3）可行性：算法中描述的每一步操作都可以通过已有的：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。基本操作执行有限次实现。（4）输入：一个算法应该有零个或多个输入。：一个算法应该有零个或多个输入。（5）输出：一个算法应该有一个或多个输出。这里所说的：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。输出是指与输入有某种特定关系的量。算法的性质算法设计的要
8、求v正确性（四个境界）（四个境界）q没有语法错误没有语法错误q对于合法的输入数据能够产生满足要求的输出对于合法的输入数据能够产生满足要求的输出q对于非法的输入数据能够得出满足规格说明的结果对于非法的输入数据能够得出满足规格说明的结果q对于任何测试数据都有满足要求的输出结果对于任何测试数据都有满足要求的输出结果v可读性：便于阅读、理解和交流：便于阅读、理解和交流v健壮性：不合法数据也能合理处理：不合法数据也能合理处理v时间效率高和存储量低11/1/202211算法效率的度量方法v事后统计方法q通过设计好的测试程序和数据，利用计算机测量其运行时间。通过设计好的测试程序和数据，利用计算机测量其运行时
9、间。q缺陷：需要先编写程序；和计算机软硬件相关；和测试数据相关。缺陷：需要先编写程序；和计算机软硬件相关；和测试数据相关。v事前分析估算方法（我们的选择）q依据依据统计方法统计方法对算法进行对算法进行估算估算。m=f(n)，m是语句总的执行次数是语句总的执行次数，n是输入的规模。是输入的规模。q和问题输入规模相关和问题输入规模相关，独立于程序设计语言和计算机软硬件，独立于程序设计语言和计算机软硬件11/1/202212算法时间复杂度11/1/202213p在进行算法分析时，语句的总执行次数在进行算法分析时，语句的总执行次数 T(n)是关于问题是关于问题规模规模 n 的函数，进而分析的函数，进而
10、分析 T(n)随随 n 的的变化情况变化情况并确定并确定 T(n)的的数量级数量级。p算法的时间复杂度，也就是算法的时间量度，用算法的时间复杂度，也就是算法的时间量度，用“大大O记法记法”记作：记作：T(n)=O(f(n)。由此得到的。由此得到的 T(n)的数量级叫的数量级叫“大大O阶阶”。它表示随问题规模。它表示随问题规模 n 的增大，算法执行时间增长的增大，算法执行时间增长率和率和 f(n)的的增长率相同增长率相同，称作算法的，称作算法的渐进时间复杂度渐进时间复杂度，简，简称时间复杂度。其中称时间复杂度。其中 f(n)是问题规模是问题规模 n 的的某个函数某个函数。p一般情况下，一般情况下
11、，T(n)增长增长越慢越慢，算法，算法越优越优。大O阶的数学定义 当当n时，有时，有f(n)/g(n)=常数常数0，则称函数，则称函数f(n)与与g(n)同阶同阶,或者说，或者说，f(n)与与g(n)同一个数量级，记作同一个数量级，记作 f(n)=O(g(n)称上式为算法的时间复杂度称上式为算法的时间复杂度,或称该算法的时间复杂或称该算法的时间复杂度为度为O(g(n)。其中其中,n为问题的规模为问题的规模(大小大小)的量度。的量度。若lim(f(n)/g(n)=lim(2n3+3n2+2n+1)/n3)=2nn则算法的时间复杂度为O(n3)算法空间复杂度11/1/202215算法的空间复杂度通
12、过计算算法算法的空间复杂度通过计算算法所需的存储空间所需的存储空间实现，实现，算法空间复杂度的计算公式记作：算法空间复杂度的计算公式记作：S(n)=O(f(n)，其中，其中，n 为问题的规模，为问题的规模，f(n)为语句关于为语句关于 n 所占存所占存储空间的函数。储空间的函数。我们主要讨论时间复杂度问题。例题解析【例1】数据元素之间的关系在计算机中有几种表示方法？各有什么特点？答：答：四种表示方法四种表示方法（1）顺序存储方式。顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些
13、操作（如插入、删除）效率较差。数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。（2）链式存储方式。链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。（3）索引存储方式。索引存储方式。除数据元素存储在一地址连续的内存
14、空间外，尚需建立一个索引除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。有静态和动态特性。（4）散列存储方式。散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机
15、存取，不能顺序存取，也称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。不能折半存取。11/1/202216例题解析【例2】有下列运行时间函数：（1）T1(n)=1000;（2）T2(n)=n2+1000n;（3）T3(n)=3n3+100n2+n+1;分别写出相应的大 O 表示的运算时间答：答：(1)O(1)(2)O(n2)(3)O(n3)11/1/202217例题解析【例3】已知如下程序段for(i=n;i0;i-)语句1 x=x+1;语句2 for(j=n;j=i;j-)语句3 y=y+1;语句4语句1执行的频度为_；语句2执行的频度为_；语句3执行的
16、频度为_；语句4执行的频度为_。答：（1）n+1 （2）n （3）n(n+3)/2 （4）n(n+1)/2 第二讲 线性表v线性结构的定义和特点q在数据元素的非空有限集中，有且仅有一个开始结点和在数据元素的非空有限集中，有且仅有一个开始结点和一个终端结点，并且所有结点只有一个直接前趋和一个一个终端结点，并且所有结点只有一个直接前趋和一个直接后继。简言之，线性结构反映结点间的逻辑关系是直接后继。简言之，线性结构反映结点间的逻辑关系是 一对一一对一。线性结构包括线性表、堆栈、队列、字符串、。线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最简单、最常用的是线性表。数组等等，其中，最简单、最
17、常用的是线性表。v线性表的存储方法q顺序存储：逻辑上相邻物理上顺序存储：逻辑上相邻物理上一定一定相邻相邻q链式存储：逻辑上相邻物理上链式存储：逻辑上相邻物理上不一定不一定相邻相邻顺序表v顺序表线性表的顺序存储表示线性表的顺序存储表示v顺序存储用一用一组地址连续的组地址连续的存储单元存储单元依次依次存储线性表存储线性表的元素，可通过的元素，可通过数组数组来实现。（逻辑上相邻物理上一定相来实现。（逻辑上相邻物理上一定相邻）邻）q LOC(ai)=LOC(a1)+(i-1)len（a1为首元素，为首元素，len为单个元素占用空间长度为单个元素占用空间长度）v顺序存储的优点q可以随机存取表中任一元素可
18、以随机存取表中任一元素O(1)；存储空间使用紧凑；存储空间使用紧凑v顺序存储的缺点q在插入元素时平均需要移动在插入元素时平均需要移动n/2个元素，删除某一元素时，平均需个元素，删除某一元素时，平均需要移动要移动n-1/2个元素。算法的平均时间复杂度为个元素。算法的平均时间复杂度为O(n)q预先分配空间需按最大空间分配，利用不充分预先分配空间需按最大空间分配，利用不充分;表容量难以扩充表容量难以扩充11/1/202220链表v链式存储结构特点q用一组任意的存储单元存储线性表的数据元素用一组任意的存储单元存储线性表的数据元素q利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素利用指针实现了用不相
19、邻的存储单元存放逻辑上相邻的元素q每个数据元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息除存储本身信息外，还需存储其直接后继的信息 v链式存储结构的优点：q结点空间可以结点空间可以动态申请和释放动态申请和释放；q数据元素的逻辑次序靠结点的指针来指示，数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移插入和删除时不需要移动数据元素动数据元素。v链式存储结构的缺点：q每个结点的每个结点的。当数据域所占字节不多时。当数据域所占字节不多时，指针域所占存储空间的比重显得很大。，指针域所占存储空间的比重显得很大。q链表链表是是结构结构。对任一结点的操作都要从头指针依链查找。对任一
20、结点的操作都要从头指针依链查找该结点，这增加了算法的复杂度该结点，这增加了算法的复杂度 O（n）q不不便于便于在表尾在表尾插入插入元素：需遍历整个表才能找到位置。元素：需遍历整个表才能找到位置。11/1/202221例题解析【例例1】说明在线性表的链式存储结构中，头指针与头说明在线性表的链式存储结构中，头指针与头结点之间的根本区别。结点之间的根本区别。答：答：在线性表的链式存储结构中，头指针指链表的指针，若链在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。用，故
21、常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不结点的操作统一了。而且无论链表是否为空，头指针均不为空。为空。11/1/202222例题解析【例例2】设顺序表设顺序表va中
22、的数据元素递增有序。试设计一个算法，将中的数据元素递增有序。试设计一个算法，将x插入插入到顺序表的适当位置上，以保持该表的有序性。到顺序表的适当位置上，以保持该表的有序性。答：答：void Insert_SqList(SqList va,int x)/*把把x插入递增有序表插入递增有序表va中中*/int i;if(va.length MAXSIZE)return;for(i=va.length-1;va.elemix&i=0;i-)va.elemi+1=va.elemi;va.elemi+1=x;va.length+;/*Insert_SqList*/11/1/2022231.#define
23、 MAXSIZE 100 2.typedef struct 3.ElemType *elem;4.int length;5.SqList；例题解析【例例3】设单链表结点指针域为设单链表结点指针域为 next，试写出删除链，试写出删除链表中指针表中指针 p 所指结点的直接后继的所指结点的直接后继的 C 语言语句。语言语句。答：答：q=p-next;p-next=q-next;free(q);11/1/202224例题解析【例例4】设单链表中某指针设单链表中某指针 p 所指结点（即所指结点（即 p 结点）结点）的数据域为的数据域为 data，链指针域为，链指针域为 next，请写出在，请写出在 p
24、 结点之前插入结点之前插入 s 结点的操作。结点的操作。答：答：设单链表的头结点的头指针为设单链表的头结点的头指针为head,且且pre=head；while(pre-next!=p)pre=pre-next;s-next=p;pre-next=s;11/1/202225例题解析【例例5】试编写在带头结点的单链表中删除（一个）最小值结点的算法。试编写在带头结点的单链表中删除（一个）最小值结点的算法。void delete（Linklist&L）答：答：题目分析题目分析 本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出本题要求在单链表中删除最小值结点。单链表中删除结点，为使
25、结点删除后不出现现“断链断链”，应知道被删结点的前驱。而，应知道被删结点的前驱。而“最小值结点最小值结点”是在遍历整个链表后才能知道。所是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。void delete（LinkedList&L）L是带头结点的单链表是带头结点的单链表 p=L-next；p为工作指针。指向待处理的结点。假定链表非空。为工作指针。指向待处理的结点。假定链表非空。pre=L；pre指向最小值结点的前驱。指向最小值结点的前驱。q=p；q指向最小值结点，初始
26、假定第一元素结点是最小值结点。指向最小值结点，初始假定第一元素结点是最小值结点。while（p-next!=null）if（p-next-datadata）pre=p；q=p-next；查最小值结点查最小值结点 p=p-next；指针后移。指针后移。pre-next=q-next；从链表上删除最小值结点从链表上删除最小值结点 free（q）；）；释放最小值结点空间释放最小值结点空间 结束算法结束算法delete。11/1/202226例题解析【例例6】一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域 coef，指数域，指数域
27、exp 和指针域和指针域 next；现对链表求一阶导数；现对链表求一阶导数，链表的，链表的头指针为头指针为 ha，头结点的，头结点的 exp 域为域为 1。void derivative(ha)q=ha;pa=ha-next;while(1)_)if(2)_)(3)_);free(pa);pa=(4)_);else pa-coef(5)_);pa-exp(6)_);q=(7)_);pa=(8)_);11/1/202227(1)pa!=ha 或或pa-exp!=-1(2)pa-exp=0 若指数为若指数为0，即本项为常数项，即本项为常数项(3)q-next=pa-next 删常数项删常数项(4)
28、q-next 取下一元素取下一元素(5)=pa-coef*pa-exp(6)-指数项减指数项减1(7)pa 前驱后移前驱后移,或或q-next(8)pa-next 取下一元素取下一元素 第三讲 栈和队列v栈q限定仅在表尾进行插入和删除的线性表，把这限定仅在表尾进行插入和删除的线性表，把这个表尾称为个表尾称为栈顶栈顶。v特点q后进先出后进先出(LIFO表表)v栈的存储方法q栈的顺序存储栈的顺序存储顺序栈顺序栈q栈的链式存储栈的链式存储链栈链栈11/1/202228关于栈要求掌握的内容11/1/202229 栈的基本概念：栈的基本概念：LIFOLIFO 栈的存储栈的存储栈的应用（了解）栈的应用（了
29、解）顺序栈顺序栈（熟练掌握）（熟练掌握）链栈链栈（熟练掌握）（熟练掌握）初始化初始化取栈顶取栈顶入栈出栈入栈出栈判断栈空判断栈空 栈栈初始化初始化取栈顶取栈顶入栈出栈入栈出栈判断栈空判断栈空队列定义11/1/202230 队列的定义队列的定义 线性表线性表 特点：先进先出特点：先进先出(FIFO结构结构)。队头队头 下图是队列的示意图：下图是队列的示意图：a1a2an 出队出队 入队入队 队头队头 队尾队尾 当队列中没有元素时称为当队列中没有元素时称为空队列空队列。表尾称为队尾表尾称为队尾(rear)表头称为队头表头称为队头(front)插入元素称为入队插入元素称为入队删除元素称为出队删除元素
30、称为出队限定在表的一端插入、另一端删除。限定在表的一端插入、另一端删除。顺序队列的假溢出问题11/1/202231 在顺序队列中，当尾指针已经指向了队列的最后一个在顺序队列中，当尾指针已经指向了队列的最后一个 位置即数组上界时，若再有元素入队，就会发生位置即数组上界时，若再有元素入队，就会发生“”。“”队列的存储空间未满，却发生了溢出。队列的存储空间未满，却发生了溢出。rear front J1 J2 J3 J4 rear front J3 J4 (1)、平移元素：把元素平移到队列的首部。、平移元素：把元素平移到队列的首部。解决解决“假溢出假溢出”的问题有两种可行的方法：的问题有两种可行的方法
31、：(2)、将新元素插入到第一个位置上，构成、将新元素插入到第一个位置上，构成循环队列循环队列，入队和出队仍按入队和出队仍按“先进先出先进先出”的原则进行。的原则进行。rear front J3 J4 front rear J3 J4 循环队列11/1/202232队空条件队空条件:front=rear (初始化时：初始化时：front=rear)队满条件队满条件：front=(rear+1)%N (N=maxsize)队列长度：队列长度：L=（Nrearfront）%N J2 J3J1 J4 J5frontrear 选用选用空闲单元法：空闲单元法：即即front和和rear之一指向实元素，另一
32、指向空闲元素。之一指向实元素，另一指向空闲元素。问问2：在具有在具有n个单元的循个单元的循环队列中，队满时共有多少环队列中，队满时共有多少个元素？个元素？n-1个个5 问问1：左图中队列长度左图中队列长度L=？例题解析【例例1】一个栈的输入序列是一个栈的输入序列是12345，若在入栈，若在入栈的过程中允许出栈，则栈的输出序列的过程中允许出栈，则栈的输出序列43512可能可能实现吗？实现吗？12345的输出呢？的输出呢？答：答：4351243512不可能实现，主要是其中的不可能实现，主要是其中的1212顺序不能顺序不能实现；实现；1234512345的输出可以实现，只需压入一个立即弹的输出可以实
33、现，只需压入一个立即弹出一个即可。出一个即可。11/1/202233例题解析【例例2】如果一个栈的输入序列为如果一个栈的输入序列为123456，能，能否得到否得到435612和和135426的出栈序列？的出栈序列？答：答：435612中到了中到了12顺序不能实现；顺序不能实现；135426可以实现。可以实现。11/1/202234例题解析【例例3 3】一个栈的输入序列为一个栈的输入序列为123123，若在入栈的过程中允许出，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？栈，则可能得到的出栈序列是什么？答：答：可以通过穷举所有可能性来求解：可以通过穷举所有可能性来求解：1 1入入1 1出
34、，出，2 2入入2 2出，出，3 3入入3 3出，出，即即123123；1 1入入1 1出，出，2 2、3 3入入3 3、2 2出，出，即即132132；1 1、2 2入，入，2 2出，出，3 3入入3 3出，出，即即231231；1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出，即即213213；1 1、2 2、3 3入，入，3 3、2 2、1 1出，出，即即321321；合计有合计有5 5种可能性。种可能性。11/1/202235例题解析【例例4】简述顺序存储队列的假溢出的避免方法及队列满和简述顺序存储队列的假溢出的避免方法及队列满和空的条件。空的条件。答：设顺序存储队列
35、用一维数组答：设顺序存储队列用一维数组qm表示，其中表示，其中m为队列中元素个数，为队列中元素个数，队列中元素在向量中的下标从队列中元素在向量中的下标从0到到m-1。设队头指针为。设队头指针为front，队尾指，队尾指针是针是rear，约定，约定front指向队头元素的前一位置，指向队头元素的前一位置，rear指向队尾元指向队尾元素。当素。当front等于等于-1时队空，时队空，rear等于等于m-1时为队满。由于队列的性时为队满。由于队列的性质（质（“删除删除”在队头而在队头而“插入插入”在队尾），所以当队尾指针在队尾），所以当队尾指针rear等于等于m-1时，若时，若front不等于不等于
36、-1，则队列中仍有空闲单元，所以队列并不，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假是真满。这时若再有入队操作，会造成假“溢出溢出”。其解决办法有二。其解决办法有二，一是将队列元素向前，一是将队列元素向前“平移平移”（占用（占用0至至rear-front-1）；二是）；二是将队列看成首尾相连，即循环队列（将队列看成首尾相连，即循环队列（0.m-1）。在循环队列下，仍）。在循环队列下，仍定义定义front=rear时为队空，而判断队满则用两种办法，一是用时为队空，而判断队满则用两种办法，一是用“牺牺牲一个单元牲一个单元”，即，即rear+1=front（准确记是（准确
37、记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是是队列容量）时为队满。另一种解法是“设标记设标记”方法方法，如设标记，如设标记tag，tag等于等于0情况下，若删除时导致情况下，若删除时导致front=rear为队为队空；空；tag=1情况下，若因插入导致情况下，若因插入导致front=rear则为队满。则为队满。11/1/202236第四讲 串和数组【例例1】填空题：填空题：1.空格串是指空格串是指_，其长度等于，其长度等于_。【答案答案】（1）由空格字符（）由空格字符（ASCII值值32）所组成的字符串）所组成的字符串 （2）空）空格个数格个数2组成串的数据元素只
38、能是组成串的数据元素只能是_。【答案答案】字符字符【解析解析】串是一种特殊的线性表，其特殊性在于串中的元素只能是字符串是一种特殊的线性表，其特殊性在于串中的元素只能是字符型数据。型数据。3两个字符串相等的充分必要条件是两个字符串相等的充分必要条件是_。【答案答案】两串的长度相等且两串中对应位置上的字符也相等。两串的长度相等且两串中对应位置上的字符也相等。4一个字符串中一个字符串中_称为该串的子串称为该串的子串。【答案答案】任意个连续的字符组成的子序列任意个连续的字符组成的子序列11/1/202237例题解析【例例2】设计一个算法，将字符串设计一个算法，将字符串s的全部字符复制到字的全部字符复制
39、到字符串符串t中，不能利用中，不能利用strcpy函数。函数。答：答：【算法分析算法分析】要实现两个字符串的复制，实质为两个字符数组之间要实现两个字符串的复制，实质为两个字符数组之间的复制，在复制时，一个字符一个字符的复制，直到遇到的复制，在复制时，一个字符一个字符的复制，直到遇到0，0一同复制过去，一同复制过去，0之后的字符不复制。之后的字符不复制。【算法源代码算法源代码】void copy(char s,char t)int i;for(i=0;si!=0;i+)ti=si;ti=si;11/1/202238例题解析【例例3】设有一个二维数组设有一个二维数组Amn，假设，假设A00存放存放
40、位置在位置在644，A22存放位置在存放位置在676，每个元素占一，每个元素占一个空间，问个空间，问A33存放在什么位置？存放在什么位置？答：设数组元素答：设数组元素Aij存放在起始地址为存放在起始地址为Loc（i,j）的存储单元中。）的存储单元中。Loc（2,2）=Loc（0,0）+2*n+2 =644+2*n+2=676.n=（676-2-644）/2=15 Loc（3,3）=Loc（0,0）+3*15+3 =644+45+3=692.11/1/202239例题解析【例例4】设有一个设有一个n n的对称矩阵的对称矩阵A，为了节约存储，可以只存对角线及对角线以，为了节约存储，可以只存对角线及
41、对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，称之为对称矩中，称之为对称矩阵阵A的压缩存储方式。试问：的压缩存储方式。试问：（1）存放对称矩阵存放对称矩阵A上三角部分或下三角部分的一维数组上三角部分或下三角部分的一维数组B有多少元素？有多少元素？（2）若在一维数组若在一维数组B中从中从0号位置开始存放，则对称矩阵中的任一元素号位置开始存放，则对称矩阵中的任一元素aij在只在只存下三角部分的情形下应
42、存于一维数组的什么下标位置？给出计算公式。存下三角部分的情形下应存于一维数组的什么下标位置？给出计算公式。答：答：（1）数组数组B共有共有12+3+n=（n+1）*n/2个元素。个元素。（2）只存下三角部分时，若只存下三角部分时，若i j，则数组元素，则数组元素Aij前面有前面有i-1行（行（1 i-1，第，第0行第行第0列不算），第列不算），第1行有行有1个元素，第个元素，第2行有行有2个元素，个元素，第，第i-1行有行有i-1个元素。个元素。在第在第i行中，第行中，第j号元素排在第号元素排在第j个元素位置，因此，数组元素个元素位置，因此，数组元素Aij在数组在数组B中的存中的存放位置为：放
43、位置为：1+2+（i-1）+j=（i-1）*i/2+j若若i j，数组元素，数组元素Aij在数组在数组B中没有存放，可以找它的对称元素中没有存放，可以找它的对称元素Aji。在数。在数组组B的第的第（j-1）*j/2+i位置中找到。如果第位置中找到。如果第0行第行第0列也计入，数组列也计入，数组B从从0号位号位置开始存放，则数组元素置开始存放，则数组元素Aij在数组在数组B中的存放位置可以改为：当中的存放位置可以改为：当i j时，时，=i*（i+1）/2+j；当；当i n，则无左孩子；，则无左孩子；3)i的右孩子是的右孩子是2i+1，如果，如果2i+1n则无右孩子。则无右孩子。例题解析1深度为深
44、度为H 的完全二叉树至少有的完全二叉树至少有_个结点；至多有个结点；至多有_个结个结点；点；H和结点总数和结点总数N之间的关系是之间的关系是_。【答案答案】（1）2H-1（2）2H-1（3）H=log2N +1 2一棵有一棵有n个结点的满二叉树有个结点的满二叉树有_个度为个度为1的结点，有的结点，有_个个分支（非终端）结点和分支（非终端）结点和_个叶子，该满二叉树的深度为个叶子，该满二叉树的深度为_。【答案答案】（1）0 （2）(n-1）/2 （3）(n+1）/2 （4）log2n +13对于一个具有对于一个具有n个结点的二叉树，当它为一棵个结点的二叉树，当它为一棵_时，具有最小高度，当时，具
45、有最小高度，当它为一棵它为一棵_时，具有最大高度。时，具有最大高度。【答案答案】（1）完全二叉树）完全二叉树（2）单支树，树中任一结点（除最后一个结点是叶子外）单支树，树中任一结点（除最后一个结点是叶子外），只有左子女或只有右子女。，只有左子女或只有右子女。4已知二叉树有已知二叉树有50个叶子结点，则该二叉树的总结点数至少是个叶子结点，则该二叉树的总结点数至少是_。【答案答案】99【解析解析】在二叉树中，在二叉树中，N0=N2+1，所以，有，所以，有50个叶子结点的二叉树，有个叶子结点的二叉树，有49个度为个度为2的结的结点。若要使该二叉树的结点数最少，度为点。若要使该二叉树的结点数最少，度为
46、1的结点应为的结点应为0个，即总结点数个，即总结点数N=N0+N1+N2=99。11/1/202243二叉树的存储（一）11/1/202244v二叉树存储方法有二叉树存储方法有顺序存储顺序存储和和链式存储链式存储v二叉树二叉树顺序存储顺序存储结构结构q完全二叉树完全二叉树：用一组地址连续的存储单元依次：用一组地址连续的存储单元依次自上而下自上而下、自左至右、自左至右存储结点元素，即将编号为存储结点元素，即将编号为 i 的结点元素的结点元素存储在一维数组中下标为存储在一维数组中下标为 i 的分量中（不用下标为的分量中（不用下标为0存存储单元）。此储单元）。此顺序存储结构仅适用于完全二叉树顺序存储
47、结构仅适用于完全二叉树 q不是完全二叉树怎么办？不是完全二叉树怎么办？o一律转为完全二叉树！方法很简单，将各层空缺处统统补上一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚虚结点结点”，其内容为空。，其内容为空。q缺点：缺点：浪费空间；插入、删除不便浪费空间；插入、删除不便二叉树的存储（二）11/1/202245二叉树链式存储结构 存储方式 一般从根结点开始存储，用二叉链表来表示。一般从根结点开始存储，用二叉链表来表示。（相应地，访问树中结点时也只能从根开始）（相应地，访问树中结点时也只能从根开始）二叉树结点的特点二叉树是非线性结构，适合用链式存储结构lchild data rchil
48、d结点结构结点结构 data rchild lchild data parentlchildrchild二叉树结点数据类型定义：二叉树结点数据类型定义：typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;二叉树遍历11/1/202246v若规定先左后右，则只有前三种情况：前（根）序遍历，前（根）序遍历，中（根）序遍历，中（根）序遍历，后（根）序遍历后（根）序遍历v根据遍历顺序确定一棵二叉树q已知二叉树的已知二叉树的前序前序序列和序列和中序中序序列，序列，可以可以唯一确定一棵二叉
49、树。唯一确定一棵二叉树。q已知二叉树的已知二叉树的后序后序序列和序列和中序中序序列，序列，可以可以唯一确定一棵二叉树。唯一确定一棵二叉树。q已知二叉树的已知二叉树的前序前序序列和序列和后序后序序列，序列，不能不能唯一确定一棵二叉树。唯一确定一棵二叉树。例题解析11/1/202247设二叉树设二叉树bt的一种存储结构如下：的一种存储结构如下：00237580101jhfdbacegi000940000012345678910lchilddatarchild 其中其中bt为树根结点指针为树根结点指针,lchild、rchild分别为结点的左、右孩分别为结点的左、右孩子指针域子指针域,在这里使用结点
50、编号作为指针域值在这里使用结点编号作为指针域值,0表示指针域为表示指针域为空空;data为结点的数据域。请完成下列各题：为结点的数据域。请完成下列各题：(1)画出二叉树的树形表示；画出二叉树的树形表示；(2)写出按先序、中序和后序遍历二叉树写出按先序、中序和后序遍历二叉树bt所得到的结点序列；所得到的结点序列；例题解析（续）11/1/20224800237580101jhfdbacegi000940000012345678910lchilddatarchild(1)画出二叉树的树形表示；因画出二叉树的树形表示；因为第为第6号结点不是任何结点的孩号结点不是任何结点的孩子结点，该结点必定是根结点，
