指针链表入门(加强版)

1、动态数据结构链表 指针的引入 数据结构分为动态数据结构和静态数据结构，在实际的编程过程中，经常会遇到这种问 题：我们不能确定操作的数据的个数。如果用数组太大，会超内存，反之可能不够用。如果随着数据的增多， 有一种数据结构随着 内存变大，就可以解决这种问题，这种数据结构就是动态数据结构。 一个动态数据结构是元素(或结点)的汇集。与数组不同，它不需要包括存储固定数目 的存储空间，而是在程序执行时随着数据的需要而扩充或缩减。 讨论动态数据结构，就要讨论与之相关的一种静态数据结构指针。指针的实质指针就是 地址，指针存储的变量就是指针变量。 指针变量单元中存放的是某种数据变 量单元的地址，通过这个地址可

2、以找到这种类型的数据。 我们所关心的是指针指向的一个什么样的数据， 即数据的基类型是什 么。指针的应用一、定义：1. typerec=A in teger;vari,j:rec;2. vari, j:Ainteger;二、使用1. 开辟 new(i);功能：系统将自动分配一个存放数据的存储单元，并把存储单元的地址赋给指针变量i，此单位能存放的数据的类型正好是 i 的基类型，存储单元的大小由数据的基类型决定。2. 释放 dispose(i);功能：为了节省空间， 对于一些已经不需要的动态变量单元， 系统能通过 dispose 收回。3. 赋值 iA:=jA;功能：给指针变量赋值，正是我们所需要的

3、数据。注:i:=j;赋值给i的是j的地址，i的地址会变成j的地址，即两个指针变量的地址相同，同时指向一个数据；iA:=jA;赋值给i的是j的数值，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. 自己通过 free pascal 编译运行的 设又一批数1 , 2, 12, 45, 6, 12, 4, 1, 65,，如何存放呢？我们当然会选择以 前学的， 数组， 但是如果不知道又多少的数据呢？那就得开一个足够大的数组，但是如果数据量很大呢？这种数据结构缺乏灵活性,往往会浪费很多空间,这就是静态数据结构。本文将介绍一种简单实用的数据结构链表。typepointer=Arec; rec=recorddata:longint;next:pointer;end;varp1,p2:pointer;new(p1); new(p2);p1data:

5、=10;p1A. next:=p2;通过这样的一种递归建立联系。第一步：申请新节点；第二步：给结点的数据域和指针域赋值；第三步：将结点链接到表中的某一位置。例题： 建立一个有十个结点的链表，最后输出该链表。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.解释：在输出链表时，将 h 作为 p1 的初值，输出 p1 所指向的结点的数据域，然后将 p1 指 针移向下一个结点，再输出，知道 p1 是 nil 。这个过程就是链表的遍历。常见的链表模型1. 先进先出链表(队)2. 先进后出链表(栈)例题 ：读入一批数据，遇到负数就停止，将读入的正数组成先进先出链表并输出。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. 自己写的，经过 cena 测评 例题 ：与上题相同，将读入的正数组成先进后出的链表并输出。 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 所指向的结点插入表头： qA.next:=h;h:=p;2. 插

9、入表中在pl和p2所指的结点之间插入 p所指的结点: p1A.next:=p ; p next:=p2;3. 插入表尾在表尾插入 q 所指的结点：p2A.next:=q ；qA.next:=nil;例题 ：在一个有序的序列链表中插入一个新的结点，只插入以后仍然有序。 保证原链表序列有序 例题 ：读入一批数，遇到负数时结束，将正数组成有序链表。由于实际需要我把它们合在一块儿写，这样其实就是用链表排序的过程。 代码；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.链表的基本操作删除删除操作包括查找和删除， 我们从头开始遍历表， 知道找到目标或到达表尾； 如果找

11、到目标，将 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. 循环链表循环链表解决约瑟夫环问题 代码：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. 双向链表在普通链表的基础上加一个前驱值 代码：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 读入一串一 #结束标志的字符，并统计每个字符出现的次数，用链表实现。例题 2 求 2100 的素数，用链表实现。例题 3 围绕着山顶有 10 个洞，一只兔子和一只狐狸各住一个洞， 狐狸总是想吃掉兔子。 一天兔子对狐狸说，你想吃掉我有一个条件，你先把洞标号为 1 到 10 ，你从 10 号出 发，先到 1 号洞找我，第二次隔一个洞找我，第三次各两个洞找我，以后以此类推，次数不

16、限。若能找到我你就能饱餐一顿。 利用单向链表编程，假定狐狸找1000次，兔子躲在那个洞里安全。例题 4 某宾馆的订房管理中， 将客人的记录按姓名的拼音字母顺序排成一个链表。 试 着编程，从键盘上输入下列字母就可以对客人记录进行管理：（1）、 I 客人订房；（ 2）、 s 查询某客人记录（或?未找到?）；（ 3）、 d 客人退房（ 4）、 q 在屏幕上列出所有客人记录并结束程序。例题 5 编一个简单的中学生新生入校登记表处理程序。参考程序：例题 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