第1章绪论 1.2逻辑结构《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

什么是数据结构 基本概念和术语 算法和算法分析 第一章 绪论 逻辑结构 --- 划分方法 一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。 二、线性结构 结构中的数据元素之间存在一对一的关系。 a1 a2 a3 a4 三、树型结构 结构中的数据元素之间存在一对多的关系。 a b c d e f g h 树形结构抽象描述示意图 四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 1 2 3 4 图形结构抽象描述示意图 存储结构（Storge Structure): 数据结构在计算机中的表示(或称映象）称为数据的存储结构，又称为物理结构。 四种基本的存储方法： （1）顺序存储方法（顺序存储结构） （2）链接存储方法（链式存储结构） （3）索引存储方法 （4）散列存储方法 同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。 顺序存储结构: 用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队列 树形结构 图形结构 数据结构的三个方面： 散列存储 索引存储 串及数组 例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。 （1） S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)} 解： 上述表达式可用图形表示为： b c a e f d 故，此结构为线性的。 （2） S=(D,R) D={di | 1≤i≤5} R={(di , dj ), i<j} d1 d5 d2 d4 d3 该结构是非线性的。 解：上述表达式可用图形表示为： 1.3 算法和算法分析 一、算法的概念和描述： 1、什么是算法？ 是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。 2、 算法描述 算法具有以下五个特性： （1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 （2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。 （3）可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。 算法设计的要求 评价一个好的算法有以下几个标准: (1) 正确性(Correctness) 算法应满足具体问题的需求。 (2) 可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解，便于调试和修改。 (3) 健状性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 (4) 效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 注意：算法和程序的关系 算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。 单击此处编辑母版文本样式 第二级