栈和队列.doc

#include #include #define M 10/1.顺序栈的类型定义#define MAX 100 /栈的最大值typedef int ElemType;typedef structElemType *base; ElemType *top;int stacksize;/ElemType aMAX; SqStack; /2.链栈的类型定义typedef struct SqNodeElemType data; struct SqNode *next; Sqptr;typedef structSqptr *top; /栈顶指针Stack;/3.顺序队列的类型定义#define max 100 /队列的最大长度typedef structElemType *base; int front,rear; SqQueue;/4.单链队列的类型定义typedef struct QNodeElemType data; struct QNode *next; Queue,*QueuePtr;typedef structQueuePtr front; /队头指针 QueuePtr rear; /队尾指针LinkQueue;/顺序栈的相关操作SqStack InitStack(SqStack S) /构造一个空栈 S.base=(ElemType *)malloc(MAX * sizeof(ElemType);if (!S.base)printf(OVERFLOW);elseS.top=S.base;S.stacksize=MAX;printf(顺序栈初始化完毕n);return S;SqStack Push(SqStack S,ElemType e) /插入元素e为新的栈顶元素if (S.top-S.base=S.stacksize)S.base=(ElemType *)realloc(S.base,(S.stacksize+M) * sizeof(ElemType); /栈满，追加存储空间if (!S.base)printf(OVERFLOW); /存储分配失败elseS.top=S.base+S.stacksize; S.stacksize+=MAX;*S.top=e;S.top+;return S;SqStack Pop(SqStack S,ElemType e) /删除栈顶元素if (S.top=S.base) /判断栈是否为空printf(空栈);else e=*-S.top;return S;void StackTraverse(SqStack S)if (S.top=S.base)printf(空栈);elseprintf(顺序栈显示:);for(S.top-;S.top=S.base;S.top-)printf(%d ,*S.top);Stack InitStack2(Stack S2)S2.top=(Sqptr *)malloc(sizeof(Sqptr);if (!S2.top)printf(OVERFLOW);elseS2.top-next=NULL;printf(链栈初始化完毕n);return S2;Stack Push2(Stack S2,ElemType e)Sqptr *p;p=(Sqptr *)malloc(sizeof(Sqptr);if (!p)printf(OVERFLOW);elsep-data=e; p-next=S2.top-next;S2.top-next=p;return S2;Stack Pop2(Stack S2,ElemType e)Sqptr *p;if (S2.top-next=NULL)printf(空栈n);elsep=S2.top-next;e=p-data;S2.top-next=p-next;free(p);return S2;void StackTraverse2(Stack S2)if (S2.top-next=NULL)printf(空栈);elseprintf(链栈显示:n);while (S2.top-next)S2.top=S2.top-next;printf(%d ,S2.top-data);SqQueue InitQueue(SqQueue Q)Q.base=(ElemType *)malloc(max*sizeof(ElemType);if (!Q.base)printf(OVERFLOWn);elseQ.front=Q.rear=0;printf(顺序队列初始化完毕n);return Q;SqQueue EnQueue(SqQueue Q,ElemType e)if (Q.rear+1)%max=Q.front)printf(ERRORn);elseQ.baseQ.rear=e;Q.rear=(Q.rear+1)%max;return Q;SqQueue DeQueue(SqQueue Q,ElemType e)if (Q.front=Q.rear)printf(ERRORn);elsee=Q.baseQ.front;Q.front=(Q.front+1)%max;return Q;void QueueTraverse(SqQueue Q)if (Q.front=Q.rear)printf(空队列n);elseprintf(顺序队列显示:n);while (Q.front!=Q.rear)printf(%d ,Q.baseQ.front); Q.front+;LinkQueue InitQueue2(LinkQueue Q2)Q2.front=Q2.rear=(QueuePtr)malloc(sizeof(QNode);if (!Q2.front)printf(OVERFLOWn);elseQ2.front-next=NULL;Q2.rear=Q2.front;printf(链队列初始化完毕n);return Q2;LinkQueue EnQueue2(LinkQueue Q2,ElemType e) QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if (!p)printf(OVERFLOW);elsep-data=e;p-next=NULL;Q2.rear-next=p;Q2.rear=p;return Q2;LinkQueue DeQueue2(LinkQueue Q2,ElemType e) QueuePtr p;if (Q2.front=Q2.rear)printf(ERRORn);elsep=Q2.front-next;e=p-data;Q2.front-next=p-next;if (Q2.rear=p)Q2.rear=Q2.front;free(p);return Q2;void QueueTraverse2(LinkQueue Q2)printf(链队列显示:n);if (Q2.front=Q2.rear)printf(空链队列n);elsewhile (Q2.front!=Q2.rear) Q2.front=Q2.front-next;printf(%d ,Q2.front-data);void main()SqStack S;Stack S2; SqQueue Q; LinkQueue Q2;ElemType e;int select;S=InitStack(S);S2=InitStack2(S2);Q=InitQueue(Q);Q2=InitQueue2(Q2);do printf(n主菜单:n); printf(1:顺序栈Pushn2:顺序栈Popn); printf(3:链栈Pushn4:链栈Popn);printf(5:顺序队列EnQueuen6:顺序队列DeQueuen);printf(7:链队列EnQueuen8:链队列DeQueuen); printf(0:exitnplease selcet(0-8)n);scanf(%d,&select); switch(select) case 1:printf(Input numbers(按Enter和Ctrl+Z结束输入):n); while (scanf(%d,&e)!=EOF)S=Push(S,e); StackTraverse(S);break; case 2:S=Pop(S,e); StackTraverse(S);break; case 3:printf(Input numbers(按Enter和Ctrl+Z结束输入):n); while (scanf(%d,&e)!=EOF) S2=Push2(S2,e); StackTraverse2(S2);break; case 4:S2=Pop2(S2,e); StackTraverse2(S2);break;case 5:printf(Input numbers(按Enter和Ctrl+Z结束输入):n); while (scanf(%d,&e)!=EOF) Q=EnQueue(Q,e); QueueTraverse(Q);break;case 6:Q=DeQueue(Q,e); QueueTraverse(Q);break;case 7:pri