【文章內(nèi)容簡(jiǎn)介】 rev=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。} ，試寫(xiě)一高效的算法，刪除表中所有值相同的多余元素（使得操作后的線(xiàn)性表中所有元素的值均不相同），同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時(shí)間復(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ě)一算法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲(chǔ)空間將線(xiàn)性表逆置為。解：// 順序表的逆置Status ListOppose_Sq(SqList amp。L){int i。ElemType x。for(i=0。i。i++){x=[i]。[i]=[]。[]=x。}return OK。}【】 試寫(xiě)一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。解：// 帶頭結(jié)點(diǎn)的單鏈表的逆置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è)線(xiàn)性表，試寫(xiě)一個(gè)按下列規(guī)則合并A，B為線(xiàn)性表C的算法，即使得 當(dāng)時(shí)； 當(dāng)時(shí)。線(xiàn)性表A，B和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。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è)有兩個(gè)按元素值遞增有序排列的線(xiàn)性表A和B，均以單鏈表作存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫(xiě)算法將A表和B表歸并成一個(gè)按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線(xiàn)性表C，并要求利用原表（即A表和B表）的結(jié)點(diǎn)空間構(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é)點(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è)以?xún)蓚€(gè)元素依值遞增有序排列的線(xiàn)性表A和B分別表示兩個(gè)集合（即同一表中的元素值各不相同），現(xiàn)要求另辟空間構(gòu)成一個(gè)線(xiàn)性表C，其元素為A和B中元素的交集，且表C中的元素有依值遞增有序排列。試對(duì)順序表編寫(xiě)求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++。elseif([i][j]) j++。else{ListInsert_Sq(C,k,[i])。i++。k++。}}return OK。} 。試對(duì)單鏈表編寫(xiě)求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)。}elseif(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ì)順序表重新編寫(xiě)求得表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++。elseif([i][j]) j++。else{if(==0){ListInsert_Sq(C,k,[i])。k++。}elseif([]!=[i]){ListInsert_Sq(C,k,[i])。k++。}i++。}}return OK。}(2)// A、B求交，然后刪除相同元素，將結(jié)果放在A(yíng)表中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++。elseif([i][j]) j++。else{if(k==0){[k]=[i]。k++。}elseif([k]!=[i]){[k]=[i]。k++。}i++。}}=k。return OK。} ，對(duì)單鏈表重新編寫(xiě)求得表C的算法。(1) 假設(shè)在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；(2) 利用原表（A表或B表）中的結(jié)點(diǎn)構(gòu)成表C，并釋放A表中的無(wú)用結(jié)點(diǎn)空間。解：(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)。}elseif(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(yíng)表中，并刪除相同元素Status ListCrossDelSame_L(LinkList amp。A,LinkList amp。B){LinkList pa,pb,qa,qb,pt。pa=A。pb=B。qa=pa。 // 保存pa的前驅(qū)指針qb=pb。 // 保存pb的前驅(qū)指針pa=panext。pb=pbnext。while(paamp。amp。pb){if(padatapbdata){pt=pa。pa=panext。qanext=pa。free(pt)。}elseif(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。} 已知A，B和C為三個(gè)遞增有序的線(xiàn)性表，現(xiàn)要求對(duì)A表作如下操作：刪去那些既在B表中出現(xiàn)又在C表中出現(xiàn)的元素。試對(duì)順序表編寫(xiě)實(shí)現(xiàn)上述操作的算法，并分析你的算法的時(shí)間復(fù)雜度（注意：題中沒(méi)有特別指明同一表中的元素值各不相同）。解：// 在A(yíng)中刪除既在B中出現(xiàn)又在C中出現(xiàn)的元素，結(jié)果放在D中Status ListUnion_Sq(SqList amp。D,SqList amp。A,SqList amp。B,SqList amp。C){SqList Temp。InitList_Sq(Temp)。ListCross_L(B,C,Temp)。ListMinus_L(A,Temp,D)。} 。試對(duì)單鏈表編寫(xiě)算法，請(qǐng)釋放A表中的無(wú)用結(jié)點(diǎn)空間。解：// 在A(yíng)中刪除既在B中出現(xiàn)又在C中出現(xiàn)的元素，并釋放B、CStatus ListUnion_L(LinkList amp。A,LinkList amp。B,LinkList amp。C){ListCross_L(B,C)。ListMinus_L(A,B)。}// 求集合AB，結(jié)果放在A(yíng)表中，并刪除B表Status ListMinus_L(LinkList amp。A,LinkList amp。B){LinkList pa,pb,qa,qb,pt。pa=A。pb=B。qa=pa。 // 保存pa的前驅(qū)指針qb=pb。 // 保存pb的前驅(qū)指針pa=panext。pb=pbnext。while(paamp。amp。pb){if(pbdatapadata){pt=pb。pb=pbnext。qbnext=pb。free(pt)。}elseif(pbdatapadata){qa=pa。pa=panext。}else{pt=pa。pa=panext。qanext=pa。free(pt)。}}while(pb){pt=pb。pb=pbnext。qbnext=pb。free(pt)。}pb=B。free(pb)。return OK。} 假設(shè)某個(gè)單向循