[数据结构与算法]预推免冲刺之数据结构（一）

一、什么是数据结构

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

2、结构包括逻辑结构和物理结构

• 逻辑结构
  • 集合：结构中的数据元素除了同属于一个集合的关系外，别无其他关系
  • 线性结构：结构中的数据元素只存在一对一的关系
  • 树形结构：结构中的数据元素存在一对多的关系
  • 图状结构和网状结构：结构中的数据元素存在多对多的关系
• 物理结构
  • 顺序存储结构：用一段连续的存储空间来存储数据元素，可以进行随机访问，访问效率较高。每个元素占用最小的存储空间。缺点是只能使用相邻的一整块存储单元,可能产生较多的外部碎片。
  • 链式存储结构：用任意的存储空间来存储数据元素，不可以进行随机访问，访问效率较低。

二、复杂度

1、时间复杂度

基本操作执行次数:T(n)

语句频度或时间频度：一个算法中的语句执行次数，记为T(n)。

渐进时间复杂度:O(f(n))

若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。

O的含义是T(n)的数量级

T(n)=O(f(n))——存在两个常量C和N，当n≥N时，有T(n)≤C*f(n)

【例】T(n)=5logn T(n)=O(logn)

2、空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

三、查找方法

1、静态查找

（1）顺序查找——O(n)

（2）折半查找/二分查找——O($lo{g}_{2}n$??)

要求查找表为顺序存储结构并且有序

代码

2、动态查找

（1）二叉排序树BST——O($lo{g}_{2}n$)~O(n)

二叉排序树为一颗二叉树，或者为空，或者满足如下条件：

• 如果它的左子树不为空，那么左子树上的所有结点的值均小于它的根结点的值
• 如果它的右子树不为空，那么右子树上的左右结点的值均大于它的根结点的值
• 根结点的左子树和右子树又是二叉排序树。

中序遍历二叉排序树便可得到一个有序序列

（2）平衡二叉树AVL——O($lo{g}_{2}n$)

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

3、哈希表——O(1)

哈希表又称为散列表，是根据关键字码的值直接进行访问的数据结构，即它通过把关键码的值映射到表中的一个位置以加快查找速度，其中映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希函数的构造方法

(1)除留余数法

取关键字被某个不大于哈希表长m的数p除后所得的余数为哈希地址。即：H(key)=key mod p,p<=m。(p的取值最好为素数)。

(2)随机法

采用一个伪随机函数做哈希函数，即：H(key)=random(key)。其中random为随机函数。
通常，当关键字长度不等时采用此法构造哈希函数较为恰当。

(3)平方取中法

当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。
这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。
例如对于关键key=1234。1234^2=1522756，H(k)关键字的哈希地址为：227.

(4)折叠法

这种方法是按哈希表地址位数将关键字分成位数相等的几部分（最后一部分可以较短），然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。具体方法有折叠法与移位法。移位法是将分割后的每部分低位对齐相加，折叠法是从一端向另一端沿分割界来回折叠（奇数段为正序，偶数段为倒序），然后将各段相加。
例如：key=12360324711202065,哈希表长度为1000，则应把关键字分成3位一段，在此舍去最低的两位65，分别进行移位叠加和折叠叠加，求得哈希地址为105和907。

移位法

123+603+247+112+020

个位：3+3+7+2+0=15%10=5

十位：2+0+4+1+2+1（低位进位）=10%10=0

百位：1+6+2+1+0+1（低位进位）=11%10=1

折叠法

123+306+247+211+020

个位：3+6+7+1+0=17%10=7

十位：2+0+4+1+2+1（低位进位）=10%10=0

百位：1+3+2+2+0+1（低位进位）=9%10=9

(5)直接定址法

取关键字或关键字的某个线性函数值为哈希地址。即：
H(key)=key 或 H(key)=a*key+b，其中a、b为常数（这种hash函数叫做自身函数）。

(6)数字分析法

如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。
例如，有1000个记录，关键字为10位十进制整数d1d2d3…d7d8d9d10，如哈希表长取1200，则哈希表的地址空间为：000~1199。假设经过分析，各关键字中 d3、d5和d7的取值分布较均匀，则哈希函数为：h(key)=h(d1d2d3…d7d8d9d10)=d3d5d7。
例如，h(3748597089)=457，h(9846372561)=432。就是找数字中分布均匀的数字。

哈希冲突解决方法

（1）开放定址法

找hash表剩下空余的空间，找到空余的空间然后插入。

（2）链地址法

链地址法的原理时如果遇到冲突，他就会在原地址新建一个空间，然后以链表结点的形式插入到该空间

四、链表

1、头指针和头结点的区别

头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。

头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。

2、数组和链表的区别？

从逻辑结构来看：数组的存储长度是固定的，它不能适应数据动态增减的情况。链表能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。

从访问方式来看：数组在内存中是一片连续的存储空间，可以通过数组下标对数组进行随机访问，访问效率较高。链表是链式存储结构，存储空间不是必须连续的，可以是任意的，访问必须从前往后依次进行，访问效率较数组来说比较低。

如果从第i个位置插入多个元素，对于数组来说每一次插入都需要往后移动元素，每一次的时间复杂度都是O（n），而单链表来说只需要在第一次寻找i的位置时时间复杂度为O（n），其余的插入和删除操作时间复杂度均为O(1），提高了插入和删除的效率。

3、链表的分类

• 单链表：代码
• 双向链表
• 循环链表
  • 如何判断当前结点p是否为尾结点：p的后继结点是否为头指针指向的结点

五、队列

1、定义

队列是允许在一端进行插入另一端进行删除的线性表，对于进入队列的元素按“先进先出”的规则处理，在表头进行删除在表尾进行插入。

2、分类

（1）循环队列

普通情况下，循环队列队空和队满的判定条件是一样的，都是Q.front == Q.rear。

队头指针指向第一个数；队尾指针指向最后一个数的下一个位置，即将要入队的位置。

方法一：牺牲一个单元来区分队空和队满，这个时候(Q.rear+1)%MaxSize == Q.front才是队满标志

方法二：类型中增设表示元素个数的数据成员。这样，队空的条件为Q.size == 0;队满的条件为 Q.size == MaxSize

（2）双端队列

限定插入和删除操作都可以在表的两端进行的线性表

六、栈

1、定义

栈是只能在表尾进行插入和删除操作的线性表，后进先出

2、两栈共享技术

两个栈共享一段存储空间S[M]

将两个栈的栈底分别放在存储空间的两端，分别是0，M-1

3、栈的应用

（1）括号匹配

（2）数制转换

（3）表达式求值

将表达式转换为后缀表达式

顺序扫描表达式，如果当前字符是字母（优先级为0的符号)，则直接输出;如果当前字符为运算符或者括号（优先级不为0的符号），则判断：

• 若当前运算符为 ( ，直接入栈;
• 若为 ) ，出栈并顺序输出运算符，直到遇到第一个(,遇到的第一个出栈但不输出;
• 若为其它，比较运算符栈栈顶元素与当前元素的优先级：
  • 如果栈顶元素是(，当前元素直接入栈;
  • 如果当前元素优先级<=栈顶元素优先级，出栈并顺序输出运算符直到当前元素优先级>栈顶元素优先级，然后当前元素入栈;
  • 如果当前元素优先级>栈顶元素优先级，当前元素直接入栈。

七、串

1、简单匹配算法——O(nm)

首先将原字符串和子串左端对齐，逐一比较；如果第一个字符不能匹配，则子串向后移动一位继续比较；如果第一个字符匹配，则继续比较后续字符，直至全部匹配。

2、KMP匹配算法——O(n+m)

代码

八、树

1、基本术语

• 结点——表示树中的元素，包括数据项及若干指向其子树的分支
• 结点的度——结点拥有的子树数
• 树的度——一棵树中最大的结点度数
• 叶子——度为0的结点
• 有序树与无序树——树中结点的各子树从左至右是有次序的（不能互换）则称该树为有序树，否则称该树为无序树。
• 森林——m（m≥0）棵互不相交的树的集合

2、树的存储结构

（1）双亲表示法

（2）孩子链表表示法

（3）孩子兄弟表示

? 又称为二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，与二叉树的二叉链表表示法所不同的是，这两个链域分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟），即左孩子右兄弟。

3、二叉树

代码

• 每个结点最多只有两个子树
• 为何要重点研究每结点最多只有两个 “叉” 的树？
  • 二叉树的结构最简单，规律性最强；
  • 所有树都能转为唯一对应的二叉树，不失一般性。
• 在二叉树的第i层上至多有$2^{i?1}$个结点（i>0）。
• 深度为k的二叉树至多有$2^k?1$个结点（k>0）。
• 对于任何一棵二叉树，若2度的结点数有$n_2$个，则叶子数（$n_0$）必定为$n_2$＋1 （即$n_0$=$n_2$+1）
• 具有n个结点的完全二叉树的深度必为$?lo{g}_{2}n＋1?$
• 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为$?i/2?$ （i＝1 时为根,除外）。

(1)遍历二叉树

• 先序遍历——根左右
• 中序遍历——左根右
• 后序遍历——左右根
• 层次遍历——使用队列

(2)完全二叉树

• 深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。
• 只有最后一层叶子不满，且全部集中在左边。

(3)满二叉树

一棵深度为k 且有$2^k$ -1个结点的二叉树。特点：每层都“充满”了结点。

(4)线索二叉树

将某结点的空指针域指向该结点的前驱后继，定义规则如下：

若结点的左子树为空，则该结点的左孩子指针指向其前驱结点。

若结点的右子树为空，则该结点的右孩子指针指向其后继结点。

这种指向前驱和后继的指针称为线索。将一棵普通二叉树以某种次序遍历，并添加线索的过程称为线索化。

当Tag域为0时,表示正常情况;

当Tag域为1时,表示线索情况。

(5)哈夫曼树

树的带权路径长度：$WPL={\sum }_{k=1}^n{W}_k{l}_k$——树中所有叶子结点的带权路径长度之和

哈夫曼树：WPL最小的树

哈夫曼树不唯一

$WPL=7?1+5?2+2?3+4?3=35$

构造哈夫曼树：

将所有结点按频次排序

从最少的字符开始，用贪心思想安排在二叉树上

w={2,3,6,7,10,19,21,32}

w1={5,6,7,10,19,21,32}

w2={7,10,11,19,21,32}

w3={11,17,19,21,32}

w4={19,21,28,32}

w5={28,32,40}

w6={40,60}

w7={100}

4、森林

（1）森林转二叉树

森林直接变兄弟，再转为二叉树

（2）二叉树转森林

把最右边的子树变为森林，其余右子树变为兄弟

九、图

1、存储结构

• 邻接矩阵
• 邻接表
• 十字链表

2、遍历

BFS、DFS

3、最小生成树

（1）判断连通

从任一点开始进行一次BFS或者DFS，如果能遍历所有点，则连通

（2）最小生成树的MST性质

假设N＝（V，｛E｝）是?个连通?，U是顶点集V的?个?空?集。若（u，v）是?条具有最?权
值的边，其中u∈U，v∈V-U ，则必存在?棵包含边（u，v)的最??成树具

（3）Prim算法

• 一条边一条边地加，维护一棵树。
• 初始E={}空集合，V ={任意一个节点}
• 循环(n-1)次，每次选择一条边(v1, v2)，满足v1属于V , v2不属于V。且( v1, v2)权值最小。
• E=E＋(v1, v2)
• V =V ＋ v2
• 最终E中的边是一棵最小生成树,V包含了全部节点。

（4）Kruskal算法

4、最短路径问题

（1）单源起点的最短路径Dijkstra

（2）任意两点最短路径Floyd

5、拓扑排序

（1）AOV网

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称之为AOV网

（2）拓扑排序

从AOV网中选择一个入度为0的顶点输出，然后删去此顶点及以它尾的弧，重复步骤直至输出图中全部顶点。

十、排序

1、稳定性

? 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的;否则称为不稳定的。

2、冒泡排序

基本思想：反复?较两两相邻元素，若不符合顺序要求，则交换相邻元素，直?有序

3、选择排序

将待排序序列看作由已排序部分和未排序部分组成，初始时，?排序部分为空

原始序列:49、38、65、97、76、13、27、49

1)在进行选择排序过程中分成有序和无序两个部分，开始都是无序序列结果:49、38、65、97、76、13、27、49

2)从无序序列中取出最小的元素13，将13同无序序列第一个元素交换，此时产生仅含一个元素的有序序列,无序序列减一

结果:{13、} {38、65、97、76、49、27、49}

3)从无序序列中取出最小的元素27，将27同无序序列第一个元素交换，此时产生仅两个元素的有序序列，无序序列减一

结果:{13、27、} {65、97、76、49、38、49}

4)从无序序列中取出最小的元素38，将38同无序序列第一个元素交换，此时产生含三个元素的有序序列，无序序列减一

结果:{13、27、38、}{97、76、49、65、49}

5)从无序序列中取出最小的元素49，将49同无序序列第一个元素交换，此时产生含四个个元素的有序序列，无序序列减一

结果:{13、27、38、49、} {76、97、65、49}
6)从无序序列中取出最小的元素49，将49同无序序列第一个元素交换，此时产生含五个元素的有序序列，无序序列减一

结果:{13、27、38、49、49、} {97、65、76}
7)从无序序列中取出最小的元素65，将65同无序序列第一个元素交换，此时产生含六个元素的有序序列，无序序列减一

结果:{13、27、38、49、49、65、}{97、76}

8)从无序序列中取出最小的元素76，将76同无序序列第一个元素交换，此时产生含七个元素的有序序列，无序序列减一

结果:{13、27、38、49、49、65、76、} {97}

9)最后一个元素肯定是最大元素，无序排序直接生产一个有序的序列

结果:{13、27、38、49、49、65、76、97}

4、插入排序

将待排序序列看作由已排序序列和未排序序列两部分构成,初始时,取第一个元素为已排序序列,剩余元素为未排序序列

任取未排序序列中的一个元素,插入到已排序序列中

循环直到未排序序列为空

5、希尔排序

希尔排序

6、堆排序

设有一个任意序列，k1,k2,…,kn，当满足下面特点时称之为堆：让此序列排列成完全二叉树，该树具有以下特点，该树中任意节点均大于或小于其左右孩子，此树的根节点为最大值或者最小值。

7、归并排序

把两个或者两个以上的有序表合并成一个新的有序表

8、快速排序

#include<iostream>
using namespace std;
int s[110];
void quick_sort(int l,int r){
	if(l<r){
		int i=l,j=r,x=s[l];
		while(i<j){
			while(i<j&&s[j]>=x){
				j--;
			}
			if(i<j){
				s[i]=s[j];
				i++;
			}
			while(i<j&&s[i]<x){
				i++;
			}
			if(i<j){
				s[j]=s[i];
				j--;
			}
		}
		s[i]=x;
		quick_sort(l,i-1);
		quick_sort(j+1,r);
	}
}
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>s[i];
	}
	quick_sort(0,n-1);
	for(int i=0;i<n;i++){
		cout<<s[i]<<" ";
	}
	return 0;
}

十一、贪心算法和动态规划以及分治法的区别

1、贪心算法

做出在当前看来是最好的结果，它不从整体上加以考虑，也就是局部最优解。贪心算法从上往下，从顶部一步一步最优，得到最后的结果，它不能保证全局最优解，与贪心策略的选择有关。

2、动态规划

动态规划常常适用于有重叠子问题和最优子结构性质的问题

把问题分解成子问题，这些子问题可能有重复，可以记录下前面子问题的结果防止重复计算。动态规划解决子问题，前一个子问题的解对后一个子问题产生一定的影响。在求解子问题的过程中保留哪些有可能得到最优的局部解，丢弃其他局部解，直到解决最后一个问题时也就 是初始问题的解。动态规划是从下到上，一步一步找到全局最优解。

3、分治法

将原问题划分成n个规模较小而结构与原问题相似的子问题； 递归地解决这些子问题，然后再合并其结果，就得到原问题的解。