Microsoft Word - 1Z.doc

Size: px

Start display at page:

Download "Microsoft Word - 1Z.doc"

斛解
5 years ago
Views:

1 第 1 章绪论数据作为计算机加工处理的对象, 如何在计算机中表示和存储是计算机科学研究的主要内容之一, 更是计算机技术需要解决的关键问题之一数据是计算机化的信息, 是计算机处理的主要对象科学计算数据处理过程控制文件存储数据库技术等, 都是对数据进行加工处理的过程因此, 要设计出一个结构好效率高的程序, 必须研究数据的特性数据间的相互关系及其对应的存储表示方法, 并利用这些特性和关系设计相应的算法和程序 1.1 从问题到程序数据结构是计算机科学与技术专业的专业基础课, 也是十分重要的核心课程, 其主要研究内容是数据之间的逻辑关系和物理实现, 即探索有利的数据组织形式及存取方式计算机系统软件和应用软件的设计开发要用到各种类型的数据结构因此, 要想更好地运用计算机来解决实际问题, 仅仅依赖几种计算机程序设计语言是不够的, 还必须学习和掌握数据结构的有关知识在计算机发展的初期, 人们使用计算机的目的主要是处理数值计算问题使用计算机来解决一个具体问题时, 一般需要经过下列几个步骤 : 首先要从该具体问题中抽象出一个适当的数学模型, 然后设计或选择一个解此数学模型的算法, 再编写程序并进行调试测试, 最后运行程序并得到答案 ( 如图 1.1 所示 ) 例如, 求解梁架结构中应力数学模型的线性方程组, 该方程组可以使用迭代算法来求解图 1.1 计算机解决问题的一般过程由于当时所涉及的运算对象是简单的整型数据实型数据或布尔型数据, 所以程序设计者的主要精力集中于程序设计的技巧上, 而无须重视数据结构随着计算机应用领域的扩大和软 / 硬件的发展, 非数值计算问题显得越来越重要据统计, 当今处理非数值计算性问题占用了 90% 以上的机器时间这类问题涉及的处理对象不再是简单的数据类型, 其形式更加多样, 结构更为复杂, 数据元素之间的相互关系一般无法直接用数学方程式加以描述因此, 解决这类问题的关键不再是数学分析和计算方法, 而是设计出合适的数据结构, 以便有效地解决问题例 1.1 图书信息检索系统在现代图书馆中, 人们往往借助计算机图书检索系统来查找需要的图书信息 ; 或者直接通过图书馆信息系统进行图书借阅为此, 需要将图书信息分类编排, 建立合适的数据结构进行存储和管理, 按照某种算法编写相关程序, 实现计算机自动检索由此, 一个简单的图书信息检索系统包括一张按图书分类号和登录号顺序排列的图书信息表, 以及分别按作者出版社等顺序排列的各类索引表, 如图 1.2 所示由这三张 1

2 表构成的文件便是图书信息检索的数学模型, 计算机的主要操作便是按照用户的要求 ( 如给定作者 ) 通过不同的索引表对图书信息进行检索查询序号图书分类号登录号书名作者出版社 1 B 梁启超家书张品兴中国文联出版社 2 C 探寻语碎李泽厚上海文艺出版社 3 D 市政学张永桃高等教育出版社 4 G 传播学邵培仁高等教育出版社 5 H 英语阅读策略李宗宏兰州大学出版社 6 K 围棋人生聂卫平中国文联出版社 7 P 通向太空之路邹惠成科学出版社 8 TN 通信与网络技术概论刘云中国铁道出版社 9 TP 计算机软件技术基础王宇川科学出版社 10 TP 网络管理与应用张琳人民邮电出版社 11 Q 普通遗传学杨业华高等教育出版社 (a) 图书信息表姓名序号邵培仁 4 李泽厚 2 李宗宏 5 刘云 8 聂卫平 6 王宇川 9 杨业华 11 张琳 10 张品兴 1 张永桃 3 邹惠成 7 (b) 作者姓名索引表出版社序号高等教育出版社 3,4,11 科学出版社 7,9 兰州大学出版社 5 人民邮电出版社 10 上海文艺出版社 2 中国铁道出版社 8 中国文联出版社 1,6 (c) 出版社索引表图 1.2 图书信息检索系统中的数据结构诸如此类的还有电话自动查号系统学生信息查询系统仓库库存管理系统等在这类数学模型中, 计算机处理的对象之间通常存在着一种简单的线性关系, 这类数学模型是线性数据结构的例 1.2 人机对弈问题人机对弈是一个古老的人工智能问题, 其解题思想是将对弈的策略事先存入计算机, 策略包括对弈过程中所有可能的情况及响应的对策在决定对策时, 根据当前状态, 考虑局势发展的趋势做出最有利的选择因此, 计算机操作的对象 ( 数据元素 ) 是对弈过程中的每一步棋盘状态 ( 格局 ), 数据元素之间的关系由比赛规则决定通常, 这个关系不是线性的, 因为从一个格局可以派生出多个格局, 所以通常用树形结构来表示, 图 1.3 所示的是井字棋对弈树 2

C 7 数据库原理 C 2,C 9 C 8 编译原理 C 4 C 9 操作系统 C 2 (a) 计算机专业的课程设置 (b) 表示课程之间优先关系的有向图图 1.

3 图 1.3 井字棋对弈树例 1.3 教学计划编排问题一个教学计划包含许多课程, 在教学计划包含的许多课程之间, 有些课程必须按规定的先后次序进行学习, 有些则没有次序要求课程之间先修和后修的次序关系可用一个称做图的数据结构来表示, 如图 1.4 所示有向图中的每个顶点表示一门课程, 如果从顶点 v i 到 v j 之间存在有向边 <v i,v j >, 则表示课程 i 必须先于课程 j 进行学习课程编号课程名称先修课程 C 1 计算机导论无 C 2 数据结构 C 1,C 4 C 3 汇编语言 C 1 C 4 C 程序设计语言 C 1 C 5 计算机图形学 C 2,C 3,C 4 C 6 接口技术 C 3 C 7 数据库原理 C 2,C 9 C 8 编译原理 C 4 C 9 操作系统 C 2 (a) 计算机专业的课程设置 (b) 表示课程之间优先关系的有向图图 1.4 教学计划编排问题的数据结构由以上几个例子可见, 描述非数值计算问题的数学模型不再是数学方程, 而是诸如表树图之类的数据结构因此, 数据结构课程是研究非数值计算的程序设计问题中计算机处理对象及它们之间关系和操作的学科学习数据结构的目的是了解和掌握计算机处理对象的特性, 将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理同时, 通过算法训练来提高学生的思维能力, 通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高 1.2 有关概念和术语在系统地学习数据结构知识之前, 先对一些基本概念和术语赋予确切的定义 1. 数据数据 (Data) 是信息的载体, 它能够被计算机识别存储和处理数据是计算机程序加工的原料, 应用程序能处理各种各样的数据, 包括数值数据和非数值数据数值数据是一些 3

4 整数实数或复数 ; 非数值数据包括字符文字图形图像语音等 2. 数据元素数据元素 (Data Element) 是数据的基本单位, 在计算机程序中通常作为一个整体进行考虑和处理一个数据元素可由若干个数据项 (Data Item) 组成在不同的条件下, 数据元素又可称为元素结点顶点记录等例如, 学生信息检索系统中学生信息表中的一个记录教学计划编排问题中的一个顶点等, 都被称为一个数据元素 3. 数据项数据项 (Data Item) 指不可分割的具有独立意义的最小数据单位, 数据项有时也称为字段 (field) 或域例如, 学籍管理系统中学生信息表的每一个数据元素就是一个学生记录它包括学生的学号姓名性别籍贯出生年月成绩等数据项这些数据项可以分为两种 : 一种叫做初等项, 如学生的性别籍贯等, 这些数据项是在数据处理时不能再分割的最小单位 ; 另一种叫做组合项, 如学生的成绩, 它可以再划分为数学物理化学等更小的项通常, 在解决实际应用问题时把每个学生记录当做一个基本单位进行访问和处理 4. 数据结构数据结构 (Data Structure) 是指互相之间存在着一种或多种关系的数据元素的集合在任何问题中, 数据元素都不会是孤立的, 在它们之间存在着这样或那样的关系, 这种数据元素之间存在的关系称为数据的逻辑结构根据数据元素之间关系的不同特性, 通常有以下 4 类基本的逻辑结构 (1) 集合结构 : 在集合结构中, 数据元素之间的关系是属于同一个集合数据元素之间除了同属一个集合外, 不存在其他关系 (2) 线性结构 : 在该结构中, 数据元素除了同属于一个集合外, 数据元素之间还存在着一对一的顺序关系 (3) 树形结构 : 该结构的数据元素之间存在着一对多的层次关系 (4) 图状结构 : 该结构的数据元素之间存在着多对多的任意关系, 图状结构也称为网状结构上述 4 类基本结构的示意图如图 1.5 所示图类基本结构的示意图由于集合是数据元素之间极为松散的一种结构, 本书不专门讨论因此, 本书主要讨论线性结构 ( 表栈队串等 ) 和非线性结构 ( 树图或网 ) 从上面所介绍的数据结构的概念中可以知道, 一个数据结构有两个要素 : 一是数据元素, 二是数据元素之间的关系因此, 数据结构通常可以采用一个二元组来表示 : Data_Structure =(D,R) 4

5 其中,D 是数据元素集合,R 是 D 中元素之间关系的集合例 1.4 假设一个数据结构定义如下 : DS = (D,R) D = { a, b, c, d, e, f, g } R = { <a, b>,<a, c>,<a, d>,<c, e>,<c, f>,<d, g> } 则该数据结构的逻辑示意如图 1.6 所示, 显然是一个树形结构数据结构包括数据的逻辑结构和物理结构数据的逻辑结构可以看做从具体问题抽象出来的数学模型, 它与数据的存储无关数据的逻辑结构在计算机中的存储表示 ( 又称映像 ) 称为数据的物理结构 ( 或称存储结构 ), 它所研究的是数据结构在计算机中的实现方法, 包括数据结构中数据元素的存储表示及数据元素之间关系的表示图 1.6 例 1.4 的数据结构逻辑示意图在计算机中, 数据的存储方法包括顺序存储和链式存储 (1) 顺序存储方法通过数据元素在计算机中存储位置关系来表示元素间的逻辑关系, 通常把逻辑上相邻的元素存储在物理位置相邻的存储单元中顺序存储是一种最基本的存储表示方法, 通常借助程序设计语言中的数组来实现 (2) 链式存储方法对逻辑上相邻的元素不要求其物理位置相邻, 元素间的逻辑关系通过指针字段来表示, 链式存储结构通常借助程序设计语言中的指针来实现除了顺序存储方法和链式存储方法外, 有时为了查找方便还采用索引存储方法和散列表 (Hash) 存储方法讨论数据结构的目的就是在计算机中实现对数据的操作, 因此在讨论数据的组织结构时必然要考虑在该结构上进行的操作 ( 或称运算 ) 事实上, 数据结构是专门研究某一类数据的表示方法及其相关操作实现算法的一门学科 5. 数据类型数据类型 (Data Type) 是和数据结构密切相关的一个概念, 在高级程序设计语言中用以限制变量取值范围和可能进行的操作的总和称为数据类型因此, 所谓数据类型, 一是限定了数据的取值范围 ( 实际上与存储形式有关 ); 二是规定了数据能够进行的一组操作 ( 运算 ) 数据类型可分为两类 : 一类是非结构的原子类型, 原子类型的值是不可再分解的, 如 C 语言中的基本类型 ( 整型实型字符型及指针类型和空类型 ); 另一类是结构类型, 它的成分可以由多个结构类型组成, 并可以分解结构类型的成分可以是非结构的, 也可以是结构的例如, 数组的值由若干分量组成, 每个分量可以是整数等基本类型, 也可以是数组等结构类型 6. 抽象数据类型抽象数据类型 (Abstract Data Type,ADT) 是指一个数学模型及定义在该模型上的一组操作抽象数据类型的定义取决于它的一组逻辑特性, 而与其在计算机内部如何表示和实现无关即无论其内部结构如何变化, 只要它的数学特性不变, 就不影响其外部的使用抽象数据类型和数据类型实质上是一个概念例如, 各种计算机都拥有的整数类型就是一个抽象数据类型, 尽管它们在不同处理器上的实现方法可以不同, 但由于其定义的数学特 5

6 性相同, 在用户看来都是相同的因此, 抽象的意义在于数据类型的数学抽象特性抽象数据类型的定义可以由一种数据结构和定义在其上的一组操作组成, 而数据结构又包括数据元素及元素间的关系, 因此抽象数据类型一般可以由元素关系及操作三个要素来定义本书在讨论各种数据结构时, 针对其逻辑结构和具体的存储结构给出相应的数据类型, 并在确定的数据类型上通过各种算法实现各种操作 1.3 算法及算法分析算法与数据结构的关系非常紧密, 在算法设计时总是先要确定相应的数据结构, 而在讨论某一种数据结构时也必然会涉及相应的算法下面就从算法特性算法描述和算法分析三个方面对算法进行介绍算法特性算法 (Algorithm) 是对特定问题求解步骤的一种描述, 是指令的有限序列其中每一条指令表示一个或多个操作一个算法应该具有下列特性 (1) 有穷性 : 一个算法必须在有穷步之后结束, 即必须在有限时间内完成 (2) 确定性 : 算法的每一步必须有确切的定义, 无二义性, 且在任何条件下算法只有唯一一条执行路径, 即对于相同的输入只能得出相同的输出 (3) 可行性 : 算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现 (4) 输入 : 一个算法具有零个或多个输入, 这些输入取自特定的数据对象集合 (5) 输出 : 一个算法具有一个或多个输出, 这些输出同输入之间存在某种特定的关系算法的含义与程序十分相似, 但又有区别一个程序不一定满足有穷性例如, 对于操作系统, 只要整个系统不遭破坏, 它将永远不会停止, 即使没有作业需要处理, 它仍处于动态等待中因此, 操作系统不是一个算法另外, 程序中的指令必须是机器可执行的, 而算法中的指令则无此限制算法代表了对问题的求解方法, 而程序则是算法在计算机上的特定实现一个算法若用程序设计语言来描述, 就是一个程序算法与数据结构是相辅相成的解决某一类特定问题的算法可以选定不同的数据结构, 而且选择恰当与否直接影响算法的效率反之, 一种数据结构的优劣由各种算法的执行效果来体现在算法设计时通常需要考虑以下几个方面的要求 (1) 正确性 : 算法的执行结果应当满足预先规定的功能和性能要求正确性要求表明算法必须满足实际需求, 达到解决实际问题的目标 (2) 可读性 : 一个算法应当思路清晰层次分明简单明了易读易懂可读性要求表明算法主要是人与人之间交流解题思路和进行软件设计的工具, 因此可读性必须要强同时一个可读性强的算法, 其程序的可维护性可扩展性都要好得多, 因此, 许多时候人们往往在一定程度上牺牲效率来提高可读性 (3) 健壮性 : 当输入不合法数据时, 应能适当处理, 不至于引起严重后果健壮性要求表明算法要全面细致地考虑所有可能的边界情况, 并对这些边界条件做出完备的处理, 尽可能使算法没有意外的情况 6

7 (4) 高效性 : 有效使用存储空间和有较好的时间效率高效性主要是指时间效率, 即解决相同规模的问题时间尽可能短一般来说, 数据结构上的基本操作主要有以下几种 (1) 查找 : 寻找满足特定条件的数据元素所在的位置 (2) 读取 : 读出指定位置上数据元素的内容 (3) 插入 : 在指定位置上添加新的数据元素 (4) 删除 : 删去指定位置上对应的数据元素 (5) 更新 : 修改某个数据元素的值算法描述算法的描述方法很多, 根据描述方法的不同, 大致可将算法描述分为以下 4 种 (1) 自然语言算法描述 : 用人类自然语言 ( 如中文英文等 ) 来描述算法, 同时还可插入一些程序设计语言中的语句来描述, 这种方法也称为非形式算法描述其优点是不需要专门学习, 任何人都可以直接阅读和理解, 但直观性很差, 复杂的算法难写难读 (2) 框图算法描述 : 这是一种图示法, 可以采用方框图流程图 N-S 图等来描述算法, 这种描述方法在算法研究的早期曾流行过它的优点是直观易懂, 但用来描述比较复杂的算法就显得不够方便, 也不够清晰简洁 (3) 伪代码算法描述 : 如类 C 语言算法描述这种算法描述很像程序, 但它不能直接在计算机上编译运行这种方法很容易编写阅读算法, 而且格式统一, 结构清晰, 专业设计人员经常使用类 C 语言来描述算法 (4) 高级程序设计语言编写的程序或函数 : 这是直接用高级语言来描述算法, 它可在计算机上运行并获得结果, 使给定问题能在有限时间内被求解, 通常这种算法描述也称为程序例 1.5 求两个整数 m n(m n) 的最大公因子, 该算法的不同描述方法如下 (1) 非形式算法描述 ( 自然语言算法描述 ) 如下 1 [ 求余数 ] 以 n 除 m, 并令 r 为余数 (0 r<n); 2 [ 判断余数是否为零 ] 若 r = 0, 则结束算法,n 就是最大公因子 ; 3 [ 替换并返回步骤 1] 若 r 0, 则 m n,n r, 返回步骤 1 (2) 算法的框图描述如图 1.7 所示图 1.7 算法的框图描述 7

8 (3)C 语言函数描述如下 int max_common_factor(int m,int n) { int r; r=m%n ; while(r!=0) { m=n;n=r;r=m%n;} return n ; } 本书主要介绍算法的思路和实现过程, 且尽可能地给出算法对应的 C 语言函数或程序 ( 或类 C 语言算法描述 ), 方便读者阅读或上机运行, 以便更好地理解算法算法分析所谓好的算法, 除了满足上文提到的几个基本要求外, 还必须以较少的时间与空间代价来解决相同规模的问题因此, 一个算法的优劣, 可以从该算法在计算机上运行的时间和所占存储空间来衡量和评判算法分析就是预先分析算法在实际执行时的时空代价指标当一个算法被转换成程序并在计算机上执行时, 其运行所需要的时间一般取决于下列几个因素 (1) 硬件的速度即主机本身运行速度, 主要与 CPU 的主频和字长有关, 也与主机系统采用的技术有关, 如多机系统的运算速度一般比单机系统要快 (2) 实现算法的程序设计语言实现算法的语言的级别越高, 其执行效率相对就越低 (3) 编译程序所生成目标代码的质量代码优化较好的编译程序所生成的程序质量较高 (4) 算法所采用的策略采用不同设计思路与解题方法, 其时空代价是不同的, 一般情况下时间指标与空间指标常常是矛盾的两个方面 (5) 问题的规模例如, 求 100 以内的素数与求以内的素数的执行时间必然不同显然, 在各种因素都不能确定的情况下, 很难比较算法的执行时间也就是说, 用算法的绝对执行时间来衡量算法的效率是不合适的为此, 可以将上述各种与计算机相关的软硬件因素都确定下来, 仅对采用不同策略的算法, 分析其运行代价随问题规模大小变化的对应关系, 即运行代价仅依赖于问题的规模 ( 通常用正整数 n 表示 ), 或者说它是问题规模的函数这种函数被称为算法的时间复杂度和空间复杂度 1. 时间复杂度一个程序的时间复杂度 (Time Complexity) 是指该程序的运行时间与问题规模的对应关系一个算法是由控制结构和原操作 ( 所谓原操作是指从算法中选取对于所研究问题是基本运算的操作 ) 构成的, 其执行时间取决于两者的综合效果为了便于比较同一问题的不同的算法, 通常的做法是 : 从算法中选取一种对于所研究的问题来说是基本运算的原操作, 以该原操作重复执行的次数为算法的时间度量一般情况下, 算法中原操作重复执行的次数是该算法所处理问题的规模 n 的某个函数 T(n) 例 1.6 两个 n n 阶的矩阵相乘的程序中的主要语句及其重复次数如下原操作语句的执行频度 8

9 for ( i = 0;i < n;i + + ) for ( j = 0;j < n;j + + ) { s [ i ][ j ] = 0; n 2 for ( k = 0;k < n;k + + ) s [ i ][ j ] = s [ i ][ j ] + a [ i ][ k ] * b [ k ][ j ]; n 3 } 则该段程序的时间复杂度 T(n) = cn 3 + n 2, 其中 c 为常量, 表示算术运算时间是简单赋值运算时间的常数倍许多时候, 精确地计算 T(n) 是困难的, 人们引入渐进时间复杂度在数量上估计一个算法的执行时间, 也能够达到分析算法的目的定义 ( 大 Ο 记号 ): 如果存在两个正常数 c 和 n 0, 使得对所有的 n(n n 0 ), 有 : T(n) c*f (n) 则 T(n)=Ο( f (n)) 例如, 一个程序的实际执行时间为 T(n)=2.7n n , 则 T(n)=Ο(n 3 ) 使用大 Ο 记号表示的算法的时间复杂度称为算法的渐进时间复杂度 (Asymptotic Time Complexity) 通常用 Ο(1) 表示常数级时间复杂度, 表明这样的算法执行时间是恒定的, 不随问题规模的扩大而增长, 显然这是最理想的, 但往往难以实现此外, 常见的渐进时间复杂度还有 : (1)O(log 2 n), 对数级复杂度 ; (2)Ο(n), 线性复杂度 ; (3)Ο(n 2 ) 和 Ο(n 3 ), 分别为平方级和立方级复杂度 ; (4)Ο(2 n ), 指数级复杂度上述时间复杂度随问题规模 n 的扩大其增长速度是不同的, 其增长速度的快慢次序表示如下 : Ο(1)<Ο(log 2 n)<ο(n)<ο(nlog 2 n)<ο(n 2 )<Ο(n 3 )<Ο(2 n ) 2. 空间复杂度一个程序的空间复杂度 (Space Complexity) 是指程序运行从开始到结束所需的存储量与问题规模的对应关系, 记做 : S(n) = Ο( f (n)) 其中 n 为问题的规模 ( 或大小 ) 一个上机执行的程序除了需要存储空间来寄存本身所用指令常数变量和输入数据外, 还需要一些对数据进行操作的工作单元和存储为实现计算所需信息的辅助空间若输入数据所占空间只取决于问题本身和算法无关, 则只需分析除输入数据和程序之外的额外空间, 否则应同时考虑输入数据本身所需空间 ( 和输入数据的表示形式有关 ) 若额外空间相对于输入数据量来说是常数, 则称此算法为原地工作, 辅助空间为 Ο(1) 如果所占空间量依赖于特定的输入, 则除特别指明外, 均按最坏情况来分析算法执行时间的耗费和所占存储空间的耗费是相互矛盾的, 难以兼得即算法执行时间上的节省是以增加存储空间为代价的, 反之亦然不过, 一般而言, 常常以算法执行时间作 9

10 为算法优劣的主要衡量指标 1.4 关于数据结构的学习计算机发展始终遵循摩尔 (1965) 法则 : 芯片容量每 18 个月加倍, 新摩尔定理 : 计算机性能每 18 个月提高一倍, 价格每半年降低一半, 是否已经到达极限? 是否会不再遵循摩尔法则? 杨振宁在西安科协 2000 年会议上, 明确地答复了这个问题 : 是什么原因促使芯片容量长期成倍地增长, 新原理新方法新道理, 是维持创新的源泉, 创新是人类知识发展生产发展的重要因素计算机机器性能价格比持续提高, 硬件发展如此之快, 是否没有必要去追求提高算法的时间复杂度没有必要去追求节省算法占用存储空间的数目呢? 不是没有必要, 而是要求越来越高原因之一是, 由于机器性能价格比的提高, 人们所面临的处理问题的问题规模越来越大, 要把过去不可能解决的问题变得可能, 必须要求高性能的算法 ; 另一个原因是, 即使在同一问题规模情况下, 算法性能好坏差别很大, 一个是 O(n) 数量级, 一种是 O(2 n ) 数量级, 当 n=32 时,2 n 的结果都已很大, 即使 n 再增大一倍,2 n 几乎都已经无法表述, 这不是硬件发展速度所能满足的由此说明, 硬件速度的提高决不是人们可以不重视算法性能的理由, 而是人们追求高性能算法的动力图 1.8 所示为数据结构与其他课程关系图图 1.8 数据结构与其他课程关系图 1. 数据结构课程地位明确提出数据结构概念不过 30 多年, 数据结构作为一门独立课程在国外 1968 年开始设立, 我国从 20 世纪 80 年代初才开始正式开设数据结构课程数据结构课程较系统地介绍了软件设计中常用数据结构及相应的存储结构和算法, 系统地介绍了常用的查找和排序技术, 并对各种结构与技术进行分析和比较, 内容非常丰富数据结构涉及多方面的知识, 如计算机硬件范围的存储装置和存取方法, 软件范围中的文件系统数据的动态管理信息检索, 以及数学范围中关于集合逻辑的知识, 还有一些综合性的知识 ( 如数据类型程序设计方法数据表示数据运算数据存取等 ), 是计算机专业一门重要的专业技术基础课程数据结构的内容将为操作系统数据库原理编译原理等后续课程的学习打下良好的基础, 数据结构课程不仅讲授数据信息在计算机中的组织和表示方法, 还训练高效地解决复杂问题程序设计的能力, 因此数据结构是数学计算机硬件计算机软件三者之间的一门核心课程, 10

11 数据结构课程是计算机专业提高软件设计水平的一门关键性课程数据结构发展趋势包括两个方面 : 一方面, 面向专门领域中特殊问题的数据结构的研究和发展, 如图形数据结构知识数据结构空间数据结构 ; 另一方面, 从抽象数据类型的角度, 用面向对象观点来讨论数据结构, 已成为新的发展趋势 2. 数据结构课程学习特点数据结构课程教学目标要求学生学会分析数据对象特征, 掌握数据组织方法和计算机的表示方法, 以便为应用所涉及的数据选择适当的逻辑结构存储结构及相应算法, 初步掌握算法时间空间分析的技巧, 培养良好的程序设计技能人类解决问题的思维方式可分为两大类 : 一类是推理方式, 凭借公理系统思维方法, 从抽象公理体系出发, 演绎归纳推理, 求证结果, 解决特定问题 ; 另一类是算法方式, 凭借算法构造思维方式, 从具体操作规范入手, 通过操作过程的构造和实施解决特定问题开发一个优秀的软件系统过程中所凭借的思维方法本质上不同于常规数学训练的公理系统思维方法, 而是一种算法构造性思维方法系统开发是创造性思维过程的实现, 因而, 对于一名开发人员, 只知道开发工具的语言规则和简单使用过程是不够的首先要有科学方法指导开发过程 ; 然后在编程技术应用技能上积累提高让学生理解习惯熟悉这一套算法构造思维方法, 是计算机软件课程教学的重要内容和主要难点数据结构的学习过程是进行复杂程序设计的训练过程技能培养的重要程度不亚于知识传授难点在于 : 理解授课内容与应用知识解答复杂问题之间的素质能力差距培养优良的算法设计思想方法技巧与风格, 进行构造性思维训练过程, 强化程序抽象能力, 培养数据抽象能力从某种意义上说, 数据结构是程序设计的后继课程如同学习英语一样, 学习英语不难, 学好英语不易, 要提高程序设计水平必须经过艰苦的磨炼因此, 学习数据结构, 仅从书本上学习是不够的, 必须经过大量的实践, 在实践中体会构造性思维方法, 掌握数据组织与程序设计的技术 3. 关于本书内容编写说明 (1) 本书基本结构基本结构分为如下四大部分第一部分 : 绪论第二部分 : 基本的数据结构包括 : 线性结构 ( 第 2~4 章 ) 线性表栈和队列串和数组 ; 非线性结构 ( 第 5 6 章 ) 树图第三部分 : 基本技术包括查找与排序 ( 第 7 8 章 ) 第四部分 : 实验实训 (2) 本书内容编排模式本书所列出的程序均在 Turbo C 2.0 下调试通过, 所有算法均采用严谨的 C 语言进行描述, 只需加以必要的类型定义与调用, 即可上机运行使用每章附有习题, 以便于读者做配套练习 11

12 本章小结 (1) 要求理解的概念包括 : 数据数据元素数据结构数据类型数据结构概念应从数据的逻辑结构存储结构和相关运算 3 个方面进行讨论它反映了数据结构设计的不同层次 : 逻辑结构属于问题抽象范畴, 是对数据描述的过程 ; 存储结构是逻辑结构在计算机中的存储映像与表示方法, 是数据表示的形式 ; 而相关运算涉及数据操作的要求, 是解决问题的实现方法 (2) 有关算法的概念和算法设计的基本要求必须了解算法的定义特性和算法设计的基本要求基本掌握 C 语言的基本概念和用 C 语言编写阅读应用程序的基本技术 (3) 算法性能分析方面, 必须了解算法的时间和空间复杂度, 掌握算法性能 ( 时间空间 ) 的简单分析方法, 特别是程序中原操作执行频度的估计和大 O 表示法, 这对于算法的评价与选择非常重要的习题选择题 (1) 计算机识别存储和加工处理的对象统称为 A. 数据 B. 数据元素 C. 数据结构 D. 数据类型 (2) 数据结构通常研究数据的及它们之间的联系 A. 存储和逻辑结构 B. 存储和抽象 C. 理想和抽象 D. 理想与逻辑 (3) 不是数据的逻辑结构的是 A. 散列结构 B. 线性结构 C. 树结构 D. 图结构 (4) 数据结构被形式地定义为 <D,R>, 其中 D 是的有限集,R 是的有限集 A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构 (5) 组成数据的基本单位是 A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 (6) 设数据结构 A=(D, R), 其中 D={1, 2, 3, 4},R={r}, r={<1, 2>, <2, 3>, <3, 4>, <4, 1>}, 则数据结构 A 是 A. 线性结构 B. 树形结构 C. 图状结构 D. 集合 (7) 数据在计算机存储器内表示时, 物理地址与逻辑地址相同并且是连续的, 称为 A. 存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链式存储结构 12

13 (8) 在数据结构的讨论中, 把数据结构从逻辑上分为 A. 内部结构与外部结构 B. 静态结构与动态结构 C. 线性结构与非线性结构 D. 紧凑结构与非紧凑结构 (9) 对一个算法的评价, 不包括方面的内容 A. 健壮性和可读性 B. 并行性 C. 正确性 D. 时空复杂度 (10) 算法分析的两个方面是 A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 1.2 填空题 (1) 数据结构是一门研究非数值计算的程序设计问题中计算机的及它们之间的和运算等的学科 (2) 数据结构包括数据的结构和结构 (3) 数据结构从逻辑上划分为三种基本类型 : 和 (4) 数据的物理结构被分为和四种 (5) 一种抽象数据类型包括和两部分 (6) 数据的逻辑结构是指, 数据的存储结构是指 (7) 数据结构是指数据及其相互之间的当结点之间存在 M 对 N(M N) 的联系时, 称这种结构为当结点之间存在 1 对 N(1 N) 的联系时, 称这种结构为 (8) 对算法从时间和空间两方面进行度量, 分别称为分析 (9) 算法的效率可分为效率和效率 (10)for(i=1,t=1,s=0;i<=n;i++) {t=t*i;s=s+t;} 的时间复杂度为 1.3 简述下列术语 : 数据数据项数据元素数据逻辑结构数据存储结构数据类型和算法 1.4 分析下面语句段执行的时间复杂度 (1)for(i=1;i<=n;i++) for(j=1;j<=n;j++) s++; (2)for(i=1;i<=n;i++) for(j=i;j<=n;j++) s++; (3)for(i=1;i<=n;i++) for(j=1;j<=i;j++) s++; (4)i=1;k=0; while(i<=n 1){ k+=10*i; i++; } 13

14 (5)for (i=1;i<=n;i++) for (j=1;j<=i ;j++) for (k=1;k<=j;k++) x=x+1; 1.5 试写一算法, 自大至小依次输出顺序读入的三个整数 X Y 和 Z 的值 1.6 编写算法, 求一元多项式 P n (x)=a 0 +a 1 x+a 2 x 2 +a 3 x 3 + +a n x n 的值 P n (x 0 ), 要求算法的时间复杂度尽可能地小 14

型来实现首先进行输入然后将数据存储在结构体类型中最后根据需要进行输出任务实现定义一个结构体类型实现学生成绩信息的存储! "# $ "%!$&& 输入三个学生的成绩 "' "' "'"# " 学号姓名成绩输出三个学生成绩 "%!$&& "''' "# 程序运行结果如图所示图简单学

型来实现首先进行输入然后将数据存储在结构体类型中最后根据需要进行输出任务实现定义一个结构体类型实现学生成绩信息的存储! # $ %!$&& 输入三个学生的成绩 ' ' '# 学号姓名成绩输出三个学生成绩 %!$&& ''' # 程序运行结果如图所示图简单学项目目标知识目标理解和掌握结构中的基本概念理解和掌握线性结构树形结构和图形结构的概念以及二元组的表示方法理解算法评价的规则算法时间复杂度和空间复杂度的概念以及数量级的表示方法技能目标具有对现实世界的数据进行抽象表示的能力具有对算法时间复杂度和空间复杂度进行简单分析的能力素质目标正确认识计算机中数据的表示与存储方法培养团队协作精神培养分析问题解决问题的能力任务简单学生成绩管理系统