1.【实验5-1】缺失的数字
一个整数集合中含有n个数字，每个数字都在0~n之间。假设0~n的n+1个数字中有且仅有一个数字不在该集合中，请找出这个数字。
【输入格式】
第一行输入一个数字s，表示集合中数字的数量
第二行输入s个数字，以空格隔开。
1 <= s <= 1000
【输出格式】
输出缺失的数字
【输入样例】
4
0 1 2 4
【输出样例】
3
思路概要：创建一个数组，将数字存入数组中，升序排序后，依次查找找出缺少数字即可
易错点：若缺失数字在数组的最后一位，则需要特判，将其输出，否则无法查找出来！
时间复杂度：O(n)
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n,num[1005];
cin>>n;
for(int i=0;i<n;i++)
cin>>num[i];
sort(num,num+n);
int cnt=0,flag=1;
for(int i=0;i<n;i++){
if(num[i]!=cnt){
cout<<cnt;
flag=0;
break;
}
cnt++;
}
if(flag) cout<<n;
return 0;
}备注：本题作者较懒(bushi)，所以使用了algorithm库的sort函数，读者最好自己写排序算法，以锻炼编码能力哦。
2.【实验5-2】查找最长单词
在进行文章重复度检查时，经常需要统计一段英文中的单词数量，并找出长度最长的单词。
设有如下定义：char str[500];
编写程序，通过利用cin.getline(str,500);实现从键盘输入一小段英文（其中可以包含空格，但在同一行），利用函数统计该段英文中包含几个单词，输出统计出的单词数量、最长单词的长度以及长度最长的单词，空格隔开。
注意：函数声明使用void split(char *str);如果有最长的单词不只一个，输出最先找到的那个。
【输入形式】一小段英文，不要超过500个字符
【输出形式】单词数量、最长单词的长度以及长度最长的单词，空格隔开。
【输入样例】welcome to china university of mining and technology
【输出样例】8 10 university
思路概要：用空格代替单词进行计数，并且定义cnt变量，记录单词的长度，用打擂台的方法找出最长单词的长度和初位置，即可完成本题。
易错点：这里也不能叫易错点吧，只是一个小技巧，我们可以在原句后加一个空格，则进行函数调用时候，不需要特判就可以计量最后一个单词的长度！
时间复杂度：O(n)
代码如下：
#include<iostream>
#include<string.h>
using namespace std;
void solveProblem(char str[]){//可以分为两个函数，但是需要遍历2次，所以这里遍历一次以缩短时间
strcat(str," ");//在字符串后加一个空格，方便下列程序的操作
int len=strlen(str);
int num=0,cnt=0,pos,max_cnt=0;
for(int i=0;i<len;i++){
if(str[i]==' ') {
num++;
if(cnt>max_cnt){
max_cnt=cnt;
pos=i-max_cnt;//找出最大单词的位置
}
cnt=0;
}
else if((str[i]>='a'&&str[i]<='z')||(str[i]>='A'&&str[i]<='Z')){
cnt++;
}
}
cout<<num<<" "<<max_cnt<<" ";
for(int i=pos;i<pos+max_cnt;i++){
cout<<str[i];
}//最后输出最长字符串
}
int main(){
char str[500];
cin.getline(str,500);
solveProblem(str);
return 0;
}备注：读者也可以将本题函数分为两个函数，分别进行处理，这样可以使得程序更加模块化，但是会增加一次遍历次数（不过本题的数据也不大咧）。
3.【实验5-3】到底买不买
小红想买些珠子做一串自己喜欢的珠串。卖珠子的摊主有很多串五颜六色的珠串，但是不肯把任何一串拆散了卖。小红要你帮忙判断一下，某串珠子里是否包含了全部自己想要的珠子？如果是，那么告诉她有多少多余的珠子。
为方便起见，用[0-9]、[a-z]、[A-Z]范围内的字符来表示颜色。如下图中，第3串是小红想做的珠串；那么第1串可以买，因为包含了她全部想要的珠子，还多了8颗不需要的珠子；第2串不能买，因为没有黑色珠子，并且少了一颗红色的珠子。
【输入形式】每次输入包含两个字符串，分别在2行中先后给出摊主的珠串和小红想做的珠串，两串都不超过500个珠子。
【输出形式】如果可以买，则在一行中输出“Yes”以及有多少颗多余的珠子，其间以1个空格分隔；如果不可以买，则在一行中输出“No”以及缺少多少颗珠子，其间以1个空格分隔；。
【输入样例1】
ppRYYGrrYBR2258
YrR8RrY
【输出样例1】
Yes 8
【输入样例2】
ppRYYGrrYB225
YrR8RrY
【输出样例2】
No 2
思路概要：创建一个数组，遍历两条珠串，第一条珠串对应的珠子的ASCII码的数组元素加1，第二条珠串对应的珠子的ASCII码的数组元素减1，例如第一条珠串”ABC”,则s[‘A’]+=1,s[‘B’]+=1…以此类推，最后判断：如果有负数的存在，则”不可以买“，负数之和的绝对值即为缺少珠子数目。若没有负数，则”可以买“，正数之和即为多余珠子数目。
易错点：最后的查找过程可以遍历整个ASCII码表，当然读者可以采用其他更加快速的方式，但这种方式是比较简单易懂的。
时间复杂度：O(n)
代码如下：
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int main(){
int str[200]={0};
int extra=0,lack=0;
bool flag=1;
char S1[505],S2[505];
cin.getline(S1,505);
int len1=strlen(S1);
for(int i=0;i<len1;i++){
str[int(S1[i])]++;//利用强转，将char转为int类型
}
cin.getline(S2,505);
int len2=strlen(S2);
for(int i=0;i<len2;i++){
str[int(S2[i])]--;
}
for(int i=0;i<200;i++){
if(str[i]<0){
flag=0;
lack-=str[i];
}
if(str[i]>0){
extra+=str[i];
}
}
if(flag) cout<<"Yes"<<" "<<extra;
else cout<<"No"<<" "<<lack;
return 0;
}4.【实验5-4】逆波兰记法
逆波兰表示法（Reverse Polish Notation，RPN，或逆波兰记法），是一种是由波兰逻辑学家 J. Lukasiewicz于1929年提出的数学表达式的方法。在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。
例如：1 + 2 * (3 – 4) – 5 * 6的后缀表达式为1 2 3 4 – * + 5 6 * –
假设表达式中只包含变量（变量名只由小写字母构成）和加、减、乘、除四种运算，并且乘、除运算符的优先级高于加、减，请设计函数
void transfer(char* source, char* target)，实现将表达式转换成逆波兰记法。
【输入格式】
一个表达式，仅包含变量、加减乘除四种运算符，并且变量名只由小写字母构成
【输出格式】
该表达式的逆波兰记法
【输入样例】
a+b*c-d+f/e
【输出样例】
abc*+d-fe/+
思路概要：这道题大概算这次实验的较难题了，这里需要用到栈的技巧，这里分几点进行讲解。
1.栈是什么？
栈是一种常见的数据结构，有着先进后出的性质，犹如一个羽毛球桶。
2.本题的思路？
本题可以使用双栈法，定义第一个栈存放运算过程，第二栈作为临时栈，用于临时存放运算符。
stack<char> s, s_tmp;3.如何进栈？or 进栈顺序如何？
1.如果碰到数字(变量)，则直接压入栈s中
if (*(source + i) >= 'a' && *(source + i) <= 'z') {
s.push(*(source + i));2.如果碰到运算符，我们有这样的入栈法则：
①如果是空栈，则入栈。
②如果不是空栈，且该运算符的优先级大于栈顶，则入栈。
当然，这里提到的栈是s_tmp。
那么问题又来了，我们如何进行优先级的判断呢？
这里给出一个函数：
int isPrio(char c) { //优先级判断
switch (c) {
case'+':
case'-':
return 1;
case'*':
case'/':
return 2;
}
return 0;
}我们将+ -的优先级定义为1，将* /的优先级定义为2。（当然读者可以设置为其他值，这里没有任何限制，只需要优先级正确即可）
4.如何出栈？or 何时出栈？
s_tmp的出栈顺序是本题的关键，这里给出出栈条件，读者可以自行揣摩：
①如果s_tmp栈不为空，并且循环到达尾声，即i=len-1,栈中剩余元素依次出栈，并且压入s中。
②如果预入栈元素优先级小于等于栈顶的元素(这个比较过程直到栈顶优先级大于预入栈元素，或者栈为空才会停止，否则一直进行)，则栈顶元素出栈，并且压入s中。最后将预入栈元素入栈。
备注：这里讲讲为什么是优先级小于等于，而不是小于。由于算式计算按照由左到右的顺序，所以左侧的运算符的优先级，且运算符本身的优先级相等的运算符大于右侧的运算符的优先级。我知道这句话非常绕，所以在下面举个例子：
例如：2+3+5 这里的2后面的+号的优先级是大于3后的+号的，所以事实上，第一个+号优先级是大于第二个+号的优先级的。
然而，我们的入栈顺序也是从左向右的，所以便是小于等于了。
这样，我们本题的思路便差不多了，下面给出代码。
代码如下：
#include <iostream>
#include <stack>
#include <string.h>
using namespace std;
void push_back(char c, char *target) {
static int len = 0;
target[len++] = c;
}
int isPrio(char c) { //优先级判断
switch (c) {
case'+':
case'-':
return 1;
case'*':
case'/':
return 2;
}
return 0;
}
void print_ex(char *target) {//反向输出，由于出栈会生成一个逆向的后缀式，所以需要反向输出
int len = strlen(target);
for (int i = len - 1; i >= 0; i--) {
cout << target[i];
}
}
void transfer(char *source, char *target) { //双栈转换法
int len = strlen(source);
stack<char> s, s_tmp;
for (int i = 0; i < len; i++) {
if (*(source + i) >= 'a' && *(source + i) <= 'z') {
s.push(*(source + i));
}
if (*(source + i) == '+' || *(source + i) == '-' || *(source + i) == '*' || *(source + i) == '/') {
if (s_tmp.empty() || isPrio(*(source + i)) > isPrio(s_tmp.top())) {
s_tmp.push(*(source + i));
} else if ((isPrio(*(source + i)) <= isPrio(s_tmp.top())) && !s_tmp.empty()) {
while (isPrio(*(source + i)) <= isPrio(s_tmp.top())) {
s.push(s_tmp.top());
s_tmp.pop();
if (s_tmp.empty()) break;
}
s_tmp.push(*(source + i));
}
}
}
if (!s_tmp.empty()) {
while (!s_tmp.empty()) {
s.push(s_tmp.top());
s_tmp.pop();
}
}
while (!s.empty()) {
push_back(s.top(), target);
s.pop();
}
print_ex(target);
}
int main() {
char source[200000]={0}, target[200000]={0};//这里必须初始化，否则后面输出结果可能会输出乱码
cin.getline(source, 200000);
transfer(source, target);
return 0;
}本题代码比较繁琐，读者需要细细研读，最好可以自己写出来，这里提供另一个博客，提供一个思路中缀表达式转逆波兰表达式（后缀表达式）
其实是本蒟蒻太菜了，写的代码太繁琐了呜呜呜呜/(ㄒoㄒ)/~~
备注：这里我使用了C++ STL库中的stack类型，感兴趣的读者可以自己试试用数组模拟一个栈，使用起来会更加方便噢。
5. 【实验5-5】集合的交集
设有两个整数集合A和B，请输出A∩B的元素，其中集合A、B用单向链表表示。
【输入格式】
第一行输入一个数字n，表示集合A中数字的数量
第二行输入n个数字，以空格隔开。
第三行输入一个数字m，表示集合B中数字的数量
第四行输入m个数字，以空格隔开。
【输出格式】
若干个整数，即A∩B的元素，每个整数后面有一个空格
【输入样例】
7
3 9 11 4 2 7 1
5
1 3 5 7 9
【输出样例】
1 7 9 3
程序请按照如下要求设计：
struct Node
{ int data;
Node *next;
};
struct Set
{ int num;
Node *head;
};
void init(Set *x)
{
x->head=NULL;
x->num=0;
}
void createSet(Set *x)
{
生成链表时一定采用往前插入的方法，即每个新产生的结点插入到链表的第一个结点的前面。
}
void intersect(Set *x,Set *y)
{
外层循环对集合x进行遍历，内层循环对集合y进行多次遍历，遇到交集的元素，输出的是集合x中的值。
}
int main()
{
Set a,b;
init(&a);
init(&b);
createSet(&a);
createSet(&b);
intersect(&a,&b);
return 0;
}
思路概要：本题已经给出了函数的具体框架，读者只需要填入缺失的地方就可以解题了。
本题还是很简单的，如果有同学不了解链表的具体定义和使用方法，可以看看下面的链接C++链表
时间复杂度：O(n)
代码如下：
#include<iostream>
using namespace std;
struct Node
{
int data;
Node *next;
};
struct Set
{
int num;
Node *head;
};
void init(Set *x)
{
x->head = NULL;
x->num = 0;
}
void createSet(Set *x)
{
int n;
int num1;
cin>>n;
for(int i=0;i<n;i++){
cin>>num1;
Node *p=new Node;
p->data=num1;
p->next=NULL;
if(x->head==NULL){
x->head=p;
}
else{
p->next=x->head;
x->head=p;
}
x->num++;
}
}
void intersect(Set *x, Set *y)
{
Node *p=x->head;
Node *q=y->head;
while(p){
while(q){
if(p->data==q->data){
cout<<p->data<<" ";
}
q=q->next;
}
q=y->head;
p=p->next;
}
}
int main()
{
Set a, b;
init(&a);
init(&b);
createSet(&a);
createSet(&b);
intersect(&a, &b);
return 0;
}备注：大家要熟悉链表的实现，在以后的程序设计中，链表的运用是很多的，需要加强练习哦。
在最后，链表最好自写一个clear函数进行清除，否则占用堆区空间则会导致系统运行缓慢，要养成好的习惯。
6. 【实验5-6】丢手绢
设有n个小朋友围坐一圈玩丢手绢（用编号1，2，……n代表玩游戏的人），从第k（k大于等于1并且小于等于n）个小朋友开始报数，数到m的那个人出列。他的下一位继续从1开始报数，数到m的人出列，依此类推，直到所有人都出列为止。
要求：n个小朋友围坐一圈用单向循环链表表示。
【输入格式】
三个整数n k m，其中n表示玩游戏的人数，k表示从第k个人开始玩，m表示报数的值
【输出格式】
n个整数，分别对应依次退出游戏的小朋友的编号
【输入样例】
13 2 3
【输出样例】
4 7 10 13 3 8 12 5 11 6 2 9 1
程序可以参考如下框架：
struct Node {
int data;
Node* next;
};
struct List {
Node* head;
int length;
};
void createList(List &lst,int n){
生成链表时采用往后插入的方法，即每个新结点插入到链表尾部，最后的结点指向链表第一个结点，形成单向循环链表。
}
void play(List& lst, int k, int m){
}
int main()
{
int n, k, m;
cin>>n>>k>>m;
List lst;
createList(lst,n);
play(lst,k,m);
return 0;
}
思路概要：本题是一个经典的约瑟夫问题，利用循环链表的结构定义与功能，多次遍历即可实现。
什么是约瑟夫问题
易错点：本题要注意，当最后删除只剩下一个节点时，便不能再采取之前删除节点的方法，而是应该特殊判断。这里给出一个两个节点便开始特殊判断的程序，读者也可以自己尝试只剩下1个节点进行特殊判断。
代码如下：
#include<iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
struct List {
Node* head;
int length;
};
void createList(List &lst,int n){
lst.length=0;
Node *q;
for(int i=1;i<=n;i++){
Node *p=new Node;
p->next=NULL;
if(i==1){
lst.head=p;
p->data=i;
q=lst.head;
lst.length++;
}
else {
while(q->next){
q=q->next;
}
q->next=p;
p->data=i;
lst.length++;
}
}
q->next->next=lst.head;
return;
}
void play(List& lst, int k, int m){
Node *q=lst.head;
Node *p=q;
int Node_count=lst.length;
if(Node_count==1) {
cout<<q->data;
return;
}
for(int i=0;i<k-1;i++){
q=q->next;//向后遍历k-1次
}
while(Node_count>2){
int cnt=1;
for(;cnt<m;cnt++){
q=q->next;
while(p->next!=q){
p=p->next;
}
}
cout<<q->data<<" ";
p->next=q->next;
q=p->next;
Node_count--;
}
for(int cnt=1;cnt<m;cnt++){
q=q->next;
}
cout<<q->data<<" "<<q->next->data;
}
int main()
{
int n, k, m;
cin>>n>>k>>m;
List lst;
createList(lst,n);
play(lst,k,m);
return 0;
}备注：作者的代码可能不是最优解，还望原谅┭┮﹏┭┮。
终章：结束
好了，这次中国矿业大学实验五的题解到此结束啦，希望同学们顺利完成实验，作者第一次写博客，写的不好还望大家多多体谅哇QAQ。
本博客可能有些问题没有说清楚，代码也存在纰漏，还望大家指出，本鼠鼠会接受大家的批评教育，努力学习，争取给大家一个比较易懂的题解┭┮﹏┭┮。
就这样啦！期待下一次见面！
文章出处登录后可见！
