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

./实验二栈、队列的实现及应用实验课程名：数据结构与算法专业班级：学号：姓名：实验时间：实验地点：指导教师：冯珊一、实验目的1、掌握栈和队列的顺序存储结构和链式存储结构,以便在实际背景下灵活运用。2、掌握栈和队列的特点,即先进后出与先进先出的原则。3、掌握栈和队列的基本操作实现方法。二、实验内容一、实验目的及要求1、掌握栈和队列的顺序存储结构和链式存储结构,以便在实际背景下灵活运用。2、掌握栈和队列的特点,即先进后出与先进先出的原则。3、掌握栈和队列的基本操作实现方法。二、实验学时2学时三、实验任务任务一：〔1实现栈的顺序存储〔2实现栈的链式存储。任务二：实现顺序存储的循环队列,完成键盘缓冲区的功能。四、实验重点、难点进栈、出栈栈顶指针都要改变。队空、队满的条件及入队、出队时指针的变更。五、操作内容与要求1.任务一〔1：完成下列程序,该程序实现栈的顺序存储结构,构建顺序栈〔栈中的元素依次为R,S,Y,F,C,T,依次进行进栈和出栈操作,判断栈空和栈满操作,返回栈顶元素操作。要求生成顺序栈时,从键盘上读取数据元素。〔1源代码：#include<stdio.h>#include<stdlib.h>#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOK1#defineERROR0typedefcharSElemType;/*顺序栈的存储类型*/typedefstruct//definestructureSqStack<>{SElemType*base;SElemType*top;intstacksize;}SqStack;/*构造空顺序栈*/intInitStack<SqStack*S> //InitStack<>sub-function{S->base=<SElemType*>malloc<STACK_INIT_SIZE*sizeof<SElemType>>;if<!S->base> { printf<"分配空间失败!\n">;return<ERROR>; }S->top=S->base;S->stacksize=STACK_INIT_SIZE; printf<"栈初始化成功！\n">;return<OK>;}//InitStack<>end/*取顺序栈顶元素*/intGetTop<SqStack*S,SElemType*e> //GetTop<>sub-function{if<S->top==S->base> { printf<"栈为空!\n">; //ifemptySqStackreturn<ERROR>; } *e=*<S->top-1>;return<OK>;}//GetTop<>end/*将元素压入顺序栈*/intPush<SqStack*S> //Push<>sub-function{SElemTypee;if<S->top-S->base>S->stacksize> {S->base=<SElemType*>realloc<S->base,<S->stacksize+STACKINCREMENT*sizeof<SElemType>>>;if<!S->base> { printf<"存储空间分配失败!\n">;return<ERROR>; }S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT; } fflush<stdin>;//清除输入缓冲区,否则原来的输入会默认送给变量x printf<"请输入要入栈的元素的值:">; e=getchar<>; *S->top++=e;return<OK>;}//Push<>end/*将元素弹出顺序栈*/intPop<SqStack*S,SElemType*e> //Pop<>sub-function{if<S->top==S->base> { printf<"栈为空!\n">;return<ERROR>; } *e=*--S->top;return<OK>;}//Pop<>endvoiddisplay<SqStack*s>{if<s->top==s->base> printf<"栈为空!\n">;else{while<s->top!=s->base> {s->top=s->top-1; printf<"%c->",*<s->top>>; } } printf<"\n">;}intmain<>{intchoice;SElemTypee;SqStacks;do { printf<"===============================\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<"%d",&choice>;while<choice<0||choice>5>{printf<"输入有误,请重新输入<0-5>:">;scanf<"%d",&choice>;}switch<choice> {case0:exit<1>;case1:InitStack<&s>;break;case2:printf<"2\n">;Push<&s>;break;case3:Pop<&s,&e>;printf<"出栈元素的值是:%c\n",e>;break;case4:GetTop<&s,&e>;printf<"栈顶元素的值是:%c\n",e>;break;case5:printf<"栈中元素的值是为：\n">;display<&s>;break; } }while<choice>;return0;}〔2运行结果结果分析顺序表通过设置栈顶运用线性结构实现先进先出功能。2.任务一〔2：完成下列程序,该程序实现栈的链式存储结构,构建链栈〔栈中的元素依次为China,Japan,France,India,Australia,依次进行进栈和出栈操作,判断栈空和栈满操作,返回栈顶元素操作。要求生成链栈时,从键盘上读取数据元素。〔1源代码：#include<stdio.h>#include<stdlib.h>#include<string.h>#defineOK1#defineERROR0typedefcharDataType;/*链式栈的存储类型*/typedefstructSNode//definestructureLinkStack{DataTypedata[20];structSNode*next;}SNode,*LinkStack;voidInitStack_L<LinkStack*top>{top=<LinkStack>malloc<sizeof<SNode>>;top->next=NULL;printf<"\n\n栈初始化成功！\n\n">;}/*取链式栈顶元素*/intGetTop_L<LinkStack*top,DataTypee[]>//GetTop_L<>sub-function{if<!top->next>{printf<"链栈为空!\n">;return<ERROR>;}else{strcpy<e,top->next->data>;return<OK>;}}//GetTop_L<>end/*将元素压入链式栈*/intPush_L<LinkStack*top>//Push_L<>sub-function{SNode*q;DataTypee[20];q=<LinkStack>malloc<sizeof<SNode>>;if<!q>{printf<"存储空间分配失败!\n">;return<ERROR>;}fflush<stdin>;//清除输入缓冲区,否则原来的输入会默认送给变量eprintf<"\n请输入要入栈的元素的值:">;gets<e>;strcpy<q->data,e>;q->next=top->next;top->next=q;return<OK>;}//Push_L<>end/*将元素弹出链式栈*/intPop_L<LinkStack*top,DataTypee[]>//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>;return<OK>;}//Pop_L<>endvoiddisplay<LinkStack*top>{LinkStackp=top->next;if<!p>printf<"栈为空!\n">;else{while<p>{printf<"%s->",p->data>;p=p->next;}}printf<"^\n">;}intmain<>{charchoice;DataTypee[20]="";LinkStacks=NULL;do{printf<"===============================\n">;printf<"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<'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':GetTop_L<&s,e>;printf<"栈顶元素的值是:%s\n",e>;break;case'5':printf<"栈中元素的值是:">;display<&s>;}}while<choice>;return0;}运行结果结果分析链表通过设置栈顶运用指针实现先进先出功能3.任务二：完成下列程序,该程序实现循环队列的存储和基本操作,构建循环队列,完成键盘缓冲区的功能,每输入一个字符,链入缓冲区队列中；每输出一个字符,将该字符从缓冲区中删除。〔1源代码：#include<stdio.h>#include<stdlib.h>#defineMAXQSIZE100#defineOK1#defineERROR0/*定义QElemType为int或别的自定义类型*/typedefcharQElemType;/*顺序队列的存储类型*/typedefstructSqQueue//definestructureSqQueue{QElemType*base;intfront;intrear;}SqQueue;/*构造空顺序队列*/intInitQueue<SqQueue*Q>//InitQueue<>sub-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/*求顺序队列长度*/intQueueLength<SqQueue*Q>//QueueLength<>sub-function{return<<Q->rear-Q->front+MAXQSIZE>%MAXQSIZE>;}/*在顺序队列尾插入新元素*/intEnQueue<SqQueue*Q,QElemTypee>//EnQueue<>sub-function{if<<Q->rear+1>%MAXQSIZE==Q->front>{printf<"队列已满!\n">;return<ERROR>;}Q->base[Q->rear]=e; Q->rear=<Q->rear+1>%MAXQSIZE;return<OK>;}//EnQueue<>end/*在顺序队列头删除旧元素*/intDeQueue<SqQueue*Q,QElemTypee>//DeQueue<>sub-function{if<Q->front==Q->rear>{printf<"队列为空!\n">;return<ERROR>;}e=Q->base[Q->front];Q->front=<Q->front+1>%MAXQSIZE;return<OK>;}//DeQueue<>endvoiddisplay<SqQueue*Q>{if<Q->front==Q->rear>printf<"队列为空!\n">;inti=Q->front;while<<i+1>%MAXQSIZE!=Q->rear>{printf<"%c->",Q->base[i]>;i++;}printf<"^\n">;}intmain<>{QElemTypee;intchoice;SqQueueQ;InitQueue<&Q>;printf<"====================