第一講 線性表

1、計算機的基本工作方式l將編好的程序和原始數(shù)據(jù)，輸入并存儲在將編好的程序和原始數(shù)據(jù)，輸入并存儲在計算機的內(nèi)存儲器中（即計算機的內(nèi)存儲器中（即“存儲程序存儲程序”）；）；l計算機按照程序逐條取出指令加以分析，計算機按照程序逐條取出指令加以分析，并執(zhí)行指令規(guī)定的操作（即并執(zhí)行指令規(guī)定的操作（即“程序控制程序控制”）。）。l這一原理稱為這一原理稱為存貯程序存貯程序和和程序控制程序控制,是現(xiàn)代是現(xiàn)代計算機的基本工作方式。計算機的基本工作方式。程序程序是計算機的靈魂是計算機的靈魂什么是數(shù)據(jù)結(jié)構(gòu)（什么是數(shù)據(jù)結(jié)構(gòu)（data structure）什么是算法（什么是算法（algorithm）程序程序=數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)

2、結(jié)構(gòu)+算法算法是數(shù)據(jù)在計算機中的組織方式及相應(yīng)的基本訪問操作。是解決問題的方法（數(shù)據(jù)處理）或者步驟程序是什么？001高等數(shù)學(xué)樊映川S01002理論力學(xué)羅遠祥L01003高等數(shù)學(xué)華羅庚S01004線性代數(shù)欒汝書S02線性表圖書館書目表數(shù)據(jù)元素計算機和人對奕問題計算機和人對奕問題樹樹.網(wǎng)絡(luò)布線網(wǎng)絡(luò)布線圖圖三種基本數(shù)據(jù)結(jié)構(gòu)l線性結(jié)構(gòu)線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對數(shù)據(jù)元素之間存在一對一的線性關(guān)系一的線性關(guān)系l樹形結(jié)構(gòu)樹形結(jié)構(gòu)數(shù)據(jù)元素之間存在一對數(shù)據(jù)元素之間存在一對多的層次關(guān)系多的層次關(guān)系l圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)數(shù)據(jù)元素之間存在多對數(shù)據(jù)元素之間存在多對多的網(wǎng)狀關(guān)系多的網(wǎng)狀關(guān)系問題問題歸并兩個有序線性表。歸并兩個

3、有序線性表。如：將下列兩個有序線性表進行歸并：如：將下列兩個有序線性表進行歸并：線性表（線性表（1 1）是：）是：33，5 5，8 8，1111，1313線性表（線性表（2 2）是：）是：11，4 4，5 5，9 9，1515問題問題2 2：歸并后的線性表為：歸并后的線性表為：11，3 3，4 4，5 5，8 8，9 9，1111，1313，1515問題問題1 1：歸并后的線性表為：歸并后的線性表為：11，3 3，4 4，5 5，5 5，8 8，9 9，1111，1313，1515順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)數(shù)據(jù)在計算機中如何存儲？數(shù)據(jù)在計算機中如何存儲？元素元素n n.元素元素i i.元素元素2

4、 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲地址存儲內(nèi)容存儲內(nèi)容Loc(元素元素i)=Lo+（i-1)*m順順序序存存儲儲M：每個元素占用的存儲單元元素元素2 2元素元素1 1元素元素3 3 元素元素4 4 鏈式存儲鏈式存儲 head13451400153613461400153613461、數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)之間有怎樣的關(guān)系？之間有怎樣的關(guān)系？討論：討論：2、從兩種結(jié)構(gòu)看如何組織數(shù)據(jù)？、從兩種結(jié)構(gòu)看如何組織數(shù)據(jù)？ 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的基本運算：查找、插入、刪除數(shù)據(jù)結(jié)構(gòu)的基本

5、運算：查找、插入、刪除 線性結(jié)構(gòu)線性結(jié)構(gòu) 順序存儲順序存儲 鏈式存儲鏈式存儲 樹形結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)小結(jié)：數(shù)據(jù)結(jié)構(gòu)的三個方面：小結(jié)：數(shù)據(jù)結(jié)構(gòu)的三個方面：鏈式結(jié)構(gòu)鏈式結(jié)構(gòu)什么是指針什么是指針指針是以存儲單元的地址作為其值的一種指針是以存儲單元的地址作為其值的一種數(shù)據(jù)類型。數(shù)據(jù)類型。 100 p1p13434F2F23434F2F2定義方式：定義方式：Type Type 指針類型標識符指針類型標識符=類型標識符；類型標識符； var var 指針變量名：指針類型標識符；指針變量名：指針類型標識符；newnew（p1p1） 向計算機申請內(nèi)存地址向計算機申請內(nèi)存地址 鏈式結(jié)構(gòu)鏈式結(jié)構(gòu)如何申請

6、、釋放存儲單元如何申請、釋放存儲單元 p1p13434F2F23434F2F2typetype point=integer; point=integer;var var p1:point;p1:point;p1:=200p1:=200 給給p1p1指向的單元賦值指向的單元賦值dispose(p1) 釋放存儲單元釋放存儲單元200200 p1:integer;arrpoint = array1.10 of real；Type point=integer; arr=array1.4 of char; arrpoint = arr; Var p1:point; p2:arrpoint;指針變量所指向

7、的類型不同，指針變量所指向的類型不同，計算機所給予的存儲單元的多計算機所給予的存儲單元的多少也不相同。少也不相同。指針類型定義中的基類型只能指針類型定義中的基類型只能是類型標識符，不能是具體的是類型標識符，不能是具體的類型定義。類型定義。 p1p1 p2p2i鏈式結(jié)構(gòu)鏈式結(jié)構(gòu)什么是指針什么是指針 begin begin new(p1);p1:=100; new(p1);p1:=100; new(p2);p2:=200; new(p2);p2:=200; p1:=p2; p1:=p2; end. end.30103011402040214022402340243011p14024p24024p1

8、 (1) (1) 同一基類型的指針變量可以互相賦值。同一基類型的指針變量可以互相賦值。鏈式結(jié)構(gòu)鏈式結(jié)構(gòu)指針變量的基本操作指針變量的基本操作(2)(2)指針變量指針變量p1p1置空置空 （nilnil）當(dāng)希望某個指針變量不指向任何存貯空間時，可以當(dāng)希望某個指針變量不指向任何存貯空間時，可以賦值為空即賦值為空即 NIL NIL 。(3)對指針變量可以進行關(guān)系運算對指針變量可以進行關(guān)系運算 如如:if P1P2 then 語句語句1 else 語句語句2; while P3 NIL do . . end; 關(guān)系運算的結(jié)果關(guān)系運算的結(jié)果,仍是仍是 FALSE , TRUE 。鏈式結(jié)構(gòu)鏈式結(jié)構(gòu)指針變量的

9、基本操作指針變量的基本操作Type pppp= stu ; stu= record name : string10 ; number : integer ; next:pppp； end; var p1, p2 : pppp鏈式結(jié)構(gòu)鏈式結(jié)構(gòu)數(shù)據(jù)元素的定義數(shù)據(jù)元素的定義p2.numberp2.numberp2.nextp2.next元素元素2 2元素元素1 1元素元素3 3 元素元素4 41345h

10、ead140015361346140015361346將獨立的多個存儲單元連接在一起，形成了一個將獨立的多個存儲單元連接在一起，形成了一個“鏈鏈”，鏈中每一個單元稱為鏈中每一個單元稱為“鏈鏈”中的一個中的一個“數(shù)據(jù)元素數(shù)據(jù)元素”。我。我們將它們通過指針域連在一起形成的鏈，稱為線性鏈表。們將它們通過指針域連在一起形成的鏈，稱為線性鏈表。 （1 1）查找結(jié)點）查找結(jié)點 （2 2）插入結(jié)點）插入結(jié)點 （3 3）刪除結(jié)點）刪除結(jié)點 鏈表的三種應(yīng)用模式：鏈表的三種應(yīng)用模式：線性鏈表線性鏈表查找查找(1)(1)設(shè)臨時工作變量設(shè)臨時工作變量p p指針指向鏈表的頭結(jié)點指針指向鏈表的頭結(jié)點( (頭結(jié)點頭結(jié)點的地

11、址不能丟失和改變，的地址不能丟失和改變，否則會丟失整個鏈表否則會丟失整個鏈表);); p:=head; p:=head;(2)while pnil do (2)while pnil do begin begin If x=p.data then 相關(guān)操作相關(guān)操作 p:=p.next;p:=p.next; end; end;n表頭插入 n表中插入n表尾插入new(s);readlnnew(s);readln(x);s.data:=x; s.next:=head; head:=s(x);s.data:=x; s.next:=head; head:=s；headpsnilx表頭插入這兩步操作這兩步操

12、作順序能顛倒順序能顛倒嗎？為什么？嗎？為什么？將將s s結(jié)點插在結(jié)點插在p p結(jié)點之后結(jié)點之后線性鏈表線性鏈表插入插入三種情況：三種情況：想一想：表中插入結(jié)點如何實現(xiàn)？想一想：表中插入結(jié)點如何實現(xiàn)？new(s);readlnnew(s);readln(x);s.data:=x; s.next:=head; head:=s(x);s.data:=x; s.next:=head; head:=sn表頭插入 n表中插入n表尾插入 new(s);readln new(s);readln(x);s.data:=x;s.next:=p.next; p.next:=s(x);s.data:=x;s.next

13、:=p.next; p.next:=sheadpsnilx表中插入將將s s結(jié)點插在結(jié)點插在p p結(jié)點之后結(jié)點之后線性鏈表線性鏈表插入插入 表尾插入結(jié)點又如何實現(xiàn)呢？表尾插入結(jié)點又如何實現(xiàn)呢？nil new(s);readln new(s);readln(x);s.data:=x;s.next:=p.next;p.next:=s(x);s.data:=x;s.next:=p.next;p.next:=snew(s);readlnnew(s);readln(x);s.data:=x; s.next:=head; head:=s(x);s.data:=x; s.next:=head; head:=

14、s將將s s結(jié)點插在結(jié)點插在p p結(jié)點之后結(jié)點之后n表頭插入 n表中插入n表尾插入 new(s);readln new(s);readln(x);s.data:=x;s.next:=nil; p.next:=s(x);s.data:=x;s.next:=nil; p.next:=sheadpsx表尾插入nil線性鏈表線性鏈表插入插入表頭刪除：表頭刪除：表中刪除：表中刪除：表尾刪除：表尾刪除：p:=head;r:=p.next;p.next:=r.next; dispose(r);表頭刪除表頭刪除headnilrp三種情況：三種情況：刪除刪除p結(jié)點后的結(jié)點后的r結(jié)點結(jié)點線性鏈表線性鏈表刪除刪除表

15、頭刪除：表頭刪除：表中刪除：表中刪除：表尾刪除：表尾刪除：p:=head;r:=p.next;p.next:=r.next; dispose(r);r:=p.next;p.next:=r.next; dispose(r);表中刪除表中刪除headnilrp線性鏈表線性鏈表刪除刪除刪除刪除p結(jié)點后的結(jié)點后的r結(jié)點結(jié)點表頭刪除：表頭刪除：表中刪除：表中刪除：表尾刪除：表尾刪除：p:=head;r:=p.next;p.next:=r.next;dispose(r);r:=p.next;p.next:=r.next; dispose(r);r:=p.next;p.next:=nil; dispose(

16、r);表尾刪除表尾刪除headnilrpnil線性鏈表線性鏈表刪除刪除刪除刪除p結(jié)點后的結(jié)點后的r結(jié)點結(jié)點（1 1）怎樣建立鏈表？怎樣建立鏈表？（2 2）應(yīng)該注意什么？）應(yīng)該注意什么？討論：討論：輸入一個正整數(shù)序列輸入一個正整數(shù)序列, ,遇遇0 0時停止，按輸入數(shù)據(jù)的時停止，按輸入數(shù)據(jù)的順序建立如下鏈表順序建立如下鏈表: :（從表頭插入結(jié)點）（從表頭插入結(jié)點） （1 1）初始化）初始化（2 2）申請一個結(jié)點并賦值，然后將結(jié)點插入表頭）申請一個結(jié)點并賦值，然后將結(jié)點插入表頭（3 3）重復(fù)（）重復(fù)（2 2），直到輸入的值為等于），直到輸入的值為等于0 0結(jié)束。結(jié)束。分析：分析：實戰(zhàn)演練實戰(zhàn)演練 r

17、eadln(n) ; head:=nil; while n 0 do插入表頭插入表頭,形成鏈表形成鏈表 begin new ( p ) ; p.data:=n; p.next:=head; head:= p ; read ( n ) ; end ; 參考程序：參考程序：討論討論（1）這樣插入的鏈表有什么特點？）這樣插入的鏈表有什么特點？（2）可以用表尾插入來改變鏈表）可以用表尾插入來改變鏈表結(jié)點的順序嗎？程序怎樣完成？結(jié)點的順序嗎？程序怎樣完成？ head:=nil; read(x); while x0 do begin if head=nil then begin new(p); p.dat

18、a:=x;p.next:=nil; q:=p; head:=p end else begin new(p); p.data:=x;pnext:=nil; q.next:=p; q:=p; end; read(x); end; head線性鏈表應(yīng)用的三種模式：線性鏈表應(yīng)用的三種模式： （1）數(shù)據(jù)元素的查找數(shù)據(jù)元素的查找 （2）數(shù)據(jù)元素的插入數(shù)據(jù)元素的插入 （3）數(shù)據(jù)元素的刪除。數(shù)據(jù)元素的刪除。線性鏈表的訪問基本方法是：線性鏈表的訪問基本方法是：（1 1）從頭結(jié)點開始沿線性鏈表方向進行探求，一）從頭結(jié)點開始沿線性鏈表方向進行探求，一般用于指向剛查過的結(jié)點地址，另一個用于指向下般用于指向剛查過的結(jié)點

19、地址，另一個用于指向下一個待查的結(jié)點地址。一個待查的結(jié)點地址。（2 2）結(jié)束訪問的條件有兩個：一個是結(jié)點地址為）結(jié)束訪問的條件有兩個：一個是結(jié)點地址為Nil,Nil,另一個是找到了相應(yīng)的結(jié)點。另一個是找到了相應(yīng)的結(jié)點。容易出錯的是：當(dāng)容易出錯的是：當(dāng)p p為為nilnil時，取時，取p.datap.data時出錯，因為時出錯，因為p p是是nilnil，p.datap.data的值無意義。的值無意義。 空間空間分配分配靜態(tài)分配。程序執(zhí)行前靜態(tài)分配。程序執(zhí)行前須確定存儲規(guī)模。估計須確定存儲規(guī)模。估計過大造成空間浪費，估過大造成空間浪費，估計太小使空間溢出機會計太小使空間溢出機會增多。增多。 動態(tài)

20、分配動態(tài)分配, ,只要內(nèi)存空間尚有空只要內(nèi)存空間尚有空閑，就不會產(chǎn)生溢出。當(dāng)線性表閑，就不會產(chǎn)生溢出。當(dāng)線性表的長度變化較大，難以估計存儲的長度變化較大，難以估計存儲規(guī)模時，宜采用動態(tài)鏈表作存儲規(guī)模時，宜采用動態(tài)鏈表作存儲結(jié)構(gòu)為好結(jié)構(gòu)為好。 時間時間存取存取隨機存取結(jié)構(gòu)，查找方隨機存取結(jié)構(gòu)，查找方便，但插入和刪除操作便，但插入和刪除操作很費時。很費時。順序存取結(jié)構(gòu)，鏈表中的結(jié)點，順序存取結(jié)構(gòu)，鏈表中的結(jié)點，需從頭指針起順著鏈掃描才能取需從頭指針起順著鏈掃描才能取得。得。 插入插入刪除刪除操作操作在順序表中進行插入和在順序表中進行插入和刪除，平均要移動表中刪除，平均要移動表中近一半的結(jié)點，尤其是

21、近一半的結(jié)點，尤其是當(dāng)每個結(jié)點的信息量較當(dāng)每個結(jié)點的信息量較大時，移動結(jié)點的時間大時，移動結(jié)點的時間開銷就相當(dāng)可觀。開銷就相當(dāng)可觀。 在鏈表進行插入和刪除，只需要在鏈表進行插入和刪除，只需要修改指針。對于頻繁進行插入和修改指針。對于頻繁進行插入和刪除的線性表，宜采用鏈表做存刪除的線性表，宜采用鏈表做存儲結(jié)構(gòu)。若表的插入和刪除主要儲結(jié)構(gòu)。若表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。指針表示的單循環(huán)鏈表為宜。 實戰(zhàn)演練：線性鏈表的歸并運算：實戰(zhàn)演練：線性鏈表的歸并運算：將下列兩個有序線性表進行歸并。將下列兩個有序線性表進行歸并。線性表（線性

22、表（1 1）是：）是：33，5 5，8 8，1111，1313線性表（線性表（2 2）是：）是：11，4 4，5 5，9 9，1515歸并后的線性表為：歸并后的線性表為：11，3 3，4 4，5 5，8 8，9 9，1111，1313，1515（1 1）線性鏈表中的結(jié)點是按數(shù)據(jù)域由小到大進行排）線性鏈表中的結(jié)點是按數(shù)據(jù)域由小到大進行排列的，根據(jù)兩個線性列的，根據(jù)兩個線性鏈鏈表中結(jié)點數(shù)據(jù)域的大小進行表中結(jié)點數(shù)據(jù)域的大小進行歸并運算；哪個表中的數(shù)據(jù)小就歸并哪一個；歸并運算；哪個表中的數(shù)據(jù)小就歸并哪一個；1 1、建立鏈表、建立鏈表2 2、歸并、歸并問題分析：問題分析：（2 2）當(dāng)兩個線性）當(dāng)兩個線性

23、鏈鏈表中有一個已歸并完畢，則另一個線表中有一個已歸并完畢，則另一個線性性鏈鏈表的剩余部分全部復(fù)制到所建立的新線性表的剩余部分全部復(fù)制到所建立的新線性鏈鏈表中。表中。（3 3）如果出現(xiàn)同值時，則選一個值。）如果出現(xiàn)同值時，則選一個值。p1:=head1;p2:=head2;p1:=head1;p2:=head2;while (p1nil) and (p2nil) dowhile (p1nil) and (p2nil) do begin begin if p1.data=p2.data if p1.data=p2.data then then 將鏈表將鏈表(1)(1)當(dāng)前結(jié)點加到新鏈表中當(dāng)前結(jié)點加

24、到新鏈表中,p1,p1指針后移指針后移; ; else else 將鏈表將鏈表(1)(1)當(dāng)前結(jié)點加到新鏈表中當(dāng)前結(jié)點加到新鏈表中,p2,p2指針后移指針后移; ; end; end;if p1nil then if p1nil then 將鏈表將鏈表(1)(1)剩余的結(jié)點連接到新表的后面剩余的結(jié)點連接到新表的后面; ;if p1nil then if p1nil then 將鏈表將鏈表(1)(1)剩余結(jié)點連到新表的后面剩余結(jié)點連到新表的后面; ;歸并算法：歸并算法：procedure combine(varprocedure combine(var head3:point;head1,hea

25、d2:point); head3:point;head1,head2:point); var var p1,p2,q,r:point; p1,p2,q,r:point; begin begin new(head3);r:=head3; new(head3);r:=head3; p1:=head1;p2:=head2; p1:=head1;p2:=head2; while (p1nil) and (p2nil) do while (p1nil) and (p2nil) do if p1.data=p2.data if p1.data=p2.data then begin then begin n

26、ew(q);r.next:=q;q.data:=p1.data; new(q);r.next:=q;q.data:=p1.data; r:=q; p1:=p1.next; r:=q; p1:=p1.next; if if p1.data=p2.data then p2:=p2.next; end end else begin else begin new(q);r.next:=q;q.data:=p2.data;r:=q; new(q);r.next:=q;q.data:=p2.data;r:=q; p2:=p2.next; p2:=p2.next; end; end; if p1nil th

27、en r.next:=p1; if p1nil then r.next:=p1; if p2nil then r.next:=p2; if p2nil then r.next:=p2; end; end;本算法在構(gòu)建鏈表本算法在構(gòu)建鏈表3 3時申請了新結(jié)點，能否時申請了新結(jié)點，能否不申請新結(jié)點來實現(xiàn)線性鏈表的歸并？不申請新結(jié)點來實現(xiàn)線性鏈表的歸并？想一想：想一想： 小結(jié)：小結(jié)： （1 1）單向線性鏈表只能向后遍歷，不能向前，）單向線性鏈表只能向后遍歷，不能向前，不能隨機訪問任一元素。不能隨機訪問任一元素。 （2 2）表頭結(jié)點很重要，如果表頭結(jié)點丟失，）表頭結(jié)點很重要，如果表頭結(jié)點丟失，則線性鏈

28、表將無法找回。則線性鏈表將無法找回。（3 3）在進行插入和刪除結(jié)點的操作時，不需要）在進行插入和刪除結(jié)點的操作時，不需要移動大量的數(shù)據(jù)，但是要注意不能斷鏈。移動大量的數(shù)據(jù)，但是要注意不能斷鏈。不帶附加不帶附加頭結(jié)點的頭結(jié)點的鏈表鏈表heada1 a2 a3 a4a1 a2 a3 a4帶附加頭結(jié)帶附加頭結(jié)點的鏈表點的鏈表線性鏈表的幾種形式：線性鏈表的幾種形式： 其特點如下：其特點如下：單向鏈表、雙向鏈表、循環(huán)鏈表單向鏈表、雙向鏈表、循環(huán)鏈表單循環(huán)鏈表雙循環(huán)鏈表雙向鏈表雙向鏈表雙鏈表的操作與單鏈表基本一致：雙鏈表的操作與單鏈表基本一致：123412type type point=node; poi

29、nt=node; node=record node=record data:datatype data:datatype; ; pre,next:point; pre,next:point; end; end;（1）每個結(jié)點有兩個指針）每個結(jié)點有兩個指針域，一個指向其前驅(qū)結(jié)點，域，一個指向其前驅(qū)結(jié)點，一個指向其后繼結(jié)點。一個指向其后繼結(jié)點。（2）從任一結(jié)點出發(fā)可以）從任一結(jié)點出發(fā)可以訪問其他結(jié)點。訪問其他結(jié)點。 便于訪問、插入和刪除。便于訪問、插入和刪除。 （1 1） 尾結(jié)點指向第一個結(jié)點；尾結(jié)點指向第一個結(jié)點；（2 2）從表中任一個結(jié)點出發(fā)可以找到鏈表中的其他結(jié)點。）從表中任一個結(jié)點出發(fā)可以

30、找到鏈表中的其他結(jié)點。（3 3）遍歷操作的結(jié)束條件是：）遍歷操作的結(jié)束條件是：（4 4）其他操作與單鏈表一樣。）其他操作與單鏈表一樣。循環(huán)鏈表循環(huán)鏈表注意：注意：帶附加頭結(jié)點帶附加頭結(jié)點 p=head.nextp=head.next不帶附加頭結(jié)點不帶附加頭結(jié)點p=headp=head雙向循環(huán)鏈表：最后一個結(jié)點的指針指向頭結(jié)點，雙向循環(huán)鏈表：最后一個結(jié)點的指針指向頭結(jié)點，且頭結(jié)點的前趨指向最后一個結(jié)點。如下圖：且頭結(jié)點的前趨指向最后一個結(jié)點。如下圖： 問題描述：設(shè)有問題描述：設(shè)有n n個人圍成一圈，并按順個人圍成一圈，并按順時針方向從時針方向從1 1到到n n編號；從第編號；從第s s個人開始進

31、個人開始進行行1 1到到m m報數(shù)，數(shù)到報數(shù)，數(shù)到m m的人出圈；接著再從的人出圈；接著再從他后面一個人重新開始他后面一個人重新開始1 1到到m m報數(shù)，直到報數(shù)，直到所有人出圈為止。輸出出圈人的次序。所有人出圈為止。輸出出圈人的次序。例例2約瑟夫問題。約瑟夫問題。分析分析: :(1) N (1) N 個人按序號圍坐一圈，即第個人按序號圍坐一圈，即第 1 1 個人后是第個人后是第 2 2 個人個人.第第N N 個人的后繼是第個人的后繼是第 1 1 個人個人, ,形成循環(huán)形成循環(huán)鏈表的結(jié)構(gòu)，鏈表的結(jié)構(gòu)， 所以可采用循環(huán)鏈表表示這所以可采用循環(huán)鏈表表示這 N N 個人個人; ;(2) (2) 每一

32、個結(jié)點有兩個域每一個結(jié)點有兩個域: : 數(shù)據(jù)域數(shù)據(jù)域人的編號人的編號, , 指針域指針域指向下一個人的地址指向下一個人的地址; ;(3) (3) 報數(shù)報數(shù) : : 即數(shù)人個數(shù)即數(shù)人個數(shù), , 每當(dāng)數(shù)到每當(dāng)數(shù)到 M M 時時, , 則該號則該號人走出圈內(nèi)人走出圈內(nèi)刪除該結(jié)點刪除該結(jié)點, , 輸出人編號輸出人編號 ; ; (4) (4) 重復(fù)重復(fù) (3)(3)過程過程, , 直到只有一個人為止。直到只有一個人為止。例2約瑟夫問題。數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： type pointman ; manrecord num : integer ; next : point ; end ; var head ,

33、p , q : point ; n , m : integer ; 建立循環(huán)鏈表建立循環(huán)鏈表Procedure creat(var head:point); var p,q:point; i:integer ; begin new(p) ; head:=p;p.num:=1;q:=p ; for i:=2 to n do begin new(p); end ; q.next := head ; end ; p.num:=i ; q.next:=p; q:=p;Procedure select(var head:point); var （選舉大王的過程）（選舉大王的過程） p,q:point;

34、i,x:integer ; begin p:=head;x:=1;q:=p; repeat p:=q.next; x:=x1 ; if x mod m = 0 then else q := p ; until p=p.next;（只剩一個結(jié)點）（只剩一個結(jié)點）writeln ; head := p ; end ;（Q Q 為為 P P 的前趨指針）的前趨指針） BEGIN 主程序主程序 readln(n,m); creat(head) ; select(head) ; write ( the king : ); writeln(head.num) ; END .begin q.next:=p.next; write(p.num:8 ) ; dispose ( p ) ; end例例3 營業(yè)額統(tǒng)計營業(yè)額統(tǒng)計給定給定N（1N32767）天的營業(yè)額）天的營業(yè)額a1,a2,an. 定義一天的最小波動值等于定義一天的最小波動值等于 min|該天以前某一天的營業(yè)額該天以前某一天的營業(yè)額-該天營業(yè)額該天營業(yè)額|特別地，第一天的最小波動值即為特別地，第一天