1、精選優質文檔-傾情為你奉上2.4已知順序表L遞增有序，試寫一算法，將X插入到線性表的適當位置上，以保持線性表的有序性。解：int InsList(SeqList *L,int X) int i=0,k; if(L-last=MAXSIZE-1)printf(表已滿無法插入！)；return(ERROR);while(ilast&L-elemilast;k=I;k-)L-elemk+1=L-elemk; L-elemi=X; L-last+; return(OK); 2.5寫一算法，從順序表中刪除自第i個元素開始的k個元素。解：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已知線性表中的元素（整數）以遞增有序排列，并以單鏈表作存儲結構。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時間復雜度（注意：mink和maxk是給定的兩個變量，他們的值為任意的整數）。解：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(參數不合法！);return ERROR;elsewhile(p-next-datanext;q=p-next;while(q-datanext=q-next;free(q);q=p-next;return OK;2.7試分別以不同的存儲結構實現線性表的就地逆置算法，即在原表的儲存空間將線性表（a1，a1，,an）逆置為（an，an-1，a1）。 （1）以順序表

4、作存儲結構。解：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）以單鏈表作存儲結構。解：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假設兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲結構，請編寫算法，將A表和B表歸并成一個按元素值遞減的有序排列的線性表C，并要求利用原表（即A表和B表的）結點空間存放表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假設有一個循環鏈表的長度大于1，且表中既無頭結點也無頭指針。已知s為指向鏈表某個結點的指針，試編寫算法在鏈表中刪除指針s所指結點的前驅結點。解：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已知有單鏈表表示的線性表中含有三類字符的數據元素（如字母字符、數字字符和其他字符），試編寫算法來構造三個以循環鏈表表示的線性表，使每個表中只含同一類字符，且利用原表中的結點空間作為這三個表的結點空間，頭結點可另辟空間。解:LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)/把單鏈表L的元素按類型分為三個循環鏈表.CiList為帶頭結點的單循環鏈表類型. 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; /建立頭結點 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設線性表A=（a1，a2，,am），B=（b1，b2，bn），試寫一個按下列規則合并A、B為線性表C的算法

9、，使得C=（a1，b1，an，bn，an+1，am）當mn時或者C=（a1，b1，am，bm，bm+1，bn）當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將一個用循環鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式中各自僅含奇次項或偶次項，并要求利用原鏈表中的結點空間來構成這兩個鏈表。解：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建立一個帶頭節點的線性表，用以存放輸入的二進制數，鏈表中每個結點的data域存放一個二進制位，并在此鏈上實現對二進制數加1的運算。解：void BinnaryFod(Dlinklist DL)DNode *p,*s;p=DL;while(p-prior!