算法笔记（二）数据结构
1.1数据结构：
数据结构实计算机中对数据的一种存储和组织的方式，同时也泛指相互之间存在一种或多种特定关系的数据的集合。
1.1.1什么是数据结构
到现在为止，计算机技术领域中还没有一个统一的数据结构的定义。以下是引用的部分解释：
名词定义
Data_Structure=(D,R) 其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。[2] 其它定义 Sartaj Sahni在他的《数据结构、算法与应用》一书中称：“数据结构是数据对象，以及存在于该对象的实例和组成实 例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。 Clifford A.Shaffer在《数据结构与算法分析》一书中的定义是：“数据结构是ADT（抽象数据类型Abstract Data Type） 的物理实现。” Robert L.Kruse在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。 数据结构具体指同一类数据元素中，各元素之间的相互关系，包括三个组成成分，数据的逻辑结构，数据的存储结构和数据运算结构。
虽然并没有一个统一的定义，但是这些定义都具有相似的含义。
数据结构实一切算法的基础。
数据结构实程序设计语言的基础。
2.1.1数据结构的基本概念
数据：数据是信息的载体，是计算机程序加工的原材料。整数，字符，字符串，实体类，图像，声音等都可以认为是数据结构。
数据元素：数据元素是数据的基本单位，也称为元素，结点，顶点，记录等。
数据结构：数据结构指的是数据之间的相互关系，也就是数据的组织形式。
2.1.2数据结构的内容
一般来说数据结构包括数据的逻辑结构，数据的存储结构和数据的运算。
数据的逻辑结构：
数据元素之间的逻辑关系。数据的逻辑结构是从逻辑关系上描述数据，跟数据在计算机中如何存储无关，是独立于计算机的抽象概念。从数学分析的角度来看，数据的逻辑结构可以看做从具体问题抽象出来的数学模型。
数据的存储结构：
数据元素及其逻辑关系在计算机存储器的表现形式。数据的存储结构依赖于计算机语言，是逻辑机构用计算机语言的实现。一般只有高级语言的层次上才会讨论存储结构，低级的机器语言存储结构是具体的。
数据的运算：
能够对数据是假的操作。数据的运算的基础为数据的逻辑结构，每种逻辑结构都可以归纳为一个运算的集合，常用的与运算有检索，插入，删除，更新和排序等。
数据结构是一个有机的整体，同一个逻辑结构可以有不同的存储结构，同一种逻辑结构也可以有不同的数据运算集合。
数据的逻辑结构，数据的存储结构和数据的运算任何一个发生改变都将导致一个全新的数据结构出现。
2.1.3数据结构分类
按照数据的逻辑结构可以简单的分为线性结构和非线性结构。
线性结构：
线性结构就是表中各个节点具有线性的关系。如线性表，栈，队列和串等。从数据结构的语言来描述，线性结构应包括：
线性结构是非空集；
线性结构有且仅有一个开始节点和一个终端节点；
线性结构所有节点左右只有一个直接前趋节点和一个直接后继节点。
非线性结构：
表中各个节点具有多个对应关系，如数组，广义表，树结构和图结构等。非线性结构应包括：
非线性结构是非空集；
非线性结构的一个节点可能有多个直接前趋节点和直接后继节点。
数据结构的存储方式：
顺序存储方式：
顺序存储方式就是在一块连续的存储区域一个接一个的存放数据。顺序存储方式把逻辑上相邻的的节点存储在物理位置上相邻的存储单元里，节点见得逻辑关系由存储单元的邻接关系来体现。顺序存储方式也称为顺序存储结构，一般用数组或结构数组来描述。
现行存储方式主要用于现行逻辑结构的数据存放，对于图合数等非线性结构并不适用。
链接存储方式：
链接存储方式不要求逻辑上相邻的节点在物理位置上相邻，节点间的逻辑关系由附加的引用字段标识，一个节点的引用字段往往指向下一个节点的存放位置。
链接存储方式也成为链式存储结构。一般在原数据项中增加引用类型表示节点之间的位置关系。
索引存储方式：
是采用附加索引表的的方式来存节点信息的一种存储方式。索引表由若干索引项组成。
索引存储方式还可以分为稠密索引和稀疏索引。
散列存储方式：
散列存储方式是根据节点的关键字直接计算出该结点的存储地址的一种存储方式。往往根据具体的数据结构来决定采用哪种存储方式。
2.1.4数据类型
按照数据类型的值是否可以分解，数据类型可以分为基本数据类型和聚合数据类型。
基本数据类型：一般是程序语言自身定义的的一些数据类型。
聚合数据类型：其值可以进一步分解为若干分量，一般是用户自定义的数据类型。
抽象数据类型(ADT)：
是指数据的组织及其相关操作。ADT可以看做数据的逻辑结构及其在逻辑结构上定义的操作。
抽象数据类型一般具有两个重要特征：
数据抽象：使用抽象数据类型时，强调的是实体的本质特，所能够完成的功能，以及与外部用户的接口。
数据封装：用于将尸体的外部特性和其内部实现细节进行分离，并且对外部用户隐藏其内部实现细节。
2.1.4常用的数据结构
数组：
数组是一种聚合数据类型，是将具有相同类型的若干变量有序的组织在一起的集合。
栈：
栈是一种特殊的线性表，其只能在一个表的一个固定的端进行数据节点的插入和删除操作。栈按照后进先出的原则存储数据。栈中没有数据称为空栈。
队列：
队列和栈类似，也是一种特殊的线性表。但队列只允许在表的一端进行插入操作，而另一端进行删除操作。进行插入操作的一端称为队尾，进行删除操作的一端称为队头。
链表：
链表是一种数据元素按照链式存储结构进行存储的树结构，这种数据结构在物理上具有非连续的特点。链表由一系列数据节点构成，每个数据节点包括数据域和引用域两部分。
树：
树是典型的非线性结构，是包括n个结点的有穷集合K。在树中有且仅有一个根节点，该结点没有前驱结点，其他结点都有且仅有一个前驱结点，而且可以有m个后继结点。
图：
图是一种非线性结构。数据结点一般称为顶点，而边是结点的序偶对。
堆：
堆是一种特殊的树形数据结构，一般讨论的对都是二叉堆。堆得特点是根节点的值是所有节点中最小或最大的，并且根节点的两个子树也是一个堆结构。
散列表：
散列表源自于散列函数，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较比较而直接取得所查记录。
2.2线性表
线性表是由n个元素组成的有限序列。
数据元素的个数为n，数据长度为n，n=0时称为空表。
对于一个非空线性表，其逻辑结构特征如下，
有且仅有一个开始结点a1，没有直接前趋结点，有且仅有一个直接后继结点a2；
有且仅有一个终结结点an，没有直接后继结点，有且仅有一个直接前趋结点a（n-1）；
其余内部结点都有且仅有一个直接前趋结点和一个直接后继结点。
对于同一线性表，各数据元素ai必须具有相同的数据类型，即统一==同一线性表中各项数据元素具有相同的类型，每个数据元素的长度相同。