d02-2011線性表習(xí)題課

線性表習(xí)題編程題1編寫一算法，實(shí)現(xiàn)單鏈表的原地置逆。即利用原來的結(jié)點(diǎn)將線性表L=（a1,a2,……,an）變換為：L

=（

an, ……

,

a2,

a1）第2

頁La1a2a3線性表習(xí)題編程題1succ

p標(biāo)志后繼結(jié)點(diǎn)（*succ）；修改指針（將*p

在頭結(jié)點(diǎn)之后）；重置結(jié)點(diǎn)*p（p重新指向原表中后繼）；第3

頁線性表習(xí)題void inverse(

LinkList

&L

){ //

逆置

結(jié)點(diǎn)的單鏈表

Lp

=

L->next;

L->next

=

NULL;while

(

p

!=

NULL

){ succ=p->next;

//succ指向

*p

的后繼在頭結(jié)點(diǎn)之后p->next

=

L->next;L->next

=

p; //

*pp

=

succ;}}第4

頁線性表習(xí)題第5

頁編程題2將兩個(gè)非遞減有序的有序單鏈表la和lb歸并為非遞增的有序表。Typedef

struct LNode

{intstruct

Lnodedata;*next;//數(shù)據(jù)域//指針域}

LNode,

*LinkList;LinkList

la,

lb；//單鏈表的頭指針請用la

和lb

中的結(jié)點(diǎn)合并生成一個(gè)新的非遞增的有序單鏈表lc。合并完成后，原來的la

和lb

成為空鏈表。線性表習(xí)題操作步驟建空表Lc;依次從La

或Lb

中“”元素值較小的4)結(jié)點(diǎn)

到

Lc表中第一個(gè)結(jié)點(diǎn)之前直至其中一個(gè)表變空為止;3)

繼續(xù)將La

或Lb

其中一個(gè)表的剩余結(jié)點(diǎn)插入在Lc

表的表頭結(jié)點(diǎn)之后;La

表和Lb

表的表頭結(jié)點(diǎn)。第6

頁線性表習(xí)題void

union

(

LinkList&

Lc,

LinkList&

La,

LinkList&

Lb

){//將非遞減的有序表La

和Lb歸并為非遞增的//有序表Lc,歸并之后，La和Lb表不再存在。//

上述三個(gè)表均為

結(jié)點(diǎn)的單鏈表，Lc

表//中的結(jié)點(diǎn)即為原

La

或Lb

表中的結(jié)點(diǎn)。Lc

=

new

LNode;

Lc->next

=

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

//初始化……

……

//歸并dele

a;

dele

b;

//}//unionLa

和Lb的頭結(jié)點(diǎn)第7

頁線性表習(xí)題while

(

pa

!=

NULL

||

pb

!=

NULL

){

if (

pa

==NULL

){

q

=

pb; pb

=

pb->next;

}elseif (

pb

==NULL

){

q

=

pa; pa

=

pa->next;}else

if

(

pa->data

<=

pb->data

){

q

=

pa; pa

=

pa->next;}else{

q

=

pb; pb

=

pb->next;

}q->next

=

Lc->next;

//Lc->next

=

q;}第8

頁線性表習(xí)題已知一帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)為如下：第9

頁假設(shè)該鏈表只給出了頭指針

list。在不改變鏈表的前提下，請?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)（k為正整數(shù)）。若查找成功，輸出該結(jié)點(diǎn)的data的值，并返回1；否則，返回

0。datalink線性表習(xí)題問題關(guān)鍵如何盡可能高效？常規(guī)算法對鏈表進(jìn)行第一遍掃描，計(jì)算出鏈表的長度

len，然后進(jìn)行第二遍掃描，計(jì)數(shù)到len-k的位置即為需要查找的倒數(shù)第k

個(gè)元素。算法時(shí)間復(fù)雜度：O(n)。問題：是否有更高效的算法能否只進(jìn)行一遍掃描即可完成？第10

頁線性表習(xí)題算法的基本設(shè)計(jì)思想假設(shè)鏈表的最后一個(gè)結(jié)點(diǎn)為倒數(shù)第1

個(gè)結(jié)點(diǎn)。對鏈表進(jìn)行掃描：用指針p

和q

分別指向兩個(gè)結(jié)點(diǎn)，且保持指針p

和指針q

之間的“距離”（包含的結(jié)點(diǎn)數(shù)）為k，當(dāng)p

指向最后一個(gè)結(jié)點(diǎn)時(shí)，q

指向的就是倒數(shù)第k

個(gè)結(jié)點(diǎn)。第11

頁線性表習(xí)題算法的詳細(xì)實(shí)現(xiàn)步驟假表頭指針為list，兩個(gè)指針變量p

和q：

距離計(jì)數(shù)器count

=0；p=q=list->link，指向鏈表第一個(gè)數(shù)據(jù)結(jié)點(diǎn)；若p

非空，則執(zhí)行③和④；否則，轉(zhuǎn)⑤；

如果count

小于k，則count

=count

+1；否則q

指向下一個(gè)結(jié)點(diǎn)；p

指向下一個(gè)結(jié)點(diǎn)，轉(zhuǎn)步驟②；

若count

等于k，則查找成功，輸出q

結(jié)點(diǎn)的data值，返回1；否則，返回0。結(jié)束。第12

頁線性表習(xí)題第13

頁int SearchRevk(

pLinkList

list, intk)intcount; /*

距離計(jì)數(shù)器*//*

p和q指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/{

pLinkList p,

q;p=q

=

list->link;count

=

0;while

(

p!=

NULL

){

if

(count<k)

count++; /*

計(jì)數(shù)器+1

*/elsep

=p->

link;q=q->link; /*

q指向下一結(jié)點(diǎn)*//*

p指向下一個(gè)結(jié)點(diǎn)*/}if

(count==k) /*查找成功

*/{

printf("%d\n",

q->data); return

1;}else

return

0; /*

查找失敗*/}線性表習(xí)題求循環(huán)小數(shù)對于任意的真分?jǐn)?shù)N/M

(0<N<M<500)，均可以求出對應(yīng)的小數(shù)。如果采用鏈表表示各個(gè)小數(shù)，對于循環(huán)節(jié)采用循環(huán)鏈表表示。head11/8=

0.125形式2∧5.

.0.

6125

（循環(huán)節(jié)125）形式5261head第14

頁線性表習(xí)題算法設(shè)計(jì)模擬手工計(jì)算過程。關(guān)鍵：記錄計(jì)算過程中的余數(shù)和對應(yīng)的商，一旦發(fā)現(xiàn)余數(shù)出現(xiàn)重復(fù)，則找到循環(huán)節(jié)。算法實(shí)現(xiàn)動(dòng)態(tài)申請有M個(gè)元素的指針數(shù)組：以每次求得的余數(shù)作為下標(biāo)，對應(yīng)的數(shù)組元素保存該余數(shù)對應(yīng)的商。第15

頁線性表習(xí)題第16

頁void

change(int

n,

int

m,

NODE

*

head

){ NODE

*

*

array; NODE

*

p=head; intk;array=(NODE

**)malloc(sizeof(NODE

*

)*

m);

for(k=0;k<m;k++)

//建立保存余數(shù)的數(shù)組array[k] =NULL;while

(n!=0)

//余數(shù)不為0，則繼續(xù)循環(huán){

if

(n*10%m==0)

//若能夠整除，則處理，結(jié)束{

p->next=

(NODE

*)

malloc(

sizeof(NODE)

);p->next->data

=

n*10

/m;p->next->next

=

NULL;n=

0;}else

{

處理一般情況}}}線性表習(xí)題第17

頁else{

if

(array[n]==NULL)

//若該余數(shù)第一次出現(xiàn){

array[n]=p->next=(NODE

*)malloc(sizeof(NODE));

p->next->data=n

*

10/m;

//保存商n=n*

10%m;

//余數(shù)擴(kuò)大10倍p

=

p->next;}else

//該余數(shù)不是第一次出現(xiàn)，則發(fā)現(xiàn)循環(huán)節(jié){

p->next=array[n];

//建立環(huán)n

=0;}}線性表習(xí)題求循環(huán)節(jié)編寫一個(gè)盡可能高效的查找循環(huán)節(jié)起始點(diǎn)的函數(shù)：NODE

*

find(

NODE

*

head)。函數(shù)的返回值為循環(huán)節(jié)的起點(diǎn)（即圖中的指針p）。head11/8=

0.125形式2∧5.

.0.

6125

（循環(huán)節(jié)125）形式5261head第18

頁線性表習(xí)題第19

頁算法設(shè)計(jì)關(guān)鍵是要找出高效算法。判斷是否有環(huán)。在確認(rèn)有環(huán)的情況下，找到環(huán)的開始。線性表習(xí)題第20

頁NODE

*

find(

NODE

*

head,

int

*

n

){ int

count=0,

ring; NODE

*

p,

*q;p

=

q=

head->next;while

(

p!=NULL&&

q!=NULL){ count

++;//p指針一次走一步p

=

p->next;q

=

q->next;if

(q!=NULL

)if

(p==q)//q指針一次走兩步q=q->next;break;

//找到重合點(diǎn)則退出}if

(

q

==

NULL)//如果不存在環(huán)則返回{ *n

=0;return

NULL;}線性表習(xí)題第21

頁ring

=

1;while

(q->next

!=p

)//求環(huán)長{ q

=

q->next; ring

++;}count

=

0; q

=

p

=

head->next;while(count<ring)

//求環(huán)的起始點(diǎn){ count

++; p

=

p->next;}while

(p!=q){ p

=

p->next; q

=

q->next;}*n

=ring;returnp;}線性表習(xí)題將n(n>1)個(gè)整數(shù)存放到一維數(shù)組R中。試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能高效的算法，將R

中保有的序列循環(huán)左移p（0﹤p﹤n）個(gè)位置，即將R中的數(shù)據(jù)由：(x0,

x1,…,xp-1,xp,xp+1,…,xn-1)變換為：(xp,xp+1,……,xn-1,x0,x1,……,xp-1)第22

頁線性表習(xí)題問題關(guān)鍵如何盡可能高效？常規(guī)算法一般的循環(huán)左移算法的時(shí)間復(fù)雜度肯定是比較大的。的法：采用一個(gè)變量作為輔助空間，每次移動(dòng)一位，反復(fù)進(jìn)行移動(dòng)K次，則時(shí)間復(fù)雜度為O(

n*k)。另一種算法是采用p

位輔助空間，空間復(fù)雜度O(

p)，時(shí)間復(fù)雜度O(

n+p)。第23

頁線性表習(xí)題第24

頁基本設(shè)計(jì)思想先將前面p個(gè)元素置反，再將后邊n-p元素置反，最后整體置反。參考程序void

leftShift(

int

r[

],

int

n,

int

p){ if

(

p>0

&&

p<n

){

rever(r,

0,

n-1);rever(r,

0,

n-p-1);rever(r,

n-p,

n-1);}}線性表習(xí)題void

rever(

int

a[

],

int

left,

int

right

){

int k=lift,

j=right,

temp;while

(

k

<

j

){ temp

=

r[k];r[k]

=

r[j];r[j]

=

temp;k++;j--;}}算法時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。第25

頁線性表習(xí)題第26

頁本題曾經(jīng)出現(xiàn)在《編程珠璣》中?；舅枷霃牡趎個(gè)元素開始移位，將它直接移到第n-p位，然后再對第n-p位操作，依次類推n-2p，n-3p.....；上述移位操作經(jīng)過一定次數(shù)后，必定又重新對第n位操作，此時(shí)完成了一次循環(huán)；例如，當(dāng)n=6，p=2時(shí)，先將第6位移到第4

位，第4

位移到第2位，第2位移到第

6

位，循環(huán)一次，此時(shí)一次循環(huán)未能將數(shù)組移位完畢。當(dāng)n=6，p=5

時(shí)，6->1；1->2；

2->3；3->4；4->5；5->6；此時(shí)一次循環(huán)即將整個(gè)數(shù)組移位完畢。線性表習(xí)題基本思想當(dāng)一次循環(huán)不能將整個(gè)數(shù)組完全移位時(shí)，可從第n-1位，再進(jìn)行第（1）步的操作；如果還沒移完，繼續(xù)從第n-2位開始循環(huán)，依次類推。現(xiàn)在的關(guān)鍵之處是移動(dòng)需要多少次循環(huán)。由數(shù)論性質(zhì)可知：a.當(dāng)n

和p的最大公約數(shù)（記為(n,p)）為1時(shí)，一次循環(huán)必定將整個(gè)數(shù)組移動(dòng)完畢。b.

當(dāng)

n

和

p

的最大公約數(shù)（記為

(

n,

p

)）大于

1時(shí)，則需要的循環(huán)次數(shù)就是

(n,p)！如

n=6，p=2，

(6,

2)

=2，第一次循環(huán)從第

6

位開始，第二次循環(huán)從第5

位開始，兩次后完成！第27

頁線性表習(xí)題定義：一個(gè)長度為L（L≥1）的升序序列S，處在第L/2

個(gè)位置的數(shù)稱為S的中位數(shù)。

例如，若序列S1=(11,13,15,17,19)，則S1

的中位數(shù)是15。兩個(gè)序列的中位數(shù)是含它們所有元素的升序

序列的中位數(shù)。例如，若S2=(2,4,6,8,20)，則S1

和S2

的中位數(shù)是11?，F(xiàn)有兩個(gè)等長升序序列A和B，設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能高效的算法，找出兩個(gè)序列A

和B

的中位數(shù)。第28

頁線性表習(xí)題較小者即為所求的中位數(shù)。第29

頁基本設(shè)計(jì)思想分別求兩個(gè)升序序列A、B的中位數(shù)，設(shè)為a和b。求中位數(shù)的過程如下：若a=b，則a或b即為所求的中位數(shù)，結(jié)束；若a<b，則舍棄A中較小一半，同時(shí)舍棄B中較大一半，要求兩次舍棄的元素個(gè)數(shù)相同。若a>b，則舍棄A中較大一半，同時(shí)舍棄B中較小一半，要求兩次舍棄的元素個(gè)數(shù)相同。在保留的兩個(gè)升序序列中，重復(fù)上述過程，直到兩個(gè)序列中均只含1

個(gè)元素時(shí)為止，則線性表習(xí)題}第30

頁基本設(shè)計(jì)思想int

M_Search

(intA[],

intB[],intn){ int

start1,

end1,

mid1,

start2,

end2,

mid2;start1=

0;end1=

n-1; start2

=

0;

end2=

n-1;while (

start1!=

end1

||start2

!=end2

){ mid1