C++与数据结构第二次上机实验堆栈和队列Word文件下载.docx
《C++与数据结构第二次上机实验堆栈和队列Word文件下载.docx》由会员分享，可在线阅读，更多相关《C++与数据结构第二次上机实验堆栈和队列Word文件下载.docx（15页珍藏版）》请在冰点文库上搜索。
（2）若输入的整数x大于等于60并小于100，则进入第二个栈；
（3）若输入的整数x大于100，则进入第三个栈；
（4）分别输出每个栈的内容。
2、编写一个程序，使用两个链队q1和q2，用来分别存储由计算机产生的20个100以内的奇数和偶数，然后每行输出q1和q2的一个值，即奇数和偶数配对输出，直到任一队列为空为止。
3、假设一个算术表达式中可以包括三种括号：
“（”和“）”，方括号“[”和“]”及花括号“{”和“}”，且这三种括号可以任意顺序的嵌套使用。
编写算法判断给定表达式中所包含的括号是否配对出现。
四、实验设计：
（1）伪代码
该算法的核心是将成绩分类，并将其分别插入到不同的栈中，栈顶指针加1；
入栈函数用模板voidPushStack（ElemTypex）函数。
将输入的数据进行条件选择，分别插入到新栈l,m,h中。
（2）程序代码：
#include<
stdlib.h>
time.h>
#include"
iostream"
usingnamespacestd;
classList;
typedefintElemType;
classSeqStack
{
unsignedheight;
inttop;
intmaxsize;
ElemType*elements;
public:
SeqStack（intsize）;
//构造函数，size用来设置栈的大小
~SeqStack（）{delete[]elements;
}//析构函数
voidPushStack（ElemTypex）;
//进栈函数，将元素x压入栈中
ElemTypePopStack（ElemTypex）;
//出栈函数，将栈顶元素值放入x中
voidClearStack（）{top=-1;
}//清栈函数，用于释放所占的内存空间
boolIsFullStack（）{returntop==maxsize-1;
}//判断栈是否为满
boolIsEmptyStack（）;
//判断栈是否为空
voidPrintStack（）;
//将栈中元素输入到屏幕上
};
SeqStack:
:
SeqStack（intsize）
height=0;
top=-1;
maxsize=size;
//设置最大栈高
elements=newElemType[size];
}
voidSeqStack:
PushStack（ElemTypex）
{if（IsFullStack（））
cout<
<
"
栈已满~"
;
else
{
elements[++top]=x;
height++;
}
ElemTypeSeqStack:
PopStack（ElemTypex）
x=elements[top];
top--;
height--;
returnx;
boolSeqStack:
IsEmptyStack（）//判断栈是否为空
return（height==0）?
true:
false;
PrintStack（）
while（IsEmptyStack（）==false）
{cout<
elements[top]<
"
endl;
intmain（）
intn;
ElemTypep;
请输入学生人数：
cin>
>
n;
SeqStackh（n）,m（n）,l（n）;
学生的成绩为：
for（inti=0;
i<
i++）
{
p;
p<
if（p>
100）
h.PushStack（p）;
elseif（p>
=60&
&
p<
=100）
m.PushStack（p）;
elsel.PushStack（p）;
小于60的成绩：
l.PrintStack（）;
小于等于100且大于等于60的成绩：
m.PrintStack（）;
大于100的成绩：
h.PrintStack（）;
system（"
PAUSE"
）;
（3）运行结果：
2、
（1）伪代码：
该程序的核心问题是将100以内的随机数分为奇数和偶数两组：
用条件m%2是否为零将其分别插入到两个新栈中。
将新栈中的数据元素间隔输出输出采用delete函数，其每次都返回删除的数据元素，知道某一新栈被全部删除。
退出输出。
（2）程序代码：
iostream>
classLinkQueue;
classListNode//定义链式队列的结点类
friendclassLinkQueue;
intdata;
ListNode*link;
classLinkQueue
{public:
ListNode*head;
ListNode*tail;
intqsize;
//定义队长
int*elements;
LinkQueue（）{head=tail=NULL;
}//构造函数,建立空队列
~LinkQueue（）{Clear（）;
voidPushTail（int&
x）;
//将新元素插入在队尾
boolPopFront（int&
//从队头取一个元素
voidClear（）;
//清空队列
intIsEmpty（）{returnhead==NULL;
}//判断队列是否为空
intDeleteQueue（）;
voidLinkQueue:
PushTail（int&
x）
ListNode*p=newListNode;
p->
data=x;
if（tail!
=NULL）
{p->
link=NULL;
tail->
link=p;
tail=p;
head=p;
}}
boolLinkQueue:
PopFront（int&
{ListNode*p;
if（head）//若队列为非空
x=head->
data;
p=head;
head=head->
link;
if（head==NULL）
tail=NULL;
deletep;
qsize--;
returntrue;
}returnfalse;
Clear（）
{intp;
while（PopFront（p））
head=tail=NULL;
intLinkQueue:
DeleteQueue（）
ListNode*q=head;
head=q->
inty=q->
deleteq;
returny;
LinkQueueq1,q2;
i<
20;
i++）
intx=rand（）%100;
x<
if（x%2==1）
q1.PushTail（x）;
//用q1链队存放奇数
q2.PushTail（x）;
//用q2链队存放偶数
while（!
q1.IsEmpty（）&
!
q2.IsEmpty（））//每一行输出一个奇数和一个偶数，直到任一队列空为止
q1.DeleteQueue（）<
q2.DeleteQueue（）<
（3）运行结果：
3、
（1）伪代码:
该程序的核心问题是实现对于三种括号是否匹配的判断。
因为括号匹配是对于先存入的数据先操作，所以采用队列形式的链表。
利用删除队头元素实现总是对队头元素进行操作。
将要判断的字符存入队列中，分三种情况讨论括号匹配的问题：
a.对做左单括号计数，其如果遇到右括号与其匹配，则左单括号数-1，如果没有遇到右单括号，则没有实现匹配；
b.如果前面没有左单括号，则右单括号没有实现匹配，右单括号数+1；
c.如果右单括号之前还有左单括号，则括号实现匹配，匹配数+1，左单括号数-1。
#include"
stdlib.h"
classQueueNode
friendclassLinkQueue;
chardata;
QueueNode*link;
QueueNode（）{data=0;
};
QueueNode*head;
//队头指针
QueueNode*tail;
//队尾指针
LinkQueue（）{head=tail=NULL;
}//构造函数，建立空队列
boolIsEmpty（）;
//判断队列是否为空
voidLpushTail（char&
//将新元素插入到队尾
charLpopFront（char&
//将队头第一个元素删除
IsEmpty（）
return（head==NULL）?
true:
voidLinkQueue:
LpushTail（char&
x）//插入，将元素插入到队尾
QueueNode*p=newQueueNode;
p->
if（tail!
p->
tail->
tail=p;
else
head=p;
charLinkQueue:
LpopFront（char&
x）//删除，从队头取出一个元素
QueueNode*p;
if（head）
x=head->
p=head;
head=head->
if（head==NULL）
tail=NULL;
deletep;
returnx;
return-1;
LinkQueueQ1,Q2,Q3;
//建立队列对象
charm,k;
intn;
//设置队列的长度
cout<
需要判断的表达式长度:
cin>
输入要判断的表达式:
for（inti=0;
i++）
cin>
m;
Q1.LpushTail（m）;
Q2.LpushTail（m）;
Q3.LpushTail（m）;
intx1=0,x2=0,x3=0;
i++）//依次检索{}的配对情况
Q1.LpopFront（k）;
//删除队头元素；
if（k=='
{'
）{x1++;
}//遇到{先计数，这个数可能是左括号与右括号匹配，也可能是只有左括号
}'
x1==0）{x2++;
}//如果左括号前面已经没有右括号与其匹配，则右括号未匹配数+1
x1>
0）{x1--,x3++;
}//遇到左右括号匹配，则左单括号数-1，成对括号数+1
有"
x3<
个{}完成配对"
x1<
个{没有完成配对"
x2<
个}没有完成配对"
inty1=0,y2=0,y3=0;
//依次检索[]的配对情况
for（intj=0;
j<
j++）
Q2.LpopFront（k）;
['
）{y1++;
]'
y1==0）{y2++;
y1>
0）{y1--,y3++;
y3<
个[]完成配对"
y1<
个[没有完成配对"
y2<
个]没有完成配对"
intz1=0,z2=0,z3=0;
//依次检索（）的配对情况
for（intl=0;
l<
l++）
Q3.LpopFront（k）;
（'
）{z1++;
）'
z1==0）{z2++;
z1>
0）{z1--,z3++;
z3<
个（）完成配对"
z1<
个（没有完成配对"
z2<
个）没有完成配对"
（3）运行结果
五、编程心得：
（1）、深刻体会到了堆栈“后进先出”的含义和队列“先进先出”的含义；
（2）、体会到数据结构的重要性，自从进入数据结构的学习后，解决的问题都不再是几行代码就能解决的问题，都需要编写100多行的代码，而数据结构将这些问题进行理论化的同时建立了一类型数据常用的操作，使得很多问题容易得到解决。
升级会员 