第1页 / 共22页
第2页 / 共22页
第3页 / 共22页
第4页 / 共22页
第5页 / 共22页
第6页 / 共22页
第7页 / 共22页
第8页 / 共22页
数据结构实验栈和队列详细实验报告.doc
实验三 栈和队列
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 为栈顶指针）
来指示当前栈顶位置
参考程序:
#include
#include
#define MAXNUM 20
1
#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->toptop=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");
2
return(0);
}
}
/*遍历顺序栈*/
void OutStack(SqStack *p)
{
int i;
printf("\n");
if(p->top<0)
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;
1
2
3
4
5
6
主菜单
初始化顺序栈
插入一个元素
删除栈顶元素
取栈顶元素
置空顺序栈
结束程序运行
do{
printf("\n");
printf("第一次使用必须初始化！\n");
printf("\n");
printf("\n
printf("\n
printf("\n
printf("\n
printf("\n
printf("\n
printf("\n
printf("\n--------------------------------\n");
printf("请输入您的选择( 1, 2, 3, 4, 5,6)");
scanf("%d",&cord);
printf("\n");
switch(cord)
{
case 1:
{
\n");
\n");
\n");
\n");
\n");
\n");
\n");
q=(SqStack*)malloc(sizeof(SqStack));
InitStack(q);
OutStack(q);
}break;
case 2:
3
{
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）链栈中的结点是动态分配的，所以可以不考虑上溢。
4
参考程序:
#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;
s->top=p;
}
/*出栈*/
Elemtype popLstack(LinkStack * s)
{
Elemtype x;
StackNode * p;
p=s->top;
if (s->top ==0)
{
//指向栈顶
//建立一个节点。
//由于是在栈顶 pushLstack，所以要指向栈顶。
//插入
printf("\n 栈空，不能出栈！\n");
exit(-1);
}
x=p->data;
s->top=p->next;
free(p);
return x;
}
//当前的栈顶指向原栈的 next
//释放
5
/*取栈顶元素*/
Elemtype StackTop(LinkStack *s)
{
if (s->top ==0)
{
printf("\n 链栈空\n");
exit(-1);
}
return s->top->data;
}
/*遍历链栈*/
void Disp(LinkStack * s)
{
printf("\n 链栈中的数据为：\n");
printf("=======================================\n");
StackNode * p;
p=s->top;
while (p!=NULL)
{
printf("%d\n",p->data);
p=p->next;
}
printf("=======================================\n");
}
void main()
{
printf("================= 链栈操作=================\n\n");
int i,m,n,a;
LinkStack * s;
s=(LinkStack *)malloc(sizeof(LinkStack));
int cord;
do{ printf("\n");
\n");
\n");
\n");
\n");
\n");
\n");
\n");
1
2
3
4
5
6
主菜单
初始化链栈
入栈
出栈
取栈顶元素
置空链栈
结束程序运行
printf("第一次使用必须初始化！\n");
printf("\n");
printf("\n
printf("\n
printf("\n
printf("\n
printf("\n
printf("\n
printf("\n
printf("\n--------------------------------\n");
printf("请输入您的选择( 1, 2, 3, 4, 5,6)");
scanf("%d",&cord);
printf("\n");
switch(cord)
{
case 1:
{
InitStack(s);
Disp(s);
6
}break;
case 2:
{printf("输入将要压入链栈的数据的个数：n=");
scanf("%d",&n);
printf("依次将%d 个数据压入链栈：\n",n);
for(i=1;i<=n;i++)
{scanf("%d",&a);
pushLstack(s,a);
}
Disp(s);
}break;
case 3:
{
printf("\n 出栈操作开始!\n");
printf("输入将要出栈的数据个数：m=");
scanf("%d",&m);
for(i=1;i<=m;i++)
{printf("\n 第%d 次出栈的数据是：%d",i,popLstack(s));}
Disp(s);
}break;
case 4:
{
printf("\n\n 链栈的栈顶元素为：%d\n",StackTop(s));
printf("\n");
}break;
case 5:
{
setEmpty(s);
Disp(s);
}break;
case 6:
exit(0);
}
}while (cord<=6);
}
[实验 3] 队列的顺序表示和实现
实验内容与要求
编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化队列
（2）建立顺序队列
（3）入队
（4）出队
（5）判断队列是否为空
（6）取队头元素
7
（7）遍历队列
分析:
队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
入队时，将新元素插入 rear 所指的位置，然后将 rear 加 1。出队时，删去 front 所指的元素，
然后将 front 加 1 并返回被删元素。
顺序队列中的溢出现象：
（1） "下溢"现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用
作程序控制转移的条件。
（2） "真上溢"现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错
状态，应设法避免。
（3） "假上溢"现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空
间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾
指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。
注意：
（1）当头尾指针相等时，队列为空。
（2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。
参考程序:
#include
#include
#define MAXNUM 100
#define Elemtype int
#define TRUE 1
#define FALSE 0
typedef struct
{
Elemtype queue[MAXNUM];
int front;
int rear;
}sqqueue;
/*队列初始化*/
int initQueue(sqqueue *q)
{
if(!q) return FALSE;
q->front=-1;
q->rear=-1;
return TRUE;
}
/*入队*/
int append(sqqueue *q, Elemtype x)
{
if(q->rear>=MAXNUM-1) return FALSE;
q->rear++;
q->queue[q->rear]=x;
return TRUE;
}
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
