指针链表补充内容文档.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《指针链表补充内容文档.pdf》由会员分享,可在线阅读,更多相关《指针链表补充内容文档.pdf(14页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、指针与链表 程序中的变量一经说明,计算机操作系统就会在内存空间中分配相应的存贮单元,其中 变量名是存贮单元的地址,而变量的值是存贮单元的内容,且该存贮单元自始至终都被该变 量所占用,直到程序结束。如果变量是局部变量,那么在它的作用域内,一经说明也占有一 定的存贮单元,直到退出其作用域为止。这样的变量,在程序执行过程中,不能随时使用随 时分配存贮空间,也不能在程序执行的过程中,释放这些空间。也就是说,一旦给这些变量 分配存贮空间,无论程序是否还需要使用,它们都要占用一定的存贮空间,以便给用户存贮 数据。我们称具有这样特点的存贮为静态存贮,它所对应的变量称为静态变量。如字符类型、数组类型、记录类型
2、等。这类变量的优点是存贮方便,查找容易,可以通过一个简单的公式 随机存取表中的任一元素,逻辑关系上相邻的两个元素在物理位置上也是相邻的,很容易找 到前趋与后继元素;缺点是在线性表的长度不确定时,必须分配足够大的存储空间,经常浪 费了宝贵的存储资源;而线性表的容量一经定义确定后就难以扩充;在插入和删除线性表的 元素时,需要移动大量的元素,时间效率也比较差。2、动态存贮 在程序执行过程中,通过向操作系统申请存贮空间或释放存贮空间的命令,达到动态管 理计算机的存贮空间,以保证存贮空间的充分利用。存贮空间可以随时申请、随时释放,这 样的存贮方式称为动态存贮,其变量称为动态变量。指针变量即为动态变量。动
3、态存储所需要的空间可以是不连续的,这样有利于充分利用零散的小空间。但缺无法 用 O(1)的时间实现存取了。如何用这些零散的空间存储数组这些大规模数据呢?如何表 示这些数据之间的逻辑关系呢?为了表示这些物理存储单元之间的逻辑关系,对于每个数据 元素来说,除了要存储它本身的信息(数据域 data)外,还要存储它的直接后继元素的存 储位置(指针域,一般用 lin k 或 next 表示)。我们往往把这两部分信息合在一起称为一个“结点 node”。N 个结点链接在一起就构成了一个链表。N=0 时,称为空链表。同时,为了 按照逻辑顺序对链表中的元素进行各种操作,我们需要定义一个变量用来存储整个链表的第
4、一个结点的物理位置,这个变量称为“头指针,一般用 H 或 head 表示”。也可以把头指针定 义成一个结点,称为“头结点”,头结点的数据域可以不存储任何信息,也可以存储线性表 的长度等附加信息,头结点的指针域(头指针)存储指向第一个结点的指针,若线性表为空 表,则头结点的指针域为空(NIL)。由于最后一个元素没有后继,所以线性表中最后一个结 点的指针域为空(NIL)。由于此链表中的每个结点都只包含一个指针域,故称为“线性链表 或单向链表”。我们已经知道使用变量之前首先在说明部分对变量进行定义。然而,变量一经定义,编译系统就会给变量分配相应的内存空间。这种分配为静态存储分配。实际应用中,经常遇到
5、事先无法确定有多少数据要存储的情况,此时只能用动态存储机制。所谓动态存储,是事先不确定数据存储,在程序运行过程中根据实际需求动态申请所需存储空间,用完后及时将存储空间归还给系统。内存中的每一个存储单元都有个一编号,也就是“地址”。存储单元中存放的是各种类型的数据,也就是存储单元的“内容”。一个存储单元的“内容”的写入或是读出是根据存储单元的“地址”进行的。针对一个存储单元而言,“地址”和“内容”是两个不同的概念,必须区分清楚。另一方面,在计算机中,“地址”实际上就是一个整数,因此地址也可以看成一个“内容”,可以存储到另外一个存储单元中。这样,两个存储单元之间建立了一个联系。可见,“内容”和“地
6、址”的概念是相对的,“地址”可以理解成“内容”,“内容”也可以理解成“地址”,这主要取决与我们在理解时所处的“角度”。二、指针类型与指针变量 1指针类型和指针变量的说明 type 指针类型标识符=基类型名;基类型不能为文件类型 var 指针变量名:指针类型标识符;2申请存储单元 动态申请、空间大小由指针变量的基类型决定 new(指针变量名);PASCAL 标准过程 3指针变量的赋值 指针变量名:=NIL;初始化,暂时不指向任何存储单元 努力就有进步,坚持就能成功 如何表示和操作指针变量?不同于简单变量(如 A:=0;),PASCAL 规定用“指 针变 量名”的形 式引用指针变量(如 P:=0;
7、)。区分如下图所示:如计算机执行下面的程序段时:NEW(H);H:=123;NEW(H);H:=234;内存示意图如下(阴影部分表示该单元已被占用):4相同基类型的指针变量之间可以进行相互赋值。如有下面的程序段,可以画出右边的 示意图:var p1,p2:integer;new(p1);new(p2);p1:=90;p2:=80;p1:=p2;努力就有进步,坚持就能成功 5关系运算 如:if p1=p2 then while p nil do 6释放动态存储单元 dispose(指针变量名);系统收回指针变量所指的内存单元另作它用,此时指针变量的值变成无定义。注意,我 们应该养成一个好的习惯,
8、就是及时释放不用的动态存储单元,很多同学使用指针变量时就 知道 new(p),而不知道及时 dispose(p),最后造成内存空间溢出错误、出现死循环甚至死 机现象。三、单向链表 1、单向链表的结构 由于单向链表的每个结点都有一个数据域和一个指针域,所以,每个结点都可以定义 成一个记录。一般,把 head 称为头结点,head.next 称为头指针。比如,有如下一个单 向链表,如何定义这种数据结构呢?方法如下:type pointer=nodetype;nodetype=record data:datatype;next:pointer;递归定义 end;var head,p,q,r:poin
9、ter;2、单链表的建立、输出 下面结合一个例子,给出建立并输出单向链表的程序。例 1、从键盘输入若干个正整数,请按输入顺序建立一个单向链表并输出它,输入-1 时表 示结束。Program creat;type pointer=nodetype;nodetype=record data: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:=ni
10、l;头结点初始化 r:=head;while x-1 do 读入的数非-1 begin new(p);则,申请一个新结点 努力就有进步,坚持就能成功 p.data:=x;p.next:=nil;r.next:=p;把新结点链接到前面的链表中,实际上 r 是 p 的直接前趋 r:=p;尾指针后移一个 read(x);end;r.next:=nil;最后一个结点的指针域赋空 readln;writeln(output:);输出 p:=head.next;头指针没有数据,只要从第一个结点开始就可以了 while p.nextnil do begin write(p.data:4);p:=p.next
11、;end;write(p.data:4);最后一个结点的数据单独输出,也可以改用 REPEAT 循环 readln;end.为了充分利用空间和随时统计出链表的实际结点个数,我们经常把链表的实际结点个数 存入到头结点的数据域(head.data)中,请大家改写上面的程序,并输出最后的结点个 数。参考程序见 creat.pas。3、查找“数据域 满足一定条件的结点”(1)从前往后找到第一个满足条件的结点,程序如下:p:=headnext;while(p.data x)and(p.nextnil)do p:=p.next;找到第一个就结束 if p.data=x then 找到了处理 else 输出
12、不存在;(2)如果想找到所有满足条件的结点,则修改如下:p:=headnext;while p.nextnil do 一个一个判断 begin if p.data =x then 找到一个处理一个;p:=p.next;end;4、获取第 i 个结点的数据域 function get(head:pointer;i:integer):integer;var p:pointer;j:integer;begin p:=head.next;j:=1;while(pnil)and (ji)do begin p:=p.next;j:=j+1;end;if(p nil)and(j=i)then writeln
13、(p.data)else writeln(i not exsit!);end;努力就有进步,坚持就能成功 5、插入一个结点到单链表中 一般情况:s.next:=p.next;p.next:=s;特殊情况,插在表头:s.next:=head;head:=s;插在表尾(假设 p 已是表尾):p.next:=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)
14、and (ji-1)t hen writeln(no this position!)else begin 插入 new(s);s.data:=x;s.next:=p.next;p.next:=s;end;end;6、删除单向链表中的第 i 个结点(如下图中数据域为“b”的结点)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 be
15、gin 删除 p 的后继结点,假设为 s s:=p.next;p.next:=p.next.next;或 p.next:=s.next dispose(s);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;四、双向链表 每个结点有两个指针域和若干数据域,其中一个指针域指向它的直接前趋结点,一个指 向它的直接后继结点。它的优点是访问、插入、删除更方便,速度也快了。实质上是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 指针 补充 内容 文档
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内