栈和队列的基本操作及应用实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
栈和队列的基本操作实验报告
《数据结构》
实
验
报
告
一
软件132
201300514211
徐蜀
实验二 栈和队列的基本操作及其应用
一、实验目的
1、掌握栈和队列的顺序存储结构和链式存储结构,以便在实际中灵活应用。
2、掌握栈和队列的特点,即后进先出和先进先出的原则。
3、掌握栈和队列的基本运算,如:入栈与出栈,入队与出队等运算在顺序存储结构和链式存储结构上的实现。
二、实验内容
1(回文判断
三、实验要求
1、按照数据结构实验任务
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
,提前做好实验预习与准备工作。
2、加“*”题目必做,其他题目任选;多选者并且保质保量完成适当加分。
3、严格按照数据结构实验报告模板和规范,及时完成实验报告。
四、实验步骤
(说明:依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
以及每个操作(函数)的伪码算法、函数实现、程序编码、调试与
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
。 附流程图与主要代码)
?、数据结构与核心算法的
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
描述
(程序中每个模块或函数应加注释,说明函数功能、入口及出口参数)
1、栈的初始长度与需要再增加的长度
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef char SElemType;//定义SElemType为char型
2、栈的顺序存储表示
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
3、队列的链式表示方法
typedef struct QNode
{
SElemType data;
struct QNode *next;
} QNode, *QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
4、初始化栈
/* 函数功能:对栈进行初始化
参数:栈(SqStack &S)
成功返回1,否则返回0*/
int InitStack(SqStack &S)
{
S.base = (SElemType *)malloc(STACK_INIT_SIZE *
sizeof(SElemType)); //申请内存
if(!S.base) //判断有无申请到空间
return ERROR; //没有申请到内存,返回0
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
5、入栈操作
/*函数功能:将元素入栈
参数:栈(SqStack &S),插入元素e
插入成功返回1,否则返回0*/
int Push(SqStack &S, SElemType e)
{
if(S.top - S.base = S.stacksize) //判断栈顶与栈底的差是否大于栈的
//容量
{
S.base = (SElemType *)realloc(S.base, (S.stacksize +
STACKINCREMENT) * sizeof(SElemType));//栈满了,重新申请内存if(!S.base) //判断是否申请成功
return ERROR; //不成功返回0
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
6、出栈操作
/*函数功能:将栈中的元素弹出
参数:栈(SqStack &S),记录元素e */
int Pop(SqStack &S, SElemType &e)
{
if(S.top == S.base) //判断栈是否为空
return ERROR;
e = *(--S.top) ;
return OK;
}
7、初始化队列
/* 函数功能:初始化队列
参数:队列(LinkQueue &Q)
成功返回1, 否则返回0 */
int InitQueue(LinkQueue &Q)
{
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); //申请结点的内存
if(!Q.front) //判断有无申请到空间
return ERROR; //没有返回0
Q.front -next = NULL;
return OK;
}
8.在队列队尾插入元素
/*函数功能:在队列队尾插入元素
参数:队列(LinkQueue &Q),插入元素e
成功返回1, 否则返回0 */
int EnQueue(LinkQueue &Q, QElemType e)
{
p = (QueuePtr)malloc(sizeof(QNode)); //申请新的结点 if(!p)
return ERROR;
p - data = e;
p - next = NULL;
Q.rear - next = P;
Q.rear = p;
return OK;
}
9.删除队头元素
/*函数功能:删除对头元素
参数:队列(LinkQueue &Q),记录值e
成功返回1,否则返回0 */
int DeQueue(LinkQueue &Q, QElemType &e)
{
if(Q.front == Q.rear) //判断队列是否为空
return ERROR;
p = Q.front - next;
e = p - data;
Q.front - next = p - next;
if(Q.rear == p)
Q.rear = Q.front;
free(p);
return OK;
}
10、主函数
int main()
{
SqStack S; //声明一个栈
LinkQueue Q; //声明一个队列
char m,k,c;
int n=0,i,j,t=0,z=0;
while(!t)
{
cout 请输入你要判断回文的字符串,输入@结束:; InitQueue
(Q);
InitStack (S);
while((c=getchar())!='@')//对字符的判断 不断输入字
符 {
EnQueue (Q,c);
Push (S,c);
n++;
}
for( j=1;j=n;j++)
{
OutQueue (Q,m);
Pop (S,k);
if(m!=k)
break;
}
if(jn) //如果j n则说明全部相等
篇二:栈和队列的基本操作的实现 数据结构实验
May 7
实验报告
2015
数据结构
第二次实验 姓名:陈斌 学号:E11314079 专业:13计算机
科学与技术
学号E11314079专业计算机科学与技术姓名陈斌
实验日期 2015.05.07教师签字成绩
实验报告
【实验名称】栈和队列的基本操作的实现
【实验目的】
1.
2.
3.
4. 理解并掌握栈和队列的逻辑结构和存储结构; 理解栈和队列
的相关基本运算; 编程对相关算法进行验证; 学会利用栈和队
列解决实际问题。
【实验内容】
1. 实现顺序栈的基本运算
编写一个程序,实现顺序栈的各种基本运算,并在此基础上设
计一个主程序完成如下功能:
(1)初始化栈s;
(2)判断栈s是否为空;
(3)依次进栈元素-1,2,10,-3,5;
(4)判断栈s是否为空;
(5)输出栈长度;
(6)输出从栈顶到栈底的元素;
(7)输出出栈序列;
(8)判断栈s是否为空。
源代码:
head.h:
#includestring.h
#includectype.h
#includemalloc.h //malloc( )
#includelimits.h // INT ,MAX
#includestdio.h //EOF,NULL
#includestdlib.h //atoi( )
#includeio.h //eof( )
#includemath.h //floor( ),ceil( ),abs( )
#includeprocess.h //exit( )
#includeiostream.h //cout,cin
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
//OVERFLOW 在 math.h 中已定义为3
typedef int Status;
typedef int Boolean; // 布尔类型
head2.h:
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
main.cpp:
#define SElemType int
#includehead.h
#includehead2.h
Status InitStack(SqStack &S)
{ /* 构造一个空栈S */
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); /* 存储分配失败 */
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack &S)
{ /* 若栈S为空栈,则返回TRUE,否则返回FALSE */
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
int StackLength(SqStack &S)
{ /* 返回S的元素个数,即栈的长度 */
return S.top-S.base;
}
Status GetTop(SqStack &S,SElemType &e)
{ /* 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR */ if(S.topS.base)
{
e=*(S.top-1);
return OK;
}
else
return ERROR;
}
Status Push(SqStack &S,SElemType e)
{ /* 插入元素e为新的栈顶元素 */
if(S.top-S.base=S.stacksize) /* 栈满,追加存储空间 */
{
S.base=(SElemType
*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); /* 存储分配失败 */
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,SElemType &e)
{ /* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
Status StackTraverse(SqStack S,Status(*visit)(SElemType))
{ /* 从栈顶到栈底依次对栈中每个元素调用函数visit()。 */
/* 一旦visit()失败,则操作失败 */
while(S.topS.base)
visit(*--S.top);
coutendl;
return OK;
}
Status visit(SElemType c)
{
coutc ;
return OK;
}
void PrintMenu()
{
cout*********************欢迎使用
*********************endl; cout1.初始化栈s.endl;
cout2.判断栈s是否为空.endl;
cout3.依次进栈元素-1,2,10,-3,5.endl;
cout4.输出栈长度.endl;
cout5.输出从栈顶到栈底的元素.endl;
cout6.输出出栈序列.endl;
cout0.退出.endl;
cout**************************************************; }
void main()
{
SqStack s;
SElemType e;
PrintMenu();
while(1)
{
coutendl;
cout选择需要执行的功能:;
int number;
cinnumber;
switch(number)
{
case 1:
InitStack(s);
cout顺序栈s初始化成功.endl;
break;
篇三:栈的操作(实验报告)
实验三 栈和队列
3.1实验目的:
(1) 熟悉栈的特点(先进后出)及栈的基本操作,如入栈、
出栈等,掌握栈的基本操作
在栈的顺序存储结构和链式存储结构上的实现;
(2) 熟悉队列的特点(先进先出)及队列的基本操作,如入队、出队等,掌握队列的基
本操作在队列的顺序存储结构和链式存储结构上的实现。
3.2 实验要求:
(1) 复习课本中有关栈和队列的知识;
(2) 用C语言完成算法和程序设计并上机调试通过;
(3) 撰写实验报告,给出算法思路或流程图和具体实现(源程序)、算法分析结果(包括
时间复杂度、空间复杂度以及算法优化设想)、输入数据及程序运行结果(必要时给出多种可能的输入数据和运行结果)。
3.3 基础实验
[实验1] 栈的顺序表示和实现
实验内容与要求:
编写一个程序实现顺序栈的各种基本运算,并在此基础上设计一个主程序,完成如下功能:
(1)初始化顺序栈
(2)插入元素
(3)删除栈顶元素
(4)取栈顶元素
(5)遍历顺序栈
(6)置空顺序栈
分析:
栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
对于顺序栈,入栈时,首先判断栈是否为满,栈满的条件为:p-top= =MAXNUM-1,栈满时,不能入栈; 否则出现空间溢出,引起错误,这种现象称为上溢。
出栈和读栈顶元素操作,先判栈是否为空,为空时不能操作,否则产生错误。通常栈空作为一种控制转移的条件。
注意:
(1)顺序栈中元素用向量存放
(2)栈底位置是固定不变的,可设置在向量两端的任意一个端点
(3)栈顶位置是随着进栈和退栈操作而变化的,用一个整型量top(通常称top为栈顶指针)来指示当前栈顶位置
参考程序:
#includestdio.h
#includestdlib.h
#define MAXNUM 20
#define ElemType int
/*定义顺序栈的存储结构*/
typedef struct
{ ElemType stack[MAXNUM];
int top;
}SqStack;
/*初始化顺序栈*/
void InitStack(SqStack *p)
{ if(!p)
printf(Eorror);
p-top=-1;
}
/*入栈*/
void Push(SqStack *p,ElemType x)
{ if(p-topMAXNUM-1)
{ p-top=p-top+1;
p-stack[p-top]=x;
}
else
printf(Overflow!\n);
}
/*出栈*/
ElemType Pop(SqStack *p)
{ ElemType x;
if(p-top!=0)
{ x=p-stack[p-top];
printf(以前的栈顶数据元素%d已经被删除~\n,p-stack[p-top]);
p-top=p-top-1;
return(x);
}
else
{ printf(Underflow!\n);
return(0);
}
}
/*获取栈顶元素*/
ElemType GetTop(SqStack *p)
{ ElemType x;
if(p-top!=0)
{ x=p-stack[p-top];
return(x);
}
else
{ printf(Underflow!\n);
return(0);
}
}
/*遍历顺序栈*/
void OutStack(SqStack *p)
{ int i;
printf(\n);
if(p-top0)
printf(这是一个空栈~);
printf(\n);
for(i=p-top;i=0;i--)
printf(第%d个数据元素是:%6d\n,i,p-stack[i]);
}
/*置空顺序栈*/
void setEmpty(SqStack *p)
{
p-top= -1;
}
/*主函数*/
main()
{SqStack *q;
int y,cord;ElemType a;
do{
printf(\n);
printf(第一次使用必须初始化~\n);
printf(\n);
printf(\n 主菜单 \n);
printf(\n 1 初始化顺序栈 \n);
printf(\n 2 插入一个元素 \n);
printf(\n 3 删除栈顶元素 \n);
printf(\n 4 取栈顶元素\n);
printf(\n 5 置空顺序栈\n);
printf(\n 6 结束程序运行 \n);
printf(\n--------------------------------\n);
printf(请输入您的选择( 1, 2, 3, 4, 5,6));
scanf(%d,&cord);
printf(\n);
switch(cord)
{ case 1:
{ q=(SqStack*)malloc(sizeof(SqStack));
InitStack(q);
OutStack(q);
}break;
case 2:
{ printf(请输入要插入的数据元素:a=);
scanf(%d,&a);
Push(q,a);
OutStack(q);
}break;
case 3:
{ Pop(q);
OutStack(q);
}break;
case 4:
{ y=GetTop(q);
printf(\n栈顶元素为:%d\n,y);
OutStack(q);
}break;
case 5:
{ setEmpty(q);
printf(\n顺序栈被置空~\n);
OutStack(q);
}break;
case 6:
exit(0);
}
}while (cord=6);
}
[实验2] 栈的链式表示和实现
实验内容与要求:
编写一个程序实现链栈的各种基本运算,并在此基础上设计一个主程序,完成如下功能:
(1)初始化链栈
(2)链栈置空
(3)入栈
(4)出栈
(5)取栈顶元素
(6)遍历链栈
分析:
链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。
注意:
(1)LinkStack结构类型的定义可以方便地在函数体中修改top指针本身
(2)若要记录栈中元素个数,可将元素个数属性放在LinkStack
类型中定义。
(3)链栈中的结点是动态分配的,所以可以不考虑上溢。
参考程序:
#include stdio.h
#include malloc.h
#include stdlib.h
typedef int Elemtype;
typedef struct stacknode {
Elemtype data;
stacknode * next;
}StackNode;
typedef struct {
stacknode * top; //栈顶指针
}LinkStack;
/*初始化链栈*/
void InitStack(LinkStack * s)
{ s-top=NULL;
printf(\n已经初始化链栈~\n);
}
/*链栈置空*/
void setEmpty(LinkStack * s)
{ s-top=NULL;
printf(\n链栈被置空~\n);
}
/*入栈*/
void pushLstack(LinkStack * s, Elemtype x)
{ StackNode * p;
p=(StackNode *)malloc(sizeof(StackNode)); //建立一个节点。 p-data=x;
p-next=s-top; //由于是在栈顶pushLstack,所以要指向栈顶。
s-top=p; //插入
}
/*出栈*/
Elemtype popLstack(LinkStack * s)
{ Elemtype x;
StackNode * p;
p=s-top; //指向栈顶
if (s-top ==0)
{ printf(\n栈空,不能出栈~\n);
exit(-1);
}
x=p-data;
s-top=p-next; //当前的栈顶指向原栈的next
free(p); //释放
return x;
}