数据结构基本代码汇总_数据结构代码

---

一、线性表

1.顺序表的定义
#define Maxsize 50
typedef struct{
	ElemType data[Maxsize];
	int length;
}SqList;

动态分配下的顺序表（不常考）
#define InitSize 100
typedef struct{
	ElemType *data;
	int MaxSize,length;
}SqList;
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize); 

2.顺序表的基本操作

//在第i个位置插入
bool ListInsert(SqList &L,int i,ElemType e){
	if(i<1||i>L.length+1) return false;
	if(L.length>=Maxsize) return false;
	for(int j=L.length;j>=i;j--){
		L.data[j]=L.data[j-1];
	}
	L.data[i-1]=e;
	L.length++;
	return true;
}

//在第i个位置删除
bool ListDelete(SqList &L,int i,ElemType &e){
	if(i<1||i>L.length) return false;
	for(int j=i-1;j<L.length;j++){
		L.data[j]=L.data[j+1];
	}
	L.length--;
	return true;
}

//按值查找（顺序查找）
int LocateElem(Sqlist L,ElemType e){
	for(int i=0;i<L.length;i++){
		if(L.data[i]==e){
			return i+1;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

2.线性表的链式表示

1.单链表定义
typedef struct LinkNode{
	ElemType data;
	struct LinkNode *next;
}LinkNode,*LinkList;

1
2
3
4
5
6

单链表的基本操作

1.头插法建立单链表
LinkList Insert_head(LinkList &L){
	LNode *s;
	int x;
	L=(LinkList)malloc(sizeof(LinkNode));
	scanf("%d",&x);
	while(x!=9999){
		s=(LinkNode*)malloc(sizeof(LinkNode));
		s->data=x;
		s->next=L->next;
		L->next=s;
		scanf("%d",&x);
	}
	return L;
}

2.尾插法建立单链表
LinkList Insert_tail(LinkList &L){
	LinkNode *s,*r;
	int x;
	L=(LinkList)malloc(sizeof(LinkNode));
	r=L;
	scanf("%d",&x);
	while(x!=9999){
		s=(LinkNode*)malloc(sizeof(LinkNode));
		s->data=x;
		r->next=s;
		r=s;
		scanf("%d",&x);
	}
	r->next=NULL;
	return L;
}

3.按序号查找节点
LinkNode *Findvalue(LinkList L,int i){
	int j=1;
	LinkNode *p=L->next;
	if(i==0) return L;
	if(i<1) return NULL;
	while(p&&j<i){
		p=p->next;
		j++;
	}
	return p;
}

4.按值查找节点
LinkNode *Getvalue(LinkList L,ElemType e){
	LinkNode *p=L->next;
	while(p&&p->data!=e){
		p=p->next;
	}
	return p;
}

5.插入节点（插入值为x的节点到第i个位置）
void Insertvalue(LinkList &L,int i,ElemType e){
	LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
	s->data=e;
	int j=1;
	LinkNode *p=L->next;
	while(p&&j<i-1){
		p=p->next;
		j++;
	}
	s->next=p->next;
	p->next=s;
	return ;
}

6.删除第i个节点
void Deletei(LinkList &L,int i){
	int j=1;
	LinkNode *p=L->next;
	while(p&&j<i-1){
		p=p->next;
		j++;
	}
	LinkNode *s=p->next;
	p->next=s->next;
	free(s);
	return ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

双链表

1.定义
typedef struct DNode{
	ElemType data;
	struct DNode *prior,*next;
}DNode,*DLinkList;

2.插入
	s->next=p->next;
	p->next->prior=s;
	p->next=s;
	s->prior=p;

3.删除
p->next=s->next;
s->next->prior=p;
free(s);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

静态链表

1.定义
#define MaxSize 50
typedef struct{
	ElemType data;
	int next;
}SLinkList[MaxSize];
1
2
3
4
5
6

二、栈

顺序栈（大题中常用此物理结构）

1.定义
#define MaxSize 50
typedef struct{
	ElemType data[MaxSize];
	int top;
}SqStack;

2.初始化
void InitStack(SqStack &S){
	S.top=-1;
}

3.判断栈为空
bool StackEmpty(SqStack S){
	if(S.top==-1)
		return true;
	else
		return false;
}

4.进栈
bool Push(SqStack &S,ElemType x){
	if(S.top==MaxSize-1) return false;
	S.data[++S.top]=x;
	return true;
}

5.出栈
bool Pop(SqStack &S,ElemType &x){
	if(S.top==-1) return false;
	x=S.data[S.top--];
	return true;
}

6.读栈顶元素
bool GetTop(SqStack &S,ElemType &x){
	if(S.top==-1) return false;
	x=S.data[S.top];
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

链式栈

1.定义
typedef struct LinkNode{
	ElemType data;
	struct LinkNode *next;
}*LiStack;


1
2
3
4
5
6
7

三、队列

顺序循环队列

1.定义
#define MaxSize 60
typedef struct{
	ElemType data[MaxSize];
	int front,rear;
}SqQueue;

2.初始化
void InitQueue(SqQueue &Q){
	Q.front=Q.rear=0;
}

3，判断队空
bool QueueEmpty(SqQueue Q){
	if(Q.front==Q.rear)
		return true;
	else
		return false;
}

4.入队
bool EnQueue(SqQueue &Q,ElemType x){
	if((Q.rear+1)%MaxSize==Q.front){
		return false;
	}
	Q.data[Q.rear]=x;
	Q.rear=(Q.rear+1)%MaxSize;
	return true;
}

5.出队
bool DeQueue(SqQueue &Q,ElemType &x){
	if(Q.rear==Q.front){
		return false;
	}
	x=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

链式队列

1.定义
typedef struct LinkNode{
	ElemType data;
	struct LinkNode *next;
}LinkNode;
typedef struct{
	LinkNode *front,*rear;
}LinkQueue;

2.初始化
void InitQueue(LinkQueue &Q){
	Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
	Q.front->next=NULL;
}

3.判断队空
bool isEmpty(LinkQueue Q){
	if(Q.front==Q.rear)
		return true;
	else
		return false;
}

4.入队（链队无须判断队满）
void EnQueue(LinkQueue &Q,ElemType x){
	LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
	s->data=x;s->next=NULL;
	Q.rear->next=s;
	Q.rear=s;
}

5.出队
bool DeQueue(LinkQueue &Q,ElemType &x){
	if(Q.rear==Q.front){
		return false;
	}
	LinkNode *p=Q.front->next;
	x=p->data;
	Q.front->next=p->next;
	if(Q.rear==p){
		Q.rear=Q.front;
	}
	free(p);
	return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

四、串

顺序存储

#define MLen 255
typedef struct{
	char ch[MLen];
	int length;
}SString;
1
2
3
4
5

堆分配存储（动态分配）

typedef struct{
	char *ch;
	int length;
}HString;
1
2
3
4

简单的模式匹配算法

int index(SString s,SString t){
	int i=1,j=1;
	while(i<=s.length&&j<=t.length){
		if(s.ch[i]==t.ch[j]){
			i++,j++;
		}else{
			i=i-j+2;
			j=1;
		}
	}
	if(j>t.length){
		return i-t.length;
	}else{
		return 0;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

KMP算法

void get_next(String s,int next[]){
	int i=1,j=0;
	next[1]=0;
	while(i<t.length){
		if(j==0||t.ch[i]==t.ch[j]){
			i++,j++;
			next[i]=j;
		}else{
			j=next[j];
		}
	}
}
int index_kmp(String s,String t,int next[]){
	int i=1,j=1;
	while(i<=s.length&&j<=t.length){
		if(j==0||s.ch[i]==t.ch[j]){
			j++,i++;
		}else{
			j=next[j];
		}
		if(j>t.length){
			return i-t.length;
		}else
			return 0;
	}
}

//优化
void get_nextval(String t,int nextval[]){
	int i=1,j=0;
	nextval[1]=0;
	while(i<t.length){
		if(j==0||t.ch[i]==t.ch[j]){
			i++,j++;
			if(t.ch[i]!=t.ch[j]) 
				nextval[i]=j;
			else 
				nextval[i]=nextval[j];
		}else{
			j=nextval[j];
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

五、树与二叉树

二叉树

1.定义
typedef struct BiNode{
	int data;
	struct BiNode *lchild,*rchild;
}BiNode,*BiTree; 

2.先序遍历
void PreOrder(BiTree T){
	if(T!=NULL){
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

3.1先序遍历的非递归算法（栈）
void PreOrder_f(BiTree T){
	InitStack(S);
	BiTree p=T;
	while(p||!isEmpty(S)){
		if(p){
			visit(p);
			Push(S,p);
			p=p->lchild;
		}else{
			Pop(S,p);
			p=p->rchild;
		}
	}
}

3.2中序遍历的非递归算法//与先序类似
void InOrder(BiTree T){
	InitStack(S);
	BiTree p=T;
	while(p||!IsEmpty(S)){
		if(p){
			Push(S,p);
			p=p->lchild;
		}else{
			Pop(S,p);
			visit(p);
			p=p->rchild;
		}
	}
}

3.3后序遍历的非递归算法（难）
void PostOrder_f(BiTree T){
	InitStack(S);
	BiTree p=T;
	BiNode *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;
			}	
		}
	}
}

4.层次遍历（队列）
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);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

线索二叉树

1.定义
typedef struct ThreadNode{
	int data;
	int ltag,rtag;
	struct ThreadNode *lchild,*rchild;
}ThreadNode,*ThreadTree;

2.中序线索化建线索二叉树
void InThread(ThreadTree &p,ThreadTree &pre){
	if(p!=NULL){
		InThread(p->lchild,pre);
		if(p->lchild==NULL){
			p->lchild=pre;
			p->ltag=1;
		}
		if(pre!=NULL&&pre->rchild==NULL){
			pre->rchild=p;
			pre->rtag=1;
		}
		pre=p;
		InThread(p->rchild,pre);
	}
}
void CreateInThread(ThreadTree T){
	ThreadTree pre=NULL;
	if(T!=NULL){
		InThread(T,pre);
		pre->rchild=NULL;
		pre->rtag=1;
	}
}

3.先序线索化建线索二叉树（防转圈）
void PreThread(ThreadTree &p,ThreadTree &pre){
	if(p!=NULL){
		if(p->lchild==NULL){
			p->lchild=pre;
			p->ltag=1;
		}
		if(pre!=NULL&&pre->rchild==NULL){
			pre->rchild=p;
			pre->rtag=1;
		}
		pre=p;
		if(p->ltag==0)//防转圈，确保左子树还没有被线索化
			PreThread(p->lchild,pre);
		PreThread(p->rchild,pre);
	}
}
void CreatePreThread(ThreadTree T){
	ThreadTree pre=NULL;
	if(T!=NULL){
		PreThread(T,pre);
		pre->rchild=NULL;
		pre->rtag=1;
	}
}

4.后序线索化建线索二叉树
void CreatePostThread(ThreadTree T){
	ThreadTree pre=NULL;
	if(T!=NULL){
		PostThread(T,pre);
		pre->rchild=NULL;
		pre->rtag=1;
	}
}
void PostThread(ThreadTree &p,ThreadTree &pre){
	if(p!=NULL){
		PostThread(p->lchild,pre);
		PostThread(p->rchild,pre);
		if(p->lchild==NULL){
			p->lchild=pre;
			p->ltag=1;
		}
		if(pre!=NULL&&pre->rchild==NULL){
			pre->rchild=p;
			pre->rtag=1;
		}
		pre=p;
	}	
}

5.中序线索二叉树的遍历
（1）求中序序列下第一个结点
ThreadNode *Firstnode(ThreadNode *p){
	while(p->ltag==0) p=p->lchild;
	return p;
}
（2）求结点p的后继
ThreadNode *Nextnode(ThreadNode *p){
	if(p->rtag==1) return p->rchild;
	return Firstnode(p->rchild);
}
（3）中序遍历中序线索二叉树
void Inorder(ThreadNode *T){
	for(ThreadNode *p=Firstnode(p);p!=NULL;p=Nextnode(p))
		visit(p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

树

1.定义
（1）双亲表示法
#define MAX_TREE 100
typedef struct{
	ElemType data;
	int parent;
}PTNode;
typedef struct{
	PTNode nodes[MAX_TREE];
	int n;
}PTree;

（2）孩子兄弟表示法
typedef struct CSNode{
	ElemType data;
	struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

（3）孩子表示法（将每个结点的孩子都用单链表链接起来形成一个线性结构，n个结点有n个孩子链表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

并查集

1.定义
#define SIZE 100
int UFSets[SIZE];

2.初始化
void Init(int S[]){
	for(int i=0;i<size;i++)
		S[i]=-1;
}

3.合并root1和root2到一个分支上
void Union(int S[],int root1,int root2){
	S[root2]=root1;
}

4.找x的祖先（根节点）
int Find(int S[],int x){
	while(S[x]>0){
		x=S[x];
	}
	return x;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

六、图

邻接矩阵

1.定义
#define MaxNode 100
typedef char VerType;
typedef int EdgeType;
typedef struct{
	EdgeType Edge[MaxNode][MaxNode];
	VerType Vex[MaxNode];
	int vernum,edgenum;
}MGraph;
1
2
3
4
5
6
7
8
9

邻接表

1.定义
typedef struct ALGraph{
	AdjList v;//表示一个顶点表数组
	int vexnum,arcnum;
}ALGraph;
typedef struct VNode{//顶点表数组 
	char data;//每个节点的名字 
	ArcNode *first;
}VNode,AdjList[MaxSize];
typedef struct ArcNode{
	int adjnum;//弧所指向的结点的编号（与顶点表数组对应） 
	struct ArcNode *next;
}ArcNode;
1
2
3
4
5
6
7
8
9
10
11
12
13

从图的邻接表表示转换成邻接矩阵

void Convert(ALGraph G1,MGraph &G2){
	G2.edgenum=G1.arcnum;
	G2.vexnum=G1.vexnum;
	for(int i=0;i<G1.vexnum;i++){//初始化G2
		for(int j=0;j<G1.vexnum;j++){
			G2.Edge[i][j]=0;
		}
	}
	for(int i=0;i<G1.vexnum;i++){
		ArcNode *p=G1.vertices[i].first;
		while(p){
			int j=p->adjnum;
			G2.Edge[i][j]=1;
			p=p->next;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

从图的邻接矩阵转化为邻接表

void convert(MGraph G1,ALGraph &G2){
	G2.arcnum=G1.edgenum;
	G2.vexnum=G1.vexnum;
	for(int i=0;i<G1.vexnum;i++){
		G2.vertices[i].first=NULL;
	}
	for(int i=0;i<G1.vexnum;i++){
		for(int j=0;j<G1.vexnum;j++){
			if(G1.Edge[i][j]){
				ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode));
				p->adjnum=j;
				p->next=G2.vertices[i].first;
				G2.vertices[i].first=p;
			}
		}
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

图的基本操作

1.NextNeighbor（MGraph &G,int x,int y）
//邻接矩阵
#define maxWeight 0x3f3f3f3f
int NextNeighbor(MGraph &G,int x,int y){
	if(x!=-1&&y!=-1){
		for(int col=y+1;col<G.vexnum;col++){
			if(G.Edge[x][col]>0&&G.Edge[x][col]<maxWeight)
				return col;
		}
	}
	return -1;
}

//邻接表
int NextNeighbor(ALGraph &G,int x,int y){
	if(x!=-1){
		ArcNode *p=G.vertices[x].first;
		while(p!=NULL&&p->data!=y)
			p=p->next;
		if(p!=NULL&&p->next!=NULL)
			return p->next->data;
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

广度优先搜索BFS（队列实现）

int vis[MaxSize];
void BFSOrder(Graph G){
	for(int i=0;i<G.vexnum;i++){
		vis[i]=0;
	}
	InitQueue(Q);
	for(int i=0;i<G.vexnum;i++){//预防非连通图的情况
		if(!vis[i])
			BFS(G,i);
	}
}
void BFS(Graph G,int i){
	vis[i]=1;
	EnQueue(Q,i);
	while(!isEmpty(Q)){
		DeQueue(Q,v);
		for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
			if(!vis[w]){
				vis[w]=1;
				EnQueue(Q,w);
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

BFS求单源最短路（无权值）

void BFS_MIN(Graph G,int u){//求u到图中其余顶点的最短路径 
	for(int i=0;i<G.vexnum;i++){
		d[i]=-1;
	}
	vis[u]=1;d[u]=0;
	EnQueue(Q,u);
	while(!isEmpty(Q)){
		DeQueue(Q,u);
		for(w=FirstNeighbor(Q,u);w>=0;w=NextNeighbor(Q,u,w)){
			if(!vis[w]){
				vis[w]=1;
				d[w]=d[u]+1;//
				EnQueue(Q,w);
			}
		}
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

深度优先搜索DFS

int vis[MaxSize];
void DFSOrder(Graph G){//和bfs一模一样
	for(int i=0;i<G.vexnum;i++){
		vis[i]=0;
	}
	for(int i=0;i<G.vexnum;i++){
		if(!vis[i]){
			DFS(G,i);
		}
	}
} 
void DFS(Graph G,int v){
	vis[v]=1;
	for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
		if(!vis[w]){
			DFS(G,w);//走一条中国特色社会主义道路
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

用dfs判断无向图是否是树

int vis[MaxSize];
bool pd_Tree(Graph G){
	int vnum=1,anum=0;
	for(int i=0;i<G.vexnum;i++){
		vis[i]=0;
	}
	DFS(G,0,vnum,anum);
	if(vnum==G.vexnum&&2*(vnum-1)=anum)
		return 1;
	else 
		return 0;
}
void DFS(Graph G,int v,int &vnum,int &anum){
	vis[v]=1;
	for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
		if(!vis[w]){
			vnum++;
			anum++;
			DFS(G,w,vnum,anum);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

dfs的非递归算法（用栈实现，与bfs基本一样）

int vis[MaxSize];
void DFS_f(Graph G,int v){//从v结点开始遍历，前提是这个图是连通图 
	int w;
	InitStack(S);
	for(i=0;i<G.vexnum;i++){
		vis[i]=0;
	}
	Push(S,v);vis[v]=1;
	while(!isEmpty(S)){
		Pop(S,p);
		visit(p);
		for(w=FirstNeighbor(G,p);w>=0;w=NextNeighbor(G,p,w)){
			if(!vis[w]){
				Push(S,w);
				vis[w]=1;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

用dfs判断是否存在vi到vj的路径

int vis[MaxSize]={0};
void DFS(ALGraph G,int i,int j,bool &can_reach){
	if(i==j){
 		can_reach=true;
 		return;
	}
	vis[i]=1;
	for(int p=FirstNeighbor(G,i);p>=0;p=NextNeighbor(G,i,p)){
	 	if(!vis[p]&&!can_reach)
	 		DFS(G,p,j,can_reach);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

用bfs判断是否存在vi到vj的路径

int vis[MaxSize]={0};
int BFS(ALGraph G,int i,int j){
	InitQueue(Q);
	EnQueue(i);
	while(!isEmpty(Q)){
		DeQueue(Q,p);
		vis[p]=1;
		if(p==j) return 1;
		for(int w=FirstNeighbor(G,p);w>=0;w=NextNeighbor(G,p,w)){
			if(w==j) return 1;
			if(!vis[w]){
				vis[w]=1;
				EnQueue(Q,w);
			}
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

vi到vj所有简单路径

void FindPath(ALGraph &G,int u,int v,int path[],int d){
	d++;
	path[d]=u;
	vis[u]=1;
	if(u==v){
		print(path[]);
	}
	ArcNode *p;
	p=G->AdjList[u].firstarc;
	while(p){
		w=p->adjnum;
		if(!vis[w])
			FindPath(G,w,v,path,d);
		p=p->next;
	}
	vis[u]=0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

最小生成树

1.Prim算法
int getSum(MGraph &G,int *prims){
	int sum=0;
	for(int i=1;i<G.vexnum;i++){
		int min=39999;
		for(int j=0;j<i;j++){
			if(G.Edge[prims[j]][prims[i]]<min){
				min=G.Edge[prims[j]][prims[i]];
			}
		}
		sum+=min;
	}
	return sum;
}
void prim(MGraph &G,int start){//邻接矩阵实现 
	int prims[MaxSize];
	int lowCost[MaxSize];
	int min,k,index=0;		
	lowCost[start]=0;//自己到自己的距离为0 
	prims[index++]=start;
	for(int i=0;i<G.vexnum;i++){
		lowCost[i]=G.Edge[start][i];//将所有连接顶点的边的权值存入 
	}
	for(int i=0;i<G.vexnum;i++){
		if(start==i) continue;
		min=39999;
		for(int j=0;j<G.vexnum;j++){
			if(lowCost[j]!=0&&lowCost[j]<min){
				min=lowCost[j];
				k=j;
			}
		}
		prims[index++]=k;
		lowCost[k]=0;//将当前选中的顶点置为已访问 
		for(int j=0;j<G.vexnum;j++){
			if(lowCost[j]&&G.Edge[k][j]<lowCost[j]){
				lowCost[j]=G.Edge[k][j];
			}
		}
		printf("%d",getSum(G,prims));
		for(int i=0;i<G.vexnum;i++){
			printf("%c",G.Vex[prims[i]]);
		}
	}
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

拓扑排序

bool TopoSort(Graph G){
	InitStack(S);
	for(int i=0;i<G.vexnum;i++){
		if(indegree[i]==0)
			Push(S,i);
	}
	int count=0;
	while(!isEmpty(S)){
		Pop(S,i);
		print[count++]=i;
		for(p=G.adjList[i].firstarc;p;p=p->next){
			v=p->adjnum;
			if(!(--indegree[v]))
				Push(S,v);
		}
	}
	if(count<G.vexnum) return false;
	else return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

DFS实现拓扑排序

int vis[MaxSize]={0};
void DFStopo(Graph G){
	time=0;
	for(v=0;v<G.vexnum;v++){
		if(!vis[v])
			DFS(G,v);
	}
}
void DFS(Graph G,int v){
	vis[v]=1;
	visit(v);
	for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
		if(!vis[w]){
			DFS(G,w);
		}
	}
	time=time+1;
	finishTime[v]=time;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

七、查找

顺序查找

typedef struct{
	Elemtype elem[MaxSize];
	int len;
}STable;
int search(STable ST,Elemtype key){
	ST.elem[0]=key;//哨兵
	int i;
	for(i=ST.len;ST.elem[i]!=key;i--);
	return i;
} 
1
2
3
4
5
6
7
8
9
10

折半查找

int binary_search(STable L,Elemtype key){
	int low=0,high=L.len-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;
}

//递归写法
int binary_search1(STable L,Elemtype key,int low,int high){
	if(low>high)
		return 0;
	mid=(low+high)/2;
	if(key>ST.elem[mid])
		binary_search1(L,key,mid+1,high);
	else if(key<ST.elem[mid])
		binary_search1(L,key,low,mid-1);
	else
		return mid; 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

顺序检索算法（找到指定结点后与前驱结点交换）

//顺序表存储
int seqsrch(STable L,Elemtype key){
	int i=0;
	while(L.elem[i]!=k&&i<n)
		i++;
	if(i<n&&i>0){
		Elemtype t=L.elem[i];
		L.elem[i]=L.elem[i-1];
		L.elem[i-1]=t;
		return --i;
	}
	else
		return -1;
}

//链表存储
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;
int seqsrch1(LinkList &L,int key){
	LNode *p=L;
	int i=1;
	if(p->data==key) return i;//第一个结点就是指定结点，无需与前面交换 
	while(p->next!=NULL){
		if(p->next->data==key){
			int t=p->next->data;
			p->next->data=p->data;
			p->data=t;
			return i;
		}
		i++;
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

二叉排序树

1.查找
BiNode *BST_Search(BiTree T,Elemtype key){
	while(T!=NULL&&key!=T->data){
		if(key<T->data) T=T->lchild;
		else T=T->rchild;
	}
	return T;
}

2.插入
int BST_Insert(BiTree &T,int k){
	if(T==NULL){
		T=(BiTree)malloc(sizeof(BiNode));
		T->data=k;
		T->lchild=T->rchild=NULL;
		return 1;
	}
	else if(k==T->data)
		return 0;
	else if(k<T->data)
		return BST_Insert(T->lchild,k);
	else 
		return BST_Insert(T->rchild,k);
}

3.构造
void Creat_BST(BiTree &T,int data[],int n){
	T=NULL;
	int i=0;
	while(i<n){
		BST_Insert(T,data[i]);
		i++;
	}
}

4.判断是否是二叉排序树
int pd=-32767;
int JudgeBST(BiTree bt){
	int b1,b2;
	if(bt==NULL) return 1;
	else{
		b1=JudgeBST(bt->lchild);
		if(b1==0||pd>=bt->data)
			return 0;
		pd=bt->data;
		b2=JudgeBST(bt->rchild);
		return b2;
	}
}

5.求指定结点在二叉排序树中的层次
int level(BiTree bt,BiNode *p){
	int n=0;
	BiTree t=bt;
	if(bt!=NULL){
		n++;
		while(t->data!=p->data){
			if(p->data<t->data)
				t=t->lchild;
			else
				t=t->rchild;
			n++;
		}
	}
	return n;
}

6.求最小和最大的关键字（根据二叉排序树性质）
int min_key(BiNode *bt){
	while(bt->lchild!=NULL)
		bt=bt->lchild;
	return bt->data;
}
int max_key(BiNode *bt){
	while(bt->rchild!=NULL)
		bt=bt->rchild;
	return bt->data;
}

7.从大到小输出所有value不小于k的关键字
void Out_k(BiNode *bt,int k){
	if(bt==NULL) return ;
	if(bt->rchild!=NULL)
		Out_k(bt->rchild,k);
	if(bt->data>=k)
		printf("%d",bt->data);
	if(bt->lchild!=NULL)
		Out_k(bt->lchild,k);
}

8.查找第k小的元素并返回其指针
typedef struct BiNode{
	int data;
	int count;//以该节点为根的子树上的结点个数
	struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
BiNode *Search_k(BiNode *t,int k){
	if(k<1||k>t->count) return NULL;
	if(t->lchild==NULL){
		if(k==1) return t;
		else return Search_k(t->rchild,k-1);
	}else{
		if(t->lchild->count==k-1) 
			return t;
		if(t->lchild->count>k-1) 
			return Search_k(t->lchild,k);
		if(t->lchild->count<k-1)
			return Search_k(t->rchild,k-(t->lchild->count+1));
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

判断是否是平衡二叉树

void Judge_AVL(BiTree bt,int &balance,int &h){
	int bl=0,br=0,hl=0,hr=0;
	if(bt==NULL){
		h=0;
		balance=1;
	}else if(bt->lchild==NULL&&bt->rchild==NULL){
		h=1;
		balance=1;
	}else{
		Judge_AVL(bt->lchild,bl,hl);
		Judge_AVL(bt->rchile,br,hr);
		h=max(hl,hr)+1;
		if(abs(hl-hr)<2)
			balance=bl&&br;
		else 
			balance=0;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

八、排序

插入排序

1.直接插入排序
void InsertSort(ElemType A[],int n){
	int i,j;
	for(i=2;i<=n;i++){
		if(A[i]<A[i-1]){
			A[0]=A[i];
			for(int j=i-1;A[0]<A[j];--j)
				A[j+1]=A[j];
			A[j+1]=A[0];
		}
	}
}

2.折半插入排序
void HalfSort(ElemType A[],int n){
	int i,j,low,high,mid;
	for(i=2;i<=n;i++){
		A[0]=A[i];
		low=1,high=i-1;
		while(low<=high){
			mid=(low+high)/2;
			if(A[mid]>A[0]) high=mid-1;
			else low=mid+1;
		}
		for(j=i-1;j>=high+1;--j)
			A[j+1]=A[j];
		A[high+1]=A[0]; 
	}
}

3.希尔排序
void ShellSort(ElemType A[],int n){
	int dk,i,j;
	for(dk=n/2;dk>=1;dk=dk/2){
		for(i=dk+1;i<=n;i++){
			if(A[i]<A[i-dk]){
				A[0]=A[i];
				for(j=i-dk;j>0&&A[0]<A[j];j-=dk)
					A[j+dk]=A[j];
				A[j+dk]=A[0];
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

交换排序

1.冒泡排序
void BubbleSort(int A[],int n){//数组下标为0 
	int flag;
	for(int i=0;i<n-1;i++){
		flag=0;
		for(j=n-1;j>i;j--){
			if(A[j-1]>A[j]){
				swap(A[j-1],A[j]);
				flag=1;
			}
		if(!flag) return;
		}
	}
}

2.快速排序
void QuickSort(int A[],int low,int high){
	if(low<high){
		int pos=Partition(A,low,high);
		QuickSort(A,low,pos-1);
		QuickSort(A,pos+1,high);
	}
} 
int Partition(int A[],int low,int high){
	int 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

插入排序衍生题目

1.双向冒泡排序
void DBubbleSort(int A[],int n){//数组下标(0,n-1) 
	int low=0,high=n-1;
	int flag=1;
	while(low<high&&flag){
		flag=0;
		for(i=low;i<high;i++){
			if(a[i]>a[i+1]){
				swap(a[i],a[i+1]);
				flag=1;
			}
		}
		high--;
		for(i=high;i>low;i--){
			if(a[i]<a[i-1]){
				swap(a[i],a[i+1]);
				flag=1;
			}
		}
		low++;
	}	
}

2.奇数在前偶数在后
void MoveJiOu(int A[],int n){
	int i=0,j=n-1;
	while(i<j){
		while(i<j&&A[j]%2==0){
			j--;
		}
		while(i<j&&A[i]%2==1){
			i++;
		}
		if(i<j){
			swap(A[i],A[j]);
			i++,j--;
		}
	}
}

3.随机枢纽快排
void Partition(int A[],int low,int high){
	int ran=low+rand()%(high-low+1);
	swap(A[ran],A[low]);
	int 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 QuickRSort(int A[],int low,int high){
	if(low<high){
		int pos=Partition(A,low,high);
		QuickSort(A,low,pos-1);
		QuickSort(A,pos+1,high);
	}
} 

4.找第k小元素
int find_mink(int a[],int k,int low,int high){
	int pivot=a[low];
	int low_temp=low;
	int high_temp=high;
	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;
	if(low==k) return a[low];
	else if(low>k) 
		find_mink(a,k,low_temp,low-1);
	else
		find_mink(a,k,low+1,high_temp);
}

5.荷兰国旗问题（三色排序）
//red是0，white是1，blue是2 
void color_sort(int a[],int n){
	int cur=0,begin=0,end=n-1;
	while(cur<=end){
		if(a[cur]==0){
			swap(a[begin],a[cur]);
			cur++,begin++;
		}else if(a[cur]==2){
			swap(a[cur],a[end]);
			end--;
		}else{
			cur++;
		}
	}
}

6.将数组个数均等分成两个数组，两个数组差值最大
int setPartition(int a[],int low,int high){
	int 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 QuickSort(int a[],int low,int high,int mid){
	if(low<high){
		int pos=setPartition(a,low,high);
		if(pos==mid) return;
		if(pos>mid)
			QuickSort(a,low,pos-1,mid);
		if(pos<mid)
			QuickSort(a,pos+1,high,mid);	
	}
}
int main()
{
	int a[]={};//待排序数组 
	int s1=0,s2=0;
	QuickSort(a,0,n-1,(n-1)/2);
	int i,j;
	for(i=0;i<=(n-1)/2;i++){
		s1+=a[i];
	}
	for(j=i;j<n;j++){
		s2+=a[j];
	}
	cout<<s2-s1;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

选择排序

1.简单选择排序
void select_sort(int a[],int n){
	for(i=0;i<n-1;i++){
		min=i;
		for(j=i+1;j<n;j++)
			if(a[j]<A[min])	min=j;
		if(min!=i) swap(a[i],a[min]);
	}
}

2.堆排序*（难点）
void BuildMaxHeap(int a[],int len){//建大根堆 
	for(int i=len/2;i>0;i--){
		HeadAdjust(A,i,len);
	}
}
void HeadAdjust(int a[],int k,int len){
	a[0]=a[k];
	for(i=2*k;i<=len;i*=2){
		if(i<len&&a[i]<a[i+1]) i++;
		if(a[0]>=a[i]) break;
		else{
			a[k]=a[i];
			k=i;
		}
	}
	a[k]=a[0];
}
void HeapSort(int a[],int len){//数组下标(1,n) 
	BuildMaxHeap(a,len);
	for(int i=len;i>1;i--){
		swap(a[i],a[1]);
		HeadAdjust(a,1,i-1);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

选择排序拓展题目

1.单链表上进行简单选择排序
void select_sort(LinkList &L){
	LinkNode *h=L,*p,*q,*r,*s;//p是工作指针，q是p前驱
	//s是最大值指针，r是s前驱
	L=NULL;
	while(h!=NULL){
		p=s=h;q=r=NULL;
		while(p!=NULL){
			if(p->data>s->data){
				s=p;
				r=q;
			}
			q=p;
			p=p->next;
		}
		if(s==h) h=h->next;//最大值在头结点
		else r->next=s->next;
		s->next=L;
		L=s;
	}
}

2.判断小根堆
bool IsMinHeap(int a[],int len){
	if(len%2==0){//注意，结点数为偶数二叉树必有一个单分支节点 
		if(a[len/2]>a[len]) return false;//对其特判 
		for(int i=len/2-1;i>0;i--){
			if(a[i]>a[i*2]||a[i]>a[i*2+1])
				return false;
		}
	}else{
		for(int i=len/2;i>0;i--){
			if(a[i]>a[i*2]||a[i]>a[i*2+1])
				return false;
		}
	}
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

归并排序

int *b=(int *)malloc((n+1)*sizeof(int));
void Merge(int a[],int low,int mid,int high){
	for(int k=low;k<=high;k++)
		b[k]=a[k];
	for(int i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
		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++];
} 
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);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

一些习题
1.计数排序
void CountSort(int a[],int b[],int n){
	int cnt,i,j;
	for(i=0;i<n;i++){
		for(j=0,cnt=0;j<n;j++){
			if(a[j]<a[i]) cnt++;
		}
		b[cnt]=a[i];
	}
}

2.找到无序数组最后一个元素位置（快排思想）
int Partitionk(int a[],int n){
	int low=0,high=n-1;
	int pivot=a[n-1];
	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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27