数据结构期末复习总结.doc

绪论
1.数据(Data)：是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。
包括数值数据和非数值数据（字符串、图形、图像、音频、视频）。
2.数据元素(DataElement)：表示一个事物的一组数据称为一个数据元素（结点顶点、记录）；数据元素是数据的基本单位。
3.数据项（DataItem）：是数据元素中有独立含义的、不可分割的最小标识单位（字段、域、属性）。一个数据元素可由若干个数据项组成。
4.数据对象(DataObject)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C={A,B,C,…}。
数据(Data)：是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。
包括数值数据和非数值数据（字符串、图形、图像、音频、视频）。
数据元素(DataElement)：表示一个事物的一组数据称为一个数据元素（结点、顶点、记录）；数据元素是数据的基本单位。
数据项（DataItem）：是数据元素中有独立含义的、不可分割的最小标识单位（字段、域、属性）。一个数据元素可由若干个数据项组成。
数据对象(DataObject)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C={A,B,C,…}。

数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合上的若干关系来表示。
四种逻辑结构：集合、线性结构、树型结构、图状结构。
数据结构的形式定义是一个二元组：
Data-Structure=(D，S)
其中：D是数据元素的有限集，S是D上关系的有限集。
例1：设数据逻辑结构B=（K，R）
K={k1,k2,…,k9}
R={<k1,k3>，<k1,k8>，<k2,k3>，<k2,k4>，<k2,k5>，<k3,k9>，<k5,k6>，<k8,k9>，<k9,k7>，<k4,k7>，<k4,k6>

有时候关系图不唯一（一般是无向图）
数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。
两种不同的存储结构：顺序存储结构和链式存储结构。
顺序结构：数据元素存放的地址是连续的；
链式结构：数据元素存放的地址是否连续没有要求，用该指针来表示数据元素之间的逻辑结构(关系)。
顺序存储—使用一组连续的内存单元依次存放数据元素，元素在内存中的物理存储次序体现它们的逻辑次序。通常使用程序设计语言中的数组来实现。

链式存储—使用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻。数据元素间的逻辑关系通过结点间的链接关系来体现。通常使用指针记载直接前驱元素或直接后继元素的存储地址。

数据操作指对一种数据结构中的数据元素进行各种运算或处理。每种数据结构都有一组数据操作。
初始化。
判断是否空状态。
统计元素的个数。
遍历：按某种次序访问所有元素，每个元素只被访问一次。
取值：获取指定元素值。
置值：设置指定元素值。
插入：增加指定元素。
删除：移去指定元素。
查找：在数据结构中寻找满足给定条件的数据元素。
排序：将数据元素
...
数据操作定义在数据的逻辑结构上；
数据操作的实现依赖于数据的存储结构。
数据结构三方面的关系：
数据的逻辑结构、数据的存储结构及操作这三方面是一个整体
例6：线性表是一种逻辑结构，若采用顺序存储，可称其为顺序表；若采用链式存储，则可称其为链表；若采用散列存储，则可称为散列表。
在给定了数据的逻辑结构和存储结构之后，按定义的操作集合及其操作的性质不同，也可能导致完全不同的数据结构。
类型（type）是具有相同逻辑意义的一组值的集合。
数据类型是指一个类型和定义在这个类型上的操作集合。
数据类型定义了数据的性质、取值范围以及对数据所能进行的各种操作
例7：Java中整型类型int的值集是
[-231,…,-2,-1,0,1,2,…,231-1]
这个值集上的操作集合[+,-,*,/,%,=,==,!=,<,<=,>,>=]

抽象数据类型(AbstractDataType，简称ADT)：是指一个数学模型以及定义在该模型上的一组操作。
ADT的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。
ADT的形式化定义是三元组：ADT=(D，S，P)
其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。
ADT的一般定义形式是：
ADT<抽象数据类型名>{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}ADT<抽象数据类型名>
例8：复数抽象数据类型描述如下：
ADTComplex{
doublereal,imag;
Comple