【文章內(nèi)容簡介】 eleteAndInsertSub(LinkList amp。la,LinkList amp。lb,int i,int j,int len){ LinkList p,q,s,prev=NULL。 int k=1。 if(i0||j0||len0) return INFEASIBLE。 // 在la表中查找第i個結(jié)點 p=la。 while(pamp。amp。ki){ prev=p。 p=pnext。 k++。 } if(!p)return INFEASIBLE。 // 在la表中查找第i+len1個結(jié)點 q=p。 k=1。 while(qamp。amp。klen){ q=pnext。 k++。 } if(!q)return INFEASIBLE。 // 完成刪除，注意，i=1的情況需要特殊處理 if(!prev) la=qnext。 else prevnext=qnext。 // 將從la中刪除的結(jié)點插入到lb中 if(j=1){ qnext=lb。 lb=p。 } else{ s=lb。 k=1。 while(samp。amp。kj1){ s=snext。 k++。 } if(!s)return INFEASIBLE。 qnext=snext。 snext=p。 //完成插入 } return OK。} 試寫一算法，在無頭結(jié)點的動態(tài)單鏈表上實現(xiàn)線性表操作Insert(L,i,b)，并和在帶頭結(jié)點的動態(tài)單鏈表上實現(xiàn)相同操作的算法進行比較。，實現(xiàn)線性表操作Delete(L,i)，并和在帶頭結(jié)點的動態(tài)單鏈表上實現(xiàn)相同操作的算法進行比較。 已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效的算法，刪除表中所有值大于mink且小于maxk的元素（若表中存在這樣的元素），同時釋放被刪結(jié)點空間，并分析你的算法的時間復(fù)雜度（注意，mink和maxk是給定的兩個參變量，它們的值可以和表中的元素相同，也可以不同）。解：Status ListDelete_L(LinkList amp。L,ElemType mink,ElemType maxk){ LinkList p,q,prev=NULL。 if(minkmaxk)return ERROR。 p=L。 prev=p。 p=pnext。 while(pamp。amp。pdatamaxk){ if(pdata=mink){ prev=p。 p=pnext。 } else{ prevnext=pnext。 q=p。 p=pnext。 free(q)。 } } return OK。} ，試寫一高效的算法，刪除表中所有值相同的多余元素（使得操作后的線性表中所有元素的值均不相同），同時釋放被刪結(jié)點空間，并分析你的算法的時間復(fù)雜度。解：void ListDelete_LSameNode(LinkList amp。L){ LinkList p,q,prev。 p=L。 prev=p。 p=pnext。 while(p){ prev=p。 p=pnext。 if(pamp。amp。pdata==prevdata){ prevnext=pnext。 q=p。 p=pnext。 free(q)。 } }} 試寫一算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表逆置為。解：// 順序表的逆置Status ListOppose_Sq(SqList amp。L){ int i。 ElemType x。 for(i=0。i。i++){ x=[i]。 [i]=[]。 []=x。 } return OK。} 試寫一算法，對單鏈表實現(xiàn)就地逆置。解：// 帶頭結(jié)點的單鏈表的逆置Status ListOppose_L(LinkList amp。L){ LinkList p,q。 p=L。 p=pnext。 Lnext=NULL。 while(p){ q=p。 p=pnext。 qnext=Lnext。 Lnext=q。 } return OK。} 設(shè)線性表，試寫一個按下列規(guī)則合并A，B為線性表C的算法，即使得 當(dāng)時； 當(dāng)時。線性表A，B和C均以單鏈表作存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲。解：// 將合并后的結(jié)果放在C表中，并刪除B表Status ListMerge_L(LinkList amp。A,LinkList amp。B,LinkList amp。C){ LinkList pa,pb,qa,qb。 pa=Anext。 pb=Bnext。 C=A。 while(paamp。amp。pb){ qa=pa。 qb=pb。 pa=panext。 pb=pbnext。 qbnext=qanext。 qanext=qb。 } if(!pa)qbnext=pb。 pb=B。 free(pb)。 return OK。} 假設(shè)有兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲結(jié)構(gòu)，請編寫算法將A表和B表歸并成一個按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線性表C，并要求利用原表（即A表和B表）的結(jié)點空間構(gòu)造C表。解：// 將合并逆置后的結(jié)果放在C表中，并刪除B表Status ListMergeOppose_L(LinkList amp。A,LinkList amp。B,LinkList amp。C){ LinkList pa,pb,qa,qb。 pa=A。 pb=B。 qa=pa。 // 保存pa的前驅(qū)指針 qb=pb。 // 保存pb的前驅(qū)指針 pa=panext。 pb=pbnext。 Anext=NULL。 C=A。 while(paamp。amp。pb){ if(padatapbdata){ qa=pa。 pa=panext。 qanext=Anext。 //將當(dāng)前最小結(jié)點插入A表表頭 Anext=qa。 } else{ qb=pb。 pb=pbnext。 qbnext=Anext。 //將當(dāng)前最小結(jié)點插入A表表頭 Anext=qb。 } } while(pa){ qa=pa。 pa=panext。 qanext=Anext。 Anext=qa。 } while(pb){ qb=pb。 pb=pbnext。 qbnext=Anext。 Anext=qb。 } pb=B。 free(pb)。 return OK。} 假設(shè)以兩個元素依值遞增有序排列的線性表A和B分別表示兩個集合（即同一表中的元素值各不相同），現(xiàn)要求另辟空間構(gòu)成一個線性表C，其元素為A和B中元素的交集，且表C中的元素有依值遞增有序排列。試對順序表編寫求C的算法。解：// 將A、B求交后的結(jié)果放在C表中Status ListCross_Sq(SqList amp。A,SqList amp。B,SqList amp。C){ int i=0,j=0,k=0。 while(i amp。amp。 j){ if([i][j]) i++。 else if([i][j]) j++。 else{ ListInsert_Sq(C,k,[i])。 i++。 k++。 } } return OK。} 。試對單鏈表編寫求C的算法。解：// 將A、B求交后的結(jié)果放在C表中，并刪除B表Status ListCross_L(LinkList amp。A,LinkList amp。B,LinkList amp。C){ LinkList pa,pb,qa,qb,pt。 pa=A。 pb=B。 qa=pa。 // 保存pa的前驅(qū)指針 qb=pb。 // 保存pb的前驅(qū)指針 pa=panext。 pb=pbnext。 C=A。 while(paamp。amp。pb){ if(padatapbdata){ pt=pa。 pa=panext。 qanext=pa。 free(pt)。 } else if(padatapbdata){ pt=pb。 pb=pbnext。 qbnext=pb。 free(pt)。 } else{ qa=pa。 pa=panext。 } } while(pa){ pt=pa。 pa=panext。 qanext=pa。 free(pt)。 } while(pb){ pt=pb。 pb=pbnext。 qbnext=pb。 free(pt)。 } pb=B。 free(pb)。 return OK。} ，對順序表重新編寫求得表C的算法。(1) 假設(shè)在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；(2) 利用A表空間存放表C。解：(1)// A、B求交，然后刪除相同元素，將結(jié)果放在C表中Status ListCrossDelSame_Sq(SqList amp。A,SqList amp。B,SqList amp。C){ int i=0,j=0,k=0。 while(i amp。amp。 j){ if([i][j]) i++。 else if([i][j]) j++。 else{ if(==0){ ListInsert_Sq(C,k,[i])。 k++。 } else if([]!=[i]){ ListInsert_Sq(C,k,[i])。 k++。 } i++。 } } return OK。}(2)// A、B求交，然后刪除相同元素，將結(jié)果放在A表中Status ListCrossDelSame_Sq(SqList amp。A,SqList amp。B){ int i=0,j=0,k=0。 while(i amp。amp。 j){ if([i][j]) i++。 else if([i][j]) j++。 else{ if(k==0){ [k]=[i]。 k++。 } else if([k]!=[i]){ [k]=[i]。 k++。 } i++。 } } =k。 return OK。} ，對單鏈表重新編寫求得表C的算法。(1) 假設(shè)在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；(2) 利用原表（A表或B表）中的結(jié)點構(gòu)成表C，并釋放A表中的無用結(jié)點空間。解： (1)// A、B求交，結(jié)果放在C表中，并刪除相同元素Status ListCrossDelSame_L(LinkList amp。A,LinkList amp。B,LinkList amp。C){ LinkList pa,pb,qa,qb,pt。 pa=A。 pb=B。 qa=pa。 // 保存pa的前驅(qū)指針 qb=pb。 // 保存pb的前驅(qū)指針 pa=panext。 pb=pbnext。 C=A。 while(paamp。amp。pb){ if(padatapbdata){ pt=pa。 pa=panext。 qanext=pa。 free(pt)。 } else if(padatapbdata){ pt=pb。 pb=pbnext。 qbnext=pb。 free(pt)。 } else{ if(padata==qadata){ pt=pa。 pa=panext。 qanext=pa。 free(pt)。 } else{ qa=pa。 pa=panext。 } } } while(pa){ pt=pa。 pa=panext。 qanext=pa。 free(pt)。 } while(pb){ pt=pb。 pb=pbnext。 qbnext=pb。 free(pt)。 } pb=B。 free(pb)。 return OK。}(2)// A、B求交，結(jié)果放在A表中，并刪除相同元素Status Li