数据结构实用教程(第三版)课后答案

⑻ 根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。如假定两个有序单链

表中的元素为(2,8,10,20)和(3,8,9,15,16)，则生成的新单链表中的元素为(2,3,8,8,9,10,15, 16,20)。

解：LNode*Merge2(LNode*p1,LNode*p2)

//根据两个有序单链表生成一个新的有序单链表 {

LNode a; //用a作为新的有序单链表的表头附加结点 LNode*p=&a; //p p->next=NULL; // while((p1!=NULL&&(p2!=NULL)) { // LNode*newptr=new LNode; if(p1->datadata)

{ // newptr->data=p1->data; p1=p1->next; } else

{ // newptr->data=p2->data; p2=p2->next; }

// p->next=newptr; p=newptr; }

while(p1!=NULL)

{ // LNode*newptr=new LNode; newptr->data=p1->data; p1=p1->next; p->next=newptr; p=newptr; }

while(p2!=NULL)

{ // LNode*newptr=new LNode; newptr->data=p2->data; p2=p2->next; p->next=newptr; p=newptr; }

. . 指向结果有序单链表的表尾结点 初始指向表头附加结点 处理两个表非空时的情况 由p1->data建立新结点，然后p1指针后移 由p2->data建立新结点，然后p2指针后移 将newptr结点插入到结果的有序表的表尾 继续处理p1单链表中剩余的结点 继续处理p2单链表中剩余的结点 .

p->next=NULL;

file:///D|/-------------------上架商品-----... (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 10／21 页）[2010-3-16 22:06:59]

file:///D|/-------------------上架商品---------------/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt return a.next; }

⑼ 根据一个元素类型为整型的单链表生成两个单链表，使得第一个单链表中包含原单链表中所有

元素值为奇数的结点，使得第二个单链表中包含原单链表中所有元素值为偶数的结点。原有单链表 保持不变。

解：void Separate(LNode*HL,LNode*&p1,LNode*&p2)

//根据一个单链表HL按条件拆分生成两个单链表p1和p2 {

LNode a,b; //a和b结点分别作为p1和p2单链表的表头附加结点 LNode*t1=&a,*t2=&b; //t1和t2分别作为指向p1和p2单链表的 //表尾结点，初始指向表头附加结点 Lnode*p=HL; while(p!=NULL)

{ //每循环一次产生一个新结点，并把它加入到p1或p2单链表 //的未尾

LNode*newptr=new LNode; if(p->data%2==1){ newptr->data=p->data; t1->next=newptr; t1=newptr; } else{

newptr->data=p->data; t2->next=newptr; t2=newptr; }

p=p->next; }

t1->next=t2->next=NULL;

p1=a.next;p2=b.next; //把指向两个单链表的表头结点的指针分别赋给 //p1和p2返回 }

6.编写一个算法，使用表头附加结点的循环单链表解决约瑟夫(Josephus)问题。其问题是 ：设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人出列(即离开坐位，

. . .

不参加以后的报数)，接着从出列的下一个人开始重新从1报数，数到m的人又出列，如此下

去直到所有人都出列为止，试求出它们的出列次序。

假如，当n=8、m=4时，若从第一个人(假定每个人的编号依次为1,2...,n)开始报数，则得 到的出列次序为:4,8,5,2,1,3,7,6。

此算法要求以n、m和s(假定从第s个人开始第一次报数)作为值参。 解：

void Josephus(int n,int m,int s)

//使用带表头附加结点的循环单链表解决约瑟夫问题

file:///D|/-------------------上架商品-----... (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 11／21 页）[2010-3-16 22:06:59]

file:///D|/-------------------上架商品---------------/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt {

//生成表头附加结点，此时循环单链表为空 LNode*HL=new LNode; HL->next=HL; int i;

//生成含有n个结点、结点依次为1,2,...n的带表头结点的循环单链表 for(i=n;i>=1;i--){ //生成新的结点

LNode*newptr=new LNode; newptr->data=i;

//把新的结点插入到表头 newptr->next=HL->next; HL->next=newptr; }

//从表头开始顺序查找出第s个结点，对应第一个开始报数的人 LNode*ap=HL,*cp=HL->next; for(i=1;i

//ap和cp指针后移一个位置 ap=cp;

cp=cp->next;

//若cp指向了表头附加结点，则仍需后移ap和cp指针，使之指向表头结点 if(cp==HL){ap=HL;cp=HL->next;} }

//依次使n-1个人出列 for(i=1;i

//顺序查找出待出列的人，即为循环结束后cp所指向的结点 for(int j=1;j

cp=cp->next;

if(cp==HL){ap=HL;cp=HL->next;}

. . .

}

//输出cp结点的值，即出列的人 cout<data<<\ //从单链表中删除cp结点 ap->next=cp->next; delete cp;

//使cp指向被删除结点的后继结点 cp=ap->next;

//若cp指向了表头附加结点，则后移ap和cp指针 if(cp==HL){ap=HL;cp=HL->next;} }

//使最后一个人出列

cout<next->data<

file:///D|/-------------------上架商品-----... (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 12／21 页）[2010-3-16 22:06:59]

file:///D|/-------------------上架商品---------------/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt delete HL->next; delete HL; }

7.对于在线性表抽象数据类型中定义的每一个操作，写出结点类型为LNode的带头附加结点 的循环单链表上实现的对应算法。 ⑴初始化单链表

解：void InitList(LNode*HL) {

HL->next=HL;//将单链表置空 }

⑵删除单链表中的所有结点，使之成为一个空表 void ClearList(LNode*HL) {

LNode*cp,*np;

cp=HL->next;//将指向第一个结点的指针赋给cp

while(cp!=HL)//遍历单链表，向系统交回每一个结点。 {

np=cp->next;//保存下一个结点的指针。 delete cp;//删除当前结点。

cp=np;//使下一个结点成为当前结点。 }

HL->next=HL;//置单链表为空 }

⑶得到单链表的长度 int ListSize(LNode*HL)

. . .

{

LNode*p=HL->next; int i=0;

while(p!=HL){i++;p=p->next;} return i; }

⑷检查单链表是否为空 int ListEmpty(LNode*hl) {

return(HL->next==HL); }

⑸得到单链表中第pos个结点中的元素 ElemType GetElem(LNode*HL,int pos) {

file:///D|/-------------------上架商品-----... (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 13／21 页）[2010-3-16 22:06:59]

file:///D|/-------------------上架商品---------------/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt if(pos<1){

cerr<<\ exit(1); }

LNode* p=HL->next; int i=0;

while(p!=HL){ i++;

if(i==pos)break; p=p->next; }

if(p!=HL)return p->data; else{

cerr<<\ exit(1); } } ⑹遍历单链表

void TraverseList(LNode*HL) {

LNode* p=HL->next; while(p!=HL){

cout<data<<\ p=p->next; }

. . .