第三章 算法与数据结构.ppt

第三章算法与数据结构 程序为什么能解题 就是它能把输入的数据 经过表达式计算 赋值 置换转移等一系列计算步骤 最后得到输出 编制程序就是要设计数据 输入的 输出的 中间的 然后针对这些数据一一安排计算步骤 即所谓算法 所以 很早就有人说 程序计算的本质是 程序 算法 数据结构 第三章算法与数据结构 程序 算法 数据结构算法和数据结构讨论的是抽象的计算逻辑 与具体的表示法无关 可以用图形 伪代码和汇编语言 高级程序设计语言表达它们 一般讨论中采用近似于高级语言的伪代码 不能上机运行 可以方便地转成编程语言代码 表达 本章讨论编程最重要的两个基础 即算法与数据结构 3 1算法 算法是什么 就字面而言是计算解题的办法 是解题策略具体化为计算机的动作 即计算机在什么情况下应该怎么做的一系列步骤 实施了这些步骤问题得到解决 计算机容许的动作是 为变量赋值 包括初值 计算表达式 在变量上做四则或逻辑运算 计算过程的选择 循环 转移控制 调用函数 子程序 例如 辗转相除法是求两个整数的最大公约数的数学算法 它的解题策略是 以小数除大数 得余数 如果余数不为零 则小数成被除数 余数成除数 除后得新余数 若余数为零 则此除数即为最大公约数 否则继续辗转除 不妨先拿两个正整数试一试 544和119 544 119的余数是68 119 68的余数是51 68 51的余数是17 51 17的余数是0 所以544和119的最大公约数是17 如何写出计算机算法呢 计算机怎么进行辗转相除呢 显然只能用计算机容许的动作 写出的算法才是可行的 看如何写出计算机的辗转相除法 见课本62页令变量x为被除数 y为除数 z为余数 计算机中有求余函数mod 则 z xmody然后x y y z就换过来了 x依然是被除数 y是除数 于是写出最大公约数 GCD 算法 1 设定x y z2 输入x y3 ify xthenz y y x x zfi4 whiley0doA z yB y xmody C x zod5 输出z 即最大公约数 其中if then fi whiledo od是分支和循环控制 fi 和 od 是编程语言Endif和Endwhile的简写 其实也可以看出if fi do od 是赋值符号 其中的序号按1 2 3 和A B C 字母数字相间表示嵌套第5步这一行最后的 表示算法结束 这种表示法是算法文献上学者们约定的表示法 3 1 1算法的表示 从GCD算法的例子看到它的表达比较自由 不过是自然语言加上编程语言的基本特征 控制结构 赋值 调用 而已 很自然地 读者就会问到 算法描述语言和编程语言有什么关系 事实上 早期的编程语言ALGOL就叫算法语言 后来发现 用编程语言描述算法往往使人们陷于表示的细节 因为编程语言的形式化 即正规性 过于严格 而在设计程序的早期 人们关心的是程序逻辑能否解题 而不是立即上机运行 于是先用伪代码写设计 再用编程语言编码实现这个设计 编码 这样写的时候要求不那么严格 3 1 1算法的表示 算法描述的是程序的计算逻辑 编程语言表达的是程序本体 源代码 更形象地说 一个是灵魂 一个是包含有灵魂的肉体 设计过程也是人们对这个问题更深入了解的过程 反复修改是必然的 何不先设计 修改好了一次翻译 编码 成功呢 于是 先设计 后编码 是早期软件行业不成文的行规 直到现在 软件开发依然强调设计和编程是两个不同阶段 只是由于开发工具的完善 伪代码越来越近似于最后实现的编程语言 甚至有些简单编程直接用编程语言 如VB VC在窗口上进行 伪代码始终没有统一的标准 类C 类Pascal 类VB之类的伪代码 也不尽相同 但程序员必须记住 用伪代码写算法 编程语言写程序 还是应该遵循的 本书约定的算法描述语言是VC语言的变体 称为类VC语言 见课本63页 这里还需要说一说流程图 FlowChart 因为它在历史上有过巨大的影响 在20世纪50 70年代结构化编程语言尚未风行时 流程图一直是表达算法的设计工具 美国国家标准协会 ANSI 还把它定为标准 为了帮助读者阅读历史的软件文档 这里做一点简单说明 图3 1常用流程图符号 如图3 1所示 其中 带圆弧的框是起止框 表示算法的起始 终止 框内填写文字 圆圈一般是连接框 连接多个流向箭头 大圈中写文字标号 无文字时是句号大小的圈 平行四边形的输入输出框表示输入数据和输出计算结果 框内应填写需要输入或输出的量 有的标准将输出画成打印纸形状 菱形的判断框根据条件判断执行的走向 框内应填上条件 矩形的处理框表示执行计算表达式和赋值操作 框内用文字或符号表明具体实现的操作 双立边矩形框是调用 引用框 框内写函数 过程名 注释框表示对操作或数据做必要的说明 框内用文字说明注释信息 流向线表示算法中控制的流向 向下向右可不画箭头 其他方向必画 画流程图时 主流程必须在一条垂直的轴线上 特别是起止框要对齐 切勿因有多次分支而将主流程画成台阶形或横宽大于纵长 3 1 2算法的定义 仍回到上述GCD算法的例子 以它来说明E Knuth对算法作的定义 一个算法 就是一个有穷规则的集合 规则规定了解决某类问题的运算序列 它是有穷的 确定的 能行的 并有0到多个输入和1到多个输出 现解释如下 运算序列体现了解题规则GCD算法例子中 运算 是广义的 就是计算机可执行的操作 不单指计算值 0到多个输入 1到多个输出没有输入 输出的计算是没有意义的 这里只需解释 0个输入 不是无输入 而是变量已有初值或缺省值 算法执行时不另要求输入 这是极为常见的 例如 公司的正式文件每页都要打上公司的商标 其缺省位置是左上角 每次调用 打印程序无需输入坐标参数 有穷的指算法实施的规则是有穷的 也就是执行了有限个步骤即结束 无限步骤即不终止就不能称之为算法 只能是称为算法模型的计算方法 数学中有些计算方法在界定收敛条件之前是不终止的 确定的指算法的每一步骤都有确切的定义和解释 所以算法描述语言力求形式化 无二义性解释 编程语言当然是形式语言 但如前所述太烦琐 多采用伪代码 能行的指算法中的每一步骤均能准确实施 也指可以证明整个算法实施后可以得到预期的解 3 1 3算法与建模 每个程序都包含了算法 设计程序首先作算法设计 就是把解题策略具体化 那么解题策略由何而来 这就需要建立计算模型 前述的 辗转相除 求最大公约数 既是模型 两个整数辗转相除 又是解题策略 不妨再举个例子 例3 1求整数1 N之和这是数学家高斯小时候回答教师 求1 100之和是多少 的做法 数据模型是整数1 100数组 求和模型如图所示 把 1 99 2 98 3 97 成对先加 共49个100 再加上50和100 换成数学表示N N 2 1 N 2 N N N 1 2这就是求和模型的数学描述 也称数学模型 代入数字 得到结果100 101 2 5050 按照这个公式写出算法的伪代码是极简单的 voidsum1 cinns n n 1 2couts 这个题目也可以直接按公式模拟人们做累加伪代码如下 voidsum2 cinni 1 s 0while i n do s s ii i 1loopcouts 算法Sum1和Sum2显然不同 一个只做加法 一个有加 乘 除法 运算速度不一样 一个用三个变量一个只用两个 存储单元耗用不同 对于复杂的计算 它们的差别就非常巨大了 算法分析就是专门研究算法时空效率的 它们的不同在于所取计算模型不同 一个是总结出的数学模型 一个是模拟自然数序列增长的过程模型 当然最常见的稍微复杂一点算法多采用结构模型 有了模型就可以在它上面思考算法 请注意 同一模型可以有多个不同的改进算法 后文的数据结构就是研究有哪些典型的结构关系及其算法 建立什么模型才易设计算法呢 这要取决于问题的性质和分析人员的水平 常见有以下三种模型 数学模型最易写算法的模型 且准确 简单不易出错 各种数学类型都有成熟的计算方法 可惜并不是所有问题都能找出数学公式建立数学模型 过程模拟模型这是处理日常业务问题算法的常用模型 结构模型已如前述 每个结点可以是一种处理动作 每一个边是输出 输出 反过来 每个结点也可以是数据的状态 每个边是一种处理的动作 结构模型虽没有数学模型简单 清晰 深刻 但比过程模拟模型要明确得多 是设计算法时常用的 3 1 4算法的优劣 同样模型 同样结果可以有不同的算法过程 其差别表现在运算次数 占用存储多少 课本69页有例子 例3 3荷兰国旗问题给出了三种不同算法这个例子说明计算模型 数据结构 算法既相关又独立 模型给出算法的思路数据结构是算法作用的对象算法有其自身的好坏 时 空效率 3 1 4算法的优劣 续 算法复杂性包含多种评价条件 时间 空间 正确 简单算法的时间复杂性单次运行 时间长短比较 买一次车票 排队等待时间多次运行 平均运行时间的比较 例如 你每次去银行 等待时间的平均值时间复杂性的度量在实践中很重要的参数与n成正比 还是与n 成正比 天差地远 3 1 5常用算法 设计算法的步骤是 先弄清问题 建立计算模型 设计实现这种模型的数据 结构 再设计使数据变化达到要求的动作步骤 证明或验证算法正确 再查看有无更好的改进 一个好算法常常是深思熟虑多次改进的结果 对于初学者先解决有无 再解决好坏 为此 本小节提供一些常用算法 模型 既可以解决一些问题 又是组合更复杂算法的思路 枚举法枚举亦称穷举 是最笨但最可靠的办法 计算机 无知觉 它根据你给的条件 无一遗漏地做一遍总可以找到解 生活中这种办法也不少见 如公安局根据少量特征把全市符合该特征的人查一遍以搜捕重要逃犯 工作量巨大 近乎蛮干 但是它是没有其他办法时的最好办法 计算机因为速度快 可以 以快补拙 所以常用这种方法 枚举法作为一种具体的算法 还可以解决常规方法不易解决的问题 例如 百元买百鸡这个古老的问题 例3 4公鸡每只五元 母鸡每只三元 小鸡三只一元 问百元买百鸡有几种买法 可以写出代数方程式 x y z 1005x 3y z 3 100再也找不出方程了 那么两方程怎么解三个未知数 这类问题只好用枚举法 因为公鸡最多20只 母鸡最多33只 一一枚举其组合 若余下的只数能与钱数匹配 就是一个解 全部枚举可以找出所有的解 枚举法的程序一般简单 但有时运算量大 如果能找到明知枚举无结果的限定规则 缩小枚举范围 这种方法还是很有效的 迭代法在科学计算领域 人们时常会遇到求解方程f x 0或微分方程的数值解等计算问题 可是人们却很难或无法用像一元二次方程的求根公式那样的解析解法 又称直接求解法 例如 一般的一元五次或更高次方程 几乎所有的超越方程 它们的解都无法用解析方法表达出来 为此 人们只能用数值方法 也称数值计算方法 求出问题的近似解 若近似解的误差可以估计和控制 且迭代的次数也为人们可以接受 它就是一种数值近似求解的好方法 它既可以用来求解代数方程 又可以用来求解微分方程 使一个复杂问题的求解过程转化为相对简单的迭代算式的重复执行过程 下面以方程求根f x 0为例说明迭代法的基本思想 首先把求解方程变换成为迭代算式x g x 然后从事先估计的一个根的初始近似值x0出发 用迭代算式xk 1 g xk 求出另一个近似值x1 再由x1确定x2 最终构造出一个迭代序列 x0 x1 x2 xn 来逐次逼近方程f x 0的根 显然 迭代过程就是通过老值求出新值 用新值替代老值的过程 对于一个收敛的迭代过程 有时也要经过千百次迭代才可以得到准确解 但实际计算时 只能作有限次迭代 因此 要精选迭代算式 研究算式的收敛性及收敛速度 如果一时找不出收敛的算式 也可以用迭代算法 例3 5终止循环的条件 两次得到的近似值之差的绝对值小于预先给定的误差值 递归法数学上有许多函数是用函数本身定义的 例如阶乘函数 fact n n n n 1 n 2 1 n fact n 1 用其自身定义非常自然 递归算法往往是对问题更本质的描述 在计算技术中它占有重要地位 写递归算法的程序极其简单 看上去几乎和递归的数学公式一样 只是注意 递归出口 自己调用自己何时才了 阶乘函数写成伪代码是 Funcfact n Integer 这是定义的接口If n 0orn 1 fact 1 出口条件Elsefact n fact n 1 是递归调用 n不断减少EndFunc递归算法一般要先问是否满足出口 递归函数放在Else部分 可以设想它的执行情况 从n n 1 一直连乘到1 而不是相反 在非数值计算中用递归建立计算模型写算法也很简单 举河内塔为例 例3 619世纪欧洲人到东方 看到Bramah神庙里有个和尚整天把三根柱子上的金盘倒来倒去 原来他是想把一个柱子上64个从下至上逐个缩小的金盘从一个柱子移到另一个柱子 规定每次移一个 而且小盘永远在大盘上 据说 全部移完之后就是世界末日 梵天再世 但是无论他倒了多少天总没有什么进展 这个装置引起欧洲人极大兴趣 后来传到欧洲作为馈赠的玩物 叫河内塔 河内塔移动规则简单 但移动次数实在惊人 64个盘子其移动的次数是次 比以秒计的地球年龄1 89 1017都大 当然 计算机移动一次不会要一秒钟 那么 编一个程序让机器作也许能多做几个 为找到这个问题的算法 先画出图 试走几个盘 大家很快就可以想到 要使n个盘从1柱移到2柱 得先把n 1个盘移到3柱 那么第n个盘 最大盘 就可以从1柱移到2柱 至于如何把n 1个盘从1柱移动到3柱暂时不管 第n盘移完之后 按同样方式再将n 1个盘从3柱移到2柱 于是n个盘从1柱移到2柱的任务就完成了 草拟算法是 MoveTower N 1 2 CallMoveTower N 1 1 3 CallMoveDisk 1 2 CallMoveTower N 1 3 2 其中过程MoveTower的参数依次表示要把几个盘子 从起始柱搬到目的柱 过程MoveDisk的参数表示把一个盘子从起始柱移到目的柱 移动N个盘的任务变成两个移动N 1个盘的任务 加上一个有效的移盘动作 看来这个问题似乎没解决 移动N个和N 1个差不多 到底如何移动还是不知道 其实这个问题已经解决了 把MoveTower N 1 1 3 这个新任务如法炮制 把2柱当成过渡柱 也可以变为两个子任务加一个MoveDisk 1 3 的动作 如此做下去 每次移动盘子的任务减1 直到0个盘子时就没有任务了 剩下的全部是动作 递归算法的内容就这三步 递归程序能自动地做到0个任务为止 可以拿三个盘子检验一下这个递归算法 可以看到 当任务为0时 剩下的全是动作 从上往下数是 1 2 1 3 2 3 1 2 3 1 3 2 1 2和实际复核的完全一样 在写算法时 只要把柱名改成变量 就可以自动改变其值 再加上递归终止条件 可以得到 MoveTower N From To Using Integer If N 0 PrintFrom ToElseCallMoveTower N 1 From Using To CallMoveDisk From To CallMoveTower N 1 Using To From 这是一个典型的递归算法 自己调用自己 它从递归给定参数出发 如例中N个 递归到达边界 N 0 递推法所谓递推法 它的数学公式也是递归的 只是在实现计算时迭代方向相反 从给定边界出发逐步迭代到达指定计算参数 它不需反复调用自己 节省了很多调用参数匹配开销 效率较高 还是以解阶乘函数为例 其递推过程是 f 0 0 1f 1 1 1 f 0 1f 2 2 2 f 1 2f 3 3 3 f 2 6 f n n n n 1 n f n 1 写出伪代码算法是 Funcfact1 N Integer IntegerIf N 0orN 1 fact1 1Else 1Do fact1 fact1 I I I 1 此处是变量引用 而不是函数调用 hile EndFunc再看一个Fibonacci数列的例子 Fib 1 1Fib 2 1Fib n Fib n 1 Fib n 2 写个递归算法的伪代码把以上公式抄进去就可以了 写递推算法伪代码只要记住 从边界开始 都用变量 FuncFib N Integer IntegerF1 1If N 1 ReturnF2 1If N 2 ReturnI 3Do Fib F1 F2F1 F2F2 FibI I 1 While I N EndFunc不难看出 递推法就是把迭代法用于递归公式 迭代方向正好和递归算法过程相反 分治法在算法优劣一节中谈到 算法分析 它是研究算法的运算次数 相对速度 和占用空间的 研究表明 运算对象的多少 大小 是一个重要指标 算法的复杂性 运算次数 随大小 n 的增长呈线性增长 指数增长 阶乘增长 它们的关系可表示为 f0 n O n 计算次数正比于nf2 n O 2n 计算次数正比于2nf3 n O n 计算次数正比于n 这就得到一个启示 把一个大的计算分成两个小的计算其计算量可以很快地降下来 n 2 n 2 6 2 3n2 2 n 2 2 62 36 2 32 18n 2 n 2 6 720 2 3 12这就是分治法的思想基础 因为常见的矩阵运算 排序 查找算法 线性复杂度不大 只要分小就是有益的 Knuth的快速排序算法 Quicksort 就是这种分治思想的连续运用 例3 7设有N个元素的数组 请按递增 递减 次序排序 随便取出一个元素A P 和数组其他元素比较 凡大于它的放在右边 小于它的放在左边 A P 的位置确定后 留下左右两个待排序的子数组 接着按同样的方法二分 递归直到一个元素 写成伪代码算法是 QuickSort A Min Max P MinTop Min 1Bot MaxDo Do Top Top 1 While A Top A P Do Bot Bot 1 While A Bot A P Swap A Top A Bot While Top BOT Swap A P A Top A P 找到恰当位置CallQuickSort A Min Top 1 小于A P 的子数组CallQuickSort A Top 1 Max 大于A P 的子数组可以证明其平均比较次数为O Nlog2N 小于一般排序的O N2 这个算法还可以改进 如果分出的子数组碰巧已排好序 另一个尚需排 如何让已排好的子数组跳出运算 把一个大的处理对象分割为小对象 如果仍用原方法处理小对象就是递归 如果分出的各部分用不同的算法处理就是分治 分治在人工智能 查找 检索的算法设计中是经常见到的 回溯法算法过程如同下棋 每一步都会对结果状态有所影响 每一步都正确结果自然正确 算法设计就是设计出能得出正确结果的全过程 为此规定每一步的约束 有时一下子规定不了必然正确的全过程 只能根据当时当地情况决策 试着来 发现不对可以反悔 如同悔棋 这就是回溯的思想 回溯法写成算法是极其有用的 回溯法的算法是 Backtracking ByRefsucc Boolean 1 确定起始状态值走第一步 本例是c 4 4 12 确定下一步还有几种可能 本例是8 其他位置是 2 3 4 6 8 3 选一可能 走下一步 记住可能和本步特征 I J N 4 做完新一步应做的事 本例是c I J N N N 15 While目标未达到DoA 确定下一步有几种可能B While没有可能and还有上一步do1 回退上一步2 查有无下一可能C If上一步没有了Return succ False D 选一可能走一步 记住可能和本步特征E 做完新一步应做的事6 Return succ True 读者可按这个框架写出骑士周游的算法 3 2数据结构 有些算法的操作对象很简单 几个变量就可以了 例如方程求根 有一些则不然 操作的对象是一组相互有关的数据 脱离了数据的关联性算法就无从施展 例如 上节的 快速分类 骑士周游 荷兰国旗问题 就是一维数组和二维矩阵上展开的 3 2 1数据的结构关系 单个的数据 变量 虽然能解决不少问题 但经常遇到要计算的问题其数据往往是关联的 甚至不关联就失去处理的价值 先分析几个例子 1 名字串ZhangSan这八个字符串在一起表示 张三 少一个多一个或次序颠倒都不是 张三 计算机在处理它时 一起存 一起取 除非张三改名 每个字符数据和其他数据是邻接的关系 2 火车行车时刻表这是一个二维表单 将车次 时间和站名放在一起就可以回答很多问题 早上7 8点到武汉可在北京乘T37次 T77次 从北京站到武汉站最快要12小时 就不单是 T37次北京18 53开 一条信息了 把这个表输入到计算机 连查找的功夫都可以省 计算机之所以 聪明 是因为它会查二维矩阵 3 分配工作图3 4申请职位关系图有五个不同专业的人申请五个不同职位 每人填两个志愿 申请情况如图3 4所示 人名A B C D E 职位a b c d e都是长串的字符串数据的简写 申请志愿的联线把它们连成一个图 图就是数据结构 是写分派工作算法的解题模型 分配的结果是每人都满足了志愿 而每个职位都有人干 图3 4申请职位关系图 这个例子小到一眼就看到结果 但如果申请人是1275人 职类87 职位44 志愿1 3 不用计算机算就太费事了 编个程序先按基本条件删去一部分人 然后按每个职类计划的职位和申请的人数分配 打出一张录用表 描述这个图不外乎数据集合D A B C D E a b c d e 和它们的关系集合R 表示前后两数据有关系 且次序不能倒 如次序可逆就要用 数据及其关系构成数据结构由以上例子看出数据结构只由两种集合构成 DS D R 数据集合D 可以是单个数据集合 也可以是不同类型子集组成的大集合 甚至可以是数据结构 第一个例子的字符串本身是字符的数据结构 字符串集合也是数据集合 关系集合R指数据间的结构关系 这里的数据间关系很抽象的 两数据只是有关不问具体是什么关系 书83页有例子 数据结构就是研究数据的结构关系 请看下例 DS1 D1 R1 D1 a b c d e R1 a b b c c d d e e a a c a d b e c e 画成图形如图3 5 a 所示 DS1是一个无向图 图3 5无向图和有向图 若DS2 D1 R2 D1 a b c d e R2 画成图形如图3 5 b 所示 DS2是一个有向图 图3 5无向图和有向图 若DS3 D3 R3 D3 a1 a2 ak R3 1 i k 1 这个关系R3说明任何两递增下标的数据元素都有相邻关系 画出图形如图3 6所示 是一个数组 图3 6数组数据结构 若DS4 D4 R4 D4 a b c d e f R4 它们的结构关系如图3 7所示 是一种树型数据结构 图3 7树的数据结构 3 2 2数据结构的研究方法 从上节的例子可以看出 数据结构的基本概念是非常简单的 数据元素及其关系 由于关系不同可以形成不同的结构 它们的计算特性也各不相同 如果能找出其中最基本的几种 熟知这几种的计算特性 那么 以数据结构模拟客观世界的数据 依托它写算法就十分方便了 如上所述数据结构中的数据元素 也可以扩充成数据结构 圆圈扩充成为一个图或表或树 这样 极其复杂的结构也能表达 其计算特性不外乎叠加 所以 熟知基础的数据结构是极为重要的 按一般文献的介绍 数据结构分四大类 表元素是线性关系 连接 图元素间是非线性关系 连接 树元素间是非线性关系 连接不得有回路 文件记录的序列 研究方法研究每种数据结构可以实施什么算法 这些结构都能映象到机器的存储中 实施的算法才有意义 这四类最基本的数据结构最重要的是表类 因为它直接对应为机器对数据的操作 找出首地址拉出一长串数据 或按首地址位移多少地址即可找到某元素 索引 如果不是存放在一起 每个元素跟下一个元素的地址 指针 也是线性表 因为用高级语言编程写算法 不能涉及具体地址只说线性表和线性链表 至于其他的数据结构机器是不能直接操作的 都得化为简单表来处理 研究方法即使是稍微复杂一点的表 如二维矩阵 每个元素也是按一维数组的数组元素来处理 所以在讨论每种数据结构时 首先研究它的逻辑结构有什么运算性质 用什么表示法表示这种逻辑结构 表或链表或复合 再按表示法和性质写出求解问题的算法下面都是按这个办法处理的 逻辑结构和物理结构数据结构是十分抽象的 学会了基本结构 表 图 树 文件 就可以用它们的复合模型刻画事物的本质 这样就形成了逻辑结构 它是客观世界数据关系的真实反映 但计算机只能处理最简单的结构 这就形成了逻辑结构和物理 实现 结构的分离 正如艾菲尔铁塔 长江大桥的拱顶是不同的逻辑结构 满足不同的用途 它们的物理结构都是各型钢铁焊接 或铆接 的结构 讨论问题或程序感兴趣的是逻辑结构 而程序的实现非物理结构不行 逻辑结构和物理结构这里还要说明逻辑结构和物理结构是相对的 直接讨论矩阵的元素写两个下标A i j 非常直观 但机器自动把它转为一维下标A n 后才能实现计算 前者在逻辑结构上说话 后者在物理结构上实现 一旦能自动实现 就认为它是 物理的 了 在讨论图的表示法时 二维数组是实现图的物理数据结构 也就是不再说二维到一维的实现了 数据结构的图形表示上小节给出图 有向图 数组 树的图形表示法 以及对应的基本的集合论定义 在实用中不去证明数据结构的某种性质 而是直接使用 定义好 了的结构 观察它的宏观性质写算法 不再写出基本的形式定义 除非要做理论证明工作 无论是逻辑的还是物理的都可以用图形表示 用一个框表示数据实体 圆形方形均可 无箭头连线表示双向关系 有箭头连线表示单向关系 当只有线性关系且不分离时 可以不画连线 图3 6即为实例 以下分别讨论这四类数据结构 3 2 3线性表 线性表的逻辑结构是n个数据元素的有限序列 a1 a2 a3 an 表中元素的个数n定义了线性表的长度 n 0 n 0的表称为空表 线性表的结构特征是 数据元素呈线性关系 线性表隐含是有序的 它必存在惟一的 第一个 数据元素和 最后一个 数据元素 除第一个元素外 每个元素都有一个且只有一个前驱元素 除最后一个元素外 每个元素都有且只有一个后继元素 在同一个线性表中所有数据元素ai必须是相同的数据结构 它可以是同类型的数 同一类符号或同样复杂的结构 线性表的逻辑图如图3 8所示 线性表也可以用机器能直接接受的符号串表示法 用括号括着的元素名或值 例如可以按问题需要建立以下线性表 表1 李研 刘丰 陈宏英 表2 李研 98 99 100 297 99 0 刘丰 97 96 94 287 95 7 陈宏英 94 96 99 289 96 3 表1是名字表 表2的数据元素是 姓名 语文成绩 数学成绩 英语成绩 总分 平均分 具体的值 虽然不是同一类型数据 但所有元素均是同一种形式 它是由简单表组成的线性表 图3 8线性表的示意图 线性表的基本运算主要有 创建一个新表 包括无表元素的空表 在两个确定的元素之间插入一个新的元素 删除线性表中某个元素 按某种要求查找线性表中的一个元素 按需要更新表元素 计算表长 元素个数 重排表元素 即排序 合并两个表第1种操作在高级语言中只要声明 编译程序就可以替你完成 其余的要先决定表的表示法 再写算法 顺序表和一维数组没有特殊说明 表是隐含顺序存放的 如果要插入或删除一个元素 那么在这个元素以后的元素存储位置都要改动 为了显式地操作存放顺序 则定义了数组 数组是以一维下标索引的顺序表 数组一旦声明其长度不可改变 中间也不许删除或插入 这就找到了一个不变的舞台 让顺序表在其上演绎变动 下面是顺序表插入和删除的算法 线性表的查找见3 3节 其余操作读者可以参考这几个算法写出 插入在线性表 a1 a2 ai ai 1 an 的第i个位置插入元素x 使之成为 a1 a2 x ai ai 1 an 其算法描述如下 Insert ByRefA Type n i x 一维数组A 1 n 第i个元素之前插入一个新元素xIf in 1 ERROR 位置不存在 插入的位置不合法Elsefor j n j i j A j 1 A j 元素后移A i x 进行插入n n 1 线性表的长度加1从上述算法可见 当i n 1 语句A j 1 A j 将不执行 因为此时循环变量的终值大于初值 即不需要移动元素而直接将x插入到A n 1 的位置上去即可 反之 当i 1时 语句A j 1 A j 将执行n次 即需将线性表中原已存在的n个元素均后移一个元素的位置才能进行插入 所以 若顺序表中元素个数为n 在往每个位置插入的概率相等的情况下 插入一个元素的平均移动元素个数为n 2 删除一般情况下 在表长为n的线性表 a1 a2 ai 1 ai ai 1 an 中删除第i个数据元素 还需将第i 1个至第n个元素向前推动一个位置 即 a1 a2 ai 1 ai 1 an 其算法描述如下 Delete ByRefA n i 一维数组A 1 n 中的第i个元素处删除该元素xIf in ERROR 位置不存在 删除的位置不合法Elsefor j i j n 1 j A j A j 1 元素前移n n 1 表长减1和插入的情况类似 当i n时 语句A j A j 1 将不执行 因为循环变量的初值大于终值 即不要移动元素 但当i 1时 语句A j A j 1 将执行n 1次 此时需将线性表中除第一个元素之外的所有元素均向前移动一个位置 所以 在等概率的情况下 删除顺序表中一个元素平均需要移动的元素个数为 n 1 2 链表以数组实现顺序表 插入或删除元素时 都不可避免地要作元素的移动 每进行一次插入或删除 都要移动近乎一半的元素 又由于数组是定长的连续存储单元 对于长度可变的线性表 只好按其可能达到的最大长度预先分配空间 这可能由于估计不足造成一部分空间太长而得不到充分利用 也可能因空间过短而造成溢出 链表恰能有效地克服这些缺点 链表一般有单链表 双向链表和循环链表等 1 单链表单链表就是链式存储的线性表 其元素除信息域外还含有一个指针域 用来指出其后继元素的位置 元素的结构如图3 9所示 单链表的最后一个结点没有后继结点 它的指针域为空 记为NIL或 另外还需要设置一个头指针head 指向单链表的第一个结点 图3 9单链表中的结点结构 例如 上述表1 李研 刘丰 陈宏英 的单链表实现如图3 10所示 链表的一个重要特点是插入 删除运算灵活方便 不需移动元素 只要改变元素中指针域的值即可 图3 11 a b 分别示出了从单链表中 插入一个新元素和删除一个元素的链接 虚线表示变化后的指针 图3 10单链表逻辑图 图3 11单链表的插入和删除 链表插入元素的算法如下 InsertLink list Q pointer 每个结点有两个域如图3 9Item Integer CallGetNode P 申请一个结点返回指向该结点的指针PP Info itemIf list Nil list P list Next Nil 如原链表为空ElseP Next Q Next 在Q所指结点之后插入itemQ Next P其他算法读者可以自行写出 值得一提的是链表有一个操作是所有指针逆反 可以很快得到反向排序的表 链表是十分有用的数据结构 它有助于快速方便地使用信息 例如 机器中按顺序录入了10个人的信息 人员还在不断增减要保证打印的文件总是按某种原则排序 如年龄 级别 工资等级 性别等 为了不致大量重排和移动所有数据 用链表排序最方便 信息只按先后次序存入且次序不变 按链表排序后打印 即可满足要求 排序的工作量是很小的 2 循环链表循环链表是结构形式和单链表稍有不同的一种链表 如图3 12所示 其差别仅在于链表中最后一个结点的指针域不为 NIL 而是指向头一个结点 整个链表成为一个由链指针相链结的环 故称之为循环链表 其插入 删除算法和单链表没有多大区别 循环链表应用也是极其广泛的 例如 要10分钟内公布一次股票涨落行情 则把所有股票号接成一个循环链表 有一批录入员负责行情变化录入 每人只管负责几个号的涨落行情录入 报表程序按链表依次处理各股票10分钟之内的变化 图3 12循环链表示意图 3 双向链表在实际应用中 链表结点可根据需要来设定 对于线性表来说 除了设有指向后继结点的指针外 还可设一个指向前驱结点的指针 习惯称这种含有两个指针域的结点构成的链表为双向链表 其结构如图3 13所示 由于每个结点中都设有两个指针 则不仅可直接得到后继结点的信息 也容易得到前驱结点的信息 这对某些需要逆向查找的算法特别有用 还可以增大表的安全性 但在作插入 删除运算时 需要同时修改两个方向上的指针 一般情况下称结点含有多个指针域的链表为多重链表 双向链表是多重链表的一种 图3 13双向链表图例 栈除了前面讲的线性表外 栈 stack 是一种特殊的线性表 对它的操作只能是 后进先出 LIFO 也是使用最为广泛的数据结构之一 因为它的运算次序受到严格的限定 故又称限定性数据结构 图3 14栈的逻辑结构 栈的结构特点在日常生活中 很多事务是按照 后到达的比先到达的优先 的顺序处理的 例如 穿衣服的顺序是先衬衫 后制服 最后是大衣 脱衣服的顺序必须反过来 最先脱的是最后穿上的大衣 若想在衬衫和制服之间加一件毛衣时 必须先脱下大衣和制服 才能穿上毛衣 又如 玩具手枪的子弹压入子弹夹时 总是要将子弹一粒粒按顺序压入 而射击时却是最后压入的一粒先打出来 而最先压入的最后一个被射出 栈的结构特点正是这些事物的抽象 栈的结构特点栈是限定仅在表尾进行插入和删除运算的线性表 表尾称为栈顶 top 表头称为栈底 bottom 表中无元素时称为空栈 如图3 14所示的栈中 元素按a1 a2 a3 an的顺序进栈 a1称为栈底元素 新元素进栈要置于an之上 删除或退栈必须先对an进行操作 栈体的物理存储可以用顺序表结构 也可用链表 2 栈的运算通常对栈进行的运算有 设置一个空栈 判定某个栈是否为空栈 进栈 退栈以及读取栈顶元素等 下面分别给出以顺序表实现的栈和进栈 退栈的算法 进栈PushStack ByRefstack m top x 在栈Stack 1 m 的栈顶top之上插入元素xIf top m ERROR 栈满 Elsetop top 1 栈顶上移stack top x 将x放入栈顶 退栈FuncPopStack ByRefstack top y Bool 当栈空时返回FALSE If top 0 Return False 反之退出栈顶元素赋给变量y并返回TRUEElsey stack top 将栈顶元素赋给变量ytop top 1 栈顶下移Return True EndFunc 当栈的最大容量事先不能估计时 也可采用链表作存储结构 简称链栈 如图3 15所示 图中top为栈顶指针 指示栈顶元素的位置 若top为空 则表示空栈 显然 链栈不出现上溢 除非系统中不存在可用结点 链栈的算法也比较简单 图3 15链栈存储结构 队列队列也是一种特殊的线性表 在实际生活中经常要靠排队来维护正常的秩序 在计算机程序设计中也有类似的问题 数据结构中的队列与生活中的 排队 极为相似 也是按 先来到先解决 的原则行事的 并且既不允许 加塞儿 也不允许 中途离队 1 队列的结构特点队列 Queue 是限定所有的插入只能在表的一端进行 而所有的删除都是在表的另一端进行的线性表 表中允许插入的一端称为队尾 Rear 允许删除的一端称为队头 Front 如图3 16所示的队列中 a1是队头元素 an是队尾元素 队列中元素以a1 a2 a3 an的次序依次进入队列 则a1是第一个出队列的元素 即队列的操作是按先进先出的原则进行的 因此 队列又称FIFO FirstInFirstOut的缩写 表 队列的物理实现可以用顺序表 也可以用链表 队列指针减队尾指针加1即为队体的长度 图3 16队列示意图 2 队列的运算通常对队列进行的运算有 设置一个空队列 判定某个队列是否是空队列 插入一个新的队尾元素 简称入队列 删除队头元素 简称出队列 读取队头元素 3 循环队列队头 队尾指针值只增不减 除非是短时工作的队列 存储空间总有耗尽的时候 而且大量空间浪费 于是 人们就想到了循环 利用空间 队列 循环队列把存储空间在逻辑上看成一个环 当R指向存储空间的末端后 就把它重新置成指向存储空间的始端 如图3 17所示 图3 17循环队列的插入 删除示意图 循环队列算法如下 怎么能在一个数组中让它的下标回头呢 用求余函数mod 设数组长N 10 Front Front 1 modNAddCQ Q Array 0 N 1 X Type 插入算法Rear Rear 1 modNIf Rear Front callQueue fullQ Rear XDelCQ Q Array 0 n 1 ByRefitem Type 删除算法If Front Rear callQueue emptyFront Front 1 modNitem Q Front 4 链表实现队列如果队列的容量 同时存在于队中元素 无法预先估计时 可以采用链表存储结构 如图3 18 虽然可用链表实现循环队 但没有必要 因为队列元素一旦删除 所占空间即可收回 图3 18队列的链表存储结构 串串 String 是一种比较特殊的线性表 可以看做一维字符数组 但其长度不恒定 可以作删除 插入操作 在这点上其结构和链表类似 串也可以用链表表示 许多高级语言把串作为一种单独的类型 其元素不可作四则运算 字符串在数据处理中是最常用到的数据结构 为了连接 删除 插入操作 用子串有时很方便 子串 Substring 是串的一部分 具有串的一切特征 3 2 4树和二叉树 上面谈的是线性数据结构 下面谈一谈非线性数据结构 树型结构是一类重要的非线性数据结构 在此结构中 元素之间存在着明显的层次或嵌套关系 树的定义和术语在人们周围存在着很多可以用树结构来描述的实际问题 如图3 19所示的Unix的文件系统 从图3 19可见 树结构类似一棵倒长的树 结构中含有一个类似 树根 的结点和若干子树 每个子树又有子子树 没有下层子树的结点就是 树叶 每层元素之间无关系 数据元素就安排在各结点之中 树的逻辑结构如图3 20所示 其中的是退化了的树 既是根 也是叶子 图3 19Unix的文件系统 图3 20树的逻辑结构 树的结构定义用递归定义最方便每个结点有几个子树m称度 degree 所有结点最大的度称m叉树 其中m 2为二叉树 是最常用的数据结构 结点除与子树关联外与其他结点均无关联 每个结点只有一个入度和若干出度 树可以用表实现 A B E F C G D H I J A B E F C G D H I J 对应为图3 21的树约定每对括号括着前一结点名下的所有子树 同级子树用逗号分隔 将这个表输入到机器 机器就可以处理了 但是机器往往要进一步把它变为链表 因为树实质是从根或结点到子树的无环有向图 上述表对应的链表如图3 22 a 所示 其中 是Nil的代号 第一个是数据项 后面的指针数与最大的出度m相同 本例是3 它指向子树或叶子 这个链表画得像树一些如图3 22 b 图3 21树结构示例 其中 是Nil的代号 第一个是数据项 后面的指针数与最大的出度m相同 本例是3 它指向子树或叶子 这个链表画得像树一些如图3 22 b 图3 21树结构示例 b 图3 22以多重链表实现的树 b 在释义上述表表示的树时 在root指针处指明是一个三叉树结构 在分配存储时拿出一个数据域和三个指针 并按括号填指针和 消除了表的圆括号 就可以使用链表了 也可以在每个结点处指明该结点的出度 这对叶子众多且出度变化大时可省去很多空单元 图3 21的例子则可改为图3 23来实现 图3 23不定分支树的链表实现 树的运算按照图3 22和图3 23建树是不同的约定 而按同样约定作树的操作就不会产生问题 一般树的操作可归结于下 SetTree T 建树返回树T Root x 数据元素x所在树的根 Parent T x 在树T中找出x结点的父结点 Child T x i 在树T中找出x结点的第i个子结点 树 Insert T x i S 将S子树插入树T 作为x结点的第i个子树 Delete T x i 将树T中x结点的第i个子树删去 Depth T h 返回树T的深度h 层 估计读者以上例为模型 写出链表表示树的以上7种操作的算法不会有太大的困难 二叉树二叉树是每个结点最多有两个子树的特殊树 由于它简明 容易计算层次数和叶子数 在某种程度上可与二值逻辑对应 非右即左子树 所以它特别有用 二叉树的定义是 不像多叉树 它必须指出是 左 还是 右 子树 可以证明 二叉树第i层上的结点数至多为nimax 2i 1 根为第一层 深度为k的二叉树结点数至多为nmax 例 k 4 nmax 15 k 3 nmax 7 若二叉树的叶结点数为nf 树中度为2的结点数为n2 则必有nf n2 1 这些性质是常用的 二叉树的实现同样可以用链表来表示 由于二叉树简单甚至可用一维数组实现 例如 各层各结点 除叶结点外 出度均为2称满二叉树 它不能再插入了 取长度为1 3 7 15 31 2k 1的数组可表示k层满二叉树 任何一个元素可立即找到 如图3 24所示 显然 它计算时存取要快于链表中的指针 有了这个好处 定义完全二叉树 即除最后一层不满外其余各层均满 且最后一层所有的叶子也是满的 如图3 25所示 图3 24用一维数表示的满二叉树 图3 25用一维数组表示的完全二叉树 如果树既不满又不完全仍可以按以上约定表达任意的二叉树 如 读者可以画出这两棵二叉树 显然 当结点稀少时存储浪费很大 链表又有优越性了 如图3 26所示 二叉树的遍历二叉树同样可做前述的7种树运算 只是找子树时分出左 右子树 Child BT x l 找出树BT中结点x的左子树 Insert BT x r s 将子树s插入树BT 作为x结点的右子树 Delete BT x l 删去树BT中 x结点的左子树 图3 26二叉树的链表表示 二叉树还有它特殊的运算可以解决很多问题 请看下例 例3 9计算表达式若有表达式赋值A B C D E F其中每个双目运算符可以看做子树的非叶结点 左操作数是左子树 右操作数是右子树 每个变量 操作数 都是叶子 这样 就可以建立二叉树的数据模型 如图3 27所示 计算由下向上执行 运算符优先级高的在最下面 按照左 根 右的次序把这棵树装入栈中 遵循左子树装完装运算符再装右子树 于是得图3 28堆栈 其计算过程是 图3 27表达式的二叉树模型图3 28表达式计算堆栈 按右叶子 运算符 左叶子弹出 如下一元素是运算符且比当前运算符优先级低 本例为E F 完成当前运算符的计算 结果是右叶子 再弹出下一个运算符和左叶子 D 再弹出下一个运算符 知比 优先级高则先算D C作左叶子 再算D C E F结果为右叶子 再弹 B和 先算 得叶子 最后弹出A 完成向A赋值 读者不难把上述文字的算法过程写成程序 完成表达式计算并赋值 在解本例时 并未把建立的二叉树输入到机器 而是把它当作模型 在它上面遍历 逐个访问结点 直至访问完 先访问的先入栈 入栈后 逐个弹出计算 按遍历的思想对栈数据结构写算法 遍历的规则是左 根 右 中序遍历 显然 读者自然能想到根 左 右 左 右 根规