数据结构

数据结构是计算机存储、组织数据的方式。是指相互之间存在一种或多种特点关系的数据元素的集合。

通常情况下，精心挑选的数据结构可以带来更高的运行或者存储效率

• 栈
• 队列
• 链表
• 数组

数据的三个层次：数据，数据元素，数据项

数据：是信息的载体，是描述客观事物的数，字符，以及能输入到计算机中，被计算机程序识别和处理的符号的集合

数据元素是数据的基本单位

数据项是数据的最小不可分割单位

加入头结点的优点:

有头结点后，插入和删除的算法就统一了，不再需要判断是否在第一个元素之前插入和删除第一个元素

循环单链表的优点,从任一结点出发都可以访问到所有元素

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合

数据结构包括三方面内容：逻辑结构、存储结构、数据的运算

逻辑结构:是指数据元素间的逻辑关系，从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。

​ 逻辑结构被分为线性结构和非线性结构

​ 集合，数据元素同属于一个集合

​ 线性结构：数据元素间只存在一对一的关系

​ 树形结构：数据元素间存在一对多的关系

​ 图形或网状：数据元素间存在多对多的关系

存储结构：数据元素在计算机中的表示

​ 存储结构主要有：顺序存储，链式存储，索引存储，散列存储

​ 顺序存储：逻辑上相邻的数据元素物理上也相邻

​ 链式存储：借助指示元素存储地址的指针来表示数据元素间的逻辑关系

​ 索引存储：在存储元素信息时，还建立附加的索引表

​ 散列存储：根据元素的关键字直接计算出该元素的存储地址

算法的特性：有穷性，可行性，确定性，零个或多个输入，一个或多

个输出

抽象数据类型的定义：取决于它的一组逻辑特性，*与它在计算机内部如何表现和实现*无关，内部结构如何变化，只要它的*数学特性*不变，不影响其他外部使用

*数据结构是一门*：研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象操作等的学科

*评价算法*：正确性，易读性，健壮性，时空效率

*栈*：是只准在一端进行插入和删除操作的线性表，允许插入的一端叫栈顶，另一端叫栈底，最后插入的元素最先删除，后进先出

*队列*：允许在一端插入在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入的元素先离开，先进先出

*循环队列*：顺序存储结构的一维数组表示队列，由于队列的性质容易造成假溢出。循环队列是解决这种现象的方法。通常把一维数组看成收尾相连的环。通常在循环队列中采用“牺牲一个单元”或“做标记tag”或采用“计数器记录总数”

数组

数组定义

狭义定义：一组数，用来存储数据的集合

广义定义：通过连续的存储空间，存储相同类型元素的集合。

内存存储：有序 ---> 索引：递增有序

存储内容：固定 ---> 随机访问：高效

元素地址=首元素地址+(索引*元素宽度)

数组定义

数组声明

int[] arrs;
String strs[];   //不推荐

数组的初始化

1. 静态初始化：

public static void main(String[] args) {
        int[] arrs = new int[] {
            1,2,3,4,5,6,7
        };
        String[] str = {"数组","队列","栈","图","树","堆"};
        System.out.println(arrs);
}

结果：[I@5cad8086

class对象名称+@+hashcode值

2. 动态初始化

public static void main(String[] args) {
    //声明一个能够存储5个元素的int类型数组
    int[] arrs = new int[5];
}

常见问题：

a：声明数组的时候，动态初始化前，不指定数组长度

​ int arrs = new int[];l

b：给数组重新赋值的时候，通过{}创建数组对象

​ int[] arrs = new int[]{1,2,3}； //用 arrs = {}; 这里会编译报错

栈

1. 初始化

   void InitStack(SqStack &S){
       S.top = -1;  //初始化栈顶元素
   }
   

2. 判栈空

   bool StackEmpty(SqStack S){
       if(S.top==-1)  			//栈空
           return true;
       else					//栈不空
           return false;
   }
   

3. 进栈

   bool Pop(SqStack &S,ElemType &x){
       if(S.top==MaxSize-1)	//栈满，报错
           return false;
       S.data[++S.top]=x;		//指针先加1，再入栈
       return true;
   }
   

4. 出栈

   bool Pop(SqStack &S,ElemType &x){
       if(S.top==-1)		//栈空报错
           return false
       x=S.data[S.top--]   //先出栈，指针再减1
       return true;
   }
   

5. 读栈顶元素

   bool Pop(SqStack &S,ElemType &x){
       if(S.top==-1)		//栈空报错
           return false
       x=S.data[S.top]   //x记录栈顶元素
       return true;
   }
   

*共享栈：*top0=-1表示0号栈空，0号栈进栈是top0先加1再赋值

top1=Maxsize时1号栈空，1号栈进栈时top1先减1再赋值

top1-top0=1时栈为满

作用：更有效地利用存储空间

*链栈的存储结构描述*

队列

循环队列

1. 牺牲一个存储单元

2. 增设计数器

队空Q.size==0

队满Q.size==MaxSize

3. tag标志

   tag0因删除致Q.frontQ.rear队空

   tag1因插入致Q.frontQ.rear队满

队列的链式存储

树

概述：

树中结点数等于所有结点的度数加1

树的路径长度是从树根到每个结点路径长度的总和

树的性质：

二叉排序树：一棵二叉树或者为空二叉树，或者是具有如下性质的二叉树，左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于根结点的关键字。左子树右子树又各是一棵二叉排序树

，中序遍历递增有序

平衡二叉树：树上任意结点的左子树和右子树的深度之差不超过1

树是一种逻辑结构

除根节点外，所有结点只有一个前驱

所有结点可以有零个或多个后继

度大于零的结点称为分支结点，又叫非终端结点

高度为h的m叉树的最小高度为㏒m(n(m-1)+1)向上取整

总结点数n=n0+n1+n2+...nm

总分支数B=1n1+2n2+...

总结点数=B+1

完全二叉树左孩子2i

右孩子2i+1

对于满二叉树和完全二叉树采用顺序存储比较合适

二叉树BiTree(BinaryTree)

顺序存储结构

链式存储结构

n个结点的二叉链表含有n-1个空链域

高度为h的二叉树只有度为0和2的结点，所包含的结点数至少为2h-1(每层两个结点，层数乘2减去根结点)最多为2^(h-1)

若i≤∟n/2，则i为分支结点，否则为叶结点

n个结点的正则二叉树中有(n+1)2个叶结点

度为m的哈夫曼树中，其叶结点个数为n,非叶结点个数为(n-1)/(m-1)¬

度为2的哈夫曼树有2n-1个结点

中序线索二叉树中，每一个非空的线索均指向其祖先

树的父链表法，其实就是用数组表示树的存储结构

当二叉排序树为单枝树时查找效率最低，引入平衡二叉树可以解决

后序线索二叉树需要借助栈

n个结点可以构造出1/(n+1)Cn！ 2n！种不同的二叉树。n个结点可以构造出不同的树的数量等于n-1

二叉树叶子结点个数为(n+1)/2 n个结点的树，分支结点的度为k,叶子结点个数(n+1)/k

分支结点为(n-1)/2

深度为k具有n个节点的完全二叉树 其编号最小的叶结点序号为∟2＾(k-2) ]+1

*树在计算机内的表示形式*，双亲链表表示法，孩子链表表示法，孩子兄弟表示法

*双亲表示法*

可以很快地找到结点双亲，求孩子需要遍历整个结构

*孩子链表表示法*

寻找子女十分方便，寻找双亲需要遍历整个结构

*孩子兄弟表示法*

存储灵活，可以方便地实现树转化为二叉树，易于查找孩子，找双亲比较麻烦

*引入二叉线索树的目的*：加快查找结点前驱或后继的速度

*线索二叉树的遍历*

*树之间相互转化*

森林转二叉树：先将每个森林都转化为二叉树，以第一颗树的根，为转化二叉树的根，将第一棵左子树作为转化后二叉树根的左子树，将第二棵树作为二叉树的右子树，第三棵树作为转化后根的右子树的右子树

含有n个结点的平衡二叉树最大深度为O(log2n)

哈夫曼树又称最优二叉树，特点：用的频率高的东西离自己近一些，频率少的离自己远一些

图

是一种网状数据结构，线性表，树可以为空，图不能为空

简单图，不存在重复边，不存在顶点到自身的边

*无向完全图：*任意两个顶点间都存在边

有n个顶点的无向完全图有n(n-1)/2条边

有向完全图：任意两个顶点间存在反向相反的两条弧n(n-1)条有向边

子图：图的一部分，若顶点集与原图相同称为生成子图

连通图：任意两个顶点都是连通的

无向图中的极大联通子图称为连通分量

n个顶点的无向图，边数只要大于n-1一定有环

极小连通子图：保证了连通又有着最少的边数

生成树：在极小连通子图的基础上，保证了包含图的全部顶点(一定没有环)

强连通图：任何一对顶点都是强连通的

强连通图n个顶点最少有n条边

有向图的强连通分量：极大强连通子图

连通图只能生成生成树，非连通图只能生成生成森林

无向图的全部顶点的度的和等于边的二倍，n个顶点e条边的度为2e

有向图顶点v的度等于入度和出度之和，有向图的全部入度出度之和相等，且等于边数

路径__回路 简单路径_--简单回路

路径：有顶点和相邻顶点序偶构成的边所形成的序列

存在回路的图不存在拓扑序列

n个顶点保证连通且边数最少(n-1)(n-2)/2+1

n个顶点的连通无向图至少有n-1条边，若少于n-1,则是非连通。连通有向图至少有n条边

空间复杂度O(|V|)

广度优先遍历若用邻接矩阵法为O(|V|^2)

若用邻接表法为O(|V|+|E|)

BFS可以解决无权图或权值相

同时的单源最短路径

BFS借助队列+辅助数组

DFS借助栈+辅助数组

• 最小生成树 Prim算法 Kruskal算法

性质：①最小生成树不唯一，树形不唯一(以为有权值相同的情况)

唯一的情况，只有n-1条边，所有权值各不相同

②最小生成树的权值之和总是唯一的，并且是最小的

③最小生成树的边数等于顶点数减1

*贪心法*

Kruskal算法

时间复杂度O(|E|log|E|)

适合于边稀疏而顶点多的图

• 最短路径

一是单源最短路径，求图中某一顶点到其他各顶点的最短路径，Dijkstra时间复杂度为O(|V|^2)

迪杰斯特拉算法按路径长度递增的次序产生最短路径

二是求每对顶点间的最短路径,Floyd时间复杂度为O(|V|^3)

拓扑排序(AOV网)，有向无环图

AOV网用每个顶点表示一个活动

AOE网用每个有向边表示一个活动(开销或时间)

性质①只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始

②只有在进入某顶点的各有向边所代表的活动都已经结束时，该顶点所代表的时间才能发生

关键路径

事件的最早发生时间(关键路径长度)和最迟开始时间

最早发生时间找最大值，从汇点开始按拓扑排序序列顺序开始找

最迟发生时间，由源点逆推到汇点，找出边最小值，源点的最迟发生时间等于它的最早发生时间，选最小值

活动的最早开始时间和最迟开始时间

活动ai的最早开始时间

先列出所有事件的最早开始时间

依次找边集弧尾端点的事件的最早开始时间

活动ai的最迟开始时间

先列出所有事件的最迟开始时间

网中的关键路径并不唯一，且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工期 只有加快那些包含在*所有*关键路径上的关键活动才能达到缩短工期的目的。

若一个有向图的顶点不能排在一个拓扑序列中，则该有向图定含有顶点数目大于1的强连通分量

若有向图具有有序的拓扑序列，邻接矩阵必为三角，若题目中不给有序，邻接矩阵则为一般

查找

查找表：用于查找的数据集合称为查找表，由同一类型的数据元素组成

静态查找表：无须动态地修改查找表

动态查找表：需要动态地删除，插入

关键字：数据元素中唯一表示该元素的某个数据项的值

静态查找：顺序查找，折半查找，分块查找

*顺序查找*(线性查找)主要用于在线性表中进行查找，关键字可以无序也可以有序

当Pi=1/n时，ASL成功=(n+1)/2 求和1/n(n-i+1) ASL不成功=n+1(表长加哨兵)

对无序线性表查找失败时要遍历整个线性表

对关键字有序线性表进行顺序查找不一定要遍历整个线性表(如果有n个成功结点，一定有n+1个失败结点)

有序不成功n/2+n/(n+1)

*折半查找*(二分查找)仅适用于有序的顺序表

*顺序查找*适用于查找顺序存储和链式存储，序列有序无序均可

折半查找只适用于顺序存储，要求序列一定有序

折半查找最坏要比较log2(n+1)向上取

平均查找长度为lod2(n+1)-1

时间复杂度度为O(log2n)

*分块查找*(索引顺序查找)吸取了顺序查找和折半查找各自的优点：将查找表分为若干子块，块内元素无序，块间有序。

①在索引表中确定待查记录所在的块，可以顺序或折半

②在块内顺序查找

k分查找，k叉树深度┕(logkn)┘+1比较次数也是┕(logkn)┘+1时间复杂度O(logkn)

*B+树B-树*

B树又称多路平衡查找树，B树中所有孩子结点的最大值称为B树的阶，通常用m表示。

具有n个关键字的m阶B树，应有n+1个叶结点

m阶B树的每个非叶结点至少有┌4/2┐-1个关键字，根结点至少有一个关键字，所以总共包含的关键字最少个数=(n-1)(┌4/2┐-1)+1

只有B+树支持顺序查找

散列函数：一个把查找表中的关键字映射成关键字对应的地址的函数

评价散列函数优劣的两个主要条件：计算简单，散列函数分布均匀

在散列函数中删除一个记录，在拉链法情况下可以物理地删除。但在开放地址法情况下，不能物理地删除，只能做删除标记。该地址可能是该记录的同义词查找路径上的地址，物理地删除就中断了查找路径

散列函数查找

装填因子α=n/m n是表中元素个数，m是表长

P取不大于表长的最大素数

散列表的平均查找长度依赖于散列表的装填因子α,并不直接依赖于n或m,α越大，表示记录越满，发生冲突的可能性越大

串是由零个或多个字符组成的有限序列

子串:任意两个连续的字符组成的子序列

串的存储结构

定长顺序存储表示

KMP算法，模式匹配时主串不会回溯，所以主串的指针不会变小

简单的模式匹配算法的时间复杂度O(nm)

KMP的时间复杂度O(m+n)

内部排序:在排序期间元素全部放在内存中的排序

外部排序:在排序期间元素无法全部同时存放在内存中，必须在排序过程中根据要求不断地在内外存之间移动

排序的稳定：经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变

插入类排序

*直接插入排序*

①设置监视哨V[0]临时保存代插入元素记录

②从后往前查找应该插入的位置

③查找与移动在同一循环中完成

空间角度需要一个辅助空间V[0]，空间复杂度为O(1)

平均总比较次数移动次数n^2/4

时间复杂度最好待排序列有序O(n)

最坏逆序O(n^2) 比较次数∑(2-n)i 移动∑(2-n)i+1

对于n个元素顺序表用直接插入排序最坏情况下比较n(n-1)/2,最好情况比较n-1

可能出现：最后一趟开始前，所有元素都不在最终位置上

稳定

适用范围，待排记录数目较少且基本有序

适用于顺序存储和链式存储

*折半插入排序*

直接插入和折半插入排序虽然都为O(n^2)但对于数据量较小的排序表，折半有更好的性能

*希尔排序*(缩小增量排序)(对直接插入排序的改进)

基本思想：先将待排序表分割成若干形如L[i,i+d,i+2d,i+3d...]的特殊子表 分别进行直接插入排序

希尔排序不会出现每趟排序都有一个元素被放置到最终位置上

希尔排序组内采用直接插入排序

交换类排序

*冒泡排序*(起泡排序)一次冒泡会将一个元素放置到它最终位置上

思想：从后往前或从前往后两两比较相邻元素值，若为逆序则交换，直到序列比较完

最好情况比较次数n(n-1)/2

移动次数3n(n-1)/2

冒泡排序排序趟数与初始序列有关

*快速排序*(一次划分会将一个pivort放置到它最终位置上)

基本思想：每次以当前表中第一个元素作为枢轴值来对表进行划分，比枢轴值大的元素向有移动，比枢轴值小的向左移动

空间复杂度最坏O(n)平均O(log2n)

快速排序在要排序数据基本有序时不太发挥其长处

就平均性能而言目前最好的内部排序方法是快速排序

对n个关键字进行快速排序，最大递归深度为n,最小递归深度为nlog2n

*选择排序*

*简单选择排序*

一趟排序后会将一个元素放置在最终位置上

简单选择排序的比较次数O(n^2),移动次数O(n)

*堆排序*

树形选择排序

在具有n个结点的堆中插入一个新元素的时间复杂度为O(log2n)删除一个元素的时间复杂度为O(log2n)

在含有n个关键|字的小根堆中，关键字最大的记录可能存在n/2+2中

构建n个记录的初始堆，其时间复杂度为O(n^2),对n个记录进行堆排序，最坏情况下时间复杂度为O(nlog2n)

堆支持删除和插入 删除堆顶元素时，先将堆的最后一个元素与堆顶元素交换，此时堆的性质破坏，对根结点进行向下调整

当插入元素时，将新结点放在堆末端

选择排序的比较次数与序列的初始状态无关，始终是n(n-1)/2

排序的稳定性：若待排序列中有两个相同元素，keyi和keyj,若经过一系列的排序后，keyi仍在keyj前面则说明该算法是稳定的，否则是不稳定的

直接选择，希尔，堆，快排都是不稳定的

希尔：当相同的关键字被划分到不同的子表时，可能会改变他们的相对次序，所以是不稳定的

快速排序：在划分算法中，若右端有两个相同的关键字时，且均小小于基准值的记录，则在交换到左端后，相对位置发生了变化

简单选择排序：在第i趟找到最小元素后，，和第i个元素交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变

堆排序：在进行筛选时，可能会把相同关键字的元素调整到前面

*归并排序和基数排序*