2．算法設(shè)計題

（1）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中不允許有重復(fù)的數(shù)據(jù)。

[題目分析]

合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開始進行比較，當兩個鏈表La和Lb均為到達表尾結(jié)點時，依次摘取其中較小者重新鏈接在Lc表的最后。如果兩個表中的元素相等，只摘取La表中的元素，刪除Lb表中的元素，這樣確保合并后表中無重復(fù)的元素。當一個表到達表尾結(jié)點，為空時，將非空表的剩余元素直接鏈接在Lc表的最后。

[算法描述]

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)

{//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向

??pa=La->next;? pb=Lb->next;???

?? //pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點

?? Lc=pc=La;? //用La的頭結(jié)點作為Lc的頭結(jié)點

?? while(pa && pb)

{if(pa->data<pb->data){pc->next=pa;pc=pa;pa=pa->next;}

??? ?//取較小者La中的元素，將pa鏈接在pc的后面，pa指針后移

???? else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;}

????? //取較小者Lb中的元素，將pb鏈接在pc的后面，pb指針后移

???? else //相等時取La中的元素，刪除Lb中的元素

{pc->next=pa;pc=pa;pa=pa->next;

????? q=pb->next;delete pb ;pb =q;

}

?? ??}

?pc->next=pa?pa:pb;??? //插入剩余段

?? ??delete Lb;??????????? //釋放Lb的頭結(jié)點

}?

（2）將兩個非遞減的有序鏈表合并為一個非遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。

[題目分析]

合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開始進行比較，當兩個鏈表La和Lb均為到達表尾結(jié)點時，依次摘取其中較小者重新鏈接在Lc表的表頭結(jié)點之后，如果兩個表中的元素相等，只摘取La表中的元素，保留Lb表中的元素。當一個表到達表尾結(jié)點，為空時，將非空表的剩余元素依次摘取，鏈接在Lc表的表頭結(jié)點之后。

[算法描述]

void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, )

{//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向

? pa=La->next;? pb=Lb->next;

//pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點

? Lc=pc=La; //用La的頭結(jié)點作為Lc的頭結(jié)點

? Lc->next=NULL;

? while(pa||pb )

{//只要存在一個非空表，用q指向待摘取的元素

??? if(!pa)? {q=pb;? pb=pb->next;}

//La表為空，用q指向pb，pb指針后移

??? else if(!pb)? {q=pa;? pa=pa->next;}

//Lb表為空，用q指向pa，pa指針后移

??? else if(pa->data<=pb->data)? {q=pa;? pa=pa->next;}

//取較小者（包括相等）La中的元素，用q指向pa，pa指針后移

??? else {q=pb;? pb=pb->next;}

//取較小者Lb中的元素，用q指向pb，pb指針后移

???? q->next = Lc->next;? Lc->next = q;??

//將q指向的結(jié)點插在Lc 表的表頭結(jié)點之后

? ??}

? ??delete Lb;???????????? //釋放Lb的頭結(jié)點

}??

?

（3）已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請設(shè)計算法求出A與B的交集，并存放于A鏈表中。

[題目分析]

只有同時出現(xiàn)在兩集合中的元素才出現(xiàn)在結(jié)果表中,合并后的新表使用頭指針Lc指向。pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開始進行比較，當兩個鏈表La和Lb均為到達表尾結(jié)點時，如果兩個表中相等的元素時，摘取La表中的元素，刪除Lb表中的元素；如果其中一個表中的元素較小時，刪除此表中較小的元素，此表的工作指針后移。當鏈表La和Lb有一個到達表尾結(jié)點，為空時，依次刪除另一個非空表中的所有元素。

[算法描述]

void Mix(LinkList& La, LinkList& Lb, LinkList& Lc)

{? pa=La->next;pb=Lb->next;

pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點

Lc=pc=La; //用La的頭結(jié)點作為Lc的頭結(jié)點

while(pa&&pb)

{ if(pa->data==pb->data)∥交集并入結(jié)果表中。

?? { pc->next=pa;pc=pa;pa=pa->next;

???? u=pb;pb=pb->next; delete u;}

??else if(pa->data<pb->data) {u=pa;pa=pa->next; delete u;}

else {u=pb; pb=pb->next; delete u;}

}

while(pa) {u=pa; pa=pa->next; delete u;}∥ 釋放結(jié)點空間

while(pb) {u=pb; pb=pb->next; delete u;}∥釋放結(jié)點空間

pc->next=null;∥置鏈表尾標記。

delete Lb;? //釋放Lb的頭結(jié)點

?? }

（4）已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請設(shè)計算法求出兩個集合A和B 的差集（即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合），并以同樣的形式存儲，同時返回該集合的元素個數(shù)。

[題目分析]

求兩個集合A和B的差集是指在A中刪除A和B中共有的元素，即刪除鏈表中的相應(yīng)結(jié)點,所以要保存待刪除結(jié)點的前驅(qū)，使用指針pre指向前驅(qū)結(jié)點。pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開始進行比較，當兩個鏈表La和Lb均為到達表尾結(jié)點時，如果La表中的元素小于Lb表中的元素，pre置為La表的工作指針pa刪除Lb表中的元素；如果其中一個表中的元素較小時，刪除此表中較小的元素，此表的工作指針后移。當鏈表La和Lb有一個為空時，依次刪除另一個非空表中的所有元素。

[算法描述]

void Difference（LinkList& La, LinkList& Lb,int *n）

{∥差集的結(jié)果存儲于單鏈表La中，*n是結(jié)果集合中元素個數(shù)，調(diào)用時為0

pa=La->next; pb=Lb->next;?????

∥pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點

? pre=La;????????? ∥pre為La中pa所指結(jié)點的前驅(qū)結(jié)點的指針

??while（pa&&pb）

{if（pa->data<q->data）{pre=pa;pa=pa->next;*n++;}

∥ A鏈表中當前結(jié)點指針后移

else if（pa->data>q->data）q=q->next;???? ∥B鏈表中當前結(jié)點指針后移

?? ?else {pre->next=pa->next;????? ∥處理A，B中元素值相同的結(jié)點，應(yīng)刪除

????????? u=pa; pa=pa->next; delete u;}?? ∥刪除結(jié)點

}

}

（5）設(shè)計算法將一個帶頭結(jié)點的單鏈表A分解為兩個具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點為A表中值小于零的結(jié)點，而C表的結(jié)點為A表中值大于零的結(jié)點（鏈表A中的元素為非零整數(shù)，要求B、C表利用A表的結(jié)點）。

[題目分析]

B表的頭結(jié)點使用原來A表的頭結(jié)點，為C表新申請一個頭結(jié)點。從A表的第一個結(jié)點開始，依次取其每個結(jié)點p，判斷結(jié)點p的值是否小于0，利用前插法，將小于0的結(jié)點插入B表,大于等于0的結(jié)點插入C表。

[算法描述]

void DisCompose(LinkedList A)

{ ??B=A;

B->next= NULL;??? ∥B表初始化

?? ??C=new LNode;∥為C申請結(jié)點空間

???? C->next=NULL;???? ∥C初始化為空表

???? p=A->next;?????? ?∥p為工作指針

???? while(p!= NULL)

??? ?{ r=p->next;??? ??∥暫存p的后繼

?????? if(p->data<0)

????? ??{p->next=B->next; B->next=p; }∥將小于0的結(jié)點鏈入B表,前插法

?????? else {p->next=C->next; C->next=p; }∥將大于等于0的結(jié)點鏈入C表,前插法

?????? p=r;∥p指向新的待處理結(jié)點。

???? }

}

?

（6）設(shè)計一個算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點。

[題目分析]

假定第一個結(jié)點中數(shù)據(jù)具有最大值，依次與下一個元素比較，若其小于下一個元素，則設(shè)其下一個元素為最大值，反復(fù)進行比較，直到遍歷完該鏈表。

[算法描述]

ElemType Max (LinkList L ){

if(L->next==NULL) return NULL;

pmax=L->next; //假定第一個結(jié)點中數(shù)據(jù)具有最大值

p=L->next->next;

while(p != NULL ){//如果下一個結(jié)點存在

??? if(p->data > pmax->data) pmax=p;//如果p的值大于pmax的值，則重新賦值

??? p=p->next;//遍歷鏈表

}

return pmax->data;

（7）設(shè)計一個算法，通過遍歷一趟，將鏈表中所有結(jié)點的鏈接方向逆轉(zhuǎn)，仍利用原表的存儲空間。

[題目分析]

從首元結(jié)點開始，逐個地把鏈表L的當前結(jié)點p插入新的鏈表頭部。

[算法描述]

void? inverse(LinkList &L)

{// 逆置帶頭結(jié)點的單鏈表 L

??? p=L->next;? L->next=NULL;

??? while ( p) {

??????? q=p->next;??? // q指向*p的后繼

??????? p->next=L->next;

??????? L->next=p;?????? // *p插入在頭結(jié)點之后

??????? p = q;

??? }

}

（8）設(shè)計一個算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素（mink和maxk是給定的兩個參數(shù)，其值可以和表中的元素相同，也可以不同 ）。

[題目分析]

分別查找第一個值>mink的結(jié)點和第一個值 ≥maxk的結(jié)點，再修改指針，刪除值大于mink且小于maxk的所有元素。

[算法描述]

void delete(LinkList &L, int mink, int maxk) {

?? p=L->next; //首元結(jié)點

?? while (p && p->data<=mink)

????? { pre=p;? p=p->next; } //查找第一個值>mink的結(jié)點

?? if (p)

{while (p && p->data<maxk)? p=p->next;

????????????????????? // 查找第一個值 ≥maxk的結(jié)點

????? q=pre->next;?? pre->next=p;? // 修改指針

????? while (q!=p)

???????? { s=q->next;? delete q;? q=s; } // 釋放結(jié)點空間

?? }//if

}

（9）已知p指向雙向循環(huán)鏈表中的一個結(jié)點，其結(jié)點結(jié)構(gòu)為data、prior、next三個域，寫出算法change(p),交換p所指向的結(jié)點和它的前綴結(jié)點的順序。

[題目分析]

知道雙向循環(huán)鏈表中的一個結(jié)點，與前驅(qū)交換涉及到四個結(jié)點（p結(jié)點，前驅(qū)結(jié)點，前驅(qū)的前驅(qū)結(jié)點，后繼結(jié)點）六條鏈。

[算法描述]

void ?Exchange（LinkedList p）

∥p是雙向循環(huán)鏈表中的一個結(jié)點，本算法將p所指結(jié)點與其前驅(qū)結(jié)點交換。

{q=p->llink；

?q->llink->rlink=p；?? ∥p的前驅(qū)的前驅(qū)之后繼為p

?p->llink=q->llink；? ?∥p的前驅(qū)指向其前驅(qū)的前驅(qū)。

?q->rlink=p->rlink；?? ∥p的前驅(qū)的后繼為p的后繼。

?q->llink=p；????????? ∥p與其前驅(qū)交換

?p->rlink->llink=q；?? ∥p的后繼的前驅(qū)指向原p的前驅(qū)

?p->rlink=q；????????? ∥p的后繼指向其原來的前驅(qū)

}∥算法exchange結(jié)束。

（10）已知長度為n的線性表A采用順序存儲結(jié)構(gòu)，請寫一時間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。

[題目分析]

在順序存儲的線性表上刪除元素，通常要涉及到一系列元素的移動（刪第i個元素，第i+1至第n個元素要依次前移）。本題要求刪除線性表中所有值為item的數(shù)據(jù)元素，并未要求元素間的相對位置不變。因此可以考慮設(shè)頭尾兩個指針（i=1，j=n），從兩端向中間移動，凡遇到值item的數(shù)據(jù)元素時，直接將右端元素左移至值為item的數(shù)據(jù)元素位置。

[算法描述]

void? Delete（ElemType A[ ]，int? n）

∥A是有n個元素的一維數(shù)組，本算法刪除A中所有值為item的元素。

{i=1；j=n；∥設(shè)置數(shù)組低、高端指針（下標）。

?while（i<j）

?? {while（i<j && A[i]!=item）i++；???????? ∥若值不為item，左移指針。

??? if（i<j）while（i<j && A[j]==item）j--；∥若右端元素為item，指針左移

??? if（i<j）A[i++]=A[j--]；}