数据结构实验报告
实验名称： 实验2——栈和队列
学生姓名：
班 级：
班内序号：
学 号：
日 期：
一、 实验要求
1、实验目的： 进一步掌握指针、模板类、异常处理的使用
掌握栈的操作的实现方法
掌握队列的操作的实现方法
学习使用栈解决实际问题的能力
学习使用队列解决实际问题的能力
2、实验内容：
根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。
要求：
实现一个共享栈
实现一个链栈
实现一个循环队列
实现一个链队列
编写测试main()函数测试线性表的正确性
二、程序分析
2.1 存储结构
顺序栈、链栈和顺序队列
顺序栈 链栈 顺序队列
2.2 关键算法分析
A、实现一个共享栈：
a、伪代码实现
入栈操作：如果栈满，则抛出上溢异常；
判断是插在栈1还是栈2，如果在栈1插入，则栈顶指针top1加1，在top1处填入x，如果在栈2插入，则栈顶指针top2加1，在top2处填入x。
出栈操作：如果栈空，则抛出下溢异常；
判断是栈1出栈还是栈2，如果是栈1，则输出栈1栈顶元素，并且top1减1，如果是栈2，则输出栈2栈顶元素，并且top2加1。
得到栈顶元素操作：如果栈空，则抛出下溢异常；
判断是栈1出栈还是栈2，如果是栈1，则输出栈1栈顶元素，如果是栈2，则输出栈2栈顶元素。
b、算法实现：
void shareseqstack::push(int x,int pushnumber)//进栈操作
{if(top1+1==top2)//异常处理
throw "上溢";
if(pushnumber==1)//判断栈1还是栈2
data[++top1]=x;
if(pushnumber==2)
data[--top2]=x;
}
void shareseqstack::pop(int popnumber)//出栈操作
{if(popnumber==1) //异常处理
{ if(top1==-1) throw "下溢";
else cout<<data[top1--]<<endl;
}
if(popnumber==2) //异常处理
{if(top2==seqstack) throw "下溢";
else cout<<data[top2++]<<endl;
}
}
void shareseqstack::gettop(int getnumber)//得到栈顶元素
{if(getnumber==1) //判断栈1还是栈2
{if(top1==-1) throw "下溢"; //异常处理
cout<<data[top1]<<endl;}
if(getnumber==2)
{if(top2==seqstack) throw "下溢";
cout<<data[top2]<<endl;
}
}
B、实现一个链栈
插入 删除
a伪代码实现
入栈：生成新结点，对新结点赋值，新结点的指向原栈顶指针，修改栈顶指针为新结点。
出栈：判断若为空栈抛出下溢异常，保存栈顶元素，建立新结点，保存栈顶指针，修改栈顶指针为原栈顶指针的下一个结点，删除栈顶指针并输出栈顶元素。
b、算法实现：
void linkstack::push(int x)//进栈操作
{Node*p=new Node;//定义新结点
p->data=x;
p->next=top;
top=p;
}
void linkstack::pop()//出栈操作
{if(empty()) throw "下溢";//异常处理
int x=top->data;
Node*p=new Node; //定义新结点
p=top;
top=top->next;
delete p;
cout<<x<<" ";
}
void linkstack::gettop()//得到栈顶元素
{if(empty()) throw "下溢";//异常处理
cout<<top->data<<endl;
}
linkstack::~linkstack()//析构
{while(top)
{Node*p=top;
top=top->next;
delete p;
}
}
C、实现一个循环队列
a、 伪代码实现:
入队：判断若为队满，抛出异常，尾指针后移，指向入队元素。
出队：判断若为队空，抛出异常，头指针后移，输出队头元素。
b、 算法实现
void circlequeue::enqueue(int x)//进队操作
{if((rear+1)%queuesize==front) throw "上溢";//异常处理
rear=(rear+1)%queuesize;
data[rear]=x;
}
void circlequeue::dequeue()//出队操作
{if(rear==front) throw "下溢";//异常处理
front=(front+1)%queuesize;
cout<<data[front]<<endl;
}
void circlequeue::getfront()得到队头元素
{if(rear==front) throw "下溢";//异常处理
cout<<data[(front+1)%queuesize]<<endl;
}
void circlequeue::getlength()//得到队列长度
{cout<<((rear-front+queuesize)%queuesize)<<endl;
}
D、实现一个链队列
void linkqueue::enqueue(int x)//进队操作
{rear->next=new Node;
rear=rear->next;
rear->data=x;
rear->next=NULL;
}
void linkqueue::dequeue()//出队操作
{Node*p=front->next;
front->next=p->next;
int x=p->data;
delete p;
if(!(front->next))rear=front;
cout<<x<<endl;
}
void linkqueue::getfront()//得到头结点元素
{if(!(front->next)) throw "上溢";//异常处理
cout<<(front->next->data)<<endl;
}
linkqueue::~linkqueue()//析构
{while(front)
{rear=front->next;
delete front;
front=rear;
}
}
2.3 其他
源代码
#include<iostream>
using namespace std;
struct Node //定义结点
{
int data;
struct Node*next;
};
const int seqstack=100;
class shareseqstack //定义共享栈
{public:
shareseqstack();
void push(int x,int pushnumber);
void pop(int popnumber);
void gettop(int getnumber);
private:
int data[seqstack];
int top1;
int top2;
};
shareseqstack::shareseqstack()//构造
{top1=-1;
top2=seqstack;
}
void shareseqstack::push(int x,int pushnumber)//进栈操作
{if(top1+1==top2)//异常处理
throw "上溢";
if(pushnumber==1)//判断栈1还是栈2
data[++top1]=x;
if(pushnumber==2)
data[--top2]=x;
}
void shareseqstack::pop(int popnumber)//出栈操作
{if(popnumber==1) //异常处理
{ if(top1==-1) throw "下溢";
else cout<<data[top1--]<<endl;
}
if(popnumber==2) //异常处理
{if(top2==seqstack) throw "下溢";
else cout<<data[top2++]<<endl;
}
}
void shareseqstack::gettop(int getnumber)//得到栈顶元素
{if(getnumber==1) //判断栈1还是栈2
{if(top1==-1) throw "下溢"; //异常处理
cout<<data[top1]<<endl;}
if(getnumber==2)
{if(top2==seqstack) throw "下溢";
cout<<data[top2]<<endl;
}
}
class linkqueue//定义链队列
{public:
linkqueue(){front=rear=new Node; front->next=NULL;}
~linkqueue();
void enqueue(int x);
void dequeue();
void getfront();
bool empty(){return front==rear? true:false;}
private:
Node*front;
Node*rear;
};
void linkqueue::enqueue(int x)//进队操作
{rear->next=new Node;
rear=rear->next;
rear->data=x;
rear->next=NULL;
}
void linkqueue::dequeue()//出队操作
{Node*p=front->next;
front->next=p->next;
int x=p->data;
delete p;
if(!(front->next))rear=front;
cout<<x<<endl;
}
void linkqueue::getfront()//得到头结点元素
{if(!(front->next)) throw "上溢";//异常处理
cout<<(front->next->data)<<endl;
}
linkqueue::~linkqueue()//析构
{while(front)
{rear=front->next;
delete front;
front=rear;
}
}
class linkstack//定义链栈
{public:
linkstack(){top=NULL;}
~linkstack();
void push(int x);
void pop();
void gettop();
bool empty(){return(NULL==top)? true:false;}
private:
struct Node*top;
};
void linkstack::push(int x)//进栈操作
{Node*p=new Node;//定义新结点
p->data=x;
p->next=top;
top=p;
}
void linkstack::pop()//出栈操作
{if(empty()) throw "下溢";//异常处理
int x=top->data;
Node*p=new Node; //定义新结点
p=top;
top=top->next;
delete p;
cout<<x<<" ";
}
void linkstack::gettop()//得到栈顶元素
{if(empty()) throw "下溢";//异常处理
cout<<top->data<<endl;
}
linkstack::~linkstack()//析构
{while(top)
{Node*p=top;
top=top->next;
delete p;
}
}
const int queuesize=1000;//定义循环队列
class circlequeue
{public:
circlequeue(){front=rear=0;}
void enqueue(int x);
void dequeue();
void getfront();
void getlength();
bool empty(){return front=rear? true:false;}
private:
int data[queuesize];
int front;
int rear;
};
void circlequeue::enqueue(int x)//进队操作
{if((rear+1)%queuesize==front) throw "上溢";//异常处理
rear=(rear+1)%queuesize;
data[rear]=x;
}
void circlequeue::dequeue()//出队操作
{if(rear==front) throw "下溢";//异常处理
front=(front+1)%queuesize;
cout<<data[front]<<endl;
}
void circlequeue::getfront()得到队头元素
{if(rear==front) throw "下溢";//异常处理
cout<<data[(front+1)%queuesize]<<endl;
}
void circlequeue::getlength()//得到队列长度
{cout<<((rear-front+queuesize)%queuesize)<<endl;
}
void main()//主函数
{ linkstack D;
D.push(1);//进栈
D.push(2);
D.push(3);
cout<<"链栈的实现："<<endl<<"出栈顺序为：";
D.pop();//出栈
D.pop();
D.pop();
D.push(1);
D.push(2);
D.push(3);
cout<<endl;
cout<<"栈顶元素为：";
D.gettop();
D.~linkstack();//析构
cout<<endl;
shareseqstack A;
A.push(1,1);
A.push(2,1);
A.push(3,1);
A.push(10,2);
A.push(9,2);
A.push(8,2);
cout<<"共享栈的实现："<<endl<<"标号为1的栈出栈元素为：";
A.pop(1);
cout<<"标号为2的栈出栈元素为：";
A.pop(2);
cout<<"标号为1的栈栈顶元素为：";
A.gettop(1);
cout<<"标号为2的栈栈顶元素为：";
A.gettop(2);
cout<<endl;
linkqueue C;
cout<<"链队列的实现："<<endl;
C.enqueue(2);
C.enqueue(4);
C.enqueue(6);
cout<<"出队元素为：";
C.dequeue();
cout<<"队头元素为：";
C.getfront();
C.~linkqueue();
cout<<endl;
circlequeue B;
B.enqueue(11);
B.enqueue(22);
B.enqueue(33);
B.enqueue(44);
B.enqueue(55);
cout<<"循环队列的实现："<<endl;
cout<<"出队的元素为：";
B.dequeue();
cout<<"队头元素为：";
B.getfront();
cout<<"队列长度为：";
B.getlength();
}
3. 程序运行结果
1、流程图
2、测试结果
4. 总结
心得体会
实践才能得出真知，在通过上机操作后，才发现了许多在平时上理论课没有想到的方方面面。编写程序时发现很多语法错误，很多英语单词记不熟，有的会记错，程序函数错用等等，以后需多多实践多多上机操作才能解决已有的问题
下一步的改进：入栈可以手动输入，这样修改入栈元素就可以不必修改原程序了。