软件实验报告栈表.docx
- 文档编号:14895224
- 上传时间:2023-06-28
- 格式:DOCX
- 页数:18
- 大小:154.79KB
软件实验报告栈表.docx
《软件实验报告栈表.docx》由会员分享,可在线阅读,更多相关《软件实验报告栈表.docx(18页珍藏版)》请在冰点文库上搜索。
软件实验报告栈表
——
(运行环境:
Dev-C++)
班级:
200715w1
学号:
20073558
一、实验名称
熟悉链式栈的基本操作
二、实验目的
●熟悉编程环境
●实现链式栈
●实现链式栈的取栈顶、删除、插入、显示操作
三、实验要求
●编写函数,实现链式栈的插入
●编写函数,实现链式栈的删除
●编写函数,实现链式栈取栈顶元素操作
●编写函数,实现链式栈显示操作
四、实验知识
栈表简介
定义:
限定只能在表的同一端进行插入和删除操作的线性表。
其中允许进行插入和删除操作的一端称为栈顶,而表中固定的一端称为栈底。
线性表、栈与队的异同点
相同点:
都是线性结构,都是逻辑结构的概念。
都可以用顺序存储或链表存储;栈和队列是两种特殊的线性表,即受限的线性表,只是对插入、删除运算加以限制。
不同点:
1、运算规则不同,线性表为随机存取,而栈是只允许在一端进行插入、删除运算,因而是后进先出表LIFO;队列是只允许在一端进行插入、另一端进行删除运算,因而是先进先出表FIFO。
2、用途不同,堆栈用于子程调用和保护现场,队列用于多道作业处理、指令寄存及其他运算等等。
五、栈表的基本操作
链栈
1、voidprint_snode(snode*currentPtr)。
显示链式栈。
2、voidpush(snode*&topPtr,intvalue)。
链式栈的入栈操作。
3、intpop(snode*&topPtr)。
链式栈的入栈操作。
4、intgettop(snode*&topPtr)。
链式栈的取栈顶操作。
5、intisempty(snode*topPtr)。
判断头节点是否为空。
6、voidinstructions(void)。
用户操作界面介绍。
顺序栈
1、voidprintstack()。
显示顺序栈。
2、voidpush(intpushvalue)。
顺序栈的入栈操作。
3、intpop()。
顺序栈的入栈操作。
4、intgettop()。
顺序栈的取栈顶操作。
5、intisempty()。
判断头节点是否为空。
6、voidinstructions(void)。
用户操作界面介绍。
六、栈表基本操作的实施步骤
顺序栈
1、入栈算法:
●判断栈是否已满
●空,则更新top值,再更新stack[top]
满,则通知用户栈溢出
2、出栈算法:
●判断栈是否为空
●不空,则弹出stack[top],再更新top值
空,则通知用户栈溢出
3、取栈顶算法:
●返回stack[top]值
4、显示栈表算法:
●判断栈表是否为空
●空,通知用户栈表为空。
不空,输出栈表中数据直到top值为-1
链式栈
1、入栈算法:
●生成一个新结点newPtr
●判断是否还有存储空间
●有,则更新newPtr数据域和指针域,在更新topPtr即:
newPtr->data=value;
newPtr->linkPtr=topPtr;
topPtr=newPtr;
无,则通知用户入栈失败
2、出栈算法:
●生成一临时结点tempPtr和一出栈数据popvalue
●更新临时结点,更新出栈数据
●更新topPtr,释放临时结点,返回出栈数据
3、取栈顶算法:
●返回头结点值
4、显示栈表算法:
●判断栈表是否为空
●空,通知用户栈表为空。
不空,输出栈表中数据直到结点中指针域为空
七、实验过程
1、程序:
(链式)
#include"stdlib.h"
#include"stdio.h"
structsnode
{
intdata;
structsnode*linkPtr;
};
voidinstructions(void)
{
printf(
"*************************************\n"
"**欢迎来到宓氏的世界!
**\n"
"**1.入栈**\n"
"**2.出栈**\n"
"**3.取栈顶元素**\n"
"**4.退出**\n"
"*************************************\n\n");
}
intisempty(snode*topPtr)
{
return(topPtr==NULL);
}
voidpush(snode*&topPtr,intvalue)
{
snode*newPtr;
newPtr=(snode*)malloc(sizeof(snode));
if(newPtr!
=NULL)
{
newPtr->data=value;
newPtr->linkPtr=topPtr;
topPtr=newPtr;
}
else
{
printf("内存中无可用空间,%d未成功插入!
\n",value);
}
}
intpop(snode*&topPtr)
{
intpopvalue;
snode*tempPtr;
tempPtr=topPtr;
popvalue=topPtr->data;
topPtr=topPtr->linkPtr;
free(tempPtr);
returnpopvalue;
}
intgettop(snode*&topPtr)
{
return(topPtr->data);
}
voidprint_snode(snode*currentPtr)
{
if(currentPtr==NULL)
{
printf("栈为空!
\n");
}
else
{
printf("栈表为:
\n");
while(currentPtr!
=NULL)
{
printf("%d-->",currentPtr->data);
currentPtr=currentPtr->linkPtr;
}
printf("NULL\n");
}
}
intmain()
{
snode*topPtr=NULL;
intchoice;
intvalue;
instructions();
printf("?
");
scanf("%d",&choice);
while(choice!
=4)
{
switch(choice)
{
case1:
printf("入栈中...\n");
printf("请输入入栈数据:
\n");
scanf("%d",&value);
printf("入栈的值是:
%d\n",value);
push(topPtr,value);
print_snode(topPtr);
break;
case2:
printf("出栈中...\n");
if(!
isempty(topPtr))
{
printf("出栈的值是:
%d\n",pop(topPtr));
}
print_snode(topPtr);
break;
case3:
printf("取栈顶元素中...\n");
printf("栈顶元素为:
%d\n",gettop(topPtr));
break;
default:
printf("选择错误!
\n");
instructions();
break;
}
printf("?
");
scanf("%d",&choice);
}
printf("对链式线性表的操作结束!
\n\n");
printf("***********宓氏出品,必属精品!
***********\n");
system("pause");
return0;
}
(顺序)
#include"stdlib.h"
#include"stdio.h"
#defineMAXSIZE100
intstack[MAXSIZE];
inttop(-1);
voidinstructions(void)
{
printf(
"*************************************\n"
"**欢迎来到宓氏的世界!
**\n"
"**1.入栈**\n"
"**2.出栈**\n"
"**3.取栈顶元素**\n"
"**4.退出**\n"
"*************************************\n\n");
}
voidpush(intpushvalue)
{
if(top==MAXSIZE-1)
{
printf("栈满,溢出!
\n");
exit
(1);
}
else
{
top++;
stack[top]=pushvalue;
}
}
intpop()
{
intpopvalue;
if(top==-1)
{
printf("栈空,溢出!
\n");
exit
(1);
}
else
{
popvalue=stack[top];
top--;
}
returnpopvalue;
}
intgettop()
{
returnstack[top];
}
voidprintstack()
{
if(top==-1)
{
printf("栈为空!
\n");
}
else
{
printf("栈表为:
\n");
for(inti=top;i>=0;i--)
printf("%d-->",stack[i]);
}
printf("NULL\n");
}
intisempty()
{
return(top==-1);
}
intmain()
{
intchoice;
intvalue;
instructions();
printf("?
");
scanf("%d",&choice);
while(choice!
=4)
{
switch(choice)
{
case1:
printf("入栈中...\n");
printf("请输入入栈数据:
\n");
scanf("%d",&value);
printf("入栈的值是:
%d\n",value);
push(value);
printstack();
break;
case2:
printf("出栈中...\n");
if(!
isempty())
{
printf("出栈的值是:
%d\n",pop());
}
printstack();
break;
case3:
printf("取栈顶元素中...\n");
printf("栈顶元素为:
%d\n",gettop());
break;
default:
printf("选择错误!
\n");
instructions();
break;
}
printf("?
");
scanf("%d",&choice);
}
printf("对顺序栈的操作结束!
\n\n");
printf("***********宓氏出品,必属精品!
***********\n");
system("pause");
return0;
}
2、运行结果:
(链式)
(顺序)
八、实验小结
此次栈表实验明显比顺序链式线性表简单多了。
只要理解栈是链式线性表的限制形式(它只允许在一端进行插入、删除运算,简称后进先出表LIFO),难么此次试验也就迎刃而解。
栈的产生是为了解决链式线性表在查找地址方面的时间复杂度而诞生地的,因而它经常用于子程序调用,保护数据方面。
因此,虽然它失去了删插数据的灵活性,但是在它擅长的方面大大的降低了时间复杂度,提高了计算机的运算效率。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 软件 实验 报告