第12章讨论题答案

第一章绪论1、研究和讨论数据结构的目的【参考答案】研究和讨论数据结构的目的是为了让计算机能够对数据进行更好的处理。从软件设计和程序设计角度看，应包括两个方面：（1）概念上一致；（2）更高的处理效率。2、数据结构与程序设计的关系【参考答案】数据结构就是为程序设计而产生，没有程序设计，数据结构就无用武之地，设计出的各种结构将会变成纯粹的脑力游戏而已，无实际价值；而没有数据结构，程序设计的效用将大打折扣，而且面对复杂问题时根本不现实。可以这样说，没有程序设计，就没有数据结构，反之亦然。3、数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？【参考答案】数据类型是一个值的集合和定义在这个值集上的一组操作的总称，如C语言中的整型、实型、字符型等；抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。抽象数据类型可理解为数据类型的进一步抽象。即把数据类型和数据类型上的运算捆在一起，进行封装。抽象数据类型的主要特点是数据抽象和数据封装，它的出现使程序设计不再是“艺术”，而是向“科学”迈进了一步。4、数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？【参考答案】数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则是依赖于存储结构。5、当你为解决某一问题而选择数据结构时，应从哪些方面考虑？在编制管理通讯录的程序时,什么样的数据结构合适?为什么?【参考答案】通常从两方面考虑：第一是算法所需的存储空间量；第二是算法所需的时间。对算法所需的时间又涉及以下三点：（1）程序运行时所需输入的数据总量。（2）计算机执行每条指令所需的时间。（3）程序中指令重复执行的次数。仅供参考：可以从两方面进行讨论：针对通讯录较少变动（如城市私人电话号码），主要用于查询，以顺序存储较方便，既能顺序查找也可随机查找；而如果通讯录经常有增删操作，用链式存储结构较为合适，将每个人的情况作为一个元素（即一个结点存放一个人），设姓名作关键字，链表安排成有序表，这样可提高查询速度。第二章线性表1、线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？【参考答案】(1)选用链表，由于多个线性表在处理过程中长度都在动态变化，主要操作是插入、删除操作，顺序表插入或删除元素时不方便，而用链表的存储结构更加灵活。（2）选用顺序表，由于线性表很少进行插入和删除，主要用于存取，用顺序表能更好的实现这样的要求。2、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？【参考答案】①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。3、举出生活中常见的几种线性表（至少5种），并说明如何用程序加以实现。生活中的线性表是否均可以用本章讨论的线性表结构予以表示或模拟呢？为什么?【参考答案】排队买票、火车车厢、12星座列表、班级同学的点名册、手机通讯录等等，对于排队买票、班级同学的点名册、手机通讯录可以用顺序表按一定序存储，而火车车厢、12星座列表可以用链表存储。生活中的线性表并不是都可以用本章讨论的线性表结构予以表示或模拟，存储结构实际还包括索引结构和散列结构，由此产生的索引表和散列表在生活中应用也是很广泛的。4、试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。voiddelete（Linklist&L）【参考答案】[题目分析]本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。LinkedListDelete（LinkedListL）∥L是带头结点的单链表，本算法删除其最小值结点{p=L-next；∥p为工作指针。指向待处理的结点。假定链表非空pre=L；∥pre指向最小值结点的前驱q=p；∥q指向最小值结点，初始假定第一元素结点是最小值结点while（p-next!=null）{if（p-next-dataq-data）{pre=p；q=p-next；}∥查最小值结点p=p-next；∥指针后移}pre-next=q-next；∥从链表上删除最小值结点free（q）；∥释放最小值结点空间}5、约瑟夫问题问题描述如下：m个人围成一圈，每个人手里有一个令牌（令牌值为一个正整数）从第一个人开始报数，数到n的人出圈，同时将其令牌的值作为新的n值；再由下一个人开始报数，数到n的人出圈；……依次输出出圈的人的编号。【参考答案】思路一：设一个包括m个元素的数组，初始时将数组的每个元素存放所持令牌值。从第一个元素开始，依次遍历数组，并通过计数器计数（如果元素所存令牌值已被清0，则不计数），当计数器的值为n时，输出该元素的下标（它即是应该出圈人的编号），并将该元素所存令牌值取出，设为新的n，同时将计数器值归0。然后将该元素所存令牌值清0，使以后计数时不再起作用，相当于该人已出圈。再从下一个元素开始，依据上面的方法，如此继续，直到输出m个值以后结束。参考程序：voidJoseph(intplayer[],intm,intn){inti=0,Counter=0,del=0;//i记录序号下标，Counter表示计数器，del表示当前已出圈人数while(delm)//delm表示当前还有人未出圈{if(player[i]!=0)//数组当前元素为0表示该人已出圈，不计其数{Counter++;if(Counter==n){printf(“出圈人序列号为%d\n”,i);n=player[i];//提取出圈人令牌值作为新的nplayer[i]=0;//出圈人元素清0del++;//出圈人数增1Counter=0；//计数器归0}}i=(++i)%m;//i后移，指向下一个人}}思路二：利用不带头结点的循环单链表解决。设一个包括m个元素的循环单链表，每个结点有三个数据域，分别保存：游戏者编号、令牌值、下一结点指针。从第一个结点开始，依次遍历链表，并通过计数器计数，当计数器的值为n时，输出该结点的所存编号（它即是应该出圈人的编号），并将该结点所存令牌值取出，设为新的n，同时将计数器值归0。然后将该结点从链表中删除，使以后计数时不再起作用，相当于该人已出圈。再从下一个结点开始，依据上面的方法，如此继续，直到输出m个值以后结束。参考程序：voidJoseph(Linklist&L,intn){intCounter=1;p=L-next;∥p为工作指针，指向第一个游戏者结点pre=L;//∥pre指向第一个游戏者结点的前驱while(pre!=p){if(Countern)//如果计数器未达到n,指针p和pre皆向后移动一个结点，同时计数器加1{pre=p;p=p-next;Counter++;}else//如果计数器达到n,指针p所指即为出圈人结点，pre则指向出圈人结点的前驱{pre-next=p-next;//pre-next指向p的后继，以便删除出圈人结点printf(出圈人序列号为%d\n,p-index);//输出出圈人序号n=p-token;//提取出圈人所持令牌值作为新的nfree(p);p=pre-next;Counter=1;}}printf(出圈人序列号为%d\n,p-index);//输出最后一个出圈人序号free(p);//删除最后一个结点L=NULL;}算法：voidJoseph(Node*head,intn,intm)//m:总人数n:出列者报的数{inti,j,;Node*p,*q;p=head;for(j=1;j=m;j++)//逐个删除结点，直至全部出列{for(i=1;in;i++)p=p-next;//找到应出列的人printf(%d,p-data);//输出出列者序号n=p-token;//n为下次应出人员计数q=p-next;p-next=p-next-next;//连接被删结点前后的两个节点free(q);//释放指针q所指变量的存储空间}}