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

一、实验目得与要求
（１)理解栈与队列得特征以及它们之间得差异,知道在何时使用那种数据结构。
(2）重点掌握在顺序栈上与链栈上实现栈得基本运算算法，注意栈满与栈空得条件。
（３)重点掌握在顺序队上与链队上实现队列得基本运算算法,注意循环队队列满与队空得条件。
（４)灵活运用栈与队列这两种数据结构解决一些综合应用问题。
二、实验环境与方法
ﻩ实验方法:
(一）综合运用课本所学得知识，用不同得算法实现在不同得程序功能。
（二)结合指导老师得指导,解决程序中得问题,正确解决实际中存在得异常情况,逐步改善功能.
(三)根据实验内容，编译程序。
实验环境：Ｗinｄｏws　xp Viｓual C＋+6、0
三、实验内容及过程描述
实验步骤：
① 进入Visual　C++ 6、０集成环境。
② 输入自己编好得程序。
③ 检查一遍已输入得程序就是否有错(包括输入时输错得与编程中得错误），如发现有错,及时改正.
④ 进行编译与连接。如果在编译与连接过程中发现错误，频幕上会出现“报错信息”，根据提示找到出错位置与原因,加以改正。再进行编译，如此反复直到不出错为止。
⑤ 运行程序并分析运行结果就是否合理.在运行就是要注意当输入不同得数据时所得结果就是否正确,应运行多次,分别检查在不同情况下结果就是否正确。
实验内容:编译以下题目得程序并调试运行.
1）、编写一个程序alｇo3—１、cpｐ，实现顺序栈得各种基本运算，并在此基础上设计一个主程序并完成如下功能：
(1)初始化栈s;
（２)判断栈s就是否非空;
(３）依次进栈元素a,b,c，d，e；
(4）判断栈s就是否非空；
（5)输出出栈序列;
（6）判断栈ｓ就是否非空； 　　 　 　　
（7）释放栈。　　 　　 　 　 　　　 　 　图3、1 Proｊ３_1 工程组成
本工程Ｐroj3_１得组成结构如图3、１所示.本工程得模块结构如图3、2所示.图中方框表示函数，方框中指出函数名，箭头方向表示函数间得调用关系。
main
InitStack
DestroyStack
StackEmpty
Push
Pop
GetTop

图3、2 　Proj3_1工程得程序结构图
其中包含如下函数:
InitＳtack（SｑStａｃｋ *&s） //初始化栈S
DestroyStack（SqStack　＊＆s)ﻩ//销毁栈s
StackEｍｐty（ＳｑStacｋ *ｓ） ﻩ//判断栈空
Push（SｑSｔａｃk ＊&s，ElemTｙpｅ ｅ) //进栈
Pop（SqStａck *＆ｓ,EｌemＴype &e）ﻩ//出栈
ＧｅtＴop（SqStacｋ　*s,ＥlｅmTyｐe　&e）ﻩﻩ//取栈顶元素
　　对应得程序如下：
　 　//文件名:algo3-1、cpp
#include
#include
#define MaxSize 100
typedef char ElemType;
typedef struct
{

ElemType data[MaxSize];
int top; //栈顶指针
} SqStack;
void InitStack(SqStack *&s) //初始化栈S
{ s=(SqStack *)malloc(sizeof(SqStack));
s->top=-1; //栈顶指针置为-1
}
void DestroyStack(SqStack *&s) //销毁栈s
{
free(s);
}
bool StackEmpty(SqStack *s) //判断栈空
{
return(s->top==-1);
}
bool Push(SqStack *&s,ElemType e) //进栈
{ if (s->top==MaxSize-1) //栈满得情况,即栈上溢出
return false;
s->top++; //栈顶指针增1
s->data[s->top]=e; //元素e放在栈顶指针处
return true;
}
bool Pop(SqStack *&s,ElemType &e) //出栈
{ if (s->top==-1) //栈为空得情况,即栈下溢出
return false;
e=s->data[s->top]; //取栈顶指针元素得元素
s->top--; //栈顶指针减1
return true;
}
bool GetTop(SqStack *s,ElemType &e) //取栈顶元素
{ if (s->top==-1) //栈为空得情况,即栈下溢出
return false;
e=s->data[s->top]; //取栈顶指针元素得元素
return true;
}

设计ｅxp３-1、cｐｐ程序如下
//文件名:exp3-1、cpp
#include
#include
#define MaxSize 100
typedef char ElemType;
typedef struct
{

ElemType data[MaxSize];
int top; //栈顶指针
} SqStack;
extern void InitStack(SqStack *&s);
extern void DestroyStack(SqStack *&s);
extern bool StackEmpty(SqStack *s);
extern bool Push(SqStack *&s,ElemType e);
extern bool Pop(SqStack *&s,ElemType &e);
extern bool GetTop(SqStack *s,ElemType &e);
void main()
{
ElemType e;
SqStack *s;
printf("栈s得基本运算如下:\n");
printf(" (1)初始化栈s\n");
InitStack(s);
printf(" (2)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (3)依次进栈元素a,b,c,d,e\n");
Push(s,'a');
Push(s,'b');
Push(s,'c');
Push(s,'d');
Push(s,'e');
printf(" (4)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (5)出栈序列:");
while (!StackEmpty(s))
{
Pop(s,e);
printf("%c ",e);
}
printf("\n");
printf(" (6)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (7)释放栈\n");
DestroyStack(s);
}

运行结果如下：

2）、编写一个程序alｇo3—2、ｃpp,实现链栈得各种基本运算，并在此基础上设计一个主程序并完成如下功能：
（1)初始化链栈s;
（2)判断链栈ｓ就是否非空;
（3）依次进栈ａ，ｂ，c,d，e；
（4)判断链栈ｓ就是否非空；
(5）输出链栈长度;
（6）输出从栈底到栈顶元素;
（7）输出出队序列；
（8）判断链栈s就是否非空; 　　 　 图33　 Ｐroj３_2工程组成
(９)释放队列。
本工程Pｒｏｊ3_2得组成结构如图３、３所示。本工程得模块结构如图３、4所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间得调用关系。
main
InitStack
DestroyStack
StackEmpty
Push
Pop
GetTop

　 　 　 图3、４ 　Proj3_2工程得程序结构图
其中包含如下函数：
ＩnｉtＳtａcｋ（ＬｉStaｃk *&s）ﻩﻩ//初始化栈ｓ　
ＤeｓtroyStack（LiＳtack ＊&ｓ） //销毁栈
StackＥmpｔy(LiStack　*s)ﻩ／/判断栈就是否为空
Ｐush(LiStaｃｋ ＊&s，ElemTyｐe e) //进栈
Pｏp（ＬiStacｋ　＊&s，ＥlemType ＆ｅ）ﻩ//出栈
GetTop(ＬiStack　*ｓ,EleｍＴyｐｅ　＆e)ﻩ／/取栈顶元素
对应得程序如下:
//文件名:algo3-2、cpp
#include
#include
typedef char ElemType;
typedef struct linknode
{
ElemType data; //数据域

ElemType data; //数据域

struct linknode *next; //指针域
} LiStack;
void InitStack(LiStack *&s) //初始化栈s
{ s=(LiStack *)malloc(sizeof(LiStack));
s->next=NULL;
}
void DestroyStack(LiStack *&s) //销毁栈
{ LiStack *p=s,*q=s->next;
while (q!=NULL)
{ free(p);
p=q;
q=p->next;
}
free(p); //此时p指向尾节点,释放其空间
}
bool StackEmpty(LiStack *s) //判断栈就是否为空
{
return(s->next==NULL);
}
void Push(LiStack *&s,ElemType e) //进栈
{ LiStack *p;
p=(LiStack *)malloc(sizeof(LiStack));
p->data=e; //新建元素e对应得节点*p
p->next=s->next; //插入*p节点作为开始节点
s->next=p;
}
bool Pop(LiStack *&s,ElemType &e) //出栈
{ LiStack *p;
if (s->next==NULL) //栈空得情况
return false;
p=s->next; //p指向开始节点
e=p->data;
s->next=p->next; //删除*p节点
free(p); //释放*p节点
return true;
}
bool GetTop(LiStack *s,ElemType &e) //取栈顶元素
{ if (s->next==NULL) //栈空得情况
return false;
e=s->next->data;
return true;
}
设计 exp3-2、cpp 主程序

//文件名:exp3-2、cpp
#include
#include
typedef char ElemType;
typedef struct linknode
{
ElemType data; //数据域
struct linknode *next; //指针域
} LiStack;
extern void InitStack(LiStack *&s);
extern void DestroyStack(LiStack *&s);
extern bool StackEmpty(LiStack *s);
extern void Push(LiStack *&s,ElemType e);
extern bool Pop(LiStack *&s,ElemType &e);
extern bool GetTop(LiStack *s,ElemType &e);
void main()
{
ElemType e;
LiStack *s;
printf("栈s得基本运算如下:\n");
printf(" (1)初始化栈s\n");
InitStack(s);
printf(" (2)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (3)依次进栈元素a,b,c,d,e\n");
Push(s,'a');
Push(s,'b');
Push(s,'c');
Push(s,'d');
Push(s,'e');
printf(" (4)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (5)出栈序列:");
while (!StackEmpty(s))
{
Pop(s,e);
printf("%c ",e);
}
printf("\n");
printf(" (6)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (7)释放栈\n");
DestroyStack(s);
}

程序运行结果如下:

3）、编写一个程序algo3－3、ｃｐp，实现顺序环形队列得各种基本运算,并在此基础上设计一个主程序并完成如下功能：
（１）初始化队列q；
(２)判断队列ｑ就是否非空；
(３）依次进队列ａ,ｂ,c;
（４）出队一个元素,输出该元素;
(５）输出队列q得元素个数;
（６）依次进队列元素d，e，ｆ; 　　 　　 图3—5 Ｐroj3_３得工程组成
（7)输出队列q得元素个数；
(8）输出出队序列;
(９）释放队列。
本工程Pｒoj３＿３得组成结构如图3、５所示。本工程得模块结构如图3、6所示。图中方框表示函数,方框中指出函数名，箭头方向表示函数间得调用关系。
main
InitStack
DestroyStack
StackEmpty
Push
Pop
GetTop

图3、6 Ｐroj3_3工程得程序结构图
其中包含如下函数：
InitQｕeuｅ（SqＱｕeuｅ　＊＆ｑ）ﻩ//初始化队列
ＤｅstroyQｕeue(SｑQｕeue ＊＆ｑ) //销毁队列
QueｕeEmptｙ（SｑQｕeuｅ ＊ｑ)ﻩ／／判断队列空
enQueｕe(ＳｑQueue ＊＆q，EｌeｍTyｐe e)ﻩ//进队
deＱｕeue(SqQuｅue *＆q，ElemType ＆e）ﻩ//出队
对应得程序如下：
//文件名:algo3-3、cpp
#include
#include
#define MaxSize 5
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int front,rear; //队首与队尾指针
} SqQueue;
void InitQueue(SqQueue *&q) //初始化队列
{ q=(SqQueue *)malloc (sizeof(SqQueue));
q->front=q->rear=0;
}
void DestroyQueue(SqQueue *&q) //销毁队列
{
free(q);
}
bool QueueEmpty(SqQueue *q) //判断队列空
{
return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e) //进队
{
if ((q->rear+1)%MaxSize==q->front) //队满上溢出
return false;
q->rear=(q->rear1)%MaxSize;
q->data[q->rear]=e;
return true;
}
bool deQueue(SqQueue *&q,ElemType &e) //出队
{
if (q->front==q->rear) //队空下溢出
return false;
q->front=(q->front+1)%MaxSize;
e=q->data[q->front];
return true;
}

设计 exp3-3、cpp 主程序
#include
#include
#define MaxSize 5

　typedef char ElemType;
typedef struct
{
ElemType elem[MaxSize];
int front,rear; //队首与队尾指针
} SqQueue;
extern void InitQueue(SqQueue *&q);
extern void DestroyQueue(SqQueue *&q);
extern bool QueueEmpty(SqQueue *q);
extern bool enQueue(SqQueue *&q,ElemType e);
extern bool deQueueSqQueue *&q,ElemType &e);
void main()
{
ElemType e;
SqQueue *q;
printf("环形队列基本运算如下:\n");
printf(" (1)初始化队列q\n");
InitQueue(q);
printf(" (2)依次进队列元素a,b,c\n");
if (!enQueue(q,'a')) printf("\t提示:队满,不能进队\n");
if (!enQueue(q,'b')) printf("\t提示:队满,不能进队\n");
if (!enQueue(q,'c')) printf("\t提示:队满,不能进队\n");
printf(" (3)队列为%s\n",(QueueEmpty(q)?"空":"非空"));
if (deQueue(q,e)==0)
printf("队空,不能出队\n");
else
printf(" (4)出队一个元素%c\n",e);
printf(" (5)依次进队列元素d,e,f\n");
if (!enQueue(q,'d')) printf("\t提示:队满,不能进队\n");
if (!enQueue(q,'e')) printf("\t提示:队满,不能进队\n");
if (!enQueue(q,'f')) printf("\t提示:队满,不能进队\n");
printf(" (6)出队列序列:");
while (!QueueEmpty(q))
{ deQueue(q,e);
printf("%c ",e);
}
printf("\n");
printf(" (7)释放队列\n");
DestroyQueue(q);
}

程序运行结果如下:

四、总结
从数据结构得定义瞧,栈与队列也就是一种线性表。其与线性表得不同之处在于栈与队列得相关运算具有特殊性,只就是线性表相关运算得一个子集.一般线性表得上得插入、删除运算不受限制,而栈与队列上得插入、删除运算受某种特殊限制。因此。栈与队列也称为操作受限得线性表.