數(shù)據(jù)結(jié)構(gòu)第二章課后答案

2.4已知順序表 L遞增有序，試寫一算法，將 X插入到線性表的適當(dāng)位置上，以保持線性表的有序性。解：intInsList(SeqList*L,intX){inti=0,k;if(L->last>=MAXSIZE-1){printf("表已滿無法插入！ ")；return(ERROR);}while(i<=L->last&&L->elem[i]<X)i++;for(k=L->last;k>=I;k--)L->elem[k+1]=L->elem[k];L->elem[i]=X;L->last++;return(OK);}2.5寫一算法，從順序表中刪除自第 i個(gè)元素開始的 k個(gè)元素。解：intLDel(Seqlist*L,inti,intk){if(i=1||(i+k>L->last+1)){printf("輸入的 i，k值不合法")；return(ERROR);}elseif(i+k==L->last+2){L->last=i-2;returnOK;}else{j=i+k-1;while(j<=L->last){elem[j-k]=elem[j];j++;}L->last=L->last-k+1;returnOK;}}2.6已知線性表中的元素（整數(shù)）以遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于間復(fù)雜度（注意： mink

mink且小于maxk的元素（若表中存在這樣的元素）和maxk是給定的兩個(gè)變量，他們的值為任意的整數(shù)）

，分析你的算法的時(shí)。解：intDelete(Linklist,intmink,intmaxk){Node*p,*q;p=L;while(p->next!=NULL)p=p->next;if(mink>=maxk||L->next->data>=maxk||mink+1=maxk){printf("參數(shù)不合法！ ");returnERROR;}else{while(p->next->data<=mink)p=p->next;q=p->next;while(q->data<maxk&&q!=NULL){p->next=q->next;free(q);q=p->next;}returnOK;}}2.7試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即在原表的儲(chǔ)存空間將線性表a1，a1，?,an）逆置為（an，an-1，?，a1）。1）以順序表作存儲(chǔ)結(jié)構(gòu)。解：intReversePosition(SpListL){intk,temp,len;intj=0;k=L->last;len=L->last+1;for(j;j<len/2;j++){temp=L->elem[k-j];elem[k-j]=elem[j];elem[j]=temp;}returnOK;}2）以單鏈表作存儲(chǔ)結(jié)構(gòu)。解：intReversePosition(LinklistL){Node*NL,q,r;q=L;r=L;NL=L->next;if(NL==NULL)returnERROR;while(q->next!=NULL){q=q->next;r->next=q;r=q;}while(NL->next!=r&&NL->next!=NULL){q=NL;while(q->next!=r)q=q->next;r->next=q;r=q;}r->next=NL;NL->next=NULL:returnOK;}2.8假設(shè)兩個(gè)按元素值遞增有序排列的線性表 A和B，均以單鏈表作為存儲(chǔ)結(jié)構(gòu)，請編寫算法，將 A表和B表歸并成一個(gè)按元素值遞減的有序排列的線性表 C，并要求利用原表（即A表和B表的）結(jié)點(diǎn)空間存放表 C解：voidmerge(SepList*LA,SepList*LB,SepList*LC){Node*p1,*p2,*q1,*q2;LA->next=p1;LB->next=q1;while(p1!=NULL&&q1!=NULL)if(p1->data>q1->data){q2=q1->next;q1->next=LC->next;LC->next=q;q1=q2;}else{p2=p1->next;p1->next=LC->next;LC->next=p1;p1=p2;}}2.9假設(shè)有一個(gè)循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點(diǎn)也無頭指針。已知某個(gè)s為指向鏈表結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。解：ElemTypeDeletePreElem(Node*s){ElemTypetemp;Node*p,*pre;p=s;while(p->next!=s)p=p->next;pre=p;while(p->next!=pre)p=p->next;p->next=s;temp=pre->data;free(pre);returntemp;}2.10已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素 （如字母字符、 數(shù)字字符和其他字符），試編寫算法來構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。解:LinkList_Divide(LinkList&L,CiList&A,CiList&B,CiList&C)//把單鏈表 L的元素按類型分為三個(gè)循環(huán)鏈表 .CiList為帶頭結(jié)點(diǎn)的單循環(huán)鏈表類型 .{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é)點(diǎn)while(s!=NULL){if(s->data>='a'&&s->data<='z'||s->data>='A'&&s->data<='Z'){p->next=s;p=s;}elseif(s->data>='0'&&s->data<='9'){q->next=s;q=s;}else{r->next=s;r=s;}}p->next=A;q->next=B;r->next=C;}2.11設(shè)線性表A=（a1，a2，?,am），B=（b1，b2，?，bn），試寫一個(gè)按下列規(guī)則合并A、B為線性表C的算法，使得C=（a1，b1，?，an，bn，an+1，?，am）當(dāng)m>n時(shí)或者C=（a1，b1，?，am，bm，bm+1，?，bn）當(dāng)m<=n時(shí)線性表A、B、C均以單鏈表作為儲(chǔ)存結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。解：Liklistmerge(LinklistALinklistB){LinklistC;Node*pa,*pb,*r;C=A;r=A;pa=A->next;pb=B->next;while(pa!=NULL&&pb!=NULL){r->next=pa;r=pa;pa=pa->next;r->next=pb;r=pb;pb=pb->next;if(pa==NULL)r->next=pb;elser->next=pa;return(C);}}2.12將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式， 使這兩個(gè)多項(xiàng)式中各自僅含奇次項(xiàng)或偶次項(xiàng)，并要求利用原鏈表中的結(jié)點(diǎn)空間來構(gòu)成這兩個(gè)鏈表。解：typedefstructPolynode{intcoef;intexp;structpolynode*next;}Polynode*PolyList;voidGreateCircleLinklistC(LinklistRL,Node*e){Node*p;p=RL->next;RL->next=e;RL=RL->next;RL->next=p;}voidDescouposeList(LinklistRLDescouposeRADescouposeRB){Node*p;p=RL->next;if(p->next=NULL)return;p=p->next;while(p!=RL->next){if(p->exp%2==0)Greate(RB,p);elseGreate(RA,p);p=p->next;}}2.13建立一個(gè)帶頭節(jié)點(diǎn)的線性表，用以存放輸入的二進(jìn)制數(shù)，鏈表中每個(gè)結(jié)點(diǎn)的放一個(gè)二進(jìn)制位，并在此鏈上實(shí)現(xiàn)對二進(jìn)制數(shù)加 1的運(yùn)算。

data

域存解：voidBinnaryFod(DlinklistDL){DNode*p,*s;p=DL;whi