数据结构概述 原
数据结构是介于数学、计算机硬件和计算机软件之间的一门核心课程。 数据结构所要研究的主要内容简单归纳为以下3个方面： 研究数据元素之间的客观联系（逻辑结构）； 研究数据在计算机内部的存储方式（存储结构）； 研究如何在数据的各种结构上实施有效的操作或处理。 所以数据结构是一门抽象地研究数据之间的关系的学科。
一、数据
数据（data）在计算机科学中是指输入到计算机中并能够被计算机识别、存储和加工处理的符号的总称。
以下是一些常用的名词及其释义。
1．数据项
数据的基本物理单位是数据项。数据项是指具有独立含义的最小识别单位。数据项具有原子性。数据项又称为项或字段。
数据项有逻辑形式（logical form）和物理形式（physical form）两方面。 用ADT给出的数据项的定义是它的逻辑形式。数据结构中对数据项的实现是它的物理形式。
2．数据元素
数据元素（data element）是数据逻辑意义上的基本单位，通常把数据元素作为一个整体进行考虑和处理。数据元素可由一个或多个数据项组成。
3．数据对象
数据对象（data object）是性质相同的数据元素的集合，是数据的子集。
4．数据域
当数据元素由若干个数据项组成时，对应于各个数据项的子位串称为数据域。
5．指针域
在非顺序映像中借助指示元素存储地址，描述数据元素之间逻辑关系的部分称为指针域。
6．结点
1>定义
计算机中表示信息的最小单位是二进制数的一位，称为位（bit）。 由若干位串表示一个数据元素，称为元素或结点。 结点也可以描述为数据处理的数据单位，它可能是一条记录、一个数据项或组合数据项。
2>分类
对应结点定义根据结点所处位置的不同可以将表中的结点分为前趋结点和后继结点。 对表中任意结点，有以下概念： 处于该结点之前的所有结点称为该结点的前趋结点。 处于该结点之后的所有结点称为该结点的后继结点。 与之相邻的前趋结点称为直接前趋结点。 与之相邻的后继结点称为直接后继结点。 表中的第一个结点称为开始结点。 表中的最后一个没有后继的结点称为终端结点。
二、数据关系
在数据结构中数据之间的关系主要有两种，它们分别是线性关系和非线性关系。 其中非线性关系又可分为树形关系和图关系。 数据的逻辑结构和存储结构是密不可分的两方面，在实现算法时，首先应该解决数据的存储问题。 数据之间纪要考虑存储，又要考虑数据单位之间的关系，在确定存储结构之后，根据存储的结构再来确定相应的操作的实现方法。
三、数据结构
结构通常指关系，所以数据结构是指数据之间的关系的一门学科，它表示的是数据之间的相互形式，机数据的组织形式。
1．定义
数据结构是研究数据的存储、数据之间的关系及对数据实现各种操作的一门学科。
数据结构（data structure）是指相互之间存在一种或多种特定关系的数据元素的集合。是组织并存储数据以便能够有效使用的一种专门格式，它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。
数据结构的定义可以记作：Data-Structure=(D,R) D是数据元素的有限集合，R是D上的关系。 数据的存储结构要能够正确反映数据元素之间的逻辑关系。
任何一种算法的设计取决于选定的逻辑结构，而算法的实现则依赖于采用的存储结构。
2．分类
根据用户和计算机两个角度可以将数据结构分为逻辑机构和存储结构。其实也就是根据抽象和具象进行分类。 根据数据的结构特性在数据的生存期间的变动情况，可以将数据分为静态结构和动态结构。
1>逻辑结构
逻辑结构又叫抽象结构 一般情况下，“关系”是指数据元素之间存在的逻辑关系，也称为数据的逻辑结构。 逻辑结构体现的是数据元素之间的逻辑关系。
①描述方式
数据的逻辑结构可以采用两种方法来描述：二元组、图形。
1)二元组
数据结构的二元组表示形式为： 数据结构= {D , S} 其中D是数据元素的集合；S是D中数据元素之间的关系集合，并且数据元素之间的关系是使用序偶来表示的。序偶是由两个元素x和y按一定顺序排列而成的二元组，记作<x , y>，x是它的第一元素，y是它的第二元素。
2)图形
当使用图形来表示数据结构时，是用图形中的点来表示数据元素，用图形中的弧来表示数据元素之间的关系。如果数据元素x与y之间有关系<x , y>，则在图形中有从表示x的点出发到达表示y的点的一条弧。
②分类
按照数据元素之间相互关系的特性来分，可以分为以下四种结构：集合、线性结构、树形结构和图状结构 只考虑数据元素而不考虑它们之间的关系的数据结构称为集合结构。 具有线性关系的数据结构称为线性结构。 除了一个数据元素意外，每个数据元素有且仅有一个直接前趋元素，但可以有多个直接后续元素的数据结构称为树结构。 每个数据元素可以有多个直接前趋元素，也可以有多个直接后续元素的数据结构称为图结构。
2>物理结构
物理结构又叫存储结构。 数据在计算机内的存储表示（或映像）称为数据的存储结构或者物理结构。 它包括数据元素的表示和关系的表示。 数据元素之间的关系在计算机中主要有两种不同的表示方法：顺序映像（Sequential Mapping）和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。
①顺序存储结构
特点： 在顺序存储结构中体现数据之间的关系。 顺序映像是借助元素在存储器中位置表示数据元素之间的逻辑关系，或逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点的逻辑关系由存储单元的邻接关系来体现。
②非顺序存储结构
非顺序结构一般采用指针实现数据之间的关系。 包括链式存储结构（链表）、散列结构和索引存储结构等。 非顺序映像是借助元素与存储地址的指针表示元素之间的逻辑关系，或逻辑上相邻的结点在物理位置上可相邻，可不相邻，逻辑关系由附加的指针段表示。
1)链式存储结构
链式存储结构利用指针直接表示数据元素之间的关系。
2)散列结构
散列结构的基本思想是根据结点的关键字，利用散列函数直接计算出该结点的存储地址。
3)索引存储结构
索引存储结构是值在存储结点信息的同时，还简历附加的索引表。 索引表的每一项称为索引项，索引项的一般形式是：关键字，地址。 关键字是能够唯一标识一个结点的那些数据项集合。 索引结构分为稠密索引和稀疏索引。
<1>稠密索引
稠密索引是指每个结点在索引表中都有一个索引项的索引表。
<2>稀疏索引
稀疏索引是指一组结点在索引表中对应一个索引项的索引表。
3>动态结构
动态结构是指在一定范围内结构的大小可以发生变动。如：堆栈、队列以及树形结构等。
4>静态结构
静态结构是指在数据存在期不发生任何变动。如：静态数组。
四、数据类型
1．定义
数据类型（data type）是指一组性质相同的数据元素的集合以及加在这个集合上的一组操作。
定义数据类型的作用： 1.隐藏计算机硬件及其特性和差别。使硬件对于用户而言是透明的，即用户可以不关心数据类型是怎么实现的而可以使用它。 2.用户能够使用数据类型定义的操作，方便的实现问题的求解。
所谓顶层的运算步骤是指定义在数据模型级上的运算步骤，或叫宏观运算。 涉及的运算以数据模型中的数据变量作为运算对象，或作为运算结果，或二者兼而为之，简称为定义在数据模型上的运算。
所谓底层的运算步骤是指顶层抽象的运算的具体实现。 底层的运算步骤包括两部分：一是数据模型的具体表示；二是定义在该数据模型上的运算的具体实现。 底层运算是顶层运算的细化，底层运算为顶层运算服务。
2．分类
数据类型根据是否允许分解可分为原子类型和结构类型。
1>原子类型
原子类型是指其值不可再分的数据类型。例如：整形、字符型。 计算机硬件的原子类型：位、字节、字
2>结构类型
结构类型是指其值可以再分解为若干成分的数据类型。
五、抽象数据类型
为了将顶层算法与底层算法隔开，使二者在设计时不会互相牵制、互相影响，必须对二者的接口进行一次抽象。让底层只通过这个接口为顶层服务，顶层也只通过这个接口调用底层的运算。这个接口就是抽象数据类型。
1．定义
抽象数据类型（Abstract Data Type,ADT）由一种数据模型和在该数据模型上的一组操作组成。
抽象数据类型包括定义和实现两个方面，其中定义是独立于实现的。 抽象数据类型的定义取决于它的一组逻辑特性，与其在计算机内的表示和实现无关。
数据结构是ADT的物理实现。
抽象数据类型比数据类型的范畴更广，它不仅局限在处理器中已经定义并实现的数据类型，还包括用户在设计软件时自己定义的数据类型。
抽象数据类型的三元组表示：ADT=(D,S,P) 其中，D表示数据对象，S是D上的关系集，P是加在D上的一组操作。 ADT可以使用以下格式描述：
ADT抽象数据类型名{
数据对象:<数据对象的定义>
数据关系:<数据关系的定义>
基本操作:<基本操作的定义>
}ADT抽象数据类型名2．分类
抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成，如果按照其值的不同特性，可细分为3种类型： 原子类型：属于原子类型的变量的值是不可再分的。 固定聚合类型：属于该类型的变量的值由确定数目的成分按照某种结构组成。 可变聚合类型：属于该类型的变量的值的成分数目不确定，其中序列的长度是可变的。 固定聚合类型和可变聚合类型统称为结构类型。
3．应用案例
1>Java中的int
整数的数学概念和施加到整数的运算就构成了一个ADT。Java中的变量类型int就是对这个抽象类型的物理实现。 但是int型变量有一定的取值范围，所以对这个抽象的整型的实现不完全正确，如果无法接受该限制，就必须引进一些其他的实现方式来实现这个抽象类型，比如：long类型。
2>整数线性表
一个整数线性表的ADT应包含以下操作： 1.数据的存储结构确定线性关系。 2.把一个新整数插入到表尾。 3.按线性表的元素顺序依次打印。 4.删除线性表的某个元素。 5.判断线性表是否存在某个元素，成功返回true，失败返回false。 6.将线性表的整数排序。
3>三元组定义
抽象数据类型的三元组定义如下：
ADT Tri{
数据对象：D={e1,e2,e3|e1,e2,e3∈element(已经定义的数据集合)}
数据关系：R1={<e1 e2> R2=<e2 e3>}
基本操作：
inittri(&t,v1,v2,v3)
结果：构造三元组t，并将v1、v2、v3赋值给e1、e2、e3完成初始化。
tansporttri(m,&t)
结果：将矩阵M转置为T。
addtri(m,n,&q)
结果：求矩阵m和n和，结果放在q中。
}4．总结
ADT的概念就是将复杂问题抽象化。抽象化之后的问题是使我们重视问题而忽略不必要的细节。 ADT不同于类，区别在于ADT相当于在概念层上描述问题，而类相当于在实现层上描述问题。
六、数据结构的意义
瑞士计算机科学家N.Wirth曾提出：算法+数据结构=程序。 其中数据结构是指数据逻辑结构和物理结构，算法是对数据运算的描述。 程序设计的实质是对具体问题选择一种好的数据结构，再设计一个好的算法，好的算法同城取决于实际问题的数据结构。 解决问题的关键是：选择合适的数据结构表示问题，然后写出有效的算法。
七、算法
如果问题是一个需要完成的任务，即对应一组输入就有一组相应的输出。只有问题被准确定义并完全理解后才能够研究问题的解决方法。
从数学的角度讲，可以把问题看做函数。函数是输入（定义域，domain）和输出（值域，range）之间的一种映射关系。输入值称为函数的参数。不同的输入可以产生不同的输出，但是给定的输入，每次必须有相同的输出。
算法设计是最具创造性的工作之一，人们解决任何问题的思想、方法和步骤实际上都可以认为是算法。
1．定义
算法（algorithm）是指令的集合，是为解决特定问题而规定的一系列操作。
算法的结构设计和选择依赖于作为其基础的数据结构。数据结构为算法提供了工具。 算法是利用这些工具来解决问题的最优方案。
算法就是解决问题的方法，或者算法是解决某个特定问题的一些指令的集合，或者由人们组织起来加以准备实施的有限的基本步骤。 流程图是图形化的算法。程序是计算机语言描述的算法。
2．特性
一个完整的算法具备一下5个性质： 1.正确性。算法得到的结果必须是正确的。 2.确定性。算法的组成指令必须是清晰的无二义的。 3.有穷性。算法必须在有限的步骤内结束。 4.输入。算法可以包含n（n≥0）个数据的输入。 5.输出。算法至少有一个输出。
3．设计要求
设计一个好的算法要达到以下4个目标： 1.正确性。包含结果、输入、输出以及执行过程的正确性。也就是这里的正确性包含算法性质的5个性质。 2.可读性。算法主要是为了阅读与交流，可读性好有助于对算法的理解。 3.健壮性。当输入非法数据时，算法能够做出反应或进行处理，不会出现莫名其妙的输出结果。 4.效率与低存储量需求。效率是指算法的执行时间。存储量需求是指算法执行过程所需要的最大的存储容量。效率和低存储量两者通常情况下是矛盾的，两者都与问题的规模有关，需要设计人员进行权衡。
4．算法分析
算法分析主要是指判定算法的优劣，判断一个算法的好坏一般从两个方面考虑，即时间角度和空间角度。评价一个算法性能的好坏，实际上就是评价算法的资源占用问题。一般算法分析从时间角度考虑的较多。
1>分析方法
度量一个程序的执行时间通常有两种方法，分别是事后统计方法和事前分析估算的方法。
①事后统计方法
这种方法的缺点是，必须先运行依据算法编制的程序；所花时间的统计量依赖于计算机的软硬件等环境因素，容易掩盖算法本身的优劣。
②事前分析估算的方法
使用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素： (1).算法选用的策略 (2).问题规模 (3).书写程序的语言 (4).编译产生的机器代码质量 (5).机器执行指令的速度 因为计算机软硬件的因素，可能使用上述5点来计算算法执行的时间有些不太合适，如果撇开这些因素，那么算法的效率就依赖于问题的规模。
实践中我们可以把两种方法结合起来使用。
2>时间复杂度
一般我们将算法的求解问题的输入称为问题的规模，使用整数n表示。 在算法的每个步骤中，可能有若干条语句，而频度就是指每条语句的执行次数。 时间复杂度是指算法的时间耗费。
以一条基本语句的执行时间为基本单位，该算法所有语句中总的基本语句的执行次数就是改算法的时间耗费，它是该算法求解的问题规模n的函数。当n趋向无穷大时，我们把时间复杂度的数量阶称为算法的渐进时间复杂度。一般我们把渐进时间复杂度称为算法的时间复杂度，记作“O”（Order）。
数学定义：T(n)=O(f(n)) 当n≥n0时满足0≤T(n)≤C*f(n)
顺序检索法的时间代价总是相差不多的，无论数组中的元素是否是按照顺序保存。 二分法检索要求元素必须按从低到高的顺序保存。根据二分法的使用环境，这个排序的要求可能会对时间代价产生损害，因为要保持数组的顺序性，在插入新元素时会增加时间代价。
3>空间复杂度
空间复杂度（Space Complexity）类似于时间复杂度，是指该算法所耗费的存储空间。也是问题规模n的函数。一般是指渐进空间复杂度。
数学定义：S(n)=O(T(n))
在存储结构中，类似指针一样的开销实际上是附加信息的开销，称为结构性开销。从理论上讲，这种结构性开销应该尽量小，而访问路径又应该尽可能多且有效。时间空间的权衡也正是研究数据结构的乐趣所在。
5．总结
算法分析时，除特别指明，均是按照最坏的情况分析。我们通常所说的算法的复杂度一般是算法的时间复杂度和空间复杂度的合称。 最好的时间空间改进来源于好的数据结构和算法。所以解决问题的步骤应该是：先调整算法，后调整代码。
参考文献：《数据结构与算法分析 Java语言描述》、《数据结构与算法分析 Java语言描述第二版》、《数据结构与算法（Java语言版解密）》