数据结构课习题参考答案

1、目录一、1.1比较2个线性链表的c函数 31.2写一个倒置顺序存贮的线性表的c函数31.3 写一个在线性表中，使线性表中没有值相同的结点的函数。41.4 编写一个求解给定多项式的值的c函数。51.5 实现多项式乘法61.7 车厢出站问题91.8编写对任一栈作进栈和出栈运算的c函数101.10 写出表达式等价的后缀表达式。121.11编写一个统计给定的线性链表的结点个数的c函数。151.12编写一个将给定的线性链表逆转的c函数。161.13编写一个插入值的c函数。181.14编写一个删除链表中结点的前趋结点的c函数。191.15试编写一个将两个链表归并成一个线性链表的c函数。201.17 用环形

2、链表解1。6题23118 将给定的线性链表改成环形链表241 19将给定的线性链表改成一个带表头的环形链表25120 编写用hash函数h（xi）xi，对x1，x2x800进行hash存储的程序261 21求广义表的深度。2721试编写一个在两个顺序字符串中寻找最大公共子串的c函数。292 2试编写一个实现strins（s1，i，s2）的c函数。3123 按照2.2题的要求，编一个实现strdel（s，i，j）的c函数。3231编写一个二分插入排序的c程序3332编写一个对给定链表进行插入排序的c程序。3435采用顺序存储实现，即用数组存放排序过程中以排好序的链表的头指针。363 6采用顺序存

3、储的结构即数组实现。3837编写一个实现快速排序的非递归的c函数。3938对于分别写出用下列排序方法对线性表进行排序的结果。4043将n阶三对角阵（即半带宽为1的带状矩阵）a按行序列序存放在一维数组b3*n-2中。若aij(|i-j|bs?as:bs; int i; for(i=0;ibi) return 1; if(aibs) return 1; if(bsas) return -1; return 0;4.测试用例：1 a3=1,2,3 b3=1,2,3 output : 0;2 a3=1.2.3 b3=1,1,3 output: 1;3 a3=1,2,3 b3=1,2,4 output:

4、 -14 a3=1,2,3 b4=1,2,3,0 output: -1;5 a4=1,2,3,0 b3=1,2,3 output: 1;6 a4=1,2,3,0 b3=1,3,2 output:-1;1.2 写一个倒置顺序存贮的线性表的c函数。要求用最少的附加存贮空间来完成。 分析：假设用数组a存贮一组int类型的数据，每次将a0取出，其余数依次前移，然后将a0放到 尚未倒置的数据元素的最后，直至整个数组完成倒置。 算法：（1）取t=a0，余下的a1，a2，.an-1依次前移一个位置； （2）an-1=t； （3）对由a0，a1.an-2组成的数组重复上述步骤。 程序： # include #

5、 define n 10 void reverse(a,n) int a; int n; int t,i,j=0; while(jn-1) t=a0; for(i=0;in-j-1;i+) ai=ai+1; ai=t; j+; void main( ) int an; int i; printf(input the array:n); for(i=0;in;i+) scanf(%d, &ai); reverse(a,n); printf(the reversed array:n); for(i=0;in;i+); printf(%d ,ai); printf(n); sample: input

6、 the array: 0 1 2 3 4 5 6 7 8 9 the reversed array:9 8 7 6 5 4 3 2 1 01.3 在具有n个结点的顺序存贮的线性表中，对值相同的结点只保留一个，把多余的结点删除掉，使线性表中没有值相同的结点。试编写一个实现上述操作的c函数，并分析该程序的执行时间。解答：首先应对线性表中每一个结点进行搜索，找到和他值相同的结点就把其删除，同时改变原结点的个数。主要运用两层循环：最外层对线性表中的第0到第n-2个元素进行扫描，第二层是对于第一层的每一个元素从其后面一个元素开始扫描，检查是否有和该元素值相同的元素若有则删除该元素，若无则循环关键值+1

7、进行下一个元素比较，直到线性表最后一个元素，然后在回到上层循环。如此继续，直到跳出所有循环时，所得线性表即为题目要求的线性表。 下面给出实现的函数。sq_delete()为删除一个结点的函数，i表示所要删除的结点的下标，del()为删除线性表中所有相同结点的函数。其中list为进行操作的线性表，*p_m和*p_n在两个函数中都表示线性表中结点个数。 #include#define m 100int sq_delete(int list,int *p_m,int i) int j; if(i=*p_m) return(1); for(j=i+1;j*p_m;j+) listj-1=listj;

8、(*p_m)-; return (0);void del(int list,int *p_n) int i,j; for(i=0;i(*p_n)-1);i+) for(j=i+1;j(*p_n);j+) if(listi=listj)sq_delete(list,p_n,j);j-;main() int listm,i,n; printf(input the number of the data:n); scanf(%d,&n); for(i=0;in;i+) printf(input data %d:n,i+1); scanf(%d,&listi); del(list,&n); for(i=

9、0;in;i+) printf(%d ,listi);对于以上程序提供一组测试数据：input the number of the data:5输入一组数据为：13 23 33 13 23执行完毕后得到的输出结果为：13 23 33对于该程序的时间复杂性分析：主要是del 和sq_delete两个函数中的循环语句的执行时间。一种极端情况是线性表中的数据没有一个重复，则只执行del中的循环体，(n-1)+(n-2)+1=o(n*n);另一种极端情况是线性表中只有一个元素，其他都与它重复，此时del的内和外循环都只执行一次，主要的执行时间用在了sq_delete上，可以知道他的复杂性也是o(n*n

10、).故总的来说该程序的时间复杂性是o(n*n)。 1.4 编写一个求解给定多项式在x=xo(xo为指定的某个值)时的值的c函数。存储法：定义结构数组 struct node int exp; float coef; ; typedef struct node term #define max 100 node amax;算法步骤：1 令sum=0, i=02 算出第i项的值，并与sum相加。3 若in, 则转2，否则return(sum)程序： float cal ( float x, term a , int n ) float sum; int i, j, k; for ( i=0; in

11、; i+ ) for ( k=1, j=1; j= ai . exp; j+) k=k*x; sum+= ai .coef*k; return(sum); 测试用例： 令x=2; 多项式为 3x6+8x4+5x2+9 结果为 349。 1.5实现多项式乘法一：存储结构：多项式以线性链表存储，以增加其插入删除的效率。结果多项式与所给多项式采取相同的存储结构，以方便实现多项式的连乘。二：分析 多项式的加法书上有源程序，而乘法与加法相似，只是由于乘法的规则与加法不同，因此我用了一个双重循环来实现（详见源程序），得到一个结果项之后，查找结果链表，若已有，则看是否相加之后为0，若为0，则将该项删去，否则

12、，就直接改系数，若没有，则直接链上。 原本想用数组加链表的索引法来实现，但据分析后，认为并不能显著提高效率，显得得不偿失，因此，我就使用了最原始的方法，请老师同学多多指教。三：输入/输出输入：先输入a、b多项式（根据提示）输出：a、b、c（ab）四：源程序#includestruct node int exp; int data; struct node *next; ;typedef struct node node;int search(int exp,node *c,node *pc,node *qc)*pc=null;*qc=c;if(c=null) return(0);while(*

13、qc)-expexp) *pc=*qc;*qc=(*qc)-next;if(*qc)-exp=exp) return(1);return(0);node *multi(node *a,node *b) node *pa,*pb,*pc,*qc,*p,*c=null; int exp,data,flag; for(pa=a;pa!=null;pa=pa-next) for(pb=b;pb!=null;pb=pb-next) exp=pa-exp+pb-exp;data=pa-data*pb-data; if(data) flag=search(exp,c,&pc,&qc); if(flag) i

14、f(!(data+qc-data) pc-next=qc-next;free(qc); else (qc-data)+=data; else p=(node *)malloc(sizeof(node); p-data=data;p-exp=exp; if(!pc) c=p; else pc-next=p; p-next=qc; return(c);node* creat()node *root,*p,*q; char ch;int i;printf(do you want to creat a null one(y/n)?n);scanf(%c,&ch);getchar();if(ch=y|c

15、h=y) return(null);p=null;ch=y;for(i=0;ch=y|ch=y;i+)q=(node*)malloc(sizeof(node);if(p=null) root=q; else p-next=q;printf(nplease input the data of node %d:n,i);scanf(%d,&(q-data);getchar();printf(please input the exp of node %d:n,i);scanf(%d,&(q-exp);getchar();printf(do you want to continue(y/n)?n);s

16、canf(%c,&ch);getchar();p=q;p-next=null;return(root);void print(node *root)int i=0;if(!root) printf(n0);while(i+,root!=null)printf(nnode %d:tdata:%dtexp:%d,i,root-data,root-exp);root=root-next;main()char ch;node *a,*b,*c;clrscr();printf(now please input a:n);a=creat();printf(now please input b:n);b=c

17、reat();printf(na:n);print(a);printf(nb:n);print(b);c=multi(a,b);printf(nnnc:n);print(c);五：测试数据：输入：a：5x6+3x4+2xb：7x3+3x2+5输出：c：35x9+15x8+21x7+34x6+29x4+6x3+10x输入：a：0b：5x3+2x2输出：0输入：a：3x2+5x1b：3x15c：01.7假设右边轨道排列有编号为1，2，3,n的n节车厢，它们依次被拖进站，从左边轨道依次出站的号的排列顺序有a n 种情况 。那么a n是用下列方法所形成的所有可能排列顺序的总数：某时刻站中只剩下编号为k

18、+1的车厢，而此时左边轨道是已出站的编号为1，2，3，,k的车厢，则排列顺序有ak种；右边轨道是尚未进站的编号为k+1，k+2,k+n的n-k-1节车厢，则可能有的排列顺序有an-k-1种。因此 给出了前k节车厢已出站的情况下所有的排列顺序，我们应该取遍k（0kn）的所有可能值，获得akan-k-1这样形式的所有项，然后把它们相加起来，可得到如下的关系式： a0=1； a1=1； an=a0an-1+a1an-2+.+an-1a0 ( n1) an=akan-k-1 (0kn-1) 为了求解排列顺序的数目，先求解这个递推关系：令 g（x）=a0+a1x+anx? n1即g（x）=akxk (k

19、0)让g（x）自乘得 g2(x)=g(x)g(x) =(a0+a1x+a2x2+.)(a0+a1x+a2x2+.) =a0a0+(a0a1+a1a0)x+(a0a2+a1a1+a2a0)x2+. =(akan-k)x? (0n,0kn)由上式可知，g2(x)的xn项的系数正好是an1。因此有g2(x)=an+1x? (n0)如果我们用x乘g2(x)，则有 xg2(x)=a1x+a2x2.两边都加上a0，又因为a0=1，故有 1+x g2(x)=akxk (k0) 1+xg2(x)=g(x)求解得g（x）=1(1-4x)/2x因为a0=1，所以g（x）=1-(1-4x)/2x再根据二项式定理，将

20、(1-4x)1/2展开，得 g(x)=1/2x1-(1n/2)(-4x)n (n0)令n=m+1,则有 g(x)= ( 1/2m+1)(-1)m 22m+1xm (m0) 比较可知an是上式中x?项的系数。所以 an=(1n+1/2)(-1)n22n+1化简得an=1/(n+1)(2nn)n节车厢出站有1/(n+1)(2nn)种排列顺序。所以，当 n=3时，有5种排列顺序，分别为，；当n=4时，有14种排列顺序。存储结构可采用栈实现。1_8.假设2个栈共享一个数组stackn，编写对任一栈作进栈和出栈运算的c函数，push(x,i) 和pop(i),i=1,2。这里i=1表示左边的栈，2则表示

21、右边的栈。要求整个数组元素都被占用时才产生溢出。存储结构：用一个数组存放2个栈。如图：(m为数组元素个数)32 tail1=0 head1 head2 tail2=m-1head1,head2分别为栈1，栈2中下个元素入栈的位置，tail1，tail2为两个栈底。分析与算法步骤：因为tail10,tail2m1，一般情况下不会变动，所以省去这2个量。初始值：head10，head2m-1；1执行入栈时：（1） 若head1-1+1head2+1，即head1head2+1时，整个数组满，溢出。（2） 若对栈1入栈，把元素存入stackhead1，head1+；（3） 若对栈2入栈，把元素存入s

22、tackhead2，head2；2执行出栈时：（1）对栈1：若head10，栈空，出栈失败；否则head1； （2）对栈2：若head2m1，栈2空，出栈失败；否则head2+；tc程序：include#define m 10int head1=0,head2=m-1;int stackm;void push(int x,int i)if(head1=head2+1) printf(the stack is full.fail to push.n); return; if(i=1) stackhead1+=x; else stackhead2-=x;void pop(int i)if(i=1)

23、 if(head1=0) printf(the stack is empty.fail to pop.n); return; *p=stack-head1; else if(head2=m1) printf(the stack is empty.fail to pop.); return; *p=stack+head2; main()int x,i,no=1; for(i=0;i=0;i-) printf(%d,stacki); printf(n); for(i=head2+1;i=a&c=a&c=z) return(1); else return(0);int mid_to_pos(char

24、 midexpress,char posexpress)char stackmaxn,c; int top,i,j; stack0=$; top=0; j=0; i=0; c=midexpress0; while(c!=0) if(ischar(c)posexpressj+=c; elseswitch(c) case +: case -: case *: case /: case : while(icp(c)0) posexpressj+=stacktop-; posexpressj=0; return(0);测试报告： void main()char midexpressmaxn,posex

25、pressmaxn,c; int i,result; i=0; printf(ninput the mid_expresstion:(end with !)n); scanf(%c,&c); while(c!=!) midexpressi+=c; scanf(%c,&c); midexpressi=0; result=mid_to_pos(midexpress,posexpress); if(result=1) printf(convertion fails!n); else printf(the pos_expresstion is:n); printf(%s,posexpress); 输入

26、：(a+b*c)d(e*f/g)-h*i!(输入以!结尾) 输出：abc*+def*g/hi*-输入：a+b*c/d+efg+h!输出：abc*d/+efg+h+输入：(a+b)*(c/d)+(ef)(g+h)!输出：ab+cd/*efgh+111 编写一个统计给定的线性链表的结点个数的c函数。存储结构：连表的结点采用：struct nodeint data;/关键字的类型自定 struct node *link;算发分析：利用链表的性质（结点中的指针指向下一个结点），逐步向表尾移动，以此计算出结点数。下面给出程序：typedef struct nodeint data; struct nod

27、e *link; node;int count(node *head)node *p;int c=0;p=head;while(p!=null)p=p-link; c+;return(c);测试报告：void main()node a10; int i=0; for(;i9;i+) ai.data=i; ai.link=&ai+1; ai.data=i; ai.link=null; printf(the total amount of the linked node is:%dn,count(&a0);输入：|0-1-2-3-4-5-6-7-8-9输出：the total amount of

28、the linked node is:10112 编写一个将给定的线性链表逆转的c函数，只允许改变结点的指针值，不允许移动结点值。算法如下：(1) 置p为链表首址，r,q为空；(2) 若p为空返回null；算法结束，转（5），否则转（3）；(3) 若链表只有一个结点，转（5），否则转（4）；(4) r=p,plink,r-linklink为空，转（5），否则转（4）；(5) p-link=r,返回p,算法结束。源程序如下：#include typedef struct node int data; struct node* link; node; node* tranfer(head) nod

29、e *head; node *p,*q,*r; p=head; r=q=null; if(head=null) return(null); if(p-link!=null) do r=p; p=p-link;r-link=q;q=r;while(p-link!=null); p-link=r; return(p); node* create(n)/*建立初始链表*/ int n; int i; node *head,*p,*q; if(n=0) return(null); head=(node*)malloc(sizeof(node); p=head; for(i=1;idata); q=(n

30、ode*)malloc(sizeof(node); p-link=q; p=q; scanf(%d,&(p-data); p-link=null; return(head); main() node *head,*r,*p; int n=5; printf(enter the data:n); head=create(n); p=head; while(p!=null) printf(%d ,p-data); p=p-link; printf(n); head=tranfer(head); p=head; printf(now the list is:n); while(p!=null) pr

31、intf(%d ,p-data); p=p-link; printf(n); 输入：1 2 3 4 5输出：5 4 3 2 11.13对于给定的线性链表,编写一个把值为a的结点插在值为b的结点的前面的c函数。若值为b的结点不在线性链表中，则把a插在表的最后。存储结构 利用线形表的链接存储：typedef struct nodechar data; struct node *link;node; 定义指针node *head,*p,*q,*t; 解题思路 指针*head指向链表的根结点，指针p指向值为b的结点，指针t指向它的前趋结点，指针q指向插入结点a。 (1) 如果头结点*head为空，或*

32、head的结点值为b，修改头指针，结束算法；(2) 查找值为b的结点，若找到，把值为a的结点插到b的前面；(3) 若找不到，把a结点插在链表最后；结束算法。 程序 #include typedef struct nodechar data; struct node *link;node; void insert(node *head,char a) node *p,*q,*t; q=(node*)malloc(sizeof(node); q-data=a; if(*head=null|(*head)-data=b) q-link=*head; *head=q; return; for(p=*head;p-data!=b&p!=null;p=p-link) t=p; q-link=p; t-link=q; 测试用例1 原链表：b,c,d,e,g,h插入a结点后：a,b,c,d,e,f,g,h测试用例2 原链表：c,d,e,f,g,h 插入a结点后:c,d,e,f,g,h,a测试用例3 原链表：c,d,e,b,f,g,h插入a结点后:c,d,e,a,b,f,g,h1-14 对于