《数据结构书本习题答案.pdf》由会员分享，可在线阅读，更多相关《数据结构书本习题答案.pdf（104页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.1简述下列概念：数据、数据元素、数据类型、数据结构、逻钳结构、存储结构、线性结构、非线性结构。数据：指能够被计算机识别、存储和加工处理的信息我体.数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。逻辑结构：指数据元素之间的逻辑关系。存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构
2、.线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有 个直接前趋和个直接后继。线性表就是个典型的线性结构。栈、队列、串等都是线性结构。非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。1.2 试举个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。答：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这 个 表 就 是 一 个数据结构。每个记录(有姓名
3、，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢？即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢？这就是存储结构的问题。在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。1.3 常用的
4、存储表示方法有哪几种？答：常用的存储表示方法有四种：顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构，通常借助于程序语言的指针类型描述。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引(D e n s e In
5、d e x)。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址1.4 设三个函数 f,g,h 分别为 f(n)=1 0 0 n 3+n 2+1 0 0 0 ,g(n)=2 5 n 3+5 0 0 0 n 2 ,h(n)=n 1.5+5 0 0 0 n l g n 请判断下列关系是否成立：(l)f(n)=O(g(n)(2)g(n)=O(f(n)(3)h(n)=O(n l.5)(4)h(n)=O(n l g n)分析：数学符号”0“的严格的数学定义：若 T (n)和 f (n)是定义在正整数集合上的两个函数，则 T (n)=
6、0 (f (n)表示存在正的常数C和nO,使得当nnO时都满足OWT(n)WC f (n)。通俗地说，就是当n-8时，f(n)的函数值增长速度与T (n)的增长速度同阶。一般，一个函数的增长速度与该函数的最高次阶同阶。即：O(f(n)=n 3O(g(n)=n 3O(h(n)=n l.5所以答案为：答：(1)成立。(2)成立。(3)成立。(4)不成立。1.5 设有两个算法在同一机器上运行，其执行时间分别为1 0 0 n 2和2 n,要使前者快于后者，n至少要多大？分析：要使前者快于后者，即前者的时间消耗低于后者，即：1 0 0 n 2 2 n求解上式，可得答：n=1 51.6 设n为正整数，利
7、用 大 记 号，将下列程序段的执行时间表示为n的函数。(l)i=l;k=0;w hi l e(i n)k=k+1 0*i;i+;)分析：i=l;/lk=0;/lw hi l e(i n)/n k=k+1 0*i;/n-1i+;/n-1)山以上列出的各语句的频度，可得该程序段的时间消耗：T(n)=1 +1 +n+(n-1 )+(n-1 )=3 n可表示为T(n)=O(n)(2)i=0;k=0;d o k=k+1 0*i;i+;)w hi l e(i n);分析：i=0;/Ik=0;/ld o /nk=k+1 0*i;/ni+;nwhile(in);/n由以上列出的各语句的频度，可得该程序段的时间
8、消耗：T(n)=l+1 +n+n+n+n=4n+2可表示为T(n)=O(n)i=l;j=0;while(i+jj)j+;else i+;)分析：通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且福执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而 while循环共做了 n 次，所以该程序段的执行时间为：T(n)=O(n)(4)x=n;/nlwhile(x=(y+l)*(y+l)y+;分析：由 x=n且 x 的值在程序中不变，又 while的循环条件(x=(y+l)*(y+l)可知：当(y+l)*(y+l)刚超过n 的值时退出循环。由(y+l)*(y+l)n 得：
9、y0)if(x100)x=x-10;y-;)else x+;分析:x=91;/ly=100;/lwhile(y0)/1101if(x100)/1100 x=x-10;/100y;/100)elsex+;/1000以上程序段右侧列出了执行次数。该程序段的执行时间为：T(n)=O(l)1.7 算法的时间复杂度仅与问题的规模相关吗？答：算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。1.8 按增长率由小至大的顺序排列下列各函数：2100,(3/2)n(2/3
10、)n,nn,n0.5,n!,2n,Ign,nlgn,n(3/2)答：常见的时间复杂度按数量级递增排列，依次为:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数 阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。先将题中的函数分成如下几类：常数阶：2100对数阶：IgnK 次方阶：n0.5、n(3/2)指数阶(按指数由小到大排)：nlgn、(3/2)n、2n、n!、nn注意：(2/3)?由于底数小于1,所以是一个递减函数，其数量级应小于常数阶。根据以上分析按增长率由小至大的顺序可排列如下：(2/3)n 2100 Ign n0.5 n(
11、3/2)nlgn (3/2)n 2n n!next-next 和 rear,查找时间都是 0(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。2.5 在单链表、双链表和单循环链表中，若仅知道指针p 指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少？答：下面分别讨论三种链表的情况。1.单链表。若指针p 指向某结点时，能够根据该指针找到其直接后继，能够顺后继指针链找到*p结点后的结点。但是由于不知道其头指针，所以无法访问到p 指针指向的结点的直接前趋。因此无法删去该结点。2.双链表。由于这样的链表提供双向指针，根据*p 结点的前趋指针和后继指针
12、可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为0(1)。3.单循环链表。根据L1知结点位置，可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p 结点的直接前趋。因此可以删去p 所指结点。其时间复杂度应为O(n)o2.6 下述算法的功能是什么？LinkList Demo(LinkList L)/L 是无头结点单链表ListNode*Q,*P;if(L&L-next)Q=L;L=L-next;P=L;while(P-next)P=P-next;P-next=Q;Q-next=NULL;)return L;/Demo答：该算法的功能是：将开
13、始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。2.7 设线性表的n 个结点定义为(aO,al,an-1)，重写顺序表上实现的插入和删除算法：InsertList和DeleteList.解:算法如下:#define ListSize 100/假定表空间大小为100typedef ini DataType;假定 DataType 的类型为 int 型typedef struct(DataType dataListSize;/向量 data 用于存放表结点int length;/当前的表长度 Seqlist;以上为定义表结构void Inser
14、tList(Seqlist*L,Datatype x,int i)(将新结点x 插入L 所指的顺序表的第i 个结点a i的位置上，即插入的合法位置为：0=ilengthintj;if(i L-length)Error(position error);非法位置，退出，该函数定义见教材P7.if(L-length=ListSize)ErrorC4overilowu);for(j=L-length-l;j=i;j-)L-data j+1 =L-data j;L-data i=x;L-length+4-;)void DeleteList(Seqlist*L,int i)/从 L 所指的顺序表中删除第i
15、 个结点ai,合法的删除位置为0=ilength-lintj;if(i=L-length)Error(u position error);for(j=i;j length;j+)L-dataj=L-data j+1;结点前移L-length-;/表长减小)2.8 试分别用顺序表和单链表作为存储结构，实现将线性表(aO,al,.an-l)就地逆置的操作，所谓 就地指辅助空间应为O(l)答：1.顺序表：要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：顺序表结构定义同上题void ReverseList(Seqlist*L)(
16、DataType temp;设置临时空间用于存放dataint i;for(i=0;iIength/2;i+)/L-length/2 为整除运算 temp=L-datai;/交换数据L-data i =L-datal L-length-1-i;L-dataf L-length-1 -i =temp;2.链表：分析：可以用交换数据的方式来达到逆置的目的。但是由于是单链表，数据的存取不是随机的，因此算法效率太低。可以利用指针改指来达到表逆置的目的。具体情况入下：(1)当链表为空表或只有一个结点时，该链表的逆置链表与原表相同。(2)当链表含2 个以上结点时，可将该链表处理成只含第一结点的带头结点链表
17、和一个无头结点的包含该链表剩余结点的链表。然后，将该无头结点链表中的所有结点顺着链表指针，由前往后将每个结点依次从无头结点链表中摘下，作为第一个结点插入到带头结点链表中。这样就可以得到逆置的链表。算法是这样的：结点结构定义如下：typedef char DataType;假设结点的数据域类型的字符typedef struct node 结点类型定义DataType data;结点的数据域struct node*next;结点的指针域JListNode;typedef ListNode*LinkList;ListNode*p;LinkList head;LinkList ReverseList(
18、LinkList head)/将 head所指的单链表(带头结点)逆置ListNode*p,*q;设置两个临时指针变量if(head-next&head-next-next)当链表不是空表或单结点时p=head-next;q=p-next;p-next=NULL;将开始结点变成终端结点while(q)每次循环将后一个结点变成开始结点p=q;q=q-next;p-next=head-next;head-next=p;)return head;)return head;如是空表或单结点表，直接返回head)2.9 设顺序表L 是一个递增有序表，试写一算法，将 x 插入L 中，并使L 仍是一个有序表
19、。答：因已知顺序表L 是递增有序表，所以只要从顺序表终端结点(设为i 位置元素)开始向前寻找到第一个小于或等于x 的元素位置i 后插入该位置即可。在寻找过程中，由于大于x 的元素都应放在x 之后，所以可边寻找，边后移元素，当找到第一个小于或等于x 的元素位置i 时，该位置也空出来了。算法如下：顺序表存储结构如题2.7void InsertIncreaseList(Seqlist*L,Datatype x)(int i;if(L-length=ListSize)EITOF(aoverflow);for(i=L-length;i0&L-data i-1 x;i-)L-data i=L-data i
20、;/比较并移动元素L-data i =x;L-length+;2.10 设顺序表L 是一个递减有序表，试写一算法，将 x 插入其后仍保持L 的有序性。答：与上题相类似，只要从终端结点开始往前找到第一个比x 大(或相等)的结点数据，在这个位置插入就可以了。(边寻找，边移动)算法如下：void InsertDecreaseList(Seqlist*L,Datatype x)int i;if(L-length=ListSize)Error(overflow);for(i=L-length;i0&L-data i-1 data i=L-data i;/比较并移动元素L-data i =x;L-leng
21、th+;)2.11 写一算法在单链表上实现线性表的ListLength(L)运算。解由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法如下:int ListLength(LinkList L)(int len=0;ListNode*p;p=L;设该表有头结点while(p-next)(p=p-next;len+;)return len;)2.1 2 已知L I和 L 2分别指向两个单链表的头结点，且已知其长度分别为m 和 n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。解：分析：山于要进行的是两单链表的连接，所以应找到放在前面的那张表的表尾结点
22、，再将后表的开始结点链接到前表的终端结点后即可。该算法的主要时间消耗是用在寻找第一张表的终端尾结点上。这两张单链表的连接顺序无要求，并且已知两表的表长，则为了提高算法效率，可选表长小的单链表在前的方式连接。具体算法如下：LinkList Link(LinkList LI,LinkList L2,int m,int n)将两个单链表连接在一起ListNode*p,*q,*s;/S指向短表的头结点,q 指向长表的开始结点，回收长表头结点空间if(mnext;free(L2);else s=L2;q=L 1 -next;free(L 1);p=s；while(p-next)p=p-next;查找短表
23、终端结点p-next=q;将长表的开始结点链接在短表终端结点后return s;)本算法的主要操作时间花费在查找短表的终端结点上，所以本算的法时间复杂度为：O(min(m,n)2.1 3 设 A 和 B 是两个单链表，其表中元素递增有序。试写一算法将A 和 B 归并成一个按元素值递减有序的单链表C,并要求辅助空间为0(1),请分析算法的时间复杂度。解：根据已知条件，A 和 B 是两个递增有序表，所以可以先取A 表的表头建立空的C 表。然后同时扫 描 A 表和B 表，将两表中最大的结点从对应表中摘下，并作为开始结点插入C 表中。如此反复，直到A 表 或 B 表为空。最后将不为空的A 表或B 表中
24、的结点依次摘下并作为开始结点插入C 表中。这时，得到的C 表就是由A 表和B 表归并成的一个按元素值递减有序的单链表C。并且辅助空间为O(l)o算法如下：LinkList MergeSort(LinkList A,LinkList B)/归并两个带头结点的递增有序表为一个带头结点递减有序表ListNode*pa,*pb,*q,*C;pa=A-next;pa指向A 表开始结点C=A;C-next=NULL;取A 表的表头建立空的C 表pb=B-next;/pb指向B 表开始结点free(B);回收B 表的头结点空间while(pa&pb)(if(pb-data data)/当 B 中的元素小于等
25、于A 中当前元素时，将 p a表的开始结点摘下q=pa;pa=pa-next;else/当 B 中的元素大于A 中当前元素时，将 pb表的开始结点摘下q=pb;pb=pb-next;q-next二 C-next;C-next=q;将摘下的结点q 作为开始结点插入C 表)若pa表非空，则处理pa表while(pa)q=pa;pa=pa-next;q-next=C-next;C-next=q;若pb表非空，则处理pb表while(pb)q=pb;pa=pb-next;q-next=C-next;C-next=q;return(C);)该算法的时间复杂度分析如下：算法中有三个w hile循环，其中第
26、二个和第三个循环只执行一个。每个循环做的工作都是对链表中结点扫描处理。整个算法完成后，A 表和B 表中的每个结点都被处理了一遍。所以若A 表 和 B 表的表长分别是m 和 n,则该算法的时间复杂度0(m+n)2.1 4 已知单链表L 是一个递增有序表，试写一高效算法，删除表中值大于m in 且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里m in和 max是两个给定的参数。请分析你的算法的时间复杂度.解：要解这样的问题，我们首先想到的是拿链表中的元素一个个地与max和 m in比较，然后删除这个结点。由于为已知其是有序链表，则介于m in和 m ax之间的结点必为连续的一
27、段元素序列。所以我们只要先找到所有大于m in结点中的最小结点的直接前趋结点*p 后，依次删除小于m ax的结点，直到第一个大于等于max结点*q 位置，然后将*p 结点的直接后继指针指向*q 结点。算法如下：void DeleteList(LinkList L,DataType min,DataType max)(ListNode*p,*q,*s;p=L;while(p-next&p-next-data next;q=p-next;/p指向第一个不大于min结点的直接前趋，q 指向第一个大于m in的结点while(q&q-datanext;free(s);删除结点，释放空间Ip-next=
28、q;/*p结点的直接后继指针指向*q 结点)2.15 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。解：本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。具体算法：void DeleteList(LinkList L)(ListNode*p,*q,*s;p=L-next;while(p-next&p-next-next)(q=p；山于要做删除操作，所以q 指针指向要删除元素的直接前趋while(q-next)if(p-data=q-next-data)s=q-next;q-nex
29、t=s-next;free(s);/删除与*p 的值相同的结点)else q=q-next;p=p-next;2.16 假设在长度大于1 的单循环链表中，既无头结点也无头指针。s 为指向链表中某个结点的指针，试编写算法删除结点*S的直接前趋结点。解：已知指向这个结点的指针是*S,那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向*S的直接前趋，然后用后删结点法，将结点*S的直接前趋结点删除即可。算法如下：void DeleteNode(ListNode*s)删除单循环链表中指定结点的直接前趋结点ListNode*p,*q;p=s;while(p-next-next!=s)p
30、=p-next;删除结点q=p-next;p-next=q-next;free(p);释放空间)注意：若单循环链表的长度等于1,则只要把表删空即可。2.1 7 已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。解：要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时,就摘下此结点链接到相应头结点指明的新链表中就是了。算法如下：设已建立三个带头结点的空循环链表A,B,C且 A、B、C 分别是尾
31、指针.void DivideList(LinkList L,LinkList A,LinkList B,LinkList C)(ListNode*p=L-next,*q;while(p)(if(p-data=a*&p-datadata=A&p-datanext;p=p-next;指向下一结点q-next二 Aonext;将字母结点链到A 表中A-next=q;A=q;)else if(p-data=Or&p-datanext;p=p-next;指 向 下一结点q-next=B-next;将数字结点链到B 表中B-next=q;B=q;)else 分出其他字符结点q=p-next;p=p-nex
32、t;指向下一结点q-nex仁C-next;将其他结点链到C 表中C-next=q;C=q;结束2.18设有一个双链表，每个结点中除有prior、data和 next三个域外，还有一个访问频度域fre q,在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,x)运算时，令元素值为x 的结点中freq域的值加I,并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。解：LocateNode运算的基本思想就是在双向链表中查找值为x 的结点，具体方法与单链表中查找一样。找到结点*p 后给fre
33、q域的值加1。由于原来比*p 结点查找频度高的结点都排它前面，所以，接下去要顺着前趋指针找到第一个频度小于或等于*p 结点频度的结点*q 后，将*p 结点从原来的位置删除，并插入到*q后就可以了。算法如下：双向链表的存储结构typedef struct dlistnodeDataType data;struct dlistnode*prior,*next;int freq;JDListNode;typedef DListNode*DLinkList;void LocateNode(LinkList L,DataType x)(ListNode*p,*q;p=L-next;带有头结点while(
34、p&p-data!=x)p=p-next;if(!p)ERRORCx is not in L);双链表中无值为x 的结点else p-freq+;/freq 力 口 1q=p-prior;以q 为扫描指针寻找第一个频度大于或等于*p 频度的结点while(q!=L&q-freqfreq)q=q-prior;if(q，next!=p)若*q 结点和*p 结点不为直接前趋直接后继关系，则将*P 结点链到*4 结点后p-prior-next=p-next;/*p 从原来位置摘下p-next-prior=p-prior;q-next-prior=p;将*p 插入*q 之后。p-next=q-next;
35、q-next=p;p-prior=q;)3.1 设将整数1,2,3,4 依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为 Push(l),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop()，则出栈的数字序列为何(这里Push表示i 进栈，Pop()表示出栈)？(2)能否得到出栈序列1423和 1432?并说明为什么不能得到或者如何得到。(3)请 分 析 1,2,3,4 的 24种排列中，哪些序列是可以通过相应的入出栈操作得到的。答：(1)出栈序列为：1324(2)不 能 得 到 1423序 列。因
36、 为 要 得 到 1 4 的 出 栈 序 列，则 应 做 Push(l),Pop(),Push(2),Push(3),Push(4),Pop()。这 样,3 在栈顶，2 在栈底，所以不能得到2 3 的出栈序列。能得到1432的出栈序列。具体操作为：Push(l),Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。(3)在 1,2,3,4的 24种排列中，可通过相应入出栈操作得到的序列是：1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321不能得到的序列是：1423
37、,2413,3124,3142,3412,4123,4132,4213,4231,43123.2 链栈中为何不设置头结点？答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。3.3 循环队列的优点是什么？如何判别它的空和满？答：循环队列的优点是：它可以克服顺序队列的“假上溢 现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的 空 或 满 不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用个元素的空间，每次入队前测试入队后头尾指针
38、是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。3.4 设长度为n 的链队用单循环链表表示，若设头指针，则入队HI队操作的时间为何？若只设尾指针呢？答：当只设头指针时，出队的时间为1,而入队的时间需要n,因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为l o 因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。3.5 指出下述程序段的功能是什么？(1)void Demo 1 (SeqStack*S)int i;arr64;n=0;whi
39、le(StackEmpty(S)arr|n+=Pop(S);for(i=0,i n;i+)Push(S,arri);/Demo 1(2)SeqStack SI,S2,tmp;DataType x;假设栈tmp和 S 2 已做过初始化while(!StackEmpty(&S 1)(x=Pop(&S 1);Push(&tmp,x);)while(!StackEmpty(&tmp)(x=Pop(&tmp);Push(&Sl,x);Push(&S2,x);(3)void Demo2(SeqStack*S,int m)/设 DataType 为 int 型SeqStack T;int i;InitSta
40、ck(&T);while(!StackEmpty(S)if(i=Pop(S)!=m)Push(&T,i);while(!StackEmpty(&T)(i=Pop(&T);Push(S,i)；)(4)void Demo3(CirQueue*Q)/设 DataType 为 int 型int x;SeqStack S;InitStack(&S);while(!QueueEmpty(Q)x=DeQueue(Q);Push(&S,x);while(!StackEmpty(&s)x=Pop(&S);EnQueue(Q,x);/Demo3(5)CirQueue QI,Q2;/设 DataType 为 int
41、 型int x,i,n=0;./设 Q I 已有内容，Q 2 已初始化过while(!QueueEmpty(&Q1)x=DeQueue(&Q1);EnQueue(&Q2,x);n+;for(i=0;i n;i+)x=DeQueue(&Q2);EnQueue(&Q1,x);EnQueue(&Q2,x);答：(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。(2)程序段的功能是利用tmp栈将一个非空栈s i 的所有元素按原样复制到一个栈S2当中去。(3)程序段的功能是利用栈T,将一个非空栈S 中值等于m 的元素全部
42、删去。(4)程序段的功能是将一个循环队列Q 经 过 S 栈的处理，反向排列，原来的队头变成队尾，原来的队尾变成队头。(5)这段程序的功能是将队列1 的所有元素复制到队列2 中去，但其执行过程是先把队列1 的元素全部出队，进入队列2,然后再把队列2 的元素复制到队列1中。3.6 回文是指正读反读均相同的字符序列，如abba和abdba”均是回文，但good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)解：根据提示，算法可设计为：以下为顺序栈的存储结构定义#define StackSize 100 假定预分配的栈空间最多为100个元素typedef char Dat
43、aType，假定栈元素的数据类型为字符typedef structDataType datafStackSize;int top;SeqStack;int IsHuiwen(char*t)判断t 字符向量是否为回文，若是，返 回 1,否则返回0SeqStack s;int i,len;char temp;InilStack(&s);len=strlen;求向量长度for(i=0;iTop=-1;/其实只是将栈置空)因为要置空的是栈S,如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的
44、结果返回给实参的话，就只能用指针来做参数传递了。3.8 利用栈的基本操作，写一个返回S 中结点个数的算法int StackSize(SeqStack S),并说明S 为何不作为指针参数？解：算法如下：int StackSize(SeqStack S)计算栈中结点个数int n=0;if(!EmptyStack(&S)(Pop(&S);n+;)return n;)上述算法的目的只要得到S 栈的结点个数就可以了。并不能改变栈的结构。所以S 不用指针做参数，以避免对原来的栈中元素进行任何改变。系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数。3.9 设计算法判断个算术表达式的圆
45、括号是否正确配对。(提示：对表达式进行扫描，凡遇到(就进栈,遇)就退掉栈顶的(，表达式被扫描完毕，栈应为空。解：根据提示，可以设计算法如下：ini PairBracket(char*SR)检查表达式ST 中括号是否配对int i;SeqStack S;定义一个栈InitStack(&s);for(i=0;itopO=-1;S-topl=StackSize;这里的top2也指出了向量空间，但由于是作为栈底，因此不会出错)int EmptyStack(DblStack*S,int i)判栈空(栈号i)return(i=0&S-topO=-1 1 1 i=1&S-top 1 =StackSize);
46、)int FullStack(DblStack*S)判栈满，满时肯定两头相遇return(S-topO=S-top 1-1);)void Push(DblStack*S,int i,DataType x)进栈(栈号i)if(FullStack(S)Error(Stack overflow);上溢、退出运行if(i=0)S-Data+S-topOJ=x;栈 0 入栈if(i=l)S-Data-S-topl=x;/栈 1 入栈)DataType Pop(DblStack*S,int i)出栈(栈号i)if(EmptyStack(S,i)Error(nStack underflow);下溢退出if(
47、i=0)return(S-Data S-topO-);返回栈顶元素，指针值减1if(i=l)return(S-Data S.topl+);因为这个栈是以另一端为底的，所以指针值加1。)3.11 Ackerman函数定义如下：请写出递归算法。r n+1 当 m=0 时AKM(m,n)=|AKM(m-1,1)当 mWO,n=0 时L AKM(m-l,AKM(m,n-l)当 mWO,n W 0 时解：算法如下int AKM(int m,int n)(if(m=0)return n+1;if(moO&n=0)return AKM(m-1,1);if(moO&noO)return AKM(m-1,AKM
48、(m,n-1);)3.12用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。解：算法设计如下：循环队列的定义#define QueueSize 100typedef char Datatype;设元素的类型为 char 型typedef struct int front;int rear;DataType DataQueueSize;JCirQueue;(1)置空队void InitQueue(CirQueue*Q)/置空队Q-front=Q-rear=0;)(2)判队空int EmptyQueue(
49、CirQueue*Q)判队空return Q-front=Q-rear;(3)判队满int FullQueue(CirQueue*Q)判队满如果尾指针加I 后等于头指针，则认为满return(Q-rear+1 )%QueueSize=Q-front;)(4)出队DataType DeQueue(CirQueue*Q)出队DataType temp;if(EmptyQueue(Q)Error(队已空，无元素可以出队)temp=Q-DataQ-front;保存元素值Q-front=(Q-front+1 )%QueueSize;/循环意义 I:的 加 1return temp;返回元素值)入队voi
50、d EnQueue(CirQueue*Q,DataType x)/入队if(FullQueue(Q)Error(队已满，不可以入队)Q-DataQ-rear=x;Q-rear=(Q-rear+1 )%QueueSize;/rear 指向下一个空元素位置)(6)取队头元素DataType FrontQueue(CirQueue*Q)取队头元素if(EmptyQueue(Q)Error(队空，无元素可取)return Q-DatalQ-frontJ;)3.13假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针)，试编写相应的置空队、判 队 空、入队和出队等算法。解：