实验二栈、队列的实现及应用

1、实验二 栈、队列的实现及应用实验课程名：数据结构与算法专业班级： 学号： 姓名： 实验时间： 实验地点： 指导教师： 冯珊 一、实验目的1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。2、掌握栈和队列的特点，即先进后出与先进先出的原则。3、掌握栈和队列的基本操作实现方法。二、实验内容一、实验目的及要求1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。2、掌握栈和队列的特点，即先进后出与先进先出的原则。3、掌握栈和队列的基本操作实现方法。二、实验学时2学时三、实验任务任务一：（1）实现栈的顺序存储（2）实现栈的链式存储。任务二：实现顺序存储的循环队列

2、，完成键盘缓冲区的功能。四、实验重点、难点1. 进栈、出栈栈顶指针都要改变。2. 队空、队满的条件及入队、出队时指针的变更。五、操作内容与要求1.任务一（1）：完成下列程序，该程序实现栈的顺序存储结构，构建顺序栈（栈中的元素依次为R，S，Y，F，C，T），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。要求生成顺序栈时，从键盘上读取数据元素。（1）源代码：#include<stdio.h>#include<stdlib.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10# define OK 1#

3、define ERROR 0typedef char SElemType;/* 顺序栈的存储类型 */typedef struct/define structure SqStack()SElemType *base;SElemType *top;int stacksize;SqStack;/*构造空顺序栈*/int InitStack(SqStack *S)/InitStack() sub-functionS->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if (!S->base)printf("

4、;分配空间失败!n");return (ERROR);S->top = S->base;S->stacksize = STACK_INIT_SIZE;printf("栈初始化成功！n");return (OK); /InitStack() end/*取顺序栈顶元素*/int GetTop(SqStack *S, SElemType *e)/GetTop() sub-functionif (S->top = S->base)printf("栈为空!n");/if empty SqStackreturn (ERROR)

5、;*e = *(S->top - 1);return (OK); /GetTop() end/*将元素压入顺序栈*/int Push(SqStack *S)/Push() sub-functionSElemType e;if (S->top - S->base>S->stacksize)S->base = (SElemType *)realloc(S->base, (S->stacksize +STACKINCREMENT*sizeof(SElemType);if (!S->base)printf("存储空间分配失败!n"

6、;);return (ERROR);S->top = S->base + S->stacksize;S->stacksize += STACKINCREMENT;fflush(stdin);/清除输入缓冲区，否则原来的输入会默认送给变量xprintf("请输入要入栈的元素的值:");e = getchar();*S->top+ = e;return (OK); /Push() end/* 将元素弹出顺序栈*/int Pop(SqStack *S, SElemType *e)/Pop() sub-functionif (S->top = S

7、->base)printf("栈为空!n");return (ERROR);*e = *-S->top;return (OK); /Pop() endvoid display(SqStack *s)if (s->top = s->base)printf("栈为空!n");elsewhile (s->top != s->base)s->top = s->top - 1;printf("%c->", *(s->top);printf("n");int main

8、()int choice;SElemType e;SqStack s;doprintf("=n");printf(" 0:退出n");printf(" 1:初始化栈n");printf(" 2:入栈n");printf(" 3:出栈n");printf(" 4:读取栈顶元素n");printf(" 5:显示栈中元素n");printf("=n");printf("输入操作选择代码(0-5):");scanf(&quo

9、t;%d", &choice);while (choice<0 | choice>5) printf("输入有误，请重新输入(0-5):"); scanf("%d", &choice); switch (choice)case 0:exit(1);case 1:InitStack(&s); break;case 2:printf("2n"); Push(&s); break;case 3:Pop(&s, &e); printf("出栈元素的值是:%cn&q

10、uot;, e); break;case 4:GetTop(&s, &e); printf("栈顶元素的值是:%cn", e); break;case 5: printf("栈中元素的值是为：n"); display(&s); break; while (choice);return 0;（2）运行结果（3） 结果分析 顺序表通过设置栈顶运用线性结构实现先进先出功能。2.任务一（2）：完成下列程序，该程序实现栈的链式存储结构，构建链栈（栈中的元素依次为China，Japan，France，India，Australia），依次进行

11、进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。要求生成链栈时，从键盘上读取数据元素。（1）源代码：#include<stdio.h>#include<stdlib.h>#include<string.h># define OK 1# define ERROR 0typedef char DataType;/* 链式栈的存储类型 */typedef struct SNode /define structure LinkStack DataType data20; struct SNode *next;SNode,*LinkStack; void Ini

12、tStack_L (LinkStack *top)top = (LinkStack)malloc(sizeof(SNode) ; top->next = NULL;printf("nn栈初始化成功！nn"); /*取链式栈顶元素*/int GetTop_L(LinkStack *top,DataType e) /GetTop_L() sub-function if(!top->next) printf("链栈为空!n"); return (ERROR); else strcpy(e,top->next->data); return

13、 (OK); /GetTop_L() end /* 将元素压入链式栈*/int Push_L(LinkStack *top) /Push_L() sub-function SNode *q;DataType e20; q=(LinkStack)malloc(sizeof(SNode); if(!q) printf("存储空间分配失败! n"); return (ERROR); fflush(stdin);/清除输入缓冲区，否则原来的输入会默认送给变量eprintf("n请输入要入栈的元素的值:");gets(e);strcpy(q->data,e)

14、; q->next=top->next; top->next=q; return (OK); /Push_L() end /*将元素弹出链式栈*/int Pop_L(LinkStack *top,DataType e) /Pop_L() sub-function SNode *q; if(!top->next) printf("链栈为空! n "); return (ERROR); strcpy(e,top->next->data); q=top->next; top->next=q->next; free(q); re

15、turn (OK); /Pop_L() end void display(LinkStack *top) LinkStack p=top->next; if(!p) printf("栈为空!n"); elsewhile(p) printf("%s->",p->data); p=p->next; printf("n"); int main()char choice;DataType e20=""LinkStack s=NULL;do printf("=n"); printf

16、(" 0:退出n"); printf(" 1:初始化栈n"); printf(" 2:入栈n"); printf(" 3:出栈n"); printf(" 4:读取栈顶元素n"); printf(" 5:显示栈中元素n"); printf("=n"); printf("输入操作选择代码(0-5):"); fflush(stdin); scanf("%c",&choice); while(choice<&#

17、39;0'|choice>'5') printf("输入有误，请重新输入(0-5):"); fflush(stdin); scanf("%c",&choice); switch(choice) case '0':exit(1); case '1': InitStack_L(&s);break; case '2': Push_L(&s);break; case '3':Pop_L(&s, e);break; case '4&

18、#39;:GetTop_L(&s, e);printf("栈顶元素的值是:%sn",e);break; case '5': printf("栈中元素的值是: ");display(&s); while(choice);return 0;（2） 运行结果 （3） 结果分析 链表通过设置栈顶运用指针实现先进先出功能3.任务二：完成下列程序，该程序实现循环队列的存储和基本操作，构建循环队列，完成键盘缓冲区的功能，每输入一个字符，链入缓冲区队列中；每输出一个字符，将该字符从缓冲区中删除。（1）源代码：#include<std

19、io.h>#include<stdlib.h># define MAXQSIZE 100# define OK 1# define ERROR 0 /* 定义QElemType为int或别的自定义类型 */typedef char QElemType; /* 顺序队列的存储类型 */typedef struct SqQueue /define structure SqQueue QElemType *base; int front; int rear;SqQueue; /* 构造空顺序队列*/int InitQueue(SqQueue *Q) /InitQueue() sub

20、-function Q->base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType); if(!Q->base) printf("分配空间失败! n"); return (ERROR); Q->front=Q->rear=0;printf("队列初始化成功! n"); return (OK); /InitQueue() end /* 求顺序队列长度*/int QueueLength(SqQueue *Q) /QueueLength() sub-function return (Q->

21、;rear-Q->front+MAXQSIZE)%MAXQSIZE); /*在顺序队列尾插入新元素*/int EnQueue(SqQueue *Q,QElemType e) /EnQueue() sub-function if(Q->rear+1)%MAXQSIZE=Q->front) printf("队列已满! n");return (ERROR); Q->baseQ->rear=e;Q->rear=(Q->rear+1)%MAXQSIZE; return (OK); /EnQueue() end /*在顺序队列头删除旧元素*/i

22、nt DeQueue(SqQueue *Q,QElemType e) /DeQueue() sub-function if(Q->front=Q->rear) printf("队列为空!n"); return (ERROR); e=Q->baseQ->front; Q->front=(Q->front+1)%MAXQSIZE; return (OK); /DeQueue() end void display(SqQueue *Q)if(Q->front=Q->rear) printf("队列为空!n");int i=Q->front;while(i+1)%MAXQSIZE!=Q-