1.栈的定义、基本操作的实现，以及典型应用
（1）编程实现顺序栈的基本操作
核心代码：
①comdef.h
#include <stdio.h> #include <iostream> using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -1 typedef int Status;
②spstackdef.H
#define MAXSIZE 100 typedef int SElemType; typedef struct{ SElemType *base;//栈底指针 SElemType *top;//栈顶指针 int stacksize;//栈可用的最大容量 }SqStack;
③spstackapp.H
//栈的初始化 Status InitStack(SqStack &S) { //构造一个空栈 S.base=new SElemType[MAXSIZE];//为顺序栈动态分配一个最大容量为MAXSIZE的数组空间 if(!S.base)//存储分配失败 exit (OVERFLOW); S.top=S.base;//top初始为base,空栈 S.stacksize=MAXSIZE; return OK; } //判断栈空 Status StackElemType(SqStack S) { return (S.base==S.top); } //求栈的长度 int StackLength(SqStack S) { return S.top-S.base; } //取栈顶 SElemType GetTop(SqStack S) { if(S.top!=S.base) return *(S.top-1); } //出栈 Status Pop(SqStack &S,SElemType &e) { //删除栈顶元素，用e返回其值 if(S.top==S.base) return ERROR; else { e=*--S.top; return OK; } } //入栈 Status Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize)//栈满 return ERROR; else { *S.top++=e; //元素e压入栈顶，栈顶指针加一 return OK; } } //输出栈 void StackTraverse(SqStack S) { SElemType *p=S.top-1; while(p>=S.base) { cout<<"\n "<<*p; p--; } }
//清空栈 void ClearStack(SqStack &S) { S.base=S.top; } //栈的销毁 bool DestroyStack(SqStack &S) { delete []S.base; S.base=NULL; S.top=NULL; S.stacksize=0; return true; }
④main.CPP
#include "comdef.h" #include "sqstackdef.h" #include "sqstackapp.h" int main(){ SqStack S; SElemType e; int choice,n,i; cout<<"\n建立顺序栈："; if (InitStack(S)==OVERFLOW){ cout<<"顺序栈空间分配失败,程序退出！"; return 0; } else{ cout<<"\n数据个数="; cin>>n; cout<<"\n输入"<<n<<"个数据: "; for(int j=0;j<n;j++) { cin>>i; Push(S,i); } cout<<"顺序栈建立成功，顺序栈为："; StackTraverse(S); } do { cout<<"\n\n==================================="; cout<<"\n 顺序栈的基本操作"; cout<<"\n==================================="; cout<<"\n1:判断栈空" ; cout<<"\n2:求栈的长度" ; cout<<"\n3:取栈顶" ; cout<<"\n4:出栈" ; cout<<"\n5:入栈" ; cout<<"\n6:输出栈" ; cout<<"\n7:清空栈" ; cout<<"\n0:操作结束" ; cout<<"\n==================================="; cout<<"\n请输入你的选择:"; cin>>choice; switch (choice) { case 1: if(StackElemType(S)) cout<<"\n数据表为空表"; else cout<<"\n数据表为非空表"; break; case 2: cout<<"\n数据栈的长度为："<<StackLength(S); break; case 3: if(StackElemType(S)) cout<<"\n栈为空，栈顶元素不存在！"; else { cout<<"\n栈顶元素为："<<GetTop(S); } break; case 4: if(!Pop(S,e)) { cout<<"\n栈为空，栈顶元素不存在！"; } else { cout<<"\n栈顶出栈成功！"<<"\n出栈后的栈为："; StackTraverse(S); } break; case 5: cout<<"入栈元素为："; cin>>e; Push(S,e); cout<<"\n入栈成功！"<<"\n入栈后的栈为："; StackTraverse(S); break; case 6: cout<<"顺序栈为："; StackTraverse(S); break; case 7: ClearStack(S); cout<<"成功清空！"<<"\n栈中无元素："; StackTraverse(S); break; case 0: break; default:cout<<"\n输入错误,重新输入！"; } } while (choice) ; DestroyStack(S); return 0; }
2.队列的定义、基本操作的实现
编程实现循环队列的基本操作
核心代码：
comdef.h#include <stdio.h> #include<stdlib.h> #include <iostream> using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -1 typedef int Status; //队列的顺序存储结构 #define MAXQSIZE 100 typedef struct { QElemType *base; //存储空间的基地址 int front; //头指针 int rear; //尾指针 }SqQueue;
SqQueueapp.h
//初始化空队列 Status InitQueue(SqQueue &Q) { //构造空队列 Q.base=new QElemType[MAXQSIZE]; //为队列分配一个最大容量为MAXQSIZE的数组空间 if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; //头指针和尾指针置空，队列为空 return OK; } //打印队列 void OutputQueue(SqQueue Q,int n) { if(Q.front==Q.rear) cout<<"队列为空"; while(Q.front!=Q.rear) { cout<<Q.base[Q.front]<<" "; Q.front=(Q.front+1)%(n+1); } } //判断队空 Status QueueEmpty(SqQueue Q) { return (Q.front==Q.rear); }
//求队列的长度 int QueueLength(SqQueue Q) { return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; }
//取队首 Status GetHead(SqQueue Q,QElemType &e) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; //返回队头元素的值，队头元素不变 return OK; }
//出队列 Status DeQueue(SqQueue &Q,QElemType &e) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; //保存队头元素 Q.front=(Q.front+1)%MAXQSIZE; //队头指针加一 return OK; }
//入队列 Status EnQueue(SqQueue &Q,QElemType e) { //插入e为新的队尾元素 if((Q.rear+1)%MAXQSIZE==Q.front) //尾指针在循环意义上加一，表明存储空间已满 return ERROR; Q.base[Q.rear]=e; //新元素为队尾 Q.rear=(Q.rear+1)%MAXQSIZE; //队尾指针加一 return OK; }
//队列的销毁 Status DestoryQueue(SqQueue &Q) { free(Q.base); Q.base=NULL; Q.front=Q.rear=0; return OK; }
main.CPP
#include "comdef.h" #include "SqQueuedef.h" #include "SqQueueapp.h" int main(){ SqQueue Q; QElemType e; int choice,n,i; cout<<"\n建立循环队列："; if (InitQueue(Q)==OVERFLOW){ cout<<"队列空间分配失败,程序退出！"; return 0; } else{ cout<<"\n元素个数="; cin>>n; cout<<"\n输入"<<n<<"个队列元素: "; for(int j=0;j<n;j++) { cin>>i; EnQueue(Q,i); } cout<<"顺序队列建立成功，队列为："; OutputQueue(Q,n); } do { cout<<"\n\n==================================="; cout<<"\n 循环队列的基本操作"; cout<<"\n==================================="; cout<<"\n1:判断队列空" ; cout<<"\n2:求队列的长度" ; cout<<"\n3:取队首" ; cout<<"\n4:出队列" ; cout<<"\n5:入队列" ; cout<<"\n6:打印队列" ; cout<<"\n0:操作结束" ; cout<<"\n==================================="; cout<<"\n请输入你的选择:"; cin>>choice; switch (choice){ case 1: if(!QueueEmpty) cout<<"此队列为空队列！"; else cout<<"此队列非空！"; break; case 2: cout<<"此队列的长度为"<<QueueLength(Q); break; case 3: GetHead(Q,e); cout<<"队首为："<<e; break; case 4: DeQueue(Q,e); cout<<"出队列的元素为："<<e<<"\n当前队列为："; OutputQueue(Q,n); break; case 5: cout<<"需要入队列的元素为："; cin>>e; EnQueue(Q,e); cout<<"\n当前队列为："; OutputQueue(Q,n+1); break; case 6: cout<<"\n队列为："; OutputQueue(Q,n); break; case 0: break; default:cout<<"\n输入错误,重新输入！"; } } while (choice) ; DestoryQueue(Q); return 0; }
