资源描述：
《数据结构的课后习题答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ML=P;(3)D⑷D(5)D⑹A7试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空I'ld将线性表(al,a2,…,an)逆置为(an,an-l,…,al)0【解答】(1)用一维数组作为存储结构voidinvert(SeqList*L,int*num){intj;ElemTypetmp;for(j=0;j<=(*num-l)/2;j++){tmp=L[j];L[j]=L[*num-j-l];L[*num-j-l]=tmp;}}(2)用单链表作为存储结构voidinvert(UnkListL){Node*pz*q,*r;if(L->next==NULL)return;/*链表为
2、空*/p=L->next;q=p->next;p->next=NULL;/*摘下第一个结点，生成初始逆置表*/while(q!=NULL)/*从第二个结点起依次义插入当前逆置表*7{r=q->next;q->next=L->next;L->next=q;q=r;}}11将线性表A=(al,a2,am),B=(bl,b2,bn>合并成线性表C,C=(al,bl,am,bm,bm+l,.bn)当m<=n吋，或C=(al,bl,an,bn,an+l,arrQ当m>n吋,线性表A、B、C以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的L<:度值m和n均未显式存储。【解答】算法
3、如下：LinkListmerge(LinkListA,LinkListB,LinkListC){Node*pa,*qa,*pb,*qbz*p;pa=A->next;/*pa表示A的当前结点*/pb=B->next;P=A;/*利用p來指向新连接的表的表初始值指向表A的头结点*/while(pa!=NULLML=P;(3)D⑷D(5)D⑹A7试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空I'ld将线性表(al,a2,…,an)逆置为(an,an-l,…,al)0【解答】(1)用一维数组作为存储结构voidinvert(SeqList*L,int*num){intj;ElemTy
4、petmp;for(j=0;j<=(*num-l)/2;j++){tmp=L[j];L[j]=L[*num-j-l];L[*num-j-l]=tmp;}}(2)用单链表作为存储结构voidinvert(UnkListL){Node*pz*q,*r;if(L->next==NULL)return;/*链表为空*/p=L->next;q=p->next;p->next=NULL;/*摘下第一个结点，生成初始逆置表*/while(q!=NULL)/*从第二个结点起依次义插入当前逆置表*7{r=q->next;q->next=L->next;L->next=q;q=r;}}11将线性表A=(al,a2
5、,am),B=(bl,b2,bn>合并成线性表C,C=(al,bl,am,bm,bm+l,.bn)当m<=n吋，或C=(al,bl,an,bn,an+l,arrQ当m>n吋,线性表A、B、C以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的L<:度值m和n均未显式存储。【解答】算法如下：LinkListmerge(LinkListA,LinkListB,LinkListC){Node*pa,*qa,*pb,*qbz*p;pa=A->next;/*pa表示A的当前结点*/pb=B->next;P=A;/*利用p來指向新连接的表的表初始值指向表A的头结点*/while(pa
6、!=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的长度Vif(pb!=NULL)p->next=pb;/*B的长度人于A的长度*/C=A;Return(C);}实习题约瑟夫环问题约瑟夫fnj题的一种描述为：编号1,2,…,n的n个人按顺时针方句围坐一陶，每个人持有一个密码(正整数)。一开始任选一个报数上限值m,从第一个人歼
7、始顺时针向1丌始顺序报数,报到m吋停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利川单14循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如m的初值为20;n=7,7个人的密码依次是:3,1，7,2,4,8人出列顺序为6,1,4/7,23,5。【解答】算法如下：type
