数据结构____用C语言描述__课后答案.pdf

《数据结构____用C语言描述__课后答案.pdf》由会员分享，可在线阅读，更多相关《数据结构____用C语言描述__课后答案.pdf（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 一 章 绪 论课堂习题1、试写一算法，自大到小依次输出顺序读入的三个整数X,Y和 Z 的值。【解答】一解：IFXvY XY;IF YZ YZ;IF XY XY;此算法最坏情况下比较3 次，移动（即赋值9 次）二解：IF XY TEMP=X;X=Y;Y=TEMP;IFYTEMPY=TEMPELSEY=X;X=TEMP;此算法最坏情况下比较3 次，移动7 次三解：IFXZ XYELSE XZ;ELSEIF XZ XZ;IFYZ Y-Z;此算法最坏情况下比较3 次，移动6 次2、抽象数据类型三元组的定义、表示和实现【解答】抽象数据类型三元组的定义已经给出（见教材12页），要求设计实现三元组基本操

2、作的演示程序。#include#include typedef int ElemType;typedef ElemType Triplet;typedef int Status;#define OK 1#define ERROR 0#define OVERFLOW-2Status InitTriplet（Triplet*T）ElemType vl,v2,v3;*T=(ElemType*)malloc(3*sizeof(ElemType);if(*T=0)return(OVERFLOW);scanf(M%d,%d,%dn,&vl,&v2,&v3);(*T)0=v 1;(*T)1 =v2;(*T)

3、2=v3;IStatus DestroyTriplet(Triplet*T)(free(*T);町=NULL;Status Get(Triplet T,int i,ElemType*e)(if(i3)return ERROR;*e=Ti-l;return OK;)Status Put(Triplet T,int i,ElemType e)(if(i3)return ERROR;(*T)i-l=e;return OK;)Status IsAscending(Triplet T)(retum(TlOT 1 )&(T 1 JTl)&(T1 T2);)Status Max(Triplet T,Elem

4、Type*e)(*e=(T0=Tl?(T0=T2)?T0:T):(T1=T2)?T1:T2);return OK;)Status Min(Triplet T,ElemType*e)(*e=(T0=Tl?(T0=T2)?T0:T2):(Tl=T2)?Tl:T2);return OK;void main()Triplet T;ElemType e;int select,i;printf(请输入三个数，建立一-个三元组：n)；if(InitTriplet(&T)=O VERFLOW)printf(存储空间分配失败,退出程序n“);else(do(printf(MI：取三元组第I 个元素n)；prin

5、tf(2：修改三元组第I 个元素n”)；printf(3：判断三元组元素是否递增n)；printfC4：判断三元组元素是否递减n)；printf(n5：取三元组最大元n);printf(n6：取三元组最小元n);printf(nO：结束n)；scanf(&d,&select);switch(select)(case 1:printf(nni=n);scanf(n%d,&i);if(Get(T,i,&e)=ERROR)printf(I 值输入不合法n)；else printf(第 I 个元素的值为dn”,e);break;case 2:printf(,ni=H);scanf(n%dH,&i);p

6、rintf(nne=);scanf(%d,&e);if(Put(T,i,e)=ERROR)p printf(I 值输入不合法n);else printf(”新三元组为：%4d%4d%4dnT0,Tl,T2);break;case 3:if(IsAscending(T)=1)printf(三元组递增有序 n”)；else printf(三元组非递增 n”)；break;case 4:if(IsDescending(T)=1)printf(三元组递减有序 n”);else printf(三元组非递减 n)；break;case 5:Max(T,&e);printf(三元组的最大元为%(111”,)

7、;break;case 6:Min(T,&e);printf(三元组的最小元为%dn,e);break;case 0:printf(操作结束n)；break;default:printf(选择出错,请输入数字(06)n)while(select!=0);DestroyTriplet(&T);课后练习一、问答题1.什么是数据结构？2.叙述四类基本数据结构的名称与含义。3.叙述算法的定义与特性。4.叙述算法的时间复杂度。5.叙述数据类型的概念。6.叙述线性结构与非线性结构的差别。7.叙述面向对象程序设计语言的特点。8.在面向对象程序设计中，类的作用是什么？9.叙述参数传递的主要方式及特点。1 0.

8、叙述抽象数据类型的概念。二、判断题(在各题后填写“J”或“X”)1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。()2.算法就是程序。()3.在高级语言(如C 或 PASCAL)中，指针类型是原子类型。()三、计算下列程序段中X=X+1的语句频度for(i=l;i=n;i+)for(j=l;jv=i;j+)for(k=1 ;k=j;k+)x=x+1;【解答】x=x+1的语句频度为：T(n)=1+(1+2)+(1+2+3)+(1+2+n)=n(n+1)(n+2)/6四、试编写算法，求 元 多 项 式 Pn(x)=ao+atx+a2x2+a3x3+.a”x的值Pn(x(),并自

9、定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求暴函数。注意：本题中的输入ai(i=0,I”.,n),x和 n,输出为Pn(x()。通常算法的输入和输出可采用F 列两种方式之一：(1)通过参数表中的参数显式传递。(2)通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出【解答】(1)通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。(2)通过全局变量隐式传递优点：减少实参与形参的个数，从而减少

10、内存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue()int i,n;float x,a,p;printf(,nn=);scanf(%f,&n);printf(unx=);scanf(B%f,&x);for(i=0;in;i+)scanf(f/*执行次数：n 次*/P=a0；for(i=1;i=n;i+)p=p+ai*x;/*执行次数：n 次*/x=x*x;printf(f”,p);)算法的时间复杂度：T(n)=O(n)通过参数表中的参数显式传递float PolyValue(float a,float x,int n)(floa

11、t p,s;inti;p=x;s=a0;for(i=1;iPRIOR；因此可直接将*P 删除掉，其时间复杂度为0(1);在单循环链表中，可 从 P 结点依次扫描到其前驱结点，故也能删除掉该结点，其时间复杂度为O(N)o2、下述算法的功能是什么？LINKLIST DEM0(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【解答】当 L 是空链表或仅有一个结点时，L 不变；当 L 有两个或两个以上结点时，将

12、第一个结点移至链表最后，关指针指向原第二个结点。3、试分别用顺序表和单链表作为存储结构，实现线性表的就地逆置。【解答】顺序表 VOID REVERSELIST(SQLIST*L)DATATYPE T;INT I,J;FOR(I=0;ILENGTH/2-1 ;I+)J=L-LENGTH-1-I;T=L-ELEMI;L-ELEMI=L-ELEMJ;L-ELEMJ=T;单链表 VOID REVERSELIST(LINKLIST*L)LNODE*P,*Q;P=L-NEXT;L-NEXT=NULL;WHILE(P)Q=P-NEXT;P-NEXT=L-NEXT;L-NEXT=P;P=Q；)4、设顺序表L

13、是一个递增有序表，试写一算法将X 插入到L 中，并使得L 仍是一个有序表。【解答】VOID INSERTSOR(SQLIST*L,DATATYPE X)INT I;IF(L-LENGTH=LISTSIZE)RETURN ERROR;I=L-LENGTH-1;WHILE(I=O&L-DATAIJX)L-ELEMI+1=L-ELEMI;I-;L-ELEMI+1J=X;L-LENGTH+;)5、已知L I和 L2分别指向两个单链表的头结点，且已知其长度分别为M 和 N,试写一算法将两个链表连接在一起，请分析算法的时间复杂度。【解答】LINKLIST CONNECT(LINKLIST LI,LINKL

14、IST L2,INT M,INT N)LISTNODE*P,*Q;INT K;IF(MN)K=N;P=L2;Q=L1;ELSEK=M;P=L2;Q=L2;WHILE(K0)P=P-NEXT;K-;P-NEXT=Q-NEXT;FREE(Q);IF(MN)RETURN L2;ELSE RETURN LI;6、写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值各不相同。【解答】VOID DELSAMENODE(LINKLIST L)LISTNODE*P,*Q,*R;P=L-NEXT;WHILE(P)Q=P；R=Q-NEXT;WHILE(R)IF R-DATA=P-DATAQ-NEXT=R-

15、NEXT;R=Q-NEXT;ELSEQ=R;R=R-NEXT;)P=P-NEXT;)7、假设在长度大于1 的单循环链表中，既无头结点也无头指针，S 为指向表中某个结点的指针，试编写算法删除结点*S 的直接前驱结点。【解答】VOID DELETEFNODE(LISTNODE*S)LISTNODE*P,*Q;P=S;WHILE(P-NEXT!=S)Q=P；P=P-NEXT;Q-NEXT=S;FREE(P);)8、狐狸逮兔子问题围绕着山顶有10个圆形排列的洞，狐狸要吃兔子逸子说:可以，但必须找到我，我就藏身于 这 10个洞中，你先到1 号洞找，第二次隔1 个洞，(即3 号洞)找，第三次就隔2 个洞(

16、即6 号洞找)，以后如此类推，次数不限.”但狐狸从早到晚进进出出了 1000次，仍没有找到兔子，问兔子究竟藏在哪个洞里？【解答】#include ustdio.h#include stdlib.h#define OK 1#define OVERFLOW-2#define LIST_INIT_SIZE 10typedef int status;typedef int elemtype;typedef struct elemtype*elem;int length;int listsize;sqlist;status initlist_sq(sqlist*1)(l-elem=(elemtype*)

17、malloc(LIST_INIT_SIZE*sizeof(elemtype);if(!(l-elem)return OVERFLOW;l-length=O;l-listsize=LIST_INIT_SIZE;return OK;)status rabbit(sqlist*1)(int i,current=O;for(i=0;ielemi=l;l-elem0=0;for(i=2;ielemcurrent=O;)printf(nthe hole are:);for(i=0;ielemi=l)printf(H%d M,i+1);return OK;)main()(sqlist 1;initlist_

18、sq(&l);rabbit(&l);getch();)9、约瑟夫问题设有N 个人围坐在圆桌周围，现从某个位置M(1=M=l;i-)(p=(cnode*)malloc(sizeof(cnode);if(p=null)return OVERFLOW;p-data=i;p-next=clist;clist=p;if(i=n)q=p;)q-next=clist;joseph=clist;return ok;)status joseph(cnode*clist,int m,int n,int k)(int i;cnode*p,*q;if(mn)return ERROR;if(!create_clist(

19、clist,n)return ERROR;p=joseph;for(i=l;inext;while(p)for(i=1 ;inext;q=p-next;printf(n%d n,q-data);if(p-next=p)p=null;else p-next=q-next;p=p-next;free(q);clist=null;main()(int m,n,k,i;cnode*clist;clist=null;printf(nplease input the number of people:);scanf(d”,&n);printf(nplease input the position star

20、t:1);scanf(n%dn,&m);printf(nnplease input the NO.out:);scanf(d”,&k);create_clist(clist,n);printf(MnTHE OUT LINE:n);joseph(clist,m,n,k);getch();课后练习一、术语理解描述以下三个概念的区别：头指针，头结点，首元素结点。二、填空题(1)在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 有关。(2)在顺序表中，逻辑上相邻的元素，其物理位置 相邻。在单链表中，逻辑上相邻的元素，其物理位置_ _ _ _ _ _ _ _ _ _ _ _ _ 相

21、邻。(3)在带头结点的非空单链表中，头结点的存储位置由 指示，首元素结点的存储位置由 指示，除首元素结点外，其它任一元素结点的存储位置由 指示。三、已知L是无表头结点的单链表，且 P 结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。a.在 P 结点后插入S 结点的语句序列是：ob.在 P 结点前插入S 结点的语句序列是：,c.在表首插入S 结点的语句序列是：d.在表尾插入S 结点的语句序列是：O供选择的语句有：(1)P-n e xt=S;(2)P-n e xt=P-n e xt-n e xt;(3)P-n e xt=S-n e xt;(4)S-n e xt=P-n

22、 e xt;(5)S-n e xt=L;(6)S-n e xt=N U L L;(7)Q=P;(8)wh i l e(P-n e xt!=Q)P=P-n e xt;(9)wh i l e(P-n e xt!=N U L L)P=P-n e xt;(1 0)P=Q;(1 1)P=L;(1 2)L=S;(1 3)L=P;四、设线性表存于a(l:a r r si ze)的前e l e n u m 个分量中且递增有序。试写一算法，将 X 插入到线性表的适当位置上，以保持线性表的有序性。五、写一算法，从顺序表中删除自第i 个元素开始的k个元素。六、已知线性表中的元素(整数)以值递增有序排列，并以单链表作

23、存储结构。试写一高效算法，删除表中所有大于m i n k 且小于m a xk 的元素(若表中存在这样的元素)，分析你的算法的时间复杂度(注意：m i n k 和 m a xk 是给定的两个参变量，它们的值为任意的整数)。七、试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表(a i,a2.,a)逆 置 为(a,a-i,.,a O o(1)以一维数组作存储结构，设线性表存于a(l :a r r si ze)的前e l e n u m 个分量中。(2)以单链表作存储结构。八、假设两个按元素值递增有序排列的线性表A和 B,均以单链表作为存储结构，请编写算法，将 A表和B表归并

24、成个按元素值递减有序排列的线性表C,并要求利用原表(即A表和B表的)结点空间存放表C。九、已知有单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其它字符)，试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。十、设线性表A=(a ,a 2,a m),B=(b,b2,.,bn),试写一个按下列规则合并A、B为线性表C的算法，使得：C=，b l,a m,b m,b m+1.,b n)当 m W n 时;或者 C=(ah b,.,an,bn,an+1,当 m n 时。线性表A、B、C均以单链表作为存

25、储结构，且 C表利用A表和B 表中的结点空间构成。注意：单链表的长度值m 和 n 均未显式存储。十一、将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。十二、建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的d a t a域存放一个二进制位。并在此链表上实现对二进制数加1 的运算。十三、设多项式P(x)采用课本中所述链接方法存储。写一算法，对给定的x 值，求 P(x)的值。十三、顺序表基本操作实现【解答】include“stdlib.h#define LISTJNIT_SIZE 100#de

26、fine LISTINCREMENT 10typedef structint*elem;int length;int listsize;sqlist;void initlist_sq(sqlist*1)(int i,j,e;l-elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int);if(!l-elem)printf(HCan not init list!nn);else(/*l-length=0;l-listsize=LIST_INIT_SIZE;printf(nInit list successful!nM);*/printf(nPlease input

27、the number of elements:1 1);scanf(%d,&i);l-length=i;l-listsize=LIST_INIT_SIZE;for(j=l;jelemj-l=e;)printf(nInit list successful!nM);)void listinsert_sq(sqlist*l,int i,int e)(int*newbase,*p,*q;if(il-length+1)printf(The position is invalid!n”)；elseif(l-length=l-listsize)newbase=(int*)realloc(l-elem,(l-

28、listsize4-LISTINCREMENT)*sizeof(int);if(!newbase)printf(HCan not realloc!nu);else(l-elem=newbase;l-length+=LISTINCREMENT;)q=&(l-elemi-1 );for(p=&(l-eleml-length-1 )；p=q;p-)*(p+l)=*p;*q=e;l-length+;void listdelete_sq(sqlist*l,int i,int*e)(int*p,*q;if(illlilength)printf(nThe position is invalidlXn1);e

29、lse(p=&(l-elemi-1 );*e=*p;q=l-elem+l-length-1;for(+p;plength;)void listprint_sq(sqlist*1)(int*p;int i;printf(The elements in the list:1);for(i=O;ilength;+i)printf(M%d,Lelemi);/*for(p=&(l-elemO);peleml-length-l);+p)printf(%d”产p);*/printfCAn);)void reverselist(sqlist*1)(int i,temp;for(i=l;ilength/2;i+

30、)temp=l-elemi-l;l-elemi-1 =l-eleml-length-i;l-eleml-length-i=temp;main()(sqlist 1;int choice=l,elem,position;initlist_sq(&l);listprintf_sq(&l)；while(choice!=0)(choice=l;printf(MPlease choice:insert 1,delete 2,reverse 3,exit 0n);scanf(M%du,&choice);switch(choice)(case l:printf(*Please input the posit

31、ion inserted:1);scanf(n%du,&position);printf(HPlease input the element:*);scanf(%d,&elem);listinsert_sq(&l,position,elem);listprint_sq(&l);break;)case 2:printf(Please input the position deleted:M);scanf(%du,&position);listdelete_sq(&l,position,&elem);listprint_sq(&l);break;)case 3:reverselist(&l);li

32、stprint_sq(&l);break;)case O:printf(ByeBye!nn);)getch();十四、单链表基本操作实现【解答】#include stdlib.h,#define null 0typedef struct Inodeint data;struct Inode*next;Inode,*linklist;void reverselist(linklist 1);void listprint_list(linklist 1);int listlength(linklist 1)int i;linklist p;p=l；i=0;while(p-next)p=p-next

33、;i+；)retum(i);void reverselist(linklist 1)(linklist p,q;if(l-next)p=l-next;l-next=null;while(p)q=q-next;p-next=l-next;l-next=p;p=q;)elseprintf(MNo element!n);)void initlist_link(linklist*1)(int i,j,e;linklist s,p;*l=(linklist)malloc(sizeof(lnode);(*l)-next=null;printf(HPlease input the number of ele

34、ments:);scanf(M%du,&i);for(j=l,p=*l;jdata=e;s-next=p-next;p-next=s;p=s;)printf(Init successful!nn);)void listinseit_link(linklist l,int i,int e)linklist p,s;intj；P=l；j=O；while(p&jnext;j+;if(!pllji-l)printf(HThe position is invalid!nH);elses=(linklist)malloc(sizeof(lnode);s-data=e;s-next=p-next;p-nex

35、t=s;void listdelete_link(linklist l,int i,int*e)(linklist p,q;intj;P=l；j=O；while(p-next&jnext;j+;if(!(p-next)llji-l)printf(nThe position is invalid!);elseq=p-next;p-next=p-next-next;*e=p-data;free(q);)void listprint_link(linklist 1)(linklist p;p=l-next;printf(The elements in the list:1);while(p)prin

36、tf(M%d n,p-data);p=p-next;printf(nn);)main()int choice,position,elem;linklist head;initlist_link(&head);listprinl_link(head);choice=l;while(choice!=0)printf(Please choice insert 1,delete 2,reverse 3,length 4,exit 0:);scanf(n%dn,&choice);switch(choice)case l:printf(nPlease input the position inserted

37、:);scanf(%d,&position);printf(nPlease input the element:n);scanf(%d”,&elem);listinsert_link(head,position,elem);listprint_link(head);break;)case 2:printf(nPlease input the postion deleted:);scanf(%d”,&position);listdeleteink(head,position,&elem);listprint_link(head);break;)case 3:reverselist(head);l

38、istprint_link(head);break;case 4:printf(The listlength is%dn,listlength(head);break;case 0:printf(ByeBye!n);break;)getch();第 三章栈和队列课堂习题1、现在A、B、C、D 四个元素相继进行入栈操作，下面不可能得到的入栈序列为：1)ABCD 2)BDAC 3)CBDA 4)DCBA【解答】2)说明:在此选项中第一个出栈的元素为B,说明元素A 必定在栈内，而第二个出栈的元素为D,则说明元素C 也必定在栈内，那 么 A 和 C 在栈内的位置必为C 在 A 之上，因此元素C 肯定比

39、元素A 选出栈.2、试写一个判别表达式开、闭括号是否配对出现的算法。【解答】STATUS EXAMPLE(SQSTACK*S,CHAR A)INT I;CHAR E;FOR(I=0;ITOP=S-BASEII*(S-TOP-1 )=T)RETURN 0;ELSE POP(S,&E);IF(AI=T)IF(S-TOP=S-BASEII*(S-TOP-1 )=(*)RETURN 0;ELSE POP(S,&E);)IF(S-TOP=S-B ASE)RETURN 1;ELSE RETURN 0;)MAIN()SQSTACKS;CHARA80;ELEMTYPE ELEM,E;IF(INITSTACK(

40、&S)=1)PRINTF(INIT SUCCESSFUL);PRINTF(HPLEASE INPUT THE STRING:,1);SCANF(H%S,A);IF(EXAMPLE(&S,A)PRINTF(HOK!N);ELSE PRINTF(ERROR!NH);GETCH();)3、试写一算法，识别依次读入的一个以 为结束符的字符序列是否是形如“序列&序列2”的字符序列，其中序列1和序列2 均不含字符&,且序列2 是序列1 的逆序。【解答】STATUS SYSERROINITSTACK(S);CH=GETCHAR();WHILE(CH!=&)IF CH=RETRUN ERROR;PUSH(S,

41、CH);CH=GETCHAR();CH=GETCHAR();WHILE(CH!=)IFCH=&,THEN RETURN(FALSE);IF(S-TOP=S-BASE)THEN RETURN(FALSE);IF(*(S-TOP-1)!=CH)THEN RETURN(FALSE);POP(S);CH=GETCHAR();)IF S-TOP!=S-BASE THEN RETURN(FALSE);ELSE RETURN(TRUE);)4、指出下列程序段的功能是什么？1)VOID DEMO1(SQSTACK*S)INT I,ARR64,N=0;WHILE(!STACKEMPTY(S)ARRN+1=POP

42、(S);FOR(I=0;IN;I+)PUSH(S,ARRI);【解答】将栈S 中的元素序列颠倒.2)VOID DEMO2(CIRQUEUE*Q)INTX;SQSTACKS;INITSTACK(&S);WHILE(!QUEUEEMPTY(Q)X=DEQUEUE(Q);PUSH(&S,X);WHILE(!STACKEMPTY(&S)X=POP(&S);ENQUEUE(Q,X);)【解答】将队列Q 中的元素序列颠倒.3)CIRQUEUEQ1,Q2;INT X,I,M=0;WHILE(!QUEUEEMPTY(&Q 1)X=DEQUEUE(&Q 1 );ENQUEUE(&Q2,X);M+;FOR(I=0

43、;IREAR=0;Q-QUELEN=0;判队空：INT QUEUEEMPTY(CIRQUEUE*Q)RETURN(Q-QUELEN=O);判队满：INT QUEUEFULL(CIRQUEUE*Q)RETURN(Q-QUELEN=QUEUESIZE);入队：VOID ENQUEUE(CIRQUEUE DATATYPE X)IF QUEUEFULL(Q)ERROR(QUEUE OVERFLOW);Q-QUELEN+;Q-REAR=(Q-REAR+1 )%QUEUESIZE;Q-DATA Q-REAR=X;)出队:DATATYPE DEQUEUE(CIRQUEUE*Q)DATATYPE TEMP;I

44、NT FRONT;IF(QUEUEEMPTY(Q)ERROR(HQUEUE UNDERFLOW1);ELSEFRONT=(Q-REAR+QUEUESIZE-Q-QUELEN+1)%QUEUESIZE;TEMP=Q-DATAfFONRT;Q-QUELEN-;RETURN(TEMP);7、试写出双向栈的判定条件以及相应的入栈和出栈算法。【解答】#DEFINE STACKSIZE 100TYPEDEF CHAR DATATYPETYPEDEF STRUCTDATATYPE DATA STACKSIZE;INTTOP1,TOP2;SQSTACK;初始化，置空栈：VOID INTISTACK(SQSTA

45、CK*S)S-TOP 1=-1;S-TOP=STACKSIZE;判栈满：INT STACKFULL(SQSTACK*S)RETURN(S-TOP2=S-TOP 1+1;进栈：VOID PUSH(SQSTACK*S,DATATYPE X,INT I)IF(STACKFULL(S)ERROR,STACK OVERFLOW);ELSEIF(I=0)S-DATA+S-TOP1=X;ELSE S-DATA-S-TOP2=X;)退栈：DATATYPE POP(SQSTACK*S,INT I)IF(I=O)IF(S-TOP1=0)RETURN S-DATAS-TOP1-;ELSE ERROR(STACK1

46、UNDERFLOW*);ELSEIF(S-TOP2DATAS-TOP2+;ELSE ERROR(STACK2 UNDERFLOW);)8、假设以带头结点的循环链表表示队列，并且只设个指针指向队尾元素结点(注意不设头指针)，试写出相应的置空队、判队空以及入队出队的算法。【解答】TYPEDEF CHAR DATATYPE;TYPEDEF STRUCT QUEUENODEDATATYPE DATA;STRUCT QUEUENODE*NEXT;QUEUENODE;TYPEDEFSTRUCTQUEUENODE*FRONT,*REAR;LINKQUEUE;置空队：VOID INITQUEUE(LINKQU

47、EUE*Q)QUEUENODE*P=(QUEUNODE*)MALLOC(SIZEOF(QUEUENODE);P-NEXT=P;Q-NEXT=P;)判队空：INT QUEUEEMPTY(LINKQUEUE*Q)RETURN Q-REAR=Q-REAR-NEXT;入队：VOID ENQUEUE(LINKQUEUE DATATYPE X)QUEUENODE*P=(QUEUENODE*)MALLOC(SIZEOF(QUEUENODE);P-DATA=X;P-NEXT=Q-REAR-NEXT;Q-REAR-NEXT=P;Q-REAR=P;出队：DATATYPE DEQUEUE(LINKQUEUE*Q)D

48、ATATYPE X;QUEUENODE*P;IF(QUEUEEMPATY(Q)ERRORCQUEUE UNDERFLOW);ELSEP=Q-REAR-NEXT-NEXT;X=P-NEXT;Q-REAR-NEXT-NEXT=P-NEXT;IF(P=Q-REAR)Q-REAR=Q-REAR-NEXT;FREE(P);RETURN X;)9、母牛问题:有一头母牛从第4 年起开始每年生一头小母牛，每头小母牛也从第4 年起每年生 头小母牛，依此类推，问 N 年后共有多少头母牛?【解答】年 份 12345头 数 11123归纳出数学模型1F(N)=F(N-l)+F(N-3)出小母牛的母牛头数.6 7 8

49、9 10469 13 19(N3)其中F(N-1)为上年母牛头数F(N-3)第N 年能生养INT F(INT N)IF(N=3)RETURN(l);ELSERETURN(F(N-1 )+F(N-3);课后练习一、按图3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度，回答：如进站的车厢序列为1 2 3,则可能得到的出站车厢序列是什么？如进站的车厢序列为123456,能否得到435612和 135426的出站序列,并说明原因。(即写出以“S”表示进栈、以“X”表示出栈的栈操作序列)。【解答】(1)可能得到的出站车厢序列是：123、是2、213、231、321.(2)不能得到435612的

50、出站序列。因为有 S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6),此时按照“后进先出”的原则,出栈的顺序必须为X(2)X(1).能得到135426的出站序列。因为有 S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。二、设队列中有A、B、C、D、E 这 5 个元素，其中队首元素为A。如果对这个队列重复执行下列4 步操作：(I)输出队首元素；(2)把队首元素值插入到队尾；(3)删除队首元素；(4)再次删除队首元素。直到队列成为空队列为止，得到输出序列：(1)A、C、E、C、C(2)A,C、E(3)A、C、E、C、C、C(4