指針鏈表入門(加強(qiáng)版)

1、動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)鏈表 指針的引入 數(shù)據(jù)結(jié)構(gòu)分為動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)和靜態(tài)數(shù)據(jù)結(jié)構(gòu)，在實(shí)際的編程過(guò)程中，經(jīng)常會(huì)遇到這種問(wèn) 題：我們不能確定操作的數(shù)據(jù)的個(gè)數(shù)。如果用數(shù)組太大，會(huì)超內(nèi)存，反之可能不夠用。如果隨著數(shù)據(jù)的增多， 有一種數(shù)據(jù)結(jié)構(gòu)隨著 內(nèi)存變大，就可以解決這種問(wèn)題，這種數(shù)據(jù)結(jié)構(gòu)就是動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。 一個(gè)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)是元素(或結(jié)點(diǎn))的匯集。與數(shù)組不同，它不需要包括存儲(chǔ)固定數(shù)目 的存儲(chǔ)空間，而是在程序執(zhí)行時(shí)隨著數(shù)據(jù)的需要而擴(kuò)充或縮減。 討論動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，就要討論與之相關(guān)的一種靜態(tài)數(shù)據(jù)結(jié)構(gòu)指針。指針的實(shí)質(zhì)指針就是 地址，指針存儲(chǔ)的變量就是指針變量。 指針變量單元中存放的是某種數(shù)據(jù)變 量單元的地址，通過(guò)這個(gè)地址可

2、以找到這種類型的數(shù)據(jù)。 我們所關(guān)心的是指針指向的一個(gè)什么樣的數(shù)據(jù)， 即數(shù)據(jù)的基類型是什 么。指針的應(yīng)用一、定義：1. typerec=A in teger;vari,j:rec;2. vari, j:Ainteger;二、使用1. 開辟 new(i);功能：系統(tǒng)將自動(dòng)分配一個(gè)存放數(shù)據(jù)的存儲(chǔ)單元，并把存儲(chǔ)單元的地址賦給指針變量i，此單位能存放的數(shù)據(jù)的類型正好是 i 的基類型，存儲(chǔ)單元的大小由數(shù)據(jù)的基類型決定。2. 釋放 dispose(i);功能：為了節(jié)省空間， 對(duì)于一些已經(jīng)不需要的動(dòng)態(tài)變量單元， 系統(tǒng)能通過(guò) dispose 收回。3. 賦值 iA:=jA;功能：給指針變量賦值，正是我們所需要的

3、數(shù)據(jù)。注:i:=j;賦值給i的是j的地址，i的地址會(huì)變成j的地址，即兩個(gè)指針變量的地址相同，同時(shí)指向一個(gè)數(shù)據(jù)；iA:=jA;賦值給i的是j的數(shù)值，i的地址并未改變。三、使用樣例 輸入兩個(gè)整數(shù)，按照從小到大打印出來(lái)。program taxis;typepointer=Ainteger;varp,q:pointer;procedure swap(var h,r:pointer); vart:pointer;begint:=h;h:=r;r:=t;end;beginnew(p);new(q);readln(pA,qA);if pAqA then swap(p,q);writeln(pA, ,qA);

4、dispose(p);dispose(q);end. 自己通過(guò) free pascal 編譯運(yùn)行的 設(shè)又一批數(shù)1 , 2, 12, 45, 6, 12, 4, 1, 65,，如何存放呢？我們當(dāng)然會(huì)選擇以 前學(xué)的， 數(shù)組， 但是如果不知道又多少的數(shù)據(jù)呢？那就得開一個(gè)足夠大的數(shù)組，但是如果數(shù)據(jù)量很大呢？這種數(shù)據(jù)結(jié)構(gòu)缺乏靈活性,往往會(huì)浪費(fèi)很多空間,這就是靜態(tài)數(shù)據(jù)結(jié)構(gòu)。本文將介紹一種簡(jiǎn)單實(shí)用的數(shù)據(jù)結(jié)構(gòu)鏈表。typepointer=Arec; rec=recorddata:longint;next:pointer;end;varp1,p2:pointer;new(p1); new(p2);p1data:

5、=10;p1A. next:=p2;通過(guò)這樣的一種遞歸建立聯(lián)系。第一步：申請(qǐng)新節(jié)點(diǎn)；第二步：給結(jié)點(diǎn)的數(shù)據(jù)域和指針域賦值；第三步：將結(jié)點(diǎn)鏈接到表中的某一位置。例題： 建立一個(gè)有十個(gè)結(jié)點(diǎn)的鏈表，最后輸出該鏈表。Program creatable(input, output);TypePointer=Arec;Rec=recordData:string5;Next:pointer;End;VarP1,p2,h:pointer;I:integer;BeginNew(p1);Readln(p1A.data);H:=p1;Fo r I:=1 to 9 doBeginNew(p2);Readln(p2A.d

6、ata);P1.next:=p2;P1:=p2;End;P2.next:=nil;P1:=h;While p1nil doBeginWrite(p1A.data, );P1:=p1.next;End;End.解釋：在輸出鏈表時(shí)，將 h 作為 p1 的初值，輸出 p1 所指向的結(jié)點(diǎn)的數(shù)據(jù)域，然后將 p1 指 針移向下一個(gè)結(jié)點(diǎn)，再輸出，知道 p1 是 nil 。這個(gè)過(guò)程就是鏈表的遍歷。常見的鏈表模型1. 先進(jìn)先出鏈表(隊(duì))2. 先進(jìn)后出鏈表(棧)例題 ：讀入一批數(shù)據(jù)，遇到負(fù)數(shù)就停止，將讀入的正數(shù)組成先進(jìn)先出鏈表并輸出。typepoin terrec;rec=recorddata:integer;n

7、ext:pointer;end;varp1,p2,h:pointer;x:integer;beginread(x);if x=0 thenbeginnew(p1);p1A.data:=x;end;h:=p1;read(x);while x0 dobeginnew(p2);p2A.data:=x;p1A.next:=p2;p1:=p2;read(x);end;p1:=h;while p1nil dobeginwriteln(p1A.data);p1:=p1A.next;end;end. 自己寫的，經(jīng)過(guò) cena 測(cè)評(píng) 例題 ：與上題相同，將讀入的正數(shù)組成先進(jìn)后出的鏈表并輸出。 typepoin

8、terrec;rec=recorddata:integer;next:pointer;end;varh,p:pointer;x:integer;beginread(x);write(x, );h:=nil;while x0 dobeginnew(h);hA.data:=x;hA. next:=p;p:=h;read(x);write(x, );end;writeln;while pnil dobeginwriteln(pA.data);p:=pA.next;end;end. 保證正確 鏈表的基本操作插入1. 插入表頭我們要將 q 所指向的結(jié)點(diǎn)插入表頭： qA.next:=h;h:=p;2. 插

9、入表中在pl和p2所指的結(jié)點(diǎn)之間插入 p所指的結(jié)點(diǎn): p1A.next:=p ; p next:=p2;3. 插入表尾在表尾插入 q 所指的結(jié)點(diǎn)：p2A.next:=q ；qA.next:=nil;例題 ：在一個(gè)有序的序列鏈表中插入一個(gè)新的結(jié)點(diǎn)，只插入以后仍然有序。 保證原鏈表序列有序 例題 ：讀入一批數(shù)，遇到負(fù)數(shù)時(shí)結(jié)束，將正數(shù)組成有序鏈表。由于實(shí)際需要我把它們合在一塊兒寫，這樣其實(shí)就是用鏈表排序的過(guò)程。 代碼；typepointer=Arec;rec=recorddata:longint;next:pointer;end;varp:pointer;procedure insert_poi(x

10、:longint; var h:pointer);varq,p1,p2:pointer;beginnew(q);qA.data:=x;if xp2A.data)and(p2A.nextnil) dobeginp1:=p2;p2:=p2A.next;end;if x=0 dobegin insert_poi(x,h); read(x);end;end;begininorder_poi(p);while pnil dobeginwrite(pA.data, ); p:=pA.next;end;end.鏈表的基本操作刪除刪除操作包括查找和刪除， 我們從頭開始遍歷表， 知道找到目標(biāo)或到達(dá)表尾； 如果找

11、到目標(biāo)，將 delete 賦為 TRUE 代碼：procedure delete_poi(x:longint; var h:pointer); varp1,p2:pointer;beginp1:=h;while (p1datax)a nd(p .n extn il) dobeginp2:=p1;p1:=p1A. next;end;if x=p1A.data thenbeginwriteln(p2A.data);if p1=h thenh:=hA.nextelse p2A.next:=p1A.next;endelsebeginwriteln(False!);halt;end;end;其他形式的鏈

12、表1. 循環(huán)鏈表循環(huán)鏈表解決約瑟夫環(huán)問(wèn)題 代碼：Program Joseph;typepointer=Arec;rec=recorddata:longint;next:pointer;end;vari,n,m,k:longint;p1,p2,h:pointer;beginreadln(n,m);new(p1);p1data:=1;h:=p1;for i:=2 to n dobegin new(p2);p2A.data:=i;p1A. next:=p2; p1:=p2;end;p1A.next:=h;i:=1; k:=1;p1:=h;repeatp2:=p1A.next;inc(i);if i

13、mod m=0 then beginp1A.next:=p2A.next;writeln(NO:,k, ,p2A.data, ); inc(k);p2A.next:=nil;dispose(p2); end else p1:=p2;until p1A.next=p1;writeln;writeln(THE LUKY DOG IS : ,p1A.data);p1A.next:=nil;dispose(p1);end.prev2. 雙向鏈表在普通鏈表的基礎(chǔ)上加一個(gè)前驅(qū)值 代碼：type pointer=Arec; rec=record prev:pointer; data:longint; nex

14、t:pointer;end;varp1,p2,h:pointer;i,j:longint;beginread(i);if i0 thenbeginnew(p1); p1data:=i;end;h:=p1;read(i);while i0 dobegin new(p2);p2A.data:=i; p2A.prev:=p1; p1A. next:=p2;p1:=p2; read(i); end;p2A.next:=nil;p1:=h;p1A.prev:=nil;while p1nil dobeginwrite(p1A.data,-); p1:=p1A.next;end;writeln(end);w

15、riteln();writeln;while p2nil dobeginwrite(p2A.data,-); p2:=p2A.prev;end;writeln(end);writeln();writeln;end.例題 1 讀入一串一 #結(jié)束標(biāo)志的字符，并統(tǒng)計(jì)每個(gè)字符出現(xiàn)的次數(shù)，用鏈表實(shí)現(xiàn)。例題 2 求 2100 的素?cái)?shù)，用鏈表實(shí)現(xiàn)。例題 3 圍繞著山頂有 10 個(gè)洞，一只兔子和一只狐貍各住一個(gè)洞， 狐貍總是想吃掉兔子。 一天兔子對(duì)狐貍說(shuō)，你想吃掉我有一個(gè)條件，你先把洞標(biāo)號(hào)為 1 到 10 ，你從 10 號(hào)出 發(fā)，先到 1 號(hào)洞找我，第二次隔一個(gè)洞找我，第三次各兩個(gè)洞找我，以后以此類推，次數(shù)不

16、限。若能找到我你就能飽餐一頓。 利用單向鏈表編程，假定狐貍找1000次，兔子躲在那個(gè)洞里安全。例題 4 某賓館的訂房管理中， 將客人的記錄按姓名的拼音字母順序排成一個(gè)鏈表。 試 著編程，從鍵盤上輸入下列字母就可以對(duì)客人記錄進(jìn)行管理：（1）、 I 客人訂房；（ 2）、 s 查詢某客人記錄（或?未找到?）；（ 3）、 d 客人退房（ 4）、 q 在屏幕上列出所有客人記錄并結(jié)束程序。例題 5 編一個(gè)簡(jiǎn)單的中學(xué)生新生入校登記表處理程序。參考程序：例題 1 ：typepoin terrec;rec=recordcount:longint;data:char;next:pointer;end;vark:c

17、har;head,s:pointer;procedure search(x:char);varp:pointer;beginp:=head;sdata:=x;while pA.datax do p:=pA .n ext; if ps the n in c(pA.co unt) elsebegin p:=head; new(head); headA.data:=x; headA.count:=1; headA.next:=p;end;end; / of searchprocedure printlist(p:pointer);beginwhile ps dobeginwriteln(pA.dat

18、a, ,pA.count); p:=pA.next;end;end; / of printbeginnew(s);sA.data:= ;sA.count:=1;sA.next:=nil; head:=s; read(k); while k# do begin search(k); read(k);end;printlist(head);end. / of main例題 2typepointer=Arec;rec=recorddata:longint;next:pointer;end;var head:pointer;procedure printlist(h:pointer); varp:po

19、inter;beginp:=h;while pnil dobeginwrite(pdata,-); p:=pA .n ext;end;end;procedure creatb;varp,q:pointer; i:longint;begin new(head); headA.data:=2; q:=head;for i:=3 to 100 dobegin new(p); pA.data:=i; pA.next:=nil; qA.next:=p;q:=p;end;end;procedure prime;varh,p,q:pointer; beginh:=head;while hnil dobegi

20、np:=h; q:=pA.next; while qnil doif .data mod hdata=O) the nbeginpA. next:=qA .n ext; dispose(q); q:=pA.next;endelse beginp:=q; q:=qA.next;end;h:=hA.next;end;end;begincreatb;printlist(head);writeln;prime;printlist(head); writeln(end);end.例題 3：type pointer=Arec; rec=record data:longint; key:boolean; n

21、ext:pointer;end;varm,n,i,l,t,step:longint; p1,p2,h:pointer;beginm:=10;n:=100; new(p1); p1A.data:=10; p1A.key:=false;h:=p1;for i:=1 to 9 dobeginnew(p2);p2data:=i; p2key:=true; p1A. next:=p2; p1:=p2;end; p1A.next:=nil; l:=0; step:=0;for step:=1 to n do begin l:=l+step; t:=l mod m;p1:=h;for i:=1 to t d

22、op1:=p1A.next;p1A.key:=false;end;p1:=h;l:=1;while p1nil dobeginif p1A.key=true thenbeginwriteLN(SAFE NO,l,:,p1A.data); inc(l);end;p1:=p1A.next;end;end.例題 4：typepointer=Arec;rec=recordna:string20;ro:integer;next:pointer;end;varh:pointer; n:string20; r:integer; k:char;procedure insert_poi(n:string;var

23、 r:integer; var h:pointer); varq,p1,p2:pointer;begin new(q);qA. na:=n;qA.ro:=r;if np2A.na)and(p2A.nextnil) do beginp1:=p2; p2:=p2A.next;end;if n=p2A.na thenbeginp1A.next:=q;qA.next:=p2; end else beginp2A.next:=q; qA.next:=nil;end;end;end;procedure search(n:string; var h:pointer); varp1,p2:pointer;beginp2:=h;while (p2A.nan)and(p2A.nextnil) do beginp1:=p2; p2:=p2A.next;end;if p2A.na=n thenbeginwritel n( Name: ,p2A. na);writel n(Room: ：p2A.ro);endelse writeln(No found! );end;procedure delete_poi(n:string; var h:pointer); varp1,p2:pointer;be