数据结构实验报告 堆栈和队列

实验报告

报告人：高晓铮（1120101390）

实验目的：

1. 掌握堆栈和队列的基本概念；

2. 掌握堆栈和队列的基本操作。

3. 了解产生随机数的相关操作。

实验内容：

1.试编写一个算法，建立一个学生成绩栈，要求从键盘上输入N个数，按照下列要求分别进入不同栈。

（1） 若输入的整数x小于60，则进入第一个栈；

（2） 若输入的整数x大于等于60并小于100，则进入第二个栈；

（3） 若输入的整数x大于100，则进入第三个栈；

（4） 分别输出每个栈的内容。

2. 编写一个程序，使用两个链队q1和q2，用来分别存储有计算机随机产生的20个100以内的奇数和偶数，然后每行输出q1和q2中的一个值，即奇数和偶数配对输出，直到任一队列为空为止。

3. 假设一个算术表达式中可以包含三种括号：“（”和“）”，方括号“[”和“]”及花括号“{”和“}”，且这三种括号可按照任意的次序嵌套使用。编写算法判断给定表达式中所含括号是否成对出现。

实验原理：

堆栈是一种只允许在表的一端进行插入和删除运算的线性表。允许插入和删除运算的一端叫栈顶，另一端叫栈底。堆栈进栈的元素都是放在原当前栈顶元素之前而成为新的栈顶元素，每次退栈元素都是原当前栈顶的元素，最后进入堆栈的数据元素总是最先退出堆栈。 队列是一种只允许在表的一端进行插入，而在表的另一端进行删除的特殊线性表。允许进行插入的一端叫队尾，另一端叫队头。队的插入和删除运算分别是在各自的一端进行的，每个元素必须按照进入的次序离队。

链栈和链队的存储结构中，逻辑上相邻的两个元素对应的存储位置是通过指针反应的，不要求物理上的相邻。

1题定义一个结点结构和栈类。栈类中定义构造函数、析构函数、进栈函数、出栈函数、清栈函数，利用各个函数实现对堆栈的操作。

2题定义一个结点结构和队类。队类中定义构造函数、析构函数、进队函数、出队函数、清队函数，利用各个函数实现对链队的操作。

3题定义一个结点结构和栈类。栈类中定义构造函数、析构函数、进栈函数、出栈函数、清栈函数、测试栈空函数，利用各个函数实现对堆栈的操作。

设计思想:

为了实现代码的重复利用，3个程序源代码使用了模板。

1题中定义三个链栈。根据输入的数值按照相关要求调用进栈函数进栈。然后对三个栈进行出栈操作，若栈为空则输出空，非空则输出相应元素。

2题中定义两个队列。随机产生20个100以内的数。根据产生的数值按照相关要求调

用进队函数进队。然后分别对两个队列交替调用出队函数出队，直到有一个队列为空为止。

3题中定义一个链栈。根据输入的值进行相应的操作。如果输入的是左括号则放入栈中。如果输入的是右括号，则先进行出栈处理，如果括号配对，则不再处理；如果括号不配对，则分别对相应的左括号和右括号进行进栈处理。如果输入其他数值和符号不进行任何操作。输入#终止输入。最后调用测试栈空函数，如果栈空则括号配对，否则不配对。

实现部分:

源代码：

1题：

#include<iostream.h>

#include<assert.h>

template<class t1>

struct stacknode{

t1 data;

stacknode *next;};

template<class t1>

class linkstack

{

stacknode<t1> *top;

unsigned height;

public:

linkstack();

~linkstack()

{clear();}

void clear();

void push(t1 &x);

bool pop(t1 &x);

bool isempty()

{return(heighe==0)?true:false;}

};

template<class t1>

linkstack<t1>::linkstack()

{height=0;

top=NULL;}

//清栈函数

template<class t1>

void linkstack<t1>::clear()

{t1 x;

while(pop(x));

}

//进栈函数

template<class t1>

void linkstack<t1>::push(t1 &x)

{stacknode<t1> *p;

if(top)

{p=new stacknode<t1>;

assert(p);

p->data=x;

p->next=top;

top=p;

}

else

{top=new stacknode<t1>;

assert(top);

top->data=x;

top->next=NULL;

}

height++;}

//出栈函数

template<class t1>

bool linkstack<t1>::pop(t1&x)

{stacknode<t1> *p;

if(height)

{x=top->data;

p=top;

top=top->next;

delete p;

height--;

return true;}

else

return false;}

int main()

{int i,j=0,x;

linkstack<int> a,b,c;

cout<<"请输入要输入整数的个数"<<endl;

cin>>i;

cout<<"请输入整数"<<endl;

while(j<i)

{cin>>x;

if(x<60)a.push(x);

if(60<=x&&x<100)b.push(x);

if(x>100)c.push(x);

j++;}

cout<<"小于60的整数"<<endl;

if(!a.pop(x))

cout<<"空";

else a.push(x);

while(a.pop(x))

{cout<<x<<" ";}

cout<<endl;

cout<<"大于等于60小于100的整数"<<endl;

if(!b.pop(x))cout<<"空";

else b.push(x);

while(b.pop(x))

{cout<<x<<" ";}

cout<<endl;

cout<<"大于100的整数"<<endl;

if(!c.pop(x))cout<<"空";

else c.push(x);

while(c.pop(x))

{cout<<x<<" ";}

cout<<endl;

return 0;

}

2题：

#include<iostream.h>

#include<assert.h>

#include<stdlib.h>

#include<time.h>

template<class t1>

struct quenenode{

t1 data;

quenenode *next;};

template<class t1>

class linkquene{

quenenode<t1> *head,*tail;

unsigned qsize;

public:

linkquene();

~linkquene()

{clear();}

void clear();

void pushtail(t1 &x);

bool popfront(t1 &x);

bool isempty()

{return(qsize==0)?true:false;}

};

template<class t1>

linkquene<t1>::linkquene()

{qsize=0;head=tail=NULL;}

//清队函数

template<class t1>

void linkquene<t1>::clear()

{ t1 x;

while(popfront(x));

head=tail=NULL;

}

//进队函数

template<class t1>

void linkquene<t1>::pushtail(t1 &x)

{quenenode<t1> *p;

p=new quenenode<t1>;

assert( …… 此处隐藏：2603字，全部文档内容请下载后查看。喜欢就下载吧 ……