当前位置:   article > 正文

实验二,栈和队列的使用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’不会被吸收。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Monodyee/article/detail/668353
推荐阅读
相关标签
  

闽ICP备14008679号