數(shù)據(jù)結(jié)構(gòu)第二章課后答案2.4已知順序表L遞增有序，試寫一算法，將X插入到線性表的適當位置上，以保持線性表的有序性。解：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個元素開始的k個元素。解：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;數(shù)據(jù)結(jié)構(gòu)第二章課后答案全文共7頁，當前為第1頁。 returnOK;數(shù)據(jù)結(jié)構(gòu)第二章課后答案全文共7頁，當前為第1頁。 }}2.6已知線性表中的元素（整數(shù)）以遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時間復(fù)雜度（注意：mink和maxk是給定的兩個變量，他們的值為任意的整數(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試分別以不同的存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法，即在原表的儲存空間將線性表（a1，a1，…,an）逆置為（an，an-1，…，a1）。（1）以順序表作存儲結(jié)構(gòu)。解：intReversePosition(SpListL){ intk,temp,len; intj=0; k=L->last; len=L->last+1; for(j;j<len/2;j++)數(shù)據(jù)結(jié)構(gòu)第二章課后答案全文共7頁，當前為第2頁。數(shù)據(jù)結(jié)構(gòu)第二章課后答案全文共7頁，當前為第2頁。 temp=L->elem[k-j]; elem[k-j]=elem[j]; elem[j]=temp; } returnOK;}（2）以單鏈表作存儲結(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è)兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲結(jié)構(gòu)，請編寫算法，將A表和B表歸并成一個按元素值遞減的有序排列的線性表C，并要求利用原表（即A表和B表的）結(jié)點空間存放表C解：voidmerge(SepList*LA,SepList*LB,SepList*LC){ Node*p1,*p2,*q1,*q2;數(shù)據(jù)結(jié)構(gòu)第二章課后答案全文共7頁，當前為第3頁。數(shù)據(jù)結(jié)構(gòu)第二章課后答案全文共7頁，當前為第3頁。 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è)有一個循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點也無頭指針。已知s為指向鏈表某個結(jié)點的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點的前驅(qū)結(jié)點。解：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)造三個以循環(huán)鏈表表示的線性表，使每個表中只含同一類字符，且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，頭結(jié)點可另辟空間。解:LinkList_Divide(LinkList&L,CiList&A,CiList&B,CiList&C)//把單鏈表L的元素按類型分為三個循環(huán)鏈表.CiList為帶頭結(jié)點的單循環(huán)鏈表類型.{s=L->next;數(shù)據(jù)結(jié)構(gòu)第二章課后答案全文共7頁，當前為第4頁。數(shù)據(jù)結(jié)構(gòu)第二章課后答案全文共7頁，當前為第4頁。p=A;B=(CiList*)malloc(sizeof(CiLNode));q=B;C=(CiList*)malloc(sizeof(CiLNode));r=C;//建立頭結(jié)點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），試寫一個按下列規(guī)則合并A、B為線性表C的算法，使得C=（a1，b1，…，an，bn，an+1，…，am）當m>n時或者C=（a1，b1，…，am，bm，bm+1，…，bn）當m<=n時線性表A、B、C均以單鏈表作為儲存結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。解：Liklistmerge(LinklistALinklistB){ LinklistC; Node*pa,*pb,*r; C=A; r=A; pa=A->next;數(shù)據(jù)結(jié)構(gòu)第二章課后答案全文共7頁，當前為第5頁。數(shù)據(jù)結(jié)構(gòu)第二章課后答案全文共7頁，當前為第5頁。 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; else r->next=pa; return(C); }}2.12將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式中各自僅含奇次項或偶次項，并要求利用原鏈表中的結(jié)點空間來構(gòu)成這兩個鏈表。解：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);數(shù)據(jù)結(jié)構(gòu)第二章課后答案全文共7頁，當前為第6頁。數(shù)據(jù)結(jié)構(gòu)第二章課后答案全文共7頁，當前為第6頁。 Greate(RA,p); p=p->next; }}2.13建立一個帶頭節(jié)點的線性表，用以存放輸入的二進制數(shù)，鏈表中每個結(jié)點的data域存放一個二進制位，并在此鏈上實現(xiàn)對二進制數(shù)加1的運算。解：voidBinnaryFod(DlinklistDL){ DNode*p,*s; p=DL; while(p->prior!=DL) { p=p->prior; if(p->data==0) { p->data=1; break; }