数据结构实验三

《数据结构》实验报告三-1-

实验报告书

课程名称：《数据结构》

实验题目：实验三

栈

一、实验目的

（1）掌握栈与队列的数据类型描述及特点；

（2）掌握栈的顺序和链式存储存表示与基本算法的实现；

（3）按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例的运行过程抓获

相关屏面验证程序设计的正确性。

二'实验内容

（1）实现顺序栈的创建（初始化）、压入（插入）、弹出（删除）操作（数据元素类型自己选取，

如整型、字符型等，或者参照书上算法选取数据类型），并给出栈的每次操作变化状态；

（2）实现链栈的创建（初始化）、压入（插入）、弹出（删除）操作（数据元素类型自己选取，如

整型、字符型等，或者参照书上算法选取数据类型），要求给出栈的操作变化过程。

三'实验步骤

#include<stdio.h>

#include<stdlib.h>

#defineTRUE1

#defineFALSE0

SdefineStackSize50

typedefintStackElcmcntType;〃栈的顺序存储结构定义

typedefstruct

StackElementTypeelem[StackSize];〃用来存放栈中元素的一堆数组

inttop;〃用来存放栈顶元素的下标

《数据结构》实验报告三_________________________-2」

JSqStack;

voidInitStack(SqStack*s);

intIsEmpty(SqStack*s);

intIsFull(SqStack*s);

intPush(SqStack*s,StackElementTypee);

intPop(SqStack*s,StackElementType*e);

intGetTop(SqStack*s,StackElementType*e);

intGetStack(SqStack*s);

intmain()

(

SqStacks;

StackElementTypee;

StackElementTypex;

intflag=l;

while(flag!=0)

(

printf(〃二二二二顺序栈的操作=二=\n〃)；

printf(〃①初始化栈\n");

printf(〃②元素进栈\n〃)；

printf(，z③元素出栈\n〃)；

printf(〃④显示栈元素\n〃)；

printf(〃⑤结束程序\n〃)；

printf(〃请输入需要进行的操作：\n〃)；

scanf&flag);

switch(flag)

(

case1:InitStack(&s);break;

case2:printf("元素进栈,请输入1个数据：\n〃)；

scanf&e);

Push(&s,e);

printf(〃进栈成功！\n〃);break;

case3:printf("开始出栈！\n〃)；

Pop(&s,&x);

printf("出栈成功！\n〃);break;

case4:GetStack(&s);break;

case5:return0;

default:printf("输入步骤错误！\n〃);

《数据结构》实验报告三-3-

)

return0;

)

voidInitStack(SqStack*s)

(

s->top=-l;

printf("栈创建成功\n");

)

intIsEmpty(SqStack*s)〃判栈s为空时返回值为真,反之为假

(

return(s->top==-1?TRUE:FALSE);

)

intIsFull(SqStack*s)〃判栈满

(

return(s->top==StackSize-1?TRUE:FALSE);

)

intPush(SqStack*s,StackElementTypee)〃进栈

(

if(s->top==StackSizeT)

(

return(FALSE);〃栈已满

}

s->top++;

s->elem[s->top]=e;

return(TRUE);

)

intPop(SqStack*s,StackElementType*e)〃将栈s的栈顶元素弹出,放到e所指的存储空间中

(

if(s->top==-1)

(

return(FALSE);

}

else

(

*e=s->elem[s->top];

s->top—;〃修改栈顶指针

《数据结构》实验报告三____________________-4」

return(TRUE);

}

)

intGetTop(SqStack*s,StackElementType*e)〃将栈s的栈顶元素弹出,放到e所指的存储空间

中，但栈顶指针保持不变

(

if(s->top==T)〃栈为空

(

return(FALSE);

)

else

(

*e=s->elem[s->top];

return(TRUE);

}

)

intGetStack(SqStack*s)〃将当前栈内元素显示出来

(

inti;

i=s->top;

printf(〃当前栈内元素：\n〃)；

for(;i>-l;i--)

(

printfs->elem[i]);

)

printf(〃\n〃);

return(TRUE);

)

链栈的操作和顺序栈十分相似，首先给出链栈的结构定义

ttinclude<stdio.h>

#include<stdlib.h>

♦defineTRUE1

#defineFALSE0

typedefintStackElementType;//链栈的结构定义

typedefstructnode

(

StackElementTypedata;

structnode*next;

《数据结构》实验报告三-5.

}LinkStackNode;

typedefLinkStackNode*LinkStack;

voidInitStackNode(LinkStacktop);

intIsEmpty(LinkStacktop);

intPush(LinkStacktop,StackElementTypex);

intPop(LinkStacktop,StackElementType*x);

intGetStack(LinkStackNode*p);

intmain()

(

LinkStacks;

intcount;

s=(LinkStack)malloc(sizeof(LinkStackNode));

intflag=l;

while(flag!=O)

(

printf(〃二二二二链栈的操作二二二=\n〃);

printfC①初始化栈\n〃)；

printf(，z②元素进栈\n〃)；

printf(z，③元素出栈\n〃)；

printf(〃④显示栈元素\n〃)；

printf(，z⑤结束程序\n〃)；

printf(〃请输入需要进行的操作：\n〃)；

scanf&flag);

switch(flag)

(

case1:printf(〃初始化链栈！\n");

InitStackNode(s);

printf("初始化成功！\n〃);break;

case2:

inti;

for(i=0;i<10;i++)

(

Push(s,i);

)

printf(〃进栈成功！\n");break;

case3:printf(〃开始出栈！\n");

Pop(s,&count);

printf("出栈成功！\n");break;

case4:GetStack(s);break;

case5:return0;

default:printf(〃输入步骤错误！\n〃);

)

)

return0;

《数据结构》实验报告/-6.

voidInitStackNode(LinkStacktop)〃建立一个空链栈

(

top->next=NULL;

)

intIsEmpty(LinkStacktop)

(

if(top->next==NULL)

return(TRUE);

return(FALSE);

)

intPush(LinkStacktop,StackElementTypex)〃将数据元素x压入栈top中

(

LinkStackNode*temp;

temp=(LinkStackNode*)malloc(sizeof(LinkStackNode));

if(temp二二NULL)

(

return(FALSE)"/申请空间失败

)

temp->data=x;

temp->next=top->next;

top->next=temp;〃修改当前栈顶指针

return(TRUE);

)

intPop(LinkStacktop,StackElementType*x)〃将栈top的栈顶元素弹出，放到x所指的存储空

间中

{

LinkStackNode*temp;

temp=top->next;

if(temp二二NULL)〃栈为空

(

r