Java版数据结构(程序员必须看)

《Java版数据结构(程序员必须看)》由会员分享，可在线阅读，更多相关《Java版数据结构(程序员必须看)（1063页珍藏版）》请在金锄头文库上搜索。

1、数据结构 计算机科学与技术学院张宏 第一章绪论 1 1什么是数据结构1 2有关概念和术语1 3算法和算法分析1 3 1算法1 3 2算法设计的要求1 3 3算法效率的度量1 3 4算法的存储空间的需求 第一章绪论 计算机学科一直处于高速发展中 而且这种发展速度还会持续 计算机科学已经难以完全覆盖学科新的发展 因此扩展后的学科称为计算学科 包括 计算机科学 计算机工程 软件工程 信息系统 关键问题 利用计算机进行信息表示和处理的涉及 信息的表示信息的处理而信息的表示和组织又直接关系到处理信息的程序的效率 随着计算机的普及 信息量的增加 信息范围的拓宽 使许多系统程序和应用程序的规模很大 结构又相

2、当复杂 因此 为了编写出一个 好 的程序 必须分析待处理的对象的特征及各对象之间存在的关系 这就是数据结构这门课所要研究的问题 1 1什么是数据结构众所周知 计算机的程序是对信息进行处理 在大多数情况下 这些信息并不是没有组织的 信息 数据 之间往往具有重要的结构关系 这就是数据结构的内容 什么是数据结构呢 例子 例1 电话号码查询系统设有一个电话号码薄 它记录了N个人的名字和其相应的电话号码 假定按如下形式安排 a1 b1 a2 b2 an bn 其中 ai bi i 1 2 n 分别表示某人的名字和对应的电话号码 要求设计一个算法 当给定任何一个人的名字时 该算法能够打印出此人的电话号码

3、如果该电话簿中根本就没有这个人 则该算法也能够报告没有这个人的信息 数据结构含义 就是研究数据的逻辑结构和物理结构以及它们之间相互关系 并对这种结构定义相应的运算 而且确保经过这些运算后所得到的新结构仍然是原来的结构类型 所有能被输入到计算机中 且能被计算机处理的符号的集合 数据 是计算机操作的对象的总称 是计算机处理的信息的某种特定的符号表示形式 1 2有关概念和术语 是数据 集合 中的一个 个体 数据元素 是数据结构中讨论的基本单位 数据结构主要指逻辑结构和物理结构数据之间的相互关系称为逻辑结构 通常分为四类基本结构 一 集合结构中的数据元素除了同属于一种类型外 别无其它关系 二 线性结构

4、结构中的数据元素之间存在一对一的关系 三 树型结构结构中的数据元素之间存在一对多的关系 四 图状结构或网状结构结构中的数据元素之间存在多对多的关系 一个数据元素可由若干个数据项组成 数据项是数据的不可分割的最小单位 数据对象 DataObject 是性质相同的数据元素的集合 是数据的一个子集 数据结构 DataStructure 是相互之间存在一种或多种特定关系的数据元素的集合 数据在计算机中的表示称为数据的物理结构 又称为存储结构 数据对象可以是有限的 也可以是无限的 数据结构不同于数据类型 也不同于数据对象 它不仅要描述数据类型的数据对象 而且要描述数据对象各元素之间的相互关系 数据类型

5、在一种程序设计语言中 变量所具有的数据种类 例1 在FORTRAN语言中 变量的数据类型有整型 实型 和复数型例2 在C 语言中数据类型 基本类型和构造类型基本类型 整型 浮点型 字符型构造类型 数组 结构 联合 指针 枚举型 自定义数据对象 某种数据类型元素的集合 例3 整数的数据对象是 3 2 1 0 1 2 3 英文字符类型的数据对象是 A B C D E F 1 3算法和算法分析1 3 1算法 是对特定问题求解步骤的一种描述 是指令的有限序列 其中每一条指令表示一个或多个操作 算法具有以下五个特性 1 有穷性一个算法必须总是在执行有穷步之后结束 且每一步都在有穷时间内完成 2 确定性算

6、法中每一条指令必须有确切的含义 不存在二义性 3 可行性一个算法是可行的 即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的 4 输入一个算法有零个或多个输入 这些输入取自于某个特定的对象集合 5 输出一个算法有一个或多个输出 这些输出是同输入有着某些特定关系的量 1 3 2算法设计的要求 设计算法时 通常应考虑达到以下目标 1 正确性2 可读性3 健壮性4 高效率与低存储量需求 1 正确性 首先 算法应当满足以特定的 规格说明 方式给出的需求 其次 对算法是否 正确 的理解可以有以下四个层次 a 程序中不含语法错误 b 程序对于几组输入数据能够得出满足要求的结果 c 程序对于精

7、心选择的 典型 苛刻且带有刁难性的几组输入数据能够得出满足要求的结果 通常以第c层意义的正确性作为衡量一个算法是否合格的标准 d 程序对于一切合法的输入数据都能得出满足要求的结果 2 可读性 算法主要是为了人的阅读与交流 其次才是为计算机执行 因此算法应该易于人的理解 另一方面 晦涩难读的程序易于隐藏较多错误而难以调试 3 健壮性 当输入的数据非法时 算法应当恰当地作出反映或进行相应处理 而不是产生莫名奇妙的输出结果 并且 处理出错的方法不应是中断程序的执行 而应是返回一个表示错误或错误性质的值 以便在更高的抽象层次上进行处理 4 高效率与低存储量需求 通常 效率指的是算法执行时间 存储量指的

8、是算法执行过程中所需的最大存储空间 两者都与问题的规模有关 1 3 3算法效率的度量 通常有两种衡量算法效率的方法 事后统计法 事前分析估算法 缺点 1 必须执行程序2 其它因素掩盖算法本质 和算法执行时间相关的因素 1 算法选用的策略 2 问题的规模 3 编写程序的语言 4 编译程序产生的机器代码的质量 5 计算机执行指令的速度 一个特定算法的 运行工作量 的大小 只依赖于问题的规模 通常用整数量n表示 或者说 它是问题规模的函数 假如 随着问题规模n的增长 算法执行时间的增长率和f n 的增长率相同 则可记作 T n O f n 称T n 为算法的 渐近 时间复杂度 如何估算算法的时间复杂

9、度 算法 控制结构 原操作 固有数据类型的操作 算法的执行时间 原操作 i 的执行次数 原操作 i 的执行时间 算法的执行时间与原操作执行次数之和成正比 从算法中选取一种对于所研究的问题来说是基本操作的原操作 以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则 voidmult inta intb intc for i 1 i n i for j 1 j n j c i j 0 for k 1 k n k c i j a i k b k j for mult 基本操作 乘法操作 时间复杂度 O n3 例1 例 x s 0 将x自增看成是基本操作 则语句频度为1 即时间复杂度为 1 如

10、果将s 0也看成是基本操作 则语句频度为1 其时间复杂度仍为 1 即常量阶 例 for i 1 i n i x s x 语句频度为 n其时间复杂度为 O n 即时间复杂度为线性阶 i 0 赋值 次 i 1 赋值2次 i 2 赋值3次 i n 1 赋值n次 1 2 3 n 1 n n 2 n2 2 n 2 例 for i 1 i n i for j 1 j n j x s x 语句频度为 n2其时间复杂度为 O n2 即时间复杂度为平方阶 例 for i 0 i n 1 i for j 0 j i j a i j 0 定义 如果f n 是正整数n的一个函数 若存在两个正常数c和n0 对于所有的n

11、 n0 有 f n c g n 则记作f n O g n 例 f x anxn an 1xn 1 a1x a0 其中an不等0 n为正整数 则f x O xn 证明 f x anxn an 1xn 1 a1x a0 anxn an 1xn 1 a1x a0 an xn an 1 xn 1 a1 x1 a0 x0 当x 1 n0 n为正整数时 xn 1 xn 所以 an xn an 1 xn 1 a1 x1 a0 x0 an xn an 1 xn a1 xn a0 xn an an 1 a1 a0 xn c xn 其中 n0 1 c an an 1 a1 a0 g n xn 一个算法时间为O 1

12、 的算法 它的基本运算执行的次数是固定的 因此 总的时间由一个常数 即零次多项式 来限界 而一个时间为O n2 的算法则由一个二次多项式来限界 以下六种计算算法时间的多项式是最常用的 其关系为 O 1 O logn O n O nlogn O n2 O n3 指数时间的关系为 O 2n O n O nn 当n取得很大时 指数时间算法和多项式时间算法在所需时间上非常悬殊 1 3 4算法的存储空间的需求 算法的空间复杂度定义为 表示随着问题规模n的增大 算法运行所需存储量的增长率与g n 的增长率相同 S n O g n 算法的存储量包括 1 输入数据所占空间 2 程序本身所占空间 3 辅助变量所

13、占空间 若输入数据所占空间只取决于问题本身 和算法无关 则只需要分析除输入和程序之外的辅助变量所占额外空间 若所需额外空间相对于输入数据量来说是常数 则称此算法为原地工作 若所需存储量依赖于特定的输入 则通常按最坏情况考虑 注意 时间与空间往往是对矛盾 要综合考虑 最坏时间复杂性 例6 有的情况下 算法中基本操作重复执行的次数还随问题的输入数据集不同而不同 例如 voidbubble sort inta intn for i n 1 i 0 i for j 0 ja j 1 a j a j 1 时间 最好情况 0次最坏情况 每次都换 n2 空间 一个数据交换的辅助空间 算法原地工作 例7 递归

14、程序的分析intfact intn if n 1 return1 elsereturnn fact n 1 f n c f n 1 c c f n 2 2c f n 2 n 1 c f 1 n 1 c c0 课时安排与考核 学分3 授课2 5 40课时 上机0 5 8 8课时 考核 平时成绩20 作业 课后与课堂 实验课程考试80 作业 计算时间复杂度sum 1 for i 0 sum n i sum i 2 设给定若干n值 比较两函数n2和50nlog2n的增长趋势 并确定在什么范围内 函数n2的值大于50nlog2n的值 第二章线性表 2 1线性表的类型定义2 2线性表的顺序表示和实现2

15、3线性表的链式表示和实现2 3 1线性链表2 3 2循环链表2 3 3双向链表2 4一元多项式的表示及相加 2 1线性表的逻辑结构线性表 由n n 0 个数据元素 结点 a1 a2 an组成的有限序列 其中数据元素的个数n定义为表的长度 当n 0时称为空表 常常将非空的线性表 n 0 记作 a1 a2 an 这里的数据元素ai 1 i n 只是一个抽象的符号 其具体含义在不同的情况下可以不同 例1 26个英文字母组成的字母表 A B C Z 例2 某校从1978年到1983年各种型号的计算机拥有量的变化情况 6 17 28 50 92 188 神经衰弱 17 男 790634 张立立 健康 2

16、1 男 790633 刘建平 一般 20 女 790632 陈红 健康 18 男 790631 王小林 健康情况 年龄 性别 学号 姓名 例3 学生健康情况登记表如下 从以上例子可看出线性表的逻辑特征是 1 对非空的线性表 有且仅有一个开始结点a1 它没有直接前驱 而仅有一个直接后继a2 2 有且仅有一个终端结点an 它没有直接后继 而仅有一个直接前驱an 1 3 其余的内部结点ai 2 i n 1 都有且仅有一个直接前驱ai 1和一个直接后继ai 1 线性表是一种典型的线性结构 数据的运算是定义在逻辑结构上的 而运算的具体实现则是在存储结构上进行的 2 2线性表的顺序存储结构2 2 1线性表把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里 用这种方法存储的线性表简称顺序表 假设线性表的每个元素需占用m个存储单元 并以所占的第一个单元的存储地址作为数据元素的存储位置作为参考点 则线性表中第i 1个数据元素的存储位置Loc ai 1 和第i个数据元素的存储位置Loc ai 之间满足下列关系 Loc ai 1 Loc ai m 线性表的第i个数据元素ai的存储位置为 Loc a1