引言

这篇博文记录大二数据结构与算法课程的内容，不定时更新。

栈

一、Ackerman函数

Ackerman函数有$A(n,m)$有两个独立的整变量$m\ge0,n\ge0$，其定义如下

$A(1,0)=2$

$A(0,m)=1 ,m\ge0$

$A(n,0)=n+2, n\ge2$

$A(n,m)=A(A(n-1,m),m-1), n\ge1且m\ge1$

根据定义式可以简单地写出它的递归代码：

int Ackerman(int n,int m){
  if(n<0 || m<0)return -1;	//无定义
	if(n==1 && m==0)return 2;
	if(n==0)return 1;
	if(m==0)return n+2;
  return Ackerman(Ackerman(n-1,m),m-1);
}

字符串

一、子串定位：KMP算法

1、算法思路

定义主串串为目标串S，子串为模式串P。在朴素模式匹配算法中，每次匹配不成功之后，模式串只是向后移动1位，即存在大量回溯；我们可以利用部分匹配的结果，让模式串在不匹配时可以往后移动尽量远的距离，减少匹配次数。

KMP算法只针对模式串进行分析，对模式串求出数组Next[j]，在模式串第j位比较失败之后利用Next[j]得到往后移几位。

Next数组的实质是找模式串中的最长相同的前缀和后缀（前缀不包括最后一个字符，后缀不包括第一个字符），实际意义为k=模式串第j位前的子串最长相同的前缀和后缀的长度+1，即将子串移动至第k位再次进行比较，如图所示。

$Next[j] =\begin{cases} 0, j=1时 \\ Max \{ k | 1<k<j \ and\ p_1p_2…p_{k-1}= p_{j-k+1}…p_{j-1} \} \\ 1,其它情况 \end{cases}$

j	1	2	3	4	5	6	7
S	a	b	a	c	a	b	c
Next[j]	0	1	1	2	1	2	3
NextVal[j]	0	1	0	2	0	1	3

根据上式，假设我们已经求出了next[j]数组，再将下标j按照C++的规则从0开始，就可以得到KMP算法的基本代码：

int KMP(string s,string t){
	int i=0,j=0;
	int n=s.size(),m=t.size();
	while(i<n && j<m){
		if(j==-1 || s[i]==t[j]){
			i++;
			j++；
		}
		else{
			j=next[j];
		}
	}
	if(j==m)return i-j;
	else return -1;
}

2、Next数组

我们的代码依赖了数组next[j]，next数组的定义上面已经说明，但它的求法更加精妙，首先我们贴出它的代码：

/*
这个算法得出的next[i]为最长前后缀的长度，即代表最长前缀的下一个字符的位置
*/
void getNext(string s){
    next[0]=-1;
    next[1]=0;
    int i=2;//i代表填充next数组的i位置
    int cn=0;//cn始终代表字符串i-1位置前面的字符串的最长前缀的下一个字符的位置
    while (i<s.size()){
  	  if(s[i-1]==s[cn])//如果字符串i-1位置上的字符等于字符串cn位置上的字符的话，直接在next[i]的基础上加1即可
  	 	 next[i++]=++cn;
 	  else if(cn>0)//这个条件满足，说明可以往前跳，让cn往前跳
         cn=next[cn];
  	  else
  	 	 next[i++]=0;//字符串i位置前面的字符串没有前缀
  	  }
}

以abacabc为例：

next[0]=-1
next[1]=0
i=2，cn=0，s[1]!=s[0]，且cn==0，next[2]=0
i=3，cn=0，s[2]==s[0]，next[3]=++cn=1
i=4，cn=1，s[3]!=s[1]，且cn>0，cn=next[1]=0，重复一次循环，i=4，cn=0，s[3]!=s[0]，next[4]=0
i=5，cn=0，s[4]==s[0]，next[4]=++cn=1
i=6，cn=0，s[5]==s[0]，next[5]=++cn=2

比较难理解的为cn=next[cn]这段代码，实际为将当前前缀长度跳回到cn这一字符的最长前缀，由于next[cn]的前后缀必相同，只需继续再次比较cn与i-1的字符即可，如图：

3、NextVal数组

观察s[4],当它不匹配时，按照next行回溯到s[1]也为字母a，这时再匹配a是徒劳的，因为已知a不匹配，所以就继续退回到s[1]字母a的next[1]=0。为了进行优化，就有了nextval:

若要求nextval[i]，将next[i]的值对应的位的值与i的值进行比较：若相等，nextval[i]=nextval[ next[i] ]；若不相等，则nextval[i]=next[i]。

代码如下：

int get_nextval(string T){
//求模式串T的next函数修正值并存入数组nextval。
	for(int i=1;i<T.size();i++){
		if(T[next[i]] == T[i])
			nextval[i]=nextval[next[i]];
		else nextval[i]=next[i];
	}
}//get_nextval

数组

一、快速转置算法

1、稀疏矩阵的三元组存储

矩阵本身的数据：行、列、元素个数

矩阵元素的数据：行序号、列序号、元素值

struct Triple{ 
  int I,j;
  elementtype e;
};	//矩阵元素

struct TSMatrix{
	Triple data[Max+1];
  int mu,nu,tu;
}; //矩阵

而由于稀疏矩阵的数据排列是行对齐的（根据行的顺序排列），所以如果进行转置，需要重新对数据进行排列，快速转置则是在尽可能少次数地遍历矩阵的情况下完成转置。

2、算法思路

首先我们给出一个$5\times5$的稀疏矩阵：

数组data	5/行	5/列	6/元素个数
0	1	1	3
1	1	5	7
2	2	3	-1
3	3	1	-1
4	3	2	-2
5	5	4	2

经过转置后，它的排列需要是这样：

数组data	5/行	5/列	6/元素个数
0	1	1	3
1	1	3	-1
2	2	3	-2
3	3	2	-1
4	4	5	2
5	5	1	7

为了预先确定矩阵M中的每一列的第一个非零元素在数组中的位置，需要先求得矩阵M中的每一列中非零元素的个数。为此，需要设置两个一维数组num[n]和cpot[n]，其中n为矩阵列数。

num[]：储存每一列非零元素的个数
cpot[]：储存每一列的第一个非零元素在数组中的位置

通过这两个数组，我们可以在仅遍历数组两次的情况下完成矩阵的转置：

在第一次遍历时，通过对列的遍历，我们可以得到num[]。
cpot[1]=0 cpot[col]=cpot[col-1]+num[col-1]
第二次遍历即可根据cpot开始元素的转置：每读取一个元素，若列为i，则将行列调换，放入新的data[cpot[data[i].j]]]之中，并将cpot[i]+1。
完成第二次遍历，完成算法。

3、代码实现

TSMatrix trans(TSMatrix mat){
	TSMatrix nmat;
	nmat.mu=mat.nu;
	nmat.nu=mat.mu;
	nmat.tu=mat.tu;
	int num[10]={0};
	int cpot[mat.nu];
	for(int i=0;i<mat.tu;i++){
		num[mat.data[i].j]++;
	}
	cpot[0]=0;
	for(int i=1;i<mat.nu;i++){
		cpot[i]=cpot[i-1]+num[i-1];
	}
	for(int i=0;i<mat.tu;i++){
		nmat.data[cpot[mat.data[i].j]].I=mat.data[i].j;
		nmat.data[cpot[mat.data[i].j]].j=mat.data[i].I;
		nmat.data[cpot[mat.data[i].j]].e=mat.data[i].e;
		cpot[mat.data[i].j]++;
	}
	return nmat;
}

二、求杨辉三角系数

1、数学模型

杨辉三角是二项式系数在三角形中的一种几何排列，即我们熟知的二项式系数$(a+b)^n=C^0_na^n+C^1_na^{n-1}b^1+\dots+C^n_nb^n$中的$C^k_n$。

如图，对于n次二项式，设第一行为n=0的系数，则n次二项式共有n+1个系数，设为0~n。

那么，我们可以发现，对于每一个n，$a_n[0]=a_n[n]=1$，且对于$0<k<n$，$a_n[k]=a_{n-1}[k-1]+a_{n-1}[k]$。

2、代码实现

这样一来，建立一个数组进行递归计算，可以简单的求出n次二项式的二次项系数。

void coff(int *a,int n){ //arr的大小为n+1
	if(n==1){
		a[0]=a[1]=1;
	}
	else{
		coff(a,n-1);
		a[n]=1;
		for(int i=n-1;i>0;i--){ //从最后一个开始，可以直接修改数组内容且不影响计算
			a[i]=a[i]+a[i-1];
		}
	}
}

3、测试函数

#define N 10
int arr[N+1];
 
int main()
{
   	coff(arr,N);
		for(int i=0;i<=N;i++){
			cout<<arr[i]<<endl;
		} 
    return 0;
}

树

一、树的存储设计

1、双亲表示法（数组）

简单的数组储存，数组内容为：

adr	info	parent
0	A	-1
1	B	0
2	C	0
3	D	2

class Tree{
		elemtype info;
    int par;
};

2、子女表示法（链表）

每个元素对应一个child链表，按顺序指向每一个孩子：

adr	info	child
0	A	->1->2
1	B	^
2	C	->3
3	D	^

class Tree{
		elemtype info;
    node* child;
};

3、子女兄弟表示法

每个元素拥有两个指针，一个指向它的第一个孩子，另一个指向它的下一个兄弟：

FirstChild	info	NextSibling
B	A	^
^	B	C
D	C	^
^	D	^

class  TreeNode{
		elemtype info;
    TreeNode *FirstChild,*NextSibling;
};

二、二叉树遍历

1、二叉树存储结构：

class TreeNode{
	elemtype data;
  TreeNode *lchild,*rchild;
  TreeNode(elemtype D,TreeNode *lc=NULL,TreeNode *rc=NULL){
  	data=D;
  	lchild=lc;
  	rchild=rc;
  }
};

2、遍历：

/*
前序遍历
*/
void PreTra(TreeNode *T){
    if(T==NULL)return;
    cout<<T->data;//此处对结点进行操作
    PreTra(T->lchild);
    PreTra(T->rchild);
    return;
}

/*
中序遍历
*/
void InTra(TreeNode *T){
    if(T==NULL)return;
    InTra(T->lchild);
    cout<<T->data;//此处对结点进行操作
    InTra(T->rchild);
    return;
}

/*
后序遍历
*/
void PosTra(TreeNode *T){
    if(T==NULL)return;
    PosTra(T->lchild);
    PosTra(T->rchild);
    cout<<T->data;//此处对结点进行操作
    return;
}

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。层序遍历就是从所在二叉树的根节点出发，自上而下，自左至右逐层访问树的结点的过程。

层序遍历的实现需要利用队列结构，首先将根节点入队，当队列中有元素时，执行以下操作：将队首元素出队，对该元素进行操作，并将该元素的左子树、右子树依次入队。

层序遍历并不需要用到递归。

/*
层序遍历
*/
void LevelTra(TreeNode *T){
    if(T==NULL)return;
    queue<TreeNode*> Q;
    Q.push(T);
    while(!Q.empty()){
    		TreeNode *S=Q.front();
    		Q.pop();
    		cout<<S->data;//对元素进行操作
    		if(S->lchild))Q.push(S->lchild);
    		if(S->rchild))Q.push(S->rchild);
    }
    return;
}

三、线索二叉树

1、存储设计

线索二叉树的存储与普通二叉树类似，但是左指针、右指针多了标识符rtag和，ltag，当rtag为1时，rchild表示后继，当rtag为0时，rchild表示右子树，左标识符同理。总而言之，只利用二叉树的空指针表示线索。

对一个确定的二叉树，分别有前序、中序、后序三种线索树，以下列二叉树为例：

它的前序遍历为ABDEC，则其前序线索树为：

2、线索化

/*
假设已经构建好二叉树T，构建中序线索树
*/
TreeNode *pre=NULL;//用于前驱线索的构建
void InitTheading(Tree *T){
		if(T){
				InitTheading(T->lchild);
				//L
				if(T->ltag==1) T->lchild=pre;//前驱
				if(pre && pre->rtag==1) pre->rchild=T;//后继
				pre=t;
				//N
				InitTheading(T->lchild);
				//R
		}
		return;
}

线索化代码需要注意的细节是前驱后继的处理，这里使用了全局变量pre存储当前操作结点的前驱，并以此得到结点T的前驱与结点pre的后继。

为了得到前序/后序线索树，只需要将上述代码的LNR交换位置。

3、任一结点前驱后继的查找

对前序线索树来说，判断流程如下：

//前驱：
  if (p->ltag==1) pre=p->lchild;
  else //如图
//后继：
  if (p->rtag==1) next=p->rchild;
  else{
      if (p->ltag==0) next=p->lchild;
      else next=p->rchild;
  }

对中序线索树来说，判断流程如下：

//前驱：
  if (p->ltag==1) pre=p->lchild;
  else {
  		pre=p->lchild;
  		while(pre->rchild){
  				pre=pre->rchild;
      }
  }
//后继：
  if (p->rtag==1) next=p->rchild;
  else{
      next=p->rchild;
  		while(next->lchild){
  				next=next->lchild;
      }
  }

对后序线索树来说，判断流程如下：

//前驱：
  if (p->ltag==1) pre=p->lchild;
  else {
  	if(p->rtag==0)pre=p->rchild;
  	else pre=p->lchild;
  }
//后继：
  if (p->rtag==1) next=p->rchild;
  else //如图

四、哈夫曼树

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

哈夫曼树可用于编码，在编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个编码。

其带权路径长度可以表示为$WPL=\sum_{k=1}^nw_kl_k$

1、存储设计

为了得到哈夫曼树，我们需要使用一种存储方式存储各个结点，为了便于算法计算，我们利用如下的结构作为结点：

class TreeNode{
		int weight;
		int par;
		int lc,rc;
};

而且我们知道，当一棵哈夫曼树有$N$个叶结点时，它的结点总数为$2N-1$，所以数组TreeNode arr[2*n-1]就是我们的哈夫曼树。

2、算法描述

假设我们得到了如下的叶结点，我们要一步一步构造哈夫曼树：

Adr	weight	par	lc	rc
0	6	-1	-1	-1
1	5	-1	-1	-1
2	8	-1	-1	-1
3	12	-1	-1	-1
4	0	-1	-1	-1
5	0	-1	-1	-1
6	0	-1	-1	-1

为了得到每一个结点，我们需要做如下步骤：

找到当前已有结点（0~k）中无父结点中最小的两个结点A、B，令其父节点为第k+1个结点。
第k+1个结点的权值为A与B的权值之和，令其左右子结点分别为A、B。
更新已有结点个数：k+=1。
将以上步骤循环n-1次，得到n-1个新结点，完成构造。

以上面为例，给出每一步的结果：

Adr	weight	par	lc	rc
0	6	4	-1	-1
1	5	4	-1	-1
2	8	-1	-1	-1
3	12	-1	-1	-1
4	11	-1	0	1
5	0	-1	-1	-1
6	0	-1	-1	-1

Adr	weight	par	lc	rc
0	6	4	-1	-1
1	5	4	-1	-1
2	8	5	-1	-1
3	12	-1	-1	-1
4	11	5	0	1
5	19	-1	2	4
6	0	-1	-1	-1

Adr	weight	par	lc	rc
0	6	4	-1	-1
1	5	4	-1	-1
2	8	5	-1	-1
3	12	6	-1	-1
4	11	5	0	1
5	19	6	2	4
6	31	-1	3	5

3、代码实现

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
 
class TreeNode{
	public:
	int info,par,lc,rc;
	TreeNode(){
     info=0; 
	 par=lc=rc=-1;
	}
};

void FindMin(int &min1,int &min2,int k,TreeNode *num){
//找到当前已有结点（0~k）中无父结点中最小的两个结点A、B
	for(int i=0;i<k;i++){
		if(num[i].par==-1){
			if(num[min1].info>num[i].info){
				min1=i;
			}
		}
	}
	for(int i=0;i<k;i++){
		if(num[i].par==-1 && i!=min1){
			if(num[min2].info>num[i].info){
				min2=i;
			}
		}
	}
	return;
}

int main(){
  int n;
	cin>>n;
	TreeNode num[2*n-1];
	for(int i=0;i<n;i++){
		cin>>num[i].info;
	}
	num[2*n-1].info=1000;
	int min1=2*n-1,min2=2*n-1;
	for(int i=0;i<n-1;i++){
	//- 更新已有结点个数：k+=1,将以上步骤循环n-1次.
		FindMin(min1,min2,n+i,num);
		num[min1].par=n+i;
		num[min2].par=n+i;
		num[n+i].info=num[min1].info+num[min2].info;
		num[n+i].lc=min1;
		num[n+i].rc=min2;
//第k+1个结点的权值为A与B的权值之和，令其左右子结点分别为A、B。
		min1=min2=2*n-1;
	}
	for(int i=0;i<2*n-1;i++){
		cout<<i<<"\t"<<num[i].info<<"\t"<<num[i].par<<"\t"<<num[i].lc<<"\t"<<num[i].rc<<endl;
	}
  return 0;
}

得到的输出和上面的表格相同

五、AVL树

图

一、存储设计

1、邻接矩阵

设图 G = (V, E)是一个有 n 个顶点的图，则图的邻接矩阵$G.arcs[n][n]$定义为： $G.arcs[i][j]=\begin{cases} 1 &若(v_i, v_j)∈E \\ 0 & else \end{cases}$

无向图的邻接矩阵是对称的，在无向图中，第 i 行/列 1 的个数就是顶点i的度。

有向图的邻接矩阵可能是不对称的，在有向图中，每个 1 **对应的列为起点 i ，对应的行为终点 j **，第 i 行 1 的个数就是顶点 i 的出度，第 j 列 1 的个数就是顶点 j 的入度。

带权图（网）：

$G.arcs[i][j]=\begin{cases} w_{ij} &v_i\ne v_j ,\ (v_i, v_j)∈E\\ 0 & v_i=v_j\\ \infin & else \end{cases}$

代码实现：

class AdjMatrix{
int mat[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
};

class MGraph{
VertexType vexs[MAX_VERTEX_NUM]; //顶点表
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //图的顶点数和弧数
};

2、邻接表

邻接表的结构如下：

// 边结点（链式）
class EdgeNode {
 public:
	int adjvex; //这条边指向哪个顶点
	int weight;	//权值
	EdgeNode* next; //指向下一条依附该顶点的边
};
// 顶点结构
class VertexNode {
 public:
	int value; //顶点的值
	EdgeNode *firstedge;	//指向第一条依附该顶点的边
};
// 图结构
class GraphList {
 public:
	VertexNode adjList[N]; //顶点信息
	int numVertex; //顶点数
	int numEdges; //边数
};

下面的图所得到的邻接表如下图所示：

adr	value	firstedge (adjvex,weight)
0	A	-> 1(10) -> 2(6) -> 3(4)
1	B	-> 2(7)
2	C	-> 1(9) -> 3(5)
3	D	-> 1(8)

已知存储结构，接下来我们需要根据输入，完成函数void createGraph(GraphList* g)，使用邻接表的方式来实现有向图的创建。输入包含3个部分：

两个整数v、e，表示图的顶点与边的个数。
v个数，表示各个顶点的值。
e行输入，每行有三个数：vi、vj、w，分别表示从结点i到结点j的边与其权值。

void createGraph(GraphList* g){
	int v,e;
	cin>>v>>e;
	g->numVertex=v;
	g->numEdges=e;
	//图的顶点与边的个数，构建图
	for(int i=0;i<v;i++){
		cin>>g->adjList[i].value;
	}//各个顶点的值，构建顶点
	for(int i=0;i<e;i++){
		int vi,vj,w;
		cin>>vi>>vj>>w;
		EdgeNode* newe=new EdgeNode;//创建一条新的边
		newe->weight=w;//边的权值
		newe->adjvex=vj;//边指向vj
		EdgeNode *p;
		p=g->adjList[vi].firstedge; //这条边以vi开头
		if(p==NULL){
			g->adjList[vi].firstedge=newe;
		}
		else {
			while(p->next != NULL){
				p=p->next;
			}
			p->next=newe;
		}//将这条边连接至边结点的最后
	}//构建边
}

在邻接表中，我们可以通过g->adjList[i]访问每一个顶点；令p=g->adjList[i].firstedge，则p所指向的链表的长度为点i的出度；如果需要得到点i的入度，需要依次访问所有的点，统计所有的p->adjvex：

int count[g->numVertex];//统计入度
for(int i=0;i<g->numVertex;i++){
  	count[i]=0;
}
for(int i=0;i<g->numVertex;i++){
		EdgeNode *p=g->adjList[i].firstedge;
		while(p){
				count[p->adjvex]++;
				p=p->next;
		}
}

二、图的遍历

1、深度优先搜索DFS

从图中的某个顶点v出发，访问之；
依次从顶点v的未被访问过的邻接点出发，深度优先遍历图，直到图中所有和顶点v有路径相通的顶点都被访问到；
若此时图中尚有顶点未被访问到，则另选一个未被访问过的顶点作起始点，重复上述（1）（2）的操作，直到图中所有的顶点都被访问到为止。（递归执行，与树的前中后序遍历思路相似）

代码实现如下：

/*
图以邻接表形式储存
*/
void DFS(GraphList *g,int i,int *visited){
	cout<<g->adjList[i].value<<" "; //访问该点
	visited[i]=1;//已访问标记
	EdgeNode *p;
	p=g->adjList[i].firstedge;//找到该点的第一个邻接点
	while(p!=NULL){
		if(visited[p->adjvex]==0)
       	DFS(g,p->adjvex,visited);//当该邻接点未被访问时，递归访问该邻接点
		p=p->next;//寻找下一个邻接点
	}
}

void DFSTraverse(GraphList *g){
	int *visited= new int [g->numVertex];
	for(int i=0;i<g->numVertex;i++){
		visited[i]=0;
	} //visited数组记录点是否已经访问
	for(int i=0;i<g->numVertex;i++){//依次访问图中顶点
		if(visited[i]==0)DFS(g,i,visited);//当该点没被访问过，进行深度优先搜索
	}
	delete [] visited;
}

2、广度优先搜索BFS

从图中的某个顶点v出发，访问之；
依次访问顶点v的各个未被访问过的邻接点，将v的全部邻接点都访问到；
分别从这些邻接点出发，依次访问它们的未被访问过的邻接点，直到图中所有已被访问过的顶点的邻接点都被访问到。（利用队列结构实现，与层序遍历思路相似）

代码实现如下：

/*
图以邻接表形式储存
*/
void BFS(GraphList *g,int i,int *visited){
	cout<<g->adjList[i].value<<" "; //访问该顶点
	visited[i]=1;	//已访问标记
	queue<int> q;	
	q.push(i); //将起始点入队
	while(!q.empty()){
	//每个while循环将一个顶点出队，并依次访问其所有邻接点
		int w=q.front();
		q.pop();
		EdgeNode *p;
		p=g->adjList[w].firstedge;//用于访问所有邻接点
		while(p!=NULL){//访问邻接链表中的所有邻接点
			if(visited[p->adjvex]==0){
				cout<<g->adjList[p->adjvex].value<<" "; //访问该顶点
				visited[p->adjvex]=1;//已访问标记
				q.push(p->adjvex);
			}
			p=p->next;
		}
	}
}

void BFSTraverse(GraphList *g){
	int *visited= new int [g->numVertex];
	for(int i=0;i<g->numVertex;i++){
		visited[i]=0;
	}//visited数组记录点是否已经访问
	for(int i=0;i<g->numVertex;i++){
		if(visited[i]==0)BFS(g,i,visited);//依次对未被访问过的顶点进行广度优先搜索
	}
	delete [] visited;
}

三、最小生成树

尽可能用网络中权值最小的边；
必须使用且仅使用 n-1 条边来联结网络中的 n个顶点；
不能使用产生回路的边。

1、Prim算法

选择新的边时必须有一个顶点在已构成的树中。

假设共有n个顶点，我们需要设置一个辅助数组closedge[n]，该数组包含两个元素：

lowcost[i]：（当前操作时）生成树内顶点与该顶点相连的最短的边的权值；起始顶点为0，未直接相连的顶点为∞。
adjvex[i]：（当前操作时）与该顶点距离最近的生成树内顶点的值，生成树内的顶点的该值为-1。

class closedge{
	int lowcost,adjvex;
};//辅助数组

class TreeNode{
	int vi,vj;
	int weight;
};//生成树

以下图为例，我们一步步得到最小生成树。

首先将0作为起始点，初始化数组：
我们需要进行n-1次循环，每次循环将一个点加入最小生成树中；
在每一次循环中，寻找adjvex[i]!=-1中lowcost[i]最小所对应的i，对i进行操作：
将该顶点加入生成树中：adjvex[i]=-1，并将边[i,j,w]存入生成树集合；
读取与该顶点相连的边[i,j]，当adjvex[j]!=-1时（不形成环），比较每条边的权值与lowcost[j]的大小，令其取最小值，并令adjvex[j]=i；
完成所有循环后，说明adjvex[i]的值均为-1，lowcost[i]的和为总权值。

N	0	1	2	3	4	5	6
lowcost	0	28	∞	∞	∞	10	∞
adjvex	-1	0	0	0	0	0	0

N	0	1	2	3	4	5	6
lowcost	0	28	∞	∞	25	10	∞
adjvex	-1	0	0	0	5	-1	0

N	0	1	2	3	4	5	6
lowcost	0	28	∞	22	25	10	24
adjvex	-1	0	0	4	-1	-1	4

N	0	1	2	3	4	5	6
lowcost	0	28	12	22	25	10	18
adjvex	-1	0	3	-1	-1	-1	3

N	0	1	2	3	4	5	6
lowcost	0	16	12	22	25	10	18
adjvex	-1	2	-1	-1	-1	-1	3

N	0	1	2	3	4	5	6
lowcost	0	16	12	22	25	10	14
adjvex	-1	-1	-1	-1	-1	-1	1

N	0	1	2	3	4	5	6
lowcost	0	16	12	22	25	10	14
adjvex	-1	-1	-1	-1	-1	-1	-1

最终得到最小生成树：

我们以邻接表存储图，代码实现该算法：

class closedge{
	int lowcost,adjvex;
};//辅助数组

class TreeNode{
	int vi,vj;
	int weight;
};//生成树

void Prim(GraphList G, MST& T, int u ) {//u为起点 
	float lowcost[NumVertices];
	int nearvex[NumVertices];
	for ( int i = 0; i < NumVertices; i++ ) {
		lowcost[i] = G.Edge[u][i]; //Vu到各点代价
		adjvex[i] = u; //及最短带权路径
	} 
	adjvex[u] = -1; //加到生成树顶点集合
	int k = 0; //存放最小生成树的结点
	for ( i = 0; i < G.n; i++ )//循环n-1次, 加入n-1条边
		if ( i != u ) { 
				EdgeData min = MaxValue; 
		int v = 0;
		for ( int j = 0; j < NumVertices; j++ )
			if ( adjvex[j] != -1 && lowcost[j] < min ){ // =-1不参选
				v = j; 
				min = lowcost[j]; 
			}
		//求生成树外顶点到生成树内顶点具有最小权值的边, v是当前具最小权值的边
		if ( v ) { //v=0表示再也找不到要求顶点
			T[k].tail = adjvex[v]; //选边加入生成树
			T[k].head = v;
			T[k].cost = lowcost[v];
			k++; 
			adjvex[v] = -1; //该边加入生成树标记
			for ( j = 0; j < G.n; j++ )
			if ( adjvex[j] != -1 && G.Edge[v][j] < lowcost[j] ) {
				lowcost[j] = G.Edge[v][j]; //修改
				adjvex[j] = v;
			}
		} 
	}
} 

2、Kruskal算法

选择新的边时选择最小的不成环的边构成树。

代码实现：

typedef int Vertex;//顶点信息 
struct Edge//边的信息 
{
	Vertex begin;
	Vertex end;
	int edge;//边的权值 
};
int n;//顶点数 
int m;//边的数目
Edge Graph[5000];//以边存储图 
int pre[110];//并查集基本操作 
int sum;//最小的生成树权值和  
void Init()
{
	for(int i=1;i<=n;i++)
	{
		pre[i]=i;
	}
}
int find(int x)
{
	int r=x;
	while(pre[r]!=r)
		r=pre[r];
	int i=x,j;
	while(i!=r)
	{
		j=pre[i];
		pre[i]=r;
		i=j;
	}
	return r;
}
void join(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
		pre[fx]=fy;
}
bool comp(Edge a,Edge b)//对边权值进行排序 
{
	return a.edge<b.edge;
}
void Kruskal() 
{
	sort(Graph,Graph+m,comp);//排序，最小权值的边最先 
	int number=0; //记录当前用于连接顶点的边数 
	Init();//初始化并查集 
	sum=0;
	for(int i=0;i<m;i++)
	{
		if(number==n-1)//n个顶点若连接n-1条边，则图已经连通 
			break;
		if(find(Graph[i].begin)!=find(Graph[i].end))//当前边所连接的顶点处于未连通的状态 
		{
			join(Graph[i].begin,Graph[i].end);
			sum+=Graph[i].edge;
			number++;
		}
	}
}

四、AOV网（拓扑排序）

1、算法思路

输入AOV网。令n为顶点个数。
在AOV网络选一个入度为0的顶点,并输出之;
从图中删去该顶点, 同时删去所有以它为出度的有向边，更新剩余点的入度;
重复以上2、3步, 直到全部顶点均已输出，拓扑序列形成，拓扑排序完成；或图中还有未输出的顶点, 但已跳出处理循环：说明图中还剩下的顶点入度都不为0，这时网络中必存在有向环。
为了得到所有顶点的入度，我们在邻接表中增设一个数组count[ ]，记录各顶点入度。
使用一个存放入度为0的顶点的链式栈/队列, 供选择和输出入度为0的顶点。

2、代码实现

void Graphcircle(GraphList *g){
	int count[g->numVertex],del[g->numVertex];
		for(int i=0;i<g->numVertex;i++){
			count[i]=0;
		}
	for(int i=0;i<g->numVertex;i++){
		EdgeNode *p=g->adjList[i].firstedge;
		while(p){
			count[p->adjvex]++;
			p=p->next;
		}
	}//初始化count,得到所有顶点的入度
	stack<int> sta;
	int num=0;
	for(int i=0;i<g->numVertex;i++){
		if(count[i]==0){
			sta.push(i);
		}
	}//将初始时所有入度为0的顶点入栈 
	while(!sta.empty()){
		int w=sta.top();
		sta.pop();//弹出一个顶点，对其进行操作
		//cout<<g->adjList[w].value; //输出排序
		num++;//统计弹出顶点数
		EdgeNode *p=g->adjList[w].firstedge;//访问该顶点的邻接点
		while(p){
			count[p->adjvex]--;
      if(count[p->adjvex]==0){
         sta.push(p->adjvex);
      }//更新剩余顶点的入度，并马上判断是否有新的顶点入度为0
			p=p->next;
		}
	} 
	 if(num==g->numVertex) cout<<"no circle";//无环，得到拓扑排序
	 else cout<<"has circle";//有环
}

五、AOE网

1、定义

无有向环的带权有向图中：

用有向边表示一个工程中的各项活动(Activity)
用边上的权值表示活动的持续时间(Duration)
用顶点表示事件(Event)

2、求完成工程所需最短时间

入度为零的点叫源点，出度为零的点叫汇点。完成整个工程所需的时间取决于从源点到汇点的最长路径长度，这条路径长度最长的路径就叫做关键路径，路径上的活动叫做关键活动。

使用邻接矩阵mat[][]存储图，利用4个辅助数组ve[]，vl[]，e[]，l[]进行计算，以下的顶点$v_0$指所有入度为零的点，顶点$v_{n-1}$指所有入度为零的点：

ve[i]：事件最早发生时间，源点$v_0$到顶点$v_i$的最长路径长度。

可从ve[0]开始递推，ve[0]=0，ve[j]=max(ve[j]，ve[i]+mat[i][j])，此时必须确保点i的最早发生时间已确定，具体实现时需要使用拓扑排序。

vl[i]：事件最迟允许时间，是在保证汇点$v_{n-1}$在ve[n-1] 时刻完成的前提下，事件$v_{i}$的允许的最迟开始时间。

可从vl[n-1]开始递推，vl[n-1]=ve[n-1]，vl[i]=min(vl[i]，vl[j]-mat[i][j])，此时必须确保点j的最迟允许时间已确定，具体实现时需要逆序使用拓扑排序。

设活动k在路径<i,j>上：

e[i]：活动最早发生时间，直接通过e[k] = ve[i]得到即可。

l[i]：活动最迟允许时间，直接通过l[k] = vl[j] - mat[i][j]得到。

当l[k] == e[k]时，活动k就是关键活动，所有关键活动组成关键路径。

3、代码实现

void AOE(){
	int n,m;
	cin>>n>>m;
	int mat[n][n],ve[n],vl[n],e[m],l[m],edge[m][2];
	for(int i=0;i<n;i++){
		ve[i]=-1;
		vl[i]=999;
		for(int j=0;j<n;j++)
			mat[i][j]=0;
	}
	for(int i=0;i<m;i++){
		int a,b,w;
		cin>>a>>b>>w;
		mat[a][b]=w;
		edge[i][0]=a;
		edge[i][1]=b;
	}
	
	//拓扑 
	int count[n];
	for(int i=0;i<n;i++){
        count[i]=0;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(mat[i][j]>0)count[j]++;
		}
	}
	stack<int> sta,last;
	int num=0;
	for(int i=0;i<n;i++){
		if(count[i]==0){
			sta.push(i);
			ve[i]=0;
		}
	}//第一个入栈 
	while(!sta.empty()){
		int w=sta.top();
		sta.pop();
        //cout<<w<<endl;
        {
        	last.push(w);
        }
		for(int i=0;i<n;i++){
			if(i!=w && mat[w][i]!=0){
				count[i]--;
				ve[i]=max(ve[i],ve[w]+mat[w][i]);
				if(count[i]==0){
					sta.push(i);
           		 }
			}			
            
		}
	}
	int w=last.top();
	vl[w]=ve[w];
	while(!last.empty()){
		int w=last.top();
		last.pop();
		for(int i=0;i<n;i++){
			if(i!=w && mat[i][w]!=0){
				vl[i]=min(vl[i],vl[w]-mat[i][w]);
			}			   
		}
	}
	
	for(int i=0;i<m;i++){
		e[i]=ve[edge[i][0]];
		l[i]=vl[edge[i][1]]-mat[edge[i][0]][edge[i][1]];
	} 
	
	for(int i=0;i<n;i++){
		cout<<ve[i]<<"\t";
	}
	cout<<endl;
	for(int i=0;i<n;i++){
		cout<<vl[i]<<"\t";
	}cout<<endl;
	
	for(int i=0;i<m;i++){
		cout<<e[i]<<"\t";
	}
	cout<<endl;
	for(int i=0;i<m;i++){
		cout<<l[i]<<"\t";
	}
	cout<<endl;
	return 0;
}

六、最短路径

1、从一个起点到任意顶点的最短路径：Dijkstra算法

为了实现算法，我们引用3个辅助数组：

dist[i]：用于记录到点i的最短路径长度。
path[i]：用于记录到点i的最短路径的前一个顶点。
S[i]：记录点i是否已知最短路径。

算法步骤如下——

初始化辅助数组；
找到未知最短路径中路径最短的顶点，加入已知顶点中（操作S）；
修改以该顶点为起点的顶点的最短路径与上一个顶点（操作dist和path）；
重复n-1次，直到所有顶点都已知。

以下面的图为例：

初始化：

i	v1	v2	v3	v4	v5	v6
dist[i]	∞	20	∞	0	∞	15
path[i]	-1	4	-1	4	-1	4
S[i]	0	0	0	1	0	0

V6：

i	v1	v2	v3	v4	v5	v6
dist[i]	∞	20	∞	0	∞	15
path[i]	-1	4	-1	4	-1	4
S[i]	0	0	0	1	0	1

V2：

i	v1	v2	v3	v4	v5	v6
dist[i]	30	20	∞	0	50	15
path[i]	2	4	-1	4	2	4
S[i]	0	1	0	1	0	1

V1：

i	v1	v2	v3	v4	v5	v6
dist[i]	30	20	45	0	50	15
path[i]	2	4	1	4	2	4
S[i]	1	1	0	1	0	1

V3：

i	v1	v2	v3	v4	v5	v6
dist[i]	30	20	45	0	50	15
path[i]	2	4	1	4	2	4
S[i]	1	1	1	1	0	1

V5：

i	v1	v2	v3	v4	v5	v6
dist[i]	30	20	45	0	50	15
path[i]	2	4	1	4	2	4
S[i]	1	1	1	1	1	1

代码实现如下：

void Dijkstra(){
	int n,m,v;//顶点数n、边数m、起点v 
	cin>>n>>m>>v;
	int mat[n][n];//邻接矩阵 
	int dist[n],path[n],S[n];//三个辅助数组 
	for(int i=0;i<n;i++){
		dist[i]=0;
		path[i]=-1;
		S[i]=0;
		for(int j=0;j<n;j++)
			mat[i][j]=0;
	}//数组初始化 
	for(int i=0;i<m;i++){
		int a,b,w;
		cin>>a>>b>>w;
		mat[a][b]=w;
	}//邻接矩阵输入 
	dist[v]=0;
	path[v]=v;
	S[v]=1;
	for(int i=0;i<n;i++){
		if(mat[v][i]>0){
				dist[i]=mat[v][i];
				path[i]=v;
		}
	}//算法初始化 
//	for(int j=0;j<n;j++){
//		cout<<dist[j]<<"\t";
//	}
//	cout<<endl;
//	for(int j=0;j<n;j++){
//		cout<<path[j]<<"\t";
//	}
//	cout<<endl;
//输出检测
	for(int i=0;i<n-1;i++){//执行n-1个循环，依次确定每个点的最短路径 
		int min=999,min_ind=0;
		for(int j=0;j<n;j++){
			if(S[j]==0){
				if(min>dist[j]){
					min=dist[j];
					min_ind=j;
				}
			}
		}//找到未得到最小路径的点中的最小值
		S[min_ind]=1;//该点确定最小路径，添加至S
		for(int j=0;j<n;j++){
			if(mat[min_ind][j]>0){
				if(dist[j]>(dist[min_ind]+mat[min_ind][j])){
					dist[j]=dist[min_ind]+mat[min_ind][j];//修改路径长度 
					path[j]=min_ind;//标记路径 
				}
			}
		}
//		for(int j=0;j<n;j++){
//			cout<<dist[j]<<"\t";
//		}
//		cout<<endl;
//		for(int j=0;j<n;j++){
//			cout<<path[j]<<"\t";
//		}
//		cout<<endl;
//输出检测 
	}
    return 0;
}

2、任意顶点间最短路径：Floyd算法

算法思路与Dijkstra算法相同，不过直接对邻接矩阵进行操作，得出所有顶点间的路径，时间复杂度为$O(n^3)$。

邻接矩阵A[i][j]存储最小路径<i,j>；增加一矩阵path[i][j]存储当前路径下顶点j的上一顶点。

矩阵$A_{k+1}$得到的路径是路线中间点序号不超过k的最短路径，最终得到不超过n-1的最短路径，即最终路径。

邻接矩阵递推关系如下：

$A_{k+1}[i][j]=min(A_k[i][j],A_k[i][k]+A_k[k][j])\\ P[i][j]==\begin{cases} P[i][j]\ \ A[i][j]更小\\ P[k][j]\ \ A[i][k]+A[k][j]更小 \end{cases}$
算法步骤如下——

初始化邻接矩阵与路线矩阵；
根据递推式修改邻接矩阵A与路线矩阵path；
重复n次，得到所有最短路径。

示例：

代码实现如下：

void Floyd(){
	int n,m;//顶点数n、边数m
	cin>>n>>m;
	int mat[n][n];//邻接矩阵 
	int path[n][n];//三个辅助数组 
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			mat[i][j]=999;
			path[i][j]=-1;
		}
		mat[i][i]=0;
		path[i][i]=i;
	}//数组初始化 
	for(int i=0;i<m;i++){
		int a,b,w;
		cin>>a>>b>>w;
		mat[a][b]=w;
		path[a][b]=a;
	}//算法初始化 
	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				//当新的路径更加短时，更新mat和path
				if(mat[i][j]>mat[i][k]+mat[k][j]){
					mat[i][j]=mat[i][k]+mat[k][j];
					path[i][j]=path[k][j];
				}
			}
    }
	}
//	for(int i=0;i<n;i++){
//		for(int j=0;j<n;j++){
//			cout<<mat[i][j]<<"\t";
//		}
//		cout<<endl;
//	}
//	cout<<endl;
//输出检测
	return 0;
}

查找

查找：在数据集合中寻找满足某种条件的数据对象。

查找表：是由同一类型的数据元素(或记录)组成的数据集合。

关键字：数据元素中的某个数据项的值，用以表示该数据元素。

主关键字：可唯一识别一个数据元素。

衡量标准：查找过程中对关键字的平均比较次数——平均查找长度ASL。设查找到第i个元素的概率为p，比较次数为c，则查找成功的$ASL_{succ}=\sum^n_{i=1}p_ic_i$

一、顺序查找

从表中最后一元素开始，顺序用关键字与给定的x比较，直至找到相等的元素。

1、算法实现

<<<<<<< HEAD
int Seq_Search(SSTable ST , KeyType key){ 
    int p ; 
    ST. elem[0].key=key ; /* 设置监视哨兵,失败返回0 */
    for (p=ST.length; !EQ(ST. elem[p].key, key); p--)
    return(p) ; 
} 

2、算法分析

等概率情况下，$p_i=\frac{1}{n},c_i=n-i+1$ $ASL_{succ}=\sum^n_{i=1}\frac{1}{n}(n-i+1)=\frac{n+1}{2}=O(n)$ $ASL_{fail}=n+1=O(n)$

二、折半查找

条件：查找表中的数据元素按照关键字有序排序。

1、算法实现

分别用Low、High、Mid表示待查找区间的下界、上界与中间查找位置。初始化Low=0，High=n-1，接下来开始查找：

取$Mid=(Low+High)/2$
比较Mid与所找x值，若Mid<x，则High=Mid-1；若Mid>x，则Low=Mid+1；并重新计算Mid值。
若Mid==x，成功查找；若Low>High，查找失败。

2、代码实现

int Bin_Search(SSTable ST , KeyType key){ 
    int Low=1，High=ST.length, Mid ;
    while (Low<High){ 
        Mid=(Low+High)/2 ;
        if (EQ(ST. elem[Mid].key, key)) 
        return(Mid) ; 
        else if (LT(ST. elem[Mid].key, key)) 
        Low=Mid+1 ;
        else High=Mid-1 ;
    }
    return(0) ; /* 查找失败 */ 
}

3、算法分析

查找时可以看作通过二叉判定树查找，由满二叉树性质知，第i 层上的结点数为$2^{i-1}\ (i≤h)$，设表中每个记录的查找概率相等，即$P_i=1/n$，查找成功时的平均查找长度ASL： $ASL=\sum^n_{i=1}\frac{1}{n}i\times 2^{i-1}=\frac{n+1}{n}\log{n+1}-1=O(\log{n})$

三、分块查找（索引查找）

1、算法思路

索引表组织：

将查找表分成几块。块与块之间有序，即第i+1块的所有关键字均大于(或小于)第i块关键字；块内无序。在查找表的基础上附加一个索引表，每一块以其最大值作为索引表的一个元素。

查找：

查找索引表，确定x所存在的块号（折半查找）。
到块中进行查找（顺序查找）。

2、代码实现

class Index{ 
    keyType maxkey ; /* 块中最大的关键字 */
    int startpos ; /* 块的起始位置指针 */
};

int Block_search(
RecType ST[ ] , 
Index ind[ ] , 
KeyType key , 
int n , 
int b){ 
/* 在分块索引表中查找关键字为key的记录 */ 
 /*表长为n ，块数为b */
    int i=0 , j , k ;
    while ((i<b)&&LT(ind[i].maxkey, key) ) 
        i++ ;
    if (i>b) { 
        printf(”\nNot found“); 
        return(0); 
    }
    j=ind[i].startpos ;
    while ((j<n)&&LQ(ST[j].key, ind[i].maxkey) ){ 
        if ( EQ(ST[j].key, key) ) break ;
        j++ ;
    } /* 在块内查找 */
    if (j>n||!EQ(ST[j].key, key) ){ 
        j=0; 
        printf(”\nNot found“); 
    }
    return(j); 
}

3、算法分析

设表长为n个记录，均分为b块，每块记录数为s，则b=⌈n/s⌉。

设记录的查找概率相等，每块的查找概率为1/b，块中记录的查找概率为1/s，则平均查找长度：

$ASL=L_b+L_w=\sum^b_{j=1}j+\frac{1}{s}\sum^s_{i=1}i=\frac{b+1}{2}+\frac{s+1}{2}$

4、方法比较

四、优先队列（堆）

给定n个元素的序列，如果对其中$i=1～\frac{n}{2}$个元素，满足$k_i\le k_{2i}$且$k_i\le k_{2i+1}$，该序列称为优先队列。

1、优先队列调整

构建优先队列本质上是构建一棵二叉树，父结点的值一定比子女结点小（小顶堆）。

给定一个序列，从$i=\frac{n}{2}$开始操作，直至i=1（从子树开始操作）：

若$k_i\le k_{2i}$且$k_i\le k_{2i+1}$，则不做操作。
若$k_i\le k_{2i}$且$k_i\gt k_{2i+1}$，则取不满足的那一对($k_{2i+1}$)进行交换。
若$k_i\gt k_{2i}$且$k_i\gt k_{2i+1}$，则与较小的那一个进行交换；若$k_{2i}==k_{2i+1}$，直接交换$k_i$与$k_{2i}$。

小顶堆建立：

代码实现：

void HeapAdjust(HeapType &H,int s,int m){ 
    ElemType rc=H.r[s];
    for (int j=2*s;j<=m;j*=2){ 
        if ((j<m) && (H.r[j].key<H.r[j+1].key))
            ++j;
        if (rc.key > H.r[j].key) break;
        H.r[s].key=H.r[j].key; 
        s=j;
    }
    H.r[s]=rc;
}

/*
主函数
*/
for (int i=H.length/2; i>0; --i)
    HeapAdjust(H,i,H.length);

2、插入

3、删除

4、性能分析

insert：$O(\log{n})$

delete：$O(\log{n})$

serach：$O(1)$

数组方式存储。

五、树型查找

二叉查找树、B树

insert：$O(\log{n})$

delete：$O(\log{n})$

serach：$O(\log{n})$

链表方式存储，实现参照树结构。

六、散列（哈希表）

1、算法思路

在关键字与存储方式之间建立一个映射关系。无需比较就可以查找到待查关键字。

数组F：散列表

F中每个单元：桶bucket

关键字集U：$k\in U$，函数$h(k)$为k的散列地址/散列值。

散列冲突：多个关键字对应同一个存储地址。

2、哈希函数构造

直接定址法：

利用线性函数：$Hash(k)=a*k+b$

一对一映射，不产生冲突；但散列地址空间大小与关键字集合大小相同。

适用情况：事先知道关键字的值，关键字取值集合不是很大且连续性较好

数字分析法：

利用数字在某些位分布不均，选取其中若干位作为哈希地址。

平方取中法：

折叠法：

除留余数法：

$Hash(k)=k%p$，k取不能被小于20的质数整除的整数。

随机数法：

$Hash(k)=random(k)$

3、解决散列冲突

a、开放定址法

当冲突发生时，形成某个探测序列；按此序列逐个探测散列表中的其他地址，直到找到给定的关键字或一个空地址为止，将发生冲突的记录放到该地址中。

$d_i$：第i次探测时的增量序列

m：散列表长

$H_i(k)=(H(k)+d_i)%m$

探测终止条件：

探测到的地址为空：插入——写入该地址；查找——查找失败。
探测到的地址有给定关键字：插入——失败；查找——成功。

$d_i=1,2,3,4……$

易产生冲突聚集。

$d_i=1^2,-1^2,2^2,-2^2……$

不易产生聚集，但不能保证探测到所有地址。

$d_i=random$

利用伪随机数。

b、再哈希

c、链地址

产生冲突时继续保存在该地址下，直接构造链表存储。

d、公共溢出区

另外建立一个溢出表，保存冲突的所有元素记录。发生冲突的元素存入溢出表中。

4、哈希查找

针对关键字x，根据哈希函数得到给定存储地址，比较所储存的关键字k；若存在不同于x的k，根据解决冲突的方式继续查找，直至找到对应关键字或者地址为空。

#define NULLKEY -1 
/* 根据关键字类型定义空标识 */
typedef struct
{ KeyType key ; /* 关键字域 */
otherType otherinfo ; /* 记录的其它域 */
}RecType ;

int Hash_search(RecType HT[], KeyType k, int m)
/* 查找散列表HT中的关键字K,用开放定址法解决冲突 */
{ int h, j ;
h=h(k) ;
while (j<m && !EQ(HT[h].key, NULLKEY) )
{ if (EQ(HT[h].key, k) ) return(h) ;
else h=R(k, ++j) ; 
}
return(-1) ;
}

#define M 15
typedef struct node
{ KeyType key;
struct node *link;
}HNode;

5、算法分析

ASL取决于：

哈希函数
处理冲突方式
填满因子：a=已填入关键字/哈希表长度

排序

排序：将一组杂乱无章的数据排列成一个按关键字有序的序列。

数据表(datalist)：待排序数据对象的有限集合。

关键字(key)：通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键字。

稳定性：序列中两个元素i、j，当关键字i==j，当完成排序后，两个元素的相对位置没有改变，称为稳定。

内排序与外排序：内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。

衡量排序方法的标准：平均比较次数、平均移动、平均辅助存储空间、稳定性

一、插入排序

1、算法思路

每步将一个待排序的对象，按关键字大小插入到前面已经排序完成序列的适当位置上。当插入第i个对象时，前面的v[0], v[1], …, v[i-1]已经排好序。

这时，用v[i]的关键字与v[i-1], v[i-2], …的关键字顺序进行比较，找到插入位置即将v[i]插入，原来位置上之后的所有对象依次向后顺移。

2、代码实现

void InsertSort(SqList &L){
    for(int i=2 ; i<=L.length ; i++){
        if(L.r[i].key < L.r[i-1].key){
            L.r[0] = L.r[i]; // 监视哨
            for(int j=i-1; L.r[0].key < L.r[j].key; j—){
                L.r[j+1] = L.r[j];
            }//依次向后移位
            L.r[j+1]=L.r[0];
        }
    }
}

3、算法分析

辅助空间：1。

设有n个元素，则算法进行n-1趟排序。最好情况下，排序前序列已经有序，则每一趟只需要与需与前面的有序对象序列的最后一个对象的关键字比较 1 次，移动 2 次对象，总的关键字比较次数为 n-1，对象移动次数为 2(n-1)。

平均情况下时间复杂度为$O(n^2)$。

稳定，数据规模较小。

二、希尔排序

1、算法思路

先将整个序列按照一定间隔分割成若干子序列，在子序列中分别进行直接插入排序。然后缩小间隔，重复以上划分子序列、分别排序堆过程直至间隔为1。最后进行一次直接插入排序。

开始时gap（间隔值）的值较大，子序列中的对象较少，排序速度较快；随着排序进展，gap 值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。

2、代码实现

void ShellSort(SqList &L , int dlta[] , int t){
    for(int k = 0 ; k < t ; k++){
        ShellInsert(L,dlta[k]);
    }
}

//
void ShellInsert(SqList &L , int gap){
    for(int i = gap + 1; i < L.length ; i++){
        if(L.r[i].key < L.r[i-gap].key){
            L.r[0] = L.r[i];
            for(int j=i-gap; L.r[0].key < L.r[j].key; j=gap){
                L.r[j+gap] = L.r[j];
            }
            L.r[j+gap]=L.r[0];
        }
    }
}

3、算法分析

辅助空间：1。

当 n 很大时，关键字平均比较次数和对象平均移动次数大约在$n^{1.25}$到$1.6n^{1.25}$ 的范围内。

三、冒泡排序（比较排序）

1、算法思路

设待排序对象序列中的对象个数为 n，最多作 n-1 趟排序。

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

2、代码实现

3、算法分析

注意引入了变量change，当已经排序完成时自动结束排序。

辅助空间：1。

至少比较1次，至多比较n-1次；每次确定一个元素的位置；可以实现部分排序；稳定排序。

a、当对象的初始排列已经按关键字从小到大排好序时，此算法只执行一趟冒泡，做n-1次关键字比较，不移动对象。这是最好的情形。

b、最坏的情形是算法执行了n-1趟冒泡，第 i 趟做了n- i 次关键字比较，执行了n-i 次对象交换。这样在最坏情形下总的关键字比较次数KCN和对象移动次数RMN为：

$KCN = \sum^{n-1}_{i=1}(n-i)=\frac{n(n-1)}{2}$

$RMN = 3\sum^{n-1}_{i=1}(n-i)=\frac{3n(n-1)}{2}$

四、快速排序（比较排序）

1、算法思路

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

排序流程如下：

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

2、代码实现

void quicksort(int left, int right) {
	int i, j, t, temp;
	if(left > right)
		return;
    temp = a[left]; //temp中存的就是基准数
    i = left;
    j = right;
    while(i != j) { //顺序很重要，要先从右边开始找
    	while(a[j] >= temp && i < j)
    		j--;
    	while(a[i] <= temp && i < j)//再找右边的
    		i++;       
    	if(i < j)//交换两个数在数组中的位置
    	{
    		t = a[i];
    		a[i] = a[j];
    		a[j] = t;
    	}
    }
    //最终将基准数归位
    a[left] = a[i];
    a[i] = temp;
    quicksort(left, i-1);//继续处理左边的，这里是一个递归的过程
    quicksort(i+1, right);//继续处理右边的 ，这里是一个递归的过程
}

3、算法分析

快速排序是不稳定的。

辅助空间：$\log{n}$。

快速排序的一次划分算法从两头交替搜索，直到low和high重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。

理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为$O(nlog_2n)$。

最坏的情况是，每次所选的基准数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为$O(n^2)$。

改进思路：若能更合理地选择基准数，使得每次划分所得的两个子序列中的对象个数尽可能地接近，可以加速排序速度。

改进办法：取每个待排序对象序列的第一个对象、最后一个对象和位置接近正中的3个对象，取其关键字大小居中者作为基准数。

五、选择排序

1、代码实现

void SelectSort(SqList &L){ 
    for (int i=0; i<L.length-1;++i){  
        for (int j=i+1;j<L.length;++j)
        if (L.r[i].key > L.r[j].key){ 
            ElemType temp=L.r[i];
            L.r[i]=L.r[j];
            L.r[j]=temp; 
        }
    }
}

2、算法分析

不稳定。

总的关键字比较次数KCN和对象移动次数RMN为：

$KCN = \sum^{n-2}_{i=0}(n-i-1)=\frac{n(n-1)}{2}$

最好情况：$RMN = 0$

最坏情况：$RMN = 3(n-1)$

六、堆排序

1、算法思路

堆顶的元素为序列的最大/最小值。

利用堆的概念，可以很容易地实现选择排序的思路。堆排序分为两个步骤：第一步，根据初始输入数据，利用堆的调整算法形成初始堆，输出堆顶元素。第二步，重新调整剩余元素使之成为堆。重复以上操作。

构建堆参照查找中的优先队列。

不稳定排序。

辅助空间：1。

$O(n\log{n})$

七、归并排序

1、算法思路

归并，是将两个或两个以上的有序表合并成一个新的有序表。

外排序只能用归并排序。

基本思想：（每次都进行两两归并）

假设初始对象序列有 n 个对象，首先把它看成是 n 个长度为 1 的有序子序列 (归并项)，先做两两归并，得到n / 2（向上取整）个长度为 2 的归并项 (如果 n 为奇数，则最后一个有序子序列的长度为1)；再做两两归并，…，如此重复，最后得到一个长度为 n 的有序序列。

2、代码实现

void Merge(elem SR[], elem TR[], int i, int n, int m){
    
}

void Msort(elem SR[], elem TR1[], int s, int t){

}

3、算法分析

稳定排序。

辅助空间：一个与原待排序对象数组同样大小的辅助数组。

归并排序算法中，递归深度为O(logn)，对象关键字的比较次数为O(nlogn)。算法总的时间复杂度为O(nlogn)。

八、基数排序

1、算法思路

基数排序是采用“分配”与“收集”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。

多关键字排序：

假定一个n个对象的序列：{$v_0,v_1….v_{n-1}$}，每个对象都含有d个关键字：$(k_i^1,k_i^2….k_i^d)$，如果对序列内任意一对元素$v_i,v_j(i<j)$，都满足：

$(k_i^1,k_i^2….k_i^d)<(k_j^1,k_j^2….k_j^d)$

则该序列对关键字：$(k^1,k^2….k^d)$有序，序列第一位关键字$k^1$为最高位关键字，最后一位关键字$k^d$为最低位关键字。

多关键字排序方法：

最高位优先MSD (Most Significant Digit first)
最低位优先LSD (Least Significant Digit first)

2、算法分析

文件管理

数据以文件的方式存储在外存，需要进行有效的管理。

一、基本概念

1、基本概念

数据项（item、field）：数据文件中最小单位，反映实体某一方面的属性的数据表示。

记录（record）：一个实体的所有数据项的集合，用来表示一个记录的数据项集合称为关键字项。

文件（file）：大量性质相同的数据记录的集合。

基本物理结构：顺序结构