《【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;,双向链表,每个结点有两个指针域和若干数据域，其中一个指针域指向它的直接前趋结点，一个指向它的直接后继结点。它的优点是访问、插入、删除更方便，速度也
