数据结构-复习和习题解析公开课一等奖优质课大赛微课获奖课件.pptx

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