阅读量:0
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; // 程序结束 }