矿大数据结构 实验三_中国矿业大学 数据结构实验

A.二叉链表存储的二叉树

定义节点 --- 建立二叉树的函数 --- 前序遍历函数 --- 中序遍历函数

#include<bits/stdc++.h>
#define ll long long
 
using namespace std;
 
struct Node{    //节点，用char存储本身的数据，指针指向左右节点 
	char data;
	Node *lc;
	Node *rc;
	Node(char c):data(c),lc(NULL),rc(NULL){}
}; 
 
Node* build(string s,int& i){   //i代表当前的位置 
	if(i>=s.length()||s[i]==' ') return NULL;
	
	Node* root = new Node(s[i]);
	i++;
	root->lc=build(s,i);
	i++;
	root->rc=build(s,i);
	return root;
}
void pre_order(Node *root){
	if(root==NULL) return;
	cout<<root->data<<' ';
	pre_order(root->lc);
	pre_order(root->rc);
}
void mid_order(Node*root){
	if(root==NULL) return ;
	mid_order(root->lc);
	cout<<root->data<<' ';
	mid_order(root->rc);
}
void midord(Node *root){
	
}
int main() {
	string s;
    getline(cin,s);
    int i=0;
    
	Node *root = build(s,i);
	pre_order(root);
	cout<<'\n';
	mid_order(root);
	cout<<'\n';
	mid_order(root);
}

B.哈夫曼树

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
  
//定义一个结点类，包含权值和左右子结点
class Node {
public:
    int weight;
    Node* left;
    Node* right;
    Node(int w) {
        weight = w;
        left = NULL;
        right = NULL;
    }
};
  
//定义一个比较函数，用于优先队列的排序
struct cmp {
    bool operator()(Node* a, Node* b) {
        return a->weight > b->weight; //权值小的优先
    }
};
  
//计算哈夫曼树的权值和
int huffmanSum(Node* root, int depth) {
    if (root == NULL) return 0; //空结点返回0
    if (root->left == NULL && root->right == NULL) return root->weight * depth; //叶子结点返回权值乘以深度
    return huffmanSum(root->left, depth + 1) + huffmanSum(root->right, depth + 1); //非叶子结点递归计算左右子树的和
}
  
int main() {
    int n; //叶结点个数
    while (cin >> n) { //多组输入
        priority_queue<Node*, vector<Node*>, cmp> pq; //创建一个优先队列，用于存储结点指针
        for (int i = 0; i < n; i++) {
            int w; //输入权值
            cin >> w;
            Node* node = new Node(w); //创建一个新的结点
            pq.push(node); //将结点指针入队
        }
        while (pq.size() > 1) { //当队列中还有多于一个结点时，循环执行以下操作
            Node* left = pq.top(); //取出队首的最小权值结点，作为左子结点
            pq.pop(); //出队
            Node* right = pq.top(); //取出队首的次小权值结点，作为右子结点
            pq.pop(); //出队
            Node* parent = new Node(left->weight + right->weight); //创建一个新的父结点，其权值为左右子结点的和
            parent->left = left; //连接左子结点
            parent->right = right; //连接右子结点
            pq.push(parent); //将父结点入队
        }
        Node* root = pq.top(); //最后队列中只剩一个结点，即为哈夫曼树的根结点
        cout << huffmanSum(root, 0) << endl; //输出哈夫曼树的权值和，初始深度为0
    }
    return 0;
}

C.

#include <iostream>
#include <vector>
using namespace std;
vector<int> in, pre, post;
bool unique = true;
void getIn(int preLeft, int preRight, int postLeft, int postRight) {
if(preLeft == preRight) {
in.push_back(pre[preLeft]);
return;
}
if (pre[preLeft] == post[postRight]) {
int i = preLeft + 1;
while (i <= preRight && pre[i] != post[postRight-1]) i++;
if (i - preLeft > 1)
getIn(preLeft + 1, i - 1, postLeft, postLeft + (i - preLeft - 1) - 1);
else
unique = false;
 
in.push_back(post[postRight]);
getIn(i, preRight, postLeft + (i - preLeft - 1), postRight - 1);
 
}
}
int main() {
int n;
scanf("%d", &n);
pre.resize(n), post.resize(n);
for (int i = 0; i < n; i++)
scanf("%d", &pre[i]);
for (int i = 0; i < n; i++)
scanf("%d", &post[i]);
getIn(0, n-1, 0, n-1);
printf("%s\n%d", unique == true ? "Yes" : "No", in[0]);
for (int i = 1; i < in.size(); i++)
printf(" %d", in[i]);
printf("\n");
return 0;
}

D.最短路径

dfs搜索即可。记得开long long

#include<bits/stdc++.h>
#define ll long long
 
using namespace std;
const int MAXN = 1e5;
int n,m;
int len[150][150];
bool t[150][150];
bool is[150][150];
ll ans=0;
 
void dfs(int x,int y,int cnt){
    if(x==y){
    	if(ans==0){
    		ans=cnt;
		}
		else {
			if(ans>cnt)
			ans=cnt;
		}
		return ;
	}
	for(int i=1;i<=n;i++){
		if(i==x) continue;
		if(len[x][i]!=0&&is[x][i]!=1){
			is[x][i]=1;
			dfs(i,y,cnt+len[x][i]);
		} 
	}
}
 
int main(){
	cin>>n>>m;
	int x,y,z;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		len[x][y]=z;
	}
	cin>>x>>y;
	dfs(x,y,0);
	ans==0? cout<<"STOP":cout<<ans;
    return 0;
} 

E.

#include <iostream>
#include <vector>
using namespace std;
 
const int INF = 0x3f3f3f3f; // 定义一个无穷大的常量，用于表示没有直接连接的情况
 
struct Edge {
    int from; // 边的起点
    int to; // 边的终点
    int cost; // 边的代价
    Edge(int f, int t, int c): from(f), to(t), cost(c) {} // 构造函数
};
 
int prim(vector<vector<int>>& graph, vector<Edge>& tree) { // 根据邻接矩阵构建最小生成树，并返回总代价
    int n = graph.size(); // 图中顶点的个数
    vector<int> pre(n, -1); // 前驱数组，存储每个顶点的前驱顶点的索引，初始为-1
    vector<bool> visited(n, false); // 访问标记数组，初始为false
    vector<int> dist(n, INF); // 距离数组，存储每个顶点到当前生成树的最短距离，初始为无穷大
    int total = 0; // 总代价，初始为0
    dist[0] = 0; // 从第一个顶点开始构建最小生成树，将其距离设为0
    for (int i = 0; i < n; i++) { // 循环n次，每次加入一个顶点到最小生成树中
        int u = -1; // 用于寻找距离最小的顶点的索引，初始为-1
        int minDist = INF; // 用于记录最小距离，初始为无穷大
        for (int j = 0; j < n; j++) { // 遍历所有顶点
            if (!visited[j] && dist[j] < minDist) { // 如果该顶点没有被访问过，且其距离小于当前最小距离
                u = j; // 更新最小距离顶点的索引
                minDist = dist[j]; // 更新最小距离
            }
        }
        if (u == -1) return -1; // 如果没有找到合适的顶点，说明图不连通，返回-1
        visited[u] = true; // 将找到的顶点标记为已访问
        total += minDist; // 将最小距离加入总代价中
        if (i > 0) tree.push_back(Edge(u, pre[u], minDist)); // 如果不是第一个顶点，将对应的边加入最小生成树中，pre[u]表示u的前驱顶点
        for (int v = 0; v < n; v++) { // 遍历所有顶点，更新距离数组和前驱数组
            if (!visited[v] && graph[u][v] < dist[v]) { // 如果该顶点没有被访问过，且u到v的边的代价小于当前距离
                dist[v] = graph[u][v]; // 更新距离
                pre[v] = u; // 更新前驱
            }
        }
    }
    return total; // 返回总代价
}
 
int main() {
    int n; // 图中顶点的个数
    cin >> n; // 输入顶点个数
    vector<vector<int>> graph(n, vector<int>(n)); // 邻接矩阵，初始为n*n的二维向量
    vector<Edge> tree; // 最小生成树，初始为空
    for (int i = 0; i < n; i++) { // 输入邻接矩阵
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j]; // 输入第i行第j列的元素，即i到j的边的代价，如果为0表示没有直接连接
            if (graph[i][j] == 0) graph[i][j] = INF; // 将0替换为无穷大，方便后续处理
        }
    }
    int result = prim(graph, tree); // 调用prim函数构建最小生成树，并得到总代价
    if (result == -1) { // 如果返回值为-1，说明图不连通
        cout << "The graph is not connected." << endl; // 输出提示信息
    } else { // 如果返回值不为-1，说明图连通
        cout << result << endl; // 输出总代价
    }
    return 0; // 程序结束
}