第二题

问题描述

队列的循环报数问题：设有n个人站成一排，从左往右的编号分别为1~n，现在从左往右报数“1,2,1,2…”，数到“1”的人出列，数到“2”的人立即站到队伍的最右端。报数过程反复进行，直到n个人都出列为止。要求给出它们的出列顺序。
n从键盘输入，出列顺序输出到控制台。
示例 1

输入：10
输出：1 3 5 7 9 2 6 10 8 4

解题思路及代码

由题意得该问题涉及队列，对于队列的奇偶位置上的数有不同的处理方法。

奇数位置：直接弹出
偶数位置：先弹出再入队

重复上述操作直至队列为空。

#include 
#include
using namespace std;
int main()
{int n;cin>>n;queueq;for(int i = 0; i < n; i++){q.push(i+1);}int flag = 1;while(!q.empty()){if(flag == 1){cout<int tmp = q.front();q.pop();q.push(tmp);flag = 1;}}return 0;
}

第三题

问题描述

无向图的最小生成树：输入在文件3.in中给出，描述了图的形状。首先给出图中结点的总数n，结点编号从0到n-1，然后接下来每一行给出边的信息，每行包含三个数字，分别是两个顶点的编号以及边长。要求出无向图对应的最小生成树，将结果输出到文件3.out中。

示例 1

输入：
9
7      6    1 
8      2    2 
6      5    2 
0      1    4 
2      5    4 
8      6    6 
2      3    7 
7      8    7 
0      7    8 
1      2    8 
3      4    9 
5      4    10
1      7    11
3      5    14
输出：
7 -- 6 : 1
6 -- 5 : 2
8 -- 2 : 2
2 -- 5 : 4
0 -- 1 : 4
2 -- 3 : 7
1 -- 2 : 8
3 -- 4 : 9

解题思路及代码

求无向图的最小生成树常用的算法是prim算法和kruskal算法，针对本题选择kruskal算法比较合适，而且相比prim算法，kruskal算法思路实现更简单，复杂度一般也低。
krus算法的实现过程：每次从无向图中选取边长最小的边加入最小生成树中，加入时要注意不能与已经加入的顶点构成连通，构成连通则需放弃加入该边，如果无向图的顶点数为n，那么选择n-1条符合条件的边即停止。
判断边是否连通的方法：用subset[n]数组来表示每个边所在的子集序号，设新加入的两个顶点的subset为i、j，出现的情况为

i == 0 && j == 0，说明两个顶点不在其他子集中，加入新的子集 
i == j && i != 0，两个顶点存在于相同的子集中，加入的边会导致连通，应该舍弃
i != j && i != 0 && j != 0，两个顶点存在与不同的子集中，合并两个不同的子集
((i != 0 && j == 0) || (i == 0 && j != 0))，将不在任何子集中的顶点加入另一个顶点的子集

#include
#include
#include
#include
using namespace std;
struct Edge
{int beg, eds, weight;Edge(int beg,int eds, int weight):beg(beg), eds(eds), weight(weight) {}
};
struct cmp //使得队列从小到大排序
{bool operator()(const Edge &l, const Edge &r){return l.weight > r.weight;}
};
int main()
{ifstream ifs("./3.in.txt");ofstream ofs("./3.out.txt");int n;ifs>>n;vectorsubset(n,0);priority_queue,cmp> edges;vector ans;int a,b,c;int maxid = 1;while(ifs>> a >> b >> c){edges.push(Edge(a,b,c));}while(!edges.empty() && ans.size() < n-1){Edge e = edges.top();edges.pop();int i = subset[e.beg], j = subset[e.eds];if(i == 0 && j == 0){subset[e.beg] = subset[e.eds] = maxid++;ans.push_back(e);}else if(i != j && i != 0 && j != 0){for(int k = 0; k < subset.size();k++){if(subset[k] == i)subset[k] = j;}ans.push_back(e);}else if(i != 0 && j == 0){subset[e.eds] = subset[e.beg];ans.push_back(e);}else if(i == 0 && j != 0){subset[e.beg] = subset[e.eds];ans.push_back(e);}}for (auto &e : ans){ofs<

输入:
5
D B A C E
D B E C A
输出: A B D C E

前序：根-左-右
中序：左-根-右
后序：左-右-根

左子树：在in数组的位置: l1 ~ i-1             在post数组的位置: l2 ~ l2+i-1-l1
右子树：在in数组的位置: i+1 ~ r1             在post数组的位置: l2+i-l1 ~ r2-1

#include
#include
#include
using namespace std;
struct TreeNode
{char val;TreeNode *lchild, *rchild;TreeNode(char val):val(val){}
};
TreeNode *make(vector in, vector post,int l1,int r1,int  l2,int r2)
{if(l1 > r1) return NULL;TreeNode *t = new TreeNode(post[r2]);int i;for(i = l1; i <= r1; i++){if(in[i] == post[r2]){break;}}t->lchild = make(in,post,l1,i-1,l2,l2+i-1-l1);t->rchild = make(in,post,i+1,r1,l2+i-l1,r2-1);return t;}
TreeNode *buildTree(vector in, vector post)
{TreeNode *root = make(in,post,0,in.size()-1,0,post.size()-1);return root;}
void inOrder(TreeNode *root,ofstream &ofs)
{if(root != NULL){ofs<val<<" ";inOrder(root->lchild,ofs);inOrder(root->rchild,ofs);}else{return;}
}
int main()
{ifstream ifs("./4.in.txt");ofstream ofs("./4.out.txt");int n;ifs>>n;vectorin(n),post(n);for(int i = 0; i < n; i++){ifs >> in[i];}for(int i = 0; i < n; i++){ifs >> post[i];}TreeNode *root = buildTree(in,post);inOrder(root,ofs);return 0;
}