数据结构栈和队列实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
一、实验目的和要求
(1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。
(4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。
二、实验环境和方法
实验方法:
(一)综合运用课本所学的知识，用不同的算法实现在不同的程序功能。 (二)结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。
(三)根据实验内容，编译程序。
实验环境:Windows xp Visual C++6.0
三、实验内容及过程描述
实验步骤:
? 进入Visual C++ 6.0集成环境。
? 输入自己编好的程序。
? 检查一遍已输入的程序是否有错(包括输入时输错的和编程中的错误)，如发现
有错，及时改正。
? 进行编译和连接。如果在编译和连接过程中发现错误，频幕上会出现“报错信
息”，根据提示找到出错位置和原因，加以改正。再进行编译，如此反复直到不出
错为止。
? 运行程序并分析运行结果是否合理。在运行是要注意当输入不同的数据时所得结
果是否正确，应运行多次，分别检查在不同情况下结果是否正确。
实验内容:编译以下题目的程序并调试运
行。
1)、编写一个程序algo3-1.cpp，实现顺序栈
的各种基本运算，并在此基础上设计一个主
程序并完成如下功能:
(1)初始化栈s;
(2)判断栈s是否非空;
(3)依次进栈元素a,b,c,d,e;
(4)判断栈s是否非空;
(5)输出出栈序列;
(6)判断栈s是否非空;
(7)释放栈。 图3.1 Proj3_1 工程组成
本工程Proj3_1的组成结构如图3.1所示。本工程的模块结构如图3.2所示。图中方框
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示函数，方框中指出函数名，箭头方向表示函数间的调用关系。
main
DestroyStack Pop InitStack StackEmpty PusGetTo h p
图3.2 Proj3_1工程的程序结构图 其中包含如下函数:
InitStack(SqStack *&s) //初始化栈S
DestroyStack(SqStack *&s) //销毁栈s
StackEmpty(SqStack *s) //判断栈空
Push(SqStack *&s,ElemType e) //进栈
Pop(SqStack *&s,ElemType &e) //出栈
GetTop(SqStack *s,ElemType &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;
}
设计exp3-1.cpp程序如下
//文件名: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)、编写一个程序algo3-2.cpp，实现链栈的各种基本运算，并在此基础上设计一个主程序并完成如
下功能:
(1)初始化链栈s;
(2)判断链栈s是否非空;
(3)依次进栈a，b，c，d，e;
(4)判断链栈s是否非空;
(5)输出链栈长度;
(6)输出从栈底到栈顶元素;
(7)输出出队序列;
(8)判断链栈s是否非空; 图3.3 Proj3_2工程组成 (9)释放队列。
本工程Proj3_2的组成结构如图3.3所示。本工程的模块结构如图3.4所示。图中方框表
示函数，方框中指出函数名，箭头方向表示函数间的调用关系。
main
DestroyStack StackEmpty Pop InitStack PusGetTo h p
图3.4 Proj3_2工程的程序结构图 其中包含如下函数:
InitStack(LiStack *&s) //初始化栈s
DestroyStack(LiStack *&s) //销毁栈
StackEmpty(LiStack *s) //判断栈是否为空
Push(LiStack *&s,ElemType e) //进栈
Pop(LiStack *&s,ElemType &e) //出栈
GetTop(LiStack *s,ElemType &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.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序
并完成如下功能:
(1)初始化队列q;
(2)判断队列q是否非空;
(3)依次进队列a,b,c;
(4)出队一个元素，输出该元素;
(5)输出队列q的元素个数;
(6)依次进队列元素d,e,f; 图3-5 Proj3_3的工程组成 (7)输出队列q的元素个数;
(8)输出出队序列;
(9)释放队列。
本工程Proj3_3的组成结构如图3.5所示。本工程的模块结构如图3.6所示。图中方框表
示函数，方框中指出函数名，箭头方向表示函数间的调用关系。
main
DestroyStack StackEmpty Pop InitStack PusGetTo h p
图3.6 Proj3_3工程的程序结构图 其中包含如下函数:
InitQueue(SqQueue *&q) //初始化队列
DestroyQueue(SqQueue *&q) //销毁队列
QueueEmpty(SqQueue *q) //判断队列空
enQueue(SqQueue *&q,ElemType e) //进队
deQueue(SqQueue *&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->rear+1)%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 deQueue(SqQueue *&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);
}
程序运行结果如下:
四、
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
从数据结构的定义看，栈和队列也是一种线性表。其与线性表的不同之处在于栈和队列的相关运算具有特殊性，只是线性表相关运算的一个子集。一般线性表的上的插入、删除运算不受限制，而栈和队列上的插入、删除运算受某种特殊限制。因此。栈和队列也称为操作受限的线性表。
浙公网安备 33021202002483