数据结构赵爽
数 据 结 构 赵爽
第1章绪论1.1 数据结构讨论的范畴1.2 与数据结构相关的基本概念1.3算法和算法的时间复杂度1.4算法的空间复杂度分析
第1章 绪论 1.1 数据结构讨论的范畴 1.2 与数据结构相关的基本概念 1.3 算法和算法的时间复杂度 1.4 算法的空间复杂度分析
1.1数据结构讨论的范畴瑞士的计算机专家在1976年出版了一本书，书名为《算法+数据结构=程序设计》，它说明了数据结构在程序设计中的作用。程序设计的实质即为计算机处理问题编制一组指令”，首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略，而数据结构即为问题的数学模型
1.1 数据结构讨论的范畴 瑞士的计算机专家在1976年出版了一本书，书名 为《算法+数据结构 = 程序设计》，它说明了数据结构 在程序设计中的作用。程序设计的实质即为计算机处 理问题编制一组"指令"，首先需要解决两个问题：即 算法和数据结构。算法即处理问题的策略，而数据结 构即为问题的数学模型
很多数值计算问题最后都可以转化为求解数学方程或数学方程组，而当计算机进入非数值计算领域特别是用在管理上的时候，计算机的操作对象之间的关系就无法用数学方程加以描述了。例一、煤气管道的铺设问题。如需为城市的各小区之间铺设煤气管道，对n个小区只需铺设n-1条管线，由于地理环境不同等因素使各条管线所需投资不同，如何使投资成本最低？例二、教学计划编排问题。一个教学计划包含许多课程，在这些课程之间，有些课程需要按规定的先后次序进行，有些课程则没有次序要求。那么如何合理的安排教学计划？
例一、煤气管道的铺设问题。如需为城市的各小区 之间铺设煤气管道，对 n 个小区只需铺设 n-1 条管线， 由于地理环境不同等因素使各条管线所需投资不同， 如何使投资成本最低？ 例二、教学计划编排问题。一个教学计划包含许多 课程，在这些课程之间，有些课程需要按规定的先后 次序进行，有些课程则没有次序要求。那么如何合理 的安排教学计划？ 很多数值计算问题最后都可以转化为求解数学方 程或数学方程组，而当计算机进入非数值计算领域， 特别是用在管理上的时候，计算机的操作对象之间的 关系就无法用数学方程加以描述了
简单地说，数据结构课程主要讨论现实世界中数据的各种逻辑结构、在计算机中的存储结构以及各种算法的设计问题
简单地说，数据结构课程主要讨论 现实世界中数据的各种逻辑结构、在计 算机中的存储结构以及各种算法的设计 问题
1.2与数据结构相关的基本概念1.数据和数据元素数据是所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等)的集合，它是计算机操作对象的总称。数据是个集合，如果用集合的表示方法来写的话，就是：数据=xx是计算机操作的对象它包括所有的数字和字符。图形和声音等信息最后也都可以转化为“字符“进行处理。而这些学符和数字是客观信息的一种描述
1.2 与数据结构相关的基本概念 1. 数据和数据元素 数据是所有能被输入到计算机中，且能被计算机处 理的符号(数字、字符等)的集合，它是计算机操作对象 的总称。 数据是个集合，如果用集合的表示方法来写的话，就 是：数据={x|x是计算机操作的对象} 它包括所有的数字和字符。图形和声音等信息最后也 都可以转化为"字符"进行处理。而这些字符和数字是客观 信息的一种描述
数据元素是数据（集合）中的一个"个体”，在计算机中通常作为一个整体进行考虑和处理，是数据结构中讨论的"基本单位"有两类数据元素：一类是不可分割的"原子型数据元素，如：整数"5"，字符"N"等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个“数据项”。数据项是数据结构中讨论的"最小单位
数据元素是数据(集合)中的一个"个体" ，在计算机 中通常作为一个整体进行考虑和处理，是数据结构中讨 论的"基本单位" 。 有两类数据元素： 一类是不可分割的"原子"型数据元素，如：整数 "5"，字符 "N" 等； 另一类是由多个款项构成的数据元素，其中每个款 项被称为一个“数据项” 。 数据项是数据结构中讨论的 "最小单位"
学号姓名性别年龄男王红1820030001男19张明20030002女吴宁1820030003如上表所示，描述一个学生信息的数据元素可由以上4个数据项组成
学号 姓名 性别 年龄 20030001 王红 男 18 20030002 张明 男 19 20030003 吴宁 女 18 如上表所示，描述一个学生信息的数据元素可由以 上4个数据项组成
数据结构课程在讨论一种类型的数据结构问题时，通常说的是抽象意义上的数据元素，是没有实际含义的。我们把没有实际含义的数据元素称作抽象数据元素
数据结构课程在讨论一种类型的数据结构 问题时，通常说的是抽象意义上的数据元素， 是没有实际含义的。我们把没有实际含义的数 据元素称作抽象数据元素
2数据结构若在特性相同的数据元素集合中的数据元素之间存在一种或多种特定的关系，则称该数据元素的集合为“数据结构”。换句话说，数据结构是带"结构"的数据元素的集合。“结构"即指数据元素之间存在的关系假设以三个4位的十进制数表示一个含12位十进制数的”长整数”，则可用如下描述的数学模型表示：它是一个含三个数据元素a1.a2.a3的集合，且在集合上存在下列次序关系：[ , )。例如，长整数"321465879345"可用a1=3214，a2=6587和a3=9345的集合表示，且三者之间的次序关系必须是，a1表示最高4位，a3表示最低的4位，a2则是中间4位
2 数据结构 若在特性相同的数据元素集合中的数据元素之间存 在一种或多种特定的关系，则称该数据元素的集合为“数 据结构” 。换句话说，数据结构是带"结构"的数据元素的 集合。 "结构"即指数据元素之间存在的关系。 假设以三个4位的十进制数表示一个含12位十进制数的" 长整数"，则可用如下描述的数学模型表示：它是一个含三个 数据元素{a1,a2,a3}的集合，且在集合上存在下列次序关系： {，}。 例如，长整数 "321465879345" 可用 a1=3214，a2=6587 和 a3=9345 的集合表示，且三者之间的次序关系必须是，a1 表示最高4位，a3 表示最低的4位，a2 则是中间4位