教材第二章部分习题参考解答.docx

教材第二章部分习题参考解答.docx

《教材第二章部分习题参考解答.docx》由会员分享，可在线阅读，更多相关《教材第二章部分习题参考解答.docx（20页珍藏版）》请在冰点文库上搜索。

教材第二章部分习题参考解答

教材第二章部分习题参考解答

一、单选题

1.B2.A3.C4.B5.D6.C

二、填空题

1．值指针

2．（38,56,25,60,42,74）

3.O（n）O

（1）

4.O

（1）O（n）

5.i-1i+1

6.p->nexta[p].next

7.表头

8．前驱后继

9．表尾表头

10．HL->next==NULLHL->next==HL

11.a[i].next=a[1].next;a[1].next=i;

12.i=a[1].next;a[1].next=a[i].next;

13.p=a[i].next;a[i].next=a[p].next;i=p;

14.a[j].next=a[i].next;a[i].next=j;

三、普通题

第1小题

1.（79,62,34,57,26,48）

2.（26,34,48,57,62,79）

3.（48,56,57,62,79,34）

4.（56,57,79,34）

5.（26,34,39,48,57,62）

第2小题

分析：

为了排版方便，假定采用以下输出格式表示单链表示意图：

每个括号内的数据表示一个元素结点，其中第一个数据为元素值，第二个数据为后继结点的指针，第一个元素结点前的数值为表头指针。

1.（7（79,6）,（62,5）,（34,4）,（57,3）,（26,2）,（48,0））

2.（3（26,5）,（34,2）,（48,4）,（57,6）,（62,7）,（79,0））

3.（2（48,8）,（56,4）,（57,6）,（62,7）,（79,5）,（34,0））

4.（8（56,4）,（57,7）,（79,5）,（34,0））

第3小题

1.ElemTypeDMValue（List&L）

//从线性表中删除具有最小值的元素并由函数返回，空出的位置

//由最后一个元素填补，若线性表为空则显示出错信息并退出运行。

{

if（ListEmpty（L））{

cerr<<"ListisEmpty!

"<

exit

（1）;

}

ElemTypex;

x=L.list[0];

intk=0;

for（inti=1;i

ElemTypey=L.list[i];

if（y

}

L.list[k]=L.list[L.size-1];

L.size--;

returnx;

}

2.intDelete1（List&L,inti）

//从线性表中删除第i个元素并由函数返回。

{

if（i<1||i>L.size）{

cerr<<"Indexisoutrange!

"<

exit

（1）;

}

ElemTypex;

x=L.list[i-1];

for（intj=i-1;j

L.list[j]=L.list[j+1];

L.size--;

returnx;

3.voidInsert1（List&L,inti,ElemTypex）

//向线性表中第i个元素位置插入一个元素。

{

if（i<1||i>L.size+1）{

cerr<<"Indexisoutrange!

"<

exit

（1）;

}

if（L.size==MaxSize）

{

cerr<<"Listoverflow!

"<

exit

（1）;

}

for（intj=L.size-1;j>=i-1;j--）

L.list[j+1]=L.list[j];

L.list[i-1]=x;

L.size++;

}

4.voidDelete2（List&L,ElemTypex）

//从线性表中删除具有给定值x的所有元素。

{

inti=0;

while（i

if（L.list[i]==x）{

for（intj=i+1;j

L.list[j-1]=L.list[j];

L.size--;

}

else

i++;

}

5.voidDelete3（List&L,ElemTypes,ElemTypet）

//从线性表中删除其值在给定值s和t之间的所有元素。

{

inti=0;

while（i

if（（L.list[i]>=s）&&（L.list[i]<=t））{

for（intj=i+1;j

L.list[j-1]=L.list[j];

L.size--;

}

else

i++;

}

6.voidDelete4（List&L,ElemTypes,ElemTypet）

//从有序表中删除其值在给定值s和t之间的所有元素。

{

inti=0;

while（i

if（L.list[i]

elsebreak;

if（i

intj=1;

while（（i+j

j++;//求出s和t之间元素的个数。

for（intk=i+j;k

L.list[k-j]=L.list[k];

L.size-=j;

}

}

7.voidMerge（List&L1,List&L2,List&L）

//将两个有序表合并成一个新的有序表并由变量返回。

{

if（L1.size+L2.size>MaxSize）{

cerr<<"Listoverflow!

"<

exit

（1）;

}

inti=0,j=0,k=0;

while（（i

if（L1.list[i]<=L2.list[j]）

{//将L1中的元素赋给L。

L.list[k]=L1.list[i];

i++;

}

else{//将L2中的元素赋给L。

L.list[k]=L2.list[j];

j++;

}

k++;

}

while（i

L.list[k]=L1.list[i];

i++;k++;

}

while（j

L.list[k]=L2.list[j];

j++;k++;

}

L.size=k;

}

8.voidDelete5（List&L）

//从线性表中删除所有其值重复的元素，使所有元素的值均不同。

{

inti=0;

while（i

intj=i+1;

while（j

{//删除重复值为L.list[i]的所有元素

if（L.list[j]==L.list[i]）{

for（intk=j+1;k

L.list[k-1]=L.list[k];

L.size--;

}

else

j++;

}

i++;

}

}

第4小题

1.voidContrary（LNode*&HL）

//将一个单链表按逆序链接。

{

LNode*p=HL;//p指向待逆序的第一个结点，初始指向原表头结点。

HL=NULL;//HL仍为逆序后的表头指针，初始值为空。

while（p!

=NULL）

{//把原单链表中的结点依次进行逆序链接。

LNode*q=p;//q指向待处理的结点。

p=p->next;//p指向下一个待逆序的结点。

//将q结点插入到已逆序单链表的表头。

q->next=HL;

HL=q;

}

}

2.voidDelete1（LNode*&HL,inti）

//删除单链表中的第i个结点。

{

if（i<1||HL==NULL）{

cerr<<"Indexisoutrange!

"<

exit

（1）;

}

LNode*ap,*cp;

ap=NULL;cp=HL;//cp指向当前结点，ap指向其前驱结点。

intj=1;

while（cp!

=NULL）

if（j==i）

break;//cp结点即为第i个结点。

else{//继续向后寻找。

ap=cp;

cp=cp->next;

j++;

}

if（cp==NULL）{

cerr<<"Indexisoutrange!

"<

exit

（1）;

}

if（ap==NULL）

HL=HL->next;

else

ap->next=cp->next;

deletecp;

}

3.ElemTypeMaxValue（LNode*HL）

//从单链表中查找出所有元素的最大值，该值由函数返回。

{

if（HL==NULL）{

cerr<<"Linkedlistisempty!

"<

exit

（1）;

}

ElemTypemax=HL->data;

LNode*p=HL->next;

while（p!

=NULL）{

if（maxdata）max=p->data;

p=p->next;

}

returnmax;

}

4.intCount（LNode*HL,ElemTypex）

//统计出单链表中结点的值等于给定值x的结点数。

{

intn=0;

while（HL!

=NULL）{

if（HL->data==x）n++;

HL=HL->next;

}

returnn;

}

5.voidCreate（LNode*&HL,ElemTypea[],intn）

//根据一维数组a[n]建立一个单链表

{

InitList（HL）;

for（inti=n-1;i>=0;i--）

InsertFront（HL,a[i]）;

}

6.voidOrderList（LNode*&HL）

//将一个单链表重新链接成有序单链表。

{

LNode*p=HL;//p指向待处理的第一个结点，初始指向原表头结点。

HL=NULL;//HL仍为待建立的有序表的表头指针，初始值为空。

while（p!

=NULL）

{//把原单链表中的结点依次进行有序链接。

LNode*q=p;//q指向待处理的结点。

p=p->next;//p指向下一个待处理的结点。

LNode*ap=NULL,*cp=HL;

//cp指向有序表中待比较的结点，ap指向其前驱结点。

while（cp!

=NULL）

{//为插入q结点寻找插入位置。

if（q->datadata）

break;

else{

ap=cp;

cp=cp->next;

}

}

//将q结点插入到ap和cp结点之间。

q->next=cp;

if（ap==NULL）

HL=q;

else

ap->next=q;

}

}

7.LNode*Merge1（LNode*&p1,LNode*&p2）

//将两个有序单链表合并成一个有序单链表。

{

LNodea;//a结点作为结果有序单链表的表头附加结点，这样

//便于处理,处理结束后返回a结点的指针域的值。

LNode*p=&a;//p指向结果有序单链表的表尾结点，

p->next=NULL;//初始指向表头附加结点。

while（（p1!

=NULL）&&（p2!

=NULL））

{//处理两个表非空时的情况。

if（p1->datadata）{

p->next=p1;p1=p1->next;

}

else{

p->next=p2;p2=p2->next;

}

p=p->next;

}

if（p1!

=NULL）p->next=p1;

if（p2!

=NULL）p->next=p2;

p1=p2=NULL;

returna.next;

}

8.LNode*Merge2（LNode*p1,LNode*p2）

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

{

LNodea;//用a作为新的有序单链表的表头附加结点。

LNode*p=&a;//p指向结果有序单链表的表尾结点，

p->next=NULL;//初始指向表头附加结点。

while（（p1!

=NULL）&&（p2!

=NULL））

{//处理两个表非空时的情况。

LNode*newptr=newLNode;

if（p1->datadata）

{//由p1->data建立新结点，然后p1指针后移。

newptr->data=p1->data;

p1=p1->next;

}

else

{//由p2->data建立新结点，然后p2指针后移。

newptr->data=p2->data;

p2=p2->next;

}

//将newptr结点插入到结果有序表的表尾。

p->next=newptr;

p=newptr;

}

while（p1!

=NULL）

{//继续处理p1单链表中剩余的结点。

LNode*newptr=newLNode;

newptr->data=p1->data;

p1=p1->next;

p->next=newptr;

p=newptr;

}

while（p2!

=NULL）

{//继续处理p2单链表中剩余的结点。

LNode*newptr=newLNode;

newptr->data=p2->data;

p2=p2->next;

p->next=newptr;

p=newptr;

}

p->next=NULL;

returna.next;

}

9.voidSeparate（LNode*HL,LNode*&p1,LNode*&p2）

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

{

LNodea,b;//a和b结点分别作为p1和p2单链表的表头附加结点。

LNode*t1=&a,*t2=&b;//t1和t2分别作为指向p1和p2单链表

//的表尾结点，初始指向表头附加结点。

LNode*p=HL;

while（p!

=NULL）

{//每循环一次产生一个新结点，并把它加入到

//p1或p2单链表的末尾。

LNode*newptr=newLNode;

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小题

参考算法如下：

voidJosephus（intn,intm,ints）

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

{

//生成表头附加结点，此时循环单链表为空。

LNode*HL=newLNode;

HL->next=HL;

inti;

//生成含有n个结点的、结点值依次为1,2,...,n的带表头附加结点

//的循环单链表。

for（i=n;i>=1;i--）{

//生成新结点。

LNode*newptr=newLNode;

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（intj=1;j

ap=cp;

cp=cp->next;

if（cp==HL）{ap=HL;cp=HL->next;}

}

//输出cp结点的值，即出列的人。

cout<data<<"";

//从单链表中删除cp结点。

ap->next=cp->next;

deletecp;

//使cp指针指向被删除结点的后继结点。

cp=ap->next;

//若cp指向了表头附加结点，则后移ap和cp指针。

if（cp==HL）{ap=HL;cp=HL->next;}

}

//使最后一个人出列。

cout<next->data<

//删除表头结点和表头附加结点。

deleteHL->next;

deleteHL;

}

第9小题

参考算法如下：

voidOrderList（SLNode*SL）

//假定SLNode类型为按题目要求所定义的结点类型，SL为指向

//表头附加结点的指针。

{

SL->range=NULL;

for（SLNode*p=SL->next;p!

=NULL;p=p->next）

{//每循环一次把p所指向的结点按序插入到以range域

//链接的有序表中

SLNode*ap,*cp;

//为p结点寻找合适的插入位置。

ap=SL;cp=ap->range;

while（cp!

=NULL）

if（p->datadata）

break;

else{

ap=cp;

cp=cp->range;

}

//插入位置在ap和cp之间，把p结点插入其中。

p->range=cp;

ap->range=p;

}

}

第10小题

参考程序如下：

//lx2-7.cpp

#include

#include

typedefintElemType;//规定元素类型为整型。

structSLNode//定义单链表结点。

{

ElemTypedata;

SLNode*next;

SLNode*range;

};

voidOrderList（SLNode*SL）

{

SL->range=NULL;

for（SLNode*p=SL->next;p!

=NULL;p=p->next）

{

SLNode*ap,*cp;

//为p结点寻找合适的插入位置。

ap=SL;cp=ap->range;

while（cp!

=NULL）

if（p->datadata）

break;

else{

ap=cp;

cp=cp->range;

}

//插入位置在ap和cp之间，把p结点插入其中。

p->range=cp;

ap->range=p;

}

}

voidmain（）

{

//按next域链接生成具有10个整数元素结点的链表。

SLNode*a=newSLNode;

a->next=NULL;

inti;

SLNode*p;

for（i=0;i<10;i++）{

p=newSLNode;

p->data=rand（）%30;//假定产生30以内的随机整数。

p->next=a->next;

a->next=p;

}

//按next域链接的次序输出单链表。

for（p=a->next;p!

=NULL;p=p->next）

cout<data<<"";

cout<

//调用按2.8题要求编写的操作算法。

OrderList（a）;

//按range域链接的次序输出单链表。

for（p=a->range;p!

=NULL;p=p->range）

cout<data<<"";

cout<

}