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

1、实用文案栈的顺序表示和实现2.2基础实验2.2.1实验目的(1)掌握栈的顺序表示和实现(2)掌握栈的链式表示和实现(3)掌握队列的顺序表示和实现(4)掌握队列的链式表示和实现2.2.2实验内容实验一：栈的顺序表示和实现【实验内容与要求】编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：(1)初始化顺序栈(2)插入元素(3)删除栈顶元素(4)取栈顶元素(5)遍历顺序栈(6)置空顺序栈【知识要点】栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top= =MAXNUM-1栈满时，不能入栈否则出现空间

2、溢出，引起错误，这种现象称为上溢。出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转 移的条件。注意：(1)顺序栈中元素用向量存放(2)栈底位置是固定不变的，可设置在向量两端的任意一个端点(3)栈顶位置是随着进栈和退栈操彳而变化的，用一个整型量top (通常称top为栈顶指针)来指示当前栈顶位置【实现提示】/*定义顺序栈的存储结构*/typedef struct ElemType stackMAXNUM;标准文档实用文案int top;SqStack;/*初始化顺序栈函数*/void InitStack(SqStack *p)q=(SqStack*)ma

3、lloc(sizeof(SqStack)/*申请空间 */)/*入栈函数*/void Push(SqStack *p,ElemType x)if(p->top<MAXNUM-1)p->top=p->top+1; /* 栈顶+1*/ p->stackp->top=x; /*数据入栈 */*出栈函数*/ElemType Pop(SqStack *p)x=p->stackp->top; /* 将栈顶元素赋给 x*/p->top=p->top-1; /* 栈顶-1*/*获取栈顶元素函数*/ElemType GetTop(SqStack *p)

4、 x=p->stackp->top;/*遍历顺序栈函数*/void OutStack(SqStack *p) for(i=p->top;i>=0;i-)printf("第d 个数据元素是：%6dn",i,p->stacki);/*置空顺序栈函数*/void setEmpty(SqStack *p) p->top= -1;【参考程序】#include<stdio.h>#include<stdlib.h>#define MAXNUM 20#define ElemType int/*定义顺序栈的存储结构*/typedef

5、 struct ElemType stackMAXNUM;int top;SqStack;/*初始化顺序栈*/void InitStack(SqStack *p) if(!p)printf("Eorror");p->top=-1;/*入栈*/标准文档实用文案void Push(SqStack *p,ElemType x) if(p->top<MAXNUM-1) p->top=p->top+1;p->stackp->top=x;elseprintf("Overflow!n");/*出栈*/ElemType Pop(

6、SqStack *p) ElemType x;if(p->top!=0) x=p->stackp->top;printf("以前的栈顶数据元素d已经被删除！n",p->stackp->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->stackp->top;return(x);

7、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 个数据元素是：6dn",i,p->stacki);标准文档实用文案/*置空顺序栈*/void setEmpty(SqStack *p)p-&g

8、t;top= -1;/*主函数*/main() SqStack *q;int y,cord;ElemType a;doprintf("n");printf("第一次使用必须初始化！n");printf("n");printf("n主菜单n");printf("n1初始化顺序栈n"printf("n2插入一个元素n"printf("n3删除栈顶元素n"printf("n4取栈顶元素n");printf("n5置空顺序栈n&quo

9、t;);printf("n6结束程序运行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&q

10、uot;,&a);Push(q,a);OutStack(q);break;case 3: Pop(q);OutStack(q);break;case 4: y=GetTop(q);printf("n栈顶元素为：%dn",y);OutStack(q);标准文档实用文案break;case 5:顺序栈被置空！ n"); setEmpty(q);printf("nOutStack(q);break;case 6:exit(0);while (cord<=6);【思考与提高】(1)读栈顶元素的算法与退栈顶元素的算法有何区别？(2)如果一个程序中要用

11、到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存 储空间。若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？实验二：栈的链式表示和实现【实验内容与要求】编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：(1)初始化链栈(2)链栈置空(3)入栈(4)出栈(5)取栈顶元素(6)遍历链栈【知识要点】链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。注意：11) LinkStack结构类型的定义可以方便地在函数体中修改top指针本身(2)若要记录栈中元素个数，可将元素个数属性放在 LinkStack类型中定义。(3)

12、链栈中的结点是动态分配的，所以可以不考虑上溢。【实现提示】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 setEmpt

13、y(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; /当前的栈顶指向原栈的free(p); /释放初始化申请空间*/建立一个节点。n

14、ext/*取栈顶元素函数*/Elemtype StackTop(LinkStack *s) return s->top->data;/*遍历链栈函数*/void Disp(LinkStack * s)while (p!=NULL) printf("%dn",p->data);p=p->next;#include "stdio.h"#include "malloc.h"#include "stdlib.h"typedef int Elemtype;typedef struct stacknod

15、e 标准文档实用文案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 *

16、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);

17、x=p->data;s->top=p->next; /当前的栈顶指向原栈的nextfree(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 *

18、p;p=s->top;while (p!=NULL) printf("%dn",p->data);p=p->next;)printf("=n");)void main() printf("=链栈操作=nn");int i,m,n,a;LinkStack * s;s=(LinkStack *)malloc(sizeof(LinkStack);int cord;do printf("n");printf("第一次使用必须初始化！n");printf("n");p

19、rintf("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("nn");printf("请输入您的选择(1,2, 3, 4, 5,6)");scanf("%d",&cord)

20、;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&qu

21、ot;);printf("输入将要出栈的数据个数：m=");scanf("%d",&m);for(i=1;i<=m;i+)printf("n第d 次出栈的数据是：%d",i,popLstack(s);Disp(s)；break;case 4: printf("nn链栈的栈顶元素为：dn",StackTop(s);printf("n");break;case 5: setEmpty(s);Disp(s);break;case 6:exit(0);while (cord<=6);

22、【思考与提高】(1)栈的两种存储结构在判别栈空与栈满时，所依据的条件有何不同？(2)在程序中同时使用两个以上的栈时，使用顺序栈共享邻接空间则很难实现，能否通过链栈来方便 地实现？如何实现？实验三：队列的顺序表示和实现【实验内容与要求】编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能:(1)初始化队列(2)建立顺序队列(3)入队(4)出队(5)判断队列是否为空标准文档实用文案(6)取队头元素(7)遍历队列【知识要点】队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。入队时，将新元素插入rear所指的位置，然后将 rear加1。出队时，删去front

23、所指的元素，然后将front力口 1并返回被删元素。顺序队列中的溢出现象：(1)"下溢"现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。(2)"真上溢"现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。(3)"假上溢"现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法 重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界 而不能做入队操作。该现象称为"假上溢"现象。注意

24、：(1)当头尾指针相等时，队列为空。(2)在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。【实现提示】/*定义队列*/typedef struct Elemtype queueMAXNUM;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->rea

25、r+;q->queueq->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)return(q->queueq->front+1);/*遍历队列函数*/void display(sqqueue *q) while(s<q->rear)s=s

26、+1;printf("%d<-", q->queues); /*建立顺序队列函数*/void Setsqqueue(sqqueue *q) for (i=0;i<n;i+)/*利用循环快速输入数据*/ scanf("%d",&m);append(q,m); /*利用入队函数快速输入数据 */【参考程序】#include <stdio.h>#include <malloc.h>#define MAXNUM 100#define Elemtype int#define TRUE 1#define FALSE

27、0typedef struct Elemtype queueMAXNUM;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->queueq->rear=x;return TRUE;/*出队*/Elem

28、type 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->queueq->fron

29、t+1);/*遍历队列*/void display(sqqueue *q) int s;s=q->front;if (q->front=q->rear)printf("队列空！n");elseprintf("n顺序队列依次为：")；while(s<q->rear)s=s+1;printf("%d<-", q->queues);printf("n");printf("顺序队列的队尾元素所在位置:rear=%dn",q->rear);printf("顺序队列的队头元素所在位置:front=%dn",q->front);/*建立顺序队列*/void Setsqqueue(sqqueue *q) int n,i,m;printf("n 请输入将要入顺序队列的长度：")；scanf("%d",&n);printf("n请依次输入入顺序队列的元素值：n");for (i=0;i<n;i+) scanf("%d