导言：整理一些考研资料
名词解释
数据结构
- 数据结构：数据结构是相互之间存在一种或多种特定关系的据元素的集合。
- 逻辑结构：集合、线性结构、树形结构、图状结构
- 物理结构：顺序存储、链式存储、索引存储<关键字，地址>、散列存储
- 抽象数据类型：抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。
- 算法：算法是对待定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。此外算法还具有有穷性、确定性、可行性、输入和输出五个特征。评价一个好的算法，有四个方面：算法的正确性、算法的易读性、算法的健壮性、算法的时空效率。
- 时间复杂度：算法中基本操作的执行次数作为算法时间复杂度的度量。
- 空间复杂度：算法在运行时所需存储空间的度量（临时占用的存储空间大小），所需额外空间是常数时，称之为原地工作
栈和队列
- 共享栈：利用栈底位置相对不变的特性，让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
- 循环队列：将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上看成一个环的队列成为循环队列。
- 队空：front==rear
- 队满：(rear+1)%Maxsize==front
- 队列长度：(rear-front+Maxsize)%Maxsize
树
-
二叉树：每个结点最多都只能有两个子结点的树结构。而且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树也可以为空树。
-
完全二叉树：设一个高度为h，有n个结点的二叉树，当且仅当其每一个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称谓完全二叉树。
-
二叉排序树：二叉排序树或者是一棵空树或者是一棵具有下列特征的非空二叉树：
a）若左子树非空，则左子树上所有结点关键字值均小于根节点的关键值。
b）若右子树非空，则左子树上所有结点关键字值均大于根节点的关键值。
c）左右子树本身也分别是一棵二叉排序树。
-
平衡因子：节点左子与右子树的高度差称为该结点的平衡因子。
图
- 有向图：在图 G = ( V , E ) 中，若E是有向边（也称为弧）的有限集合，则图G为有向图。
查找
- 散列表处理冲突的方法：① 拉链法、② 开放定址法
- 平均查找长度：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。
排序
-
稳定性：多个相同关键字排序前后相对位置不变则此排序稳定，否则不稳定。
-
内部排序：指待排序序列完全存放在内存中所进行的排序过程，适合不太大的元素排序。
-
外部排序：待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。
栈
中缀转后缀
int compare(char a,char b)
{
if(a=='+'||a=='-')
{
if(b=='-'||b=='+')
return 0;
if(b=='*'||b=='/')
return -1;
}
if(a=='*'||a=='/')
{
if(b=='*'||b=='/')
return 0;
if(b=='+'||b=='-')
return 1;
}
return -1;
}
void change(char str[])
{
int i;
s.top=0;
q.head=0;
q.rear=0;
int len=strlen(str);
for(i=0;i<len;i++)
{
if(str[i]=='(') //1.遇到左括号，将其进栈
{
s.data[s.top]=str[i];
s.top++;
}
else if(str[i]==')') //2.遇到右括号，执行出栈操作，直到遇到左括号
{
s.top--;
while(s.top>=0&&s.data[s.top]!='(')
{
q.data[q.rear]=s.data[s.top];
q.rear++;
s.top--;
}
//if(s.top=='(')
// s.top--;
//s.top++;
}
else if((str[i]>='0'&&str[i]<='9')||(str[i]>='a'&&str[i]<='z')||(str[i]>='A'&&str[i]<='Z')) //3.遇到操作数，直接进队列
{
q.data[q.rear]=str[i];
q.rear++;
}
else //4.遇到其他运算符
{
s.top--;
while(s.top>=0&&compare(s.data[s.top],str[i])>=0) //如果该运算符的优先级不高于栈里的运算符的优先级
{
q.data[q.rear]=s.data[s.top];
q.rear++;
s.top--;
}
s.top++;
s.data[s.top]=str[i];
s.top++;
}
}
s.top--;
while(s.top>=0)
{
q.data[q.rear]=s.data[s.top];
q.rear++;
s.top--;
}
}
二叉树
树的结构
typedef struct BiTNode{
int data; // 数据域
struct BiTNode *lchild, *rchild; // 左右孩子指针
}BiTNode,*BiTree;
树的遍历
先序遍历(递归)
void PreOrder(BiTree T){
if(T!=NULL){
visit(T); // 访问结点
PreOrder(T->lchild); // 递归遍历左子树
PreOrder(T->rchild); // 递归遍历右子树
}
}
先序遍历
void PreOrder2(BiTree T){
InitStack(S); BiTree p=T; // 初始化栈S; p是遍历指针
while(p || !IsEmpty(S)){ // 栈不空或p不空时循环
if(p){ // 一路向左
visit(p); Push(S,p); // 访问当前结点，并入栈
p=p->lchild; // 左孩子不空，一直向左走
}
else{ // 出栈，并转向出栈结点的右子树
Pop(S,p); // 栈顶元素出栈
p=p->rchild; // 向右子树走，p赋值为当前结点的右孩子
} // 返回while循环继续进入if-else语句
}
}
中序遍历(递归)
void InOrder(BiTree T){
if(T!=NULL){
InOrder(T->lchild); // 递归遍历左子树
visit(T); // 访问结点
InOrder(T->rchild); // 递归遍历右子树
}
}
中序遍历
void InOrder2(BiTree T){
InitStack(S); BiTree p=T; // 初始化栈S; p是遍历指针
while(p || !IsEmpty(S)){ // 栈不空或p不空时循环
if(p){ // 一路向左
Push(S,p); // 当前结点入栈
p=p->lchild; // 左孩子不空，一直向左走
}
else{ // 出栈，并转向出栈结点的右子树
Pop(S,p); visit(p); // 栈顶元素出栈，访问出栈结点
p=p->rchild; // 向右子树走，p赋值为当前结点的右孩子
} // 返回while循环继续进入if-else语句
}
}
后序遍历(递归)
void PostOrder(BiTree T){
if(T!=NULL){
PostOrder(T->lchild); // 递归遍历左子树
PostOrder(T->rchild); // 递归遍历右子树
visit(T); // 访问结点
}
}
后序遍历
void PostOrder2(BiTree T){
InitStack(S); BiTree p=T; // 初始化栈S; p是遍历指针
r=NULL;
while(p || !IsEmpty(S)){
if(p){ // 走到最左边
Push(S,p);
p=p->lchild;
}
else{ // 向右
GetTop(S,p); // 读栈顶结点（非出栈）
if(p->rchild && p->rchild!=r)// 若右子树存在，且未被访问过
p=p->rchild; // 转向右
else{ // 否则，弹出结点并访问
Pop(S,p); // 将结点弹出
visit(p); // 访问该结点
r=p; // 记录最近访问过的结点
p=NULL; // 访问结束后，重置p指针
}
}
}
}
层次遍历
void LevelOrder(BiTree T) {
InitQueue(Q); // 初始化辅助队列
BiTree p;
EnQueue(Q,T); // 将根结点入队
while (!IsEmpty(Q)) { // 队列不空循环
DeQueue(Q,p); // 队头元素出队
visit(p); // 访问出队结点
if (p->lchild!=NULL)
EnQueue(Q,p->lchild); // 左子树不空，则左子树根节点入队列
if (p->rchild!=NULL)
EnQueue(Q,p->rchild); // 右子树不空，则右子树根节点入队列
}
}
图
图的结构
邻接矩阵法
#define MaxVertexNum 100 // 顶点数目的最大值
typedef char VertexType; // 顶点的数据类型
typedef int EdgeType; // 带权图中边上权值的数据类型
typedef struct {
VertexType Vex[MaxVertexNum]; // 顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵，边表
int vexnum, arcnum; // 图的当前顶点数和弧数
} MGraph;
邻接表法
#define MaxVertexNum 100 // 图中顶点数目的最大值
typedef struct ArcNode { // 边表结点
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *next; // 指向下一条弧的指针
//InfoType info; // 网的边权值
} ArcNode;
typedef struct VNode { //顶点表结点
VertexType data; // 顶点信息
ArcNode *first; // 指向第一条依附该结点的弧的指针
} VNode, AdjList[MaxVertexNum];
typedef struct { // 图的邻接表存储结构定义
AdjList vertices; // 邻接表
int vexnum, arcnum; // 图的顶点数和弧数
} ALGraph;
图的遍历
广度优先遍历-BFS
bool visited[MAX_VERTEX_NUM]; // 访问标记数组
void BFSTraverse(Graph G){
//对图G进行广度优先遍历，设访问函数为visit()
for(int i=0; i<G.vexnum; ++i){
visited[i]=false; // 访问标记数组初始化
}
InitQueue(Q); // 初始化辅助队列Q
for (i = 0; i < G.vexnum; ++i) // 从0号顶点遍历
if(!visited[i]) // 对每个连通分量调用一次BFS
BFS(G,i); // Vi未访问过，从Vi开始BFS
}
void BFS(Graph G,int v){
//从顶点v出发，广度优先遍历图G，算法借助一个辅助队列Q
visit(v); // 访问初始顶点v
visited[v]=true; // 对v做已访问标记
EnQueue(Q,v); // 顶点v入队列
while(!IsEmpty(Q)){
DeQueue(Q,v); // 顶点v出队列
for (int w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)){
//检测v所有邻接点
if(!visited[w]){ // w为v的尚未访问的邻接顶点
visit(w); // 访问顶点w
visited[w]=true; // 对w做已访问标记
EnQueue(Q,w); // 顶点w入队列
}// if
}
}// while
}
深度优先遍历-DFS
bool visited[MAX_VERTEX_NUM]; // 访问标记数组
void DFSTraverse(Graph G){
//对图G进行深度优先遍历
for(int v = 0; v < G.vexnum; ++v)
visited[v]=false; // 初始化已访问标记数据
for (v = 0; v < G.vexnum; ++v) // 本代码中是从v=0开始遍历
if(!visited[v])
DFS(G,v);
}
void DFS(Graph G,int v){
//从顶点v出发，采用递归思想，深度优先遍历图G
visit(v); // 访问顶点v
visited[v]=true; // 设已访问标记
for (int w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)){
if(!visited[w]){ // w为u的尚未访问的邻接顶点
DFS(G,w);
}// if
}
}
最小生成树
Prim算法
void Prim(G,T){
T=NULL; // 初始化空树
U={w}; // 添加任一顶点w
while((V-U)!=NULL){ // 若树中不含全部顶点
设(u,v)是使u∈U与v∈(V-U),且权值最小的边;
T=T∪{(u,v)}; // 边归入树
U=U∪{v}; // 顶点归入树
}
}
Krustal算法
void Kruskal(V,T){
T=V; // 初始化树T，仅含顶点
numS=n; // 连通分量数
while(numS>1){ //如果连通分量数大于1
从E中取出权值最小的边(v,u);
if(v和u属于T中不同的连通分量){
T=T{(v,u)}; // 将此边加入生成数中
numS--; // 连通分量数减1
}
}
}
拓扑排序
bool TopologicalSort(Graph G){
// 如果G存在拓扑序列，返回true；否则返回false，这时G中存在环
InitStack(S); // 初始化栈，存储入度为0的顶点
for (int i = 0; i < G.vexnum; ++i){
if(indegree[i]==0)
Push(S,i); // 将所有入度为0的顶点进栈
}
int count=0; // 计数，记录当前已经输出的顶点数
while(!IsEmpty(S)){ // 栈不空，则存在入度为0的顶点
Pop(S,i); // 栈顶元素出栈
print[count++]=i; // 输出顶点i
for(p=G.vertices[i].firstarc; p; p=p->nextarc){
//将所有i指向的顶点的入度减 1，并且将入度减为 0 的顶点压入栈S
v=p->adjvex;
if(!(--indegree[v]))
Push(S,v); //入度为0，则入栈
}// for
}// while
if(count < G.vexnum)
return false; // 排序失败，有向图中有回路
else
return true; // 拓扑排序成功
}
排序
各种排序算法的性质
| 算法种类 | 最好 | 平均 | 最坏 | 空间复杂度 | 是否稳定 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n²) | O(n²) | O(1) | √ |
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | √ |
| 简单选择排序 | O(n²) | O(n²) | O(n²) | O(1) | × |
| 希尔排序 | O(1) | × | |||
| 快速排序 | O(nlog~2~n) | O(nlog~2~n) | O(n²) | O(log~2~n) | × |
| 堆排序 | O(nlog~2~n) | O(nlog~2~n) | O(nlog~2~n) | O(1) | × |
| 2路归并排序 | O(nlog~2~n) | O(nlog~2~n) | O(nlog~2~n) | O(n) | √ |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r) | √ |
插入排序
在已经有序的序列中插入新的关键字
直接插入排序
void InsertSort(int *arr, int len){
int i,j;
for(i=2; i<len; i++){ // 依次将arr[2]~arr[len]插入前面已排序序列
if(arr[i] < arr[i-1]){ // 若arr[i]关键码小于其前驱，将arr[i]插入有序表
arr[0] = arr[i]; // 复制为哨兵，arr[0]不存放元素
for(j=i-1; arr[0]<arr[j]; --j){ // 从后往前查找待插入位置
arr[j+1] = arr[j]; // 向后挪位
}
arr[j+1] = arr[0]; // 复制到插入位置
}
}
}
折半插入排序
void InsertSort(int *arr, int len){
int i,j,low,high,mid;
for(i-2; i<=len; i++){ // 依次将arr[2]~arr[len]插入前面的已排序序列
arr[0] = arr[i]; // 将arr[i]暂存到arr[0]
low = 1; high =i-1; // 设置折半查找的范围
while(low <= high){ // 折半查找（默认递增有序）
mid = (low+high)/2; // 取中间点
if(arr[mid] > arr[0])
high = mid-1; // 查找左半子表
else
low = high+1; // 查找右半子表
}
for(j=i-1; j>=high+1; --j){
arr[j+1] = arr[j]; // 统一后移元素，空出插入位置
}
arr[high+1] = arr[0]; // 插入操作
}
}
交换排序
通过“交换”关键字的操作，使序列有序
冒泡排序
void BubbleSort(int *arr, int len){
int i,j;
bool flag;
for (i=0; i<len-1; i++) {
flag = false; // 表示本趟，泡是否发生交换的标志
for (j = len - 1; j > i; j--) { // 一趟冒泡过程
if (arr[j-1] > arr[j]){ // 若为逆序
Swap(&arr[j-1], &arr[j]); // 交换
flag = true;
}
}
if(flag==false)
return;
}
}
快速排序
void QuickSort(int *arr, int low, int high){
if(low<high){ // 递归跳出的条件
// Partition()就是划分操作，将表arr[low...high]划分为满足上述条件的两个子表
int pivotpos = Partition(&arr,low,high); // 划分
QuickSort(&arr, low, pivotpos-1); // 依次对两个子表进行递归排序
QuickSort(&arr, pivotpos+1, high);
}
}
int Partition(int *arr, int low, int high){ // 一趟划分
int pivot = arr[low]; // 将当前表中第一个元素设为枢轴，对表进行划分
while(low < high){ // 循环跳出条件
while(low < high && arr[high] >= ivot)
--high; // 将比枢轴小的元素移动到左端
arr[low] = arr[high];
while(low < high && arr[low] <= ivot)
--low; // 将比枢轴大的元素移动到右端
arr[high] = arr[low];
}
arr[low] = pivot; // 枢轴元素存放到最终位置
return low; // 返回存放枢轴的最终位置
}
选择排序
每趟选出一个“最值”
简单选择排序
void SelectSort(int *arr, int len){
int min, i, j;
for (i = 0; i < len - 1; ++i) { // 一共进行 len-1 趟
min = i; // 记录最小元素位置
for (j = i+1; j < len; ++j) { // 在arr[i...len-1]中选择最小的元素
if (arr[j] < arr[min]) // 更新最小元素位置
min = j;
}
if (min != i)
Swap(&arr[min], &arr[i]);
}
}
堆排序
void HeapSort(int *arr, int len){
BuildMaxHeap(&arr, len); // 初始建堆
for(i=len; i>1; i--){ // len-1 趟的交换和建堆过程
Swap(&arr[i], &arr[1]); // 输出堆顶元素（和堆底元素交换）
HeadAdjust(&arr, 1, i-1); // 调整，把剩余的 i-1 个元素整理成堆
}
}
void BuildMaxHeap(int *arr，int len){
for(int i=len/2; i>0; i--){
HeadAdjust(&arr, i, len);
}
}
void HeadAdjust(int *arr, int k, int len){
//函数HeadAdjust将元素k为根的子树进行调整
arr[0] = arr[k]; // arr[0]暂存子树的根结点
for(i=2*k; i<=len; i*=2){ // 沿 key 较大的子结点向下筛选
if(i<len && arr[i]<arr[i+1])
i++; // 取 key 较大的子结点的下标
if(arr[0]>=arr[i])
break; // 筛选结束
else{
arr[K] = arr[i]; // 将A[i]调整到双亲结点上
k = i; // 修改k值，以便继续向下筛选
}
}
arr[k] = arr[0]; // 被筛选结点的值放入最终位置
}
归并排序
“归并”即将多个有序序列合并成一个有序序列，分而治之
int *B=(int *)malloc((n+1)*sizeof(int)); // 辅助数组B
void Merge(int *arr, int low, int mid, int high){
for(int k=low; k<=high; k++)
B[k]=arr[k]; // 将arr中所有元素复制到B中
for(i=low,j=mid+1,k=i; i<=mid && j<=high; k++){
if(B[i]<=B[j]) // 比较B的左右两段中的元素
arr[k]=B[i++]; // 将较小值复制到arr中
else
arr[k]=B[j++];
}//for
while(i<=mid)
arr[k++]=B[i++]; // 若第一个表未检测完，复制
while(j<=high)
arr[k++]=B[j++]; // 若第二个表未检测完，复制
}
void MergeSort(int *arr,int low,int high){
if(low < high){
int mid=(low+high)/2; // 从中间划分两个子序列
MergeSort(arr,low,mid); // 对左侧子序列进行递归排序
MergeSort(arr,mid+1,high); // 对右侧子序列进行递归排 序
Merge(arr,low,mid,high); // 归并
}//if
}