数据结构学习笔记（全）_数据结构笔记

目录

第一章 绪论

基本概念

第二章 线性表

第三章 栈与队列

1.栈

2.队列

循环队列

第四章 树

1.树的概念

2.二叉树

3.遍历二叉树

4.树和森林

5.最优二叉树

第五章 图

图的相关概念

图的储存结构

一、数组表示法（邻接矩阵表示）

二、邻接表：图的链式存储结构

图的遍历

深度遍历

广度遍历

图的最小生成树

普里姆算法

克鲁斯卡尔算法

第六章 查找

1.静态查找表

无序表的查找：顺序查找

有序表的查找：折半查找

索引顺序表的查找：分块查找

2.动态查找表

二叉排序树的查找

二叉排序树的存储与删除

3.哈希表

第七章 排序

1.插入排序

2.快速排序（重点）

3.选择排序

简单选择排序（不是重点）

堆排序（重点）

---

第一章 绪论

基本概念

数据的逻辑结构：数据之间的结构关系，是具 体关系的抽象

数据元素之间存在四种基本逻辑结构：集合（无关系）、线性结构（一对一）、树形结构（一对多）、图状结构（多对多）

数据的存储结构：顺序存储结构、链式存储结构

第二章 线性表

四个“唯一”：

◆ 存在唯一的被称作“第一个”的数据元素;

◆ 存在唯一的被称作“最后一个”的数据元素;

◆ 除第一个外，集合中的每个数据元素均只有 一个前驱;

◆ 除最后一个外，集合中的每个数据元素均只 有一个后继

线性表分为顺序表和链式表

顺序表直接插入删除，链式表插入删除需要有一定的顺序

第三章 栈与队列

1.栈

栈是限定仅能在表尾一端进行插入、删除操作的线性表，能进行插入和删除的一端称为栈顶，另一 端称为栈底。 称插入操作为进栈，删除操作为出栈。进 栈出栈操作只能在栈顶进行。

空栈 top = base ；栈满 top-base = stacksize (无可分配空间)

2.队列

队列是限定仅能在表头进行删除，表尾进行 插入的线性表。能进行插入的一端称为队尾，能进行删除的 一端称为队头。 称插入操作为入队，删除操作为出队。

设两个指针：front,rear。 rear指向队尾元素的下一个 位置；front指向队头元素。 初值 front= rear= 0。

队空条件：front==rear；            

入队列：Q.base [ rear ] = e;rear++;                  

出队列：e =Q.base[ front ];front++;

循环队列

将队列的头尾连接，利用“求模”运算，另外设一个标志以区别队空、队满 。少用一个元素空间： 队空：front==rear 队满：(rear+1)%M==front；

第四章 树

1.树的概念

树是n个结点的有限集合，在任一棵非空树中： （1）有且仅有一个称为根的结点。 （2）其余结点可分为若干个互不相交的集合，且这 些集合中的每一集合本身又是一棵树，称为根的子树。

逻辑结构： 1）树是一种分支结构：（除了一个称为根的 结点外）每个元素都有且仅有一个直接前趋， 有且仅有零个或多个直接后继。         2）除根外的其它结点，都存在唯一一条从根 到该结点的路径；

树的表示： 1）图示表示         2）广义表表示: (A(B(E, F), C(G), D(H, I, J)))

关于树的基本术语：

结点: 数据元素+若干指向子树的分支。

结点的度：分支的个数。

树的度：树中所有结点的度的最大值。

叶子结点：度为零的结点。

分支结点：度大于零的结点。

（从根到结点的)路径： 由从根到该结点所经 分支和结点构成。

结点的层次: 假设根结点的层次为1，第l 层的结 点的子树根结点的层次为l+1。

树的深度：树中叶子结点所在的最大层次。

森林：是 m(m≥0) 棵互不相交的树的 集合。

任何一棵非空树都是一个二元组 Tree = （root，F） 其中：root 称为根结点，F 称为子树森林。

有序树：子树之间存在明确的次序关系的树。

无序树：不考虑子树的顺序

2.二叉树

二叉树有五种基本形态：

二叉树的特点：

1）二叉树中每个结点最多有两棵子树——结点的度 小于等于2。

2）左、右子树不能颠倒——有序树。

二叉树的性质：

1）在二叉树的第 i 层上至多有2 i-1 个结点(i≥1)

2）深度为k的二叉树上至多含2 k -1个结点(k≥1)

3）对任何一棵二叉树，若它含有n0 个叶子结 点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1

二叉树的特殊类型：

满二叉树：指的是深 度为 k 且含有 2 k -1 个 结点的二叉树。

完全二叉树：树中所 含的 n 个结点和满二 叉树中编号为 1 至 n 的结点一一对应。

完全二叉树的性质：

具有 n 个结点的完全二叉树的深度为 | log2n | +1。

若对含 n 个结点的完全二叉树从上到下且从左至 右进行 1 至 n 的编号，则对完全二叉树中任意一个 编号为 i 的结点：

(1) 若 i=1，则该结点是二叉树的根，无双亲, 否 则，编号为 i/2 的结点为其双亲结点；

(2) 若 2i>n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；

(3) 若 2i+1>n，则该结点无右孩子结点，否则， 编号为2i+1 的结点为其右孩子结点。

3.遍历二叉树

遍历的基本概念： 1）遍历：按某种搜索路径访问二叉树中的每个结点， 而且每个结点仅被访问一次。    2）访问：含义很广，可以是对结点的各种处理，如 修改结点数据、输出结点数据等

二叉树的先序遍历（DLR） A F G D E B C 若二叉树非空 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树

二叉树的中序遍历（LDR） A F G D E B C 若二叉树非空 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。

二叉树的后序遍历（LRD） A F G D E B C 若二叉树非空 （1）后序遍历左子树； （2）后序遍历右子树。 （3）访问根结点；

4.树和森林

树的存储结构：孩子兄弟表示法（左孩子、右兄弟），用二叉链表作为树的存贮结构。

森林与二叉树的转换：将森林中树的根看成兄弟，用树与二叉树的转 换方法，进行森林与二叉树转换。

树的遍历：

先根（序）遍历：先访问树的根结点，然后依 次先根遍历根的每棵子树。

后根（序）遍历：先依次后根遍历每棵子树， 然后访问根结点。

按层次遍历：先访问第一层上的结点，然后依 次遍历第二层，……第n层的结点

森林的遍历：要先转换为二叉链表，再以二叉树的方式遍历。

树、森林与二叉树遍历的关系

5.最优二叉树

路径：从一个祖先结点到子孙结点之间的分支构成这 两个结点间的路径；

路径长度：路径上的分支数目称为路径长度；

结点的权：给树中结点所赋的具有物理意义的值；

结点的带权路径长度：从根到该结点的路径长度与该 结点权的乘积；

树的带权路径长度=树中所有叶子结点的带权路径之 和；通常记作 WPL=  wi * Li。

哈夫曼树：假设有n个权值（w1 ,w2 , … , wn），构造 有 n 个叶子结点的二叉树，每个叶子结点有一个 wi 作为它的权值。则带权路径长度最小的二叉树称为哈 夫曼树

构造哈夫曼树：总选取最小的两个权值的根结点，将其作为子树构成二叉树，重复以上步骤

Huffman编码（数据通信用的二进制编码）： 用赫夫曼树可以构造一种不等长的二进制编码， 并且构造所得的赫夫曼编码是一种最优前缀编码， 即，使得所传电文的总长度最短。 思想：根据字符出现频率编码，使电文总长最 短。 编码：根据字符出现频率构造Huffman树，然 后将树中结点引向其左孩子的分支标为“0”，引向 其右孩子的分支标为“1”；每个字符的编码即为从 根到每个叶子的路径上得到的0、1序列

第五章 图

图的相关概念

图的定义：图G是由两个集合V(G)和 E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无 序对或有序对。

图的分类：有向图和无向图，有向图的边是有指向的，而无向图没有

图的基本术语：

1、邻接点及关联边 邻接点：边的两个顶点 关联边：若边e= (v, u), 则称顶点v、u 关联边e

2、顶点的度、入度、出度

顶点V的度 = 与V相关联的边的数目

在有向图中：

顶点V的出度 = 以V为起点有向边数 

顶点V的入度 = 以V为终点有向边数

顶点V的度 = V的出度+V的入度 设图G 的顶点数为 n，边数为 e 图的所有顶点的度数和 = 2*e 

连通图（强连通图）：在无（有）向图 G=< V, E > 中，若对任何两个 顶点 v、u 都存在从 v 到 u 的路径，则称G是连通 图（强连通图）

子图：父图完全包含子图的顶点和边

连通分量（强连通分量）：无（有）向图的极 大（强）连通子图。 极大（强）连通子图：该子图是（强）连通子图， 若再将G的任何不在该子图中的顶点加入，子图就 不再（强）连通。连通分量只对顶点数和必须连通有要求，对边的数量没有要求。

         

生成树：包含无向图 G 所有顶点的极小连通子图称为G生 成树。 极小连通子图意思是：该子图是G的连通子图， 在该子图中删除任何一条边，子图不再连通

图的储存结构

一、数组表示法（邻接矩阵表示）

邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵：

二、邻接表：图的链式存储结构

1.无向图的邻接表    顶点：通常按编号顺序将顶点数据存储在一维数组 中； 关联同一顶点的边：用线性链表存储。

2、有向图的邻接表     顶点：用一维数组存储（按编号顺序） 以同一顶点为起点的弧：用线性链表存储

图的遍历

深度遍历

1.连通图的深度遍历：优先访问未被访问的结点，进行深度优先的遍历（访问顺序可以不唯一）

2.非连通图的深度遍历（非重点）：首先将图中每个顶点的访问标志设为 FALSE，之后搜索图中每个顶点，如果未 被访问，则以该顶点为起始点，进行深度 优先搜索遍历，否则继续检查下一顶点。

广度遍历

        从图中的某个顶点V0出发，并在访问此顶点之后 依次访问V0的所有未被访问过的邻接点，之后按这 些顶点被访问的先后次序依次访问它们的邻接点，直 至图中所有和V0有路径相通的顶点都被访问到。

        若此时图中尚有顶点未被访问，则另选图中一个 未曾被访问的顶点作起始点，重复上述过程，直至 图中所有顶点都被访问到为止。

图的最小生成树

普里姆算法

先选择一个顶点（无要求），选择权值最短的边，将其与一个新的顶点连接，并将其看为一个新的整体，重复进行”选择权值最短的边，将其与一个新的顶点连接“的操作直至所有顶点相连。

克鲁斯卡尔算法

总是选择图中权值最小的边，将边两端的顶点相连，且每次连接必须有新的顶点，重复以上过程直至所有顶点相连。

第六章 查找

查找的主要操作：比较

1.静态查找表

无序表的查找：顺序查找

静态查找表是用线性表表示的，可以用顺序表和线性链表两种方式表达，静态查找表的查找方式为顺序查找。

顺序查找的特点：无排序要求；存储结构为顺序或链式；平均查找长度为（n+1）/2.

有序表的查找：折半查找

查找方法：折半查找（二分查找）

查找过程：先确定待查记录所在的范围（区间）， 然后逐步缩小范围直到找到或找不到该记录为止。

查找low-mid之间的元素，如果查找到则将high缩小至mid，若没有则要查找的元素在高位，将low提高到mid，以此往复，当low==mid==high时找到所查元素，若low>high则该集合中没有所查元素即查找失败。

折半查找的特点：要求元素按关键字有序；存储结构为顺序；平均查找长度为 log2 (n+1)-1

索引顺序表的查找：分块查找

查找表的组织：分块索引，除表本身以外，尚 需建立一个“索引表”。

查找方法：查找索引表；在数据块内顺序查找

2.动态查找表

二叉排序树的查找

查找规则：比根节点大则向右子树查找，比根节点小则向左子树查找，直到查找到相等的值为止，若最终查找结果为空，则查找失败。

二叉排序树的存储与删除

插入：比根节点大则向右子树查找，比根节点小则向左子树查找，当遇到NULL空树时则插入。

删除：删除一个根节点s，若只有一个孩子，则孩子直接继承被删除根节点的位置。若有两个孩子，其右孩子为q，则将左孩子的最右边结点p删除，并将p放在被删除的根节点的位置，如果被删除的p有左子树，则直接继承在p的位置。

3.哈希表

在记录的存储地址和它的关键字之间建立一个确 定的对应关系，一次存取就能得到所查元素的查找 方法。即：通过简单计算直接得到数据的地址。

哈希(Hash)函数是一个映象，即：将关键字 的集合映射到某个地址集合上。

映象原则：地址集合的大小不超出允许范围。

哈希函数：addr(ai )=H(ki )

◆ ai是表中的一个元素

◆ addr(ai )是ai的存储地址

◆ ki是ai的关键字。

第七章 排序

排序的主要操作：比较、移动

1.插入排序

直接插入排序：按照顺序插入（较为简单）

折半插入排序：缩小范围，找到需要插入元素的位置。

交换排序：冒泡排序，将待排记录中两两记录的关键字进行 比较，若逆序则交换位置。

2.快速排序（重点）

需要插入的数x总是与离它最远的数相互比较。

1.在最右边创建一个虚拟的x（如49），将 j 指针指向该虚拟x

2.原所需插入数x在指针 i ，从 j 指针开始从右往左查找第一个比x小的数y（如27<49）并与其交换位置，并将 j 指针移动到y原本的位置。移动后所需插入数x在指针 j 。

3.原所需插入数x在指针 j ，从 i 指针开始从左往右查找第一个比x大的数z（如65>49）并与其交换位置，并将 i 指针移动到z原本的位置。移动后所需插入数x在指针 i 。

4.循环第二第三步，直到  i==j  则此时所需插入数 x 在最终位置。

3.选择排序

简单选择排序（不是重点）

堆排序（重点）

堆是一棵完全二叉树，如果满足下面的条件，则称其为堆： 根结点关键字 >= 左、右孩子结点的关键字； 左、右子树也是堆。

    

大根堆和小根堆的区别在于，在根、左孩子、右孩子之中，大根堆以最大数据作为作为根的数据，小根堆以最小数据作为根的数据。

堆排序的主要操作：筛选操作

筛选操作：在一个无序的完全二叉树中，在根、左孩子、右孩子之中，以特点方式（比如最大最小）选取数据并与根数据交换。

    -->        -->      -->

建堆：从堆的最后一个分支结点（第n/2（取整）个元 素）开始到根结点 ，依次进行筛选，最 终将之调整为堆。对每一个结点都进行一次筛选操作

     -->         -->    -->

   -->        -->      -->

   -->   

堆排序的实现：循环一下三步：将堆顶元素与堆最后的元素互换；输出堆最后的元素（删除）；将其余的元素重新筛选成堆。

  -->循环这一步，就能将整个堆输出了