目录
1.研究方向
2.基本概念和术语
3.数据结构
3.1 逻辑结构
3.2 存储结构
3.3 数据类型和抽象数据类型
计算机主要用于数值计算时， 一般要经过如下几个步骤：
在此过程中寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间的关系，然后用数学语言加以描述，即建立相应的数学方程。例如:
- 用计算机进行全球天气预报时，就需要求解一组球面坐标系下的二阶椭圆偏微分方程
- 预测人口增长情况的数学模型为常微分方程
求解这些数学方程的算法是计算数学研究的范畴，如高斯消元法、差分法、有限元法等算法。数据结构主要研究非数值计算问题，非数值计算问题无法用数学方程建立数学模型.
数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。数据结构的研究不仅涉及计算机硬件（特别是编码理论、存储装置和存取方法等） 的研究范围，而且和计算机软件的研究有着密切的关系，无论是编译程序还是操作系统都涉及数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以使查找和存取数据元素更为方便。因此，可以认为数据结构是介于数学、计算机硬件和软件三者之间的一门核心课程。
随着大型程序和大规模文件系统的出现，很多人认为程序设计的实质就是对所处理的问题选择一种好的数据结构，并在此结构基础上施加一种好的算法，著名科学家Wirth教授的《算法+数据结构＝程序》正是这种观点的集中体现。
数据(Data)： 是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑中用到的字符串，多媒体程序处理的图形、图像、声音及动画等通过特殊编码定义后的数据。
数据元素(Data Element)： 是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、记录等。数据元素用于完整地描述一个对象，如前一节示例中的一名学生记录，树中棋盘的一个格局（状态），以及图中的一个顶点等。
数据项(Data Item) ：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象(Data Object)： 是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N= {O, 士1' 士2, …}, 字母字符数据对象是集合C= {'A','B', …，'Z','a','b', …，'z'}, 学生基本信息表也可以是一个数据对象。由此可以看出，不论数据元素集合是无限集（如整数集），或是有限集（如字母字符集），还是由多个数据项组成的复合数据元素（如学生表） 的集合， 只要集合内元素的性质均相同， 都可称之为一个数据对象。
数据结构(Data Structure) ：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说， 数据结构是带”结构＂ 的数据元素的集合， “结构” 就是指数据元素之间存在的关系。
数据结构包括逻辑结构和存储结构两个层次。
数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，
数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的逻辑结构有两个要素： 一是数据元素；二是关系。数据元素的含义如前所述，关系是指数据元素间的逻辑关系。根据数据元素之间关系的不同特性， 通常有四类基本结构， 如图1.3所示。它们的复杂程度依次递进。
下面四种结构中所举的示例是以某班级学生作为数据对象（数据元素是学生的学籍档案记
录），来分别考察数据元素之间的关系。
(1) 集合结构
数据元素之间除了“属于同一集合” 的关系外， 别无其他关系。例如， 确定一名学生是否为
班级成员， 只需将班级看做一个集合结构。
(2) 线性结构
数据元素之间存在一对一的关系。例如， 将学生信息数据按照其入学报到的时间先后顺序进
行排列，将组成一个线性结构。
(3) 树结构
数据元素之间存在一对多的关系。例如， 在班级的管理体系中，班长管理多个组长， 每位组
长管理多名组员， 从而构成树形结构。
(4) 图结构或网状结构
数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系， 任何两位同学都可以是
朋友，从而构成图状结构或网状结构。
其中集合结构、树结构和图结构都属于非线性结构。
线性结构包括线性表（典型的线性结构， 如例1.1中的学生基本信息表）、栈和队列（具有特
殊限制的线性表，数据操作只能在表的一端或两端进行）、字符串（也是特殊的线性表，其特殊性
表现在它的数据元素仅由一个字符组成）、数组（是线性表的推广，它的数据元素是一个线性表）、广义表（也是线性表的推广， 它的数据元素是一个线性表，但不同构，即或者是单元素，或者是线性表）。非线性结构包括树（具有多个分支的层次结构）和二叉树（具有两个分支的层次结构）、有向图（一种图结构，边是顶点的有序对）和无向图（另一种图结构，边是顶点的无序对）。
数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。把数据对象存储到
计算机时，通常要求既要存储各数据元素的数据， 又要存储数据元素之间的逻辑关系，数据元素
在计算机内用一个结点来表示。数据元素在计算机中有两种基本的存储结构，分别是顺序存储结
构和链式存储结构。
(1)顺序存储结构
顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助
程序设计语言的数组类型来描述。
对于前面的“学生基本信息表”， 假定每个结点（学生记录） 占用50 个存储单元，数据从0
号单元开始由低地址向高地址方向存储，对应的顺序存储结构如表1.2所示。
(2) 链式存储结构
顺序存储结构要求所有的元素依次存放在一片连续的存储空间中， 而链式存储结构，无需占
用一整块存储空间。但为了表示结点之间的关系， 需要给每个结点附加指针字段，用于存放后继
元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。
假定给前面的“学生基本信息表” 中的每个结点附加一个“下一个结点地址＂，即后继指针字段，用于存放后继结点的首地址，则可得到如表1.3所示的链式存储结构。从表中可以看出，每个结点占用两个连续的存储单元，一个存放结点的信息，另一个存放后继结点的首地址。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。例如，C语言中的整型变址，其值集为某个区间上的整数（区间大小依赖于不同的机器），定义在其上的操作为加、减、乘、除和取模等算术运算；而实型变量也有自己的取值范围和相应运算，比如取模运算是不能用于实型变量的。程序设计语言允许用户直接使用的数据类型由具体语言决定，数据类型反映了程序设计语言的数据描述和处理能力。
抽象数据类型(Abstract Data Type, ADT) 一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。说白了在C++中就是struct和class。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/1393.html