1、精選優(yōu)質(zhì)文檔-傾情為你奉上2.4已知順序表L遞增有序，試寫一算法，將X插入到線性表的適當(dāng)位置上，以保持線性表的有序性。解：int InsList(SeqList *L,int X) int i=0,k; if(L-last=MAXSIZE-1)printf(表已滿無(wú)法插入！)；return(ERROR);while(ilast&L-elemilast;k=I;k-)L-elemk+1=L-elemk; L-elemi=X; L-last+; return(OK); 2.5寫一算法，從順序表中刪除自第i個(gè)元素開始的k個(gè)元素。解：int LDel(Seqlist *L,int i,int k)if

2、(i=1|(i+kL-last+1)printf(輸入的i，k值不合法)；return(ERROR);else if(i+k=L-last+2)L-last=i-2;return OK;elsej=i+k-1;while(jlast)elemj-k=elemj;j+;L-last=L-last-k+1;return OK;2.6已知線性表中的元素（整數(shù)）以遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時(shí)間復(fù)雜度（注意：mink和maxk是給定的兩個(gè)變量，他們的值為任意的整數(shù)）。解：int Delete(L

3、inklist,int mink,int maxk)Node *p,*q;p=L;while(p-next!=NULL)p=p-next;if(mink=maxk|L-next-data=maxk|mink+1=maxk)printf(參數(shù)不合法！);return ERROR;elsewhile(p-next-datanext;q=p-next;while(q-datanext=q-next;free(q);q=p-next;return OK;2.7試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即在原表的儲(chǔ)存空間將線性表（a1，a1，,an）逆置為（an，an-1，a1）。 （1）以順序表

4、作存儲(chǔ)結(jié)構(gòu)。解：int ReversePosition(SpList L)int k,temp,len;int j=0;k=L-last;len=L-last+1;for(j;jelemk-j;elemk-j=elemj;elemj=temp;return OK; （2）以單鏈表作存儲(chǔ)結(jié)構(gòu)。解：int ReversePosition(Linklist L)Node *NL,q,r;q=L;r=L;NL=L-next;if(NL=NULL)return ERROR;while(q-next!=NULL)q=q-next;r-next=q;r=q;while(NL-next!=r&NL-next!

5、=NULL)q=NL;while(q-next!=r)q=q-next;r-next=q; r=q;r-next=NL; NL-next=NULL: return OK;2.8假設(shè)兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法，將A表和B表歸并成一個(gè)按元素值遞減的有序排列的線性表C，并要求利用原表（即A表和B表的）結(jié)點(diǎn)空間存放表C解：void merge(SepList *LA,SepList *LB,SepList *LC)Node *p1,*p2,*q1,*q2;LA-next=p1;LB-next=q1;while(p1!=NULL&q1!=NULL)if(p

6、1-dataq1-data)q2=q1-next;q1-next=LC-next;LC-next=q;q1=q2;elsep2=p1-next;p1-next=LC-next;LC-next=p1;p1=p2;2.9假設(shè)有一個(gè)循環(huán)鏈表的長(zhǎng)度大于1，且表中既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針。已知s為指向鏈表某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。解：ElemType DeletePreElem (Node *s)ElemType temp;Node *p,*pre;p=s;while(p-next!=s)p=p-next;pre=p;while(p-next!=pre)p=p-next

7、;p-next=s;temp=pre-data;free(pre);return temp;2.10已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如字母字符、數(shù)字字符和其他字符），試編寫算法來(lái)構(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(CiLN

8、ode); 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-datadata=A&s-datanext=s; p=s; else if(s-data=0&s-datanext=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的算法

9、，使得C=（a1，b1，an，bn，an+1，am）當(dāng)mn時(shí)或者C=（a1，b1，am，bm，bm+1，bn）當(dāng)mnext;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)空間來(lái)構(gòu)成這兩個(gè)鏈表。解：typedef struct Polynodeint coef;i

10、nt exp;struct polynode *next;Polynode *PolyList;void GreateCircle LinklistC(Linklist RL,Node *e)Node *p;p=RL-next;RL-next=e;RL=RL-next;RL-next=p;void DescouposeList(Linklist RL Descoupose RA Descoupose RB)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)的data域存放一個(gè)二進(jìn)制位，并在此鏈上實(shí)現(xiàn)對(duì)二進(jìn)制數(shù)加1的運(yùn)算。解：void BinnaryFod(Dlinklist DL)DNode *p,*s;p=DL;while(p-prior!