数据结构-复习和习题解析省公共课一等奖全国赛课获奖课件.pptx

数据结构 与 算法复习与习题解析(第1-5讲）第1页第一讲 绪论p了解数据结构相关概念含义，尤其是数据逻辑了解数据结构相关概念含义，尤其是数据逻辑结构和存放结构之间关系；（结构和存放结构之间关系；（重点重点）p熟悉类熟悉类C C语言书写规范；语言书写规范；p了解计算算法时间复杂度方法。（了解计算算法时间复杂度方法。（难点难点）10/10/2第2页数据结构定义 按某种逻辑关系按某种逻辑关系组织起来一批数据（或称带组织起来一批数据（或称带结构数据元素集合）应用计算机语言并结构数据元素集合）应用计算机语言并按一按一定存放表示方式定存放表示方式把它们存放在计算机存放器把它们存放在计算机存放器中，并中，并在其上定义了一个运算集合在其上定义了一个运算集合。第3页基本概念和术语p【数据】是对信息一个符号表示。是是对信息一个符号表示。是能够输入能够输入计算机中，计算机中，能被计算机能被计算机识别处理和输出识别处理和输出一切一切符号集合。符号集合。p【数据元素】是数据是数据基本单位基本单位，在计算机中通常作为一个，在计算机中通常作为一个 整体进行考虑和处理。也称为整体进行考虑和处理。也称为统计统计。p【数据项】一个数据元素可由若干个数据项组成。是数据不一个数据元素可由若干个数据项组成。是数据不可分割可分割最小单位最小单位。p【数据对象】是是性质相同性质相同数据元素集合。是数据一个数据元素集合。是数据一个 子集子集。10/10/4p【数据结构】相互之间存在一个或各种相互之间存在一个或各种特定关系特定关系数据数据 元素集合元素集合第4页计算机怎样处理问题10/10/5问题问题机外表示机外表示处理要求处理要求逻辑结构逻辑结构基本运算基本运算数学模型数学模型存放结构存放结构编程实现编程实现实现实现建模建模求精求精研究数据结构是为了帮计算机处理问题！研究数据结构是为了帮计算机处理问题！第5页数据结构研究内容10/10/6【数据结构三个方面研究内容】详细来说，数据结构包含详细来说，数据结构包含三个方面内容，即三个方面内容，即数据逻辑结构数据逻辑结构，数据存放结构数据存放结构和和对数据对数据所施加运算所施加运算（操作）。（操作）。数据逻辑结构数据逻辑结构（面向人类）（面向人类）数据存放结构数据存放结构（面向计算机）（面向计算机）数据运算（操作）：检索、排序、插入、删除、修改等数据运算（操作）：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构次序存放次序存放链式存放链式存放 线性表线性表栈栈队列队列树形结构树形结构图形结构图形结构散列存放散列存放索引存放索引存放串及数组串及数组第6页四种基本逻辑结构10/10/7【集合】数据元素间除了“同属于一个集合”外，无其它关系。【线性结构】1对1关系比如线性表、栈、队列。【树形结构】1对多关系比如树。【图形结构】多对多关系比如图。第7页算法与数据结构p算法与数据结构关系亲密p选择数据结构是否恰当直接影响算法效率；而数选择数据结构是否恰当直接影响算法效率；而数据结构优劣由算法执行来表达。据结构优劣由算法执行来表达。p“算法算法 +数据结构数据结构 =程序程序”p算法!=程序p算法是算法是供人阅读供人阅读，程序是，程序是让机器执行让机器执行p算法用算法用计算机语言实现计算机语言实现时就是程序时就是程序p程序不含有算法程序不含有算法有穷性有穷性第8页算法概念v算法是处理某个特定问题求解算法是处理某个特定问题求解步骤步骤描述。描述。v算法在计算机中表现为指令算法在计算机中表现为指令有限有限序列，每条指令表示一个序列，每条指令表示一个或多个操作。或多个操作。v计算机对数据操作能够分为计算机对数据操作能够分为数值性数值性和和非数值性非数值性两种类型。两种类型。在数值性操作中主要进行是算术运算；而在非数值性操作在数值性操作中主要进行是算术运算；而在非数值性操作中主要进行是检索、排序、插入、删除等等。中主要进行是检索、排序、插入、删除等等。v程序程序不等于不等于算法：计算机程序是算法详细实现。算法：计算机程序是算法详细实现。10/10/9第9页（1）有穷性：一个算法必须在执行有穷步之后结束。：一个算法必须在执行有穷步之后结束。（2）确定性：算法中每一步，必须有确切含义，在他人了：算法中每一步，必须有确切含义，在他人了解时不会产生二义性。解时不会产生二义性。（3）可行性：算法中描述每一步操作都能够经过已经有基：算法中描述每一步操作都能够经过已经有基本操作执行有限次实现。本操作执行有限次实现。（4）输入：一个算法应该有零个或多个输入。：一个算法应该有零个或多个输入。（5）输出：一个算法应该有一个或多个输出。这里所说输：一个算法应该有一个或多个输出。这里所说输出是指与输入有某种特定关系量。出是指与输入有某种特定关系量。算法性质第10页算法设计要求v正确性（四个境界）（四个境界）q没有语法错误没有语法错误q对于正当输入数据能够产生满足要求输出对于正当输入数据能够产生满足要求输出q对于非法输入数据能够得出满足规格说明结果对于非法输入数据能够得出满足规格说明结果q对于任何测试数据都有满足要求输出结果对于任何测试数据都有满足要求输出结果v可读性：便于阅读、了解和交流：便于阅读、了解和交流v健壮性：不正当数据也能合理处理：不正当数据也能合理处理v时间效率高和存放量低10/10/11第11页算法效率度量方法v事后统计方法q经过设计好测试程序和数据，利用计算机测量其运行时间。经过设计好测试程序和数据，利用计算机测量其运行时间。q缺点：需要先编写程序；和计算机软硬件相关；和测试数据相关。缺点：需要先编写程序；和计算机软硬件相关；和测试数据相关。v事前分析估算方法（我们选择）q依据依据统计方法统计方法对算法进行对算法进行估算估算。m=f(n)，m是语句总执行次数，是语句总执行次数，n是输入规模。是输入规模。q和问题输入规模相关和问题输入规模相关，独立于程序设计语言和计算机软硬件，独立于程序设计语言和计算机软硬件 10/10/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页大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页算法空间复杂度10/10/15算法空算法空间复复杂度度经过计算算法算算法所需存放空所需存放空间实现，算法，算法空空间复复杂度度计算公式算公式记作：作：S(n)=O(f(n)，其中，其中，n 为问题规模，模，f(n)为语句关于句关于 n 所占存放空所占存放空间函数。函数。我们主要讨论时间复杂度问题。第15页例题解析【例1】数据元素之间关系在计算机中有几个表示方法？各有什么特点？答：答：四种表示方法四种表示方法（1）次序存放方式。次序存放方式。数据元素次序存放，每个存放结点只含一个元素。存放位置反应数据元素次序存放，每个存放结点只含一个元素。存放位置反应数据元素间逻辑关系。存放密度大，但有些操作（如插入、删除）效率较差。数据元素间逻辑关系。存放密度大，但有些操作（如插入、删除）效率较差。（2）链式存放方式。链式存放方式。每个存放结点除包含数据元素信息外还包含一组（最少一个）指每个存放结点除包含数据元素信息外还包含一组（最少一个）指针。指针反应数据元素间逻辑关系。这种方式不要求存放空间连续，便于动态操作针。指针反应数据元素间逻辑关系。这种方式不要求存放空间连续，便于动态操作（如插入、删除等），但存放空间开销大（用于指针），另外不能折半查找等。（如插入、删除等），但存放空间开销大（用于指针），另外不能折半查找等。（3）索引存放方式。索引存放方式。除数据元素存放在一地址连续内存空间外，尚需建立一个索引表，除数据元素存放在一地址连续内存空间外，尚需建立一个索引表，索引表中索引指示存放结点存放位置（下标）或存放区间端点（下标），兼有静态索引表中索引指示存放结点存放位置（下标）或存放区间端点（下标），兼有静态和动态特征。和动态特征。（4）散列存放方式。散列存放方式。经过散列函数和处理冲突方法，将关键字散列在连续有限地址空经过散列函数和处理冲突方法，将关键字散列在连续有限地址空间内，并将散列函数值解释成关键字所在元素存放地址，这种存放方式称为散列存间内，并将散列函数值解释成关键字所在元素存放地址，这种存放方式称为散列存放。其特点是存取速度快，只能按关键字随机存取，不能次序存取，也不能折半存放。其特点是存取速度快，只能按关键字随机存取，不能次序存取，也不能折半存取。取。10/10/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页例题解析【例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页第二讲 线性表v线性结构定义和特点q在数据元素非空有限集中，有且仅有一个开始结点和一在数据元素非空有限集中，有且仅有一个开始结点和一个终端结点，而且全部结点只有一个直接前趋和一个直个终端结点，而且全部结点只有一个直接前趋和一个直接后继。简言之，线性结构反应结点间逻辑关系是接后继。简言之，线性结构反应结点间逻辑关系是 一对一对一一。线性结构包含线性表、堆栈、队列、字符串、数组。线性结构包含线性表、堆栈、队列、字符串、数组等等，其中，最简单、最惯用是线性表。等等，其中，最简单、最惯用是线性表。v线性表存放方法q次序存放：逻辑上相邻物理上次序存放：逻辑上相邻物理上一定一定相邻相邻q链式存放：逻辑上相邻物理上链式存放：逻辑上相邻物理上不一定不一定相邻相邻第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页链表v链式存放结构特点q用一组任意存放单元存放线性表数据元素用一组任意存放单元存放线性表数据元素q利用指针实现了用不相邻存放单元存放逻辑上相邻元素利用指针实现了用不相邻存放单元存放逻辑上相邻元素q每个数据元素每个数据元素ai，除存放本身信息外，还需存放其直接后继信息除存放本身信息外，还需存放其直接后继信息 v链式存放结构优点：q结点空间能够结点空间能够动态申请和释放动态申请和释放；q数据元素逻辑次序靠结点指针来指示，数据元素逻辑次序靠结点指针来指示，插入和删除时不需要移动数插入和删除时不需要移动数据元素据元素。v链式存放结构缺点：q每个结点每个结点指针域需额外占用存放空间指针域需额外占用存放空间指针域需额外占用存放空间指针域需额外占用存放空间。当数据域所占字节不多时，。当数据域所占字节不多时，指针域所占存放空间比重显得很大。指针域所占存放空间比重显得很大。q链表链表是是非随机存取非随机存取非随机存取非随机存取结构结构。对任一结点操作都要从头指针依链查找该。对任一结点操作都要从头指针依链查找该结点，这增加了算法复杂度结点，这增加了算法复杂度 O（n）q不不便于便于在表尾在表尾插入插入元素：需遍历整个表才能找到位置。元素：需遍历整个表才能找到位置。10/10/21第21页例题解析【例例1】说明在线性表链式存放结构中，头指针与头结说明在线性表链式存放结构中，头指针与头结点之间根本区分。点之间根本区分。答：答：在线性表链式存放结构中，头指针指链表指针，若链表有在线性表链式存放结构中，头指针指链表指针，若链表有头结点则是链表头结点指针，头指针含有标识作用，故惯头结点则是链表头结点指针，头指针含有标识作用，故惯用头指针冠以链表名字。用头指针冠以链表名字。头结点是为了操作统一、方便而设置，放在第一元素结点头结点是为了操作统一、方便而设置，放在第一元素结点之前，其数据域普通无意义（当然有些情况下也可存放链之前，其数据域普通无意义（当然有些情况下也可存放链表长度、用做监视哨等等），有头结点后，对在第一元素表长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点操结点前插入结点和删除第一结点，其操作与对其它结点操作统一了。而且不论链表是否为空，头指针均不为空。作统一了。而且不论链表是否为空，头指针均不为空。10/10/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页例题解析【例例3】设单链表结点指针域为设单链表结点指针域为 next，试写出删除链，试写出删除链表中指针表中指针 p 所指结点直接后继所指结点直接后继 C 语言语句。语言语句。答：答：q=p-next;p-next=q-next;free(q);10/10/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页例题解析【例例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页例题解析【例例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页第三讲 栈和队列v栈q限定仅在表尾进行插入和删除线性表，把这个限定仅在表尾进行插入和删除线性表，把这个表尾称为表尾称为栈顶栈顶。v特点q后进先出后进先出(LIFO表表)v栈存放方法q栈次序存放栈次序存放次序栈次序栈q栈链式存放栈链式存放链栈链栈10/10/28第28页关于栈要求掌握内容10/10/29 栈基本概念：栈基本概念：LIFOLIFO 栈存放栈存放栈应用（了解）栈应用（了解）次序栈次序栈（熟练掌握）（熟练掌握）链栈链栈（熟练掌握）（熟练掌握）初始化初始化取栈顶取栈顶入栈出栈入栈出栈判断栈空判断栈空 栈栈初始化初始化取栈顶取栈顶入栈出栈入栈出栈判断栈空判断栈空第29页队列定义10/10/30 队列定义队列定义 队列：队列：队列：队列：线性表线性表 (queue)(queue)特点：先进先出特点：先进先出(FIFO结构结构)。队尾队尾队尾队尾 队头队头 下列图是队列示意图：下列图是队列示意图：a1a2an 出队出队 入队入队 队头队头 队尾队尾 当队列中没有元素时称为当队列中没有元素时称为空队列空队列。表尾称为队尾表尾称为队尾(rear)表头称为队头表头称为队头(front)插入元素称为入队插入元素称为入队删除元素称为出队删除元素称为出队限定在表一端插入、另一端删除限定在表一端插入、另一端删除。第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页循环队列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页例题解析【例例1】一个栈输入序列是一个栈输入序列是12345，若在入栈过，若在入栈过程中允许出栈，则栈输出序列程中允许出栈，则栈输出序列43512可能实现吗可能实现吗？12345输出呢？输出呢？答：答：4351243512不不可可能能实实现现，主主要要是是其其中中1212次次序序不不能能实实现；现；1234512345输出能够实现，只需压入一个马上弹出输出能够实现，只需压入一个马上弹出一个即可。一个即可。10/10/33第33页例题解析【例例2】假如一个栈输入序列为假如一个栈输入序列为123456，能否，能否得到得到435612和和135426出栈序列？出栈序列？答：答：435612中到了中到了12次序不能实现；次序不能实现；135426能够实现。能够实现。10/10/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页例题解析【例例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页第四讲 串和数组【例例1】填空题：填空题：1.空格串是指空格串是指_，其长度等于，其长度等于_。【答案答案】（1）由空格字符（）由空格字符（ASCII值值32）所组成字符串）所组成字符串 （2）空格）空格个数个数2组成串数据元素只能是组成串数据元素只能是_。【答案答案】字符字符【解析解析】串是一个特殊线性表，其特殊性在于串中元素只能是字符型数串是一个特殊线性表，其特殊性在于串中元素只能是字符型数据。据。3两个字符串相等充分必要条件是两个字符串相等充分必要条件是_。【答案答案】两串长度相等且两串中对应位置上字符也相等。两串长度相等且两串中对应位置上字符也相等。4一个字符串中一个字符串中_称为该串子串称为该串子串。【答案答案】任意个连续字符组成子序列任意个连续字符组成子序列10/10/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页例题解析【例例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页例题解析【例例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页例题解析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页二叉树存放（一）10/10/44v二叉树存放方法有二叉树存放方法有次序存放次序存放和和链式存放链式存放v二叉树二叉树次序存放次序存放结构结构q完全二叉树完全二叉树：用一组地址连续存放单元依次：用一组地址连续存放单元依次自上而下、自上而下、自左至右自左至右存放结点元素，即将编号为存放结点元素，即将编号为 i 结点元素存放结点元素存放在一维数组中下标为在一维数组中下标为 i 分量中（不用下标为分量中（不用下标为0存放单元）存放单元）。此此次序存放结构仅适合用于完全二叉树次序存放结构仅适合用于完全二叉树 q不是完全二叉树怎么办？不是完全二叉树怎么办？o一律转为完全二叉树！方法很简单，将各层空缺处统统补上一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚虚结点结点”，其内容为空。，其内容为空。q缺点：缺点：浪费空间；浪费空间；插入、删除不便插入、删除不便第44页二叉树存放（二）10/10/45二叉树链式存放结构 存放方式 普通从根结点开始存放，用二叉链表来表示。普通从根结点开始存放，用二叉链表来表示。（对应地，访问树中结点时也只能从根开始）（对应地，访问树中结点时也只能从根开始）二叉树结点特点二叉树是非线性结构，适适用链式存放结构lchild data rchild结点结构结点结构 data rchild lchild data parentlchildrchild二叉树结点数据类型定义：二叉树结点数据类型定义：typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;第45页二叉树遍历10/10/46v若要求先左后右，则只有前三种情况：qqDLR DLR 前（根）序遍历，前（根）序遍历，qqLDR LDR 中（根）序遍历，中（根）序遍历，qqLRD LRD 后（根）序遍历后（根）序遍历v依据遍历次序确定一棵二叉树q已知二叉树已知二叉树前序前序序列和序列和中序中序序列，序列，能够能够唯一确定一棵二叉树。唯一确定一棵二叉树。q已知二叉树已知二叉树后序后序序列和序列和中序中序序列，序列，能够能够唯一确定一棵二叉树。唯一确定一棵二叉树。q已知二叉树已知二叉树前序前序序列和序列和后序后序序列，序列，不能不能唯一确定一棵二叉树。唯一确定一棵二叉树。第46页例题解析10/10/47设二叉树设二叉树bt一个存放结构以下：一个存放结构以下：00237580101jhfdbacegi000940000012345678910lchilddatarchild 其中其中bt为树根结点指针为树根结点指针,lchild、rchild分别为结点左、右孩子分别为结点左、右孩子指针域指针域,在这里使用结点编号作为指针域值在这里使用结点编号作为指针域值,0表示指针域为空表示指针域为空;data为结点数据域。请完成以下各题：为结点数据域。请完成以下各题：(1)画出二叉树树形表示；画出二叉树树形表示；(2)写出按先序、中序和后序遍历二叉树写出按先序、中序和后序遍历二叉树bt所得到结点序列；所得到结点序列；第47页例题解析（续）10/10/4800237580101jhfdbacegi000940000012345678910lchilddatarchild(1)画出二叉树树形表示；因为第画出二叉树树形表示；因为第6号结点不是任何结点孩子结点，号结点不是任何结点孩子结点，该结点必定是根结点，再依据和该结点必定是根结点，再依据和结点左、右指针域值很轻易得到结点左、右指针域值很轻易得到该二叉树树形表示为该二叉树树形表示为 abgfdcehij第48页例题解析（续）10/10/4900237580101jhfdbacegi000940000012345678910lchilddatarchildabgfdcehij (2)写出按先序、中序和后写出按先序、中序和后序遍历二叉树序遍历二叉树bt所得到结点序所得到结点