数据结构---C++版

1.1 数据结构在程序设计中的作用
1）程序设计的实质是什么?
数据表示：将数据存储在计算机（内存）中
数据处理：处理数据，设计方案（算法）
1.2 计算机求解问题:
1）问题→抽象出问题的模型→求模型的解
问题——数值问题、非数值问题
2）数 值 问 题→数学方程
非数值问题→数据结构
3）本书讨论非数值问题的数据组织和处理，主要内容如下：
（1）数据的逻辑结构：线性表、树、图等数据结构，其核心
是如何组织待处理的数据以及数据之间的关系；
（2）数据的存储结构：如何将线性表、树、图等数据结构存
储到计算机的存储器中，其核心是如何有效地存储数据以及
数据之间的逻辑关系；
（3）算法：如何基于数据的某种存储结构实现插入、删除、
查找等基本操作，其核心是如何有效地处理数据；
（4）常用数据处理技术：查找技术、排序技术、索引技术等。
1.3 数据结构的基本概念
1）数据结构的基本概念
（1）数据：所有能输入到计算机中并能被计算机程序识别和处理的符号集合。
数值数据：整数、实数等
非数值数据：图形、图象、声音、文字等
（2）数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
（3）数据项：构成数据元素的不可分割的最小单位。
2）数据、数据元素、数据项之间的关系
（1）包含关系：数据由数据元素组成，数据元素由数据项组成。
（2）数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。
3）数据结构的基本概念
（1）数据结构：相互之间存在一定关系的数据元素的集合。
按照视点的不同，数据结构分为逻辑结构和存储结构。
逻辑结构：指数据元素之间逻辑关系的整体。
（2）数据的逻辑结构是从具体问题抽象出来的数据模型
数据的逻辑结构在形式上可定义为一个二元组：
Data_Structure = (D, R)
其中D是数据元素的有限集合，R是D上关系的集合。
（3）存储结构：又称为物理结构，是数据及其逻辑结构在计算机中的表示。
（4）存储结构实质上是内存分配，在具体实现时依赖于计算机语言。
5）数据结构从逻辑上分为四类：
（1）集合：数据元素之间就是“属于同一个集合” ；
（2）线性结构：数据元素之间存在着一对一的线性关系；
（3）树结构：数据元素之间存在着一对多的层次关系；
（4）图结构：数据元素之间存在着多对多的任意关系。
6）通常有两种存储结构：
（1）顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。
（2）链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示 。
7）逻辑结构和存储结构之间的关系
（1）数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。
（2）一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。
8）抽象数据类型
（1） 数据类型（Data Type）：一组值的集合以及定义于这个值集上的一组操作的总称。
例如：C++中的整型变量
（2）抽象（Abstract）:抽出问题本质的特征而忽略非本质的细节。
例如： 地图、驾驶汽车
（3）抽象数据类型（Abstract Data Type，ADT）:一个数据结构以及定义在该结构上的一组操作的总称。
注意：在设计ADT时，把ADT的定义、设计和实现分开来。定义部分只包含数据的逻辑结构和所允许的操作集合，一方面，ADT的使用者依据这些定义来使用ADT，即通过操作集合对该ADT进行操作；另一方面，ADT的实现者依据这些定义来完成该ADT各种操作的具体实现。
9）抽象数据类型
ADT 抽象数据类型名
Data
数据元素之间逻辑关系的定义
Operation
操作1
前置条件：执行此操作前数据所必须的状态
输 入：执行此操作所需要的输入
功 能：该操作将完成的功能
输 出：执行该操作后产生的输出
后置条件：执行该操作后数据的状态
操作2
……
……
操作n
……
endADT
10）数据结构的基本概念（小结）

1.4 算法及算法分析
1）算法的相关概念