数据结构-代码模板

prim

#include<iostream>
#define max_number 9999
using namespace std;

typedef struct Graph {
	int vexsnums;// 表示顶点的个数
	int arcsnums;// 表示边的个数
	int arcs[20][20];// 边的信息
	char vexs[20];// 顶点的信息
};
typedef struct CloseEdge { // 定义一个辅助的数组
	char vexs;// 记录顶点
	int weight;// 记录这个顶点到这个已经有的树的最小距离
};
CloseEdge* InitCloseEdge(Graph* G, int indexnumber) { // 初始化这个距离prim树最小距离
	CloseEdge* closeedge = new CloseEdge[G->vexsnums];
	for (int i = 0;i < G->vexsnums;i++) {
		closeedge[i].vexs = G->vexs[indexnumber]; // 记录这个在prim里面的顶点
		closeedge[i].weight = G->arcs[indexnumber][i];// 给每一个在prime树之外的顶点距离目标indexnumber的权值大小
	}
	return closeedge;
}
int GetMinEdge(Graph* app, CloseEdge* closeedge) { // 获取最小权值的顶点的权值的下标
	int indexnumber = -1;
	int minnumber = max_number;
	for (int i = 0;i < app->vexsnums;i++) {
		if (closeedge[i].weight != 0 && closeedge[i].weight < minnumber) {// 0表示的是在这个最小生成树里面了
			minnumber = closeedge[i].weight;
			indexnumber = i;
		}
	}
	return indexnumber;
}
void Prim(Graph* G, int indexnumber) {
	int minnumber;// 声明一个最小值变量
	CloseEdge* closeedge = InitCloseEdge(G, indexnumber);
	for (int i = 0;i < G->vexsnums - 1;i++) {
		minnumber = GetMinEdge(G, closeedge);// 获得最小权值的顶点下标
		closeedge[minnumber].weight = 0;// 加入到最小生成树里面去
		for (int j = 0;j < G->vexsnums;j++) {
			if (G->arcs[minnumber][j] < closeedge[j].weight) {
				closeedge[j].weight = G->arcs[minnumber][j];
				closeedge[j].vexs = G->vexs[minnumber];
			}
		}
	}
}

哈夫曼树

#include<iostream>
using namespace std;

typedef struct hafumantree { // 构造一个哈夫曼树
	int weight;// 权值
	int parent;// 父节点
	int leftchild;// 左子树
	int rightchild;// 右子树
};
void selectmintwo(hafumantree*& HT, int n, int& s1, int& s2) {
	for (int j = 1;j <= n;j++) {
		if (HT[j].parent == 0) {// 如果在这个哈夫曼书中找到了这个父节点没有的节点的话就通过
			if (s1 == -1 || HT[s1].weight > HT[j].weight) {// 找到两个最小的节点
				s2 = s1;
				s1 = j;
			}
			else if (s2 == -1 || HT[s2].weight > HT[j].weight) {
				s2 = j;
			}
		}
	}
}
void Createhafumantree(hafumantree*& HT, int n) {// 传入一个定义的哈夫曼树以及节点的数目
	if (n <= 1)return;
	int m = 2 * n - 1;
	HT = new hafumantree[m + 1]; // 动态分配空间的大小到哈夫曼树里面去
	//接下来就是对哈夫曼树进行初始化
	for (int i = 1;i <= m;i++) {
		HT[i].leftchild = 0;
		HT[i].parent = 0;
		HT[i].rightchild = 0;
		HT[i].weight = 0;
	}
	// 接下来就是对这个哈夫曼数进行输入他自己的权值到自己的哈夫曼树脸面去
	for (int i = 1;i <= n;i++) {
		cin >> HT[i].weight;// 在这里后面可以自己去添加一些想要添加地一些其他的了类型地值进去,比如节点对印的值等
		//只处理权值的输入。如果需要添加更多信息（例如节点的标识、符号等），可以进一步扩展输入部分。
	}
	// 下面就hi对这个哈夫曼数进行构造地过程,就是每次循环寻找没有双亲地节点而且这个节点的权值是最小的那一个[需要这样的节点两个]
	for (int i = n + 1;i < m + 1;i++) {
		int s1 = -1, s2 = -1;
		selectmintwo(HT, i - 1, s1, s2);// 通过这个方式来找到最小的两个值在[1,i-1]这个范围中找到s1和s2这两个最小的值,其中这两个代表地是数组地下标
		// 接着就可以进行操作
		HT[i].leftchild = s1;
		HT[i].rightchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
		HT[s1].parent = i;
		HT[s2].parent = i;
	}
}

kruskal

#include<iostream>
using namespace std;

#define max_vexs 100
#define max_number 9999

typedef struct Graph {
	char vexs[max_vexs];
	int arcs[max_vexs][max_vexs];
	int vexsnumber;
	int arcsnumber;
};
typedef struct Edge { // 定义一个存储连通分量的数据结构
	int start;
	int end;
	int weight; // 连通分量的标志
};
Edge* InitEdge(Graph* G) {// 初始化储存顶点以及边的信息以及权值
	int index = 0;
	Edge* edge = new Edge[G->arcsnumber];
	for (int i = 0; i < G->vexsnumber; i++) {
		for (int j = i + 1; j < G->vexsnumber; j++) {
			if (G->arcs[i][j] != max_number) {
				edge[index].start = i;
				edge[index].end = j;
				edge[index].weight = G->arcs[i][j];
				index++;
			}
		}
	}
	return edge;
}
void sortEdge(Edge* edge, int length) {
	if (length == 1)return;
	for (int i = 0;i < length - 1;i++)if (edge[i].weight > edge[i + 1].weight) swap(edge[i], edge[i + 1]);
	return sortEdge(edge, length - 1);
}
void kruskal(Graph* G) { // kruskal算法
	int connected[max_number];
	for (int i = 0; i < G->vexsnumber; i++) connected[i] = i;
	Edge* edge = InitEdge(G);
	sortEdge(edge, G->arcsnumber);
	for (int i = 0; i < G->arcsnumber; i++) {
		int start = connected[edge[i].start];
		int end = connected[edge[i].end];
		if (start != end) {
			for (int j = 0; j < G->vexsnumber; j++) {
				if (connected[j] == end) connected[j] = start;
			}
		}
	}
}

Dijkstra

#include<iostream>
using namespace std;

#define max_vexs 100
#define max_number 9999

// 全局设计三个数组用来存储顶点是否被访问过,以及这个这个点距离源点的距离大小是多少,最后一个就是用来存储这个顶点的前驱是哪一个顶点,后面可以通过前驱来找到这个最短的路径
bool visted[max_number];// 用来记录是否被访问到
int path[max_number]; // 用来记录这个顶点的前驱是哪一个数组的下标
int power[max_number];// 用来存储这个源点到这个点的距离大小是多少

typedef struct Graph { // 定义一个图的数据结构
	char vexs[max_vexs];// 存储顶点
	int arcs[max_vexs][max_vexs];
	int vexsnumber;
	int arcsnumber;
};
void Dijkstra(Graph* G, int index) { // DJ算法,index是指从哪一个源点出发
	for (int i = 0;i < G->vexsnumber;i++) {// 首先是初始化这三个数组
		visted[i] = false;
		power[i] = G->arcs[index][i];
		if (power[i] < max_number) {
			path[i] = index;
		}
		else {
			path[i] = -1;
		}
	}
	visted[index] = true;power[index] = 0;
	for (int k = 1;k < G->vexsnumber;k++) {// 初始化结束,开始循环找最短距离,更新这三个数组的值
		int minnumber = max_number;int vexs;
		for (int i = 0;i < G->vexsnumber;i++) {// 寻找最小值,在这个没有被遍历过的顶点当中
			if (!visted[i] && power[i] < minnumber) {
				minnumber = power[i];
				vexs = i;
			}
		}
		visted[vexs] = true;
		for (int j = 0;j < G->vexsnumber;j++) {// 接下来就是对最短路径的更新处理
			if (!visted[j] && (power[vexs] + G->arcs[vexs][j] < power[j])) {// 如果从一个点出发到他四周的点的权值比之前的还要小,那就更新这个新的点到这个权值中来
				power[j] = power[vexs] + G->arcs[vexs][j];// 更新新的权值
				path[j] = vexs;// 更新前驱
			}
		}
	}
}

Floyd

#include<iostream>
using namespace std;

#define max_vexs 100
#define max_number 9999

int D[max_vexs][max_vexs];// 定义一个二维数组用来存储权值大小,也就是距离大小
int Path[max_vexs][max_vexs];// 定义一个二维数组用来存储这个路径的前驱,如果中间没有前驱的话就是直接-1,有前驱的话就是复制为那个顶点的下标

typedef struct Graph { // 定义一个图的数据结构
	char vexs[max_vexs];// 存储顶点
	int arcs[max_vexs][max_vexs];
	int vexsnumber;
	int arcsnumber;
};
void Floyd(Graph* app) {
	for (int i = 0;i < app->vexsnumber;i++) {// 首先先初始化这两个二维数组
		for (int j = 0;j < app->vexsnumber;j++) {
			D[i][j] = app->arcs[i][j];
			if (app->arcs[i][j] < max_number) {// 如果这个点的值不是max_vexs的话就是要设置这个顶点的前驱
				Path[i][j] = i;
			}
		}
	}
	for (int k = 0;k < app->vexsnumber;k++) {// 接下来就是对这两个二维数组进行赋值
		for (int g = 0;g < app->vexsnumber;g++) {
			for (int t = 0;t < app->vexsnumber;t++) {
				if (D[g][k] + D[k][t] < D[g][t]) {// 如果中间增加了节点之后的权值比之前的权值好药小的话就直接更新这个权值
					D[g][t] = D[g][k] + D[k][t];// 更新新的权值大小
					Path[g][t] = Path[k][t];// 更新新的前驱
				}
			}
		}
	}
}