数据结构概述

数据结构就是按一定的逻辑关系组织起来的待处理数据元素的表示和相关操作,包含数据的逻辑结构,存储结构和数据的运算.

数据的逻辑结构

从具体问题中抽象出来的数学模型,反应了事物的组成结构和事物之间的逻辑关系.

逻辑结构可以用一个二元组B = (K, R)表示.K是数据结点(node)组成的有穷集合,每个结点代表一个或者一组明确结构的数据,R是定义在集合K上的一组关系,每个关系r(r∈R)都是K上的二元关系,用来描述数据结点的逻辑结构.

数据结构重点研究的是数据之间的结构关系,因此把组成结构的那些元素均称为结点.

数据的逻辑结构一般有三种,分别是线性结构,树形结构,图结构.

关系r为线性关系,每个结点最多只有一个前驱一个后继.

关系r为层次结构,每个结点最多有一个前驱可以有多个后继.

也称为网络结构,每个结点的前驱和后继数量不加限制.

数据的存储结构要解决各种逻辑结构在计算机中物理存储表示.

计算机的主存储器具有空间相邻和随机访问的特点:用非负整数对存储地址编码,提供对存储空间上相邻的单元集合的随机访问;计算机指令具有按地址随机访问存储空间内任意单元的能力,访问不同地址所需的访问时间基本相同.

同一种逻辑结构可以用不同的存储结构.

把一组结点放在一片地址相邻的存储单元中,结点之间的逻辑关系用存储单元之间的自然顺序表达.

在结点的存储结构中附加指针域来存储结点之间的逻辑关系.

索引是顺序方法的一种推广.通过建造一个由整数域Z映射到存储地址域D的索引函数,把整数索引值映射到结点的存储地址,形成存储了一组指针的索引表.

散列方法是索引方法的延伸和推广,散列法用散列函数进行索引计算,通过索引表求出结点的指针地址.

数据运算是对数据依某种模式而建立起来的关系进行处理的过程。最基本的数据运算有：
算术运算，如：加、减、乘、除、乘方、开方、取模等；
关系运算，如：等于、不等于、大于、小于等；
逻辑运算，如：与、或、非、恒等。

为了实现算法细节和数据结构的隐蔽,出现了类,随后出现了模块.模块分为模块式和模块体,模块式定义外部可见的运算接口,模块体定义不可见的私有数据和运算.

通过接口和实现的分离,达到数据抽象,信息隐蔽的作用.模块所定义的数据类型就叫做抽象数据类型.

抽象意味着一个概念有多种实现方式.一旦有一个抽象问题得到解决,很多同类问题也会得到解决.