数据结构(c语言版)第三版习题解答.rtf

《数据结构(c语言版)第三版习题解答.rtf》由会员分享，可在线阅读，更多相关《数据结构(c语言版)第三版习题解答.rtf（111页珍藏版）》请在沃文网上搜索。

1、 1 数据结构（C语言版）（第3版）习题解析 揭安全 李云清 杨庆红 编著 江西师范大学计算机信息工程学院 联系方式： 2012年12月 2 第1章 绪论 1.1什么是数据结构？【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。1.2 数据结构涉及哪几个方面？【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集合。1.3 两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？【答】：不能，运算集合是数据结构的重要组成

2、部分，不同的运算集合所确定的数据结构是不一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样，所以它们是两种不同的数据结构。1.4 线性结构的特点是什么？非线性结构的特点是什么？【答】：线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端结点，其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性结构则没有这个特点，元素之间的关系可以是一对多的或多对多的。1.5 数据结构的存储方式有哪几种？【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。1.6 算法有哪些特点？它和程序的主要区别是什么？【答】：算法具有（1）有穷

3、性（2）确定性（3）0个或多个输入（4）1个或多个输出（5）可行性等特征。程序是算法的一种描述方式，通过程序可以在计算机上实现算法。1.7 抽象数据类型的是什么？它有什么特点？【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽

4、象数据类型的使用者依据这些描述使用抽象数据类型。1.8 算法的时间复杂度指的是什么？如何表示？【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为n的数据处理问题，用T(n)表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写O符号表示算法的时间复杂度

5、，大写O符号给出了函数f的一个上限。其它义如下：定义：f(n)=O(g(n)当且仅当存在正的常数c和n0，使得对于所有的nn0，有f(n)c g(n)。3 上述定义表明，函数f顶多是函数g的c倍，除非n 小于n0。因此对于足够大的n(如nn0)，g是f 的一个上限（不考虑常数因子c）。在为函数f 提供一个上限函数g 时，通常使用比较简单的函数形式。比较典型的形式是含有n的单个项（带一个常数系数）。表1-1列出了一些常用的g函数及其名称。对于表1-1中的对数函数logn，没有给出对数基，原因是对于任何大于1的常数a和b都有logan=logbn/logba,所以logan和logbn都有一个相对

6、的乘法系数1/logba，其中a是一个常量。表1-1常用的渐进函数 函数 名称 1 常数 logn 对数 n 线性 nlogn n个logn n2 平方 n3 立方 2n 指数 n!阶乘 1.9 算法的空间复杂度指的是什么？如何表示？【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表示为问题规模的函数，并通过大写O符号表示空间复杂度。1.10 对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度T(n)。（1）i+;（2）for(i=0;in;i+)if(aix)x=ai;（3）for(i=0;in;i+)for(j=0;jn;j+)print

7、f(“%d”,i+j);（4）for(i=1;i=n-1;i+)k=i;for(j=i+1;jaj+1)k=j;t=ak;ak=ai;ai=t;（5）for(i=0;in;i+)for(j=0;jn;j+)+x;s=s+x;【答】：（1）O（1）；（2）O（n）；（3）O（n2）；（4）O（n2）；（5）O（n2）4 第2章 线性表及其顺序存储 2.1 选择题（1）表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（E），删除一个元素所需移动元素的平均个数为（A）。A（n1）/2 Bn Cn+1 Dn1 En/2 F(n+1)/2 G

8、(n2)/2（2）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列为e2、e4、e3、e6、e5和e1，则栈S的容量至少应该为（C）。A6 B4 C3 D2（3）设栈的输入序列为1、2、3 n，若输出序列的第一个元素为n，则第i个输出的元素为（B）。A不确定 Bni+1 Ci Dni（4）在一个长度为n的顺序表中删除第i个元素（1=i=n）时，需向前移动（A）个元素。Ani Bni+1 Cni1 Di（5）若长度为n的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时间复杂度为（A）。AO(n)BO(1

9、)CO(n2)DO(n3)（6）表达式a*(b+c)d的后缀表达式是（B）。Aabcd*+Babc+*d Cabc*+d D+*abcd（7）队列是一种特殊的线性表，其特殊性在于（C）。A插入和删除在表的不同位置执行 B插入和删除在表的两端位置执行 C插入和删除分别在表的两端执行 D插入和删除都在表的某一端执行（8）栈是一种特殊的线性表，具有（B）性质。A先进先出 B先进后出 C后进后出 D顺序进出（9）顺序循环队列中（数组的大小为n），队头指示front指向队列的第1个元素，队尾指示rear指向队列最后元素的后1个位置，则循环队列中存放了n 1个元素，即循环队列满的条件为（B）。A(rear

10、+1)%n=front1 B(rear+1)%n=front C(rear)%n=front Drear+1=front（10）顺序循环队列中（数组的大小为6），队头指示front和队尾指示rear的值分别为3和0，当从队列中删除1个元素，再插入2个元素后，front和rear的值分别为（D）。A5和1 B2和4 C1和5 D4和2 2.2什么是顺序表？什么是栈？什么是队列？5【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶），因此，栈具有先进后出、后进先出的特点。队列也是一种特殊

11、的线性表，它的特殊性表现在约定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具有先进先出，后进后出的特点。2.3设计一个算法，求顺序表中值为x的结点的个数。【答】：顺序表的存储结构定义如下：#include#define N 100 /*预定义最大的数据域空间*/typedef int datatype;/*假设数据类型为整型*/typedef struct datatype aN;/*此处假设数据元素只包含一个整型的关键字域*/int size;/*线性表长度*/sequence_list;/*预定义的顺序表类型*/算法count()用于求顺序表H中值为x的结

12、点的个数。int count(sequence_list*H,datatype x)int j=0;int i;for(i=0;isize;i+)if(H-ai=x)j+;return j;2.4 设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组a中，倒置的结果是使得数组a中的a0等于原来的最后一个元素，a1 等于原来的倒数第2个元素，a的最后一个元素等于原来的第一个元素。【答】：实现顺序表倒置的算法程序如下：void verge(seqlist*L)int t,i,j;i=0;j=L-length-1;while(idatai;L-datai+=L-dataj;L-da

13、taj-=t;2.5已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x的结点，使顺序表中的结点仍然是从小到大有序。【答】：实现本题要求的算法程序如下：6 void insertx(seqlist*L,datatype x)int j;if(L-lengthlength-1;while(j=0&L-datajx)L-dataj+1=L-dataj;j-;L-dataj+1=x;L-length+;2.6 将下列中缀表达式转换为等价的后缀表达式。(1)5+6*7(2)(5-6)/7(3)5-6*7*8(4)5*7-8(5)5*(7-6)+8/9(6)7*(5-6*8)-9【答

14、】：(7)5+6*7 后缀表达式：5 6 7*+(8)(5-6)/7 后缀表达式：5 6-7/(9)5-6*7*8 后缀表达式：5 6 7*8*-(10)5*7-8 后缀表达式：5 7*8-(11)5*(7-6)+8/9 后缀表达式：5 7 6-*8 9/+(12)7*(5-6*8)-9 后缀表达式：7 5 6 8*-*9-2.7 循环队列存储在一个数组中，数组大小为n，队首指针和队尾指针分别为front和rear，请写出求循环队列中当前结点个数的表达式。【答】：循环队列中当前结点个数的计算公式是：(n+rear-front)%n 2.8编号为1,2,3,4的四列火车通过一个栈式的列车调度站，

15、可能得到的调度结果有哪些？如果有n列火车通过调度站，请设计一个算法，输出所有可能的调度结果。【答】：方法一：算法思想：逐次输出所有可能，用回溯法。即：总体：对原始序列中的每一个元素，总是先入栈，后出栈 1入栈后的操作：a.该元素出栈；b.下一个元素入栈；2出栈后的操作：a.（栈中其他元素）继续出栈；b.（原始序列中）下一个数入栈；注意：回溯法，关键在于回溯，即在某分支结点X：处理X的一个子分支，再退回分支X，接着处理X的下一个子分支,若所有X的子分支处理完，再退回上一层分支节点。所谓“退回”，7 实际上就是恢复。程序代码：(2_8_1.c)#include#define MAX 26 type

16、def struct s char aMAX;int top;Stack;/*定义一些全局变量*/Stack S;/*定义全局性的栈*/char dMAX,seqMAX;/*dMAX用于存储原始入栈序列，seqMAX用于存储输出序列*/int len;/*定义将通过栈的元素个数*/int count=0;/*用于统计输出序列的个数 */void initStack(Stack*S)/*初始化空栈*/S-top=-1;void push(Stack*S,char x)/*进栈*/if(S-top=MAX)return;S-top+;S-aS-top=x;char pop(Stack*S)/*出栈

17、*/if(S-top=-1)printf(ERROR,POP Empty Stack);return-1;S-top-;return S-aS-top+1;int isEmpty(Stack*S)/*判断栈是否为空*/if(S-top=-1)return 1;return 0;void outSeq(char*seq,int len)/*输出顶点序列*/int i;for(i=0;ilen;i+)printf(%2c,seqi);printf(n);void scheduler(int pos,int seq_pos)8 /*pos:处理到原始数据中的第pos个元素，seq_pos：若出栈，应

18、放在当前输出数组的第seq_pos个位置*/int i=0;char t;/*对任何一个数，总是先进栈，再出栈。另外，这里不需要循环，类似于“查找数组中元素”用递归*/if(pos=len&isEmpty(&S)outSeq(seq,len);count+;int main()int i;printf(nplease input the num be scheduled:);scanf(%d,&len);/*用len存储待调度的火车数量*/for(i=0;i1时，perm(R)由(r1)perm(R1),(r2)perm(R2),(rn)perm(Rn)构成。依此递归定义，可设计产生perm(

19、R)的递归算法如下：递归解法：(2_8_2.c)#include int cont=1;/*全局变量，用于记录所有可能的出栈序列个数*/void print(int str,int n);/*求整数序列str从k到n的全排列*/void perm(int str,int k,int n)int i,temp;if(k=n-1)print(str,n);else for(i=k;in;i+)temp=strk;strk=stri;stri=temp;perm(str,k+1,n);/*递归调用*/temp=stri;stri=strk;strk=temp;/*本函数判断整数序列str是否满足进出

20、栈规则,若满足则输出*/void print(int str,int n)int i,j,k,l,m,flag=1,b2;for(i=0;in;i+)/*对每个stri判断其后比它小的数是否为降序序列*/m=0;for(j=i+1;jstrj)if(m=0)bm+=strj;else if(strjb0)flag=0;else b0=strj;if(flag)/*满足出栈规则则输出str中的序列*/10 printf(%2d:,cont+);for(i=0;in;i+)printf(%d,stri);printf(n);int main()int str100,n,i;printf(input

21、 a int:);/*输出排列的元素个数*/scanf(%d,&n);for(i=0;in;i+)/*初始化排列集合*/stri=i+1;printf(input the result:n);perm(str,0,n);printf(n);return 0;当参与进出栈的元素个数为4时，输出的结果如下图所示。该算法执行的时间复杂度为O（n!）。随着n的增大，算法的执行效率非常的低。非递归解法：（2_8_3.c）对一组数穷尽所有排列，还可一种更直接的方法，将一个排列看作一个长整数，则所有排列对应着一组整数，将这组整数按从小到大的顺序排成一个数列，从对应最小的整数开始，按数列的递增顺序逐一列举每个

22、排列对应的每一个整数，这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为1,2,4,6,5,3，并令其对应的长整数为124653。要寻找比长整数124653更大的排列，可从该排列的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大时，如本例中的6比它的前一位数字4大，则说明还有可能对应更大整数的排列。但为顺序从小到大列举出所有的排列，不能立即调整得太大，如本例中将数字6与数字4交换得到的排列为126453就不是排列124653的下一个排列。为得到排列124653的下一个排列，应从已考察过的那部分数 11 字中选出

23、比数字4大，但又是它们中最小的那一个数字，比如数字5，与数字4交换。该数字也是从后向前考察过程中第一个比4大的数字，5与4交换后，得到排列125643。在前面数字1，2，5固定的情况下，还应选择对应最小整数的那个排列，为此还需将后面那部分数字的排列颠倒，如将数字6，4，3的排列顺序颠倒，得到排列1,2,5,3,4,6，这才是排列1，2，4，6，5，3的下一个排列。按照以上想法可以编写非递归程序实现n个数的全排列，对满足进出栈规则的排列则计数并输出。/*本程序输出1 2.n个序列进栈出栈的序列*/#include int pl(int n)int a100;/*最大处理范围为99个数*/int

24、flag=1,flag1=0;FILE*rf;int i,j,k,x,count=0;rf=fopen(stack.txt,w);/*pl.txt用于存放进出栈序列结果*/for(i=1;i=n;i+)/*初始序列*/ai=i;while(flag)/*还剩余未输出的排列*/flag1=1;/*判断本次排列是否符合进栈出栈序列 */for(i=1;i=n;i+)j=i+1;while(jai)j+;/*找ai后第一个比ai小的元素aj*/k=j+1;while(k=n)/*如果aj后还有比ai小且比aj大的元素,则此排列无效*/if(ak aj)flag1=0;k+;if(flag1)for(

25、i=1;i1&aij&aiaj)i-;12 k=aj;/*交换两元素的值*/aj=ai;ai=k;k=j+1;/*对交换后后面的数据由小到大排序*/for(i=k+1;i=k&xnext=NULL Bp=NULL Cp-next=head Dp=head（3）在带头结点的单链表中查找x应选择的程序体是（C）。Anode*p=head-next;while(p&p-info!=x)p=p-next;if(p-info=x)return p else return NULL;Bnode*p=head;while(p&p-info!=x)p=p-next;return p;Cnode*p=head-

26、next;while(p&p-info!=x)p=p-next;return p;Dnode*p=head;while(p-info!=x)p=p-next;return p;（4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。A必须是连续的 B部分地址必须是连续的 C一定是不连续的 D连续不连续都可以（5）在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（B）。AO(1)BO(n)CO(n2)DO(nlog2n)（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（D）。A仅修改队头指针 B

27、仅修改队尾指针 C队头、队尾指针都要修改 D队头,队尾指针都可能要修改（7）若从键盘输入n个元素，则建立一个有序单向链表的时间复杂度为（B）。AO(n)BO(n2)CO(n3)DO(nlog2n)（8）下面哪个术语与数据的存储结构无关（D）。A顺序表 B链表 C散列表 D队列（9）在一个单链表中，若删除p所指结点的后续结点，则执行（A）。Ap-next=p-next-next;Bp=p-next;p-next=p-next-next;Cp-next=p-next;Dp=p-next-next;（10）在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（B）。As-next

28、=p;p-next=s;Bs-next=p-next;p-next=s;Cs-next=p-next;p=s;Dp-next=s;s-next=p;3.2 设计一个算法，求一个单链表中的结点个数。【答】：单链表存储结构定义如下（相关文件：linklist.h）#include 14#include typedef struct node int data;struct node*next;linknode;typedef linknode*linklist;/*尾插法创建带头结点的单链表*/linklist creatlinklist()linklist head,r,s;int x;head

29、=r=(linklist)malloc(sizeof(linknode);printf(n请输入一组以0结束的整数序列：n);scanf(%d,&x);while(x)s=(linklist)malloc(sizeof(linknode);s-data=x;r-next=s;r=s;scanf(%d,&x);r-next=NULL;return head;/*输出带头结点的单链表*/void print(linklist head)linklist p;p=head-next;printf(List is:n);while(p)printf(%5d,p-data);p=p-next;print

30、f(n);基于上述结构定义，求单链表中的结点个数的算法程序如下：int count(linklist head)int c=0;linklist p=head;while(p)15 c+;p=p-next;return c;3.3设计一个算法，求一个带头结点单链表中的结点个数。【答】：带头结点的单链表的存储结构定义同题3.2，实现本题功能的算法程序如下（3_3.c）#include linklist.h int count(linklist head)int c=0;linklist p=head-next;while(p)c+;p=p-next;return c;main()/*测试函数*/

31、linklist head;head=creatlinklist();print(head);printf(nLength of head is:%d,count(head);getch();当输入5个数据时，产生的输出结果如下图所示：3.4设计一个算法，在一个单链表中值为y的结点前面插入一个值为x的结点。即使值为x的新结点成为值为y的结点的前驱结点。【答】：#include linklist.h void insert(linklist head,int y,int x)/*在值为y的结点前插入一个值为x的结点*/linklist pre,p,s;pre=head;16 p=head-nex

32、t;while(p&p-data!=y)pre=p;p=p-next;if(p)/*找到了值为y的结点*/s=(linklist)malloc(sizeof(linknode);s-data=x;s-next=p;pre-next=s;void main()/*测试程序*/linklist head;int y,x;head=creatlinklist();/*创建单链表*/print(head);/*输出单链表*/printf(n请输入y与x的值:n);scanf(%d%d,&y,&x);insert(head,y,x);print(head);程序的一种运行结果如下图所示：3.5设计一个算

33、法，判断一个单链表中各个结点值是否有序。【答】：#include linklist.h int issorted(linklist head,char c)/*当参数c=a时判断链表是否为升序，当参数c=d是判断链表是否为降序*/int flag=1;linklist p=head-next;switch(c)17 case a:/*判断带头结点的单链表head是否为升序*/while(p&p-next&flag)if(p-datanext-data)p=p-next;else flag=0;break;case d:/*判断带头结点的单链表head是否为降序*/while(p&p-next&

34、flag)if(p-data=p-next-data)p=p-next;else flag=0;break;return flag;int main()/*测试程序*/linklist head;head=creatlinklist();print(head);if(issorted(head,a)printf(单链表head是升序排列的！n);else if(issorted(head,d)printf(单链表head是降序排列的！n);else printf(单链表head是无序的！n);程序运行时的三种输出结果如下图所示：3.6设计一个算法，利用单链表原来的结点空间将一个单链表就地转置。

35、【答】：#include linklist.h void verge(linklist head)18/*本函数的功能是就地倒置带头结点的单链表*/linklist p,q;p=head-next;head-next=NULL;while(p)/*每次从原表取一个结点插入到新表的最前面*/q=p;p=p-next;q-next=head-next;head-next=q;int main()/*测试函数*/linklist head;head=creatlinklist();/*创建单链表*/print(head);/*输出原单链表*/verge(head);/*就地倒置单链表*/print(

36、head);/*输出倒置后的单链表*/3.7设计一个算法，将一个结点值自然数的单链表拆分为两个单链表，原表中保留值为偶数的结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表。【答】：#include linklist.h linklist sprit(linklist head)/*将带头结点的单链表head中的奇数值结点删除生成新的单链表并返回*/linklist L,pre,p,r;L=r=(linklist)malloc(sizeof(linknode);r-next=NULL;pre=head;p=head-next;while(p)if(p-data%2=1)/*删除奇

37、数值结点*/pre-next=p-next;r-next=p;r=p;p=pre-next;else /*保留偶数值结点*/pre=p;p=p-next;19 r-next=NULL;/*置链表结束标记*/return L;int main()/*测试函数*/linklist head,L;head=creatlinklist();/*创建单链表*/print(head);/*输出原单链表*/L=sprit(head);/*分裂单链表head*/printf(n原单链表为:n);print(head);/*输出倒置后的单链表*/printf(n分裂所得奇数单链表为:n);print(L);本程

38、序的一组测试情况如下图所示。3.8设计一个算法，对一个有序的单链表，删除所有值大于x而不大于y的结点。【答】：#include linklist.h void deletedata(linklist head,datatype x,datatype y)/*删除带头结点单链表中所有结点值大于x而不大于y的结点*/linklist pre=head,p,q;p=head-next;/*初始化*/while(p&p-datanext;while(p&p-datanext;q=pre-next;/*删除大于x而小于y的结点*/pre-next=p;20 pre=q-next;while(pre!=p

39、)/*释放被删除结点所占用的空间*/free(q);q=pre;pre=pre-next;void main()/*测试函数*/linklist head,L;datatype x,y;head=creatlinklist();/*创建单链表*/print(head);/*输出原单链表*/printf(n请输入要删除的数据区间:n);scanf(%d%d,&x,&y);deletedata(head,x,y);print(head);/*输出删除后的单链表*/3.9设计一个算法，在双链表中值为y的结点前面插入一个值为x的新结点。即使值为x的新结点成为值为y的结点的前驱结点。【答】：首先定义双链

40、表的数据结构，相关文件dlink.h，内容如下：typedef int datatype;/*预定义的数据类型*/typedef struct dlink_node /*双链表结点定义*/datatype data;struct dlink_node*llink,*rlink;dnode;typedef dnode*dlinklist;/*双链表结点指针类型定义*/*尾插法创建带头结点的双链表*/dlinklist creatdlinklist(void)dlinklist head,r,s;datatype x;head=r=(dlinklist)malloc(sizeof(dnode);/

41、*建立双链表的头结点*/head-llink=head-rlink=NULL;printf(n请输入双链表的内容：（整数序列，以0结束）n);scanf(%d,&x);while(x)/*输入结点值信息，以0结束*/s=(dlinklist)malloc(sizeof(dnode);s-data=x;21 s-rlink=r-rlink;/*将新结点s插入到双链表链尾*/s-llink=r;r-rlink=s;r=s;scanf(%d,&x);return head;/*输出双链表的内容*/void print(dlinklist head)dlinklist p;p=head-rlink;p

42、rintf(n双链表的内容是：n);while(p)printf(%5d,p-data);p=p-rlink;本题的求解程序如下：#include#include dlink.h void insertxaty(dlinklist head,datatype y,datatype x)dlinklist s,p;/*首先在双链表中找y所在的结点，然后在y前面插入新结点*/p=head-rlink;while(p&p-data!=y)p=p-rlink;if(!p)printf(n双链表中不存在值为y的结点,无法插入新结点!n);else /*插入值为x的新结点*/s=(dlinklist)ma

43、lloc(sizeof(dnode);s-data=x;s-rlink=p;s-llink=p-llink;p-llink-rlink=s;p-llink=s;void main()/*测试函数*/dlinklist head;22 datatype x,y;head=creatdlinklist();print(head);printf(n请输入要输入的位置结点值y:n);scanf(%d,&y);printf(n请输入要输入的结点值x:n);scanf(%d,&x);insertxaty(head,y,x);/*在值为y的结点前插入值为x的新结点*/print(head);/*输出新的双链

44、表*/getch();本程序的一组测试情况如下图所示。3.10设计一个算法，从右向左打印一个双链表中各个结点的值。【答】：本题的双链表定义同题3.9，实现从右向左打印双链表的各个结点的值可以用递归程序实现如下：#include#include dlink.h void vprint(dlinklist head)/*递归方法从右向左打印双链表的值*/if(head-rlink)vprint(head-rlink);printf(%5d,head-rlink-data);void main()/*测试函数*/dlinklist head;head=creatdlinklist();print(h

45、ead);23 printf(n从右向左打印的双链表的内容是:n);vprint(head);getch();本程序的一组测试情况如下图所示。3.11设计一个算法，将一个双链表改建成一个循环双链表。【答】：#include#include dlink.h/*将一个双链表改成循环双链表*/void dlinktocdlink(dlinklist head)dlinklist r;r=head;while(r-rlink)/*寻找尾结点*/r=r-rlink;head-llink=r;r-rlink=head;void printcdlink(dlinklist head)/*打印双链表*/dli

46、nklist p;p=head-rlink;while(p!=head)printf(%5d,p-data);p=p-rlink;int main()/*测试函数*/dlinklist head;head=creatdlinklist();dlinktocdlink(head);printf(n循环双链表的内容是：n);printcdlink(head);24 第4章 字符串、数组和特殊矩阵 4.1 稀疏矩阵常用的压缩存储方法有（三元组顺序存储）和（十字链表）两种。4.2 设有一个1010的对称矩阵A采用压缩方式进行存储，存储时以按行优先的顺序存储其下三角阵，假设其起始元素a00的地址为1，每

47、个数据元素占2个字节，则a65的地址为（53）。4.3 若串S=“software”，其子串的数目为（36）。4.4 常对数组进行的两种基本操作为（访问数据元素）和（修改数组元素）。4.5 要计算一个数组所占空间的大小，必须已知（数组各维数）和（每个元素占用的空间）。4.6 对于半带宽为b的带状矩阵，它的特点是：对于矩阵元素aij，若它满足（|i-j|b），则aij=0。4.7 字符串是一种特殊的线性表，其特殊性体现在（该线性表的元素类型为字符）。4.8 试编写一个函数，实现在顺序存储方式下字符串的strcompare（S1，S2）运算。【答】：#include#include#define

48、MAXSIZE 100 typedef struct char strMAXSIZE;int length;seqstring;/*函数strcompare()的功能是：当s1s2时返回1，当s1=s2时返回0，当s1s2时返回-1*/int strcompare(seqstring s1,seqstring s2)int i,m=0,len;len=s1.lengths2.length?s1.length:s2.length;for(i=0;is2.stri)m=1;break;else if(s1.stris2n);else if(m=-1)printf(s2s1n);else if(m=

49、0)printf(s1=s2n);4.9 试编写一个函数，实现在顺序存储方式下字符串的replace（S，T1，T2）运算。【参考程序1】：/*本程序用来在顺序存储下用快速匹配模式实现在字符串S中用T2替换所有T1出现的可能*/#include#include#include#define maxsize 100 typedef struct char strmaxsize;int length;seqstring;/求next函数 void getnext(seqstring*p,int next)int i,j;next0=-1;i=0;j=-1;while(ilength)if(j=-1

50、|p-stri=p-strj)+i;+j;nexti=j;else j=nextj;/快速模式匹配算法 int kmp(seqstring*t,seqstring*p,int next,int temppos)int i,j;26 i=temppos,j=0;while(ilength&jlength)if(j=-1|t-stri=p-strj)i+;j+;else j=nextj;if(j=p-length)return(i-p-length);else return(-1);/替换函数 void takeplace(seqstring*S,seqstring*T1,seqstring*T2