數據結構與算法線性表復習習題【6】[1]

　　 已知AB和C為三個遞增有序的線性表現要求對A表作如下操作刪去那些既在B表中出現又在C表中出現的元素試對順序表編寫實現上述操作的算法並分析你的算法的時間復雜度（注意題中沒有特別指明同一表中的元素值各不相同）

　　解

　　// 在A中刪除既在B中出現又在C中出現的元素結果放在D中

　　Status ListUnion_Sq(SqList &DSqList &ASqList &BSqList &C)

　　{

　　SqList Temp;

　　InitList_Sq(Temp);

　　ListCross_L(BCTemp);

　　ListMinus_L(ATempD);

　　}

　　 要求同題試對單鏈表編寫算法請釋放A表中的無用結點空間

　　解

　　// 在A中刪除既在B中出現又在C中出現的元素並釋放BC

　　Status ListUnion_L(LinkList &ALinkList &BLinkList &C)

　　{

　　ListCross_L(BC);

　　ListMinus_L(AB);

　　}

　　// 求集合AB結果放在A表中並刪除B表

　　Status ListMinus_L(LinkList &ALinkList &B)

　　{

　　LinkList papbqaqbpt;

　　pa=A;

　　pb=B;

　　qa=pa;// 保存pa的前驅指針

　　qb=pb;// 保存pb的前驅指針

　　pa=pa>next;

　　pb=pb>next;

　　while(pa&&pb){

　　if(pb>data<pa>data){

　　pt=pb;

　　pb=pb>next;

　　qb>next=pb;

　　free(pt);

　　}

　　else

　　if(pb>data>pa>data){

　　qa=pa;

　　pa=pa>next;

　　}

　　else{

　　pt=pa;

　　pa=pa>next;

　　qa>next=pa;

　　free(pt);

　　}

　　}

　　while(pb){

　　pt=pb;

　　pb=pb>next;

　　qb>next=pb;

　　free(pt);

　　}

　　pb=B;

　　free(pb);

　　return OK;

　　}

　　 假設某個單向循環鏈表的長度大於且表中既無頭結點也無頭指針已知s為指向鏈表中某個結點的指針試編寫算法在鏈表中刪除指針s所指結點的前驅結點

　　解

　　// 在單循環鏈表S中刪除S的前驅結點

　　Status ListDelete_CL(LinkList &S)

　　{

　　LinkList pq;

　　if(S==S>next)return ERROR;

　　q=S;

　　p=S>next;

　　while(p>next!=S){

　　q=p;

　　p=p>next;

　　}

　　q>next=p>next;

　　free(p);

　　return OK;

　　}

[]  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23386.html