《数据结构》实验报告
实验序号：5 实验项目名称：链式栈 学 号 实验地点 1207082131 姓 名 指导教师 罗维卿 专业、班 实验时间 12物联网 一、实验目的及要求 1. 掌握栈的存储结构的表示和实现方法。 二、实验设备（环境）及要求 微型计算机； windows 操作系统； Microsoft Visual Studio 6.0集成开发环境。 三、实验内容与步骤 （1）根据输入的栈中元素个数和各元素值建立一个链栈，并输出链栈中各元素值, 观察输入的内容与输出的内容是否一致,特别注意栈顶元素的位置。 （2）将数据元素x入栈，并输出入栈后的链栈中各元素值。 （3）将链栈中的栈顶元素出栈，并输入出栈元素的值和出栈后链栈中各元素值。 四、实验结果与数据处理 五、分析与讨论 对上机实践结果进行分析，上机的心得体会。 六、教师评语 签名： 日期： 成绩 附源程序清单：
http://wenku.http://www.wodefanwen.com//link?url=G15bQUbjDe_Kx-bejATfZkUM_pkAPWkfLo2EnxBAF1_JkQ2w7BGlIgDUSr2mwxNssTelZ5prE5lUSaSvDuE3V3hgOrpTCkWodEdQTyACQWi 1．实验要求
编程实现如下功能：
（1）根据输入的栈中元素个数n和各元素值建立一个顺序栈，并输出栈中各元素值。 （2）将数据元素e入栈，并输出入栈后的顺序栈中各元素值。
（3）将顺序栈中的栈顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值。 2. 实验相关原理：
栈是一种插入和删除操作都限制在表的一端进行的特殊线性表，它的操作具有“先进后出”的特性。采用顺序存储结构的栈称为顺序栈。栈的存储结构描述如下：
#define MAXSIZE 100; /*顺序栈的最大长度*/ typedef struct
{ Selemtype base[MAXSIZE]; /*存储栈中数据元素的数组*/
int top; /*top为栈顶指针，它指示栈顶元素的存储空间的下一个存储单元*/ }Sqstack;
【核心算法提示】
1．顺序栈入栈操作的基本步骤：首先判断顺序栈是否为满，如果满，则函数返回ERROR，否则将待入栈的数据元素存放在top所指示的存储单元中，再使top后移一个存储单元位置，即将top值加1，最后函数返回OK。
2． 顺序栈出栈操作的基本步骤：首先判断顺序栈是否为空，如果空，则函数返回ERROR，否则将栈顶指针前移一个存储单元位置，即将top值减1,再将top所指示的栈顶元素用e返回其值，并使函数返回OK。 【核心算法描述】
status Push(Sqstack &S,Selemtype e)
/*将数据元素e压入到顺序栈S中，使其成为新的栈项元素*/ { if (S.top >=MAXSIZE) /*如果栈满，则函数返回ERROR*/ return ERROR;
S.base[S.top++]=e;/*将新元素e存放在top所指示的存储单元中,并使top值加1*/ return OK; }
status Pop(Sqstack &S,Selemtype &e)
/*将顺序栈S中的栈顶元素从栈中删除，并用e返回其值*/ { if (S.top==0) /*如果栈空，则函数返回ERROR*/ Return ERROR;
e=S.base[--S.top];/*将top值减1,并用e保存top所指示的栈顶元素值*/ return OK; }
3．源程序代码参考
#define MAXSIZE 100 typedef struct
{ int base[MAXSIZE];
int top; /*top指示存储栈顶元素的下一存储单元*/ }Sqstack; /*顺序栈的类型定义*/
Sqstack Push(Sqstack S,int e) /*顺序栈的入栈操作函数*/ { if (S.top>=MAXSIZE)
printf(\
else
S.base[S.top++]=e;
return S; }
Sqstack Pop(Sqstack S,int *e) /*顺序栈的出栈操作函数*/ { if (S.top==0)
printf(\
else
*e=S.base[--S.top];
return S; }
void Stack_display(Sqstack S) /*顺序栈的输出函数*/ { int i;
for(i=0; i { Sqstack S; int i,j,n,x,e; printf(\请求输入顺序栈中元素个数*/ scanf(\ printf(\请求输入顺序栈中各个元素值*/ for(i=0;i scanf(\ S.top=n; printf(\ Stack_display(S); printf(\请求输入需要入栈的新元素*/ scanf(\ S=Push(S,x); printf(\提示输出入栈后栈中各个元素值*/ Stack_display(S); /*调用顺序栈的输出函数*/ S=Pop(S,&e); printf(\输出出栈元素的值*/ printf(\提示输出出栈后栈中各个元素值*/ Stack_display(S); /*调用顺序栈的输出函数*/ } （1）根据输入的栈中元素个数和各元素值建立一个链栈，并输出链栈中各元素值, 观察输入的内容与输出的内容是否一致,特别注意栈顶元素的位置。 （2）将数据元素x入栈，并输出入栈后的链栈中各元素值。 （3）将链栈中的栈顶元素出栈，并输入出栈元素的值和出栈后链栈中各元素值。 ⑵ 核心算法提示 采用链式存储结构的栈称为链栈，链栈的存储结构描述如下： typedef struct Snode { Selemtype data;/*数据域*/ struct Snode *next;/*指针域*/ }SNODE,* LinkStack;/*其中SNODE为链栈中的结点类型名, LinkStack为指向结点的指针类型名*/ 如果栈中元素序列为{a1,a2，?,an}，则链栈的存储结构如下图3-1所示： 图3-2： 链栈的存储结构示意图 top an an-1 an-2 … a1 ^ 从图3-1可看出，栈的链式存储结构与单链表的存储结构相同，所有在链栈上进行入栈和出栈操作与单链表上的插入和删除操作的主要步骤相同。只不过要特别注意以下几点： （1）链栈中无需加头结点。 （2）链栈中的指针是指向栈中元素序列的前驱结点。 （3）链栈中的入栈和出栈操作都是在链表的表头进行。 ⑶ 核心算法描述 status Push(LinkStack &top,int e) /*将数据元素e压入到链栈top中，使其成为新的栈项元素*/ { LinkStack p; p=(LinkStack)malloc(sizeof(SNODE)); /*生成一个新的结点*/ if (!p) /*如果分配空间失败，则函数返回\ return OVERFLOW; p->data=e; /*新结点的数据域赋值*/ p->next=top; /*修改链使新结点插入到链表的头部,并成为新的栈顶元素*/ top=p; return OK; } status Pop(LinkStack &top,int &e) /*将链栈top中的栈顶元素从栈中删除，并用e返回其值*/ { LinkStack q; if (!top) /*如果栈空，则函数返回ERROR*/ return ERROR; e=top->data; /*将被删的栈顶元素的值保存在e中*/ q=top; /*用q记下待删的栈顶元素*/ top=q->next; /*修改链使待删结点从链中“卸下”，此时被删结点的后继成为新的栈顶元素结点*/ free(q); /*释放被删结点的存储空间*/ return OK; } 《数据结构》实验报告 实验序号：7 实验项目名称：串 学 号 实验地点 31 姓 名 指导教师 罗维卿 专业、班 实验时间 12物联网 一、实验目的及要求 1. 掌握串的顺序表示和堆表示实现方法； 二、实验设备（环境）及要求 微型计算机；