内容简介本书基于我们多年的教学经验从实用的角度出发对线性和非线性数据结构的顺序和链式存储及其操作进行了详细讲解书中的每一章均配有实践练习及大量习题实现了理论与实践相结合让学生学以致用本书免费提供电子课件源程序及习题答案全部案例均在 Visual C 环境中成功

Size: px

Start display at page:

Download "内容简介本书基于我们多年的教学经验从实用的角度出发对线性和非线性数据结构的顺序和链式存储及其操作进行了详细讲解书中的每一章均配有实践练习及大量习题实现了理论与实践相结合让学生学以致用本书免费提供电子课件源程序及习题答案全部案例均在 Visual C 环境中成功"

谐单
5 years ago
Views:

1 高等学校计算机应用规划教材数据结构 (C 语言版 ) 梁海英王凤领谭晓东巫湘林张波胡元闯主编副主编北京

2 内容简介本书基于我们多年的教学经验从实用的角度出发对线性和非线性数据结构的顺序和链式存储及其操作进行了详细讲解书中的每一章均配有实践练习及大量习题实现了理论与实践相结合让学生学以致用本书免费提供电子课件源程序及习题答案全部案例均在 Visual C 环境中成功运行本书既可作为普通高校非计算机专业的计算机公共课教材计算机类应用型本科及专科教材也可作为计算机软件考试的优秀教材本书对应的电子课件习题答案和源代码可以到网站下载本书封面贴有清华大学出版社防伪标签无标签者不得销售版权所有侵权必究侵权举报电话图书在版编目(CIP)数据数据结构 C 语言版 / 梁海英王凤领主编. 北京清华大学出版社 2017 (高等学校计算机应用规划教材) ISBN Ⅰ. ①数 Ⅱ. ①梁 ②王 Ⅲ. ①数据结构高等学校教材 ②C语言程序设计高等学校教材 Ⅳ. ①TP ②TP312.8 中国版本图书馆 CIP 数据核字(2017)第号责任编辑胡辰浩马玉萍装帧设计孔祥峰责任校对曹阳责任印制出版发行清华大学出版社网址地址北京清华大学学研大厦 A 座社总机邮编邮购投稿与读者服务 , c-service@tup.tsinghua.edu.cn 质量反馈 , zhiliang@tup.tsinghua.edu.cn 印刷者装订者经销全国新华书店开本 185mm 260mm 印张 21 版次 2017 年 8 月第 1 版印次 2017 年 8 月第 1 次印刷印数 1~2500 定价元字数 511 千字产品编号

3 前言数据结构在计算机科学中是一门综合性的专业基础课, 是介于数学计算机硬件和计算机软件三者之间的一门核心课程数据结构不仅是一般程序设计的基础, 而且是设计和实现编译程序操作系统数据库系统及其他系统程序的重要基础目前比较权威的数据结构教材大多是考研指定教材, 难度比较大, 不太适合应用型本科三本及专科学生使用为此, 我们编写了这本教材, 通过引入大量案例, 将复杂的理论问题直观化, 案例驱动式教学, 更有利于这个层次的学生接受我们基于多年的丰富的教学经验及素材积累, 精心编写此书, 目的是让初学者能循序渐进地掌握各种数据结构及操作, 力求透彻全面易学易用, 充分调动学生的学习积极性书中使用 C 语言定义各种数据结构描述算法本书对每种数据结构和算法的剖析都遵循由浅入深的原则, 并配以实用的案例和图示, 配有相应的 C 语言源代码, 适合具有 C 语言基础的数据结构初学者全书共分 8 章, 对于常用的数据结构, 如线性表栈队列串矩阵广义表树二叉树图等进行深入讲解, 使读者能够全面地理解基本概念逻辑结构存储结构操作运算实现算法以及案例应用, 进而利用比较法讲解各种查找和排序的方法, 并对各种算法的性能进行分析, 以便在不同的应用场合选取合适的方法本书由梁海英博士和王凤领教授任主编, 谭晓东巫湘林张波和胡元闯任副主编, 全书由贺州学院梁海英教授统稿在本书编写过程中, 得到了所在学院的同事的热心帮助和支持, 参加本书内容编写程序调试课件制作习题收集答案制作内容审校等工作的老师有赵方珍罗兰花李立信千文黄华升陈冠萍袁淑丹等, 在此向他们表示衷心的感谢! 由于水平有限, 书中难免存在不妥之处, 敬请读者谅解, 并提出宝贵意见我们的电话是 , 信箱是 huchenhao@263.net 本书对应的电子课件习题答案和源代码可以到网站下载编者 2017 年 5 月

4 目录第 1 章绪论数据结构概述常用术语和基本概念数据类型数据类型概述抽象数据类型算法和算法复杂度算法的重要性时间复杂度空间复杂度本章实战练习本章小结习题第 2 章线性表线性表概述线性表的定义及特点线性表的抽象数据类型的定义线性表的顺序存储及运算的实现线性表的顺序存储顺序表的基本操作线性表的链式存储及运算的实现单链表循环链表双向链表本章实战练习顺序表的常用操作单链表的常用操作通讯录管理本章小结习题第 3 章栈和队列栈栈的定义栈的顺序存储与操作栈的链式存储与操作队列队列的定义队列的顺序存储与操作队列的链式存储与操作本章实战练习 top 为指针且指向栈顶元素的下一个位置 top 为整数且指向栈顶元素的下一个位置栈的应用数制转换顺序队列的基本操作循环队列设置不同队空与队满条件的解决方案链队列的基本操作本章小结习题第 4 章串数组矩阵和广义表串的定义串的基本概念串的抽象数据类型的定义串的存储与操作串的顺序存储与操作串的链式存储与操作数组

5 IV 数据结构 (C 语言版 ) 数组的定义数组的顺序存储矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵及其压缩存储广义表广义表的定义广义表的存储结构及实现本章实战练习串的常见操作串的基本操作及应用数组应用方阵数组应用稀疏矩阵本章小结习题第 5 章树树的概念树的定义树的基本术语二叉树二叉树的定义二叉树的性质二叉树的存储结构二叉树的顺序存储二叉树的链式存储与操作二叉树的遍历遍历算法线索二叉树遍历算法的应用举例树与森林树和森林的存储二叉树树和森林的转换树和森林的遍历哈夫曼树哈夫曼树的定义哈夫曼树的构造算法哈夫曼编码本章实战练习二叉树的基本操作线索二叉树的操作树的应用模拟资源管理器哈夫曼树构造本章小结习题第 6 章图图的定义和基本术语图的定义图的基本术语图的存储与操作邻接矩阵邻接表十字链表图的遍历深度优先遍历算法广度优先遍历算法图与最小生成树生成树和森林的算法最小生成树最短路径单源点到其余各顶点的最短路径任意源点之间的最短路径 AOV 网与拓扑排序 AOV 网拓扑排序 AOE 网与关键路径 AOE 网

6 目录 V 关键路径本章实战练习图的邻接矩阵操作图的邻接表操作利用邻接矩阵实现连通图的深度优先遍历利用邻接表实现连通图的深度优先遍历利用邻接矩阵实现连通图的广度优先遍历利用邻接表实现连通图的广度优先遍历普里姆最小生成树算法迪杰斯特拉最短路径算法本章小结习题第 7 章查找查找的定义静态查找算法顺序查找折半查找分块查找动态查找算法二叉排序树平衡二叉树哈希表哈希表的定义哈希函数的构造处理冲突的方法哈希表的查找和性能本章实战练习顺序查找算法折半查找算法二叉排序树查找算法本章小结习题第 8 章排序排序的定义插入排序算法直接插入排序折半插入排序二路插入排序表插入排序希尔排序交换排序算法冒泡排序快速排序选择排序算法直接选择排序堆排序归并排序算法排序算法的比较本章实战练习本章小结习题参考文献

7 第 1 章绪论本章对数据结构进行简要概述, 主要介绍数据结构的相关概念以及它所研究的问题与内容, 目的是让读者对数据结构有个大致的了解, 为后续内容的学习提供必要的基础知识本章介绍的主要内容包括 : 数据结构概述常用术语和基本概念数据类型算法和算法复杂度 1. 总体要求了解数据结构的意义, 数据结构在计算机领域中的地位和作用 ; 掌握数据结构各名词术语的含义和有关的基本概念 ; 数据的逻辑结构和存储结构之间的关系 ; 了解使用 C 语言对数据结构进行抽象数据类型的存储和实现的方法 ; 了解算法的五个特征 ; 掌握通过计算语句执行次数来估算算法时间复杂度的方法 2. 相关知识点相关术语 : 数据数据元素数据项数据对象数据结构数据的逻辑结构 : 集合线性结构树和图数据的物理结构 : 顺序和非顺序结构算法的五个特征时间复杂度及空间复杂度 3. 学习重点数据的逻辑结构和存储结构及其之间的关系 ; 算法时间复杂度空间复杂度及其计算 1.1 数据结构概述数据结构 (Data Structure)+ 算法 (Algorithm)= 程序 (Program) 计算机算法与数据的结构密切相关, 算法无不依附于具体的数据结构, 数据结构直接关系到算法的选择和效率运算由计算机来完成, 这就需要设计相应的插入删除和修改的算法也就是说, 数据结构还需要给出每种结构类型所定义的各种运算的算法一般来说, 用计算机来解决一个具体问题时, 大致需要经过以下几个步骤 : 首先, 要从具体问题中抽象出一个适当的数学模型, 然后设计一个解此数学模型的算法 (Algorithm), 最后编写程序进行测试, 调试和运行直到得到最终解答寻求数学模型的实质是分析问题, 从中提取操作的对象, 并找出这些操作对象之间含有的关系, 然后用数学的语言加以描述当人们用计算机处理数值计算问题时, 所用的数学模型是用数学方程描述的所涉及的运算对象一般是简单的整型实型和逻辑型数据, 因此程序设计者的主要精力集中于程序设计技巧上, 而不是数据的存储和组织上然而,

8 2 数据结构 (C 语言版 ) 计算机应用的更多领域是非数值型计算问题, 它们的数学模型无法用数学方程描述, 而是用数据结构描述, 解决此类问题的关键是设计出合适的数据结构, 非数值型问题的数学模型是用线性表树图等结构来描述的例 1.1 学生信息登记表每年新生入学都会用类似表 1.1 所示的二维表进行信息登记, 以便完成各种数据的统计, 比如, 统计男生和女生的比例生源籍贯等二维表 ( 即线性表 ) 是经常用到的数学模型表 1.1 学生信息登记表学号姓名性别民族籍贯出生日期苏宏男汉族南宁市梁琪女汉族贵港市韦华男壮族崇左市覃婷女汉族南宁市例 1.2 酒店管理系统中的客房分配问题在酒店的客房分配管理中, 希望同类房中各间客房的入住机会均等, 以保证维持一个平均的磨损率为此, 分配客房的算法应该是先退的客房先被启用相应地, 所有空的同类客房的管理模型应该是一个队列, 即酒店前台每次接待客人入住时, 从队头分配客房 ; 当客人结账离开时, 应将退掉的空客房排在队尾, 如图 1.1 所示队列是经常用到的一种数学模型客人入住 a 0,a 1, a 2,, a n-1 客人退房队头图 1.1 酒店客房管理队尾例 1.3 人机对弈问题将对弈的策略事先存入计算机中, 然后计算机才能和人进行对弈在对弈问题中, 计算机操作的对象是对弈过程中可能出现的棋盘状态 ( 称为格局 ) 例如, 图 1.2(a) 所示为井字棋的一个格局, 而格局之间的关系是由比赛规则决定的通常, 这个关系不是线性的, 因为从一个棋盘格局可以派生出几个格局, 例如, 从图 1.2(a) 所示的格局可以派生出 5 个格局, 如图 1.2(b) 所示, 而从每一个新的格局又可派生出 4 个可能出现的格局因此, 若将从对弈开始到结束的过程中所有可能出现的格局都画在一张图上, 则可得到一棵倒立生长的树树根是对弈开始之前的棋盘格局, 而所有的叶子就是可能出现的格局, 对弈的过程就是从树根沿树杈到某个叶子的过程树可以是某些非数值计算问题的数学模型, 它也是一种数据结构综合以上 3 个例子可见, 描述这类非数值计算问题的数学模型不再是数学方程, 而是诸如二维表队列和树之类的数据结构因此, 简单来说, 在非数值计算的程序设计问题中, 数据结构是一门研究计算机的操作对象及其相互之间的关系和运算等的学科

9 第 1 章绪论 3 (a) 棋盘格局示例 (b) 对弈树的局部图 1.2 人机对弈 1.2 常用术语和基本概念要学好数据结构这门课程, 必须要明确各种概念及其相互之间的关系本节只介绍一些常用的术语和基本概念, 其他的相关术语和概念将在以后各章节中陆续讲解 1. 数据数据 (Data) 是信息的载体, 是可以被计算机识别存储并加工处理的描述客观事物的信息符号的总称在计算机学科中, 数据是指所有能输入到计算机中, 并能被计算机程序所处理的符号的集合, 它是计算机程序加工处理的对象因此, 客观事物包括数值字符声音图形图像等, 它们本身并不是数据, 只有通过编码变成能被计算机识别存储和处理的符号后才是数据 2. 数据元素和数据项数据元素 (Data Element) 是描述数据的基本单位, 一个数据元素由若干个数据项组成数据项 (Data Item) 是描述数据的最小单位在计算机中存储数据时, 都是以一个数据元素为单位的数据项分为两种类型 : 组合项和原子项 (1) 组合项若数据元素可再分, 则每一个独立的处理单元就是数据项, 数据元素是数据项的集合例如, 用一条记录表示一个数据元素时, 这条记录中一般会有多个描述记录属性的小项,

10 4 数据结构 (C 语言版 ) 称为数据项通常, 数据项是不可再分的数据 (2) 原子项若数据元素不可再分, 则数据元素和数据项是同一概念, 如 : 整数 "5" 字符"A" 等例如, 例 1.1 描述一个学生信息的数据元素可由下列 6 个数据项构成 : 学号姓名性别民族籍贯出生日期其中, 出生日期又可以由 3 个数据项 " 年 " " 月 " 和 " 日 " 组成, 因此称 " 出生日期 " 为组合项, 而其他不可分割的数据项为原子项 3. 数据对象数据对象 (Data Object) 是性质相同的一类数据元素的集合, 是数据的一个子集例如, 整数数据对象是 {0,±1,±2,±3, }, 字符数据对象是 {a,b,c, } 数据对象可以是有限的, 也可以是无限的 4. 数据结构数据结构 (Data Structure) 由数据和结构两部分构成其中, 数据部分是指数据元素的集合 ; 结构就是关系, 结构部分是指数据元素之间关系的集合所以, 数据结构就是指数据元素的集合及数据元素之间关系的集合概括地讲, 数据结构就是指相互之间有一种或多种特定关系的数据元素的集合在计算机上要处理数据, 就要保存数据及它们之间的关系在这里, 关系就是数据的逻辑结构, 它指反映数据元素之间的逻辑关系的数据结构, 其中的逻辑关系是指数据元素之间的前后件关系, 而与它们在计算机中的存储位置无关 (1) 数据的逻辑结构数据的逻辑结构 (Logic Structure) 是从具体问题抽象出来的数学模型, 与数据在计算机中的具体存储没有关系数据的逻辑结构独立于计算机, 是数据本身所固有的特性从逻辑上可以把数据结构分为线性结构和非线性结构, 主要包括 : 集合线性树形和图状结构 : 1 集合结构集合结构 (Set Structure) 中的数据元素除了同属于一个集合的关系外, 再无其他关系如整数集字符集等 2 线性结构线性结构 (Linear Structure) 中的数据元素之间存在一对一的关系比如数组队列等 3 树形结构树形结构 (Tree Structure) 中的数据元素之间存在一对多的关系比如例 1.3 中的人机对弈等 4 图状结构图状结构 (Graphic Structure, 也称网状结构 ) 中的数据元素之间存在多对多的关系比如城市交通图等图 1.3 是上述几种结构的关系图其中, 树形结构和图状结构又称为非线性结构由于集合中数据元素之间的关系是非常松散的, 因此, 常用其他几种结构来描述集合

11 第 1 章绪论 5 (a) (a) 集合结构 (b) (b) 线性结构 (c) (c) 树形结构树型结构 (d) (d) 网状结构图 1.3 四种基本数据结构关系图数据结构由相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成数据结构的形式化定义记为 :Data_Structure=(D,R) 其中,D 是数据元素的有限集合,R 是数据集合 D 中所有元素之间的关系的有限集合例 1.4 定义集合 D={3, 6, 9, 18, 27} 的数据结构 DS 1 =(D,R 1 ), 其中 R 1 定义为 D 上的 > ( 大于 ) 关系, 则数据结构 DS 1 可以表示为如图 1.4(a) 所示的形式, 该结构为线性结构 DS 2 =(D,R 2 ), 其中 R 2 定义为 D 上的整除关系, 则 R 2 ={(3,6),(3,9),(3,18),(3,27),(6,18),(9,18),(9,27)}, 数据结构 DS 2 可以表示为如图 1.4(b) 所示的形式, 该结构为图状结构 (a) 数据结构 DS (b) 数据结构 DS 2 图 1.4 集合 D 上定义的两个数据结构从上面的例子可以看出, 即使是由相同元素构成的集合, 只要定义的关系不同, 也不是同一数据结构数据结构不仅描述了结构中的元素, 还描述了这些元素之间的关系数据结构的定义仅是对操作对象的一种数学描述, 结构中定义的关系是数据元素之间的逻辑关系数据结构可以分为逻辑上的数据结构和物理上的数据结构数据结构的形式化定义为逻辑结构物理结构为数据在计算机中的存储, 它包括数据元素的存储和关系的存储在计算机中存储信息的最小单位是二进制的位 (bit), 可以用一个由若干位组合起来形成的一个位串存储一个数据元素因此可将位串看成是数据元素在计算机中的存储形式 (2) 数据的物理结构 (Physical Structure) 数据的物理结构, 又称为存储结构 (Storage Structure), 是指数据的逻辑结构在计算机存储空间的存放形式数据的物理结构是数据结构在计算机中的存储, 它包括数据元素的机内存储和关系的机内存储由于具体实现的方法有顺序链式索引散列等多种, 因此, 一种数据结构可存储成一种或多种存储结构数据元素的机内存储方法 : 用二进制位的位串存储数据元素通常称这种位串为节点

12 6 数据结构 (C 语言版 ) (node) 当数据元素由若干个数据项组成时, 位串中与各数据项对应的子位串称为数据域 (data field) 因此, 节点是数据元素的机内存储关系的机内存储方法 : 数据元素之间的关系的机内存储可以分为顺序存储和非顺序存储, 这样就可以得到两种不同的存储结构, 即顺序存储结构和链式存储结构顺序存储借助元素在存储器中的相对位置来存储数据元素之间的逻辑关系链式存储借助指示元素存储位置的指针 (pointer) 来存储数据元素之间的逻辑关系 1 顺序存储结构 (Sequence Storage Structure) 顺序存储结构通过数据元素在计算机存储器中的相对位置来存储数据元素的逻辑关系, 一般把逻辑上相邻的数据元素存储在物理位置相邻的存储单元中, 它是一种最基本的存储方法, 一般采用数组来实现 2 链式存储结构 (Linked Storage Structure) 链式存储结构对逻辑上相邻的两个数据元素不要求其存储位置必须相邻, 元素间的逻辑关系通过指针来存储, 一般采用链表来实现链式存储结构中的数据元素称为节点 (node), 在节点中附设地址域 (Address Domain) 来存储与该节点相邻的节点的地址, 从而实现节点间的逻辑关系图 1.5 给出了图 1.4 中数据结构 DS 1 的不同存储方式地址数据元素地址数据元素 (a) 顺序存储结构 (b) 链式存储结构图 1.5 数据结构 DS 1 存储结构示意图 (3) 数据的运算算法的设计取决于数据的逻辑结构, 而算法的实现依赖于数据采用的存储结构数据的存储结构实质上是它的逻辑结构在计算机存储器中的实现, 为了全面地反映一个数据的逻辑结构, 它在存储器中的映象包括两方面的内容, 即数据元素之间的信息和数据元素之间的关系不同的数据结构有其相应的若干运算数据的运算是在数据的逻辑结构上定义的操作算法, 如检索插入删除更新和排序等数据的运算是数据结构的一个重要方面, 讨论任何一种数据结构时都离不开对该结构上的数据运算及其实现算法的探讨 1.3 数据类型数据类型概述数据类型 (Data Type) 是高级程序设计语言中的概念, 是数据的取值范围和对数据进行

13 第 1 章绪论 7 操作的总和数据类型规定了程序中对象的特性程序中的每个变量常量或表达式的结果都应该属于某种确定的数据类型一方面, 在程序设计语言中, 每一个数据都属于某种数据类型类型显式或隐式地规定了数据的取值范围存储方式以及允许进行的运算数据类型是在程序设计中已经实现了的数据结构另一方面, 在程序设计过程中, 当需要引入某种新的数据结构时, 总是借助编程语言所提供的数据类型来描述数据的存储结构在客观世界中, 任何数据元素都应该有自身的取值范围和所允许进行的运算操作数据类型就是一个值的集合和定义在这个值集上的一组操作的总称例如,C 语言中的基本整数类型 (signed int), 它的值集是 ~32767, 在这个值集上能进行的操作有加减乘除和取余数等, 而在实数类型 (float) 上就不能进行取余数操作按值的不同特性, 数据类型又可分为不可分解的原子类型及可分解的结构类型比如,C 语言中的整型实型字符型就属于原子类型 ; 而数组结构体和共用体类型就属于结构类型, 由其他类型构造得到抽象数据类型 1. 抽象的数据类型抽象的数据类型 (Abstract Data Type,ADT) 是指基于一类逻辑关系的数据类型以及定义在这个类型上的一组操作在软件设计中, 抽象数据类型通常包含元素关系和操作三部分所以, 一般而言, 抽象数据类型可用以下三元组表示 : ADT_Type = (D,R,P) 其中,D 是数据元素有限集, 即数据对象,R 是 D 上的关系集,P 是对 D 的基本操作集 2. 抽象数据类型定义的一般形式 ADT 抽象数据类型名 { 数据对象 :< 数据对象的定义 > 数据关系 :< 数据关系的定义 > 基本操作 :< 基本操作的定义 > }ADT 抽象数据类型名例如, 线性表这样的抽象数据类型, 其数学模型是数据元素的集合, 该集合内的元素有这样的关系 : 除第一个和最后一个外, 每个元素有唯一的前趋和唯一的后继可以有这样的一些操作 : 插入一个元素删除一个元素例如, 线性表的抽象数据类型就可以定义为 : ADT list { 数据对象 : 任意数据元素的集合数据关系 : 除第一个和最后一个外, 每个元素有唯一的直接前驱和唯一的直接后继基本操作 :

14 8 数据结构 (C 语言版 ) ListInsert(&L,i,e) /* 元素的插入 */ ListDelete(&L,i,e) /* 元素的删除 */ }ADT list 3. 本书在用 C 语言描述时的约定 (1) C 语言的数组元素的下标从 0 开始, 为此, 在表示数据结构时, 数据元素的序号也从 0 开始 (2) 数据元素的类型约定为 ElemType 具体的类型可以由用户在使用时定义: typedef int ElemType /* 定义所用数据类型为 int*/ (3) 数据存储结构用类型定义 (typedef) 描述, 例如 : typedef struct{ ElemType *elem; int length; int listsize; }SqList; /* 定义名为 SqList 的线性表采用顺序存储结构的类型定义 */ (4) 算法以函数形式描述 : 类型标识符函数名 ( 形参表 ) /* 算法说明 */ { 语句 } 通过以上定义可以看出, 抽象数据类型只是数学的抽象, 在 ADT 的定义中根本没有涉及如何实现操作的集合对于每个 ADT 并不存在什么法则来说明必须要有哪些操作, 这只是一个设计决策 4. 抽象数据类型可以细分为 3 种类型 (1) 原子类型 : 其值是不可分的 (2) 固定聚合类型 : 其值由确定数目的成分按某种结构组成 (3) 可变聚合类型 : 其值由不确定数目的成分构成一个抽象数据类型的软件模块通常包含定义存储和实现这 3 个部分 1.4 算法和算法复杂度解决实际问题需要找出解决问题的方法用计算机解决实际问题, 就要先给出解决问题的算法, 再依据算法编写程序完成要求算法 (Algorithm) 是指在有限的时间范围内, 为解决某一问题而采取的方法和步骤的准确完整的描述, 它是一个有穷的规则序列, 这些规则决定了解决某一特定问题的一系列运算算法是程序设计的精髓, 算法的设计取决于数

15 第 1 章绪论 9 据的逻辑结构, 算法的实现取决于数据的物理结构算法的重要性 1. 算法的五个特征 (1) 有穷性一个算法必须总是 ( 对任何合法的输入值 ) 在执行有穷步之后结束, 且每一步都可在有穷的时间内完成这也是算法与程序的最主要区别, 程序可以无限地循环下去, 如操作系统的监控程序在机器启动后就一直监测着操作者的鼠标动作和输入的命令 (2) 确定性算法中的每一条指令都必须有明确的含义, 不应使读者产生二义性并且在任何条件下, 算法只有唯一的一条执行路径, 即对于相同的输入只能得到相同的输出 (3) 可行性一个算法是可以被执行的, 即算法中的每个操作都可以通过已经实现的基本运算执行有限次来完成 (4) 有输入根据实际问题的需要, 一个算法在执行时可能要接收外部数据, 也可能无须外部输入所以一个算法应有零个或多个输入, 这取决于算法本身要实现的功能 (5) 有输出一个算法在执行完毕后, 一定要有一个或多个结果或结论这就要求算法一定要有输出, 这些输出是同输入有着某些联系的量通常, 解决同一个问题, 不同的人有不同的想法, 即使是同一个人, 在不同的时间里可能对同一个问题的理解也不完全相同算法是依据个人的理解和想法人为设计出来的求解问题的步骤, 不同的人或同一个人在不同的时间里设计出来的算法也不尽相同, 那么哪种算法设计得好呢? 如何评价一个算法的好与坏呢? 2. 算法效率的度量标准通常, 在算法设计时应该考虑从以下几个方面来度量算法的效率 : (1) 正确性正确性 (Correctness), 满足预先规定的功能和性能的要求, 这是算法设计最基本的要求, 算法应严格地按照特定的规格说明进行设计, 要能够解决给定的问题但是, 正确一词的含义在通常的用法中有很大的区别, 大体上可分为以下 4 个层次 : 1 依据算法所编写的程序中不含语法错误 ; 2 程序对于几组输入数据能够得到满足规格要求说明的结果 ; 3 程序对于经过精心挑选较为苛刻的几组输入数据也能够得到令人满意的结果 ; 4 程序对于所有符合要求的输入数据都能得到正确的输出

16 10 数据结构 (C 语言版 ) 对于大型软件需要进行专业测试, 一般情况下, 通常以第 3 个要求作为衡量算法正确性的标准 (2) 可读性可读性 (Readability) 是指一个算法应当思路清晰层次分明简单明了易读易懂设计算法的主要目的是解决实际问题, 在设计实现一个项目时, 往往不是一个人独立完成的为了达到可读性的要求, 在设计算法时, 一般要使用有一定意义的标识符来命名变量函数等, 以便于见名知意其次, 可以在算法的开头或指令的后面加注释来解释算法和指令的功能 (3) 健壮性健壮性 (Robustness) 是指一个算法应该具有很强的容错能力, 当输入不合法的数据时, 算法应当能做适当的处理, 使得不至于引起严重的后果当输入不合法的数据时, 算法能做出相应的响应或进行适当的处理, 避免带着非法数据执行, 导致莫名其妙的结果 (4) 高效率运行时间 (Running Time) 是指算法在计算机上运行所花费的时间, 它等于算法中每条语句执行时间的总和一般来说, 执行时间越短, 性能越好依据算法编写的程序运行速度较快 (5) 低存储占用空间 (Storage Space) 是指算法在计算机上存储所占用的存储空间, 包括存储算法本身所占用的存储空间算法的输入及输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间依据算法编写的程序在运行时所需内存空间较小对于一个系统设计人员来说, 前 3 项很容易实现在使用软件时, 人们更加注重于软件的运行速度, 而后两项恰恰是影响速度的主要因素时间复杂度 1. 时间复杂度的定义一个程序的运行时间是指程序从开始到结束所需要的时间通常, 用 n 作为表示问题规模的量我们把规模为 n 的算法的执行时间, 称为时间复杂度 (Time Complexity), 记为 T(n) 通常把算法中基本操作重复执行的次数 ( 频度 ) 作为算法的时间复杂度 :T(n)=f(n) 渐进时间复杂度, 即当 n 逐渐增大时的极限情况一般把这种算法的渐进复杂度简称为时间复杂度为了便于分析, 时间复杂度常用数量级的形式来表示, 即 T(n)=O(f(n)) 其中大写字母为 Order( 数量级 ) 的第一个字母,f(n) 为函数形式, 如 T(n)=O(n 2 ) 一般用数量级的形式表示 T(n), 当 T(n) 为多项式时, 可只取其最高次幂, 且其系数也可省略算法的执行时间需通过依据该算法所编写的程序在计算机上运行时所消耗的时间来度量

17 第 1 章绪论度量一个程序执行时间的两种方法 (1) 事后统计法这种统计方法依据算法所编写的程序在计算机上运行时所消耗的时间但是, 同一个程序在不同类型的机器上运行所需的时间不一定相同, 所以这种统计是片面的 (2) 事先估计法根据每条指令的执行时间来估算依据算法编写的程序在计算机上运行时所消耗的时间但是, 因为每种类型机器的指令集不同, 执行的时间也不尽相同, 所以这种方法也离不开具体的机器软硬件环境和设备 3. 时间复杂度的计算方法显然, 以具体的时间单位作为计算机程序执行时的时间变量是不科学的所以在计算算法的执行时间时, 应该抛开具体机器软硬件环境和设备, 而使用指令的执行次数作为时间单位更合理一些在算法中, 可以使用基本语句的执行次数作为算法的时间度量单位, 可以认为, 一个特定算法时间性能只依赖于问题的规模 ( 通常用 n 来表示 ), 或者说它是关于问题规模 n 的一个函数 f(n), 当问题规模 n 趋近于无穷大时的时间量级就称为算法的渐进时间复杂性, 简称为时间复杂性或时间复杂度记作 T(n)=O(f(n)), 即 T(n) 是 f(n) 的同阶无穷大例 1.5 分析如下程序段的时间复杂度 s=0; for(i=1;i<=n;i++) 分析 : s=s+i; s=0; 执行 1 次 i=1; 执行 1 次 i<=n; 执行 n+1 次 s=s+i; 执行 n 次 i++; 执行 n 次总的执行次数为 3(n+1) 次, 因此, 该算法的时间复杂度为 T(n)=O(3(n+1))=O(n) 在分析算法的时间性能时, 常用最基本语句的执行次数来估算所谓最基本语句通常是指最深层循环体中的语句, 也是执行频率最快的语句它的执行次数反映了整个算法的基本时间性能如例 1.5 中的 s=s+i 和 i++ 均被执行了 n 次, 所以 T(n)=O(n) 4. 算法时间复杂度的时间量级实际上, 算法的时间量级有多种形式, 见表 1.2, 其对应的函数曲线见图 1.6

18 12 数据结构 (C 语言版 ) 表 1.2 算法的时间量级分类表名称时间复杂度 T(n) 说明常量阶 O(1) 与问题规模无关的算法线性阶 O(n) 与问题规模相关的单重循环平方阶 O(n 2 ) 与问题规模相关的二重循环立方阶 O(n 3 ) 与问题规模相关的三重循环指数阶 O(e n ) 较为复杂对数阶 O(log n 2 ) 折半查找算法复合阶如 O(nlog n 2 ) 堆排序算法其他不太确定过于复杂一个算法的时间复杂度可能存在最好情况和最坏情况, 通常要以算法的平均时间复杂度来进行算法分析但是算法的平均时间复杂度取决于各种数据出现的概率, 难以进行分析所以, 往往借助于最坏时间复杂度来进行算法分析与评价一般地, 对于足够大的 n, 常用的时间复杂度存在如下顺序 : O(1) < O(log n 2 ) < O(n) < O(n log n 2 ) < O(n 2 ) < O(n 3 ) < < O(2 n ) < O(3 n ) < < O(n!) T e n e n nn3 3 n 2 n2 n n log 2 n 2 0O 图 1.6 常见函数的增长率 n 空间复杂度空间是指执行算法所需要的存储空间, 算法所对应的程序在运行时所需的存储空间包括固定部分和可变部分固定部分所占空间与所处理的数据结构外数据的大小和数量无关, 或者称与该问题的实例的特征无关主要包括程序代码常量简单变量等所占的空间 ; 可变部分所占空间与该算法在某次执行中处理的特定数据的大小和规模有关例如,100 个数据元素的排序算法与 1000 个数据元素的排序算法所需的存储空间显然是不同的 1. 空间复杂度的定义与算法的时间复杂度类似, 空间复杂度也是关于问题规模 n 的一个函数, 当问题规模

19 第 1 章绪论 13 n 趋近于无穷大时的空间量级就称为算法的渐进空间复杂度, 简称空间复杂度 (Space Complexity) 可以将空间复杂度作为算法所需存储空间的度量, 记作 :S(n)=O(f(n)) 2. 空间复杂度的计算方法那么, 算法的空间需求有哪些呢? 大体上, 依据算法所编写的程序除了需要存储空间来寄存程序本身所用的指令常数变量和输入数据外, 也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间通常, 程序所占空间变化不大, 所以在此主要考虑算法的辅助空间需求例 1.6 分析下面程序的时间复杂度和空间复杂度 RevArray(int a[],int n) { int i,j,*b; b=(int *)malloc(sizeof(int)*n); for(i=0,j=n-1;i<n;i++,j--) b[j]=a[i]; for(i=j=0;i<n;i++,j++) a[i]=b[i]; free(b); } 算法空间复杂度的分析 : 因为基本语句就是循环内的赋值语句, 共执行了 2n 次, 所以 T(n)=2n=O(n) 而算法的辅助空间是一个与问题规模同量级的一维数组空间, 另外再加上两个控制变量 i 和 j, 共 n+2 个, 所以 S(n)=n+2=O(n) 1.5 本章实战练习 1. 什么是数据结构? 2. 在数据结构中, 从逻辑上可以把数据结构分为 ( ) A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C 线性结构和非线性结构 D 内部结构和外部结构 3. 设有数据逻辑结构为 : B=(K,R) K=(k 1,k 2,,k 9 ) R={<k 1,k 2 >,<k 1,k 8 >,<k 2,k 3 >,<k 2,k 4 >,<k 2,k 5 >,<k 3,k 9 >,<k 5,k 6 >,<k 8,k 9 >,<k 9,k 7 >} 试画出这个逻辑结构的图示 4. 什么是抽象数据类型? 5. 什么是算法?

20 14 数据结构 (C 语言版 ) 6. 算法应该具有什么特征? 7. 算法的衡量标准或依据是什么? 8. 分析下列程序片段的时间复杂度 (1) 程序片段 1: sum=0; for(i=0;i<n;i++) sum++; (2) 程序片段 2: sum=0; for(i=0;i<n;i++) for(j=0;j<n;j++) sum++; (3) 程序片段 3: sum=0; for(i=0;i<n;i++) for(j=0;j<n*n;j++) sum++; (4) 程序片段 4: sum=0; for(i=0;i<n;i++) for(j=0;j<i;j++) sum++; (5) 程序片段 5: sum=0; for(i=0;i<n;i++) for(j=0;j<i;j++) for(k=0;k<j;k++) sum++; 实战练习参考答案 1. 数据结构是指同一数据元素集合中各数据元素之间存在的关系 2. C 3. 该逻辑结构示意图如图 1.7 所示 4. 抽象数据类型 (Abstract Data Type,ADT) 是指一个数学模型以及定义在此数学模型上的一组操作, 抽象数据类型可以使人们更容易描述现实世界 5. 算法是解题的步骤, 是指令的有限序列 6. 一个算法应该具有 5 个特征 : 有穷性确定性可行性有输入有输出

21 第 1 章绪论 15 k1 k2 k3 k8 k9 图 1.7 逻辑结构图 7. 算法是通过时间复杂度和空间复杂度进行衡量的其中, 算法的时间复杂度是指运行算法时所需要消耗的时间算法的空间复杂度是指算法在计算机内执行时所需存储空间的度量 8. (1) O(n) (2) 是嵌套循环, 其时间复杂度为 O(n 2 ) (3) 关键语句 sum++ 执行次数为 N*N*N, 因此, 时间复杂度为 O(n 3 ) (4) 关键语句 sum++ 执行次数为 N=N(N+1)/2, 因此, 时间复杂度为 O(n 2 ) (5) O(n 3 ) 1.6 本章小结数据结构是计算机存储组织数据的方式数据结构是指相互之间存在一种或多种特定关系的数据元素的集合一个数据结构是由数据元素依据某种逻辑关系组织起来的对数据元素间逻辑关系的描述称为数据的逻辑结构 ; 数据必须在计算机内存储, 数据的存储结构是数据结构的实现形式, 是其在计算机内的存储 ; 此外, 讨论一个数据结构必须同时讨论在该类数据结构上执行的运算才有意义一个逻辑数据结构可以有多种存储结构, 且各种存储结构会影响数据处理的效率通常情况下, 精心选择的数据结构可以带来更高的运行效率或者存储效率 1. 数据结构指的是数据之间的相互关系, 即数据的组织形式 2. 数据元素是数据的基本单位在不同的条件下, 数据元素又可称元素节点顶点记录等 3. 数据对象是性质相同的数据元素的集合, 是数据的一个子集 4. 数据结构的 4 种基本结构是集合结构线性结构树形结构图状结构 5. 数据结构的形式定义为 Data_Structure=(D,R) 其中,D 是数据元素的有限集,R 是 D 上关系的有限集 6. 抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作抽象数据类型可以使我们更容易描述现实世界

22 16 数据结构 (C 语言版 ) 7. 算法是解题的步骤, 是指令的有限序列 8. 一个算法应该具有 5 个特征 : 有穷性确定性可行性有输入有输出 9. 算法通过时间复杂度和空间复杂度进行度量 10. 算法的时间复杂度是指运行算法时所需要消耗的时间 11. 算法的空间复杂度是指算法在计算机内执行时所需存储空间的度量 1.7 习题 1 一选择题 1. 算法分析的目的是 ( ) A 找出数据结构的合理性 B 研究算法中的输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易懂性和文档性 2. 数据结构中, 与所使用的计算机无关的是数据的 ( ) 结构 A 存储 B 物理 C 逻辑 D 物理和存储 3. 对一个算法的评价, 不包括如下 ( ) 方面的内容 A 健壮性和可读性 B 并行性 C 正确性 D 时空复杂度 4. 算法分析的两个主要方面是 ( ) A 空间复杂性和时间复杂性 B 正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性 5. 算法指的是 ( ) A 计算机程序 B 解决问题的计算方法 C 排序算法 D 解决问题的有限运算序列 6. 线性结构表示数据元素之间存在一种 ( ) 关系 A 一对多 B 多对多 C 多对一 D 一对一 7. 某程序的时间复杂度为 (3n+nlog n 2 +n 2 +8), 其数量级表示为 ( ) A O(n) B O(nlog n 2 ) C O(n 2 ) D O(log n 2 ) 8. 计算机算法指的是 ( ) A 计算方法 B 排序方法 C 解决问题的有限运算序列 D 调度方法 9. 计算机算法必须具备输入输出和 ( ) 等 5 个特性 A 可行性可移植性和可扩充性 B 可行性确定性和有穷性 C 确定性有穷性和稳定性 D 易读性稳定性和安全性 10. 以下属于逻辑结构的是 ( ) A 顺序表 B 哈希表 C 有序表 D 单链表

23 第 1 章绪论 17 二填空题 1. 数据结构按逻辑结构可分为两大类, 它们分别是和 2. 数据的物理结构主要包括和两种情况 3. 数据结构是指数据及其相互之间的当节点之间存在 M 对 N(M:N) 的关系时, 称这种结构为 4. 数据的逻辑结构被分为线性结构树形结构和 4 种 5. 线性结构中元素之间存在关系, 树形结构中元素之间存在关系 6. 数据结构的形式定义为 (D,R), 其中 D 是的有限集合,R 是 D 上的有限集合 7. 在图状结构中, 每个节点的前驱节点数和节点数可以 8. 抽象数据类型包括和两个部分 9. 在非数值计算的程序设计问题中, 数据结构是一门研究计算机的及相互之间的和运算等的学科 10. 在线性结构中, 第一个节点前驱节点, 其余每个节点有且只有 1 个前驱节点 ; 最后一个节点后继节点, 其余每个节点有且只有 1 个后继节点 11. 数据的运算最常用的有 5 种, 它们分别是插入修改和排序 12. 数据结构包括数据的数据的和数据的运算这三个方面的内容 13. 在树形结构中, 根节点没有节点, 其余每个节点有且只有个前驱节点 14. 数据的存储结构可用 4 种基本的存储方法表示, 它们分别是链式和散列三判断题 1. 算法的优劣与算法描述语言无关, 但与所用计算机有关 ( ) 2. 数据的物理结构是指数据在计算机内的实际存储形式 ( ) 3. 数据元素是数据的最小单位 ( ) 4. 数据的逻辑结构是指数据的各数据项之间的逻辑关系 ( ) 四简答题 1. 分析下面程序段的时间复杂度 x=0; for(i=1; i<n; i++) for(j=1; j<=n-i; j++) x++;

24 18 数据结构 (C 语言版 ) 2. 分析下面程序段的时间复杂度 i=1; while(i<=n) i=i*3; 3. 分析下面程序段的时间复杂度 s=0; for(i=0; i<n; i++) for(j=0; j<n; j++) s+=b[i][j]; sum=s; 4. 分析下面程序段的时间复杂度 for(i=0;i<n;i++ for(j=0;j<m;j++) a[i][j]=0;)

<4D F736F F D B8BDBCFE4220D7A8D2B5BBF9B4A1D3EBBACBD0C4BFCEB3CCC3E8CAF62E646F6378>

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