阿坝网站建设公司

考研心得：考研数据结构算法大全-创新互联

本人考研的算法笔记，包含考研数据结构会涉及到的算法，全部掌握让你考研算法题稳稳拿下！！

创新互联公司是一家专业提供彭山企业网站建设,专注与成都网站建设、网站制作、H5页面制作、小程序制作等业务。10年已为彭山众多企业、政府机构等服务。创新互联专业网站设计公司优惠进行中。
一、排序 1.插入排序

算法思想：第i次插入排序：向i-1个有序数列中插入一个元素，使之称为含有i个元素的有序子序列。将当前元素和前驱元素比较，若大于则表示有序，不用改变；否则将该元素插入到前面，并且前面比它大的元素后移。

void InsertSort ( int a[] , int n )
{int temp , i , j;
    for( i = 1 ; itemp = a[i]; 				//保存该元素值
            for( j = i-1 ; a[j] >temp; --j)//前面大于的依次后移
            a[j+1] = a[j];
            a[j+1] = temp;				//放到应该在的位置
        }
}
2.希尔排序

算法思想：也叫缩小增量排序。取一个小于n的整数d作为增量，把数据分组，所有距离为d的倍数的记录放在同一个组中，在各组内进行直接插入排序。初次取序列的一半为增量，以后每次减半，直到增量为1，即排序结束。

void ShellSort ( int a[] , int n )	相当于插入排序中的1换成d
{int temp , i , j;
    for( d = n/2 ; d >=1 ; d = d/2)					//步长变化
        for( i = d + 1 ; itemp = a[i]; 				//保存该元素值
            for( j = i-d ; a[j] >temp ; j-=d )	//前面大于的依次后移
            a[j+d] = a[j];
            a[j+d] = temp;				//放到应该在的位置
        }
}
3.折半排序

算法思想：直接插入排序的改进，在插入到前面有序子队列时使用折半查找方式进行查找。

void BInsertSort( int a[] , int n )
{int low , high , mid , temp , i , j;
    for( i = 1 ; itemp = a[i];				//保存元素
            low = 0;
            high = i-1;
            while(lowmid = (low + high)/2;
                if( a[mid] >temp )		
                high = mid-1;	//查找左边
                else 
                low = mid+1;	//查找右边
            }
            a[low] = temp;			//放到指定位置
        }
}
4.冒泡排序

算法思想：每次都从第一个元素开始，依次两个两个比较，小的放前面，使得前i个元素的大放在第i的位置，在算法中设置flag=1标志，若此次发生交换则flag设置为1，若未发生变换则flag=0说明整个数组有序，排序结束

void BubbleSort( int a[] , int n )
{int flag = 1;
​	for (int i = n-1 ; i>0 && flag ==1 ; i--)	//对前i个元素进行冒泡，因为是两两比较，所有i>0，不能等于0
​	{​		flag = 0;						//初始化flag
​		for (int j = 0 ; ja[j+1] )				//若大于后继，则互换
​			{​				Swap( a[j] = a[j+1]);
​				flag = 1;				//更新flag
​			}
​	}
}
5.双向冒泡排序

算法思想：每次先从前往后冒泡，当一次往后之后再从后往前冒泡一遍，并且每次冒泡后都需要更新上下界

void bubble2(int a[], int n)//交替
{​	int low = 0, high = n - 1;
​	bool flag = true;//一趟冒泡后记录元素是否发生交换的标志，若没有发生则表示已经有序
​	while (low< high&&flag)
​	{​		flag = false;//每次排序初始化flag为false
​		for (int i = low; i< high; i++)//从前往后冒泡
​			if (a[i] >a[i + 1])//大的往后
​			{​				swap(a[i], a[i + 1]);
​				flag = true;
​			}
​		high--;//更新上界
​		for (int i = high; i >low; i--)//从后往前冒泡
​			if (a[i]< a[i - 1])//小的往前
​			{​				swap(a[i], a[i - 1]);
​				flag = true;
​			}
​		low++;//更新下界
​	}
}
5.快速排序

算法思想：使用分治算法的思想，将数据进行拆分，直至拆到最小再进行排序合并。首先选取第一个数作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序，之后递归直至所有元素排完。

void QuickSort(int a[] , int low , int high) 					//分治拆分，递归
{​	if (low< high)
​	{​		int pivotpos = Partition(a,low,high);
​		QuickSort(a, low, pivotpos - 1);
​		QuickSort(a, pivotpos + 1, high);
​	}
}

int Partition(int a[], int low, int high)						//从表的两端交替向中间扫描，一趟划分
{​	int pivot = a[low];								//将表第一个元素设置为中心点	
while (low< high)
​	{​		while (low< high && a[high] >= pivot)  --high;		//先从后往前找第一个小于pivot的位置
​		a[low] = a[high];							//更新
​		while (low< high && a[low]<= pivot)  ++low;		//再从前往后找第一个大于pivot的位置
​		a[high] = a[low];							//更新
​	}
​	a[high] = pivot;								//pivot放入，这时high=low
​	return high;
}
6.简单选择排序

算法思想：每次都从序列后的n-i+1个元素中选出最小的元素与该元素组的第1个元素交换，即与整个序列的第i个元素交换。依此类推，直至i=n-1为止。也就是说，每一趟排序从未排好顺序的那些元素中选择一个最小的元素，然后与这些未排好序的元素的第一个元素互换

void SelectSort(int a[], int n)
{​	int min;
​	for (int i = 0; i< n; i++)
​	{​		min = i;					//记录最小元素位置
​		for (int j = i + 1; j< n; j++)		//找最小
​			if (a[min] >a[j])   min = j;	//更新最小元素位置
​		if (min != i)					//若i不是最小的元素，则互换
​			Swap(a[min] , a[j])
​	}
}
7.堆排序

算法思想：将待排序序列构造成一个大顶堆，此时，整个序列的大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

void buildmaxheap(int a[], int n)			//创建大根堆
{​	for (int i = len / 2; i >0; i--)			//从n/2~1贩反复调整堆
​		headadjust(a, i, n);
}
void headadjust(int a[ ], int k, int n)			//将元素k为根的子树进行调整
{​	a[0] = a[k];
​	for (int i = 2 * k; i<= n; i *= 2)		//一层一层向下
​	{​		if (i< n&&a[i]< a[i + 1])  i++;	//取key较大的子结点
​		if (a[0] >a[i])        break;	//若较大的子结点小于k，则不用再比
​		else
​		{​			a[k] = a[i];				//若子结点小于k，则和子结点互换
​			k = i;					//指向k的新位置，以便继续向下筛选
​		}
​	}
​	a[k] = a[0];						//被筛选的值放在最终位置
}
void heapsort(int a[ ], int n)
{​	buildmaxheap(a, n);				//初始建堆
​	for (int i = n; i >1; i--)				//将堆顶和最后一个结点互换，放到其排序的位置
​	{​		Swap(a[1],a[i]);				//互换
​		headadjust(a, 1, i - 1);			//i-1之后的已经有序，只用排之前的
​	}
}
8.归并排序

算法思想：使用分治算法的思想。使用递归方法来实现归并排序时，核心思想是两个有序子序列的合并，注意这里是有序子序列的合并，因此下面要做两件事，整个过程：

(1)将待排序序列从中间一分为二，对左右两边再进行递归分割操作，得到n个相互独立的子序列；

(2)对n个独立的子序列递归的执行合并操作，最终得到有序的序列。

void MergeSort(int a[], int low, int high)	//合并两个有序的子序列
{​	if (low< high)
​	{​		int mid = (low + high) / 2;	//从中划分成两个子序列
​		MergeSort(a, low, mid);		//对左侧进行归并排序
​		MergeSort(a, mid + 1, high);	//对右侧进行归并排序
​		Merge(a, low, mid, high);	//将[low-mid]和[mid+1-high]归并
​	}
}
int *b = (int*)malloc(n*sizeof(int));				 //辅助函数b
void Merge(int a[], int low, int mid, int high) 	 	 //将序列[low-mid]和[mid+1-high]合并成一个有序序列
{​	int i = low, j = mid + 1, k = low;
​	for (int p = low; p<= high; p++)  b[p] = a[p];	 //将a[ ]中元素都复制到b[ ]中
​	while (i<= mid && j<= high)			   //合并放入a[ ]
​	{​		if (b[i]< b[j]) a[k++] = b[i++];		 //将小的放入
​		else			a[k++] = b[j++];
​	}
​	while (i<= mid)	 a[k++] = b[i++]; 	//若没有排完添加到后面
​	while (j<= high) a[k++] = b[j++];
}
二、查找 1.一般线性表顺序查找

算法思想：查找全部元素，若找到则输出，未找到则输出-1

int Search(int a[], int n, int x)
{​	for (int i = 0; i< n; i++)
​		if (a[i] == x)  return i;
​	return -1;
}
2.有序表的顺序查找

算法思想：当当前元素小于关键字则向后找，若大于关键字或者遍历完，则返回-1

int Search(int a[], int n, int x)
{​	for (int i = 0; i< n ***\*&& a[i] >x\****; i++)
​		if (a[i] == x) return i;
​	return -1;
}
3.折半查找

算法思想：将表分为两部分，关键字和中间的元素比较，若小于则在左边查找，若大于则在右边查找，直至找到，若未找到返回-1

int BSearch(int a[], int n, int x)
{​	int low = 0, high = n - 1, mid;
​	while (low<= high)
​	{​		mid = (low + high) / 2;
​		if (a[mid] == x)	return mid;
​		if (a[mid] >x)	high = mid - 1;	//从前半部分找
​		else			low = mid + 1;	//从后半部分找
​	}
​	return -1;
}
三、图 存储结构：

①邻接矩阵

typedef struct MGraph{	char Vex[Max_VexNum];					//顶点表
	int Edge[Max_Vexnum] [Max_Vexnum];		//邻接矩阵，边表
	int vexnum,arcnum;					//顶点数和边数
}MGraph;

②邻接表法

typedef struct ArcNode{//边表结点
	int adjvex;							//改弧指向的顶点位置
	struct ArcNode *next;					//指向下一条弧的指针
}ArcNode;

typedef struct VNode{//顶点表结点
	char data;							//顶点信息
	ArcNode *first;						//指向第一条依附该顶点的弧的指针
}VNode, AdjList[Max_VexNum];				

typedef struct ALGraph{//是以邻接表存储的图类型
	AdjList vertices;						//邻接表
	Int vexnum,arcnum;					//图的顶点数和弧数
}ALGraph;
1.广度优先算法BFS

算法思想：类似树的层序遍历，1.访问完当前顶点的所有邻接点。2.访问当前已在集合内的顶点的邻接点（邻接点不包括已在集合内的）

bool visited[max_vex_num];					//访问标记数组
void BFSTraverse(Graph G)
{​	for (int i = 0; i< G.Vexnum; i++)
​		visited[i] = false;					//初始化访问标记数组
​	for (int j = 0; j< G.Vexnum; j++)			//从0号开始遍历
​		if (!visited[j])						//对每一连通分量调用一次BFS
​			BFS(G, j);
}

void BFS(Graph G, int v)						//从顶点v出发开始广度优先遍历
{​	int p;
​	int Q[G.Vexnum];					//建立队列（和DFS的差别就是这个队）
​	int front = 0, rear = 0;				//初始化队列
​	visit(v);							//访问初始结点
​	visited(v) = true;						//标记访问
​	Q[rear++] = v;						//入队
​	while (front!=rear)						//队列非空
​	{​		p =Q[front++];				//顶点出队
​		for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
//检测v所有邻接点
​			if (!visited[w])				//若w为v尚未访问的邻接点
​			{​				visit(w);			//访问结点
​				visited(w) = true;			//标记访问
​				Q[rear++] = w;		//入队
​			}
​	}
}
2.BFS算法求单源最短路径问题

算法思想：因为BFS算法是以根开始广度优先遍历

bool visited[max_vex_num];					//访问标记数组
void BFS_Min_Distance(Graph G, int u)			//d[i]表示从u到i结点的最短路径
{​	visited[u] = true;						//初始化根结点
​	d[u] = 0;
​	for (i = 0; i< G.vexnum; i++)				//初始化路径长度
​		d[i] = ∞;
​	int Q[G.vexnum];						//创建队列
​	int front = 0, rear = 0, x ;				//初始化队列
​	Q[rear++] = u;						//u入队
​	while (front != rear)
​	{​		x = Q[front++];					//出队
​		for (int w = FirstNeighbor(G, x); w >= 0; w = NextNeighbor(G, x, w))
​			if (!visited[w])
​			{​				visited[w] = true;
​				d[w] = d[u]+1;			//路径长度+1
​				Q[rear++] = w;
​			}
​		
​	}
}
3.深度优先算法DFS

算法思想：类似树的先序。首先访问图中某一起始点v，然后由v出发，访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点w2，重复上述操作。当不能继续向下访问时，退回到最近被访问的顶点，若它还有邻接点未被访问，则从该顶点继续上述搜索过程，直至图中所有结点都被访问。

bool visited[max_vex_num];					//访问标记数组
void DFSTraverse(Graph G)
{​	for (int i = 0; i< G.Vexnum; i++)
​		visited[i] = false;					//初始化访问标记数组
​	for (int i = 0; i< G.Vexnum; i++)
​		if (!visited[i])
​			DFS(G, i);
}

void DFS(Graph G, int v)
{​	visit(v);
​	visited[v] = true;
​	for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
//w为u的尚未访问的邻接顶点
​		if (!visited[w])
​			DFS(G, w);
}
四、树 1.递归遍历
void Track(BiTree p)
{if(p)
	{//1.先序
    Track(p->lchild);
    //2.中序
    Track(p->rchild);
    //3.后序
    }	
}
2.先序/中序遍历

算法思想（先序）：1.沿着根的左孩子，依次入栈并访问，直到孩子为空。2.栈顶元素出战，并开始遍历右子树

算法思想（中序）：1.沿着根的左孩子，依次入栈，直到孩子为空。2.栈顶元素出栈并访问，并开始遍历右子树

void Order(BiTree T)
{​	if (T)
​	{​		BiTNode *Stack[Max_Size];		//建栈并初始化
​		int top = -1;
​		BiTNode *p = T;
​		while (top != -1 || p != NULL)		//栈非空并且树未遍历完时
​		{​			if (p)
​			{​				//1.先序
​				Stack[++top] = p;		//入栈
​				p = p->lchild;		//遍历左子树
​			}
​			else
​			{​				p = Stack[top--];		//出栈
​				//2.中序
​				p = p->rchild;		//遍历右子树
        	}	
        }	
    }	
}
3.后序遍历（双栈/单栈标记法）

①双栈法

算法思想：用两个栈来存储，1.先将根结点入栈1；2.出栈顶元素入站2，依次将左右子树入栈1。重复操作2直至栈1为空，再将所有栈2元素出栈

void Post_order(BiTree T)
{​	if (!T)	 return;
​	BiTNode * stack1[Max_Size], * stack2[Max_Size];
​	int top1 = -1, top2 = -1;
​	BiTNode * p;
​	stack1[++top1] = T;	 //根入栈1
​	while (top1 != -1)
​	{​		p = stack1[top1--];//1栈顶元素出栈入栈2
​		stack2[++top2] = p;
​		if (p->lchild)		//左右子树入栈1
​			stack1[++top1] = p->lchild;
​		if (p->rchild)
​			stack1[++top1] = p->rchild;
​	}//while end
​	while (top2 != -1)			//栈2所有元素出栈
​	{​		p = stack2[top2--];
​		visit(p);
	}	
}

②单栈标记法

算法思想：1.沿着根的左孩子，依次入栈，直至左孩子为空；2.栈顶元素出栈，若其右孩子不空且未被访问过，则右孩子入栈执行1；否则栈顶元素出栈访问并且标记。因为后序遍历，当前结点若右子树存在，则当前结点的前驱为其右孩子

void Post_order(BiTree T)
{​	BTNode *stack[Max_Size];				//建栈并初始化
​	int top = -1;
​	BTNode *p = T, *r = NULL;				//r指向最近访问的点
​	while (top != -1 || p != NULL)				//栈非空或树未遍历完时
​	{​		if (p)							//走到最左边
​		{​			stack[++top] = p;				//入栈
​			p = p->lchild;				//遍历左子树
​		}
​		else							//向右
​		{​			p = stack[top--];				//出栈
​			if (p->rchild && p->rchild != r)	//若右子树存在并且未被访问
​			{​				stack[++top] = p;			//再次入栈，因为还没访问完
​				p = p->rchild;			//遍历右子树
​			}
​			else						//否则，弹出结点并访问
​			{​				visit(p);				//执行结点
​				r = p;					//标记结点
​				p = NULL;				//指针设为空，因为要返回双亲结点
​			}
​		}
​	}
}
4.层序遍历

算法思想：借助队列,1.将根结点入队。2.出队并将其左右子树（若存在）依次入队。重复2，直至队空

void Level_order(BiTree T)
{​	if (!T) return;
​	BTNode* Q[10];			//初始化队
​	int front = 0, rear = 0;
​	BTNode *p = NULL;
​	Q[rear++] = T;
​	while (front< rear)		//队非空
​	{​		p = Q[front++];		//出队
​		visit(p);
​		if (p->lchild)		//左右子树入队
​			Q[rear++] = p->lchild;
​		if (p->rchild)
​			Q[rear++] = p->rchild;
​	}
}
5.求二叉树的层数

①非递归（层序遍历）

算法思想：设置标记层数的depth和一个指向下一行最后一个结点的指针p。1.根入队，设置p=rear2.队头出队并将左右子树入队，若当前行已经遍历完即front=tag，则层数+1并且更新p=rear。

int Tree_Depth2(BiTree T)
{​	if (T == NULL)	return 0;
​	BiTree Q[Max_Size], p;			//创建队列和辅助指针p
​	int front = 0, rear = 0;
​	Q[rear++] = T;					//根入队
​	int depth = 0, tag = rear;			//下一层最后一个为rear=1
​	while (front< rear)				//队非空
​	{​		p = Q[front++];				//队头出队
​		if (p->lchild)	Q[rear++] = p->lchild;
​		if (p->rchild)	Q[rear++] = p->rchild;
​		if (front == tag)				//当遍历完当前行最后一个后
​		{​			depth++;				//层数增加并更新标记最后结点的tag
​			tag = rear;
​		}
​	}
​	return depth;
}

②递归

int Tree_Depth(BiTree T)
{​	if (T == NULL)
​		return 0;
​	int ldepth = Tree_Depth(T->lchild);
​	int rdepth = Tree_Depth(T->rchild);
​	if (ldepth >rdepth)
​		return ldepth+1;
​	else
​		return rdepth+1;
}
6.求结点所在层数

①非递归（简化）

用5①的非递归，当发现所查结点时输出depth+1（因为这时当前行还没运行完，depth还没有+1）

while (front< rear)				//队非空
{​	p = Q[front++];	//队头出队
​	if (p == x) return depth + 1;	//若找到则返回深度
​	if (p->lchild)	Q[rear++] = p->lchild;
​	if (p->rchild)	Q[rear++] = p->rchild;
​	if (front == tag)				//当遍历完当前行最后一个后
​	{​		depth++;				//层数增加并更新标记最后结点的tag
​		tag = rear;
​	}
}

②递归

思想：若当前结点为空则返回0；若找到该结点则返回该结点的层数；遍历左右子树，若左右子树大于0则表示找到了，返回左/右子树的返回值

int Level(BTree T, BTNode* p, int depth)
{if(!T) return 0;
    if(T==p)  return depth;
    int L = Level(T->lchild, p, depth+1);
    if(L>0)  return L;			//即找到了
    int R = Level(T->lchild, p, depth+1);
    if(R>0)  return R;			//即找到了
    return -1;					//未找到
}
7.求树的宽度

①非递归int Width_Depth(BiTree T)（简化）

算法思想：利用5①的非递归遍历，在遍历每一行的时候都计算下一行的个数count=front-rear

int count=1, width=1;				//count表示下一行的结点个数，max表示树的宽度(大count)
​	while (front< rear)				//队非空
​	{​		p = Q[front++];	//队头出队
​		if (p->lchild)	Q[rear++] = p->lchild;
​		if (p->rchild)	Q[rear++] = p->rchild;
​		if (front == tag)						//当遍历完当前行最后一个后
​		{tag = rear;
width= rear - front;				//计算当前行的个数
​			if (width>max)		max = width;	//更新大width
​		}
​	}
​	return width;	//返回width

②递归

算法思想：开辟一个数组count[二叉树高度],遍历每一个节点,然后根据当前节点所在层次i,则执行count[i]++;最后遍历完求出大的count即为二叉树宽度

int count[10];
int Max = -1;
void FindWidth(BiTree T, int k)
{​	if (!T)	return;
​	count[k]++;						//k层结点数+1
​	if (Max< count[k])	Max = count[k];		//更新大的count
​	FindWidth(T->lchild, k + 1);			//遍历左右子树
​	FindWidth(T->rchild, k + 1);
}
8.交换二叉树所有结点的左右子树

①算法思想：使用层序遍历，但是在每次将左右子树入队时改为右左的顺序入队

②递归：算法思想：先序遍历（中序也可）左右子树，并且每次遍历将左右子树互换

void swap(BiTree T)
{   BiTree q;		//左右子树互换
​	q = T->lchild;
​	T->lchild = T->rchild;
​	T->rchild = q;	
    swap(T->lchild);//递归交换左右孩子的左右子树
​	swap(T->rchild);	
}
9.求叶子结点个数-递归

算法思想：1.若结点为空则返回0；2.若结点为叶子结点则返回1；3.否则返回左子树和右子树叶子结点的和。递归调用

int Degree0(BiTree T)
{​	if (!T)	return 0;
​	if (T->lchild == NULL && T->rchild == NULL)	return 1;	//若为叶子结点，返回1
​	else return Degree0(T->lchild) + Degree0(T->rchild);		//否则返回左右子树叶子数相加
}
10.求度为2的结点个数-递归

算法思想：1.若结点为空则返回0；2.若结点度为2则返回1+左右子树度为2的结点之和；3.否则返回左子树和右子树叶子结点的和。递归调用

int Degree2(BiTree T)
{​	if (!T)	return 0;
​	if (T->lchild != NULL && T->rchild != NULL)			//若度为2，则		
return 1+ Degree2(T->lchild) + Degree2(T->rchild);	//返回左右子树的度为2的结点个数和+1
​	else return Degree2(T->lchild) + Degree2(T->rchild);		//否则当前结点不是度为2，结点数不+1
}
11.求度为1的结点个数-递归

算法思想：1.若结点为空则返回0；2.若结点度为2则返回1+左右子树度为2的结点之和；3.否则返回左子树和右子树叶子结点的和。递归调用

int Degree1(BiTree T)
{​	if (!T)	return 0;
​	if (T->lchild != NULL && T->rchild == NULL)	
​		return 1+ Degree1(T->lchild) + Degree1(T->rchild);
else if (T->lchild == NULL && T->rchild != NULL)	
​	return 1+ Degree1(T->lchild) + Degree1(T->rchild);
​	else return Degree1(T->lchild) + Degree1(T->rchild);
}
12.找最近公共祖先（求祖先都用后序遍历，因为栈保存的都是其祖先）

算法思想：后序遍历当找到任意一个时保存当前栈中的元素，若两个都找到后退出循环并遍历找公共组先

BTNode* PrintParents_qp(BiTree T, BTNode *x,BTNode *y)
{​	if (!T) return NULL;
​	BTNode *stack[10], *a[10], *b[10], *p = T, *r = NULL;//初始化栈
​	int top = -1, pa = 0, pb = 0;
​	while (top != -1 || p != NULL)				//栈非空或树未遍历完
​	{​		if (p)							//走到最左边
​		{​			if (p == x)					//若找到x，则保存此时的栈
​			{​				for (int i = 0; i<=top; i++)
​					a[i] = stack[i];
​				pa = top;
​			}
​			if (p == y)					//若找到y，则保存此时的栈
​			{​				for (int i = 0; i<= top; i++)
​					b[i] = stack[i];
​				pb = top;
​			}			
stack[++top] = p;
​			p = p->lchild;
​		}
​		else
​		{​			p = stack[top--];//出栈
​			if (p->rchild&&p->rchild != r)	//若右子树并且未遍历
​			{​				stack[++top] = p;		//再把结点入栈并退出循环
​				p = p->rchild;		//右子树入栈
​			}
​			else					//否则直接继续循环
​			{​				r = p;
​				p = NULL;
​			}
​		}
​	}
​	//找公共祖先
​	int i=0;
​	for(i=0; a[i] == b[i]&&i<=pa&&i<=pb;i++) //找第一个不同的点
​	return a[i - 1];//返回前驱
}
13**.已知一颗满二叉树的先序序列为pre，求其后续序列post,二分法**

算法思想：因为先序第一个是根结点，后续最后一个是根结点，并且满二叉树的任意一个结点的左右子树均有相等的结点数，所以将先序的第一个放到后续的最后一个，再将先序除第一个结点的剩下所有结点分成两份继续执行上述操作。

void pre_post1(int pre[], int a1, int a2, int post[], int b1, int b2)
{​	int half;
​	if (a1<= a2)//若pre[]的首和尾位置合法
​	{​		post[b2] = pre[a1];
​		half = (a2 - a1) / 2;
​		pre_post(pre, a1 + 1, a1 + half, post, b1, b1 + half - 1);
​		pre_post(pre, a1 + half + 1, a2, post, b1 + half, b2-1);
​	}
}
14.二叉排序树（BST） 14.1二叉排序树插入操作

算法思想：若根为空将要插入的值设置为根节点；若树中存在相同的值则返回0；若小于结点的值则插入到左子树中；若大于结点的值则插入到右子树

int BST_Insert(BiTree &T, int key)//二叉树插入操作，因为会改变树所以用&T
{​	if (T == NULL)	//原树为空，新插入的记录为根节点
​	{​		T = (BTNode *)malloc(sizeof(BTNode));
​		T->data = key;
​		T->lchild = T->rchild = NULL;
​		return 1;	//返回1，插入成功
​	}
​	else if (T->data == key)//若树中存在相同关键字，则插入失败
​		return 0;
​	else if (T->data >key)	//插入到T的左子树中
​		return BST_Insert(T->lchild, key);
​	else					//插入到T的右子树中
​		return BST_Insert(T->rchild, key);
}
14.2二叉排序树搜索操作

算法思想：若等于结点的值或结点为空则返回结点；若小于结点的值则搜索左子树；若大于结点的值则搜索右子树

BTNode * BST_Search(BiTree T, int key)//非递归查找算法
{​	while (T&&T->data != key)//若树非空或不等于结点值
​	{​		if (key< T->data)	T = T->lchild;//若小于则向左查找
​		else	T = T->rchild;	//若大于则向右查找
​	}
​	return T;
}
14.3二叉排序树构造操作

算法思想：通过二叉树的插入算法，将数组中的所有结点都依次插入到二叉排序树中

void Creat_BST(BiTree &T, int str[], int n)//构造二叉树
{​	T = NULL;	//初始时T为空树
​	int i = 0;
​	while (i< n)	//依次将数组中的关键字插入到二叉排序树中
​	{​		BST_Insert(T, str[i]);
​		i++;
​	}
}
14.4判断是否是二叉排序树

算法思想：若当前结点小于左子树或者小于右子树则返回false，若为空返回true，否则返回左右子树相与

bool Decide(BiTree T)
{​	if (!T)	return true;
​	if (T->lchild&&T->lchild->data >T->data)	return false;
​	if (T->rchild&&T->rchild->data< T->data)	return false;
​	return Decide(T->lchild) && Decide(T->lchild);
}
15.判断是否是平衡二叉树

算法思想:设置二叉树的平衡标记balance，标记返回二叉树T是否为平衡二叉树，若为平衡二叉树则返回1，否则返回0；h为二叉树T的高度。采用后序遍历的递归算法：

①若T为空，则高度为0，balance=1；

②若T为仅有根结点（即叶子结点），则高度为1，balance=1；

③否则，对T的左右子树进行递归操作，返回左右子树的高度和平衡标记，

T的高度为最高的子树的高度+1.

若左右子树的高度差大于1，则balance=0；

若左右子树的高度差小于等于1，*且左右子树都平衡时*，balance=1，否则balance=0.

void Judge_AVL(BiTree T, int &balance, int &h)//加上取地址符
//balance返回是否是平衡二叉树，若是则返回1，否则返回0；h是二叉树的高度
{​	int bl = 0, br = 0, hl = 0, hr = 0;		//左右子树的平衡标记和高度
​	if (!T) //空树，高度为0
​	{​		h = 0;
​		balance = 1;
​	}
​	else if (T->lchild == NULL && T->rchild == NULL)
​	{	//若为根结点，则高度为1
​		h = 1;
​		balance = 1;
​	}
​	else
​	{​		Judge_AVL(T->lchild, bl, hl);	//判断左子树
​		Judge_AVL(T->rchild, br, hr);	//判断右子树
​		h = (hl >hr ? hl : hr) + 1;
​			balance = bl&&br;		//若左右子树都平衡时，二叉树平衡
​		else
​			balance = 0;
​	}
}
五、串 1.存储结构

①定长顺序存储

typedef struct SString  selected选定
{char ch[Max_Size];	//每个分量存储一个字符
	int length;			//串的实际长度
}SString;

②堆分配存储

typedef struct HString  heap堆
{char * ch;			//按串长分配存储区，ch指向串的基地址
	int length;			//串的实际长度
}HString;

③块链存储(eg大小为1的链表)

typedef struct LString
{char data;			//按串长分配存储区，ch指向串的基地址
	struct LString *Next;	//指向下一个结点
}LString;
2.KMP
void get_next(String T, int next[])
{​	int i = 1, j = 0;				//i表示next的位置
​	next[1] = 0;					//初始化第一个值
​	while (i< T.length)
​	{​		if (j == 0 || T.c[i] == T.c[j])	
​		{​			next[++i] = ++j;		//若pi=pj，则next[j+1]=next[j]+1
​		}
​		else
​			j = next[j];			//否则令j=next[j]，循环继续
​	}
}

int KMP(String S, String T, int next[])
{​	int i = 1, j = 1;
​	while (i< S.length&&j< T.length)
​	{​		if (j == 0 || S.c[i] == T.c[j])
​		{​			i++; j++;
​		}
​		else
​			j = next[j];
​	}
​	if (j >T.length)//此时j=T.length+1；因为上面一步会j++
​		return i - T.length;//匹配成功
​	else
​		return 0;
}
六、栈和队列 1.栈的存储结构

①顺序存储

typedef struct Stack		//顺序栈
{​	int data[Max_Size];	//值域
​	int top;			//栈顶指针
}Stack;

②链式存储：入栈和出栈在对头进行

typedef struct LStack		//链式队列
{​	int data;			//值域
​	struct LStack *Next;	//指针域
}LStack;
2.队列的存储结构

①顺序存储

typedef struct Queue		//顺序队列的结点
{​	int data[Max_size];		//值域
​	int front, rear;			//队头指针和队尾指针
}Queue;

②链式存储

typedef struct LinkNode		//链式队列的结点
{​	int data;				//值域
​	struct LinkNode *Next;	//指针域
}LinkNode;
typedef struct LQueue		//链式队列
{​	struct LinkNode *front, *rear;	//队列的头结点和尾结点
}LQueue;
七、线性表 存储结构

①顺序存储

静态分配：

typedef struct SqList
{int data[Max_Size];	//顺序表元素
	int length;			//表长度
}SqList;

②堆分配存储

typedef struct SqList
{int * data;			//动态分配数组的指针
	int length;			//表长度
}SqList;

②链式存储

typedef struct LNode	//单链表
{​	int data;			//值域
​	struct LNode *Next;	//指针域
}LNode;

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


分享标题：考研心得：考研数据结构算法大全-创新互联
网页URL：http://abwzjs.com/article/doepjg.html

其他资讯