栈和队列的基本操作.doc

/*验四：栈和队列的基本操作实验内容 1采用链式存储实现栈的初始化、入栈、出栈操作。 2采用顺序存储实现栈的初始化、入栈、出栈操作。 3采用链式存储实现队列的初始化、入队、出队操作。 4采用顺序存储实现循环队列的初始化、入队、出队操作。 5在主函数中设计一个简单的菜单，分别测试上述算法。*/#include stdio.h#include stdlib.h#define STACK_INIT_SIZE 100/存储空间初始分配量#define STACKINCREMENT 10/存储空间分配增加量#define ERROR 0#define OVERFLOW -2#define OK 1typedef int SElemType;typedef int QElemType;typedef struct /顺序栈的结构SElemType *base;SElemType *top;int stacksize;SqStack;typedef struct SqNode/链栈的结构单元SElemType data;SqNode *Link;*Sqptr,NODE;typedef structSqptr top; /栈顶指针 Stack;int InitStackb(Stack &S)/链式存储实现栈的初始化S.top=(Sqptr)malloc(sizeof(NODE);if(!S.top) exit (OVERFLOW);S.top-Link=NULL;return 1;void Pushb(Stack &S)/链式存储实现栈的入栈操作Sqptr p;int x;printf(请输入入栈元素(以0结束):);scanf(%d,&x);while(x)p=(Sqptr)malloc(sizeof(NODE);if(!p) return ;p-data=x;p-Link=S.top-Link;S.top-Link=p;scanf(%d,&x);void Popb(Stack &S)/链式存储实现栈的出栈操作int x;Sqptr p;while(S.top-Link) p=S.top-Link; x=p-data; S.top-Link=p-Link; printf(t删除的栈顶元素是%dn,x); free(p); int InitStack(SqStack &S)/顺序存储初始化栈 S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(-2);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK; void createStack(SqStack &S)/顺序栈元素入栈 int a; printf(请输入入栈元素(以0结束):); scanf(%d,&a); while(a) if(S.top-S.base=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+=a; scanf(%d,&a); void Popa(SqStack &S)/顺序存储实现栈的出栈操作SElemType *p;int x;while(S.top-S.base) p=S.top;x=*-S.top;printf(删除的栈顶元素是%dn,x); typedef struct QNode QElemType data; struct QNode *next;*QueuePtr,QNode; typedef structQueuePtr front;QueuePtr rear;LinkQueue;int InitQueue(LinkQueue &Q)/链式存储实现队列的初始化Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit(OVERFLOW);Q.front-next=NULL; return 1;void EnQueue(LinkQueue &Q)/链式存储实现队列的入队 int x; QueuePtr p; printf(请输入队列元素(以0结束); scanf(%d,&x);while(x) p=(QueuePtr)malloc(sizeof(QNode); if(!p) exit(OVERFLOW); p-data=x; p-next=NULL; Q.rear-next=p; Q.rear=p; scanf(%d,&x);void DeQueue(LinkQueue &Q)/链式存储实现队列的出队int x;QueuePtr p; while(Q.front!=Q.rear) p=Q.front-next; x=p-data; printf(t删除的队头元素是：%dn,x); Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); typedef structSElemType *base;int front,rear;SqQueue;int InitQueueb(SqQueue &S)/顺序存储实现队列的初始化 S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.front=S.rear=0; return 1;void EnQueueb(SqQueue &S)/顺序存储实现队列的入队int x;printf(请输入入队元素(以0结束):);scanf(%d,&x);while(x)if(S.rear+1)%STACK_INIT_SIZE=S.front) return;S.baseS.rear=x;S.rear=(S.rear+1)%STACK_INIT_SIZE;scanf(%d,&x);void DeQueueb(SqQueue &S)/顺序存储实现队列的出队int x; while(S.front!=S.rear) x=S.baseS.front; printf(t删除的队头元素是:%dn,x); S.front=(S.front+1)%STACK_INIT_SIZE; void main()SqStack La;int menu;Stack Lb;LinkQueue Q;SqQueue S;Lb.top=NULL;La.base=NULL;La.top=NULL;doprintf(1 创建顺序桟n);printf(2 顺序栈出栈操作n);printf(3 创建链栈n);printf(4 链栈出栈操作n);printf(5 创建链队列n);printf(6 连队的出对操作n);printf(7 创建顺序队列n);printf(8 顺序队列出对操作n);printf(0 退出n);printf(n请输入所选菜单（0-10）:);scanf(%d,&menu);switch(menu)case 1:InitStack(La);createStack(La);break;case 2: if(La.base=NULL|La.top=NULL)printf(I am is null,Plase create firstn);break;Popa(La);break;case 3: InitStackb(Lb); Pushb(Lb);break;case 4:if(Lb.top=NULL) printf(这是个空栈,无法执行输出操作n); break; Pop