数据结构与算法（C 语言版）

《数据结构与算法（C 语言版）》由会员分享，可在线阅读，更多相关《数据结构与算法（C 语言版）（813页珍藏版）》请在金锄头文库上搜索。

1、数据结构与算法 （C+语言版）第1章 绪论教科书介绍 出版社：电子工业出版社 著者：肖南峰 教授赵洁 讲师等 ISBN： 978-7-121-08301-3主要著者介绍 肖南峰博士，男，1962年11月生，华南理工大学计算机科学与工程学 院教授，博士生导师。 1982年7月毕业于华中工学院（现为华中科技 大学）自动控制与计算机工程系，获工学学 士学位；1989年1月毕业于东北工学院（现为 东北大学），获工学硕士学位；2001年6月毕业于日本横浜国立大学，获工学博士学位。 2001年9月至2002年9月在澳大利亚Deakin大学从事科学研究。主要著者介绍（续）他作为主持人先后完成了2项国家自然科

2、学基金 项目、2项广东省自然科学基金重点项目，1项 教育部留学回国人员科研启动基金项目，以及 由广东省教育厅和华南理工大学等资助的20多 项教学与科研课题，在国内外发表学术论文120 多篇，其中被三大索引收录近50篇，出版专著 和教材5部，申请或获得发明及实用新型专利5 项，软件版权10项。课程内容第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 串 第五章 多维数组和广义表 第六章 树和二叉树 第七章 图 第八章 查找 第九章 内部排序 第十章 文件组织与外排序 第十一章 贪婪算法第十二章 分而治之算法 第十三章 动态规划 第十四章 回溯第一章 绪论背景：从世界上第一台计算机诞生至今，

3、已有60多年的历 史。在这期间，计算机的发展和应用已经渗透到了人类社 会的各个领域，计算机加工和处理的对象也从纯粹的数值 发展到了字符、图像、声音等各种具有一定结构的数据。 为了更好地设计程序，以提高计算机在解决复杂问题时的 处理效率，研究数据的特性和数据之间存在的关系至关重 要。“数据结构”作为计算机科学与技术领域中的一门专业 基础课，它专门研究数据的特性和数据之间存在的关系， 以及如何在计算机中有效地存取数据和处理数据。因此，“ 数据结构”是设计和实现编译程序、操作系统、数据库系统 和大型应用程序的重要基础，它也是介于数学、计算机硬 件和计算机软件之间的一门核心课程，并将随着人类社会 的各

4、个领域中计算问题的不断深入研究而继续发展。什么是数据结构基本概念（1）数据：信息的载体，是客观事物的符号表示。数据能 够被计算机识别、存取和处理，数据也是计算机程序加工 和处理的“原料”。例如实数、字符串、图像和声音等。 （2）数据项：具有独立的含义的最小标识单位。例如，字 段、域、属性等。 （3）数据元素：数据的基本单位。一个数据元素可由若干 个数据项组成。什么是数据结构（4）数据对象：性质相同的数据元素的集合，是数据的一 个子集。例如，26个英文字母构成的字符集合，一个学校 全体学生或教师构成的学生集合或教师集合等。 （5）数据结构：相互之间存在一种或多种特定关系的数据 元素的集合，即数据

5、的组织形式。数据结构的形式化定义 通常用一个二元组Data_Structure=(D, R)来表示，式中，D是 数据元素的有限集（也即数据对象），R是D上关系的有限 集。什么是数据结构数据结构的内涵数据结构一般包含数据的逻辑结构和存储结构及数据运算 。 数据的逻辑结构:数据的逻辑结构是指数据元素以及它们相互之间的逻辑关 系，数据的逻辑结构与数据的存储无关。根据数据元素之 间关系的不同特性，通常有4类逻辑结构： 集合，集合的 逻辑结构中所有数据元素都属于同一个集合，所有数据元 素杂乱无章地聚集在一起，各个数据元素之间无任何联系 ； 线性结构，逻辑结构中的数据元素之间存在着一个对 一个的关系，各个

6、数据元素之间通常有严格的先后次序关 系； 树形结构，逻辑结构中的数据元素之间存在着一个 对多个的关系，各个数据元素之间通常有严格的层次关系 ； 图状结构，逻辑结构中的数据元素之间存在着多个对 多个的关系，各个数据元素之间均可能存在相互联系。什么是数据结构根据数据元素（结点）之间的前后相邻关系，数据的逻辑 结构还可分为线性结构和非线性结构两大类： 线性结构 的逻辑特征是，若结构是非空集，则有且仅有一个开始结 点和一个终端结点，并所有结点都最多只有一个直接前驱 结点和一个直接后继结点。线性表是一个典型的线性结构 ，栈、队列和串等都是线性结构； 非线性结构的逻辑特 征是，一个结点可能有多个直接前驱和

7、直接后继。树和图 都是非线性结构。例1-1 怎样描述数据的逻辑结构对数据元素之间关系的描述是数据的逻辑结构，它可形式 地用一个二元组表示为K=(D, R)，式中，D是由有限个结点 所构成的集合，R是由有限个关系所构成的集合。有时为了 直观起见，也用以图示法来表示数据的逻辑结构。逻辑结 构与使用的计算机无关。例如，一批数据的逻辑结构K=(D, R)，式中，D=d1, d2, , d9，R=,，则该批数据 的逻辑结构如上图所示。对于R中包含有多种关系的情况， 也可用类似的方法描述。 什么是数据结构数据的存储结构 数据的存储结构（物理结构）是指数据在计算机中的存储 表示，它包括数据元素的表示和关系的

8、表示。数据的存储 结构有以下4种基本存储方法。 顺序存储。该存储方法把逻辑上相邻的结点存储在物理 位置上相邻的存储单元中，结点间的逻辑关系由存储单元 的邻接关系来体现。 链接存储。该方法不要求逻辑上相邻的结点在物理位置 上也相邻，结点之间的逻辑关系由附加的指针字段表示。 索引存储。该方法通常在存储结点信息的同时，还要建 立附加的索引表。 散列存储。该方法根据结点的关键字直接计算出该结点 的存储地址。什么是数据结构数据的运算 数据的运算是对数据施加的操作。数据的运算定义在数据 的逻辑结构上，每种逻辑结构都有一个运算的集合。在数 据结构中，运算不仅仅是加、减、乘、除等运算，大多数 的运算都涉及算法

9、的实现问题，算法的实现与数据的存储 结构是密切相关的。什么是数据结构数据类型和抽象数据类型 数据类型是一个值的集合和定义在这个值的集合上的一组 操作的总称，通常它可看作是高级程序设计语言中已经实 现的数据结构。 按“值”的不同特性，在高级程序语言中可分为： 原子类型，其值不可分解。 结构类型，其值是由若干个成分按某种结构组成的，故 可分解，其成分可以是非结构的，也可以是结构的。什么是数据结构抽象数据类型（abstract data type，ADT）是指一个数学模 型以及定义在该模型上的一组操作。抽象数据类型的定义 仅取决于它的一组逻辑特性，而与其在计算机内部如何表 示和实现无关，也即，不论其

10、内部结构如何变化，只要它 的数学特性不变，都不会影响其外部的使用。抽象数据类 型可表示为一个三元组（D, R, P），式中，D是数据对象， R是D上的关系集，P是对D的基本操作集。本书采用以下格 式定义抽象数据类型：ADT抽象数据类型名 数据集合：数据关系：数据操作： ADT抽象数据类型名什么是数据结构其中，数据对象和数据关系的定义用伪码描述，基本操作 的定义格式为：数据操作名(参数表)输入：输出：例1-2 抽象数据类型的与数据结构的区别ADT是高级程序设计语言中数据类型概念的推广，它是一 个数学模型和定义在该模型上操作集合的总称。ADT的实 现方法是，将ADT转换成现有高级程序设计语言的说明

11、语 句，加上对应于该ADT中每个操作的过程或函数，也即， 用现有高级程序设计语言能够支持的适当数据结构来表示 ADT中的数学模型，并用一组过程或函数来实现定义在该 模型上的各个操作。数据结构则是利用该语言的基本数据 类型和复合数据的构造机制来构成的。例如，数组和记录 就是C+语言中两种主要的复合数据的构造机制。根据ADT 定义，如果在相同的数学模型上定义两个不同的操作集， 则认为它们代表两个不同的抽象数据类型。故相同的数学 模型以及在其上所定义的操作有可能在不同的ADT中出现 。算法和算法分析算法（algorithm）定义：为了解决某一类问题而设计的一 个有限长的操作序列。一个算法须满足以下5

12、个重要特性。 有穷性。算法对于任意合法的输入值，在执行有限步之 后一定能结束。 确定性。算法中的每一个操作必须有确切的含义，无二 义性，并在任何条件下，算法都只有一条执行路径。 可行性。算法中的所有操作都可通过已经实现的基本运 算有限次地实现。 输入。算法具有零个或多个输入，这些输入为一组特定 的数据对象集合。 输出。算法具有一个或多个输出，它是一组与“输入”有 确定关系的量值。算法和算法分析算法设计的要求 （1）正确性（correctness）算法的执行结果应当满足预先规定的4个要求：程序不含 语法错误； 程序对于几组输入数据能够得出满足规格说 明要求的结果；程序对于精心选择的典型、苛刻且带

13、有 刁难性的几组输入数据能得出满足规格说明要求的结果； 程序对于一切合法的输入数据都能产生满足规格说明要 求的结果。 （2）可读性（readability）算法应有助于人们阅读、理解和调试，晦涩难懂的算法易 于隐藏较多错误，难以调试和修改。算法和算法分析（3）健壮性（robustness）当输入不合法的数据时，算法能够做出适当的反应或处理 ，不至于产生莫名其妙的结果。同时，处理出错的方法应 该是返回一个表示错误或错误性质的值，并终止程序的执 行，以便在更高的抽象层次上进行处理。 （4）时空效率（efficiency）要求算法执行的时间应该尽可能短、算法执行过程中占用 的存储空间应该尽可能少。时

14、空要求与求解问题的规模有 关，两者通常相互矛盾，因此，应在它们之间有所平衡。算法和算法分析算法分析算法分析的两个主要方面是分析算法的时间复杂度和空间 复杂度，主要考察算法的时间效率和空间效率，以便比较 和改进算法。通常，在算法的运算空间较为充裕的情况下 ，更多地关注算法的时间复杂度。算法和算法分析时间复杂度 算法执行的时间可通过依据该算法编制的程序在计算机上 从开始运行到结束运行所消耗的时间来度量，也就是算法 中每条语句的执行时间之和。 一般而言，算法中基本操作的频度是问题规模n（如算法所 处理的矩阵的阶数，线性表的长度）的某个函数f(n)，算法 的时间量度记作T(n)=O(f(n)，它表示随

15、问题规模n的增大， 算法的执行时间增长率与f(n)的增长率相同，称为算法的渐 进时间复杂度（asymptotic time complexity），简称时间复 杂度。同时，要全面地分析算法，需要分别考虑算法在最 坏情况、最好情况以及平均情况下的时间代价。对于最坏 情况下的时间复杂度，主要采用大写数学符号O表示法来描 述。一般定义为：当且仅当存在正整数c和n0，使得T(n)c f(n)对所有的nn0成立，则称该算法的渐进时间复杂度为 T(n)=O(f(n)。例1-3 如何进行算法的时间复杂度分析首先介绍计算增长率的加法规则和乘法规则。设T1(n)和 T2(n)分别是程序段P1和P2的运行时间，且

16、T1(n)=O(f(n)， T2(n)=O(g(n)，即T1(n)是f(n)的函数，T2(n)是g(n)的函数（O 函数定义见后），则执行P1之后紧接着执行P2的运行时间为 ：T1(n)+T2(n)=O(maxf(n)，g(n)，称为加法规则； T1(n)T2(n)=Of(n)g(n)，称为乘积规则。一般来说，分析 程序的时间复杂度是，先求出各模块（各语句）的运行时 间，再求整个程序的运行时间，它可表示成唯一参数 输入数据的规模n的函数。具体可遵循以下规则。 每个赋值或读/写语句的运行时间通常是O(1)。如果赋值 语句的右部为函数调用，则要考虑计算函数值所消耗的时 间。 序列语句的运行时间由加法规则确定。例1-3 如何进行算法的时间复杂度分析 语句if B then S1 else S2的运行时间为条件B的测试时间（ 通