数据结构复习资料 第一章 绪论
- 格式：doc
- 大小：116.50 KB
- 文档页数：6
第一章绪论
重点：理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。
掌握计算语句频度和估算算法时间复杂度的方法。
难点：抽象数据类型的定义、表示和实现方法，算法时间复杂度的分析。
1.1 数据结构的基础知识
一．什么是数据结构？
一般地，用计算机解决一个具体问题时，大致需要以下几个步骤：
①找出求解问题的数学模型
②设计一个算法（解此模型的）
③编程调试
下面通过三个典型例子来说明数据结构的概念及所讨论的问题。
例1 图书馆的书目检索系统自动化问题
诸如此类的还有查号系统自动化、仓库帐目管理等。
在这类文档管理的数学模型中，计算机处理的对象之间通常存在着的是一种最简单的线性关系，这类数学模型称为线性的数据结构。
例2人机对弈
解决这类问题的数学模型可称为“树形”数据结构。
“树”可以是某些非数值计算问题的数学模型，它也是一种数据结构，是一种非线性的树形数据结构。
例3多叉路口交通灯的管理问题
通常，这种交通、道路问题的数学模型是一种称为“图”的数据结构，是一种复杂的非线性的图形数据结构。
综上所述，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如
表、树和图之类的数据结构。
因此，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
二．基本术语
数据（data ）
数据元素(data element)
数据元素是数据这个集合中的个体，即数据的基本单位。
数据元素在计算机程序中通常作为一个整体进行考虑和处理。
数据项(data item)
例 一个学生登记表
数据对象(data object)
结构(structure)
数据结构(data structure) （相互之间存在一种或多种特定关系的数据元素的集合）
数据结构的概念一般包括：数据之间的逻辑关系，数据在计算机中的存储方式和数据的运算三个方面。
为了叙述上的方便，把上述数据结构的三个方面分别称为：
⎪⎩⎪⎨⎧数据的运算
数据的存储结构
数据的逻辑结构
)3()2()1( 在理解时，不要孤立地去理解一个方面，而要注意它们之间的联系。
根据元素之间关系的不同特性，通常有四类结构：
① 集合
② 线性结构
③ 树形结构
④图状结构或网状结构
数据结构的形式定义为：数据结构是一个二元组：
）（S D Structure Data ,=-
其中：D ——数据元素的有限集；S ——是D 上元素关系的有限集。
例4 在计算机科学中，复数可如下定义：复数是一种数据结构
()R C complex ,=
其中：C 是含两个实数的集合{}21,c c C =，{}P R =，而P 是定义在
集合C 上的一种关系{2
1,c c P =
，其中有序偶21,c c 表示1c 是复数的实
部，2c 是复数的虚部。
例5 5P 例1.5。
数据的逻辑结构（logical structure ）
数据的存储结构(storage structure):它包括数据元素的存储及元素之间关系的存储，更重要的是元素之间关系的存储！ 位（bit ）
结点（node ）
域（field ）
数据元素之间的关系在计算机中有两种不同的表示方法（但细分有4种不同的存储方式：顺序存储、链式存储、索引存储、哈希存储）：
顺序映象和非顺序映象，由此得到两种不同的存储结构：
⎩⎨
⎧链式存储结构顺序存储结构
数据的存储结构是逻辑结构在计算机存储器里的实现。
1．顺序存储结构
主要特点：
2．链式存储结构
主要特点：
** 任何一个算法的设计取决于所选定的数据（逻辑）结构，而算法的实现
则依赖于采用的存储结构。
·数据类型（data type ）
·抽象数据类型(ADT:Abstract Data Type)
元素（element ）
·原子类型——原子类型的变量的值是不可分解的。
·非原子类型——其值可以再分解的数据类型。
从以上对数据类型的讨论中可见，与数据结构密切相关的是定义在数据结构上的一组操作。
·数据的操作（运算）
数据的各种逻辑结构均有的相应运算：
⎪⎪⎪⎩⎪⎪⎪⎨⎧新排列。
点按某种指定的顺序重列的结点数不变，把结保持线性结构中结点序排序：查找更新
删除插入
所有的操作分为两类：
·加工型操作（constructor ）——操作改变了（操作前）结构的值。
·引用型（selector ）——不改变结构的值，只是查询或求得结构的值。
1.2 算法的描述和算法分析
一．什么是算法？
算法的五大特征：
（1）有穷性
（2）确定性
（3）可行性
（4）输入
（5）输出：
二．算法的描述
本书采用类C 语言描述。
10P （要求：学生必须掌握）。
三．算法设计的原则（性能标准）
通常设计一个“好”算法应达到以下目标：
（1）正确性（correctness ）
（2）可读性（readability ）
（3）健壮性（robustness ）
（4）运行时间（时间复杂性）
（5）占用的存储空间（空间复杂性）
四．算法效率的度量
1．事前估计法
2．事后统计法
算法分析是确定一个算法需多少计算时间和存储空间的技术。
·问题的规模n （size of problem ）
·空间复杂度)(n S （space complexity ）
·时间复杂度)(n T （time complexity ）
·最坏情况运行时间（复杂度）)(n T
·期望（平均）运行时间（复杂度）)(n T avb
·语句的频度（frnquency count ）
要分析算法，首先要确定要用哪些运算及执行运算所花的时间。
⎩⎨⎧-+的比较。
基本运算的复合：如串，，比较，赋值，调用等，，
，基本运算：)1(/*O
注：各种算术运算和逻辑运算的时间为)1(O （即囿于常数时间）；赋值（数据传递）的时间亦为)1(O 。
))(()(n f O n T =、))(()(n g n T Ω=的含义。
例6 设函数2323)(n n n T +=，证明)()(3n O n T =，)()(3
n n T Ω=。
例7 计算!n 的递归函数)(n fact 的运行时间的分析。
例8 累加求和
常见的算法时间复杂度有：
)()()log ()()(log )1(3
2n O n O n n O n O n O O <<<<<
)()!()2(n n n O n O O << ·算法的空间复杂度
算法的存储量包括:
1．输入数据所占空间
2．程序本身所占空间
3．辅助变量所占空间
注意：算法的所有性能之间都存在着或多或少的相互影响，因此，当设计一个算法，特别是大型算法时，要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的大小、算法描述语言的特性及算法运行的机器系统环境等各方面因素，才能设计出比较好的算法。
