C++与数据结构第二次上机实验堆栈和队列.docx
- 文档编号:6087020
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:15
- 大小:76.51KB
C++与数据结构第二次上机实验堆栈和队列.docx
《C++与数据结构第二次上机实验堆栈和队列.docx》由会员分享,可在线阅读,更多相关《C++与数据结构第二次上机实验堆栈和队列.docx(15页珍藏版)》请在冰点文库上搜索。
C++与数据结构第二次上机实验堆栈和队列
[键入公司名称]
实验二堆栈和队列
——数据结构实验报告
实验二堆栈和队列
一、实验目的和要求:
1、掌握堆栈和队列的基本概念;
2、掌握堆栈和队列的基本操作。
二、实验原理:
1、堆栈的定义:
堆栈是一种只允许在表的一端进行插入和删除运算的特殊的线性表。
允许进行插入和删除运算的一端称为栈顶,另一端称为栈底,当链表中没有元素时,称为空栈。
2、堆栈的插入运算称为入栈或者进栈,删除运算称为出栈或者退栈,栈顶的当前位置是动态的,标识栈顶当前位置的指针称为栈顶指针。
每次进栈的数据元素都放在原当前栈顶元素之前成为新的栈顶元素,每次退栈的数据元素都是原当前栈顶元素,最后进入堆栈的数据元素总是最先退出堆栈。
3、堆栈的存储结构:
(1)顺序存储结构:
栈的顺序存储结构称为顺序栈。
顺序栈的本质是顺序表的简化。
(2)链式存储结构:
栈的链式存储结构称为链栈,通常用单链表示。
链栈的插入和删除操作只需处理栈顶的情况。
4、队列的定义:
队列是允许在表的一端进行插入,而在表的另一端进行删除的特殊线性表。
允许进行插入的一端称为队尾,允许进行删除的一端称为队头。
队列的插入运算称为进队或者入队,删除运算称为出队或者离队,因此队列又称为先进先出表。
5、队列的存储结构
队列的存储结构同线性表一样,可以分为顺序结构和链式结构。
(1)顺序存储结构:
用顺序存储结构存储队列称为顺序队列。
顺序队列会出现假溢出问题,解决办法是用首尾相接的书顺序存储结构,称为循环队列。
在队列中,只要涉及队头或者队尾指针的修改都要对其求模。
(2)链式存储结构:
用链式存储结构存储的队列称为链队列。
链队列的基本操作的实现基本上也是单链表操作的简化。
通常附设头结点,并设置队头指针指向头结点,队尾指针指向终端结点。
插入数据时只考虑在链队列的尾部进行,删除数据时只考虑在链队列的头部进行。
三、实验内容:
1、试编写一个算法,建立一个学生成绩栈,要求从键盘上输入N个整数,按照下列要求分别进入不同的栈。
(1)若输入的整数X小于60,则进入第一个栈;
(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
#include
#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;
}
voidSeqStack:
:
PrintStack()
{
while(IsEmptyStack()==false)
{cout< top--; height--; } cout< } intmain() { intn; ElemTypep; cout<<"请输入学生人数: "; cin>>n; SeqStackh(n),m(n),l(n); cout<<"学生的成绩为: "; for(inti=0;i { cin>>p; cout< if(p>100) h.PushStack(p); elseif(p>=60&&p<=100) m.PushStack(p); elsel.PushStack(p); } cout< cout<<"小于60的成绩: "; l.PrintStack(); cout<<"小于等于100且大于等于60的成绩: "; m.PrintStack(); cout<<"大于100的成绩: "; h.PrintStack(); system("PAUSE"); } (3)运行结果: 2、 (1)伪代码: 该程序的核心问题是将100以内的随机数分为奇数和偶数两组: 用条件m%2是否为零将其分别插入到两个新栈中。 将新栈中的数据元素间隔输出输出采用delete函数,其每次都返回删除的数据元素,知道某一新栈被全部删除。 退出输出。 (2)程序代码: #include #include usingnamespacestd; 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&x);//从队头取一个元素 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; } else {p->link=NULL; tail=p; head=p;}} boolLinkQueue: : PopFront(int&x) {ListNode*p; if(head)//若队列为非空 { x=head->data; p=head; head=head->link; if(head==NULL) tail=NULL; deletep; qsize--; returntrue; }returnfalse; } voidLinkQueue: : Clear() {intp; while(PopFront(p)) head=tail=NULL; } intLinkQueue: : DeleteQueue() { ListNode*q=head; head=q->link; inty=q->data; deleteq; returny; } intmain() { LinkQueueq1,q2; for(inti=0;i<20;i++) { intx=rand()%100; cout< if(x%2==1) q1.PushTail(x);//用q1链队存放奇数 else q2.PushTail(x);//用q2链队存放偶数 } cout< while(! q1.IsEmpty()&&! q2.IsEmpty())//每一行输出一个奇数和一个偶数,直到任一队列空为止 { cout< } cout< system("PAUSE"); } (3)运行结果: 3、 (1)伪代码: 该程序的核心问题是实现对于三种括号是否匹配的判断。 因为括号匹配是对于先存入的数据先操作,所以采用队列形式的链表。 利用删除队头元素实现总是对队头元素进行操作。 将要判断的字符存入队列中,分三种情况讨论括号匹配的问题: a.对做左单括号计数,其如果遇到右括号与其匹配,则左单括号数-1,如果没有遇到右单括号,则没有实现匹配; b.如果前面没有左单括号,则右单括号没有实现匹配,右单括号数+1; c.如果右单括号之前还有左单括号,则括号实现匹配,匹配数+1,左单括号数-1。 (2)程序代码: #include"iostream" usingnamespacestd; #include"stdlib.h" classLinkQueue; classQueueNode { friendclassLinkQueue; chardata; QueueNode*link; public: QueueNode(){data=0;link=NULL;} }; classLinkQueue { QueueNode*head;//队头指针 QueueNode*tail;//队尾指针 public: LinkQueue(){head=tail=NULL;}//构造函数,建立空队列 boolIsEmpty();//判断队列是否为空 voidLpushTail(char&x);//将新元素插入到队尾 charLpopFront(char&x);//将队头第一个元素删除 }; boolLinkQueue: : IsEmpty() { return(head==NULL)? true: false; } voidLinkQueue: : LpushTail(char&x)//插入,将元素插入到队尾 { QueueNode*p=newQueueNode; p->data=x; if(tail! =NULL) { p->link=NULL; tail->link=p; tail=p; } else { p->link=NULL; tail=p; head=p; } } charLinkQueue: : LpopFront(char&x)//删除,从队头取出一个元素 { QueueNode*p; if(head) { x=head->data; p=head; head=head->link; if(head==NULL) tail=NULL; deletep; returnx; } return-1; } intmain() { LinkQueueQ1,Q2,Q3;//建立队列对象 charm,k; intn;//设置队列的长度 cout<<"需要判断的表达式长度: "; cin>>n; cout<<"输入要判断的表达式: "; for(inti=0;i { cin>>m; Q1.LpushTail(m); Q2.LpushTail(m); Q3.LpushTail(m); } intx1=0,x2=0,x3=0; for(inti=0;i { Q1.LpopFront(k);//删除队头元素; if(k=='{'){x1++;}//遇到{先计数,这个数可能是左括号与右括号匹配,也可能是只有左括号 if(k=='}'&&x1==0){x2++;}//如果左括号前面已经没有右括号与其匹配,则右括号未匹配数+1 if(k=='}'&&x1>0){x1--,x3++;}//遇到左右括号匹配,则左单括号数-1,成对括号数+1 } cout<<"有"< cout<<"有"< cout<<"有"< inty1=0,y2=0,y3=0;//依次检索[]的配对情况 for(intj=0;j { Q2.LpopFront(k); if(k=='['){y1++;} if(k==']'&&y1==0){y2++;} if(k==']'&&y1>0){y1--,y3++;} } cout<<"有"< cout<<"有"< cout<<"有"< intz1=0,z2=0,z3=0;//依次检索()的配对情况 for(intl=0;l { Q3.LpopFront(k); if(k=='('){z1++;} if(k==')'&&z1==0){z2++;} if(k==')'&&z1>0){z1--,z3++;} } cout<<"有"< cout<<"有"< cout<<"有"< system("PAUSE"); (3)运行结果 五、编程心得: (1)、深刻体会到了堆栈“后进先出”的含义和队列“先进先出”的含义; (2)、体会到数据结构的重要性,自从进入数据结构的学习后,解决的问题都不再是几行代码就能解决的问题,都需要编写100多行的代码,而数据结构将这些问题进行理论化的同时建立了一类型数据常用的操作,使得很多问题容易得到解决。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- C+ 数据结构 第二次 上机 实验 堆栈 队列