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

　　 試寫一算法對單鏈表實現就地逆置

　　解

　　// 帶頭結點的單鏈表的逆置

　　Status ListOppose_L(LinkList &L)

　　{

　　LinkList pq;

　　p=L;

　　p=p>next;

　　L>next=NULL;

　　while(p){

　　q=p;

　　p=p>next;

　　q>next=L>next;

　　L>next=q;

　　}

　　return OK;

　　}

　　 假設有兩個按元素值遞增有序排列的線性表A和B均以單鏈表作存儲結構請編寫算法將A表和B表歸並成一個按元素值遞減有序（即非遞增有序允許表中含有值相同的元素）排列的線性表C並要求利用原表（即A表和B表）的結點空間構造C表

　　解

　　// 將合並逆置後的結果放在C表中並刪除B表

　　Status ListMergeOppose_L(LinkList &ALinkList &BLinkList &C)

　　{

　　LinkList papbqaqb;

　　pa=A;

　　pb=B;

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

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

　　pa=pa>next;

　　pb=pb>next;

　　A>next=NULL;

　　C=A;

　　while(pa&&pb){

　　if(pa>data<pb>data){

　　qa=pa;

　　pa=pa>next;

　　qa>next=A>next;//將當前最小結點插入A表表頭

　　A>next=qa;

　　}

　　else{

　　qb=pb;

　　pb=pb>next;

　　qb>next=A>next;//將當前最小結點插入A表表頭

　　A>next=qb;

　　}

　　}

　　while(pa){

　　qa=pa;

　　pa=pa>next;

　　qa>next=A>next;

　　A>next=qa;

　　}

　　while(pb){

　　qb=pb;

　　pb=pb>next;

　　qb>next=A>next;

　　A>next=qb;

　　}

　　pb=B;

　　free(pb);

　　return OK;

　　}

　　 假設以兩個元素依值遞增有序排列的線性表A和B分別表示兩個集合（即同一表中的元素值各不相同）現要求另辟空間構成一個線性表C其元素為A和B中元素的交集且表C中的元素有依值遞增有序排列試對順序表編寫求C的算法

　　解

　　// 將AB求交後的結果放在C表中

　　Status ListCross_Sq(SqList &ASqList &BSqList &C)

　　{

　　int i=j=k=;

　　while(i<Alength && j<Blength){

　　if(Aelem[i]<Belem[j])i++;

　　else

　　if(Aelem[i]>Belem[j])j++;

　　else{

　　ListInsert_Sq(CkAelem[i]);

　　i++;

　　k++;

　　}

　　}

　　return OK;

　　}

[]  []  []  

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