pascal第8章 指针与链表.ppt

第八章指针与链表 前面介绍的各种简单类型的数据和构造类型的数据属于静态数据 在程序中 这些类型的变量一经说明 就在内存中占有固定的存储单元 直到该程序结束 程序设计中 使用静态数据结构可以解决不少实际问题 但也有不便之处 如建立一个大小未定的姓名表 随时要在姓名表中插入或删除一个或几个数据 而用新的数据类型 指针类型 通过指针变量 可以在程序的执行过程中动态地建立变量 它的个数不再受限制 可方便高效地增加或删除若干数据 这比修改一个记录数组更加方便 指针的定义及操作 1 指针类型和指针变量在Pascal中 指针变量 也称动态变量 存放某个存储单元的地址 也就是说 指针变量指示某个存储单元 指针类型的格式为 基类型说明 一个指针只能指示某一种类型数据的存储单元 这种数据类型就是指针的基类型 基类型可以是除指针 文件外的所有类型 例如 下列说明 typepointer integer varp1 p2 pointer 定义了两个指针变量p1和p2 这两个指针可以指示一个整型存储单元 即p1 p2中存放的是某存储单元的地址 而该存储单元恰好能存放一个整型数据 和其它类型变量一样 也可以在var区直接定义指针型变量 例如 vara real b boolean 又如 typeperson recordname string 20 sex maLe femaLe age 1 100end varpoint person Pascal规定所有类型都必须先定义后使用 但只有在定义指针类型时可以例外 如下列定义是合法的 typepointer rec 允许rec类型后定义rec recorda integer b charend 2 开辟和释放动态存储单元 开辟动态存储单元在Pascal中 指针变量的值一般是通过系统分配的 开辟一个动态存储单元必须调用标准过程new new过程调用的一般格式 new 指针变量 功能 开辟一个存储单元 此单元能存放的数据的类型正好是指针的基类型 并把此存储单元的地址赋给指针变量 说明 1 这实际上是给指针变量赋初值的基本方法 例如 设有说明 varp integer 这只定义了P是一个指示整型存储单元的指针变量 但这个单元尚未开辟 或者说P中尚未有值 某存储单元的首地址 当程序中执行了语句new p 才给 赋值 即在内存中开辟 分配 一个整型变量存储单元 并把此单元的地址放在变量 中 示意如下图 a 编译时给P分配空间 表示值不定 b 执行new p 后生成新单元 新单元地址为XXXX c b 的简略表示 2 一个指针变量只能存放一个地址 如再一次执行New p 语句 将在内存中开辟另外一个新的整型变量存储单元 并把此新单元的地址放在 中 从而丢失了原存储单元的地址 3 当不再使用 当前所指的存储单元时 可以通过标准过程Dispose释放该存储单元 释放动态存储单元dispose语句的一般格式 dispose 指针变量 功能 释放指针所指向的存储单元 使指针变量的值无定义 例如 new p dispose p 3 动态存储单元的引用在给一个指针变量赋以某存储单元的地址后 就可以使用这个存储单元 引用动态存储单元一般格式 指针变量 说明 在用New过程给指针变量开辟了一个它所指向的存储单元后 要使用此存储单元的唯一方法是利用该指针 对动态存储单元所能进行的操作是该类型 指针的基类型 所允许的全部操作 例8 1设有下列说明 Varp integer i integer 画出执行下列操作后的内存示意图 New p P 4 i p 分析 如下图所示 4 对指针变量的操作前已述及 对指针所指向的变量 如 可以进行指针的基类型所允许的全部操作 对指针变量本身 除可用New Dispose过程外 尚允许下列操作 具有同一基类型的指针变量之间相互赋值例8 2设有下列说明与程序段 varp1 p2 p3 integer beginnew p1 new p2 new p3 p1 p2 同一基类型的指针变量之间可以相互赋值p2 p3 end 可以给指针变量赋nil值nil是Pascal的关键字 它表示指针的值为 空 例如 执行 p1 ni1后 p1的值是有定义的 但p1不指向任何存储单元 可以对指针变量进行相等或不相等的比较运算在实际应用中 通常可以在指针变量之间 或指针变量与nil之间进行相等 或不相等 的比较 比较的结果为布尔值 例8 3输入两个整数 按从小到大打印出来 分析 不用指针类型可以很方便地编程 但为了示例指针的用法 我们利用指针类型 定义一个过程swap用以交换两个指针的值 程序如下 Typepointer integer varp1 p2 pointer procedureswap varq1 q2 pointer varq pointer beginq q1 q1 q2 q2 q end BEGINnew p1 new p2 readln p1 p2 ifp1 p2 thenswap p1 p2 writeln Output2data p1 4 p2 4 END 链表结构 1 单向链表的结构由于单向链表的每个结点都有一个数据域和一个指针域 所以 每个结点都可以定义成一个记录 一般 把head称为头结点 head next称为头指针 比如 有如下一个单向链表 如何定义这种数据结构呢 方法如下 typepointer nodetype nodetype recorddata datatype next pointer 嵌套定义end varhead p q r pointer 2 单链表的建立 输出下面结合一个例子 给出建立并输出单向链表的程序 例8 4从键盘输入若干个正整数 请按输入顺序建立一个单向链表并输出它 输入 1时表示结束 Programcreat typepointer nodetype nodetype recorddata integer next pointer end varhead p r pointer r指向链表的当前最后一个结点 可以称为尾指针x integer beginwriteln pleaseinputnum 1isend read x new head 申请头结点head nil 头结点初始化r head whilex 1do 读入的数非 1beginnew p 则 申请一个新结点p data x p next nil r next p 把新结点链接到前面的链表中 实际上r是p的直接前趋r p 尾指针后移一个read x end r next nil 最后一个结点的指针域赋空writeln output 输出p head next 头指针没有数据 只要从第一个结点开始就可以了whilep nextnildobeginwrite p data 4 p p next end write p data 4 最后一个结点的数据单独输出 也可以改用REPEAT循环readln end 为了充分利用空间和随时统计出链表的实际结点个数 我们经常把链表的实际结点个数存入到头结点的数据域 head data 中 请大家改写上面的程序 并输出最后的结点个数 参考程序见creat pas 3 查找 数据域满足一定条件的结点 1 从前往后找到第一个满足条件的结点 程序如下 p head next while p datax and p nextnil dop p next 找到第一个就结束 ifp data xthen找到了处理else输出不存在 2 如果想找到所有满足条件的结点 则修改如下 p head next whilep nextnildo 一个一个判断 beginifp data xthen找到一个处理一个 p p next end 4 获取第i个结点的数据域functionget head pointer i integer integer varp pointer j integer beginp head next j 1 while pnil and jnil and j i thenwriteln p data elsewriteln inotexsit end 5 插入一个结点到单链表中 一般情况 s next p next p next s 特殊情况 插在表头 s next head head s 插在表尾 假设p已是表尾 p next s p s 程序实现时 从表头开始找 是一致的 procedureinsert head pointer i integer x integer 插入X到第i个元素之前varp s pointer j integer beginp head j 0 while pnil and ji 1 thenwriteln nothisposition elsebegin 插入new s s data x s next p next p next s end end 6 删除单向链表中的第i个结点 如下图中数据域为 b 的结点 proceduredelete head pointer i integer 删除第i个元素varp s pointer j integer beginp head j 0 while p nextnil and ji 1 thenwriteln nothisposition elsebegin 删除p的后继结点 假设为ss p next p next p next next 或p next s nextdispose s end end 7 求单向链表的实际长度functionlen head pointer integer varn integer beginp head n 0 whilepnildobeginn n 1 p p next end len n end 双向链表 每个结点有两个指针域和若干数据域 其中一个指针域指向它的直接前趋结点 一个指向它的直接后继结点 它的优点是访问 插入 删除更方便 速度也快了 实质上是以空间换时间 数据结构的定义 typepointer nodetype nodetype recorddata datatype pre next pointer pre指向前趋 next指向后继end varhead p q r pointer 下面给出双向链表的插入和删除过程 Proceduredelete head pointer i integer 删除双向链表的第i个结点Varp pointer j integer BeginP head j 0 while p nextnil and j i dobeginp p next j j 1 end p指向第i个结点ifp nilthenwriteln nothisposition elsebegin 将结点P删除p pre next p next P的前趋结点的后继赋值为P的后继p next pre p pre P的后继结点的前趋赋值为P的前趋end End Procedureinsert head pointer i x integer 在双向链表的第i个结点之前插入XVars p pointer j integer BeginNew s S data x P head j 0 while p nextnil and j i dobeginp p next j j 1 end p指向第i个结点ifp nilthenwriteln nothisposition elsebegin 将结点S插入到结点P之前s pre p pre 1 将S的前趋指向P的前趋p pre s 2 将S作为P的新前趋s next p 3 将S的后继指向Pp pre next s 4 将P的本来前趋结点的后继指向Send End 循环链表 1 单向循环链表 最后一个结点的指针指向头结点 2 双向循环链表 最后一个结点的后继指针指向头结点 且头结点的前趋指针指向最后一个结点 循环链表的应用举例 例8 5约瑟夫问题 问题描述 有n只猴子 按顺时针方向围成一圈 开始时编号为1 2 n 选大王 从第1号猴子开始报数1 2 3 数到m号时该猴子退出到圈外 如此报数直到圈内只剩下一只猴子时 此猴便是大王 你的任务是从键盘读入n m 程序判断输出最后的大王是几号 如输入 135输出 6换个问法 n只猴子围成一个圈 按顺时针方向报数 报到m的出圈 直到剩下一只猴子结束 输出猴子依次出圈的序号 样列输入 135 样列输出 5102819413123711thekingis 6 算法分析 很明显这是一个单向循环链表 数据域为猴子的编号 指针域为下一个猴子的地址 从第1个猴子开始一一报数 报数实际上是计数 只要设一个计数器就可以了 当计数器由1变化到m时 删除该结点 从下一个结点开始继续计数 计数器回1或者用求余运算 直到链表中只剩下一个结点 参考程序一 programking typepoint node node recorddata integer next point end varm n i integer p q head point beginwrite inputn m readln n m new head q head head data 1 fori 2tondobeginnew q next q q next q data i end q next head i 1 q head repeatp q next i i 1 ifimodm 0thenbeginq next p next writeln p data 4 dispose p endelseq puntilq next q writeln thekingis q data end 参考程序二 programex11 6b typepointer node node recordval integer next pointerend varptr ptb pointer i j n m integer beginreadln n m new ptb ptb val 1 ptr ptb 申请第1个结点fori 2tondobeginnew ptr next ptr ptr next 申请第2到n结点ptr val i end ptr next ptb j 0 第n结点指针指向第1个结点 repeati 1 repeat 报数 报到m人出列 ptr ptb ptb ptb next i i 1 untili m write ptb val 2 ptb ptb next ptr next ptb j j 1 将m结点驱出链表 untilj n 1 直到n个人均出队为止 writeln ptb val 4 end 上机练习 1 狐狸捉兔子 问题描述 围绕着山顶有10个洞 一只兔子和一只狐狸各住一个洞 狐狸总想吃掉兔子 一天兔子对狐狸说 你想吃我有一个条件 第一次隔一个洞找我 第二次隔两个洞找我 以后依次类推 次数不限 若能找到我 你就可以饱餐一顿 在没找到我之前不能停止 狐狸一想只有1