线性表

顺序表的定义

#define MaxSize 50
typedef struct{

	ElemType data[MaxSize]；

	int length;

}SqList;

顺序表插入

在下标为i的位置插入元素e：

bool ListInsert(SqList &L, int i, ElemType e){
	if(i<0||i>L.length||L.length==MaxSize)			//i取0到length
		return false;
	for(int j=L.length-1; j>=i; --j)
		L.data[j+1]=L.data[j];			//从后往前，逐个将元素后移一个位置
	L.data[i]=e;
	++(L.length);
	return true;
}

a	b	c	d	e	f
0	1	2	3	4	5	6

顺序表删除

删除下标为i的元素，并返回元素值e：

bool ListDelete(SqList &L, int i, ElemType &e){
	if(i<0||i>L.length-1)
		return false;
	e=L.data[i];
	for(int j=i; j<L.length-1; ++j)
		L.data[j]=L.data[j+1];
	--(L.length);
	return true;
}

顺序表按值查找

查找第一个等于e的元素，并返回其下标：

int LocateElem(SqList L, ElemType e){
	int i;
	for(i=0; i<L.length; ++i){
		if(L.data[i]==e)
			return i;
	}
	return 0;
}

元素逆置

设计一个高效算法，将顺序表所有元素逆置，要求算法的空间复杂度为O(1)：

void Reverse(SqList &L,){
	ElemType temp;		//定义一个临时变量
	for(int i=0,j=L.length-1; i<j; ++i,--j){
		temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
}

合并顺序表

将两个有序顺序表合并成新的有序顺序表，并由函数返回结果顺序表：

bool Merge(SqList A, SqList B, SqList &C){
	if(A.length+B.length>C.MaxSize)
		return false;
	int i=0,j=0,k=0;
	while(i<A.length && j<B.length){
		if(A.data[i]<=B.data[j]){		//若A中元素值小于B中元素值，则A值入C
			C.data[k]=A.data[i];
			++k;
			++i;
		}else{
			C.data[k]=B.data[j];
			++k;
			++j;
		}
	}
	while(i<A.length){				//若A中有剩余
			C.data[k]=A.data[i];
			++k;
			++i;
	}
	while(j<B.length){				//若A中有剩余
		C.data[k]=B.data[j];
			++k;
			++j;
	}
	C.length=k;
	return true;
}

单链表定义

typedef struct LNode{			//因为结构体中包含了LNode，所以定义结构体时struct后面要加LNode
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;

头插法

头插法建立单链表（天勤）

void List_HeadInsert(LNode *&C, int a[], int n){
	LNode *s;				//s用来指向新申请的结点
	int i;
	C=(LNode *)malloc(sizeof(LNode));	//申请C的头结点空间
	C->next=NULL;
	for(i=0; i<n; ++i){
		s=(LNode*)malloc(sizeof(LNode));
		s->data=a[i];
		s->next=C->next;	//新插入的s结点的next指向头结点C的next
		C->next=s;			//头结点C的next指向新建的s结点
	}
	r->next=NULL;
}

尾插法

尾插法建立单链表（天勤）

void List_TailInsert(LNode *&C, int a[], int n){
	LNode *s, *r;
	int i;
	C=(LNode *)malloc(sizeof(LNode));
	C->next=NULL;
	r=C;
	for(i=0; i<n; ++i){
		s=(LNode *)malloc(sizeof(LNode);
		s->data=a[i];
		r->next=s;		//r所在的next指向新建的s结点
		r=r->next;
	}
	r->next=NULL;
}

合并链表

A，B是两个带头结点的单链表，其中元素递增有序，设计一个算法，将A，B归并成一个按元素值非递减有序的链表C，C由A和B中的结点组成。

void Merge(LNode *A, LNode *B, LNode *&C){
	LNode *p=A->next;
	LNode *q=B->next;
	LNode *r;			//r始终指向C的终端结点
	C=A;
	C->next=NULL;
	free(B);
	r=C;
	while(p!=NULL && q!=NULL){
		if(p->data<=q->data){
			r->next=p;
			p=p->next;
			r=r->next;
		}
		else{
			r->next=q;
			q=q->next;
			r=r->next;
		}
	}
	r->next=NULL;
	if(p!=NULL)			//将剩余结点链接在C的尾部
		r->next=p;
	if(q!=NULL)
		r->next=q;
}

栈与队列

基本概念

当n个元素以某种顺序进栈，并在任意时刻出栈，排列数目 N=$\frac{1}{n+1}$ KaTeX parse error: Undefined control sequence: \C at position 1: \̲C̲_{2n}^{n}=$\frac{(2n)!}{(n+1)(n!{)}^2}$

栈：先进后出； 队列：先进先出；

当较大的数首先出栈时，较小的数都是降序压在栈内的。

循环队列：

​ 队空状态：qu.rear==qu.front;

​ 队满状态：(qu.rear+1)%maxSize==qu.front;

递归过程或者函数调用时，处理参数及返回地址要用栈。

串是一种特殊的线性表，其数据元素是一个字符。

树与二叉树

基本概念

结点数 = 度数 + 1

度为m的树第i层至多有 m^i-1 个结点

高度为h的m叉树至多有(m^h-1)/(m-1)个结点

具有n个结点的m叉树最小高度为 $\lceil$ log_m^(n(m-1)+1)$\rceil$

非空二叉树上叶子结点数等于双分支结点数加1

总结点数=n₀+n₁+···+n_m ①

总分支数=1n₁+2n₂+···+m*n_m ②

总分支数=总结点数-1 ③

由①②③得 n₀=1+n₂+2n₃+···+(m-1)n_m

二叉树的第i层上最多有 2^i-1个结点

高度为k的二叉树上最多有2^k-1个结点

具有n个结点的完全二叉树的深度为$\lfloor$log₂n$\rfloor$+1

在哈夫曼二叉树中任何一个序列都不是另一个序列的前缀，且树中不含单分支结点

二叉树链式存储结构定义

typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

二叉树遍历

先序遍历递归（根左右）

void PreOrder(BiTree T){
	if(T!=NULL){
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

中序遍历递归（左根右）

void InOrder(BiTree T){
	if(T!=NULL){
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
}

后序遍历递归（左右根）

void PostOrder(BiTree T){
	if(T!=NULL){
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}

先序遍历递归（根左右）

void PreOrder(BiTree T){
	InitStack(S);
	BiTree T;
	while(p||!IsEmpty(S)){		//栈不空或p不空时循环
		if(p){					//一路向左
			visit(p);
			Push(S,p);
			p=p->lchild;
		}
		else{
			Pop(S,p);
			p=p->rchild;
		}
	}
}

中序遍历非递归（左根右）

void InOrder(BiTree T){
	InitStack(S);
	BiTree p=T;
	while(p||!IsEmpty(S)){		//栈不空或p不空时循环
		if(p){
			Push(S,p);
			p=p->lchild;
		}
		else{
			Pop(S,p);
			visit(p);
			p=p->rchild;
		}
	}
}

后序遍历非递归（左右根）

void PostOrder(BiTree){
	InitStack(S);
	p=T;
	r=NULL;
	while(p||!IsEmpty(S)){
		if(p){								//走到最左边
			Posh(S,p);
			p=p->lchild;
		}
		else{								//向右
			GetTop(S,p);					//读栈顶结点（非出栈）
			if(p->rchild && p->rchild!=r){	//若左子树存在且未被访问过
				p=p->rchild;				//转向右
				Push(S,p);					//压栈
				p=p->lchild;				//再走到最左
			}
			else{							//否则，弹出结点并访问
				Pop(S,p);					//出栈
				visit(p->data);
				r=p;						//记录最近访问过的结点
				p=NULL;
			}
		}
	}
}

层次遍历

void LevelOrder(BiTree T){
	InitQueue(Q);		//初始化辅助队列
	BiTree T;
	EnQueue(Q,T);		//根节点入队
	while(!IsEmpty(Q)){
		DeQueue(p);		//队头结点出队
		visit(p);
		if(p->lchild!=NULL)		//若左子树不空，左子树根节点入队
			EnQueue(Q,p->lchild);
		if(p->rchild!=NULL)
			EnQueue(Q,p->rchild);
	}
}

图

基本概念

有向完全图：若有向图有n个顶点，则最多有n(n-1)条边，将具有n(n-1)条边的有向图成为有向完全图。

无向完全图：若无向图有n个结点，则最多有n(n-1)/2条边，将具有n(n-1)/2条边的有向图成为无向完全图。

连通图：如果图中任意两个顶点都连通，则称该图为连通图；否则，图中的极大连通子图称为连通分量。

强连通图：在有向图中，从v_i到v_j和从v_j到v_i都有路径，则称该图为强连通图；否则将其中的极大强连通子图称为强连通分量。

图的定义

邻接矩阵定义

#define MaxVertexNum 100		//顶点数目的最大值
typedef char VertexType;		//顶点的数据类型
typedef int EdgeType;			//带权图中边上权值的数据类型
typedef struct{
	VertexType Vex[MaxVertexMum];	//顶点表
	EdgeType Edge[MaxVertexMum][MaxVertexNum];	//邻接矩阵，边表
	int vexnum, arcnum;			//图当前的定点数和边数
}

邻接表存储结构定义

#define MaxVertexNum 100		//图中顶点数的最大值
typedef struct ArcNode{			//边表结点
	int adjvex;					//该弧指向的顶点的位置
	struct ArcNode *next;		//指向下一条弧的指针
}ArcNode;
typedef struct VNode{			//顶点表结点
	VertexType data;			//顶点信息
	ArcNode *first;				//指向第一条依附该顶点的弧的指针
}VNode, AdjList[MaxVertexNum];
typedef struct{					
	AdjList vertices;			//邻接表
	int vexnum; arcnum;			//图的顶点数和弧数
}ALGraph;						//ALGraph是以邻接表存储的图类型

图的遍历

图的广度优先遍历

bool visited[MAX_VERTEX_NUM];	//访问标记数组
void BFSTraverse(Graph G){		//对图G进行广度优先遍历
	for(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
	visit(v);	
	visited[v]=TRUE;			//对v做以访问标记
	EnQueue(Q,v);				//顶点v入队Q
	while(!isEmpty(Q)){
		DeQueue(Q,v);
		for(w=FirstNeighbor(G,v); w>=0; w=NexNeighbor(G,v,w)){	//检测v所有邻接点
			if(!visited[w]){	//w为v的尚未访问的邻接顶点
				visit(w);
				visited[w]=TRUE;
				EnQueue(Q,w);
			}
		}
	}
}

图的深度优先遍历

bool visited[MAX_VERTEX_NUM];	//建立访问标记数组
void DFSTraverse(Graph G){		//对图G进行深度优先遍历
	for(v=0; v<G.vexnum; ++v)	//将所有位置都置false
		visited[v]=FALSE;
	for(v=0; v<G.vexnum; ++v)	
		if(!visited[v])			//只要未被访问过就执行DFS
			DFS(G,v);
}
void DFS(Graph G, int v){		//从顶点v出发，深度优先遍历图G
	visit(v);
	visited[v]=TRUE;
	for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w))
		if(!visited[w]){		//若w未被访问，则执行DFS
			DFS(G,w);
		}
}

拓扑排序

拓扑排序算法实现（17年考过一次）

bool TopologicalSort(Graph G){
	InitStack(S);				//初始化栈，存储入度为0的顶点
	for(int i=0; i<G; ++i)
		if(indegree[i]==0)		//将所有入度为0的顶点进栈
			Push(S,i);
	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]))	//入度为0则入栈
				Push(S,v);
		}
	}
	if(count<G.vexnum)	//排序失败，有向图中有回路
		return false;
	else
		return true;	//排序成功
}

查找

顺序查找

typedef struct{			//查找表的数据结构
	ElemType *elem;		//元素存储空间基址，建表时按实际长度分配，0号单元留空
	int TableLen;		//表的长度
}SSTable;
int Search_Seq(SSTable ST, ElemType key){
	ST.elem[0]=key;		//“哨兵”
	for(i=ST.TableLen; ST.elem[i]!=key; --i);	//从后往前找
	return i;			//若表中不存在key，将查找到i为0时退出for循环
}

折半查找

int Binary_Search(SeqList L, ElemType key){
	int low=0, high=L.TableLen-1, mid;
	while(low<=high){
		mid=(low+high)/2;
		if(L.elem[mid]==key)
			return mid;
		else if(L.elem[mid]>key)
			high=mid-1;
		else
			low=mid+1;
	}
	return -1;
}

排序

冒泡排序

void BubbleSort(ElemType A[], int n){
	for(i=0; i<n-1; ++i){
		flag=false;				//表示本趟冒泡是否发生交换的标志
		for(j=n-1; j>i; --j){	//一趟冒泡过程
			if(A[j-1]>A[j]){	//若为逆序
				swap(A[j-1],A[j]);	//交换
				flag=true;
			}
		}
		if(flag==false)
			return 0;			//本趟遍历后没有发生交换，说明表已有序
	}
}

快速排序

void QuickSort(ElemType A[], int low, int high){
	if(low<high){									//递归跳出的条件
	//Partition()就是划分操作，将表A[low···high]划分为满足上述条件的两个子表
		int pivotpos=Partition(A,low,high);	//划分
		QuickSort(A,low,pivotpos-1);		//依次对两个子表进行递归排序
		QuickSort(A,pivotpos-1,high);
	}
}
int Partition(ElemType A[], int low, int high){		//一趟划分
	ElemType pivot=A[low];	//将表中第一个元素设为枢轴，对表进行划分
	while(low<high){		//循环跳出条件
		while(low<high && A[high]>=pivot)
			--high;
		A[low]=A[high];		//将比枢轴小的元素移动到左端
		while(low<high && A[low]<=pivot)
			++low;
		A[high]=A[low];		//将比枢轴大的元素移动到右端

	}
	A[low]=pivot;			//枢轴元素存放到最终位置
	return low;				//返回存放枢轴的最终位置
}

简单选择排序

void SelectSort(ElemType A[], int n){
	for(i=0; i<n-1; ++i){
		min=i;							//记录最小元素位置
		for(j=i+1; j<n; ++j)			//在A[i...n-1]中选择最小的元素
			if(A[j]<A[min])				//更新最小元素位置
				min=j;
		if(min!=i)						//封装的swap()函数共移动元素3次
			swap(A[i],A[min]);
	}
}

各种排序的算法性质