數(shù)據(jù)結(jié)構(gòu)(c語言版 嚴蔚敏)習題集答案第2章 線性表

StatusOrderListlnsert-sq(SqListva,ElemTypex){

〃將x插入到遞增有序的順序表va中，插入后va仍然遞增有序(算法1)

pe));

if(!newbase)exit(OVERFLOW);

}〃當前存儲空間已滿，增加分配空間

for

*q=x;

returnOK;

}//OrderListlnsert-sq

StatusOrderListlnsert-sq(SqListva,ElemTypex){

〃將x插入到遞增有序的順序表va中,插入后va仍然遞增有序(算法2)

newbase=(ElemType*)

if(!newbase)exit(OVERFLOW);

}〃當前存儲空間已滿，增加分配空間

*(p+l)=x;

returnOK;

}//OrderListlnsert-sq

,d)和B=(b?...,b”)均為順序表，A'和B'分別為A和B中除去最大共同前綴后的子表。若

A'二B'二空表，則A=B；若A'二空表，而B'#空表，或者兩者均不為空表，且A'的首元小于B'的

首元，則*B；否則A>B。試寫一個比較A,B大小的算法。

intCompare-List(SqLista,SqListb){

〃a,b為順序表，若a<b時，返回T；a=b時,返回0；a>b時,返回1

i=0;

switch{

.length-1)

default:return1;

}

}//Compare-List

statusdel-l(LinkList&la,intmink,intmaxk){

〃匕為帶頭結(jié)點的單鏈表的頭指針，單鏈表中的結(jié)點以值遞增有序排列

//本算法刪除表中所有值大于mink且小于maxk的元素，mink<maxk

if(mink>=maxk)returnERROR

P=la;

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

q=p;

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

q=q->next;

p1=p->next;

while(p1<>q){q1=p1;p1=p1->next;free(q1);}

p->next=q;

}//del-l

LinkListpriou(LinkListla,LinkListq1){

〃返回指向單鏈表la中結(jié)點的指針p1,p1->next=q1

p1=la;

while(p1->next!=q1)p1=p1->next;

returnp1;

}//priou

voidReverse-List-l(LinkList&la){

〃就地逆置單鏈表la(算法1)

if(!la->next)return;

p=la->next;q=priou(la,NULL);

while(p!=q){

p->data〈?〉q->data;

if(p=q)return;

q=priou(la,q);

)

}//Reverse-List-l

voidReverse-List-l(LinkList&la){

〃就地逆置單鏈表la(算法2)

p=priou(la,NULL);last=p;

pre=priou(la,p);

while(pre!=la){

p->next=pre;

p=pre;

pre=priou(la,p);

)

p->next=NULL;

la->next=last;

}//Reverse-List-l

voidReverse-List-l(LinkList&la){

〃就地逆置單鏈表la(算法3)

if(!la->next)return;〃空表

pre=la->next;〃前

if(!pre->next)return;

p=pre->next;〃中

pre->next=NULL;〃原來的第一項將被作為最后一項；

next=p->next;〃后

while(p){〃當p不指向空地址時；

p->next=pre;〃最終使每一個后項的地址域都指向前一項，實現(xiàn)逆置；

pre=p;〃后移

p=next;〃后移

if(p)next=p->next;〃當p不指向空地址，即原來的next沒有被指向空；

)

la->next=pre;〃將頭指針指向現(xiàn)在的第一項；

return;

}//Reverse-List-l

voidReverse-List-l(LinkList&la){

〃就地逆置單鏈表la(算法4)

p=la->next;

if(!p||!p->next)return;〃空表或只有一項；

pn=p->next;p->next=NULL;

while(pn){

p=pn;pn=pn->next;〃后移;

p->next=la->next;〃后一項的地址域指向前一項；

la->next=p;〃頭指針指向后一項；

}

return;

}//Reverse-List-l

voidMergeList(LinkList&a,LinkList&b,LinkList&c){

〃已知單鏈表a和b的元素按值遞增有序排列

〃歸并a和b得到新的單鏈表c,c的元素按值遞減有序

c=a;p=a->next;q=b->next;c->next=NULL;

while(p&&q)

if(p->data<q->data){

pn=p->next;p->next=c->next;

c->next=p;p=pn;

)

else{

qn=q->next;q->next=c->next;

c->next=q;q=qn;

)

while(p){pn=p->next;p->next=c->next;c->next=p;p=pn;}

while(q){qn=q->next;q->next=c->next;c->next=q;q=qn;}

free(b);

}//MergeList

voidCutApart-LinkList(LinkList&l,LinkListla,LinkListlb,LinkListlc){

〃單鏈表1中的元素含有三類字符：字母、數(shù)字和其它字符

〃本算法將I分割為la.lb和1c三個循環(huán)鏈表，它們分別只含字母、數(shù)字和其它字符

la=(LinkList)malloc(sizeof(LNode));la->next=la;

lb=(LinkList)malloc(sizeof(LNode));lb->next=lb;

lc=(LinkList)malloc(sizeof(LNode));lc->next=lc;

pn=l->next;

while(pn){

p=pn;pn=pn->next;

switch{

case('a'<=p->data&&p->data<='z')

||('A'<=p->data&&p->data<='Z'):p->next=la->next;la->next=p;break;

case('0'<=p->data&&p->data<-9'):p->next=lb->next;lb->next=p;break;

default:p->next=lc->next;lc->next=p;

}//switch

}//while

free(l);

}//CutApart-LinkList

typedefstruct{

floatcoef;

intexpn;

}*Poly,ElemType;

floatPolynomial(Poly&p,intm,floatx0){

〃多項式P的順序存儲結(jié)構(gòu)中依次存放有Cl,ei,C2,e2,...,Cm,em

〃X0為給定值，本算法計算Pn(XO)的值

x=xOAp[O].expn;

pn=p[0].coef*x;

for(i=1;i<=m;++i){

x=x*xOA(p[i].expn-p[i-1].expn);

pn=pn+p[i].coef*x;

}

retrunpn;

}//Polynomial

(以下內(nèi)容來自)

第二章線性表

StatusDeleteK(SqList&a,inti,intk)〃刪除線性表a中第i個元素起的k個元素

returnOK;

}//DeleteK

Statuslnsert_SqList(SqList&va,intx)〃把x插入遞增有序表va中

returnOK;

}//lnsert_SqList

intListComp(SqListA.SqListB)〃比較字符表A和B,并用返回值表示結(jié)果，值為

正，表示A>B;值為負，表示A〈B;值為零，表示A=B

return0;

}//ListComp

LNode*Locate(LinkListL,intx)〃鏈表上的元素查找，返回指針

(

for(p=l->next;p&&p->data!=x;p=p->next);

returnp;

}//Locate

intLength(LinkListL)〃求鏈表的長度

(

for(k=0,p=L;p->next;p=p->next,k++);

returnk;

}//Length

voidListConcat(LinkListha.LinkListhb.LinkList&hc)〃把鏈表hb接在ha后面形

成鏈表he

hc=ha;p=ha;

while(p->next)p=p->next;

p->next=hb;

}//ListConcat

見書后答案.

Statuslnsert(LinkList&L,inti,intb)〃在無頭結(jié)點鏈表L的第i個元素之前插入元

素b

(

p=L;q=(LinkList*)malloc(sizeof(LNode));

if(i==1)

(

}

else

(

while(-i>1)p=p->next;

q->next=p->next;p->next=q;〃插入在第i個元素的位置

)

}//lnsert

StatusDelete(LinkList&L,inti)〃在無頭結(jié)點鏈表L中刪除第i個元素

(

if(i==1)L=L->next;//刪除第一^個元素

else

(

P=L；

while(-i>1)p=p->next;

p->next=p->next->next;//刪除第i個元素

)

}//Delete

StatusDelete_Between(Linklist&L,intmaxk)//刪除元素遞增排列的鏈

表L中值大于mink且小于maxk的所有元素

P=L;

while(p->next->data<=mink)p=p->next;//p是最后一^不大于mink的元素

if(p->next)〃如果還有比mink更大的元素

(

q=p->next;

while(q->data<maxk)q=q->next;//q是第一個不小于maxk的元素

p->next=q;

}

}//Delete_Between

StatusDelete_Equal(Linklist&L)〃刪除元素遞增排列的鏈表L中所有值相同的元

素

(

p=L->next;q=p->next;〃p,q指向相鄰兩元素

while(p->next)

(

if(p->data!=q->data)

(

p=p->next;q=p->next;〃當相鄰兩元素不相等時,p,q都向后推一步

)

else

(

while(q->data==p->data)q=q->next;

p->next=q;p=q;q=p->next;〃當相鄰元素相等時刪除多余元素

}

}//while

}//Delete_Equal

voidreverse(SqList&A)〃順序表的就地逆置

}//reverse

voidLinkList_reverse(Linklist&L)〃鏈表的就地逆置;為簡化算法,假設(shè)表長大于2

p=L->next;q=p->next;s=q->next;p->next=NULL;

while(s->next)

(

q->next=p;p=q;

q=s;s=s->next;//把L的元素逐個插入新表表頭

)

q->next=p;s->next=q;A->next=s;

}//LinkList_reverse

分析:本算法的思想是，逐個地把L的當前元素q插入新的鏈表頭部,p為新表表頭.

voidmerge1(LinkList&A,LinkList&B,LinkList&C)//把鏈表A和B合并為C,A和

B的元素間隔排列，且使用原存儲空間

(

p=A->next;q=B->next;C=A;

while(p&&q)

(

s=p->next;p->next=q;〃將B的元素插入

if(s)

(

t=q->next;q->next=s;〃如A非空，將A的元素插入

}

P=s；q=t;

}//while

}//merge1

voidreverse_merge(LinkList&A,LinkList&B,LinkList&C)〃把元素遞增排列的鏈

表A和B合并為C,且C中元素遞減排列，使用原空間

(

pa=A->next;pb=B->next;pre=NULL;//pa和pb分別指向A,B的當前元素

while(pa&&pb)

(

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

(

pc=pa;q=pa->next;pa->next=pre;pa=q;〃將A的元素插入新表

}

else

pc=pb;q=pb->next;pb->next=pre;pb=q;〃將B的元素插入新表

)

pre=pc;

)

while(pa)

(

q=pa->next;pa->next=pc;pc=pa;pa=q;〃插入A中余下的元素

)

while(pb)

(

q=pb->next;pb->next=pc;pc=pb;pb=q;//ffiAB中余下的元素

}

C=A;A->next=pc;〃構(gòu)造新表頭

}//reverse_merge

分析:本算法的思想是，按從小到大的順序依次把A和B的元素插入新表的頭部

pc處，最后處理A或B的剩余元素.

voidSqList_lntersect(SqListA.SqListB.SqList&C)〃求元素遞增排列的線性表A

和B的元素的交集并存入C中

(

i=1;j=1;k=O;

i++;j++;〃就添加到C中

)

}//while

}//SqList_lntersect

voidLinkList_lntersect(LinkListA,LinkListB.LinkList&C)〃在鏈表結(jié)構(gòu)上重做上

題

(

p=A->next;q=B->next;

pc=(LNode*)malloc(sizeof(LNode));

while(p&&q)

(

if(p->data<q->data)p=p->next;

elseif(p->data>q->data)q=q->next;

else

(

s=(LNode*)malloc(sizeof(LNode));

s->data=p->data;

pc->next=s;pc=s;

p=p->next;q=q->next;

)

}//while

C=pc;

}//LinkList_lntersect

voidSqList_lntersect_True(SqList&A,SqListB)〃求元素遞增排列的線性表A和

B的元素的交集并存回A中

(

i=1;j=1;k=O;

i++;j++;〃且C中沒有，就添加到C中

)

}//while

}//SqList_lntersect_True

voidLinkList_lntersect_True(LinkList&A,LinkListB)〃在鏈表結(jié)構(gòu)上重做上題

(

p=A->next;q=B->next;pc=A;

while(p&&q)

(

if(p->data<q->data)p=p->next;

elseif(p->data>q->data)q=q->next;

elseif(p->data!=pc->data)

(

pc=pc->next;

pc->data=p->data;

p=p->next;q=q->next;

}

}//while

}//LinkList_lntersect_True

voidSqList_lntersect_delete(SqList&A,SqListB,SqListC)〃從有序順序表A中

刪除那些在B和C中都出現(xiàn)的元素

(

i=1;j=1;k=1;

else//找到了需要從A中刪除的元素

}//else

}//while

)

J++；

}//for

}//SqList_lntersect_delete

分析:本算法的時間復雜度為O(m),m為表長.思考:你自己的算法時間復雜度是多

少？實際上也可以只用一遍掃描就完成整個操作，且時間復雜度也為0(m),但非常

復雜，你能寫出來嗎？

voidLinkList_lntersect_delete(LinkList&A,LinkListB,LinkListC)〃在鏈表結(jié)構(gòu)上

重做上題

(

p=B->next;q=C->next;r=A-next;

while(p&&q&&r)

(

if(p->data<q->data)p=p->next;

elseif(p->data>q->data)q=q->next;

else

(

u=p->data;〃確定待刪除元素u

while(r->next->data<u)r=r->next;//確定最后一個小于u的元素指針r

if(r->next->data==u)

(

s=r->next;

while(s->data==u)

t=s;s=s->next;free(t);//確定第一^大于u的元素指針s

}//while

r->next=s;//刪除r和s之間的元素

}//if

while(p->data=u)p=p->next;

while(q->data=u)q=q->next;

}//else

}//while

}//LinkList_lntersect_delete

StatusDelete_Pre(CiLNode*s)〃刪除單循環(huán)鏈表中結(jié)點s的直接前驅(qū)

(

P=s;

while(p->next->next!=s)p=p->next;//找到s的前驅(qū)的前驅(qū)p

p->next=s;

returnOK;

}//Delete_pre

StatusDuLNode_pre(DuLinkList&L)〃完成雙向循環(huán)鏈表結(jié)點的pre域

(

for(p=L;!p->next->pre;p=p->next)p->next->pre=p;

returnOK;

}//DuLNode_pre

(

s=L->next;

A=(CiList*)malloc(sizeof(CiLNode));p=A;

B=(CiList*)malloc(sizeof(CiLNode));q=B;

C=(CiList*)malloc(sizeof(CiLNode));r=C;〃建立頭結(jié)點

while(s)

(

if(isalphabet(s->data))

(

p->next=s;p=s;

)

elseif(isdigit(s->data))

q->next=s;q=s;

)

else

(

r->next=s;r=s;

)

}//while

p->next=A;q->next=B;r->next=C;〃完成循環(huán)鏈表

}//LinkList_divide

voidPrint_XorLinkedList(XorLinkedListL)〃從左向右輸出異或鏈表的元素值

(

while(p)

(

printf("%d",p->data);

q=XorP(p->LRPtr,pre);

pre=p;p=q;//任何一個結(jié)點的LRPtr域值與其左結(jié)點指針進行異或運算即得

到其右結(jié)點指針

)

}//Print_XorLinkedList

Statuslnsert_XorLinkedList(XorLinkedList&L,intx,inti)〃在異或鏈表L的第i個

元素前插入元素x

(

r=(XorNode*)malloc(sizeof(XorNode));

r->data=x;

if(i==1)//當插入點在最左邊的情況

(

r->LRPtr=p;

returnOK;

)

j=[;q=p_>LRPtr;//當插入點在中間的情況

while(++j<i&&q)

(

q=XorP(p->LRPtr,pre);

pre=p;p=q;

}//while〃在p,q兩結(jié)點之間插入

if(!q)returnINFEASIBLE;//i不可以超過表長

p->LRPtr=XorP(XorP(p->LRPtr,q),r);

q->LRPtr=XorP(XorP(q->LRPtr,p),r);

r->LRPtr=XorP(p,q);〃修改指針

returnOK;

}//lnsert_XorLinkedList

StatusDelete_XorLinkedList(XorlinkedList&L,inti)〃刪除異或鏈表L的第i個元

素

(

if(i==1)〃刪除最左結(jié)點的情況

(

q=p->LRPtr;

q->LRPtr=XorP(q->LRPtr,p);

returnOK;

)

j=1;q=p->LRPtr;

while(++j<i&&q)

(

q=XorP(p->LRPtr,pre);

pre=p;p=q;

}//while〃找到待刪結(jié)點q

if(!q)returnINFEASIBLE;//i不可以超過表長

p->LRPtr=XorP(p->LRPtr,q);

returnOK;

)

r=XorP(q->LRPtr,p);〃q為中間結(jié)點的情況，此時p,r分別為其左右結(jié)點

p->LRPtr=XorP(XorP(p->LRPtr,q),r);

r->LRPtr=XorP(XorP(r->LRPtr,q),p);〃修改指針

free(q);

returnOK;

}//Delete_XorLinkedList

while(p->next!=L&&p->next->next!=L)

(

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

p=p->next;

}〃此時p指向最后一個奇數(shù)結(jié)點

if(p->next==L)p->next=L->pre->pre;

elsep->next=l->pre;

p=p->next;〃此時p指向最后一個偶數(shù)結(jié)點

while(p->pre->pre!=L)

(

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

p=p->next;

}

p->next=L;〃按題目要求調(diào)整了next鏈的結(jié)構(gòu)，此時pre鏈仍為原狀

for(p=L;p->next!=L;p=p->next)p->next->pre=p;

}//reform

分析:next鏈和pre鏈的調(diào)整只能分開進行.如同時進行調(diào)整的話，必須使用堆棧保

存偶數(shù)結(jié)點的指針，否則將會破壞鏈表結(jié)構(gòu)，造成結(jié)點丟失.

DuLNode*LOCATE(DuLinkedList&L,intx)〃帶freq域的雙向循環(huán)鏈表上的查找

if(p==L)returnNULL;//沒找到

p->freq++;q=p->pre;

while(q->freq<=p->freq)q=q->pre;〃查找插入位置

if(q!=p->pre)

(

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

q->next->pre=p;p->next=q->next;

q->next=p;p->pre=q;〃調(diào)整位置

)

returnp;

}//LOCATE

floatGetValue_SqPoly(SqPolyP,intx0)〃求升幕順序存儲的稀疏多項式的值

(

PolyTerm