数据结构

基本术语

数据是输入计算机且能被计算机处理的各种符号的集合

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，也简称为元素、或称为记录、结点或顶点。一个数据元素可由若干哥数据项组成。数据项是构成数据元素的不可分割的最小单位。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

例如:
整数数据对象是集合N={0，±1，±2，…}
字母字符数据对象是集合C={‘A’，B’, …’z’}
学籍表也可看作一个数据对象

数据元素不是孤立存在的，它们之间存在着某种关系，数据元素相互之间的关系称为结构(Structure )
是指相互之间存在一种或多种特定关系的数据元素集合·或者说，数据结构是带结构的数据元素的集合

数据结构包括以下三个方面的内容：

有且仅有一个开始和一个终端结点，并且所有结点最多只有一个直接前趋和一个直接后继。

例如：线性表、栈、队列、串

一个结点可能有多个直接前趋和直接后继。

例如：树、图

用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示，C语言中用数组来是实现顺序存储结构

用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。C语言中用指针来实现链式存储结构。

在存储结点信息的同时，还建立附加的索引表。

根据结点的关键字直接计算出该结点的存储地址

在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。·一些最基本数据结构可以用数据类型来实现，如数组、字符串等;·而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示。

数据类型 = 值的集合+值集合上的一组操作

抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作。由用户定义，从问题丑行出数据模型（逻辑结构）

基本操作定义格式说：

参数表：赋值参数只为操作提供输入值

引用参数以&打头，除可提供输入值外，还将返回操作结果

初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应的出错信息。若初始条件为空，则省略之。

操作结果：说明操作正常完成之后，数据结构的变化状况和应返回的结果。