数据结构栈和队列

1、实验二 栈和队列一、实验目的1. 掌握栈的顺序表示和实现2. 掌握队列的链式表示和实现二、实验内容1. 编写一个程序实现顺序栈的各种基本运算。2. 实现队列的链式表示和实现。三、实验步骤1. 初始化顺序栈2. 插入元素3. 删除栈顶元素4. 取栈顶元素5. 遍历顺序栈6. 置空顺序栈7. 初始化并建立链队列8. 入链队列9. 出链队列10. 遍历链队列四、实现提示1. /*定义顺序栈的存储结构*/typedef struct      ElemType stackMAXNUM;     int top;SqStac

2、k; /*初始化顺序栈函数*/void InitStack(SqStack *p) q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/)/*入栈函数*/void Push(SqStack *p,ElemType x) if(p->top<MAXNUM-1)     p->top=p->top+1;     /*栈顶+1*/      p->stackp->top=x;   /*数据入栈

3、*/*出栈函数*/ElemType Pop(SqStack *p)x=p->stackp->top; /*将栈顶元素赋给x*/p->top=p->top-1; /*栈顶-1*/*获取栈顶元素函数*/ElemType GetTop(SqStack *p) x=p->stackp->top;/*遍历顺序栈函数*/void OutStack(SqStack *p) for(i=p->top;i>=0;i-)printf("第%d个数据元素是：%6dn",i,p->stacki);/*置空顺序栈函数*/void setEmpty

4、(SqStack *p) p->top= -1;2. /*定义链队列*/typedef struct Qnode   ElemType data;     struct Qnode *next;Qnodetype;typedef struct   Qnodetype *front;     Qnodetype *rear;Lqueue; /*初始化并建立链队列函数*/void creat(Lqueue *q)    h=(Qnodetype*)mal

5、loc(sizeof(Qnodetype); /*初始化申请空间*/     h->next=NULL;     q->front=h;     q->rear=h;for(i=1;i<=n;i+)*利用循环快速输入数据*/          scanf("%d",&x);      &

6、#160;     Lappend(q,x);   /*利用入链队列函数快速输入数据*/*入链队列函数*/void Lappend(Lqueue *q,int x) s->data=x;     s->next=NULL;     q->rear->next=s;     q->rear=s;/*出链队列函数*/ElemType Ldelete(Lqueue *q) p=q->fr

7、ont->next;     q->front->next=p->next;     if(p->next=NULL)     q->rear=q->front;     x=p->data;     free(p); /*释放空间*/*遍历链队列函数*/void display(Lqueue *q) while(p!=NULL)  /*利

8、用条件判断是否到队尾*/          printf("%d->",p->data);            p=p->next;     五、思考与提高1. 读栈顶元素的算法与退栈顶元素的算法有何区别？2. 如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。若每个栈都预分配过大的存储

9、空间，势必会造成系统空间紧张。如何解决这个问题？（1）链栈只有一个top指针，对于链队列，为什么要设计一个头指针和一个尾指针？（2）一个程序中如果要用到两个栈时，可通过两个栈共享一维数组来实现。即双向栈共享邻接空间。如果一个程序中要用到两个队列，能否实现？如何实现？六、完整参考程序 1. 栈的顺序表示和实现#include <stdio.h>#include <stdlib.h>#include <conio.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBL

10、E -1#define OVERFLOW -2typedef int Status;typedef int SElemType;/- 栈的顺序存储表示 -#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;Status InitStack(SqStack &S);Status DestroyStack(SqStack &S);Status StackDisplay(SqStack &am

11、p;S);Status GetTop(SqStack S,SElemType &e);Status Push(SqStack &S,SElemType e);Status Pop(SqStack &S,SElemType &e);Status StackEmpty(SqStack S);Status InitStack(SqStack &S)/构造一个空栈SS.base = (SElemType *) malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) exit(OVERFLOW); /存储分配失效S

12、.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;/InitStackStatus DestroyStack(SqStack &S)/销毁栈Sif(S.base) free(S.base);S.top = S.base = NULL;return OK;/InitStackStatus StackDisplay(SqStack &S)/显示栈SSElemType * p=S.base;int i = 0;if(S.base = S.top) printf("堆栈已空!n"); return OK;wh

13、ile( p < S.top)printf("%d:%d",+i,*p+);printf("n");return OK;/StackDisplayStatus GetTop(SqStack S,SElemType &e) /若栈不空，则用e返回S的栈顶元素，/并返回OK；否则返回ERRORif(S.top=S.base) return ERROR;e=*(S.top-1);return OK;/GetTopStatus Push(SqStack &S,SElemType e)/插入元素e为新的栈顶元素if(S.top-S.base&

14、gt;=S.stacksize)/栈满，追加存储空间S.base=(SElemType*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if( ! S.base ) exit(OVERFLOW);/存储分配失败S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;* S.top + = e;return OK;/PushStatus Pop(SqStack &S,SElemType &e)/若栈不为空，则删除S的栈顶元素，/用e返回其值

15、，并返回OK；否则返回ERROR if (S.top = S.base) return ERROR; e = * -S.top; return OK;/PopStatus StackEmpty(SqStack S)/若S为空栈，则返回TRUE，否则返回FALSE。if(S.top = S.base) return TRUE;else return FALSE;/ StackEmptyvoid main()SqStack St;Status temp;int flag=1,ch;int e;printf("本程序实现顺序结构的堆栈的操作。n");printf("可以

16、进行入栈，出栈，取栈顶元素等操作。n");InitStack(St); /初始化堆栈Stwhile(flag)printf("请选择:n");printf("1.显示栈中所有元素 n");printf("2.入栈 n");printf("3.出栈 n");printf("4.取栈顶元素 n");printf("5.退出程序 n");scanf("%d",&ch);switch(ch)case 1:StackDisplay(St);brea

17、k;case 2:printf("请输入要入栈的元素(一个整数):");scanf("%d",&e); /输入要入栈的元素temp=Push(St,e); /入栈if(temp!=OK) printf("堆栈已满!入栈失败!n");else printf("成功入栈!n"); /成功入栈StackDisplay(St);break;case 3:temp=Pop(St,e); /出栈if(temp=ERROR) printf("堆栈已空!n"); else printf("成功

18、出栈一个元素:%dn",e); /成功出栈StackDisplay(St);break;case 4:temp=GetTop(St,e); /取得栈顶元素if(temp=ERROR) printf("堆栈已空!n");else printf("栈顶元素是:%dn",e); /显示栈顶元素break;default:flag=0;printf("程序结束，按任意键退出!n");getch();DestroyStack(St);2. 队列的链式表示和实现#include <conio.h>#include <s

19、tdio.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/Status 是函数的类型,其值是函数结果状态代码typedef int Status;/ElemType 是顺序表数据元素类型,此程序定义为int型typedef int QElemType;/-单链队列-队列的链式存储结构-typedef struct QNode /定义结点结构QElemType data; /数据域struct

20、 QNode *next; /指针域QNode,*QueuePtr;typedef struct linkqueue /定义队列结构QueuePtr front; /队头指针QueuePtr rear; /队尾指针LinkQueue;Status InitLinkQueue(LinkQueue &); /初始化一个队列Status DestroyLinkQueue(LinkQueue &); /销毁一个队列int LinkQueueLength(LinkQueue &Q); /队列的长度Status EnLinkQueue(LinkQueue &,QElemTy

21、pe); /将一个元素入队列Status DeLinkQueue(LinkQueue &,QElemType &);/将一个元素出队列Status DisplayLinkQueue(LinkQueue); /显示队列中所有元素void main()LinkQueue LQ;QElemType e;int flag=1,ch,len;Status temp;printf("本程序实现链式结构队列的操作。n");printf("可以进行入队列、出队列等操作。n");InitLinkQueue(LQ); /初始化队列while(flag)pri

22、ntf("请选择:n");printf("1.显示队列所有元素n");printf("2.入队列n");printf("3.出队列n");printf("4.求队列的长度n");printf("5.退出程序n");scanf("%d",&ch);switch(ch)case 1:DisplayLinkQueue(LQ); /显示队列中所有元素break;case 2:printf("请输入要人队的元素(一个整数):");scan

23、f("%d",&e); /输入要入队列的字符EnLinkQueue(LQ,e);/入队列DisplayLinkQueue(LQ);break;case 3:temp=DeLinkQueue(LQ,e); /出队列if(temp=OK)printf("出队一个元素:%dn",e);DisplayLinkQueue(LQ);else printf("队列为空!n");break;case 4:len=LinkQueueLength(LQ);printf("队列的长度为:%dn",len);break;defau

24、lt:flag=0;printf("程序运行结束，按任意键退出!n");getch();Status InitLinkQueue(LinkQueue &Q)/队列初始化Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode); /生成一个头结点，并把首尾指针指向头结点Q.front->next=NULL;return OK;Status DestroyLinkQueue(LinkQueue &Q)/销毁一个队列QueuePtr p;QElemType e;while(Q.front!=Q.rear)DeLinkQueue(Q,e);free(Q.front);Q.front=Q.rear=NULL;return OK;int LinkQ