实验二 堆栈和队列基本操作的编程实现
【实验目的】
堆栈和队列基本操作的编程实现
要求：
堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。
【实验性质】
验证性实验（学时数：2H）
【实验内容】
内容：
把堆栈和队列的顺序存储（环队）和链表存储的数据进队、出队等运算其中一部分进行程序实现。可以实验一的结果自己实现数据输入、数据显示的函数。
利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。
【思考问题】
1. 栈的顺序存储和链表存储的差异？
2. 还会有数据移动吗？为什么？
3. 栈的主要特点是什么？队列呢？
4. 栈的主要功能是什么？队列呢？
5. 为什么会有环状队列？
【参考代码】
（一）利用顺序栈实现十进制整数转换转换成r进制
1、算法思想
将十进制数N转换为r进制的数，其转换方法利用辗转相除法，以N=3456，r=8为例转换方法如下：
N N / 8 （整除） N % 8（求余）
3456 432 0 低
432 54 0
54 6 6
6 0 6 高
所以：（3456）10 =（6600）8
我们看到所转换的8进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。
算法思想如下：当N>0时重复1，2
①若 N≠0，则将N % r 压入栈s中 ，执行2;若N=0，将栈s的内容依次出栈，算法结束。 ②用N / r 代替 N
2、转换子程序
#include<stdio.h>
#define L_size 100 //根据需要自己定义L_size为顺序栈的最大存储容量 void conversion(int N,int r)
{ //将十进制数N转换为r进制的数
int s[L_size],top;
//定义一个顺序栈，top为栈顶指针，注意此处没有使用结构体类型
int x;
top=-1; //初始化栈
while (N!=0) //此循环为入栈操作
{
//余数入栈
//商作为被除数继续
}
while (top!=-1)
{
x=s[top--];
if(x==10)printf("A");
else if(x==11)printf("B");
else if(x==12)printf("C");
else if(x==13)printf("D");
else if(x==14)printf("E");
else if(x==15)printf("F");
else printf("%d",x);
}
printf("\n");
}
3、编写主函数验证上述转换子函数是否正确。
void main()
{
int number,r; //number为待准备转换的十进制数，r为进制 printf("请输入一个十进制整数：");
scanf("%d",&number);
printf("选择将该数转换为几进制数(2，8，16)：");
scanf("%d",&r);
printf("转换后的结果为：");
conversion(number,r);
}
（二）用顺序栈实现算术后缀表达式求值
1、算法思想。
后缀表达式求值步骤：
a、循环读出后缀表达式中的每一个字符；
b、若是数字，将对应的字符串转换成整数，入栈；
c、若是运算符，从栈中弹出2个数，将运算结果再压入栈；
d、若表达式输入完毕，栈顶即表达式值；
2、后缀表达式求值子程序 //此循环为出栈操作
#include<stdio.h>
#include<stdlib.h>
#define L_size 50
void postexp()
{
int st[L_size],top=-1; //定义一个顺序栈，top为栈顶指针
int d=0; //定义用来字符串转换整数的变量d
char ch;
printf("请输入规范的后缀表达式(操作数、运算符之间使用空格间隔开，eg:3 2 5 * +):\n"); //输入范例
while((ch=getchar())!='\n') { if(ch==' ') else switch(ch) { //判断输入是否运算符，如果时就进行相应的操作 //开始输入字符并赋给ch //如果输入的是空格，不做处理 case '+': ; ; break; case '-': st[top-1]=st[top-1]-st[top]; top--; break; case '*': st[top-1]=st[top-1]*st[top]; top--; break; case '/': if(st[top]!=0)//分母不为零计算才有效 { st[top-1]=st[top-1]/st[top]; top--; } else { } printf("除数为0!\n"); //分母为零计算无效，退出程序 exit(1); break; default: while(ch>='0'&&ch<='9') { ; ch=getchar();
} } st[++top]=d;//将转换后的数值入栈 d=0;
}
printf("运算结果是:%d\n",st[top]);
}
3、编写主函数验证上述求值子函数是否正确。
void main()
{
postexp();
}
（三）链式队列基本操作
1、队列结点定义
根据实际处理数据的类型定义链队中结点的值域类型ElemType
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
typedef int Elemtype;
typedef struct node //队列结点类型定义
{ Elemtype data;
struct node *link;
}NODE;
struct QueueLk
{ //定义链队
NODE *front,*rear;//定义链队队头和队尾指针
};
2、入队
struct QueueLk *ldcr(struct QueueLk *QL,Elemtype x)
//将元素x插入到链队列rear中，作为rear的新队尾
{
NODE *p;
p=(NODE *)malloc(sizeof(NODE));
p->data=x;
p->link=NULL; //置新结点的指针为空
if(QL->front==NULL) QL->front=QL->rear=p; //队列为空 //队列的数据元素类型 //指向后继结点的指针 else { ; //将链队列中最后一个结点的指针指向新结点 ; //将队尾指向新结点
}
return QL;
}
3、出队
Elemtype ldsc(struct QueueLk *QL)
//若链队列不为空，则删除队头元素，返回其元素值
{ NODE *s;
Elemtype x;
if(QL->front==QL->rear) //队空，退出程序
exit(1);
s=QL->front->link; //取队头保存在s中
; //删除队头结点
if(s->link==NULL) //如果删除后队列为空，则处理队尾指针 QL->rear=QL->front;
x=s->data; //将刚才出队的结点值给x
; //释放出该结点的空间 return x;
}
4、队列的初始化
void initqueue(QueueLk *QL)
{
QL->front=(NODE *)malloc(sizeof(NODE));
}
5、队列的显示
void dispqueue(QueueLk *QL)
{
NODE *q;
q=QL->front->link; if(q==NULL)printf("队列已空!\n"); while(q!=NULL) { printf("%5d",q->data); q=q->link; } printf("\n"); QL->front->link=NULL; QL->rear=QL->front;
}
6、编写主函数验证上述子函数是否正确。
void main()
{
struct QueueLk *p; int choice,elemdata,x=0; p=(struct QueueLk *)malloc(sizeof(struct QueueLk)); initqueue(p); while(1)
{
printf("请输入你的操作选择：\n");
printf("(1)元素入队请按数字1!\n"); printf("(2)元素出队请按数字2!\n");
printf("(3)显示队列请按数字3!\n"); printf("(4)清屏幕请按数字4!\n"); printf("(5)退出程序请按数字5!\n"); scanf("%d",&choice);
switch(choice) { case 1:printf("请输入待进队元素的值："); scanf("%d",&elemdata); p=ldcr(p,elemdata); break;
case 2:x=ldsc(p); printf("元素%d出队成功!\n",x); break; case 3:printf("队列中的元素分别为：\n"); dispqueue(p); break; case 4:system("cls"); break; case 5:return; }
}
}
【实验小结】 (总结本次实验的重难点及心得、体会、收获)
得 分_____________
评阅日期_____________
教师签名__ __________
第二篇：实验 二 栈和队列的基本操作实现及其应用
软件114班李大宝 201100834416
数
据
结
构
实
验
报
告
（二）
姓名: 李 大 宝 学院：计算机学院
第1页
软件114班李大宝 201100834416
实验 二 栈和队列的基本操作实现及其应用
一、实验目的
1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。
2、会用栈和队列解决简单的实际问题。
二、实验内容
题目一
试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。
一、相关常量及结构定义：
# define STACK_INIT_SIZE 100
# define STACKINCREMENT 10
# define OK 1
# define ERROR 0
typedefcharSElemType; //把char类型定义为SElemType
//栈类型定义
typedefstructSqStack
{ SElemType *base; //栈底
SElemType *top; //栈顶
intstacksize; //最大容量
}SqStack;
//队列类型定义
typedefstructQNode
{
SElemType data;
structQNode *next;
}QNode,*QueuePtr;
typedefstruct
{
QueuePtr front; //队首
QueuePtr rear; //队尾
}LinkQueue;
二、设计相关函数声明：
判断函数：
intIsReverse()
栈：
intInitStack(SqStack&S )
int Push(SqStack&S, SElemType e )
int Pop(SqStack&S,SElemType&e)
intStackEmpty(s)
队列；
第2页
软件114班李大宝 201100834416
intinitqueue(LinkQueue&Q)
intEnQueue(LinkQueue&Q,SElemType e)
intDeQueue(LinkQueue&Q,SElemType&e)
三、函数说明：
1、栈初始化
/*
函数功能：对栈进行初始化
参数：栈(SqStack&S)
成功初始化返回1,否则返回0 */
intInitStack(SqStack&S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); //对栈申请空间。
if(!S.base)
exit(0); //未申请空间退出。
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
2、弹出栈顶元素，并返回
/*
函数功能：对栈删除栈顶元素
参数：栈SqStack&S, 元素SElemType&e
用e返回栈顶元素 */
int Pop(SqStack&S,SElemType&e)
{
if(S.top==S.base) //栈为空时返回错误。
return ERROR;
e=*--S.top; //成功返回栈顶元素
return OK;
}
3、向栈中压入元素
/*
函数功能：向栈中压入元素
参数：栈SqStack&S, 元素SElemTypee
成功压入返回1，否则返回0 */
int Push(SqStack&S,SElemType e)
{
if(S.top-S.base>=S.stacksize) //栈的大小过小时，从新申请内存 {
S.base=(SElemType
*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base)
exit(0);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++ = e; //成功压入元素。
第3页
软件114班李大宝 201100834416
return OK;
}
4、栈是否为空
/*
函数功能：判断栈是否为空
参数：栈SqStackS
为空返回1，否则返回0 */
intStackEmpty(SqStack S)
{
if(S.top==S.base) //为空条件S.top=S.base return OK;
else
return ERROR; //不空返回0
}
5、队列初始化
/*
函数功能：对队列进行初始化
参数：队列(LinkQueue&Q)
成功初始化返回1,否则返回0 */
intinitqueue(LinkQueue&Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)
exit(ERROR);
Q.front->next=NULL;
return OK;
}
6、入队
/*
函数功能：对队列进行入队
参数：队列LinkQueue&Q，元素SElemType e 成功入栈返回1 */
intEnQueue(LinkQueue&Q,SElemType e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));//对p申请内存 if(!p)
exit(ERROR); //未申请到内存退出 p->data=e;
p->next=NULL;
if(Q.rear==NULL) //队列为空时
{
Q.front->next=p;
Q.rear=p;
}
Else //队列不为空时
{
第4页
软件114班李大宝 201100834416
Q.rear->next=p;
Q.rear=p; //在队尾入栈
}
return OK;
}
7、出队
/*
函数功能：对队列进行出队
参数：队列LinkQueue&Q，元素SElemType&e
用元素e将队首元素进行返回
成功出栈返回1 */
intDeQueue(LinkQueue&Q,SElemType&e)
{
if(Q.front==Q.rear)
return ERROR; //队空
QueuePtr p;
p=Q.front->next;
e=p->data; //队首元素
Q.front->next=p->next;
if(Q.rear==p) //p为最后一个元素时
Q.rear=Q.front;
free(p); //释放p节点
return OK;
}
8、判断函数：
/*
函数功能：判断字符串是否是回文字符串
参数：栈SqStack S,队列LinkQueue&Q
如果是回文字符串返回1，否则返回0 */
intIsReverse(SqStackS,LinkQueue Q)
{
SElemTypea,b;
while(!StackEmpty(S)) //栈不为空时
{
Pop(S,a);
DeQueue(Q,b);
if(a!=b) //栈顶元素与队首元素进行比较，不相等返回0 return 0;
}
return 1; //栈与队列相同返回1，即字符串为回文字符串。 }
三、主函数设计
int main()
{
char YES; //用来存放字符
do
{
SElemType e;
SqStack S;
第5页
软件114班李大宝 201100834416
} LinkQueue Q; InitStack(S); //初始化栈 initqueue(Q); //初始化队列 cout<<"请输入字符串以'@'结尾！"<<endl; while((e=getchar())!='@') //输入以@结束。 { Push(S,e); //入栈 EnQueue(Q,e); //入队 } if(IsReverse(S,Q)==1)//判断返回是否为1，为1就是回文字符串 cout<<"此字符串是回文字符串"<<endl; else cout<<"此字符串不是回文字符串"<<endl; cout<<"是否继续，继续（y/Y），其他键退出"<<endl; cin>>YES; getchar(); //getchar()接收缓冲区本来保存的东西 }while(YES=='y'||YES=='Y'); return 0;
四、程序调试及运行结果分析
程序完美运行。
特别注意：
cin>>YES;
getchar();
这里很容易出错getchar()是用来做缓冲。用getchar()接收缓冲区本来保存的东西
程序运行结果如下：
五、实验总结
通过这次试验我熟悉了对栈和队列的基本操作，
对基本的栈和队列操作有了
第6页
软件114班李大宝 201100834416
很好的掌握，知道自己容易在什么地方出错。
六、程序清单
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;
# define STACK_INIT_SIZE 100
# define STACKINCREMENT 10
# define OK 1
# define ERROR 0
typedef char SElemType;
typedefstructSqStack
{
SElemType *base;
SElemType *top;
intstacksize;
}SqStack;
typedefstructQNode
{
SElemType data;
structQNode *next;
}QNode,*QueuePtr;
typedefstruct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
intInitStack(SqStack&S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)
exit(0);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
int Pop(SqStack&S,SElemType&e)
{
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
int Push(SqStack&S,SElemType e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType
*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base)
第7页
软件114班李大宝 201100834416
exit(0);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
intStackEmpty(SqStack S)
{
if(S.top==S.base)
return OK;
else
return ERROR;
}
intinitqueue(LinkQueue&Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)
exit(ERROR);
Q.front->next=NULL;
return OK;
}
intEnQueue(LinkQueue&Q,SElemType e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)
exit(ERROR);
p->data=e;
p->next=NULL;
if(Q.rear==NULL)
{
Q.front->next=p;
Q.rear=p;
}
else
{
Q.rear->next=p;
Q.rear=p;
}
return OK;
}
intDeQueue(LinkQueue&Q,SElemType&e)
{
if(Q.front==Q.rear)
return ERROR;
QueuePtr p;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
第8页
软件114班李大宝 201100834416
Q.rear=Q.front;
free(p);
return OK;
}
intIsReverse(SqStackS,LinkQueue Q)
{
SElemTypea,b;
while(!StackEmpty(S))
{
Pop(S,a);
DeQueue(Q,b);
if(a!=b)
return 0;
}
return 1;
}
int main()
{
char YES;
do
{
SElemType e;
SqStack S;
LinkQueue Q;
InitStack(S);
initqueue(Q);
cout<<"请输入字符串以'@'结尾！"<<endl;
while((e=getchar())!='@')
{
Push(S,e);
EnQueue(Q,e);
}
if(IsReverse(S,Q)==1)
cout<<"此字符串是回文字符串"<<endl; else
cout<<"此字符串不是回文字符串"<<endl;
cout<<"是否继续，继续（y/Y），其他键退出"<<endl; cin>>YES;
getchar(); //表示缓冲字符YES； }while(YES=='y'||YES=='Y');
return 0;
} STL标准模板库程序：
#include<iostream>
using namespace std;
#include<stack>
#include<queue>
stack<char> s;
第9页
软件114班李大宝 201100834416
queue<char> q;
intIsReverse()
{
while(!s.empty())
{
if(s.top()!=q.front())
return 0;
s.pop();
q.pop();
}
return 1;
}
int main()
{
char YES;
do
{
cout<<"请输入字符串以'@'结尾！"<<endl;
char e;
while((e=getchar())!='@')
{
s.push(e);
q.push(e);
}
getchar();
if(IsReverse()==1)
cout<<"此字符串是回文字符串"<<endl;
else
cout<<"此字符串不是回文字符串"<<endl;
while(!s.empty())
s.pop();
while(!q.empty())
q.pop();
cout<<"是否继续，继续（y/Y），其他键退出"<<endl;
cin>>YES;
getchar();
}while(YES=='y'||YES=='Y');
}
题目二
编程模拟队列的管理，主要包括：出队列、入队、统计队列的长度、查找队列某个元素e、及输出队列中元素。
[实现提示]：参考教材循环队列的有关算法，其中后两个算法参考顺序表的实现。
第10页
软件114班李大宝 201100834416
一、相关结构定义
#define elemtypeint //定义int为elemtype类型
typedefstruct STD
{
elemtype data;
struct STD *next;
}Qnode,*Queueptr;
typedefstruct
{
Queueptr front; //队首
Queueptr rear; //队尾
int count;
}linkqueue;
二、函数说明：
1、初始化队列
/*
函数功能：对队列进行初始化
参数：队列(linkqueue&Q)
成功初始化返回1,否则返回0 */
intinit(linkqueue&Q)
{
Q.front=Q.rear=(Queueptr)malloc(sizeof(Qnode)); //对队列申请空间。 if(!Q.front)
exit(0); //未申请空间退出。
Q.front->next=NULL;
Q.count=0;
return 1;
}
2.出队
/*
函数功能：对队列进行出队
参数：队列linkqueue&Q，元素elemType&e
成功出栈返回1 */
intdequeue(linkqueue&Q)
{
Queueptr p;
if(Q.front==Q.rear) //队空
return 0;
p=Q.front->next;
Q.front->next=p->next;
if(Q.rear==p) //p为最后一个元素时
Q.rear=Q.front;
free(p); //释放p节点
Q.count--; //队长度减1
return 1;
}
3.入队
/*
第11页
软件114班李大宝 201100834416
函数功能：对队列进行入队
参数：队列linkqueue&Q，元素elemType e
成功入栈返回1 */
intenqueue(linkqueue&Q,elemtype e)
{
Queueptr p;
p=(Queueptr)malloc(sizeof(Qnode)); //对p申请内存 if(!p)
exit(0); //未申请到内存退出
p->data=e;
p->next=NULL;
if(Q.front==NULL) //队列为空时 {
Q.front->next=p;
Q.rear=p;
}
Else//队列不为空时
{
Q.rear->next=p;
Q.rear=p;//在队尾入栈
}
Q.count++; //长度加1。
return 1;
}
4.长度
/*
函数功能：返回队列的长度
参数：队列linkqueueQ
返回Q.count */
int length(linkqueue Q)
{
return Q.count; //队列的长度
}
5.查找
/*
函数功能：在队列中查找元素
参数：队列linkqueueQ，元素elemtype e
找到返回1，否则返回0 */
int find(linkqueueQ,elemtype e)
{
Queueptr p;
p=Q.front->next;
while(p)
{
if(p->data==e) //找到元素e返回1 return 1;
p=p->next;
}
第12页
软件114班李大宝 201100834416
return 0; //找不到元素e返回0
}
6.显示
/*
函数功能：显示队列中所有元素
参数：队列linkqueueQ
无返回值 */
void show(linkqueue Q)
{
Queueptr p;
p=Q.front->next;
while(p) //队列元素不为空时
{
cout<<p->data<<'\t'; //输出元素值
p=p->next;
}
cout<<endl;
}
7.主界面
/*
函数功能：操作主界面
参数：无
无返回值 */
voidzhujiemian()
{
cout<<endl<<endl;
cout<<"\t\t\t\t数据结构实验二"<<endl;
cout<<"\t\t----------------------------------------------"<<endl<<endl; cout<<"\t\t 1 队列初始化"<<endl;
cout<<"\t\t 2 出队列"<<endl;
cout<<"\t\t 3 入队列"<<endl;
cout<<"\t\t 4 队列长度"<<endl;
cout<<"\t\t 5 在队列中查找元素"<<endl;
cout<<"\t\t 6 遍历队列"<<endl;
cout<<"\t\t其他键退出"<<endl;
cout<<"\t\t----------------------------------------------"<<endl<<endl<<endl; cout<<"\t请选择要进行操作的序号（1--6）:";
//选择数字序号进行不同的操作
}
三、主函数设计
int main()
{
linkqueue Q;
inta,b,c;
zhujiemian();
cin>>a;
while(a!=1) //第一步一定要对队列初始化
{
cout<<"输入错误，必须先初始化，请重新输入：";
cin>>a;
}
cout<<endl;
do
第13页
软件114班李大宝 201100834416
} { switch(a) { case 1: if(init(Q)==1) cout<<"初始化成功！"<<endl; else cout<<"初始化失败！"<<endl; break; case 2: if(length(Q)==0) { cout<<"队列为空无法出队！"<<endl; break; } if(dequeue(Q)==1) cout<<"删除成功！"<<endl; else cout<<"删除失败！"<<endl; break; case 3: cout<<"输入你要入队元素"<<endl; cin>>c; if(enqueue(Q,c) ==1) cout<<"入队成功！"<<endl; else cout<<"入队失败！"<<endl; break; case 4: b=length(Q); cout<<"队列的长度为："<<b<<endl; break; case 5: cout<<"您要查找的元素："; cin>>b; if(find(Q,b)==1) cout<<"恭喜您，队列中有您要找的元素"<<b<<endl; else cout<<"不好意思，队列中没有您要找的元素"<<b<<endl; break; case 6: if(length(Q)==0) { cout<<"队列为空！"<<endl; break; } show(Q); break; default: break; } system("pause"); // 按任意键继续 system("cls"); //清屏 zhujiemian(); cin>>a; cout<<endl; }while(a>0&&a<=6); //判断输入的a是否在1-6之间。 return 0;
第14页
软件114班李大宝 201100834416
四、程序调试及运行结果分析
运行主界面：
操作界面清晰，方便操作。
入队：
出队：
当队列为空时不会出现错误。
第15页
软件114班李大宝 201100834416
查找：
五、实验总结
通过这个实验我明白了队列的基本操作，和熟练掌握了队列的基本实现。通过这次实验我懂得了关于队列该如何操作。
六、程序清单
#include <cstdio>
#include <stdlib.h>
#include <iostream>
#include <malloc.h>
#include <windows.h>
第16页
软件114班李大宝 201100834416
using namespace std;
#define elemtypeint
typedefstruct STD
{
elemtype data;
struct STD *next;
}Qnode,*Queueptr;
typedefstruct
{
Queueptr front;
Queueptr rear;
int count;
}linkqueue;
intinit(linkqueue&Q)
{
Q.front=Q.rear=(Queueptr)malloc(sizeof(Qnode)); if(!Q.front)
exit(0);
Q.front->next=NULL;
Q.count=0;
return 1;
}
intdequeue(linkqueue&Q)
{
Queueptr p;
if(Q.front==Q.rear)
return 0;
p=Q.front->next;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
Q.count--;
return 1;
}
intenqueue(linkqueue&Q,elemtype e)
{
Queueptr p;
p=(Queueptr)malloc(sizeof(Qnode));
if(!p)
exit(0);
p->data=e;
p->next=NULL;
if(Q.front==NULL)
{
Q.front->next=p;
Q.rear=p;
}
else
{
Q.rear->next=p;
第17页
软件114班李大宝 201100834416
Q.rear=p;
}
Q.count++;
return 1;
}
int length(linkqueue Q)
{
returnQ.count;
}
int find(linkqueueQ,elemtype e)
{
Queueptr p;
p=Q.front->next;
while(p)
{
if(p->data==e)
return 1;
p=p->next;
}
return 0;
}
void show(linkqueue Q)
{
Queueptr p;
p=Q.front->next;
while(p)
{
cout<<p->data<<'\t';
p=p->next;
}
cout<<endl;
}
voidzhujiemian()
{
cout<<endl<<endl;
cout<<"\t\t\t\t数据结构实验二"<<endl;
cout<<"\t\t----------------------------------------------"<<endl<<endl; cout<<"\t\t 1 队列初始化"<<endl;
cout<<"\t\t 2 出队列"<<endl;
cout<<"\t\t 3 入队列"<<endl;
cout<<"\t\t 4 队列长度"<<endl;
cout<<"\t\t 5 在队列中查找元素"<<endl;
cout<<"\t\t 6 遍历队列"<<endl;
cout<<"\t\t其他键退出"<<endl;
cout<<"\t\t----------------------------------------------"<<endl<<endl<<endl;
cout<<"\t请选择要进行操作的序号（1--6）:";
}
int main()
{
linkqueue Q;
第18页
软件114班李大宝 201100834416
inta,b,c; zhujiemian(); cin>>a; while(a!=1) { cout<<"输入错误，必须先初始化，请重新输入："; cin>>a; } cout<<endl; do { switch(a) { case 1: if(init(Q)==1) cout<<"初始化成功！"<<endl; else cout<<"初始化失败！"<<endl; break; case 2: if(length(Q)==0) { cout<<"队列为空无法出队！"<<endl; break; } if(dequeue(Q)==1) cout<<"删除成功！"<<endl; else cout<<"删除失败！"<<endl; break; case 3: cout<<"输入你要入队元素"<<endl; cin>>c; if(enqueue(Q,c) ==1) cout<<"入队成功！"<<endl; else cout<<"入队失败！"<<endl; break; case 4: b=length(Q); cout<<"队列的长度为："<<b<<endl; break; case 5: cout<<"您要查找的元素："; cin>>b; if(find(Q,b)==1) cout<<"恭喜您，队列中有您要找的元素"<<b<<endl; else cout<<"不好意思，队列中没有您要找的元素"<<b<<endl; break; case 6: 第19页
软件114班李大宝 201100834416
} if(length(Q)==0) { cout<<"队列为空！"<<endl; break; } show(Q); break; default: break; } system("pause"); system("cls"); zhujiemian(); cin>>a; cout<<endl; }while(a>0&&a<=6); return 0;
题目三、Rails
Description
There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.
The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N <= 1000 coaches numbered in increasing order 1, 2, ..., N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, ..., aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in
the direction A and also once it has left the station in the direction B it cannot return back to the
第20页
软件114班李大宝 201100834416
station.
Input
The input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, ..., N. The last line of the block contains just 0. The last block consists of just one line containing 0. Output
The output contains the lines corresponding to the lines with permutations in the input. A line of the output contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input. Otherwise it contains No. In addition, there is one empty line after the lines corresponding to one block of the input. There is no line in the output corresponding to the last ``null'' block of the input.
Sample Input
5
1 2 3 4 5
5 4 1 2 3
6
6 5 4 3 2 1
Sample Output
Yes
No
Yes
程序清单：（STL标准模板库）
一、
#include<cstdio>
#include<iostream>
#include<stack>
using namespace std;
int a[1001],n,i,j;
int fan()
{
stack<int>s; //火车是按（1--n）的顺序进栈
inti,j;
for(i=0,j=1;i<n&&j<=n+1;)
{
if(s.empty()||s.top()!=a[i])//栈空或栈顶元素不与a[i]相同时进站
{
if(j==(n+1)) //不能正常出站条件
return 0; //不能正常出站返回0
第21页
软件114班李大宝 201100834416
s.push(j++); //将j压入栈中
}
else //栈顶元素与a[i]相同时进站
{
s.pop(); //弹出栈顶元素
i++; //i++，a的下个元素继续进行
}
}
return 1;
}
/*
fan()解释：
1--n和a[n]的每个元素进行比较。
用j=1，j++表示1—n的每个元素
用a[i]（0<=i<n）表示a[i]的每个元素。
如果栈为空时让j进栈，然后j++。
如果栈顶元素与a[i]不相同，让j进栈，然后j++。
如果栈顶元素与a[i]相同，弹出栈顶元素，然后i++。
结束条件：1、j=(n+1)时表示不能按给出的顺序出站，则返回0
2、循环结束返回1
*/
int main()
{
while(scanf("%d",&n),n)//有多少辆火车，以0结束。
{
while(scanf("%d",&a[0]),a[0]) //输入出站次序，以0结束 {
for(i=1;i<n;i++)
scanf("%d",&a[i]); //把出站次序放在数组a中。
if(fan())
printf("Yes\n"); //可以出站输出Yes
else
printf("No\n"); //不可以正常出站输出No
}
}
return 0;
}
运行结果：
第22页
软件114班李大宝 201100834416
二、
#include<cstdio>
#include<iostream>
#include<stack>
using namespace std;
int a[1001],n,i,j,k;
int fan()
{
stack<int>s;
inti,j=0,k;
for(i=1;i<=n;i++)
{
if(a[j]==i) //当a[j]与i相同时
{
j++; //进行下一个a中的元素
while(!s.empty())//栈不空时
{
k=s.top(); //得到栈顶元素
s.pop(); //弹出栈顶元素
if(k==a[j]) //栈顶元素与a[j]相同，继续进行下一个 j++;
else //栈顶元素与a[j]不同时
{
s.push(k); //把k再压入栈中
break; //if语句结束。
第23页
软件114班李大宝 201100834416
}
}
}
else //当a[j]与i不相同时把i压入栈中
s.push(i);
}
if(s.empty()) //栈空返回1
return 1;
else //栈不空返回0
return 0;
}
int main()
{
while(scanf("%d",&n),n)
{
while(scanf("%d",&a[0]),a[0])
{
for(i=1;i<n;i++)
scanf("%d",&a[i]);
if(fan())
printf("Yes\n");
else
printf("No\n");
}
}
return 0;
}
/*
主要解释一下fan()
1--n和a[n]的每个元素进行比较。
用i=1，i++表示1—n的每个元素
用a[j]（0<=j<n）表示a[j]的每个元素。
当a[j]与i相同时，j++，让栈顶元素继续与a[j]比较，直到a[j]与栈顶元素不同 当a[j]与i相同时将i压入栈中。
结束条件：1、最后栈空，返回1（可以按所给的顺序出站）
2、栈不空，返回0（不可以按所给的顺序出站）
*/
题目四、Sliding Window
Description
An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 3.
第24页
软件114班李大宝 201100834416
Minimum value Maximum value
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7
1 3 [-1 -3 5] 3 6 7
1 3 -1 [-3 5 3] 6 7
1 3 -1 -3 [5 3 6] 7
1 3 -1 -3 5 [3 6 7] -3 -3 -3 3 3 3 5 5 6 7 Window position
Your task is to determine the maximum and minimum values in the sliding window at each position.
Input
The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.
Output
There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.
Sample Input
8 3
1 3 -1 -3 5 3 6 7
Sample Output
-1 -3 -3 -3 3 3
3 3 5 5 6 7
程序清单：
#include<cstdio>
#include<iostream>
#include<algorithm> //*min_element()，*max_element()所包含头文件 using namespace std;
int main()
{
intn,k,i,a[1001],min[1000],max[1000];
//a[1001]存放输入数据，min[1000]存放最小值，max[1000]存放最大值
while(scanf("%d%d",&n,&k)!=EOF) //输入到文件结尾结束。
{
for(i=0;i<n;i++)
scanf("%d",&a[i]); //也可以写出scanf("%d",a+i);
for(i=0;i<=n-k;i++)
{
min[i]=*min_element(a+i,a+i+k);
//求一个范围段的最小值，保存在数组min[1000]中
max[i]=*max_element(a+i,a+i+k);
//求一个范围段的最大值，保存在数组max[1000]中
}
第25页
软件114班李大宝 201100834416
for(i=0;i<=n-k;i++) //输出最小值。 printf("%d ",min[i]);
printf("\n");
for(i=0;i<=n-k;i++) //输出最大值。 printf("%d ",max[i]);
printf("\n");
}
return 0;
}
运行结果：
第26页