**章    概论

算法+数据结构=程序

从宏观上看，数据、数据元素和数据项实际上反映了数据组织的三个层次，数据可由若干个数据   元素组成，而数据元素又可由若干个数据项组成。

数据的逻辑结构是指数据元素之间的逻辑关系。

集合中任意两个结点之间都没有邻接关系，组织形式松散；

线性结构中结点按逻辑关系依次排列形成一条“链”，结点之间一个一个依次相邻接；

树形结构具有分支、层次特性，其形态像自然界中的树，上层的结点可以和下层多个结点相   邻接，但下层结点只能和上层的一个结点相邻接；

图结构较复杂，其中任何两个结点都可以相邻接。

*二章    线性表

线性表（Linear List）是一种线性结构，它是由 n（n>0）个数据元素组成的有穷序列。

线性表的顺序存储：将表中的结点依次存放在计算机内存中一组连续的存储单元中，一般使用数   组来表示顺序表。

顺序表的插入与删除：元素的移动次数不仅与顺序表的长度 n 有关，还与插入的位置 i 有关。

线性表的链接存储：各个结点在内存中的存储位置并不一定连续，可存放在内存的不同位置。   5.单链表的插入：p->next=q->next 和 q->next=p 两条语句的执行顺序不能颠倒。

6 单链表上的删除：p=q->next;Q->next=p->next;free (p); 7.双向循环链表的删除：

（1）p->prior->next=p->next;    //p 前驱结点的后链指向 p 的后继结点

（2）p->next->prior=p->prior;   //p 后继结点的前链指向 p 的前驱结点

（3）free (p) ;    '    //释放的空间8.双向循环链表的插入：

（1）t 一〉prior=p;

（2）t->next=p->next；

（3）p->next->prior=t；

（4）p->next=t；

*三章    栈、队列和数组

栈的概念：栈是运算受限的线性表，这种线性表上的插入和删除运算限定在表的某一端进行。允   许进行插入和删除的一端称为栈**，另一端称为栈底。不含任何数据元素的栈称为空栈。处于栈**位   置的数据元素称为栈**元素。

栈的运算特点：后进先出。

栈的插入和删除操作分别称为进栈和出栈。

双栈满的条件：top1+1=top2（假设 top1<top2） 5.栈的简单应用与递归：函数调用应用栈

顺序队列的入队操作：SQ.rear=SQ.rear+1;SQ.data[SQ.rear]=x;

出队操作：SQ.front=SQ.front+1;

循环队列的入队操作：SQ.rear=(SQ.rear+1)%maxsize;SQ.data[SQ.rear]=x;

出队操作：SQ.front=(SQ.front+1)%maxsize;

循环队列满条件：（（CQ.rear+1）%maxsize==CQ.front）成立队列空条件：（CQ.rear==CQ.front）成立

矩阵的压缩存储：针对一些有许多值相同的元素或零元素的高阶矩阵，为了节省空间，对这类矩阵采用多个值相同的元素只分配一个存储空间，零元素不存储的策略，这一方法称为矩阵的压缩存储。

特殊矩阵：n 阶的对称矩阵和三角矩阵占用存储空间大小为：

（1）对称矩阵。若一个 n 阶方阵 A 中的元素满足下述条件：n(n+1)/2 11.稀疏矩阵的三元组表示法：

（i,j,a_ij）,i 表示行序号，j 表示列序号，a_ij 是非零元素的值。

*四章    树和二叉树

树的概念：可为空，若不空，左右子树互不相交。

叶子：度为 0 的结点

二叉树的概念：二叉树(Binary Tree)是 n(n≥0)个元素的有限集合，该集合或者为空，或者由一个根及两棵互不相交的左子树和右子树组成，其中左子树和右子树也均为二叉树。

二叉树的性质：

二叉树* i（i≥1）层上至多有 2i1 个结点。

深度为 k（k≥1）的二叉树至多有 2k 1 个结点。

对任何一棵二叉树，若度数为 0 的结点（叶结点）个数为 n₀，度数为 2 的结点个数为 n₂，则n₀=n₂+1。

含有 n 个结点的完全二叉树的深度为 log2n +1。

完全二叉树结点编号关系：编号 i 的双亲为i / 2 ，左孩子为 2*i，右孩子为 2*i+1

二叉树的顺序存储：用一维数组来实现。对非完全二叉树不成立。如果需要顺序存储非完全二叉   树，首先必须将其转化为完全二叉树，可增设若干个虚拟结点。但这种方法造成了空间的浪费。

二叉树的链式存储：二叉树有不同的链式存储结构，其中较常用的是二叉链表与三叉链表。

每个二叉链表还必须有一个指向根结点的指针，该指针称为根指针。对二叉链表的访问只能从根   指针开始。

二叉树遍历的递归实现：

先序遍历：根-左-右

中序遍历：左-根-右

后序遍历：左-右-根

二叉树的层次遍历：二叉树的层次遍历是指从二叉树根结点的这一层开始，逐层向下遍历，在每   一层上按从左到右的顺序对结点逐个访问。层次遍历可用队列来实现。

树的存储结构：

（1）孩子链表表示法；（2）带双亲的孩子链表表示法。；（3）孩子兄弟链表；（4）双亲表示法。   孩子兄弟链表的结构形式与二叉链表完全相同，但结点中指针的含义不同。

树、二叉树、森林的关系：

树（森林）转化成二叉树：①左孩子=左孩子；②兄弟=右孩子。

二叉树转换成树（森林）：①左孩子=左孩子；②右孩子=兄弟。

森林的遍历：

森林有两种遍历方法：先序遍历和中序遍历

对森林转换成的二叉树分别进行先序遍历和中序遍历，可以分别得到与该森林的先序序列和中序   序列相同的序列。

分类与判定树：用于描述分类过程的二叉树称为判定树。

哈夫曼树的构造：两个较小的结点构造新结点。   n 个结点构成的哈夫曼树共有 2n-1 个结点。

哈夫曼编码：左 0 右 1

*五章    图

任何两点之间都有边的无向图称为无向完全图。一个具有 n 个**点的无向完全图的边数为C2 =nn-1/2 。任何两点之间都有弧的有向图称为有向完全图。一个具有 n 个**点的有向完全图的弧数为P2 =nn-1 。

含有 n 个结点的图的生成树的边的数目一定为 n-1，若大于，说明有环。

图的存储结构

邻接矩阵：无向图的邻接矩阵是一个对称矩阵。

邻接表：有向图邻接表的表长等于点的出度，逆邻接表的表长等于点的入度。

图的遍历：遍历图的基本方法有两种：深度**搜索和广度**搜索。

连通图的深度**搜索：深度**搜索遍历类似于树的先序遍历。（注意：可回退）

连通图的广度**搜索：广度**搜索遍历类似于树的按层次遍历的过程。

图的应用：

较小生成树

①较小生成树的概念：一个图的较小生成树是图所有生成树中权总和较小的生成树。

②构造较小生成树的 Prim 算法：从一个**点出发添加权值小的边。

③构造较小生成树的克鲁斯卡尔（Kruskal）方法：从多有边当中选择权值较小的边。

单源较短路径（Dijkstra 算法）

拓扑排序：

前提条件：完成拓扑排序的前提条件是 AOV 网中不允许出现回路。步骤：

图中选择一个入度为 0 的**点，输出该**点；

从图中删除该**点及其相关联的弧，调整被删弧的弧头结点的入度(入度减 1);

重复执行(1)、(2)直到所有入度为 0 的**点均被输出，拓扑排序完成，或者图中再也没有入度

为 0 的**点。