实验二，栈和队列的使用2021-10-27_栈和队列的操作实验报告舞伴问题

一、实验目的与实验环境
1．目的：熟练掌握应用两种数据结构栈和队列，完成对应的实验题目；
2. 实验环境：Window10 64位 ，Dev-C++
二、实验内容，测试数据及程序运行结果分析
问题一：

【问题描述】假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。(0<m,n,k<1000)
【输入形式】第一行男士人数m和女士人数n； 第二行舞曲的数目k。
【输出形式】共k行，每行两个数，表示配对舞伴的序号，男士在前，女士在后。

【样例输入】

2 4
6

【样例输出】

1 1
2 2
1 3
2 4
1 1
2 2

思路：从题目中，易提取出关键:女队和男队是各自同时循环输出，故将循环队列封装，进行运用。

//SeqQueue.h
#include <iostream>
#include<cstdio>
using namespace std;
class Node {//定义节点
	public:
		Node *next;
		int data;
};
class SeqQueue {
	private:
		Node* head;
		int length;//循环列表元素个数 
	public:
		SeqQueue () {
			head = new Node(); 
			head->next = head;
			head->data = 0;
			length = 0;
		}
		~SeqQueue () {
			delete(head);
		}
		void createSeqQueue (int n);  //创建单向循环链表
		void traverseNode(); 		   //遍历链表
		void deleteNode(int n);        //删除位置为n的结点
		void insertNode(int n,int data);//在制定位置插入结点
		int getLength();               //得到链表长度
		bool isEmpty();                //判断链表是否为空
		int getNumber(int n);//得到n位置的元素
};
void SeqQueue ::createSeqQueue (int n) {   //创建单向循环链表
	if(n<0) {
		cout << "n error " << endl;
	} else {
		length = n;
		Node *p,*q;
		p = head;
		for(int i=1; i<=n; i++) {
			q = new Node();
			q->data=i;
			p->next = q;
			q->next = head;		//尾节点指向头节点
			p = q;
		}
	}
}
void SeqQueue ::traverseNode() { //遍历链表
	Node *p;
	p = head->next;
	while(p!=head) {
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}

void SeqQueue ::deleteNode(int n) {    //删除n位置的结点
	if(n<0||n>length) {
		printf("delete is  illegal\n");
		return;
	} else {
		Node *p,*q;
		p = head;
		for(int i=1; i<n; i++)//找到n位置 
			p=p->next;
		q = p->next;	 
		p->next = q->next;
		delete q;
		q = NULL;
		length--;
	}
}
void SeqQueue ::insertNode(int n,int data) {  //在n位置插入一个节点  节点的值为data
   Node *q,*p = new Node();
   p->data = data;
   q = head;
	for(int i = 1; i<n; i++)//找到n位置 
		q = q->next;
	p->next = q->next;//插入 
	q->next = p;
}
int SeqQueue ::getNumber(int n) {
	Node *q = new Node();
	q = head;
	for(int i = 1; i<=n; i++)
		q = q->next;
	return q->data;
}
int SeqQueue ::getLength() {   //返回循环链表长度
	return length;
}
bool SeqQueue ::isEmpty() {    //判断是否为空
	return head==head->next;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

main

#include <iostream>
#include<cstdio>
#include"SeqQueue.h"
using namespace std;
int main() {
	SeqQueue que_women,que_men;
	int NumberOfwomen,NumberOfmen;//女队人数，男队人数 
	int NumberOfsong;//歌数 
	
	scanf("%d%d%d",&NumberOfmen,&NumberOfwomen,&NumberOfsong);
	que_women.createSeqQueue(NumberOfwomen);
	que_men.createSeqQueue(NumberOfmen);
	int i=1;//男队出列第i号 
	int j=1;//女队出列第j号 
	for(int k=0; k<NumberOfsong; k++) {
		if(i>NumberOfmen) i=1;
		if(j>NumberOfwomen) j=1;
		printf("%d %d\n",que_men.getNumber(i),que_women.getNumber(j));
		i++;
		j++;
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

性能分析：
时间复杂度是O(k),k为歌曲数目。
优化方案：
对于男队和女队数量较少时，用数组直接循环输出更方便，但数据量很大时，内存连续空间就可能不够，此时就应用队列链表。

#include <iostream>
#include<cstdio>
using namespace std;
const int MAXN=1000;
int women[MAXN],men[MAXN];
int main() {
	int NumberOfwomen,NumberOfmen;//女队人数，男队人数 
	int NumberOfsong;//歌数 
	cin>>NumberOfmen>>NumberOfwomen>>NumberOfsong;
	int k;
	for(k=1;k<=NumberOfwomen;k++)
	{
		women[k]=k;
	}
	for(k=1;k<=NumberOfmen;k++)
	{
		men[k]=k;
	}
	int i=1;//男队出列第i号 
	int j=1;//女队出列第j号 
	for(k=0; k<NumberOfsong; k++) {
		if(i>NumberOfmen) i=1;
		if(j>NumberOfwomen) j=1;
		cout<<men[i]<<" "<<women[j]<<endl;
		i++;
		j++;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

输出结果

问题二：

【问题描述】
输入一个后缀表达式，求这个表达式的值。输入的数字皆为大于或等于零的整数，涉及的运算只有加法、减法及乘法。数字之间用空格隔开。表达式以#结束
【输入形式】 以#为结束标志的后缀表达式
【输出形式】 后缀表达式的计算结果

【样例输入】

10 5 2 3 * - 2 * + #

【样例输出】

8

思路：主要解决问题，输入类型有整形和字符型，因为字符型转整型容易，且以#为输入结束标志，所以输入变量类型为字符。

//利用str输入
#include <iostream>
#include<cstdio>
#include<stack>
#include<cstdlib>
using namespace std;

int main() {
	stack<int> sta;
	string str;
	cin>>str;
	while(str!="#") {
		if(str=="+"||str=="-"||str=="*") {//遇符号，取出栈top1，top2进行运算，运算结果存入栈中
			int n1,n2,sum;
			n1=sta.top();
			sta.pop();
			n2=sta.top();
			sta.pop();
			switch(str[0]) {
				case'+':
					sum=n2+n1;
					break;
				case'-':
					sum=n2-n1;
					break;
				case'*':
					sum=n2*n1;
					break;
			}
			sta.push(sum);
		} else {//遇数字，存入栈中
			int temp=atoi(str.c_str());//字符串转整型
			sta.push(temp);
		}
		cin>>str;
	}
	cout<< sta.top()<<endl;
	return 0;
}
//10 5 2 3 * - 2 * + #

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

//利用char输入
#include <iostream>
#include<cstdio>
#include<stack>
#include<cstdlib>
using namespace std;
int main() {
	stack<int> sta;
	char ch;
	char buffer[10];//缓冲区，存暂时输入的整数 
	int i=0,n1,n2;
	int sum;
	scanf("%c",&ch);
	while(ch!='#') {
		while(ch>='0'&&ch<='9') {//输入整数
			buffer[i++]=ch;
			buffer[i]='\0';
			scanf("%c",&ch);
			if(ch==' ') {//遇到空格，输入一个完整的整数
				int temp=atoi(buffer);
				sta.push(temp);
				i=0;
				break;
			}
		}
		if(ch=='+'||ch=='-'||ch=='*') {
			n1=sta.top();
			sta.pop();
			n2=sta.top();
			sta.pop();
			switch(ch) {
				case'+':
					sum=n1+n2;
					break;
				case'-':
					sum=n2-n1;
					break;
				case'*':
					sum=n2*n1;
					break;
			}
			sta.push(sum);
		}
		scanf("%c",&ch);
	}
	printf("%d\n",sta.top());
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

运行结果

问题三：

【问题描述】首先建立一个单链表，通过栈实现该链表的原地逆置，注意仅使用链表中的原有的结点空间，结点的数据成员为int型。注意这个题需要单链表和栈两个类。
【输入形式】输入只有一行，依次输入若干个整数，整数之间用一个空格分开，最后以-1结束，用表尾添加结点的方法建立一个单链表。
【输出形式】输出有2行，第1行为原链表数据，第2行为逆置后的链表数据，具体格式见样例输出

【样例输入】

1 2 3 4 5 -1

【样例输出】

1–>2–>3–>4–>5
5–>4–>3–>2–>1

#include <iostream>
#include"list.h"
#include<cstdio>
#include<stack> 
using namespace std;
int main() {
	List<int>L;
	L.inputRear(-1);//输入单链表 
	L.output();//输出原单链表 
	stack<int> sta;
	int x;
	for(int i=0; i<L.Length(); i++) {//输入栈 
		L.getData(i+1,x);	
		sta.push(x);
	}
	for(int i=0; i<L.Length(); i++) {//栈输出，利用先进后出逆置链表 
		x=sta.top();
		L.setData(i+1,x);
		sta.pop();
	}
	L.output();
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

性能分析：
时间复杂度是O(length),length为列表长度。
优化方案：
可以采取就地逆置，但对于链表来说，双指针，一个指针指向头指针，另一个指针先遍历至链表末端后，然后两个指针指向的数据互相交换，往中间靠，直至两指针指向相等。两个思路的时间复杂度差不多，但第二个思路空间复杂度低一些。

二、实验过程中出现的问题及解决方法
第二个问题中，输入卡了很久，在用char输入的时候，所有输入输出都用cin和cout，运行结果都如下所示

反复检查代码，思路是没有逻辑问题，debug了许久，发现是输入问题，于是查询相关资料，cin和scanf对于字符输入的区别 ：scanf 输入字符时，会将’\n’吸收，而cin输入字符的时候，’\n’不会被吸收。