一、实验目的与实验环境
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;
}
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;
}
性能分析：
时间复杂度是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;
}
输出结果
问题二：
【问题描述】
输入一个后缀表达式，求这个表达式的值。输入的数字皆为大于或等于零的整数，涉及的运算只有加法、减法及乘法。数字之间用空格隔开。表达式以#结束
【输入形式】 以#为结束标志的后缀表达式
【输出形式】 后缀表达式的计算结果
【样例输入】
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 * + #
//利用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;
}
运行结果
问题三：
【问题描述】首先建立一个单链表，通过栈实现该链表的原地逆置，注意仅使用链表中的原有的结点空间，结点的数据成员为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;
}
性能分析：
时间复杂度是O(length),length为列表长度。
优化方案：
可以采取就地逆置，但对于链表来说，双指针，一个指针指向头指针，另一个指针先遍历至链表末端后，然后两个指针指向的数据互相交换，往中间靠，直至两指针指向相等。两个思路的时间复杂度差不多，但第二个思路空间复杂度低一些。
二、实验过程中出现的问题及解决方法
第二个问题中，输入卡了很久，在用char输入的时候，所有输入输出都用cin和cout，运行结果都如下所示
反复检查代码，思路是没有逻辑问题，debug了许久，发现是输入问题，于是查询相关资料，cin和scanf对于字符输入的区别 ：scanf 输入字符时，会将’\n’吸收，而cin输入字符的时候，’\n’不会被吸收。