第2讲_线性数据结构(一)顺序表_线性链表_.ppt

第1页 123 第2单元线性数据结构 一 教学目标 了解数据结构的有关概念什么是线性DS 线性表 了解线性DS的特点 了解线性DS的逻辑结构 物理结构以及操作 第2页 123 学习要求 通过本单元的学习 了解并掌握 有关数据结构 DS 的基本概念数据元素 DS 逻辑结构 物理结构 DS的分类及特点 算法 时间复杂度等 线性DS的常用存储结构顺序 链表 索引 散列存储结构单向 双向 循环链表等 线性DS的有关算法增 删 改 第3页 123 涉及的章节 第2章的2 1数据结构概述 P22 P24 2 2线性表 P25 P34 第4页 123 数据结构问题的由来 计算机求解问题过程步骤 实际问题求解问题模型算法 分析抽象 模型求解 命令编程 调试程序 编制程序 运行程序 求解结果 结果输出 用户需求 数据类型 格式 逻辑结构 数据逻辑运算 数据的物理操作 第5页 123 问题模型 结构分析 线性方程组人口预报 微分方程优化问题 线性规划 非线性规划振动问题 矩阵分析 特征值 特征向量信息管理 二维数据表下棋 人工智能 树型结构 交通管理 最佳道路选择 图型结构 第6页 123 一 基本概念P22 数据 Data 是信息的载体 它可以用计算机表示并加工 如数 字符 符号等的集合 数据元素 DataElement 是数据的基本单位 数据集合中的个体 数据对象 DataObject 具有相同性质的数据元素的集合 数据结构 DataStructure 是指同一数据对象中各数据元素间存在的关系 它有三个要素 DS 数据的逻辑结构 存储结构 数据的运算数据结构是以数据为加工对象 研究数据组织方式和相关操作方法的学问 也可以说 怎样去组织一批特定的数据 第7页 123 数据结构分类 线性表栈队列串数组 树二叉树图 线性结构 非线性结构 数据结构DS 第8页 123 1 数据的逻辑结构 它是描述数据间的顺序 逻辑 关系 只是抽象地反映数据元素的结构 而不管它们在计算机中如何存放 一般用下列二元组来描述 DS D R 其中 D 是数据元素的有限集合 R 是数据元素之间关系的集合 第9页 123 举例 课题组由1名教师 1 3名研究生 1 6名本科生组成 成员关系是 教师指导研究生 研究生指导1 2名本科生 定义DS如下 Group D R 其中 D T G1 Gn S11 Snm 1 n 3 1 m 2R R1 R2 R1 1 i n 1 n 3 R2 1 i n 1 j m 1 n 3 1 m 2 第10页 123 2 数据的存储结构 又称物理结构是指数据结构在计算机中的表示 又称映象 即数据在计算机中的存放 第11页 123 逻辑结构和物理结构的关系 数据的逻辑结构是从逻辑关系 某种顺序 上观察数据 它是独立于计算机的 可以在理论上 形式上进行研究 推理 运算等各种操作 数据的存储结构是逻辑结构在计算机中的实现 是依赖于计算机的 离开了机器 则无法进行任何操作 任何一个算法的设计取决于选定的逻辑结构 而算法的最终实现依赖于采用的存储结构 第12页 123 数据存储结构分类 顺序存储结构链式存储结构索引存储结构散列存储结构 第13页 123 顺序存储结构 把数据元素按某种顺序存放在一块连续的存储单元中的存储形式 数据结点结构 特点 连续存放 逻辑上相邻 物理上也相邻 结构简单 易实现 插入 删除操作不便 需大量移动元素 d1d2 dn 数据域 第14页 123 链式存储结构 以链表形式将数据元素存放于任意存储单元中 可连续存放 也可以不连续存放 以指针实现链表间的联系 数据结点结构 特点 非连续存放 借助指针来表示元素间的关系 插入 删除操作简单 只要修改指针即可 结构较复杂 需要额外存储空间 d1 d2 dn 数据域指针域 第15页 123 散列存储结构 在数据元素与存储位置之间建立一种存储关系F 根据这种关系F 已知元素E 就可以得到它的存储地址 即D F E 哈希查找中的哈希表就是这样一种存储结构 特点 数据元素间无内在联系 存储形式不定 索引存储除建立存储结点信息外 还建立附加的索引表来标识结点的地址 索引表由若干索引项组成 如果每个节点在索引表中都有一个索引项 则该索引表就被称为稠密索引 若一组节点在索引表中只对应于一个索引项 则该索引表就成为稀疏索引 索引项的一般形式一般是关键字 地址 第16页 123 3 数据运算 数据运算是指对存放在物理结构上的数据 按定义的逻辑结构进行的各种操作 常见操作有 输入 插入 删除 查找 修改 排序等 第17页 123 4 算法与算法分析 算法 Algorithm 是对特定问题求解步骤的一种描述 是一组指令的有限集合 算法和数据结构的关系P23下为了充分地利用系统资源 既要效率高 速度快 又要存储空间少 显然 这是矛盾的 研究算法追求的目标是 时间和空间的适当和谐 第18页 123 算法的特性 有穷性一个算法必须总是在执行有穷步后结束 且每一步都可在有穷时间内完成 确定性算法中的每一个指令必须有明确的含义 不能有二义性 可行性算法中描述的操作都是可通过已经实现的基本运算 执行有限次实现的 输入一个算法应有0个或多个输入 输出一个算法应有1个或多个输出 第19页 123 算法的设计要求 正确性 Correctness 可读性 Readability 健壮性 Robustness 高效率与低存储量 第20页 123 1 算法中对数据的运算和操作 算术运算 加减乘除 逻辑运算 与或非 关系运算 大于 小于 等于 不等于 数据传输 赋值 输入 输出等 2 算法的控制结构 算法的基本要素 第21页 123 1 符号与表达式loop i i 1 设x是A中的最大项 其中A是一个数组 将x插入到L之中 其中L是某个表 算法描述语言中 关系运算符用 逻辑运算符用and 与 or 或 not 非 算法描述语言 第22页 123 2 赋值语句a ea ba b e 第23页 123 3 控制转移语句无条件转移语句GOTO标号条件转移语句IFCTHENS或IFCTHENS1ELSES2 第24页 123 4 循环语句WHILE语句WHILECDOS功能等价于如下的IF语句 loop IFCTHEN SGOTOloop 第25页 123 FORi initTOlimitBYstepDOSFORi initTOlimitDOS当step 0时 功能等价于如下的IF语句 i initloop IFi limitTHEN Si i stepGOTOloop FOR语句 第26页 123 当step 0时 功能等价于如下的IF语句 i initloop IFi limitTHEN Si i stepGOTOloop 第27页 123 5 其他语句EXITRETURNREAD 或INPUT WRITE 或PRINT 或OUTPUT 第28页 123 1 算法中的注释用 括起来 2 几个短的语句可以写在同一行上 但彼此之间要用分号隔开 3 复合语句总是用一对花括号 括起来作为语句组 4 有时为了叙述方便 对算法中的每一行可加上行号 注 需要说明的几点 第29页 123 1 列举法根据提出的问题 列举所有可能的情况 并用问题中给定的条件检验哪些是需要的 哪些是不需要的 因此 列举法常用于解决 是否存在 或 有多少种可能 等类型的问题 例如求解不定方程的问题 算法设计基本方法 第30页 123 例设每只母鸡值3元 每只公鸡值2元 两只小鸡值1元 现要用100元钱买100只鸡 设计买鸡方案 假设买母鸡I只 公鸡J只 小鸡K只 第31页 123 FORI 0TO100DOFORJ 0TO100DOFORK 0TO100DO M I J KN 3I 2J 0 5KIF M 100 and N 100 THENOUTPUTI J K RETURN总循环次数为1013 算法1 第32页 123 FORI 0TO33DOFORJ 0TO50 1 5IDO K 100 I JIF 3I 2J 0 5K 100 THENOUTPUTI J K RETURN总循环次数为 算法2 第33页 123 首先 考虑到母鸡为3元一只 因此 最多只能买33只母鸡 即算法1中的外循环只需要从0到33就可以了 没有必要从0到100 其次 考虑到公鸡为2元一只 因此 最多只能买50只公鸡 又考虑到对公鸡的列举是在算法的第二层循环中 且买一只母鸡的价钱相当于买1 5只公鸡 因此在第一层循环中已确定买I只母鸡的情况下 公鸡最多只能买50 1 5I只 即第二层中对J的循环只要从0到50 1 5I就可以了 最后 考虑到总共买100只鸡 因此 在第一层循环中已确定买I只母鸡 且第二层已确定买J只鸡的情况下 买小鸡的数量只能是K 100 I J 即第三层的循环已没有必要了 并且 在这种情况下 条件I J K 100自然已经满足 第34页 123 include stdio h main inti j k for i 0 i 33 i for j 0 j 50 1 5 i j k 100 i j if 3 i 2 j 0 5 k 100 0 printf 5d 5d 5d n i j k 第35页 123 运行结果如下 2306852570820721115741410761757820080 第36页 123 2 归纳法通过列举少量的特殊情况 经过分析 最后找出一般的关系 3 递推从已知的初始条件出发 逐次推出所要求的各中间结果和最后结果 算法设计基本方法 第37页 123 例 第38页 123 第39页 123 第40页 123 第41页 123 4 递归将一个复杂的问题归结为若干个较简单的问题 然后将这些较简单的每一个问题再归结为更简单的问题 这个过程可以一直做下去 直到最简单的问题为止 注意 这种逐层分解实际上并没有对问题进行求解 而只是当解决了最简单的问题后 再沿着原来逆分解的过程逐步进行综合 这就是递归的基本思想 算法设计基本方法 第42页 123 编写一个过程 对于输入的参数n 依次打印输出自然数1到n PROCEDUREWRT n FORk 1TOnDOOUTPUTkRETURN include stdio h wrt intn intk for k 1 k n k printf d n k return 例 第43页 123 PROCEDUREWRT1 n IF n 0 THEN WRT1 n 1 OUTPUTn RETURN include stdio h wrt1 intn if n 0 wrt1 n 1 printf d n n return 输出自然数1到n的递归算法 第44页 123 5 减半递推技术所谓 减半 是指将问题的规模减半 而问题的性质不变 所谓 递推 是指重复 减半 的过程 算法设计基本方法 第45页 123 第46页 123 第47页 123 第48页 123 第49页 123 二分法求方程实根的减半递推过程 首先取给定区间的中点c a b 2 然后判断f c 是否为0 若f c 0 则说明c即为所求的根 求解过程结束 如果f c 0 则根据以下原则将原区间减半 若f a f c 0 则取原区间的前半部分 若f b f c 0 则取原区间的后半部分 最后判断减半后的区间长度是否已经很小 若 a b 则过程结束 取 a b 2为根的近似值 若 a b 则重复上述的减半过程 例 设方程f c 0在区间 a b 上有实根 且f a 与f b 异号 利用二分法求该方程的实根 第50页 123 FUNCTIONROOT a b eps f f0 f a WHILE a b DO c a b 2 f1 f c IF f1 0 THEN ROOT c RETURN IF f0 f1 0 THENa cELSEb c c a b 2 ROOT cRETURN 第51页 123 include stdio h include math h doubleroot a b eps f doublea b eps f doublef0 f1 c f0 f a while fabs a b eps c a b 2 f1 f c if f1 0 return c if f0 f1 0 a c elseb c c a b 2 return c 第52页 123 6 回溯法通过对问题的分析 找出一个解决问题的线索 然后沿着这个线索逐步试探 对于每一步的试探 若试探成功 就得到问题的解 若试探失败 就逐步回退 换别的路线再进行试探 算法设计基本方法 第53页 123 由n2个方块排成n行n列的正方形称为 n元棋盘 如果两个皇后位于棋盘上的同一行或同一列或同一对角线上 则称它们为互相攻击 现要求找使n元棋盘上的n个皇后互不攻击的所有布局 例 求解皇后问题 第54页 123 八皇后问题是一个古老而著名的问题 是回溯算法的典型例题 该问题是十九世纪著名的数学家高斯1850年提出 在8X8格的国际象棋上摆放八个皇后 使其不能互相攻击 即任意两个皇后都不能处于同一行 同一列或同一斜线上 问有多少种摆法 高斯认为有76种方案 1854年在柏林的象棋杂志上不同的作者发表了40种不同的解 后来有人用图论的方法解出92种结果 第55页 123 方法一 每个皇后在一行 做个8重循环 把每个皇后安排在每行的每个位置都试一遍 1 棋盘是8 8数组 定义9个空棋盘 2 第一个皇后从1行1列到1行8列循环 复制一个空棋盘到棋盘1 在皇后能控制的点上做上标记 3 第二个皇后从2行1列到2行8列循环 若本点是前面标注了的被控制点 则此点不能放棋子 若有地方安排 将棋盘1复制到棋盘2 在棋盘2上将本皇后能控制的点上做上标记 4 第三个皇后从3行1列到3行8列循环 若本点是前面标注了的被控制点 则此点不能放棋子 若有地方安排 将棋盘2复制到棋盘3 在棋盘3上将本皇后能控制的点上做上标记 到第8重循环 若8个皇后都有地方安排 则这是八后问题的一个解 8重循环结束 得八后问题的所有解 第56页 123 方法二 循环实现 用一个8位的8进制数表示棋盘上皇后的位置 比如 45615353表示 第0列皇后在第4个位置 第1列皇后在第5个位置 第2列皇后在第6个位置 第7列皇后在第3个位置 循环变量从00000000加到77777777 8进制数 的过程 就遍历了皇后所有的情况 程序中用八进制数用一个一维数组data 表示 第57页 123 方法三 递归循环 分别一一测试每一种摆法 直到得出正确的答案 主要解决以下几个问题 1 冲突 包括行 列 两条对角线 1 列 规定每一列放一个皇后 不会造成列上的冲突 2 行 当第I行被某个皇后占领后 则同一行上的所有空格都不能再放皇后 要把以I为下标的标记置为被占领状态 3 对角线 对角线有两个方向 在同一对角线上的所有点 设下标为 i j 要么 i j 是常数 要么 i j 是常数 因此 当第I个皇后占领了第J列后 要同时把以 i j i j 为下标的标记置为被占领状态 如果有一个Q为chess i j 则不安全的地方是k行j位置 j k i位置 j k i位置 第58页 123 2 数据结构 1 解数组A A I 表示第I个皇后放置的列 范围 1 8 2 行冲突标记数组B B I 0表示第I行空闲 B I 1表示第I行被占领 范围 1 8 3 对角线冲突标记数组C D C I J 0表示第 I J 条对角线空闲 C I J 1表示第 I J 条对角线被占领 范围 7 7D I J 0表示第 I J 条对角线空闲 D I J 1表示第 I J 条对角线被占领 范围 2 16 第59页 123 3算法 数据初始化 从n列开始摆放第n个皇后 因为这样便可以符合每一竖列一个皇后的要求 先测试当前位置 n m 是否等于 未被占领 如果是 摆放第n个皇后 并宣布占领 记得要横列竖列斜列一起来 接着进行递归 如果不是 测试下一个位置 n m 1 但是如果当n8时 便一一打印出结果 第60页 123 方法四 回溯法假设棋盘上的每一行放置一个皇后 分别用自然数进行编号为1 2 n 首先定义一个长度为n的一维数组q 其中每一个元素q i i 1 2 n 随时记录第i行上的皇后所在的列号 初始时 先将各皇后放在各行的第1列 即数组q的初值为q i 1 i 1 2 n第i行与第j行上的皇后在某一对角线上的条件为 q i q j i j 而它们在同一列上的条件为q i q j 第61页 123 回溯法的步骤如下 从第一行 即i 1 开始进行以下过程 设前i 1行上的皇后已经布局好 即它们均互不攻击 现在考虑安排第i行上的皇后的位置 使之与前i 1行上的皇后也都互不攻击 为了实现这一目的 可以从第i行皇后的当前位置q i 开始按如下规则向右进行搜索 第62页 123 若q i n 1 将第i个皇后放在第1列 即置q i 1 且回退一行 考虑重新安排第i 1行上的皇后与前i 2行上的皇后均互不攻击的下一个位置 此时如果已退到第0行 实际没有这一行 则过程结束 若q i n 则需检查第i行上的皇后与前i 1行的皇后是否互不攻击 若有攻击 则将第i行上的皇后右移一个位置 即置q i q i 1 重新进行这个过程 若无攻击 则考虑安排下一行上的皇后位置 即置i i 1 若当前安排好的皇后是在最后一行 即第n行 则说明已经找到了n个皇后互不攻击的一个布局 将这个布局输出 即输出q i i 1 2 n 然后将第n行上的皇后右移一个位置 即置q n q n 1 重新进行这个过程 以便寻找下一个布局 第63页 123 PROCEDUREQUEEN n 定义长度为n的数组存储空间q FORi 1TOnDOq i 1i 1loop IF q i n THEN k 1WHILE k i and q k q i q k q i k i 0 DOk k 1IF k i THENq i q i 1 回溯法求解皇后问题 第64页 123 ELSE i i 1IF i n THEN OUTPUTq i i 1 2 n q n q n 1i n 第65页 123 ELSE q i 1i i 1IF i 1 THENRETURNq i q i 1 GOTOloopRETURN 第66页 123 include stdio h include math h include stdlib h voidqueen intn inti j k jt q q malloc n sizeof int for i 0 i n i q i 0 i 0 jt 1 printf n printf dqueenproblem n n 第67页 123 while jt 1 if q i n k 0 while k i q k q i fabs q k q i fabs k i 0 k k 1 if k i q i q i 1 else i i 1 if i n 1 for j 0 j n j printf 5d q j 1 第68页 123 printf n q n 1 q n 1 1 i n 1 else q i 0 i i 1 if i 0 printf n free q return q i q i 1 第69页 123 第70页 123 第71页 123 第72页 123 第73页 123 第74页 123 算法的描述 算法的描述方式 常用的 自然语言流程图特定的表示算法的图形符号算法描述伪语言包括程序设计语言的三大基本结构 顺序 选择 循环 及自然语言的一种语言 软件工程 类语言类似高级语言的语言 例如 类PASCAL 类C语言 本书采用一种接近高级语言的算法描述语言 第75页 123 算法的评价 算法评价的标准 时间复杂度和空间复杂度 时间复杂度指在计算机上运行该算法所花费的时间 用 O 数量级 来表示 称为 阶 常见的时间复杂度有 O 1 O logn O n O n2 常量型对数型线性型平方型空间复杂度指算法在计算机上运行所占用的存储空间 度量同时间复杂度 P25 第76页 123 时间复杂度举例 a X X 1 O 1 b FORI 1TOnDOX X 1 O n c FORI 1TOnDOFORJ 1TOnDOO n2 X X 1 第77页 123 二 线性表 是指数据元素之间的关系为一一对应的线性关系的数据结构 例如 一星期七天的英文缩写表示 Sun Mon The wed Thu Fri Sat 是一个线性表 其中的元素是字符串 表的长度为7 线性表虽然简单 但是应用范围非常广泛 第78页 123 一 线性表的逻辑结构 定义 线性表是n n 0 个元素a1 a2 an的有限序列 表中每个数据元素 除了第1个和最后1个外 有且仅有一个前趋元素和后继元素 形式定义 含有n个数据元素的线性表是一种数据结构 表示为 Linear list D R 其中 D a1 a2 an R ai 1 ai D i 2 n D是数据元素的有限集合 R是D上逻辑关系的有限集合 第79页 123 相互关系描述 1 L的长度为n n 0 当n为0时 表示是空表 2 每个元素 除了第1个和最后一个元素外 有唯一的前趋和后继 3 线性表中各元素间存在着线性关系 4 均匀性 各元素数据类型必须相同 5 有序性 各元素是有序的 不可交换次序 第80页 123 线性表的基本操作 Setnull L 置空表Length L 求表长度 求表中元素个数Get L i 取表中第i个元素 1 i n Prior L i 取i的前趋元素Next L i 取i的后继元素Locate L x 返回指定元素在表中的位置Insert L i x 插入元素Delete L x 删除元素Empty L 判别表是否为空 第81页 123 二 线性表的顺序存储结构 将线性表中元素一个接一个的存入一组连续的存储单元中 这种存储结构是顺序结构 采用顺序存储结构的线性表简称为 顺序表 顺序表的存储特点是 只要确定了起始位置 表中任一元素的地址都通过下列公式得到 adr ai adr a1 i 1 L1 i n其中 L是每个元素占用存储单元的长度 第82页 123 线性表元素存储示意图 a1 a2 ai 元素序号内存状态存储地址 1 2 i adr a1 adr a1 1 adr a1 i 1 第83页 123 算法1 1插入算法 算法步骤 将x插入表中第i个位置 step1将第n至第i个元素后移一个存储位置 step2将x插入到ai 1之后 step3表的长度 1 线性表采用一维数组存放 C语言描述为 defineMAXLENGTH100intlist MAXLENGTH intlast last指示表中最后一个元素的序号 后续课件中涉及到C语言描述和具体C语言程序部分仅供参考 x 第85页 123 算法1 1插入算法 insert inti intx intk if last MAXLENGTH printf 线性表已满 n exit 1 if ilast 1 插入位置 元素序号 printf 插入位置错误 n exit 2 else for k last 1 K i 1 k list k 1 list k 数组下标0 n 1 list i 1 x last 第86页 123 算法1 1插入算法主程序参考 defineMAXLENGTH100 例1 1主程序 intlist MAXLENGTH 5 3 1 10 7 8 1 4 intlast 8 main intx j loc printf Enterx loc n scanf d d 第87页 123 算法1 2 线性表删除算法 算法步骤 删除表中位置为i的数据 step1判别指定的位置是否合法 step2若合法 则将位置i 1至n上的元素前移一个存储位置 step3表的长度 1 线性表采用一维数组存放 C语言描述为 defineMAXLENGTH100intlist MAXLENGTH intlast last指示表中最后一个元素的序号 第88页 123 算法1 2 线性表删除算法 delete inti intk if ilast printf 表中不存在位置为i的元素 n exit 1 for k i 1 k last 1 k list k last k 1 last 第90页 123 算法1 2 线性表删除算法主程序 defineMAXLENGTH100 例1 2主程序 intlist MAXLENGTH 5 3 1 10 7 8 1 4 intlast 8 main intj loc printf Enterloc n scanf d 第91页 123 顺序存储结构的特点 数据连续存放 随机存取 P26L 5 逻辑上相邻 物理上也相邻存储结构简单 易实现插入 删除操作不便存储密度大 空间利用率高结论 顺序存储结构适合于表中元素变动较少的情况 第92页 123 三 线性表的链式存储结构 线性表的顺序存储结构容易实现 可以随机存取表中的任意元素 P26L 5 顺序表缺点是 难于插入 删除操作 需要预先分配空间 不管这些空间能否最大限度地利用 链表存储结构在这两个方面恰好是优点 容易插入 删除操作不需要预分空间 第93页 123 1 链表有关基本概念 结点 NODE 表中元素的存储单元 链表存储结构形式为 链表结构的C语言描述为 structnode intdata structnode next typedefstructnodeNODE datanext 数据域指针域 第94页 123 链表 Link 由结点组成的表 头指针 head 指向链表中第1个结点的指针 首元结点第一个结点 a1 头结点为方便操作 在头指针和首元结点之间设置的结点 基本概念 head a1 头指针 头结点 首元结点 ai 第i个结点 第95页 123 表示形式的统一 空表和非空表表示形式在头结点上得到统一空表的形式 head next NULL非空表的形式 head next Address head 头结点 head 头结点 3种写法 head next head next next head head所指向结点的next域 第96页 123 表示形式不统一 若没有头结点 空表和非空表的表示形式将不统一 空表形式 head NULL非空表形式 head next address head head a1 第97页 123 链表举例 由食品组成的单链表 biscuit butter cheese eggs grapes jam 不带头结点 biscuit butter cheese jam grapes eggs head 头指针 第98页 123 单链表在存储区的物理状态 Grapes60 biscuit61 cheese13 eggs1 jamNULL butter12 存储地址数据域 data 指针域 next 11112136061 11 头指针head 逻辑上相邻 物理上不相邻 第99页 123 2 单链表的操作 指针的基本操作单链表的查找get单链表的插入insert单链表的删除delete 第100页 123 指针的基本操作 设指针变量p q的定义为 NODE p q 对链表的操作实际上是对指针的操作 例如 要删除结点ai 首先要使指针p指向ai 即 a1 head ai an p 第101页 123 指针的基本操作列表 p NODE malloc sizeof NODE 申请一个NODE型结点空间 并将该结点的地址送入p中 free p 释放p指针所指结点的空间p q指针p指向指针q所指的结点p q next指针p指向指针q所指结点的后继p p next指针p向后移动一个结点p next q将指针q所指结点改接为指针p所指结点的后继p next NULL将指针p所指结点与后继结点断开 第102页 123 指针操作的举例 p q nextp指向q所指结点的后继 ai ai 1 ai 1 ai ai 1 ai 1 q q p p 操作前状态 操作后状态 第103页 123 单链表的查找算法 单链表查找ai算法操作步骤 step1初始化 指针p指向头指针 计数器置0step2p非空且计数器小于i循环step3每循环一次 p后移一个位置 计数器加1step4循环结束 返回指向ai的指针p 第104页 123 单链表查找算法程序 get NODE head int 查找i子函 NODE p 结构指针 intcounter 0 p head next while p NULL 第105页 123 单链表插入算法1 3 单链表插入算法操作步骤 将s插到ai 1和ai间 step1找到ai 1的位置 使指针p指向ai 1step2申请并生成新结点sstep3使s插入到ai 1和ai之间s next p nextp next ss data x 或写为 next s next p next p sdata s x ai 1 ai p x s 第106页 123 单链表的插入算法程序 insert NODE head inti intx NODE p s if i 1 p head elsep get head i 1 if p NULL printf 插入位置错 n exit 0 else s NODE malloc sizeof NODE s data x s next p next p next s 令p指向ai 1 若i 1 p指向头指针 p为空 说明找不到i位置 p定位成功 第107页 123 单链表删除算法1 4 算法1 4操作步骤 删除结点ai step1找到ai 1的位置 使指针p指向ai 1step2使指针t指向p所指结点的后继step3使t所指结点ai脱链step4释放tt p nextp next t nextfree t 亦可写为 p next p next next p t ai 1 ai ai 1 第108页 123 单链表的删除算法程序 delete NODE head inti NODE p t if i 1 p head elsep get head i 1 if p NULL printf i表长 1 无此结点 n exit 0 if p next NULL printf i 表长 1 无此结点 n exit 0 else t p next p next t next free t P定位ai 1操作 P定位成功 第109页 123 3 循环单链表和双向链表 链表检索只能从头指针开始 且只能顺链表方向移动 在单链表中 从表的任一结点ai找其前趋结点 时间复杂度是O n 如果让链表首尾相接 构成环形 这就是单循环链表 链表可以从两个方向检索 效果更佳 这就是双向循环链表 第110页 123 单循环链表 单循环链表表示形式 单循环链表为空的条件 head next head表示形式为 head head a1 a2 an 第111页 123 单循环链表特点 从表中任一结点出发 均可以找到表中其它结点 找其前趋结点的时间复杂度是O n 第112