《【pascal教程】第8章 指针与链表课件》由会员分享,可在线阅读,更多相关《【pascal教程】第8章 指针与链表课件(28页珍藏版)》请在金锄头文库上搜索。
1、第八章指针与链表,前面介绍的各种简单类型的数据和构造类型的数据属于静态数据。在程序中,这些类型的变量一经说明,就在内存中占有固定的存储单元,直到该程序结束。 程序设计中,使用静态数据结构可以解决不少实际问题,但也有不便之处。如建立一个大小未定的姓名表,随时要在姓名表中插入或删除一个或几个数据。而用新的数据类型指针类型。通过指针变量,可以在程序的执行过程中动态地建立变量,它的个数不再受限制,可方便高效地增加或删除若干数据,这比修改一个记录数组更加方便。,指针的定义及操作,(1)指针类型和指针变量 在Pascal中,指针变量(也称动态变量)存放某个存储单元的地址;也就是说, 指针变量指示某个存储单
2、元。 指针类型的格式为: 基类型 说明: 一个指针只能指示某一种类型数据的存储单元,这种数据类型就是指针的基类型。基类型可以是除指针、文件外的所有类型。例如,下列说明: type pointer=integer; var p1,p2 : pointer; 定义了两个指针变量p1和p2,这两个指针可以指示一个整型存储单元( 即p1、p2 中存放的是某存储单元的地址,而该存储单元恰好能存放一个整型数据 )。 和其它类型变量一样,也可以在var区直接定义指针型变量。 例如:var a : real;b : boolean; 又如:type person=record name : string20;
3、 sex : (maLe,femaLe); age : 1.100 end; var point : person;, Pascal规定所有类型都必须先定义后使用,但只有在定义指针类型时可以例外,如下列定义是合法的: type pointer=rec; /允许rec类型后定义 rec=record a : integer; b : char end; (2)开辟和释放动态存储单元 开辟动态存储单元 在Pascal中,指针变量的值一般是通过系统分配的,开辟一个动态存储单元必须调用标准过程new。 new过程调用的一般格式: new(指针变量) 功能:开辟一个存储单元,此单元能存放的数据的类型正好
4、是指针的基类型,并把此存储单元的地址赋给指针变量。,说明:1) 这实际上是给指针变量赋初值的基本方法。例如,设有说明:var p : integer; 这只定义了P是一个指示整型存储单元的指针变量,但这个单元尚未开辟,或者说P中尚未有值(某存储单元的首地址)。当程序中执行了语句new(p)才给赋值,即在内存中开辟(分配)一个整型变量存储单元,并把此单元的地址放在变量中。示意如下图:,(a)编译时给P分配空间,?表示值不定,(b)执行new(p)后生成新单元,新单元地址为XXXX,(c)(b)的简略表示,2) 一个指针变量只能存放一个地址。如再一次执行New(p)语句,将在内存中开辟另外一个新的
5、整型变量存储单元,并把此新单元的地址放在中,从而丢失了原存储单元的地址。 3) 当不再使用当前所指的存储单元时,可以通过标准过程Dispose释放该存储单元。, 释放动态存储单元 dispose语句的一般格式:dispose(指针变量) 功能:释放指针所指向的存储单元,使指针变量的值无定义。例如: new(p); dispose(p); (3)动态存储单元的引用 在给一个指针变量赋以某存储单元的地址后,就可以使用这个存储单元。 引用动态存储单元一般格式:指针变量 说明: 在用New过程给指针变量开辟了一个它所指向的存储单元后,要使用此存储单元的唯一方法是利用该指针。 对动态存储单元所能进行的操
6、作是该类型(指针的基类型)所允许的全部操作。,例8.1 设有下列说明: Var p : integer; i : integer; 画出执行下列操作后的内存示意图: New(p); P : =4; i : =p; 【分析】 如下图所示。,(4)对指针变量的操作 前已述及,对指针所指向的变量(如)可以进行指针的基类型所允许的全部操作。对指针变量本身,除可用New、Dispose过程外,尚允许下列操作: 具有同一基类型的指针变量之间相互赋值 例8.2 设有下列说明与程序段 : var p1,p2,p3 : integer; begin new(p1); new(p2); new(p3); p1 :
7、 =p2; /同一基类型的指针变量之间可以相互赋值 p2 : =p3; end;, 可以给指针变量赋nil值 nil是Pascal的关键字,它表示指针的值为空。例如,执行: p1 : =ni1后,p1的值是有定义的,但p1不指向任何存储单元。 可以对指针变量进行相等或不相等的比较运算 在实际应用中,通常可以在指针变量之间,或指针变量与nil之间进行相等(=)或不相等()的比较,比较的结果为布尔值。,例8.3 输入两个整数,按从小到大打印出来。 【分析】 不用指针类型可以很方便地编程,但为了示例指针的用法,我们利用指针类型。定义一个过程swap用以交换两个指针的值。 程序如下: Type poi
8、nter=integer; var p1,p2 : pointer; procedure swap(var q1,q2 : pointer); var q : pointer; begin q : =q1; q1 : =q2; q2 : =q; end; BEGIN new(p1); new(p2); readln(p1,p2); if p1p2 then swap(p1,p2); writeln(Output 2 data : ,p1 : 4,p2 : 4); END.,链表结构,1、单向链表的结构 由于单向链表的每个结点都有一个数据域和一个指针域,所以,每个结点都可以定义成一个记录。一般,
9、把head称为头结点,head.next称为头指针。比如,有如下一个单向链表,如何定义这种数据结构呢?方法如下:,type pointer=nodetype; nodetype=record data:datatype; next:pointer; /嵌套定义 end; var head,p,q,r:pointer;,2、单链表的建立、输出 下面结合一个例子,给出建立并输出单向链表的程序。 例8.4 从键盘输入若干个正整数,请按输入顺序建立一个单向链表并输出它,输入-1时表示结束。 Program creat; type pointer=nodetype; nodetype=record da
10、ta:integer; next:pointer; end; var head,p,r:pointer; /r指向链表的当前最后一个结点,可以称为尾指针 x:integer; begin writeln(please input num(-1 is end):); read(x); new(head); /申请头结点 head:=nil; /头结点初始化 r:=head;,while x-1 do /读入的数非-1 begin new(p); /则,申请一个新结点 p.data:=x; p.next:=nil; r.next:=p; /把新结点链接到前面的链表中,实际上r是 p的直接前趋 r:
11、=p; /尾指针后移一个 read(x); end; r.next:=nil; /最后一个结点的指针域赋空 writeln(output: ); /输出 p:=head.next; /头指针没有数据,只要从第一个结点开始 就可以了 while p.nextnil do begin write(p.data:4); p:=p.next; end; write(p.data:4); /最后一个结点的数据单独输出,也可以改用 REPEAT循环 readln; end.,为了充分利用空间和随时统计出链表的实际结点个数,我们经常把链表的实际结点个数存入到头结点的数据域(head.data)中,请大家改写
12、上面的程序,并输出最后的结点个数。参考程序见creat.pas。 3、查找“数据域满足一定条件的结点” (1)从前往后找到第一个满足条件的结点,程序如下: p:=headnext; while (p.data x) and (p.nextnil) do p:=p.next; 找到第一个就结束 if p.data = x then 找到了处理 else 输出不存在; (2)如果想找到所有满足条件的结点,则修改如下: p:=headnext; while p.nextnil do 一个一个判断 begin if p.data = x then 找到一个处理一个; p:=p.next; end;,4
13、、获取第i个结点的数据域 function get(head:pointer;i:integer):integer; var p:pointer;j:integer; begin p:=head.next; j:=1; while (pnil) and (j nil) and (j=i) then writeln(p.data) else writeln(i not exsit!); end;,5、插入一个结点到单链表中,一般情况:s.next:=p.next; p.next:=s; 特殊情况,插在表头:s.next:=head; head:=s; 插在表尾(假设p已是表尾):p.next:=
14、s; p:=s;,程序实现时,从表头开始找,是一致的。 procedure insert(head:pointer;i:integer;x:integer); /插入X到第i个元素之前 var p,s:pointer;j:integer; begin p:=head; j:=0; while (pnil) and (ji-1) then writeln(no this position!) else begin /插入 new(s); s.data:=x; s.next:=p.next; p.next:=s; end; end;,6、删除单向链表中的第i个结点(如下图中数据域为“b”的结点),
15、procedure delete(head:pointer;i:integer;); /删除第i个元素 var p,s:pointer;j:integer; begin p:=head; j:=0; while (p.nextnil) and (ji-1) then writeln(no this position!) else begin /删除p的后继结点,假设为s s:=p.next; p.next:=p.next.next; /或p.next:=s.next dispose(s); end; end;,7、求单向链表的实际长度 function len(head:pointer):integer; var n:integer; begin p:=head; n:=0; while p nil do begin n:=n+1; p:=p.next; end; len:=n; end;,双向链表,每个结点有两个指针域和若干数据域,其中一个指针域指向它的直接前趋结点,一个指向它的直接后继结点。它的优点是访问、插入、删除更方便,速度也