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

栈的顺序表示和实现

基础实验

实验目的

（1）掌握栈的顺序表示和实现 （2）掌握栈的链式表示和实现 （3）掌握队列的顺序表示和实现 （4）掌握队列的链式表示和实现

实验内容

实验一：栈的顺序表示和实现

【实验内容与要求】

编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能： （1）初始化顺序栈 （2）插入元素 （3）删除栈顶元素 （4）取栈顶元素 （5）遍历顺序栈 （6）置空顺序栈

【知识要点】

栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。

对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top= =MAXNUM-1，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。

出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。

注意：

（1）顺序栈中元素用向量存放

（2）栈底位置是固定不变的，可设置在向量两端的任意一个端点

（3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置

【实现提示】

/*定义顺序栈的存储结构*/ typedef struct {

ElemType stack[MAXNUM];

1

-

int top; }SqStack;

/*初始化顺序栈函数*/ void InitStack(SqStack *p)

{q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/) /*入栈函数*/

void Push(SqStack *p,ElemType x) {if(p->top{p->top=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\ /*置空顺序栈函数*/ 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; } /*入栈*/

2

-

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->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\ }

3

-

/*置空顺序栈*/

void setEmpty(SqStack *p) {

p->top= -1; }

/*主函数*/ main() { SqStack *q;

int y,cord;ElemType a; 4

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\ printf(\"\\n\"); switch(cord) { case 1:

{ q=(SqStack*)malloc(sizeof(SqStack)); InitStack(q); OutStack(q); }break; case 2:

{ printf(\"请输入要插入的数据元素：a=\"); scanf(\"%d\ Push(q,a); OutStack(q); }break; case 3:

{ Pop(q); OutStack(q); }break; case 4:

{ y=GetTop(q);

printf(\"\\n栈顶元素为：%d\\n\ 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;

5

-

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=p->next; } }

【参考程序】

#include \"\" #include \"\" #include \"\"

typedef int Elemtype; typedef struct stacknode {

6

-

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); }

7

-

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=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\ printf(\"\\n\"); switch(cord) { case 1:

{ InitStack(s); Disp(s); }break; case 2:

{printf(\"输入将要压入链栈的数据的个数：n=\"); scanf(\"%d\

printf(\"依次将%d个数据压入链栈：\\n\ for(i=1;i<=n;i++)

8

-

{scanf(\"%d\ pushLstack(s,a); } Disp(s); }break; case 3:

{ printf(\"\\n出栈操作开始!\\n\");

printf(\"输入将要出栈的数据个数：m=\"); scanf(\"%d\ for(i=1;i<=m;i++)

{printf(\"\\n第%d次出栈的数据是：%d\ Disp(s); }break; case 4:

{ printf(\"\\n\\n链栈的栈顶元素为：%d\\n\ printf(\"\\n\"); }break; case 5:

{ setEmpty(s); Disp(s); }break; case 6: exit(0); } }while (cord<=6); }

【思考与提高】

（1）栈的两种存储结构在判别栈空与栈满时，所依据的条件有何不同？

（2）在程序中同时使用两个以上的栈时，使用顺序栈共享邻接空间则很难实现，能否通过链栈来方便地实现？如何实现？

实验三：队列的顺序表示和实现

【实验内容与要求】

编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能： （1）初始化队列 （2）建立顺序队列 （3）入队 （4）出队

9

-

（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->front=-1; 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)

10

-

{ if (q->front==q->rear) return TRUE;} /*取队头元素函数*/ int gethead(sqqueue *q) {return(q->queue[q->front+1]);} /*遍历队列函数*/ void display(sqqueue *q) { while(srear) {s=s+1;

printf(\"%d<-\ }

/*建立顺序队列函数*/ void Setsqqueue(sqqueue *q)

{ for (i=0;iappend(q,m);} } /*利用入队函数快速输入数据*/

【参考程序】

#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; } /*出队*/

11

-

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<-\ } printf(\"\\n\");

printf(\"顺序队列的队尾元素所在位置:rear=%d\\n\ printf(\"顺序队列的队头元素所在位置:front=%d\\n\ } }

/*建立顺序队列*/

void Setsqqueue(sqqueue *q) { int n,i,m;

printf(\"\\n请输入将要入顺序队列的长度:\"); scanf(\"%d\

printf(\"\\n请依次输入入顺序队列的元素值:\\n\"); for (i=0;i12

-

{ 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\"); 13

printf(\"4出队 \\n\");

printf(\"5判断队列是否为空\\n\"); printf(\"6取队头元素 \\n\"); printf(\"7遍历队列\\n\");

printf(\"===================================\\n\"); scanf(\"%d\ 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\ append(head,x); display(head); break; } case 4:

{ z=Delete(head);

printf(\"\\n队头元素%d已经出队！\\n\ display(head); break; } case 5:

{ if(Empty(head)) printf(\"队列空\\n\"); else

-

printf(\"队列非空\\n\"); break; } case 6:

{ y=gethead(head);

printf(\"队头元素为:%d\\n\ break; } case 7:

14

{ display(head); break; } }

}while(select<=7); }