⑻ 根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。如假定两个有序单链
表中的元素为(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->data
{ // 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< //使cp指向被删除结点的后继结点 cp=ap->next; //若cp指向了表头附加结点，则后移ap和cp指针 if(cp==HL){ap=HL;cp=HL->next;} } //使最后一个人出列 cout< 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< . . .
数据结构实用教程(第三版)课后答案
