数据结构复习与习题解析.ppt

数据结构与算法,复习与习题解析(第1-5讲）,第一讲绪论,了解数据结构有关概念的含义，特别是数据的逻辑结构和存储结构之间的关系；（重点）熟悉类C语言的书写规范；了解计算算法时间复杂度的方法。（难点）,22/11/2019,2,数据结构的定义,按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。,基本概念和术语,【数据】是对信息的一种符号表示。是可以输入计算机中，能被计算机识别处理和输出的一切符号集合。【数据元素】是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。也称为记录。【数据项】一个数据元素可由若干个数据项组成。是数据不可分割的最小单位。【数据对象】是性质相同的数据元素的集合。是数据的一个子集。,22/11/2019,4,【数据结构】相互之间存在一种或多种特定关系的数据元素的集合,计算机如何解决问题,22/11/2019,5,问题,机外表示处理要求,逻辑结构基本运算,数学模型,存储结构编程实现,实现,建模,求精,研究数据结构是为了帮计算机解决问题！,数据结构的研究内容,22/11/2019,6,【数据结构的三个方面研究内容】具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存储结构和对数据所施加的运算（操作）。,数据的逻辑结构（面向人类）,数据的存储结构（面向计算机）,数据的运算（操作）：检索、排序、插入、删除、修改等,线性结构,非线性结构,顺序存储,链式存储,线性表,栈,队列,树形结构,图形结构,散列存储,索引存储,串及数组,四种基本逻辑结构,22/11/2019,7,【集合】数据元素间除了“同属于一个集合”外，无其他关系。,【线性结构】1对1的关系比如线性表、栈、队列。,【树形结构】1对多的关系比如树。,【图形结构】多对多的关系比如图。,算法与数据结构,算法与数据结构关系密切选择的数据结构是否恰当直接影响算法的效率；而数据结构的优劣由算法的执行来体现。“算法+数据结构=程序”算法!=程序算法是供人阅读的，程序是让机器执行的算法用计算机语言实现时就是程序程序不具有算法的有穷性,算法的概念,算法是解决某个特定问题的求解步骤的描述。算法在计算机中表现为指令的有限序列，每条指令表示一个或多个操作。计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。程序不等于算法：计算机程序是算法的具体实现。,22/11/2019,9,（1）有穷性：一个算法必须在执行有穷步之后结束。（2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。（3）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。（4）输入：一个算法应该有零个或多个输入。（5）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。,算法的性质,算法设计的要求,正确性（四个境界）没有语法错误对于合法的输入数据能够产生满足要求的输出对于非法的输入数据能够得出满足规格说明的结果对于任何测试数据都有满足要求的输出结果可读性：便于阅读、理解和交流健壮性：不合法数据也能合理处理时间效率高和存储量低,22/11/2019,11,算法效率的度量方法,事后统计方法通过设计好的测试程序和数据，利用计算机测量其运行时间。缺陷：需要先编写程序；和计算机软硬件相关；和测试数据相关。事前分析估算方法（我们的选择）依据统计方法对算法进行估算。m=f(n)，m是语句总的执行次数，n是输入的规模。和问题输入规模相关，独立于程序设计语言和计算机软硬件,22/11/2019,12,算法时间复杂度,22/11/2019,13,在进行算法分析时，语句的总执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，用“大O记法”记作：T(n)=O(f(n)。由此得到的T(n)的数量级叫“大O阶”。它表示随问题规模n的增大，算法执行时间增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。其中f(n)是问题规模n的某个函数。一般情况下，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为问题的规模(大小)的量度。,则算法的时间复杂度为O(n3),算法空间复杂度,22/11/2019,15,算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n)，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。,我们主要讨论时间复杂度问题。,例题解析,【例1】数据元素之间的关系在计算机中有几种表示方法？各有什么特点？答：四种表示方法（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。（3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。,22/11/2019,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),22/11/2019,17,例题解析,【例3】已知如下程序段for(i=n;i0;i-)语句1x=x+1;语句2for(j=n;j=i;j-)语句3y=y+1;语句4语句1执行的频度为_；语句2执行的频度为_；语句3执行的频度为_；语句4执行的频度为_。答：（1）n+1（2）n（3）n(n+3)/2（4）n(n+1)/2,第二讲线性表,线性结构的定义和特点在数据元素的非空有限集中，有且仅有一个开始结点和一个终端结点，并且所有结点只有一个直接前趋和一个直接后继。简言之，线性结构反映结点间的逻辑关系是一对一。线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最简单、最常用的是线性表。线性表的存储方法顺序存储：逻辑上相邻物理上一定相邻链式存储：逻辑上相邻物理上不一定相邻,顺序表,顺序表线性表的顺序存储表示顺序存储用一组地址连续的存储单元依次存储线性表的元素，可通过数组来实现。（逻辑上相邻物理上一定相邻）LOC(ai)=LOC(a1)+(i-1)len（a1为首元素，len为单个元素占用空间长度）顺序存储的优点可以随机存取表中任一元素O(1)；存储空间使用紧凑顺序存储的缺点在插入元素时平均需要移动n/2个元素，删除某一元素时，平均需要移动n-1/2个元素。算法的平均时间复杂度为O(n)预先分配空间需按最大空间分配，利用不充分;表容量难以扩充,22/11/2019,20,链表,链式存储结构特点用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息链式存储结构的优点：结点空间可以动态申请和释放；数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。链式存储结构的缺点：每个结点的指针域需额外占用存储空间。当数据域所占字节不多时，指针域所占存储空间的比重显得很大。链表是非随机存取结构。对任一结点的操作都要从头指针依链查找该结点，这增加了算法的复杂度O（n）不便于在表尾插入元素：需遍历整个表才能找到位置。,22/11/2019,21,例题解析,【例1】说明在线性表的链式存储结构中，头指针与头结点之间的根本区别。答：在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。,22/11/2019,22,例题解析,【例2】设顺序表va中的数据元素递增有序。试设计一个算法，将x插入到顺序表的适当位置上，以保持该表的有序性。答：voidInsert_SqList(SqListva,intx)/*把x插入递增有序表va中*/inti;if(va.lengthMAXSIZE)return;for(i=va.length-1;va.elemix/*Insert_SqList*/,22/11/2019,23,#defineMAXSIZE100typedefstructElemType*elem;intlength;SqList；,例题解析,【例3】设单链表结点指针域为next，试写出删除链表中指针p所指结点的直接后继的C语言语句。答：q=p-next;p-next=q-next;free(q);,22/11/2019,24,例题解析,【例4】设单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，请写出在p结点之前插入s结点的操作。答：设单链表的头结点的头指针为head,且pre=head；while(pre-next!=p)pre=pre-next;s-next=p;pre-next=s;,22/11/2019,25,例题解析,【例5】试编写在带头结点的单链表中删除（一个）最小值结点的算法。voiddelete（Linklistpa=ha-next;while(1)_)if(2)_)(3)_);free(pa);pa=(4)_);elsepa-coef(5)_);pa-exp(6)_);q=(7)_);pa=(8)_);,22/11/2019,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取下一元素,第三讲栈和队列,栈限定仅在表尾进行插入和删除的线性表，把这个表尾称为栈顶。特点后进先出(LIFO表)栈的存储方法栈的顺序存储顺序栈栈的链式存储链栈,22/11/2019,28,关于栈要求掌握的内容,22/11/2019,29,栈的基本概念：LIFO,栈的存储,栈的应用（了解）,顺序栈（熟练掌握）,链栈（熟练掌握）,初始化,取栈顶,入栈出栈,判断栈空,栈,初始化,取栈顶,入栈出栈,判断栈空,队列定义,22/11/2019,30,队列的定义,队列：线性表(queue),特点：先进先出(FIFO结构)。,队尾,队头,当队列中没有元素时称为空队列。,表尾称为队尾(rear)表头称为队头(front)插入元素称为入队删除元素称为出队,限定在表的一端插入、另一端删除。,顺序队列的假溢出问题,22/11/2019,31,在顺序队列中，当尾指针已经指向了队列的最后一个位置即数组上界时，若再有元素入队，就会发生“溢出”。,“假溢出”队列的存储空间未满，却发生了溢出。,(1)、平移元素：把元素平移到队列的首部。效率低。,解决“假溢出”的问题有两种可行的方法：,(2)、将新元素插入到第一个位置上，构成循环队列，入队和出队仍按“先进先出”的原则进行。操作效率、空间利用率高。,循环队列,22/11/2019,32,队空条件:front=rear(初始化时：front=rear)队满条件：front=(rear+1)%N(N=maxsize)队列长度：L=（Nrearfront）%N,选用空闲单元法：即front和rear之一指向实元素，另一指向空闲元素。,问2：在具有n个单元的循环队列中，队满时共有多少个元素？,n-1个,5,问1：左图中队列长度L=？,例题解析,【例1】一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？答：43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，只需压入一个立即弹出一个即可。,22/11/2019,33,例题解析,【例2】如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？答：435612中到了12顺序不能实现；135426可以实现。,22/11/2019,34,例题解析,【例3】一个栈的输入序列为123，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？答：可以通过穷举所有可能性来求解：1入1出，2入2出，3入3出，即123；1入1出，2、3入3、2出，即132；1、2入，2出，3入3出，即231；1、2入，2、1出，3入3出，即213；1、2、3入，3、2、1出，即321；合计有5种可能性。,22/11/2019,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则为队满。,22/11/2019,36,第四讲串和数组,【例1】填空题：1.空格串是指_，其长度等于_。【答案】（1）由空格字符（ASCII值32）所组成的字符串（2）空格个数2组成串的数据元素只能是_。【答案】字符【解析】串是一种特殊的线性表，其特殊性在于串中的元素只能是字符型数据。3两个字符串相等的充分必要条件是_。【答案】两串的长度相等且两串中对应位置上的字符也相等。4一个字符串中_称为该串的子串。【答案】任意个连续的字符组成的子序列,22/11/2019,37,例题解析,【例2】设计一个算法，将字符串s的全部字符复制到字符串t中，不能利用strcpy函数。答：【算法分析】要实现两个字符串的复制，实质为两个字符数组之间的复制，在复制时，一个字符一个字符的复制，直到遇到0，0一同复制过去，0之后的字符不复制。【算法源代码】voidcopy(chars,chart)inti;for(i=0;si!=0;i+)ti=si;ti=si;,22/11/2019,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=15Loc（3,3）=Loc（0,0）+3*15+3=644+45+3=692.,22/11/2019,39,例题解析,【例4】设有一个nn的对称矩阵A，为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储方式。试问：（1）存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？（2）若在一维数组B中从0号位置开始存放，则对称矩阵中的任一元素aij在只存下三角部分的情形下应存于一维数组的什么下标位置？给出计算公式。答：（1）数组B共有12+3+n=（n+1）*n/2个元素。（2）只存下三角部分时，若ij，则数组元素Aij前面有i-1行（1i-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若in则无右孩子。,例题解析,1深度为H的完全二叉树至少有_个结点；至多有_个结点；H和结点总数N之间的关系是_。【答案】（1）2H-1（2）2H-1（3）H=log2N+12一棵有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。,22/11/2019,43,二叉树的存储（一）,22/11/2019,44,二叉树存储方法有顺序存储和链式存储二叉树顺序存储结构完全二叉树：用一组地址连续的存储单元依次自上而下、自左至右存储结点元素，即将编号为i的结点元素存储在一维数组中下标为i的分量中（不用下标为0存储单元）。此顺序存储结构仅适用于完全二叉树不是完全二叉树怎么办？一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。缺点：浪费空间；插入、删除不便,二叉树的存储（二）,22/11/2019,45,二叉树链式存储结构,存储方式一般从根结点开始存储，用二叉链表来表示。（相应地，访问树中结点时也只能从根开始）,二叉树结点的特点二叉树是非线性结构，适合用链式存储结构,二叉树结点数据类型定义：typedefstructBiTNodeTElemTypedata;structBiTNode*lchild,*rchild;BiTNode,*BiTree;,二叉树遍历,22/11/2019,46,若规定先左后右，则只有前三种情况：DLR前（根）序遍历，LDR中（根）序遍历，LRD后（根）序遍历根据遍历顺序确定一棵二叉树已知二叉树的前序序列和中序序列，可以唯一确定一棵二叉树。已知二叉树的后序序列和中序序列，可以唯一确定一棵二叉树。已知二叉树的前序序列和后序序列，不能唯一确定一棵二叉树。,例题解析,22/11/2019,47,设二叉树bt的一种存储结构如下：,其中bt为树根结点指针,lchild、rchild分别为结点的左、右孩子指针域,在这里使用结点编号作为指针域值,0表示指针域为空;data为结点的数据域。请完成下列各题：,(1)画出二叉树的树形表示；,(2)写出按先序、中序和后序遍历二叉树bt所得到的结点序列；,例题解析（续）,22/11/2019,48,(1)画出二叉树的树形表示；因为第6号结点不是任何结点的孩子结点，该结点必定是根结点，再根据和结点左、右指针域的值很容易得到该二叉树的树形表示为,例题解析（续）,22/11/2019,49,(2)写出按先序、中序和后序遍历二叉树bt所得到的结点序列；,a.先序序列,a,b,c,e,d,f,h,g,i,j,例题解析（续）,22/11/2019,50,(2)写出按先序、中序和后序遍历二叉树bt所得到的结点序列；,a.先序序列,a,b,c,e,d,f,h,g,i,j,b.中序序列,e,c,b,h,f,d,j,i,g,a,例题解析（续）,22/11/2019,51,(2)写出按先序、中序和后序遍历二叉树bt所得到的结点序列；,a.先序序列,a,b,c,e,d,f,h,g,i,j,b.中序序列,e,c,b,h,f,d,j,i,g,a,b.后序序列,e,c,h,f,j,i,g,d,b,a,树与森林,【例题】从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。答：树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树惟一表示，并可使用二叉树的一些算法去解决树和森林中的问题。树和二叉树的区别有3：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。,22/11/2019,52,例题解析,【例题】已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA（1）给出这棵二叉树；（2）转换为对应的森林。答：,22/11/2019,53,例题解析,【例题】假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI,中序序列为BCDAFEHIG。请画出该二叉树，并将其转换为对应的森林。答：按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部分：左子树和右子树。若左子树不空，层次序列中第二个结点为左子树的根；若右子树为空，则层次序列中第三个结点为右子树的根。对右子树也作类似的分析。层次序列的特点是，从左到右每个结点或是当前情况下子树的根或是叶子。,22/11/2019,54,二叉树的应用：Huffman树,22/11/2019,55,Huffman树的应用带权路径计算WPL带权路径长度WPL最小的二叉树称作赫夫曼树具有相同带权结点的哈夫曼树不惟一满二叉树不一定是哈夫曼树哈夫曼树的结点的度数为0或2，没有度为1的结点。包含n个叶子结点的哈夫曼树中共有2n1个结点。,Huffman树的构造过程,给定权值集w=2,3,4,7,8,9,试构造关于w的的一颗哈夫曼树，并求其带权路径长度WPL。,22/11/2019,56,2,3,4,7,8,9,4,7,8,9,2,3,5,7,8,9,2,3,5,4,9,9,2,3,5,4,9,7,8,15,Huffman树的构造过程,22/11/2019,57,给定权值集w=2,3,4,7,8,9,试构造关于w的的一颗哈夫曼树，并求其带权路径长度WPL。,7,8,15,9,2,3,5,4,9,18,7,8,15,9,2,3,5,4,9,18,33,WPL=,(2+3),4,+,4,3,+,9,2,+,(7+8),2,=80,【例题】T=(a,2),(b,3),(c,4),(d,7),(e,9)为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度WPL、T中每个字符的哈曼夫编码和哈夫曼编码的平均长度。,2,3,4,7,9,Huffman编码过程,T=(a,2),(b,3),(c,4),(d,7),(e,9)为带权字符集，试构造关于该字符集的一颗哈夫曼树，求其加权路径长度WPL、T中每个字符的哈曼夫编码和哈夫曼编码的平均长度。,2,3,4,7,9,2,3,5,T=(a,2),(b,3),(c,4),(d,7