- PDF 免费下载

Size: px

Start display at page:

Download ""

敬巫
5 years ago
Views:

1 前言数据结构课程是计算机类电子信息类及相关专业的专业基础课它在整个课程体系中处于承上启下的核心地位 : 一方面扩展和深化在离散数学程序设计语言等课程学到的基本技术和方法 ; 另一方面为进一步学习操作系统编译原理数据库等专业知识奠定坚实的理论与实践基础本课程在教给学生数据结构设计和算法设计的同时, 培养学生的抽象思维能力逻辑推理能力和形式化思维方法, 增强分析问题解决问题和总结问题的能力, 更重要的是培养专业兴趣, 树立创新意识本教材在内容选取上符合人才培养目标的要求及教学规律和认知规律, 在组织编排上体现先理论后应用理论与应用相结合的原则, 并兼顾学科的广度和深度, 力求适用面广泛全书共 11 章第 1 章综述数据数据结构和抽象数据类型等基本概念及算法描述与分析方法 ; 第 2~9 章主要从抽象数据类型的角度分别讨论线性表栈和队列串数组和广义表树和二叉树图等基本类型的数据结构及其应用 ; 第 10 章和第 11 章讨论查找和排序的各种方法, 着重从时间性能应用场合及使用范围方面进行分析和比较本书对数据结构众多知识点的来龙去脉做了详细解释和说明 ; 每章后面配有难度各异的习题, 并在附录中给出习题的参考答案, 供读者理解知识及复习提高之用全书采用 C 语言描述数据结构和算法从课程性质上讲, 数据结构是高等院校计算机科学电子信息科学及相关专业教学计划中的一门专业基础课 ; 其教学要求是学会分析研究计算机加工的数据结构的特性, 以便为实际应用涉及的数据选择适当的逻辑结构存储结构及其相应的算法, 并初步掌握算法的时空分析技术从课程学习上讲, 数据结构的学习是复杂程序设计的训练过程 ; 其教学目的是着眼于原理与应用的结合, 在深化理解和灵活掌握教学内容的基础上, 学会把知识用于解决实际问题, 书写出符合软件工程规范的文件, 编写出结构清晰及正确易读的程序代码可以说, 数据结构比高级程序设计语言等课程有着更高的要求, 它更注重培养分析抽象数据的能力本书是编者多年从事该课程教学工作的教学成果, 编者都是具有副教授以上职称有 15 年以上该课程教学经验的一线教师本书由任志国担任主编赵传成蓝才会祁建宏达文姣岳秋菊刘君担任副主编其中的第 1 章第 2 章第 5 章第 7 章第 8 章第 9 章由任志国编写, 第 3 章由赵传成编写, 第 4 章由岳秋菊编写, 第 6 章由达文姣编写, 第 10 章由蓝才会编写, 第 11 章由祁建宏编写, 所有章节习题部分由刘君编写在本书的构思与编写过程中, 得到了安天庆教授党建武教授王治和教授的帮助, 在算法的实现与调试以及插图的制作过程中, 得到了杨业史淑娟宗小兵等研究生的帮助, 在此表示感谢本书可以作为计算机类专业和电子信息类相关专业的教材或考研参考用书, 也可供从事计算机工程与应用工作的科技工作者参考由于作者水平有限, 教材中不当之处敬请读者提出批评和建议, 编者电子邮件地址 :ren_zhiguo@qq.com 编者 2016 年 6 月 i

3 目录前言第 1 章绪论引言数据结构的基本概念有关概念和术语数据的逻辑结构数据的存储结构数据的运算数据类型和抽象数据类型数据类型抽象数据类型算法算法及其特征常见的算法描述方法常见的算法设计方法算法性能分析与度量时间复杂度空间复杂度关于学习数据结构数据结构课程的地位数据结构课程体系数据结构课程学习特点 15 习题一 16 第 2 章线性表线性表的类型定义线性表的定义线性表的抽象数据类型线性表的顺序存储及基本操作线性表的顺序存储结构顺序表及相关操作的实现顺序表应用举例线性表顺序存储结构分析线性表的单链表存储结构线性表的单链表存储结构 30 iii

4 2.3.2 单链表上相关操作的实现链表应用举例链式存储结构的分析双链表与其他链式结构线性表的双链表存储结构双链表上相关操作的实现循环链表静态链表一元多项式的表示及运算一元多项式的表示及存储一元多项式创建与打印一元多项式相加一元多项式相乘 48 习题二 50 第 3 章栈栈的定义及基本运算栈的定义栈的抽象数据类型顺序栈顺序栈的定义及存储结构顺序栈的基本操作链栈链栈的定义及存储结构链栈的基本操作共享栈与多栈共享栈多链栈栈的应用栈的简单应用栈与递归 70 习题三 71 第 4 章队列队列的定义及基本运算队列的定义队列的抽象数据类型循环队列循环队列的存储实现循环队列的基本操作动态循环队列 79 iv

5 4.3 链队列链队列的定义及存储结构链队列的基本操作队列的其他存储结构循环多队列动态循环多队列与链式多队列队列的应用 84 习题四 85 第 5 章串串的定义及其基本运算串的定义串的抽象数据类型串的定长顺序存储定长顺序存储的定义定长顺序串的基本运算串的模式匹配算法简单模式匹配算法 BF 算法改进的模式匹配算法 KMP 算法串的堆存储结构堆存储结构的定义基于堆结构的基本运算串的块链存储结构块链存储结构的定义及其存储结构基于块链结构的基本运算串的应用 113 习题五 113 第 6 章数组和广义表数组的概念和存储数组的概念数组的存储结构特殊矩阵的压缩存储对称矩阵的压缩存储三角矩阵的压缩存储带状矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的三元组表存储稀疏矩阵的十字链表存储广义表广义表的基本概念 133 v

6 6.4.2 广义表的基本运算广义表的存储结构广义表上的基本算法 138 习题六 140 第 7 章二叉树和树二叉树的定义与性质二叉树的基本概念二叉树的主要性质二叉树的抽象数据类型二叉树的存储结构及创建顺序存储结构二叉树的链式存储结构二叉树的创建算法二叉树的遍历及应用二叉树的遍历二叉树遍历的非递归实现遍历算法的应用由遍历序列恢复二叉树线索二叉树线索二叉树的定义及结构线索二叉树的创建及遍历线索二叉树的其他相关算法哈夫曼树及其应用哈夫曼树的基本概念构造哈夫曼树哈夫曼编码哈夫曼树的应用树的概念与表示树的定义及相关术语树的表示树的存储树与二叉树的转换树或树林转换为二叉树二叉树转换为树或树林树或树林的遍历树的应用判定树集合的表示 185 习题七 186 vi

7 第 8 章图论图的基本概念图的定义图的相关术语图的抽象数据类型图的邻接表存储结构图的邻接表存储结构定义建立在图的邻接表存储结构的基本算法创建图的邻接表存储结构图的邻接矩阵存储结构图的邻接矩阵存储结构定义建立在图的邻接矩阵存储结构的基本操作算法创建图的邻接矩阵存储结构图的其他存储结构图的十字链表存储结构图的邻接多重表存储结构图的广度优先遍历广度优先搜索邻接矩阵存储结构上的 BFS 算法邻接表存储结构上的 BFS 算法图的深度优先遍历深度优先搜索邻接矩阵存储结构上的 DFS 算法邻接表存储结构上的 DFS 算法 221 习题八 223 第 9 章图算法及应用最小生成树最小生成树的定义构成最小生成树的 Prim 算法构成最小生成树的 Kruskal 算法最短路径求图中某一顶点到其余各顶点的最短路径 Dijstra 算法每一对顶点之间的最短路径 Floyd 算法 AOV 网的应用 AOV 网的定义拓扑排序 AOE 网的应用 AOE 网的定义关键路径 241 习题九 247 vii

8 第 10 章查找查找的基本概念静态查找表顺序查找有序表的折半查找分块查找二叉排序树二叉排序树的定义二叉排序树的相关算法二叉排序树的查找效率分析平衡二叉排序树平衡二叉排序树的定义调整不平衡的二叉排序树创建平衡二叉排序树其他查找树 B 树及其基本操作 B+ 树的基本概念散列表散列表的基本概念散列函数的设计冲突的处理方法散列表的查找分析 272 习题十 273 第 11 章排序排序的基本概念排序的定义排序方法的分类排序算法的分析方法插入排序直接插入排序折半插入排序希尔排序交换排序冒泡排序快速排序选择排序简单选择排序树形选择排序堆排序 294 viii

9 11.5 归并排序基数排序多关键码排序链式基数排序内部排序算法的比较内部排序算法的比较内部排序算法的选用 305 习题十一 306 附录一习题参考答案 312 附录二学期考试样卷 318 参考文献 323 ix

11 第 1 章绪论用计算机求解任何问题都离不开程序设计, 而程序设计的实质是数据表示和数据处理数据要能被计算机处理, 首先要能够被存储在计算机的内存中, 这项任务称为数据表示, 数据表示的核心任务是数据结构的设计一个实际问题的求解必须满足各项处理要求, 这项任务称为数据处理, 数据处理的核心任务是算法设计数据结构课程主要讨论数据表示和数据处理的基本问题本章概括地介绍数据结构的基本概念基本思想和基本方法学习要点 : 数据结构的研究内容数据结构相关的概念和术语数据结构的三要素 : 逻辑结构物理结构和数据运算算法及算法的时间复杂度和空间复杂度的分析与计算 1.1 引言自 1946 年世界上第一台计算机诞生以来, 计算机产业飞速发展的速度远远超出了人们对它的预料现在计算机的应用已经渗透到人类生活的各个领域如今, 计算机的应用不再局限于科学计算, 而更多地用于过程控制管理信息处理等非数值计算领域计算机加工处理的对象也由数值发展到字符表格图形图像音频视频动画等具有一定结构的数据, 这就给程序设计带来一个新的课题为了编写出一个好的程序, 必须分析待处理对象的特性及各处理对象之间存在的关系这就是数据结构这门学科形成和发展的背景目前, 计算机更多的是用于过程控制事务管理信息处理等非数值计算领域计算机要进行信息处理首先要进行信息的表示, 信息的表示和组织又直接关系到处理信息的程序的效率随着应用问题的不断复杂, 导致信息量剧增与信息范围拓宽, 使许多系统程序和应用程序的规模很大, 结构又相当复杂因此, 必须分析待处理问题中对象的特征及各对象之间存在的关系, 这就是数据结构这门学科所要研究的问题一般来说, 用计算机解决一个具体问题时, 一般需要经过如下几个步骤 : 首先从具体问题中抽象出一个适当的数学模型, 然后选择或设计一个求解此数学模型的数据结构和算法, 接着编写程序进行调试测试, 最后运行该程序, 直至得到最终结果很多问题的求解最后都转化为求解数学方程或数学方程组, 即使是不需要计算机求解的简单问题也需要一个数学模型来描述例如, 大家熟悉的鸡兔同笼问题可转化为二元一次方程组进行求解又如, 在房屋设计或桥梁设计中的结构应力分析计算问题可化解为线性代数方程组求解的问题再如, 对于天天看到的天气预报, 它的数学模型是一个环流模式方程如果读者对此类的数学问题感兴趣, 可以学习计算方法等课程这些问题不作为数据结构所讨论的问题数据结构主要讨论非数值计算问题, 如人们在日常生活中遇到的下面一些问题 (1) 文档的编辑处理对一个班级学生信息的管理等问题用编辑器处理文档, 其实质是 1

12 对字符串的处理问题班级学生信息的管理问题主要考虑如何根据基本的操作有效地组织数据存储数据 (2) 八皇后问题在八皇后问题中, 处理过程不是根据某种确定的计算法则, 而是利用试探和回溯的探索技术求解为了求得合理布局, 在计算机中要存储布局的当前状态从最初的布局状态开始, 一步步地进行试探, 每试探一步形成一个新的状态, 整个试探过程形成了一棵隐含的状态树如图 1.1 所示 ( 为了描述方便, 将八皇后问题简化为四皇后问题 ) 图 1.1 四皇后问题中隐含的状态树回溯法求解过程实质上就是一个遍历状态树的过程在这个问题中所出现的树也是一种数据结构, 它可以应用在许多非数值计算的问题中 (3) 多叉路口信号灯的设置问题通常, 在多叉路口只需设红绿两色的交通灯便可以保证正常的交通秩序, 而在多叉路口须设计几种颜色的交通灯才能既使车辆相互之间不碰撞, 又能达到车辆的最大流量呢? 如图 1.2 所示的五叉路口, 其中 C 和 E 为单行道, 在路口有 13 条可行的通路 (A >B A >C A >D B >A D >C E >D B >C B >D E >A D >A D >B E >B E >C), 其中有的可以同时通行, 如 A >B 和 E >C, 而有的不能同时通行, 如 E >B 和 A >D 那么, 在路口应如何设置交通灯进行车辆的管理呢? 通常, 这类交通道路问题的数学模型是一种称为图的数据结构如图 1.3 所示, 图中每个圆圈 ( 又称为顶点 ) 表示五叉路口上的一条通路, 两个圆圈之间的连线 ( 又称为边 ) 表示两个圆圈所代表的通路, 不能同时通行, 则设置交通灯的问题等价为对图的顶点的染色问题, 要求对图上的每个顶点染一种颜色, 并且要求有线相连的两个顶点不能具有相同的颜色, 2

13 而总的颜色种类应尽可能地少如图 1.3 所示为一种染色结果, 圆圈中的数字表示交通灯的不同颜色 1 号色灯 :A >B A >C A >D B >A D >C E >D 2 号色灯 :B >C B >D E >A 3 号色灯 :D >A D >B 4 号色灯 :E >B E >C 图 1.2 多叉路口图 1.3 多叉路口各方向通路综上所述, 描述这类非数值计算问题的数学模型不再是数学方程, 而是诸如表树图之类的数据结构, 这些问题就是数据结构所研究的内容所以, 可以直观地认为数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象, 以及它们之间的关系操作存储等问题的学科 1968 年, 美国唐纳德克努特 (Donald Ervin Knuth) 教授开创数据结构的最初体系他的数百万字的多卷本计算机程序设计的艺术 (The Art of Computer Programming) 堪称计算机科学理论与技术的经典巨著 1968 年出版的该巨著第一卷基本算法是第一本较系统地阐述数据的逻辑结构存储结构及其操作的著作该巨著的第一卷和 1973 年出版的第三卷排序与搜索中的一些基本内容就构成了数据结构的最初体系由于唐纳德克努特对计算机科学的卓越贡献, 他本人获得了 1974 年的图灵奖数据结构从诞生到现在, 在不到半个世纪的时间里形成了坚实的理论基础和广泛的应用领域, 吸引越来越多的研究者加入数据结构的诞生和发展给计算机信息管理带来了一场巨大的革命同时, 随着应用的扩展与深入, 数据结构的研究领域也已经大大地拓广和深化 1.2 数据结构的基本概念数据结构是计算机科学与技术专业最重要的专业基础核心课程所有计算机系统软件和应用软件都要用到各种类型的数据结构因此, 要想更好地运用计算机来解决实际问题, 仅掌握几种计算机程序设计语言是难以应付众多复杂问题的要想有效地使用计算机充分发挥计算机的性能, 还必须学习和掌握好数据结构的有关知识打好数据结构这门课程的扎实基础, 对于学习计算机专业的其他课程, 如算法设计与分析操作系统编译原理数据库管理系统软件工程人工智能等都是非常最重要的 3

14 1.2.1 有关概念和术语在系统地学习数据结构知识之前, 先对一些基本概念和术语赋予确切的定义数据 (Data): 是信息的载体, 是描述客观事物属性的数字字符及所有能够输入到计算机中并被计算机识别存储和加工处理的符号的集合数据是计算机程序加工的原料, 是计算机加工处理的对象它可以是数值数据, 也可以是非数值数据数值数据是一些整数实数或复数, 主要用于工程计算科学计算和商务处理等 ; 非数值数据包括字符文字图形图像语音等数据项 (Data Item): 是数据中不可分割, 且具有独立含义的最小单位, 数据元素是数据项的集合数据元素 (Data Element): 是数据的基本单位, 通常作为一个整体进行考虑和处理一个数据元素可以由若干个数据项来组成, 数据项是构成数据元素不可分割的最小单位在有些情况下, 数据元素也称为元素结点顶点和记录例如, 学生记录就是一个数据元素, 由学号姓名性别等数据项组成数据对象 (Data Object): 是具有相同性质的数据元素的集合, 是数据的一个子集数据结构 (Data Structure): 是指互相之间存在一种或多种关系的数据元素的集合数据结构包括逻辑结构存储结构和数据的运算三方面的内容 ( 也称为数据结构三要素 ) 数据的逻辑结构和存储结构是密不可分的两个方面, 一个算法的设计取决于所选定的逻辑结构, 而算法的实现依赖所采用的存储结构数据的逻辑结构在任何问题中, 数据元素之间都不会是孤立的, 它们之间都存在这样或那样的关系, 这种数据元素之间的关系称为结构根据数据元素间关系的不同特性, 通常有集合结构线性结构树形结构图形结构等 4 种基本的逻辑结构, 如图 1.4 所示图 1.4 数据的逻辑结构 (1) 集合结构 : 在集合结构中, 数据元素间的关系是属于同一个集合集合是元素关系极为松散的一种结构 (2) 线性结构 : 该结构的数据元素之间存在一对一的关系 (3) 树型结构 : 该结构的数据元素之间存在一对多的关系 (4) 图形结构 : 该结构的数据元素之间存在多对多的关系, 图形结构也称为作网状结构 4

15 数据的逻辑结构又可分为线性结构和非线性结构线性结构又包括一般线性表操作受限线性表 ( 栈队列串 ) 和线性表推广 ( 数组广义表 ) 非线性结构又包括集合树形结构和图形结构数据的存储结构数据结构在计算机中的表示 ( 又称为映像 ) 称为数据的物理结构, 又称为存储结构它不同于逻辑结构, 是依赖计算机语言的, 是具体的通常, 一个数据元素在计算机内用一块连续的存储单元来表示那么, 在计算机中怎样存储表中所有的数据元素呢? 数据结构一般用下面四种基本的存储结构来表示数据元素之间的关系 1. 顺序存储结构该方法把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里, 数据元素之间的逻辑关系由存储单元的邻接关系来体现, 由此得到的存储表示称为顺序存储结构顺序存储结构主要应用于线性结构, 非线性结构也可以通过某种线性的方法实现顺序存储其优点是可以实现随机存取, 每个元素占用最少的存储空间, 即存储密度大其缺点是只能使用相邻的一整块存储单元, 因此可能产生较多的外部碎片 2. 链式存储结构该方法不要求逻辑上相邻的数据元素在物理位置上也相邻, 数据元素之间的逻辑关系由附加的指针表示, 由此得到的存储表示称为链式存储结构其优点是不会出现碎片现象, 可充分利用所有存储单元其缺点是每个元素因存储指针而占用额外的存储空间, 并且只能实现顺序存取 3. 索引存储结构该方法通常在存储数据元素信息的同时, 还建立附加的索引表索引表由若干索引项组成索引项的一般形式是 :( 关键字地址 ) 关键字(Key) 是能唯一标识一个数据元素的那些数据项其优点是检索速度快缺点是增加附加的索引表占用较多的存储空间在增加和删除数据时要修改索引表, 因而花费较多的时间 4. 哈希 ( 散列 ) 存储结构该方法的基本思想是根据数据元素的关键字直接计算出该数据元素的存储地址其优点是检索增加删除结点的操作都很快缺点是如果散列函数不好, 可能出现数据元素存储地址的冲突, 而解决冲突会增加时间和空间开销这四种基本存储方法既可以单独使用, 也可以组合起来对数据结构进行存储映像同一逻辑结构采用不同的存储方法, 可以得到不同的存储结构 ; 采用不同的存储结构, 其数据处理效率往往不同选择何种存储结构来表示相应的逻辑结构, 视具体要求而定, 主要考虑运算方便及算法的时空要求数据的运算为了有效地处理数据, 可将数据按一定的逻辑结构组织起来, 并选择适当的存储方法存储数据, 然后再对数据进行运算 5

16 数据的运算是定义在数据的逻辑结构之上的, 每一种逻辑结构都有一个运算的集合, 并指出运算的功能, 例如, 查找插入删除修改等, 这些运算实际上是在数据元素上施加的一系列的抽象操作所谓抽象操作, 是只知道这些操作要求做什么, 而无须考虑如何做, 只有在确定了存储结构之后, 才考虑如何具体实现这些运算下面介绍几种常见的数据运算 (1) 建立 (Create) 一个数据结构 ; (2) 消除 (Cancel) 一个数据结构 ; (3) 从一个数据结构中删除 (Delete) 一个数据元素 ; (4) 把一个数据元素插入 (Insert) 到一个数据结构中 ; (5) 对一个数据结构进行访问 (Visit); (6) 对一个数据结构中的数据元素进行修改 (Modify); (7) 对一个数据结构进行排序 (Sort); (8) 对一个数据结构进行查找 (Search) 由于数据的运算是建立在数据的逻辑结构之上的, 因此, 某一种具体的数据结构, 除了这些基本运算之外, 根据实际问题还有其特有的一些运算例如 : 在城市交通问题中, 求两城市之间最短路线的算法 ; 判断从城市的任一点出发乘坐公共汽车是否可以达到城市任何地方的运算 ; 在家族中如何找到某个人的兄弟等运算 ; 在电话号码管理问题中如何高效快速查找相关联系人等运算所以, 数据的其他运算是除了基本运算之外根据处理的问题灵活出现的在数据结构的教学中一般只讨论那些基本运算数据结构的发展趋势包括两个方面 : 一是面向专门领域中特殊问题的数据结构的研究和发展, 如图形数据结构知识数据结构空间数据结构 ; 二是从抽象数据类型的角度出发, 用面向对象的观点来讨论数据结构 1.3 数据类型和抽象数据类型数据类型数据类型是和数据结构密切相关的一个概念它最早出现在高级程序设计语言中, 用以刻画程序中操作对象的特性在用高级语言编写的程序中, 每个变量常量或表达式都有一个它所属的确定的数据类型数据类型显性或隐性规定在程序执行期间变量或表达式所有可能的取值范围, 以及在这些值上允许进行的操作因此, 数据类型 (Data Type) 是一个值的集合和定义在这个值集上的一组操作的总称在高级程序设计语言中, 数据类型可分为两类 : 一类是原子类型, 另一类则是结构类型原子类型的值是不可分解的, 如 C 语言中整型字符型浮点型双精度型等基本类型, 分别用保留字 int char float double 标识结构类型的值是由若干成分按某种结构组成的, 因此是可分解的, 并且它的成分可以是结构的, 也可以是非结构的例如, 数组的值由若干分量组成, 每个分量可以是整数, 也可以是数组等在某种意义上, 数据结构可以看成是一组具有相同结构的值, 而数据类型则可被看成是由一种数据结构和定义在其上的一组操作所组成的 6

17 1.3.2 抽象数据类型抽象数据类型 (Abstract Data Type,ADT) 是指一个数学模型, 以及定义在该模型上的一组操作抽象数据类型的定义取决于它的一组逻辑特性, 而与其在计算机内部如何表示和实现无关, 即不论其内部结构如何变化, 只要它的数学特性不变, 不影响其外部使用抽象数据类型和数据类型实质上是一种概念例如, 各种计算机都拥有的整数类型就是一种抽象数据类型, 尽管它们在不同处理器上的实现方法可以不同, 但由于其定义的数学特性相同, 在用户看来都是相同的因此, 抽象的意义在于数据类型的数学抽象特性在另一方面, 抽象数据类型的范畴更广, 它不再局限于前述各处理器中已定义并实现的数据类型, 还包括用户在设计软件系统时自己定义的数据类型为了提高软件的重用度, 在程序设计方法学中, 要求在构成软件系统每个相对独立的模块上定义一组数据和施于这些数据上的一组操作, 并在模块的内部给出这些数据的表示方法及其操作的细节, 而在模块的外部使用的只是抽象的数据及抽象的操作这也就是面向对象的程序设计方法可以用数据对象数据关系和基本操作定义一个完整的抽象数据类型抽象数据类型的定义形式如下 ADT 抽象数据类型名 { 数据对象 :< 数据对象的定义 > 数据关系 :< 数据关系的定义 > 基本操作 :< 基本操作的定义 > }ADT 抽象数据类型名其中, 数据对象和数据关系的定义用伪码描述, 基本操作的定义格式为 : 基本操作名 ( 参数表 ) 初始条件 :< 初始条件描述 > 操作结果 :< 操作结果描述 > 初始条件用来描述操作执行之前数据结构和参数应满足的条件, 若不满足, 则操作失败, 返回相应的出错信息操作结果用来描述操作正常完成之后, 数据结构的变化状况和应返回的结果例 1.1 用抽象数据类型定义一个三元组三元组即排列在一起的 3 个元素, 可以对三元组进行的操作有 : 初始化三元组销毁三元组获取三元组中一个元素的值改变三元组中一个元素的值判断三元组中的元素是否按升序排列判断三元组中元素的值是否按降序排序求三元组中元素的最大值求三元组中元素的最小值三元组 ADT 描述如下 ADT Triplet{ 数据对象 :D={e1,e2,e3 e1,e2,e3 ElemSet } 数据关系 :R={< e1,e2>,< e2,e3>} 基本操作 : (1) 三元组的初始化 :InitTriplet(&T,v1,v2,v3) 初始条件 : 三元组 T 不存在操作结果 : 构造三元组 T, 元素 e1,e2,e3 分别被赋值为 v1,v2,v3 (2) 销毁三元组 :DestroyTriplet(&T) 初始条件 : 三元组 T 已存在 7

18 操作结果 : 三元组 T 被销毁 (3) 取三元组中元素 :Get(T,i,&e) 初始条件 : 三元组 T 已存在,1 i 3 操作结果 : 用 e 返回 T 中第 i 个元素的值 (4) 修改三元组元素 :Put(T,i,e) 初始条件 : 三元组 T 已存在,1 i 3 操作结果 : 将 T 中第 i 个元素的值修改为 e (5) 升序排序 :IsAscending(T) 初始条件 : 三元组 T 已存在操作结果 : 若 T 中的元素按升序排列, 则返回 1, 否则返回 0 (6) 降序排序 :IsDescending(T) 初始条件 : 三元组 T 已存在操作结果 : 若 T 中的元素按降序排列, 则返回 1, 否则返回 0 (7) 求最大值 :Max(T,&e) 初始条件 : 三元组 T 已存在操作结果 : 用 e 返回 T 的三个元素中的最大值 (8) 求最小值 :Min(T,&e) 初始条件 : 三元组 T 已存在操作结果 : 用 e 返回 T 的三个元素中的最小值 }ADT Triplet 多形数据类型 (Polymorphic Data Type) 是指其值的成分不确定的数据类型可以看出上面定义的三元组 Triplet 是一个多形数据类型, 其数据元素 e1,e2,e3 可以是整数实数字符字符串, 也可以是更为复杂的结构体类型, 如学生图书商品等其他类型的数据元素从抽象数据类型的角度来看, 具有相同的数学抽象特性, 故称为多形数据类型 1.4 算法算法与数据结构关系紧密, 在算法设计时先要确定相应的数据结构, 而在讨论某一种数据结构时也必然会涉及相应的算法下面就从算法特性算法描述常见的算法设计方法等三个方面对算法进行介绍算法及其特征算法 (Algorithm) 是对特定问题求解步骤的一种描述, 是指令的有限序列, 其中每一条指令表示一个或多个操作例如, 将一维数组 A 的 n 个元素倒置算法可描述如下 :1 首先设置 i=0,j=n 1;2 当 i<j 时, 交换 A[i] 和 A[j];3i 向后走一个位置,j 向前走一个位置 ;4 判断 i<j 是否成立, 若成立转 2 继续执行, 否则算法结束一个算法应该具有有穷性确定性可行性零个或多个输入一个或多个输出等特征 (1) 有穷性 : 一个算法对于任何合法的输入值必须总是在执行有穷步之后结束, 且每一步都可在有穷时间内完成 8

19 (2) 确定性 : 算法中的每一条指令必须有确切的含义, 读者理解时不会产生二义对于相同的输入, 算法在执行时对应着唯一的一条执行路经, 所以也只能得出相同的输出 (3) 可行性 : 算法描述的操作都可以通过已经实现的基本运算的有限次执行得以实现 (4) 输入 : 算法具有零个或多个输入, 这些输入取自特定的数据对象集合 (5) 输出 : 算法具有一个或多个输出, 这些输出同输入之间存在某种特定的关系算法的含义与程序十分相似, 但又有区别一个程序不一定满足有穷性, 例如, 操作系统只要整个系统不遭破坏, 它永远不会停止, 即使没有作业需要处理, 它仍处于动态等待中因此, 操作系统不是一个算法另一方面, 程序中的指令必须是机器可执行的, 而算法中的指令则无此限制算法代表了对问题的求解, 而程序则由算法在计算机上特定实现一个算法若用程序设计语言来描述, 则它就是一个程序算法与数据结构是相辅相承的解决某一特定类型问题的算法可以选用不同的数据结构, 而且选择恰当与否直接影响算法的效率反之, 一种数据结构的优劣由各种算法的执行来体现要设计一个好的算法通常要考虑达到以下目标 (1) 正确性 : 算法的执行结果应当满足预先规定的功能和性能要求 (2) 可读性 : 一个算法应当思路清晰层次分明简单明了易读易懂 (3) 健壮性 : 输入不合法数据时, 应能适当处理, 不至引起严重后果 (4) 通用性 : 算法应具有一般性, 即算法的处理结果对于一般的数据集合都成立 (5) 高效率与低存储量需求 : 高效率指的是算法执行的时间要快 ; 低存储量需求指算法执行过程中所需要的最大存储空间要小在一般情况下, 两者与问题的规模有关, 且高效率与低存储是一对矛盾体常见的算法描述方法算法可以使用各种不同的方法来描述最简单的方法是使用自然语言用自然语言来描述算法的优点是简单且便于人们对算法的阅读, 缺点是不够严谨通常, 可以采用下列四种方法描述一个算法 (1) 流程图算法描述这种描述方法直观易懂, 但用来描述比较复杂的算法时就显得不够方便, 也不够清晰简洁 (2) 非形式算法描述用中文语言, 同时还使用一些程序设计语言中的语句来描述算法, 这称为非形式算法描述这种方法比较自然方便表达, 但经常会不够准确, 容易产生二义性 (3) 类语言 ( 伪代码 ) 算法描述这种算法不能直接在计算机上运行, 但专业设计人员经常使用类 C 语言类 Java 语言等来描述算法它容易编写阅读和统一格式, 也比较容易转换为高级语言程序, 便于算法实现 (4) 高级语言编写的程序或函数这是可以在计算机上运行并获得结果的算法, 使给定问题能在有限时间内被求解, 但要求符合高级语言的规则使用程序流程图和非形式算法描述的特点是描述过程简洁明了用以上两种方法描述的算法不能够直接在计算机上执行, 若要将它转换成可执行的程序, 还有一个编程的问题可以直接使用某种程序设计语言来描述算法, 但直接使用程序设计语言并不容易, 而且不太直观, 常常须借助注释才能使人看明白 9

20 为了解决理解与执行这两者之间的矛盾, 人们常常使用一种称为伪码语言的描述方法来进行算法描述伪码语言介于高级程序设计语言和自然语言之间, 它忽略高级程序设计语言中一些严格的语法规则与描述细节, 因此它比程序设计语言更容易描述和被人理解, 而比自然语言更接近程序设计语言它虽然不能直接执行, 但很容易被转换成高级语言高级语言最大的特点是能直接在计算机上运行, 让人们可以直观地看到算法运行的结果常见的算法设计方法算法是程序设计的灵魂, 它在产生程序的过程中占有重要的地位, 常见的算法设计方法有贪婪法递归法回溯法分治法等方法 : (1) 贪婪法贪婪法 (Greedy) 能够解决不同领域中的问题事实上, 找最小耗费生成树的 Kruskal 算法单源问题的 Dijkstra 算法等都是采用贪婪法的设计技术贪婪法是一种对某些求最优解问题更简单更迅速的设计方法但使用贪婪法是否能得到最优解, 是必须加以证明的 (2) 递归法递归法是算法设计中一种重要的方法递归子程序 ( 包括直接递归和间接递归子程序 ) 都是最终通过自己调用自己, 将求解问题转化成性质相同的子问题, 从而达到求解的目的递归算法充分地利用了计算机系统内部功能, 自动实现调用过程中对相关且必要的信息的保存与恢复功能, 从而省略了求解过程中许多细节的描述利用递归求解是训练有素的软件设计人员设计算法的常用方法递归算法的程序设计存在两个问题 :1 并不是所有的语言都支持递归法 ;2 递归程序比非递归程序要花费更多的时间, 当递归层数太多时, 会出现栈溢出对于许多复杂问题求解, 递归法比非递归法容易设计因此, 通常先设计出递归程序, 然后再转化成非递归程序, 而不是直接写出非递归程序 (3) 回溯法回溯法是一种满足某约束条件的穷举式搜索技术, 适应于解决一些组合数相当大的问题, 是算法设计的重要方法之一它的解题方式用通俗的语言说就是走不通回头, 最贴近人的本能思维对于那些涉及寻找一组解的问题或者求某约束条件的最优解答问题, 可以用回溯法来求解例如, 皇后问题迷宫问题子集和数问题图的染色问题等都可以用回溯法来求解 (4) 分治法在现实生活中, 对于求解一个复杂的问题或一个较大的问题, 经过系统地分析, 将其划分成一些简单问题或较小问题进行解决当这些问题解决之后, 把它们的解联结起来, 得到原问题的解这种分而治之的思想也应用于算法设计中即对于求解问题进行系统分析之后, 将其分解成若干个性质相同的子问题, 所得结果称为求解子集对这些求解子集分别处理如果某些子集还需分而治之, 再递归地使用上述方法, 直到求解子集不再细分为止最后归并子集的解即得原问题的解具有这种设计思想的算法设计方法称为分治法 1.5 算法性能分析与度量求解同一个问题, 可以有许多不同的算法, 那么如何来评价这些算法的优劣呢? 显然, 首先要求选用的算法应该是正确的, 此外, 主要考虑如下三点 : (1) 执行算法所耗费的时间 10

<4D F736F F D B8BDBCFE4220D7A8D2B5BBF9B4A1D3EBBACBD0C4BFCEB3CCC3E8CAF62E646F6378>

<4D F736F F D B8BDBCFE4220D7A8D2B5BBF9B4A1D3EBBACBD0C4BFCEB3CCC3E8CAF62E646F6378> B212CC: 数据结构与算法课程描述 0 课程基本信息课程编号 : B212CC 课程名称 : 数据结构与算法英文名称 : Data Structures and Algorithms 英文简称 : DSA 预备课程 : 计算系统基础离散数学授课时间 : 二年级第一学期时间分配 : 课堂教学 (48 课时 )+ 实验安排 (48 课时 )+ 课后作业与阅读 (48 课时 ) 学分数 : 3