数据结构——绪论

Data Structure

算法 + 数据结构 = 程序设计

基本数据结构：

线性结构：线性表；栈，队列，双队列；数组，串；
非线性结构：树，二叉树；图，网。

用计算机解决具体问题的步骤主要是：

首先从具体问题抽象出一个适当的数字模型；
设计一个解决此数学模型的算法；
编程序，进行测试，调整直至得到最终解答。

基本概念

数据

所有能输入到计算机中并被计算机程序加工、处理的符号的总称。如：整数、实数、字符、声音、图像、图形等。

数据元素

数据的基本单位。在计算机程序中通常作为一个整体进行考虑和处理。也被称为记录。

数据项

是数据的不可分割的最小单位。如：姓名、年龄等。一个元素可由一个或多个数据项组成。

数据对象

由性质相同（类型相同）的数据元素组成的集合。数据对象是数据的一个子集。

数据结构

相互之间存在一种或多种特定关系的数据关系的数据元素的集合。数据元素之间的关系称为结构。四类基本结构：集合、线性结构、树形结构、图状结构。

数据的存储结构

数据结构在计算机存储器中的映像。存储结构也称为：存储表示、物理结构、物理表示。

顺序存储结构（向量、一维数组）；
非顺序存储结构（链接表）。

数据类型

一个值的集合和定义在这个值上的一组操作的总称。

原子类型（如：int, char, float等）
结构类型（如：线性表、数组、树等）

抽象数据类型

抽象数据类型一般是指一个数学模型以及定义在该模型上的一组操作，它是对数据结构逻辑上的定义，与计算机的实现无关。

一个抽象数据类型可用一个三元组来表示：（D，S，P）。D表示数据对象，S表示数据元素之间的关系集，P是对D中数据元素的基本操作。

算法

基本特征

所谓算法是对特定问题求解步骤的一种描述，换言之，算法给出了求解一个问题的大致思路和步骤，但它还不是程序。

有穷性：在有限步（或有限时间）之后算法终止；
确定性：每条指令或步骤都无二次元性，具有明确的含义；
可行性：算法中的操作都是已经实现的基本运算执行有限次实现的；
输入：有零或多个输入量；
输出：至少有一个输出量。

设计要求

正确性：
- 无语法错误；
- 对几组输入产生正确结果；
- 对特殊输入产生正确结果；
- 对所有输入产生正确结果。
可读性：算法主要是为了人的阅读与交流
健壮性：不同的输入都要有相应的反应；
高效性与低存储量。

描述工具

自然语言；
程序设计语言；
流程图（框图）；
伪码语言：一种包括高级程序设计语言的三种基本结构（顺序、选择、循环）和自然语言成分的“面向读者”的语言；
类C语言：介于伪码语言和程序设计语言之间的一种表示形式。保留了C语言的精华；不拘泥于C语言的语法细节；同时也添加了一些C++的成分。有着便于理解、阅读；能方便地转换成C语言的特点。

主题

函数：用以表示算法

函数类型 函数名 (函数参数表) 
{
    //算法说明
    语句序列
} //函数名

注：算法说明应包括功能说明，输入，输出；为提高算法可读性，关键位置加以说明；明确函数实参和形参的匹配规则，以便能正确使用算法函数。