【文章內(nèi)容簡(jiǎn)介】 ile(kj){ s=snext。 k++。 } snext=p。 qnext=snext。 return OK。}　　解：Status DeleteAndInsertSub(LinkList amp。laLinkList amp。lbint iint jint len){ LinkList pqsprev=NULL。 int k=1。 if(i0||j0||len0) return INFEASIBLE。 // 在la表中查找第i個(gè)結(jié)點(diǎn) p=la。 while(pamp。amp。ki){ prev=p。 p=pnext。 k++。 } if(!p)return INFEASIBLE。 // 在la表中查找第i+len1個(gè)結(jié)點(diǎn) 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é)點(diǎn)插入到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é)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)線性表操作Insert(Lib)并和在帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比較實(shí)現(xiàn)線性表操作Delete(Li)并和在帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比較 已知線性表中的元素以值遞增有序排列并以單鏈表作存儲(chǔ)結(jié)構(gòu)試寫一高效的算法刪除表中所有值大于mink且小于maxk的元素（若表中存在這樣的元素）同時(shí)釋放被刪結(jié)點(diǎn)空間并分析你的算法的時(shí)間復(fù)雜度（注意mink和maxk是給定的兩個(gè)參變量它們的值可以和表中的元素相同也可以不同）　　解：Status ListDelete_L(LinkList amp。LElemType minkElemType maxk){ LinkList pqprev=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。} 試寫一高效的算法刪除表中所有值相同的多余元素（使得操作后的線性表中所有元素的值均不相同）同時(shí)釋放被刪結(jié)點(diǎn)空間并分析你的算法的時(shí)間復(fù)雜度　　解：void ListDelete_LSameNode(LinkList amp。L){ LinkList pqprev。 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)。 } }} 試寫一算法實(shí)現(xiàn)順序表的就地逆置即利用原表的存儲(chǔ)空間將線性表逆置為　　解：// 順序表的逆置Status ListOppose_Sq(SqList amp。L){ int i。 ElemType x。 for(i=0。i。i++){ x=[i]。 [i]=[]。 []=x。 } return OK。} 試寫一算法對(duì)單鏈表實(shí)現(xiàn)就地逆置　　解：// 帶頭結(jié)點(diǎn)的單鏈表的逆置Status ListOppose_L(LinkList amp。L){ LinkList pq。 p=L。 p=pnext。 Lnext=NULL。 while(p){ q=p。 p=pnext。 qnext=Lnext。 Lnext=q。 } return OK。} 設(shè)線性表試寫一個(gè)按下列規(guī)則合并AB為線性表C的算法即使得 當(dāng)時(shí)； 當(dāng)時(shí)線性表AB和C均以單鏈表作存儲(chǔ)結(jié)構(gòu)且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成注意：?jiǎn)捂湵淼拈L(zhǎng)度值m和n均未顯式存儲(chǔ)　　解：// 將合并后的結(jié)果放在C表中并刪除B表Status ListMerge_L(LinkList amp。ALinkList amp。BLinkList amp。C){ LinkList papbqaqb。 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è)有兩個(gè)按元素值遞增有序排列的線性表A和B均以單鏈表作存儲(chǔ)結(jié)構(gòu)請(qǐng)編寫算法將A表和B表歸并成一個(gè)按元素值遞減有序（即非遞增有序允許表中含有值相同的元素）排列的線性表C并要求利用原表（即A表和B表）的結(jié)點(diǎn)空間構(gòu)造C表　　解：// 將合并逆置后的結(jié)果放在C表中并刪除B表Status ListMergeOppose_L(LinkList amp。ALinkList amp。BLinkList amp。C){ LinkList papbqaqb。 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é)點(diǎn)插入A表表頭 Anext=qa。 } else{ qb=pb。 pb=pbnext。 qbnext=Anext。 //將當(dāng)前最小結(jié)點(diǎn)插入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è)以兩個(gè)元素依值遞增有序排列的線性表A和B分別表示兩個(gè)集合（即同一表中的元素值各不相同）現(xiàn)要求另辟空間構(gòu)成一個(gè)線性表C其元素為A和B中元素的交集且表C中的元素有依值遞增有序排列試對(duì)順序表編寫求C的算法　　解：// 將A、B求交后的結(jié)果放在C表中Status ListCross_Sq(SqList amp。ASqList amp。BSqList amp。C){ int i=0j=0k=0。 while(i amp。amp。 j){ if([i][j]) i++。 else if([i][j]) j++。 else{ ListInsert_Sq(Ck[i])。 i++。 k++。 } } return OK。} 試對(duì)單鏈表編寫求C的算法　　解：// 將A、B求交后的結(jié)果放在C表中并刪除B表Status ListCross_L(LinkList amp。ALinkList amp。BLinkList amp。C){ LinkList papbqaqbpt。 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。} 對(duì)順序表重新編寫求得表C的算法　　(1) 假設(shè)在同一表（A或B）中可能存在值相同的元素但要求新生成的表C中的元素值各不相同；　　(2) 利用A表空間存放表C　　解：(1)// A、B求交然后刪除相同元素將結(jié)果放在C表中Status ListCrossDelSame_Sq(SqList amp。ASqList amp。BSqList amp。C){ int i=0j=0k=0。 while(i amp。amp。 j){ if([i][j]) i++。 else if([i][j]) j++。 else{ if(==0){ ListInsert_Sq(Ck[i])。 k++。 } else if([]!=[i]){ ListInsert_Sq(Ck[i])。 k++。 } i++。 } } return OK。}(2)// A、B求交然后刪除相同元素將結(jié)果放在A表中Status ListCrossDelSame_Sq(SqList amp。ASqList amp。B){ int i=0j=0k=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。} 對(duì)單鏈表重新編寫求得表C的算法　　(1) 假設(shè)在同一表（A或B）中可能存在值相同的元素但要求新生成的表C中的元素值各不相同；　　(2) 利用原表（A表或B表）中的結(jié)點(diǎn)構(gòu)成表C并釋放A表中的無用結(jié)點(diǎn)空間　　解： (1)// A、B求交結(jié)果放在C表中并刪除相同元素Status ListCrossDelSame_L(LinkList amp。ALinkList amp。BLinkList amp。C){ LinkList papbqaqbpt。 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。