1.1数据结构的研究内容:

计算机数值计算一般步骤：首先从具体问题抽象出数学模型——》然后设计一个解释此数学模型的算法——》最后编写程序。

上述过程中，寻求数学模型的实质是分析问题；从中提取操作对象，并找出这些对象之间的关系，然后用数学语言加以描述，即建立相应的数学方程。

数据结构主要研究非数值计算问题，非数值计算问题无法用数学方程建立数学模型；

数据结构：（简化定义）是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作

的学科，数据结构是介于数学、计算机硬件和软件三者之间的一门核心课程。

非数值计算数据结构模型实例：

线性表结构（元素之间一一对应）：学生学籍管理模型，图书馆的书目管理系统，库存管理系统

树数据结构（元素之间一对多）：人机对弈问题，计算机文件系统，单位组织机构

图结构（元素之间多对多）：最短路径问题，网络工程图，网络通信

数据结构发展简述：

20实际60年代初期，“数据结构”散见于操作系统、编译原理；

1968年，作为独立课程列入美国一些大学的计算机科学教学计划；同年计算机科学家D.E.Knuth教授发表《计算机程序设计艺术》第一卷《基本算法》。这是第一本教系统的阐述数据机构基本内容的著作。

之后，结构化程序设计成为程序设计方法学的主要研究方向，人们普遍认为，程序设计的实质，就是对所处理的问题选择一种好的数据结构，并在此结构的基础上施加一种好的算法。著名科学及Wirth教授的《算法+数据结构=程序》正是这种观点的集中体现。

数据结构发展方向：

一方面，面向个专门领域中特殊问题的数据结构正在研究和发展；

一方面，从抽象数据类型的观点来讨论数据结构，已成为一种新趋势。

1.2.1基本概念和术语：

数据（data）：客观事物的表示符号，是所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素（data-element）：数据的基本单位，一般也被称为元素；用于完成的描述一个对象，例如学生学籍管理模型中一名学生的记录，可被称为一个数据元素。

数据项（data item）：是组成数据元素的、有独立含义的、不可分割的最小单位。例如一名学生记录表中的学号、姓名、性别等。

数据对象（data object）：是性质相同的数据元素的集合，是数据的一个子集。学生基本信息表也可被看作一个数据对象，他是学生信息的集合。一个集合内，元素的性值均相同，都可称之为一个数据对象。

数据结构（data structure）：是相互之间存在一种或多种特定关系的数据元素的集合，换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是数据元素之间存在的关系，比如线性结构，树结构等。

数据结构的形式定义：

是一个二元组：

Data-Structure（D，S）；其中D是数据元素的有限集合，S是D上关系的有限集合；

数据结构包括逻辑结构和存储结构两个层次：

1）逻辑结构：数据的逻辑结构是从逻辑关系上描述数据，他与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据元素之间的关系，可以是数据之间代表某种元素的自然关系，也可以是为处理问题方便人为定义的关系，这种自然或人为定义的关系，称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。

逻辑结构两要素：数据元素，关系。关系是指数据元素之间的逻辑关系；根据数据元素之间关系的不同特性，通常有四类结构，如下所示，他们的复杂程度一次递进：

a.集合结构：数据元素属于同一集合，别无其他关系

b.线性结构：数据元素之间一一对应的关系结构；例如将学生信息按学号一一排列

c.树结构：数据元素之间存在一对多的关系；例如，在公司管理中，老板管理多个项目组，项目组管理多个员工

d.图结构或网状结构：数据元素之间存在多对多的关系；例如多位同学之间的朋友关系

其中集合结构，树结构，网状结构，都是非线性结构

线性结构包括线性表、栈、队列（具有特殊限制的线性表，数据操作只能在表的一端多两端进行）、字符、数组、广义表。

非线性结构包括树、二叉树、有向图、无向图

2）存储结构：数据对象在计算机中的存储表示数据的存储结构，也称物理结构，把数据对象存储在计算机时，既要存储数据元素的数据，又要存储数据元素之间的关系，数据元素在计算机内用一个结点表示。

数据元素在计算机中的两种基本存储结构：顺序存储结构、链式存储结构。

顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构，顺序存储结构要求元素依次存放在一片连续的存储空间中；如下图所示：

链式存储结构：顺序存储结构要求元素依次存放在一片连续的存储空间中，而链式结构无需占用一整块存储空间，但为了表示节点之间的关系，需要给每个结点附加一个指针字段，用于存放后继元素的存储地址，所以链式存储结构通常借助于程序设计语言的指针类型来描述，如下图所示：

顺序存储结构、链式存储结构的区别和联系：

区别：

顺序结构：数据元素存放的地址是连续的；

链式结构：数据元素之间存放的地址是否连续没有要求

联系：

数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选的逻辑结构，而算法的实现依赖于所采用的逻辑结构。

逻辑结构与所采用的存储结构：

1.2.2数据类型和抽象数据类型

数据类型（data type）：指的是一个值的集合和定义在该值集上的一组操作的总称。

数据类型和数据结构密不可分，js中有引用数据类型和基本数据类型

数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描写数据对象各元素之间的相互关系。

数据结构的运算：

1）建立（create）一个数据结构

2）消除（Destroy）一个数据结构

3）从一个数据结构中删除（Delete）一个数据元素

4）把一个数据元素插入（Insert）到一个数据结构中

5）对一个数据结构进行访问（Access）

6）对一个数据结构中的元素进行修改（Modify）

7）对一个数据结构进行排序（Sort）

8）对一个数据结构进行查找（Search）

抽象数据类型（Abstract Data Type，ADT）：是指一个数学模型，以及定义在该模型上的一组操作。

ADT定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关，因此，不论ADT内部结构如何让变化，只要其数学特性不变，都不影响其外部使用

ADT的形式化定义是三元组：ADT = （D，S，P）

其中D是数据对象，S（数据关系）是D上的关系集，P（基本操作）是对D的基本操作。

ADT的一般定义形式：

ADT<抽象数据类型名>{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

        基本操作：<基本操作的定义>

} ADT<抽象数据类型名>

  ——其中，数据对象和数据关系的定义用伪码描述;

       ——<基本操作的定义> ：

<基本操作名>(<参数名>)

初始条件：<初始条件描述>

操作结果：<操作结果描述>

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

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

抽象数据类型使用的意义：

运用抽象数据类型描述数据结构，有助于在设计一个软件系统时，不必首先考虑其中包含的数据对象，以及操作在不同处理器中的表现和实现细节，而是在构成软件系统的每个相对独立的模块上定义一个数据和相应的操作，把这些数据的表示和操作细节留在模块内部解决，在更高层次上进行软件的分析和设计，从而提高软件的整体性能和利用率。

ADT概念与卖你想对象思想一致，ADT独立于具体实现，将数据和操作封装在一起，使得用户程序只能通过ADT定义的某些操作来访问其中的数据，从而实现了信息隐藏。在C++中，类的声明表示ADT，类的实现表示ADT的实现。