mutong在yj41上第21講指針與鏈表

第4講指針類型與鏈表學(xué)習(xí)的原因：構(gòu)造合適的哈希函數(shù)，便于分類查找。

空間和時(shí)間都得到改進(jìn)。搜索中應(yīng)用（查找某個(gè)元素是否在某個(gè)集合中）存儲(chǔ)數(shù)據(jù)的需要

樹和圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：操作方便減少空間

需要多少，申請(qǐng)多少，沒有冗余。最簡(jiǎn)單的例子Varp:^integer;Beginnew(p);p^:=123;writeln(p^);End.一、指針的定義

指針的定義：

1、type指針名字=^指向的基類型；如：typepoint=^integer;varp1,p2:point;2、直接定義指針變量：

varp1,p2:^integer;p1,p2是指向整型的指針指針名字可以是任意的標(biāo)識(shí)符基類型可以是基本類型或自定義的類型。一般變量：靜態(tài)變量

只要定義了，就分配占用固定的存儲(chǔ)單元，直到程序結(jié)束。指針變量：動(dòng)態(tài)變量存儲(chǔ)的某個(gè)存儲(chǔ)單元的地址如果是僅僅定義了指針變量，并沒有開辟存儲(chǔ)單元開辟一個(gè)動(dòng)態(tài)的存儲(chǔ)單元：調(diào)用標(biāo)準(zhǔn)過程：newVarp:^integer;//定義指向整型的指針Beginnew(p);//動(dòng)態(tài)分配內(nèi)存區(qū)域

p^:=123;//為p指向的區(qū)域賦值

writeln(p^);//輸出p指向的區(qū)域內(nèi)容End.//p^即相當(dāng)于整型變量格式：new(指針變量)功能：開辟一個(gè)指針類型的存儲(chǔ)單元，并把此存儲(chǔ)單元的地址賦給指針變量。標(biāo)準(zhǔn)過程：new功能：釋放空間的

如：dispose(p)

慎用！標(biāo)準(zhǔn)過程：dispose(指針變量）Nil符號(hào)：空地址指針變量除了指向內(nèi)存地址外，還可以指向空地址，用nil表示。表示不指向任何一個(gè)地址。例：varp^:integer;

p:=nil;

往往初始化指針時(shí)用二、鏈表數(shù)組和鏈表是線形表的兩種表現(xiàn)形式。

數(shù)組存取方便，但插入元素復(fù)雜度高。鏈表插入方便，但隨機(jī)讀取復(fù)雜度高。存儲(chǔ)一批數(shù)：鏈表定義typePoint=^node;//指向結(jié)點(diǎn)的指針

node=record//結(jié)點(diǎn)類型

data:integer;//結(jié)點(diǎn)數(shù)據(jù)

next:point;//下一個(gè)指針

end;varhead,p,q:point;單鏈表：必須有一個(gè)頭指針指向鏈表的第一個(gè)結(jié)點(diǎn)，然后依次可以訪問后面的結(jié)點(diǎn)。操作：插入查找刪除在鏈表前端插入元素新生成一個(gè)結(jié)點(diǎn)p；給p的數(shù)據(jù)域賦值；該結(jié)點(diǎn)next指向head指針；head指向該指針；pnew(p);P^.data:=x;P:=head;Head:=p;1、插入（前插,后插,中間插）例1建立一個(gè)由n個(gè)數(shù)組成的鏈表，每讀入一個(gè)數(shù)后，將該數(shù)插入到鏈表的最前端。然后從頭依次輸出n個(gè)數(shù)。輸入：512345輸出：54321//按讀入順序倒序輸出typepoint=^node;node=recorddata:integer;next:point;end;varhead:point;n,i,x:integer;beginhead:=nil;readln(n);fori:=1tondobeginread(x);

insert(x);end;

print;cedureinsert(x:integer);//前插xvarp:point;beginnew(p);p^.data:=x;p^.next:=head;head:=p;end;procedureprint;//從頭依次輸出結(jié)點(diǎn)的值

varp:point;beginp:=head;whilep<>nildobeginwrite(p^.data,'');p:=p^.next;end;end;在鏈表尾端插入元素（再設(shè)置一個(gè)尾指針tail）新生成一個(gè)結(jié)點(diǎn)p；給p的數(shù)據(jù)域賦值；尾tail的next指向p指針；tail指向p；new(p);P^.data:=x;tail^.next:=p;tail:=p;例2建立一個(gè)由n個(gè)數(shù)組成的鏈表，每讀入一個(gè)數(shù)后，將該數(shù)插入到鏈表的最前端。然后從頭依次輸出n個(gè)數(shù)。輸入：512345輸出：12345//按讀入順序倒序輸出為了插入方便，先單獨(dú)建立第一個(gè)結(jié)點(diǎn)head:=nil;readln(n);

new(tail);read(x);tail^.data:=x;head:=tail;fori:=1ton-1dobeginread(x);insert(x);end;print;5nilheadtailprocedureinsert(x:integer);//表尾插入，表尾指針tailvarp:point;beginnew(p);p^.data:=x;//p^.next:=nil;tail^.next:=p;tail:=p;end;鏈表中間插入元素：設(shè)r是指向需插入的元素的指針，r應(yīng)插入指針p與q之間，則插入過程為；

p^.next:=r;r^.next:=q;若果q=nil,就是在尾插入。

所以表后插入是中間插入的特例

操作一樣2、鏈表中查找元素x用一個(gè)臨時(shí)指針p遍歷鏈表，每次與p^.data比較，如果相等，則查找成功，否則p:=p^.next，如果p為空，則查找失敗。functionfind(x:integer):boolean;varp:point;;beginp:=head;while(p<>nil)and(p^.data<>x)dop:=p^.next;ifp=nilthenexit(false)elseexit(true);end;3、鏈表元素的刪除設(shè)p指向需刪除的元素，q是p的前一個(gè)元素，則刪除過程為：

q^.next:=p^.next;(dispose(p);)proceduredel(x:integer);varp,q:point;beginifhead^.data=xthen//頭元素

beginhead:=head^.next;exit;end;p:=head;while(p<>nil)and(p^.data<>x)dobeginq:=p;p:=p^.next;end;ifp=nilthenwriteln('nofound')elseq^.next:=p^.next;end;例3：p4.pas輸入n及n個(gè)元素，建立一個(gè)鏈表。輸出元素（順序或逆序都可以）輸入一x，如果在鏈中，就刪除，不在輸出“nofound”輸出刪除后的數(shù)據(jù)如：3123321231head:=nil;readln(n);fori:=1tondobeginread(x);

insert(x);end;print;readln(x);

del(x);print;1、用鏈表實(shí)現(xiàn)插入排序（從小到大）如：輸入：531425輸出：12345三、綜合應(yīng)用方法1：p31readln(n);new(head);read(x);head^.data:=x;//先建第一個(gè)結(jié)點(diǎn)

fori:=2tondobeginread(x);insert(x);end;print;procedureinsert(x:integer);varp,q,r:point;beginnew(r);r^.data:=x;ifx<head^.datathen//前插：最小

beginr^.next:=head;head:=r;exit;end;q:=head;while(q<>nil)and(x>q^.data)dobeginp:=q;q:=q^.next;end;p^.next:=r;r^.next:=q;end;方法2：p32附加一個(gè)無窮小的頭結(jié)點(diǎn)，這樣可以保證x一定是后插（相對(duì)于head而言）。

readln(n);new(head);head^.data:=-maxlongint;fori:=1tondobeginread(x);insert(x);end;print;procedureinsert(x:integer);//肯定不會(huì)插在最前面：尾插或中間插一樣操作

varp,q,r:point;beginq:=head;while(q<>nil)and(x>q^.data)dobeginp:=q;q:=q^.next;end;new(r);r^.data:=x;p^.next:=r;r^.next:=q;end;2、輸入n(<=10000)個(gè)正整數(shù)，按照他們對(duì)m的余數(shù)分類。然后按余數(shù)的大小從小大大輸出n個(gè)數(shù)。重復(fù)的只輸出一次（重復(fù)的數(shù)只保留一個(gè)即可）如：m=10；輸入：61511152011輸出：20111155constm=10;typepoint=^node;node=recorddata:integer;next:point;end;vara:array[0..m-1]ofpoint;n,i,x:integer;Main：fori:=0tom-1doa[i]:=nil;readln(n);fori:=1tondobeginread(x);ifnotfind(x)theninsert(x);end;print;functionfind(x:integer):boolean;varp:point;k:integer;begink:=xmodm;p:=a[k];while(p<>nil)and(p^.data<>x)dop:=p^.next;ifp=nilthenexit(false)elseexit(true);end;procedureinsert(x:integer);varp:point;k:integer;beginnew(p);p^.data:=x;k:=xmodm;p^.next:=a[k];a[k]:=p;end;procedureprint;varp:point;beginfori:=0tom-1doifa[i]<>nilthenbeginp:=a[i];whilep<>nildobeginwrite(p^.data,'');p:=p^.next;end;writeln;end;end;3：輸入100000個(gè)1至1000000000之間的整數(shù)，然后輸入m個(gè)需查找的數(shù)，輸出是否存在。分析：定義一個(gè)0至99999之間數(shù)組，數(shù)組元素為鏈表，數(shù)組a[i]存儲(chǔ)mod100000余數(shù)為i的所有的數(shù)。查找是只需遍歷其中某一個(gè)鏈表。平均每個(gè)數(shù)組中有一個(gè)元素，時(shí)間復(fù)雜度為O(n)4、字符串轉(zhuǎn)換（chuan22.pas）Maxn=1000000;point=^pnode;pnode=recordstr:string;next:point;end;hash:array[0..maxn-1]ofpoint;//如果在鏈中，返回true，如果不在，插入到鏈中。

functionfind(s:string):boolean;vark,i:longint;p:point;begink:=0;fori:=1tolength(s)dobegink:=k*131+ord(s[i]);k:=kmod1000000;end;p:=hash[k];while(p<>nil)and(p^.str<>s)dop:=p^.next;ifp<>nilthenexit(true);new(p);p^.str:=s;p^.next:=hash[k];hash[k]:=p;exit(false);end;5、方程的解數(shù)（noi2001）四、總結(jié)1、如果鏈表加一個(gè)頭結(jié)點(diǎn)，不存要求的信息，真正的信息從第二個(gè)開始存，這樣可以保證插入和刪除都是在后面進(jìn)行，可以統(tǒng)一處理，不要單獨(dú)考慮刪除頭或在鏈頭插入元素。缺點(diǎn)是多了一個(gè)結(jié)點(diǎn)。根據(jù)習(xí)慣選擇合適的方法。2、可以用數(shù)組來模擬鏈表。目前有很多選手采取這樣的方法。尤其在保存圖時(shí)（稀疏圖）如：輸入n(<=10000)個(gè)正整數(shù)，按照他們對(duì)m的余數(shù)分類。然后按余數(shù)的大小從小大大輸出n個(gè)數(shù)。重復(fù)的只輸出一次（重復(fù)的數(shù)只保留一個(gè)即可）如：m=10；輸入：7151115202125輸出：202111125155下標(biāo)1234567data151115202125next001203415111520212505162030405760708090Hash[i]topa[i]下標(biāo)datanext15111520212500102030405060