数据结构栈和队列.doc

实验二 栈与队列
一、实验目得
1、掌握栈得特点(先进后出FILO)及基本操作,如入栈、出栈等,栈得顺序存储
结构与链式存储结构,以便在实际问题背景下灵活应用。
2、掌握队列得特点(先进先出FIFO)及基本操作,如入队、出队等,队列顺序存储
结构、链式存储结构与循环队列得实现,以便在实际问题背景下灵活应用。
二、实验内容
1、顺序栈得实现与运算;
2、循环队列得实现与运算;
3、栈得运用—十进制转八进制运算。
三、实验要求
1、学生用C++/C完成算法设计与程序设计并上机调试通过;
2、撰写实验报告,提供实验测试数据与实验结果;
3、分析算法,要求给出具体得算法分析结果,包括时间复杂度与空间复杂度,
并简要给出算法设计小结与心得。
四、实验准备
1、掌握栈与队列这两种抽象数据类型得特点,并能在相应得应用任务中正确选用它们;
2、熟练掌握顺序栈与循环队列得基本操作实现算法,特别应注意栈满与栈空得条件以及它们得描述方法,循环队列中队满与队空得描述方法。
3、在学习顺序栈得基本操作实现算法时,应注意:在书上给出得结构定义就是采用了一种动态管理方式(不够时,可以再分配),但在C 语言中,用数组来存储顺序栈,就是静态分配,即不能随机分配空间,这点易引起大家得误解。
五、实验步骤
1、编程实现顺序栈得各种基本运算,并在此基础上设计一个主程序,完成如下功能:
(1)初始化顺序栈;
(2)给定一个元素,将此元素压入此栈中;
(3)将栈顶一个元素弹出此栈。
2、编写一个程序实现循环队列得各种基本运算,并在此基础上设计一个主程序,
完成如下功能:
(1)初始化循环队列;
(2)给定一个元素,将此元素插入此队列中;
(3)将队头一个元素出队。
3、栈得运用实例 十进制转八进制。
六、实验参考代码
1、顺序栈得实现与运算;
#include <stdio、h>
#include <stdlib、h>
#define OK 1
#define ERROR 0
#define OVERFLOW 2
typedef int ElemType;
typedef int Status;
// 栈得顺序存储表示
#define STACK_INIT_SIZE 100 // 存储空间得初始分配量
#define STACKINCREMENT 10 // 存储空间得分配增量
typedef struct {
ElemType *base;
ElemType *top;
int stacksize;
} SqStack;
// 构造一个空栈S
Status InitStack(SqStack &S){
S、base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!S、base) exit (OVERFLOW);
S、top = S、base;
S、stacksize = STACK_INIT_SIZE;
return OK;
}
// 判栈S就是否为空栈
Status StackEmpty(SqStack S){
if (S、top==S、base) return OK;
else return ERROR;
}
//入栈函数
Status Push (SqStack &S, ElemType e) {
if(S、top S、base >= S、stacksize){
S、base=(ElemType*)realloc(S、base,(S、stacksize+STACKINCREMENT)* sizeof(ElemType));
if(!S、base) exit (OVERFLOW);
S、top = S、base + S、stacksize;
S、stacksize += STACKINCREMENT;
}
* S、top++ = e;
return OK;
}
//出栈函数
Status Pop (SqStack &S, ElemType &e) {
if(S、top == S、base) return ERROR;
e = * S、top;
return OK;
}
//输出顺序栈函数
void OutStack(SqStack S)
{ int *p;
if(S、top == S、base){
printf("这就是一个空栈！");
}
else
for(p= S、top1; p>= S、base;p)
printf("%6d", *p);
printf("\n");
}
//主函数
void main
{ SqStack s;
int cord; ElemType a;
printf("第一次使用必须初始化！\n");
do{
printf("\n 主菜单 \n");
printf(" 1 初始化顺序栈 ");
printf(" 2 插入一个元素 ");
printf(" 3 删除栈顶元素 ");
printf(" 4 结束程序运行 ");
printf("\n\n");
printf("请输入您得选择( 1, 2, 3, 4)");
scanf("%d",&cord);
printf("\n");
switch(cord)
{ case 1:
InitStack(s);
OutStack(s);
break;
case 2:
printf("请输入要插入得数据元素:a=");
scanf("%d",&a);
Push(s,a);
printf("%d 进栈之后得栈:",a);
OutStack(s);
break;
case 3:
Pop(s,a);
printf("栈顶元素 %d 出栈之后得栈:",a);
OutStack(s);
break;
case 4:
exit(0);
}
}while (cord<=4);
}
2、循环队列得实现与运算;
#include <stdio、h>
#include <stdlib、h>
#define OK 1
#define ERROR 0
#define OVERFLOW 2
typedef int QElemType;
typedef int Status;
// 队列得顺序存储表示
#define MAXQSIZE 100 // 存储空间得初始分配量
typedef struct {
QElemType *base;
int front;
int rear;
} SqQueue;
// 构造一个空队列Q
Status InitQueue(SqQueue &Q){
Q、base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
if(!Q、base)exit(OVERFLOW);
Q、front=Q、rear=0;
return OK;
}
//判队列就是否为空
Status QueueEmpty (SqQueue Q) {
if(Q、rear==Q、front) return OK;
else return ERROR ;
}
//入队函数
Status EnQueue (SqQueue &Q, QElemType e) {
if((Q、rear+1)%MAXQSIZE==Q、front) return ERROR;
Q、base[Q、rear]=e;
Q、rear=(Q、rear+1)%MAXQSIZE;
return OK;
}
//出队函数
Status DeQueue (SqQueue &Q, QElemType &e) {
if(Q、rear==Q、front) return ERROR;
e=Q、base[Q、front];
Q、front=(Q、front+1)%MAXQSIZE;
return OK;
}
//输出循环队列函数
void OutQueue(SqQueue Q)
{ int n, i;
if(Q、front == Q、rear){
printf("这就是一个空队列！");
}
else{
n= (Q、rear Q、front+ MAXQSIZE) % MAXQSIZE;
i= 1;
while ( i<= n){
printf("%6d", Q、base[(Q、front+i1)% MAXQSIZE] );
i++;}
printf("\n");
}
}
//主函数
void main
{ SqQueue q;
int cord; QElemType a;
printf("第一次使用必须初始化！\n");
do{
printf("\n 主菜单 \n");
printf(" 1 初始化循环队列 ");
printf(" 2 进队一个元素 ");
printf(" 3 出队一个元素 ");
printf(" 4 结束程序运行 ");
printf("\n\n");
printf("请输入您得选择( 1, 2, 3, 4)");
scanf("%d",&cord);
printf("\n");
switch(cord)
{ case 1:InitQueue(q); //调用初始化算法;
OutQueue(q);
break;
case 2:
printf("请输入要插入得数据元素:a=");
scanf("%d",&a);
EnQueue (q, a); //调用进队算法;
printf("%d 进队之后得队列:",a);
OutQueue(q);
break;
case 3:
DeQueue (q, a); //调用出队算法;
printf("队头元素 %d 出队之后得队列:",a);
OutQueue(q);
break;
case 4:
exit(0);
}
}while (cord<=4);
}
3、栈得应用—十进制转八进制
#include <stdio、h>
#include <stdlib、h>
#define OK 1
#define ERROR 0
#define OVERFLOW 2
typedef int ElemType;
typedef int Status;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct {
ElemType *base;
ElemType *top;
int stacksize;
} SqStack;
// 构造一个空栈S
Status InitStack(SqStack &S){
S、base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!S、base) exit (OVERFLOW);
S、top = S、base;
S、stacksize = STACK_INIT_SIZE;
return OK;
}
// 判栈S就是否为空栈
Status StackEmpty(SqStack S){
if (S、top==S、base) return OK;
else return ERROR;
}
//入栈函数
Status Push (SqStack &S, ElemType e) {
if(S、top S、base >= S、stacksize){
S、base=(ElemType*)realloc(S、base,(S、stacksize+STACKINCREMENT)* sizeof(ElemType));
if(!S、base) exit (OVERFLOW);
S、top = S、base + S、stacksize;
S、stacksize += STACKINCREMENT;
}
* S、top++ = e;
return OK;
}
//出栈函数
Status Pop (SqStack &S, ElemType &e) {
if(S、top == S、base) return ERROR;
e = * S、top;
return OK;
}
//十进制转八进制函数
void conversion
{ SqStack S;
int n,e;
InitStack(S);
printf("请输入一个十进制数:");
scanf("%d",&n);
while(n)
{
Push(S,n%8);
n=n/8;
}
printf("转换之后得八进制数为:");
while(!StackEmpty(S))
{
Pop(S, e);
printf("%d",e);
}
printf("\n");
}
void main
{
conversion;
}