用顺序结构表示栈并实现栈的各种基本操作.doc

栈的顺序表示和实现
2.2基础实验
2.2.1实验目的
（1）掌握栈的顺序表示和实现
（2）掌握栈的链式表示和实现
（3）掌握队列的顺序表示和实现
（4）掌握队列的链式表示和实现
2.2.2实验内容
实验一：栈的顺序表示和实现
【实验内容与要求】
编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化顺序栈
（2）插入元素
（3）删除栈顶元素
（4）取栈顶元素
（5）遍历顺序栈
（6）置空顺序栈
【知识要点】
栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top= =MAXNUM-1，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。
出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。
注意：
（1）顺序栈中元素用向量存放
（2）栈底位置是固定不变的，可设置在向量两端的任意一个端点
（3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置
【实现提示】
/*定义顺序栈的存储结构*/
typedef struct {
ElemType stack[MAXNUM];
int top;
}SqStack;
/*初始化顺序栈函数*/
void InitStack(SqStack *p)
{q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/)
/*入栈函数*/
void Push(SqStack *p,ElemType x)
{if(p->toptop=p->top+1; /*栈顶+1*/
p->stack[p->top]=x; } /*数据入栈*/
}
/*出栈函数*/
ElemType Pop(SqStack *p)
{x=p->stack[p->top]; /*将栈顶元素赋给x*/
p->top=p->top-1; } /*栈顶-1*/
/*获取栈顶元素函数*/
ElemType GetTop(SqStack *p)
{ x=p->stack[p->top];}
/*遍历顺序栈函数*/
void OutStack(SqStack *p)
{ for(i=p->top;i>=0;i--)
printf("第%d个数据元素是：%6d\n",i,p->stack[i]);}
/*置空顺序栈函数*/
void setEmpty(SqStack *p)
{ p->top= -1;}
【参考程序】
#include
#include
#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->topNUM-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->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;
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);
}
【思考与提高】
（1）读栈顶元素的算法与退栈顶元素的算法有何区别？
（2）如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？
实验二：栈的链式表示和实现
【实验内容与要求】
编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化链栈
（2）链栈置空
（3）入栈
（4）出栈
（5）取栈顶元素
（6）遍历链栈
【知识要点】
链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。
注意：
（1）LinkStack结构类型的定义可以方便地在函数体中修改top指针本身
（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。
（3）链栈中的结点是动态分配的，所以可以不考虑上溢。
【实现提示】
typedef int Elemtype;
typedef struct stacknode {
Elemtype data;
stacknode * next;
}StackNode;
/*定义链栈*/
typedef struct {
stacknode top; //栈顶指针
}LinkStack;
/*初始化链栈函数*/
void InitStack(LinkStack * s)
{ s=(LinkStack *)malloc(sizeof(LinkStack));/*初始化申请空间*/
s->top=NULL;}
/*链栈置空函数*/
void setEmpty(LinkStack * s)
{ s->top=NULL;}
/*入栈函数*/
void pushLstack(LinkStack * s, Elemtype x)
{ p=(StackNode *)malloc(sizeof(StackNode)); //建立一个节点。
p->data=x;
p->next=s->top; //指向栈顶。
s->top=p; //插入
}
/*出栈函数*/
Elemtype popLstack(LinkStack * s)
{x=p->data;
s->top=p->next; //当前的栈顶指向原栈的next
free(p); //释放
}
/*取栈顶元素函数*/
Elemtype StackTop(LinkStack *s)
{ return s->top->data;}
/*遍历链栈函数*/
void Disp(LinkStack * s)
{while (p!=NULL)
{ printf("%d\n",p->data);
p=p->next;
}
}
【参考程序】
#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;
}
/*取栈顶元素*/
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");
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:
{ InitStack(s);
Disp(s);
}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);
}
【思考与提高】
（1）栈的两种存储结构在判别栈空与栈满时，所依据的条件有何不同？
（2）在程序中同时使用两个以上的栈时，使用顺序栈共享邻接空间则很难实现，能否通过链栈来方便地实现？如何实现？

实验三：队列的顺序表示和实现
【实验内容与要求】
编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化队列
（2）建立顺序队列
（3）入队
（4）出队
（5）判断队列是否为空
（6）取队头元素
（7）遍历队列
【知识要点】
队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
入队时，将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front加1并返回被删元素。
顺序队列中的溢出现象：
（1） "下溢"现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
（2） "真上溢"现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
（3） "假上溢"现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。
注意：
（1）当头尾指针相等时，队列为空。
（2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。
【实现提示】
/*定义队列*/
typedef struct
{ Elemtype queue[MAXNUM];
int front;
int rear;
}sqqueue;
/*队列初始化函数*/
int initQueue(sqqueue *q)
{q=(sqqueue*)malloc(sizeof(sqqueue)); /*初始化申请空间*/
q->front1;
q->rear=-1;
}
/*入队函数*/
int append(sqqueue *q, Elemtype x)
{ q->rear++;
q->queue[q->rear]=x;}
/*出队函数*/
Elemtype Delete(sqqueue *q)
{ x=q->queue[++q->front];}
/*判断队列是否为空函数*/
int Empty(sqqueue *q)
{ if (q->front==q->rear) return TRUE;}
/*取队头元素函数*/
int gethead(sqqueue *q)
{returnq->queue[q->front+1]);}
/*遍历队列函数*/
void display(sqqueue *q)
{ while(srear)
{s=s+1;
printf("%d<-", q->queue[s]); }
}
/*建立顺序队列函数*/
void Setsqqueue(sqqueue *q)
{ for (i=0;i
#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;
}
/*出队*/
Elemtype Delete(sqqueue *q)
{ Elemtype x;
if (q->front==q->rear) return 0;
x=q->queue[q->front];
return x;
}
/*判断队列是否为空*/
int Empty(sqqueue *q)
{ if (q->front==q->rear) return TRUE;
return FALSE;
}
/*取队头元素*/
int gethead(sqqueue *q)
{ if (q->front==q->rear) return 0;
return(q->queue[q->front+1]);
}
/*遍历队列*/
void display(sqqueue *q)
{ int s;
s=q->front;
if (q->front==q->rear)
printf("队列空!\n");
else
{printf("\n顺序队列依次为：");
while(srear)
{s=s+1;
printf("%d<-", q->queue[s]);
}
printf("\n");
printf("顺序队列的队尾元素所在位置:rear=%d\n",q->rear);
printf("顺序队列的队头元素所在位置:front=%d\n",q->front);
}
}
/*建立顺序队列*/
void Setsqqueue(sqqueue *q)
{ int n,i,m;
printf("\n请输入将要入顺序队列的长度:");
scanf("%d",&n);
printf("\n请依次输入入顺序队列的元素值:\n");
for (i=0;i append(q,m);}
}
main()
{ sqqueue *head;
int x,y,z,select;
head=(sqqueue*)malloc(sizeof(sqqueue));
do{printf("\n第一次使用请初始化！\n");
printf("\n请选择操作(1--7):\n");
printf("===================================\n");
printf("1初始化\n");
printf("2建立顺序队列\n");
printf("3入队\n");
printf("4出队 \n");
printf("5判断队列是否为空\n");
printf("6取队头元素 \n");
printf("7遍历队列\n");
printf("===================================\n");
scanf("%d",&select);
switch(select)
{case 1:
{ initQueue(head);
printf("已经初始化顺序队列！\n");
break;
}
case 2:
{ Setsqqueue(head);
printf("\n已经建立队列！\n");
display(head);
break;
}
case 3:
{ printf("请输入队的值:\n ");
scanf("%d",&x);
append(head,x);
display(head);
break;
}
case 4:
{ z=Delete(head);
printf("\n队头元素%d已经出队！\n",z);
display(head);
break;
}
case 5:
{ if(Empty(head))
printf("队列空\n");
else
printf("队列非空\n");
break;
}
case 6:
{ y=gethead(head);
printf("队头元素为:%d\n",y);
break;
}
case 7:
{ display(head);
break;
}
}
}while(select<=7);
}