数据结构第2章作业

第2章作业参考答案

(2.12)、(2.19*)、(2.20)、(2.22)、(2.24*)、(2.28)、(2.33)、(2.38)

[2.12]

intSqListCompare(SqListA,SqListB)

(

p=0;

while(p<A.length&&p<B.length)

if(A.elem[p]==B.elem[p])p++;

elsebreak;

if(p==A.length&&p==B.length)return0;

if(p==A.length)return-1;

if(p==B.length)return1;

if(A.elem[p]<B.elem[p])return-1;

elsereturn1;

)

[2.19]

StatusListDelete(LinkList&L,intminkjntmaxk)

(

if(L->next==NULL)returnERROR;

pre=L;p=L->next;

while(p&&(p->data<=mink)){

pre=p;p=p->next;

)

while(p&&p->data<maxk)p=p->next;

if(pre->next){

t=pre->next;pre->next=p;

while(t!=p){

pre=t->next;

deletet;

t=pre;

)

)

returnOK;

)

需要考虑的情况：

(1)maxk<mink

(2)全部需要删除

(3)全不删除

(4)删除前半部分

(5)删除后半部分

(6)删除中间部分

[2,20]

StautsListDelete(LinkList&L)

(

if(L->next==NULL||L->next->next==NULL)returnERORR;

p=L->next;

while(p->next){

if(p->data==p->next->data){

q=p->next;

p->next=q->next;

deleteq;

)

elsep=p->next;

)

returnOK;

)

时间复杂度：O(n)

[2.22]

StatusReverse(LinkList&L)

(

p=L->next;

L->next=NULL;

while(p){

q=p->next;

p->next=L->next;L->next=p;

P二q;

)

returnOK;

)

注意：通常对链表中结点之间的连接顺序通过修改next实现，而不要修改dala内容。

[2.24]

StatusListMerge(LinkList&LC,LinkListLA,LinkListLB)

{

pa=LA->next;pb=LB->next;

LC=LA;LC->next=NULL;

while(pa&&pb){

if(pa->data<=pb->data){

q=pa;pa=pa->next;

q->next=LC->next;LC->next=q;

)

else{

q=pb;pb=pb->next;

q->next=LC->next;LC->next=q;

)

while(pa){

q=pa;pa=pa->next;

q->next=LC->next;LC->next=q;

)

while(pb){

q=pb;pb=pb->next;

q->next=LC->next;LC->next=q;

)

deleteLB;

returnOK;

)

[2.33]

StatusClassify(LinkListL,LinkList&LA,LinkList&LB,LinkList&LC)

(

InitList(LA);InitList(LB);InitList(LC);

p=L->next;

pa=LA->next;pb=LB->next;pc=LC->next;

while(p!=L){

switch{

case(p->datainletter):

pa->next=p;pa=pa->next;break;

case(p->dataindtgital):

pb->next=p;pb=pb->next;break;

casep->datainother):

pc->next=p;pc=pc->next;break;

)

p=p->next;

)

pa->next=LA;pb->next=LB;pc->next=LC;

returnOK;

【2.38]

StatusLocate(DULinkList&L,DULinkList&p,ElemTypee)

(

p=L->next;

while(p!=L&&p->data!=e)p=p->next;

if(p!=L){

p->freq++;

pre=p->prior;

while(pre!=L&&p->freq>pre->freq)pre=pre->prior;

p->next->pr