资源描述：
《数据结构的课后习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ML=P;(3)D(4)D(5)D(6)A7试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表（a1,a2,…,an）逆置为(an,an-1,…,a1)。【解答】（1）用一维数组作为存储结构voidinvert(SeqList*L,int*num){intj;ElemTypetmp;for(j=0;j<=(*num-1)/2;j++){tmp=L[j];L[j]=L[*num-j-1];L[*num-j-1]=tmp;}}（2）用单链表作为存储结构voidinvert(Li
2、nkListL){Node*p,*q,*r;if(L->next==NULL)return;/*链表为空*/p=L->next;q=p->next;p->next=NULL;/*摘下第一个结点，生成初始逆置表*/while(q!=NULL)/*从第二个结点起依次头插入当前逆置表*/{r=q->next;q->next=L->next;L->next=q;q=r;}}11将线性表A=(a1,a2,……am),B=(b1,b2,……bn)合并成线性表C,C=(a1,b1,……am,bm,bm+1,……
3、.bn)当m<=n时，或C=(a1,b1,……an,bn,an+1,……am)当m>n时,线性表A、B、C以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。【解答】算法如下：LinkListmerge(LinkListA,LinkListB,LinkListC){Node*pa,*qa,*pb,*qb,*p;pa=A->next;/*pa表示A的当前结点*/pb=B->next;p=A;/*利用p来指向新连接的表的表尾，初始值指向表A的头结点*/w
4、hile(pa!=NULL&&pb!=NULL)/*利用尾插法建立连接之后的链表*/{qa=pa->next;qb=qb->next;p->next=pa;/*交替选择表A和表B中的结点连接到新链表中；*/p=pa;p->next=pb;p=pb;pa=qa;pb=qb;}if(pa!=NULL)p->next=pa;/*A的长度大于B的长度*/if(pb!=NULL)p->next=pb;/*B的长度大于A的长度*/C=A;Return(C);}实习题约瑟夫环问题约瑟夫问题的一种描述为：编号1,
5、2,…,n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如m的初值为20；n=7，7个人的密码依次是：3,1,7,2,4,8,4,出列顺序为6,1,4,7,2,3,5。【解答】算法如
6、下：typedefstructNode{intpassword;intnum;structNode*next;}Node,*Linklist;voidJosephus(){LinklistL;Node*p,*r,*q;intm,n,C,j;L=(Node*)malloc(sizeof(Node));/*初始化单向循环链表*/if(L==NULL){printf("链表申请不到空间!");return;}L->next=NULL;r=L;printf("请输入数据n的值(n>0):");scan
7、f("%d",&n);for(j=1;j<=n;j++)/*建立链表*/{p=(Node*)malloc(sizeof(Node));if(p!=NULL){printf("请输入第%d个人的密码:",j);scanf("%d",&C);p->password=C;p->num=j;r->next=p;r=p;}}r->next=L->next;printf("请输入第一个报数上限值m(m>0):");scanf("%d",&m);printf("*************************
8、****************");printf("出列的顺序为:");q=L;p=L->next;while(n!=1)/*计算出列的顺序*/{j=1;while(jnext;j++;}printf("%d->",p->num);m=p->password;/*获得新密码*/n--;q->next=p->next;/*p出列*/r=p;p=p->next;free(r);}printf
