1 绪论

数据结构主要是研究数据结构的逻辑结构、存储结构以及定义在该结构上的操作及操作实现三个方面的内容.

基本概念和常用术语

数据：数据是描叙客观事物的数值、字符以及能输入机器且能被处理的各种字符的集合，

即计算化的信息。

数据元素：数据元素也称为结点，它是组成数据的基本单位，是一个数据整体中相对独立的单元。

字段：字段是构成数据的最小单位。

数据对象：在数据结构中，将性质相同的数据元素的集合称为数据对象，它是数据的一个子 集。

数据结构：由某一数据元素集合及该集合中所有数据元素之间的关系组成。具体来说，数据结构包含3个方面的内容，即数据的逻辑结构、数据的存储结构和对数所施加的操作。

根据数据结构中元素之间的结构关系的不同特征，通常将数据结构分为如下四种基本结构：
（1）、集合结构(set)::数据元素的有限结合。（2）、线性结构或者称为序列：：数据元素的有序结合。（3）、树形结构(tree)::树的层次结构，树中数据元素之间存在一对多的关系。（4）、图形结构：：：图中数据元素之间的关系是多对多。

逻辑结构

《结点和结点之间的逻辑关系称为数据的逻辑结构。》

(1)、线性结构。元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。

（2）、非线性结构。元素之间为一对多或多对多的非线性关系，元素可有多个直接前驱或多个直接后继。

（3）、集合结构。元素之间无任何关系，元素的排序无任何顺序。

存储结构

《数据的逻辑结构是独立于计算机的，它与数据在计算中的存储无关，要对数据进行处理，

就必须将数据存储在计算机中。数据在计算机中的存储方式称为 数据的存储结构。数据的

存储结构主要有4种。》

树《一对多》

《树形结构是计算机算法中最重要的非线性数据结构，其中以树和二叉树最为常用，它可以很好地描述具有分支关系和层次特性的对象，同时也是具有层次关系的数据在计算机中的表示提供了一种自然的表示方法。》

2.1 树的基本概念

树(Tree)是由n(n>=0)个结点组成的有限集合。n=0的树称为空树；n>0的树即为任意一颗非空树。

2.1.1 树的逻辑表示方法

(1)、直接表示法

(2)、嵌套集合表示法

(3)、凹入表示法<似文档目录>

(4)、广义表表示法

2.1.2 树的基本术语

1)、结点的度(degree)-----------指结点中所拥有的子树的个数。

(2)、树的度--------------是指树中各结点的度的最大值。《结点的度的最大值》

(3)、结点的层次(level)---在树中根节点的层次为1,其余任一结点的层次等于其双亲结点的层次加1.

(4)、树的深度(depth)------树中结点的最大层次称为树的深度，又称高度。

2.2 二叉树的概念和性质

2.2.1 定义

二叉树(binary tree)是指树的度最大为2的有序树。它是一种最简单、最重要的树，在计算机领域有着广泛的应用。

2.2.2 二叉树的性质

性质1：在一棵非空的二叉树的第i层上，最多有2^i-1次方个结点(i>=0)。

性质2：一棵深度为K的二叉树，最多具有2^K-1个结点(K>=1)。

性质3：对任意一棵非空二叉树，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。

满二叉树：一棵深度为K且含有2^k-1个结点的二叉树称为满二叉树。

完全二叉树：一个深度为k,有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序编号，如果编号为i(1<=i<=n)的结点与满二叉树中编号为i的结点在二叉树中位置相同，则称此二叉树为完全二叉树。

性质4：具有n个结点的完全二叉树的深度为|log2N|+1.

性质5：如果对一棵有n个结点的完全二叉树(其深度为|log2N|+1)的结点按层次编号（从第一层到第|log2N|+1层，每层从左到），则对任一结点i(1<=i<=n),有如下性质：

(1)

3 图《多对多》

3.1 图的定义

图(graph)是由非空的顶点集合和一个描述顶点之间的关系-----边(或者弧)的有限集**

合组成的一种数据结构。

3.2 图的相关术语

无向图：没有方向。
有向图：有方向，射线。
无向完全图：有n(n-1)/2条边的图<n为顶点数>。*
有向完全图：有n(n-1)条边的图<n为顶点数>。*
稀疏图和稠密图：由顶点引发边的多少来判断。
顶点的度，《入度，出度相对于有向图来说》：无向图顶点的度----引发的线段数

有向图顶点的度<TD>----=入度<ID>+出度<OD>
权和网：权值，边或者弧带有权值的图形成为网。
**路径和路径长度：

路径
由顶点和相邻顶点偶对构成的边所形成的序列 路径长度------连接顶点的轨迹的权值相加。
回路：从顶点回到顶点形成的闭合环形。
子图：图的部分。
连通图和连通分量：《连通图》：每顶点都能与其余顶点相连想成强连通图和强连通分量：《强连通图》---有向图，双向连接的连通图 《强连通分量》：把不是强连通图拆分成多个子强连通图。**
生成树：它必包含且仅包含G的n-1条边。《多一条：形成了回路；少一条：非连通》
生成森林。

3.3 图的存储结构

3.3.1 邻接矩阵存储结构

形式：
A[i][j]=@1: 1------代表两顶点存在边
=@2：0----代表两顶点不存在边

1：无向连接矩阵图

特点：对称分布
顶点的度：行中非零点的个数。

2：有向连接矩阵图
特点：一般不是对称分布，仅当它为完全有向图时对称。非零点的个数：行中非零点的个数代表出度。
列中非零点的个数代表入度

3：无向连接矩阵网

带权图，矩阵中的1用权值替换，0用无穷值替换。

4：有向连接矩阵网

带权图，矩阵中的1用权值替换，0用无穷值替换。

3.3.2 邻接表存储结构

相对于稀疏图来说，是为了节约存储空间，引入了指针

1：无向图邻接表
将每一顶点连接的线段转换为一个单链表。

顶点的度为：分得的段数.<节点数>

矩阵大小:n^2

2：有向图邻接表

将每一顶点连接的线段转换为一个单链表。
只关心出度。

如果要关心入度则引入：有向图逆邻接表

3: 延伸

延伸：对于一个具有n个顶点和e条边的无向图，若采取邻接表表示，则表头向量的大小为:n, 所有邻接表中的结点总数是:2e

4.4 栈和队列

1:栈的定义《先进后出》------是限定只能在表的一端进行插入和删除操作的线性表。(栈顶<允许插入和删除的一端>，栈底<不允许插入和删除的一端>).
分为：顺序栈和链栈。

2：***顺序栈，的定义，初始化，入栈，出栈，取栈顶元素操作，判断空操作,置栈空操作。

3：多<双>栈共享(邻接空间)

4：链栈<涉及到指针>:栈也可以采用链式的存储结构表示，这种结构的栈简称为链栈。
链栈的操作:

• 1：分配节点空间
• 2:数据域
• 3:指针域
• 3:顶指针节点指向》

5:队列---《先进先出，对其操作时：队尾插入，对头删除。》:是一种限定性的线性表，它只允许在表的一端插入元素，而在表的另一端删除数据。
《队列分为:顺序队列和链队列》

6：顺序队列：队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也必须用一个向量空间来存放当前队列中的元素。
由于队列的对头和队尾的位置是变化的，因而要设置两个指针front和rear,分别用于指示对头元素和队尾元素在向量空间的位置。
(特殊说明：指针front和rear初始化均应设置为0；在非空队列里，头指针始终指向对头元素，而为指针始终指向队尾元素的下一个位置)
为了防止“假溢出现象”引入-------循环队列。
------循环队列（在front==rear的情况下）是为空还是队列已满：两种方法--：
《
方法一:牺牲存储空间。判断队列“满”的条件为(rear+1)MAXSIZE=front。
方法二：设置一个标志变量的方法。（标志tag=0表示最后的一次操作是出队，tag=1表示最后的一次操作是入队）---判断队空的条件为:front==rear && tag==0
判断队满的条件为:front==rear && tag==1。
》

7：链队列--队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，
为此再添加一个为指针，指向链表上的最后一个节点。于是，一个链队列由一个头指针和一个尾指针唯一确定。**