栈和队列(代码)

1、栈和队列1.顺序栈sqstack.h#include using namespace std;const int MAXSIZE=50;struct Elemint data;typedef int ElemType;struct SqStackElemType baseMAXSIZE; int top;void initStack(SqStack& s);void clearStack(SqStack& s);bool isEmpty(SqStack& s);bool isFull(SqStack& s);ElemType peek(SqStack& s);void push(SqStack

2、& s,const ElemType& e); ElemType pop(SqStack& s);sqstack.cpp#include sqstack.hvoid initStack(SqStack& s)s.top=0;void clearStack(SqStack& s)s.top=0;bool isEmpty(SqStack& s)return s.top=0;bool isFull(SqStack& s)return s.top=MAXSIZE; ElemType peek(SqStack& s)if(s.top=0)cerrStack is empty!endl; exit(1);

3、return s.bases.top-1;void push(SqStack& s,const ElemType& e) if(s.top=MAXSIZE)cerrStack overflow!endl; exit(1);s.bases.top=e;+s.top;ElemType pop(SqStack& s)if(s.top=0)cerrStack is empty!endl; exit(1);-s.top;ElemType temp=s.bases.top; return temp;main.cpp#include sqstack.hvoid conversion(int n,int r)

4、SqStack s;initStack(s);while(n)push(s,n%r);n=n/r;while(!isEmpty(s)coutpop(s);coutendl;bool bracketsCheck(char* c)SqStack s;initStack(s);for(int i=0;ci!=0;+i) switch(ci)case :case (:push(s,ci); break; case :if(peek(s)=) pop(s); elsereturn false; break; case ):if(peek(s)=() pop(s); elsereturn false; b

5、reak; if(isEmpty(s)return true;elsereturn false;int main()SqStack a;ElemType b=s,c=g; initStack(a);coutisEmpty(a)endl; push(a,b);coutpeek(a)endl; push(a,c);coutpeek(a)endl; coutisFull(a)endl; coutpop(a)endl; char h=3*(4+9);coutbracketsCheck(h)endl; conversion(1348,8); 2.迷宫求解sqstack.h#include using n

6、amespace std;const int MAXSIZE=100;struct PosType / 迷宫坐标位置类型int x; / 行值int y; / 列值;struct Elem / 栈的元素类型int ord; / 通道块在路径上的序号PosType seat; / 通道块在迷宫中的坐标位置int di; / 从此通道块走向下一通道块的方向(03表示东北) ;typedef Elem ElemType;struct SqStackElemType baseMAXSIZE;int top;void initStack(SqStack& s);void clearStack(SqSta

7、ck& s);bool isEmpty(SqStack& s);bool isFull(SqStack& s);ElemType peek(SqStack& s);void push(SqStack& s,const ElemType& e);ElemType pop(SqStack& s);sqstack.cpp同前main.cpp#include #include #include sqstack.hconst int MAXLENGTH=25; / 设迷宫的最大行列为25typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宫数组行列MazeType m;

8、 / 迷宫数组int curstep=1; / 当前足迹,初值为1/ 定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹bool pass(PosType b)/ 当迷宫m的b点的序号为1(可通过路径)，return OK; 否则，return ERROR。 if(mb.xb.y=1)return true;elsereturn false;void footPrint(PosType a) / 使迷宫m的a点的序号变为足迹(curstep)ma.xa.y=curstep;PosType nextPos(PosType c,int di) / 根据当前位置及移动方向，返回下一

9、位置 PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量,列增量/ 移动方向,依次为东南西北c.x+=direcdi.x;c.y+=direcdi.y;return c;void markPrint(PosType b) / 使迷宫m的b点的序号变为-1(不能通过的路径) mb.xb.y=-1;bool mazePath(PosType start,PosType end)/若迷宫maze中存在从入口start到出口end的通道，则求得一条/存放在栈中(从栈底到栈顶)，并返回TRUE；否则返回FALSESqStack s;PosType curpos;ElemTyp

10、e e;initStack(s);curpos=start;doif(pass(curpos) / 当前位置可以通过，即是未曾走到过的通道块 footPrint(curpos); / 留下足迹e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;push(s,e); / 入栈当前位置及状态curstep+; / 足迹加1if(curpos.x=end.x&curpos.y=end.y) / 到达终点(出口)return true;curpos=nextPos(curpos,e.di);else / 当前位置不能通过if(!isEmpt

11、y(s)e=pop(s); / 退栈到前一位置curstep-;while(e.di=3&!isEmpty(s) / 前一位置处于最后一个方向(北) markPrint(e.seat); / 留下不能通过的标记(-1)e=pop(s); / 退回一步curstep-;if(e.di3) / 没到最后一个方向(北)e.di+; / 换下一个方向探索push(s,e);curstep+;curpos=nextPos(e.seat,e.di); / 设定当前位置是该新方向上的相邻块 while(!isEmpty(s);return false;void print(int x,int y) / 输出

12、迷宫的解for(int i=0;ix;i+)for(int j=0;jy;j+)coutsetw(3)mij;coutendl;int main()PosType begin,end;int x=8,y=10;begin.x=1;begin.y=1;end.x=6;end.y=8;ifstream infile;infile.open(data.txt); /打开文件for(int i=0;i8;i+)for(int j=0;jmij;infile.close(); /关闭文件cout迷宫结构如下:n;print(x,y);if(mazePath(begin,end) / 求得一条通路cout

13、此迷宫从入口到出口的一条路径如下:n; print(x,y); / 输出此通路elsecout此迷宫没有从入口到出口的路径n; 3.表达式求值sqstack.h 应用函数模板#include using namespace std;const int MAXSIZE=100;template struct SqStackElemType baseMAXSIZE;int top;template void initStack(SqStack& s)s.top=0;template void clearStack(SqStack& s)s.top=0;template bool isEmpty(S

14、qStack& s)return s.top=0;template bool isFull(SqStack& s)return s.top=MAXSIZE;template ElemType peek(SqStack& s)if(s.top=0)cerrStack is empty!endl;exit(1);return s.bases.top;template void push(SqStack& s,const ElemType& e) if(s.top=MAXSIZE)cerrStack overflow!endl;exit(1);s.bases.top=e;+s.top;templat

15、e ElemType pop(SqStack& s)if(s.top=0)cerrStack is empty!endl;exit(1);-s.top;ElemType temp=s.bases.top;return temp;change.cpp#include sqstack.hint precede(char op)switch(op)case +:case -:return 1;case *:case /:return 2;case (:case :default:return 0;void change(char* s1,char* s2)/将字符串s1中的中缀表达式转换为在于s2中

16、的后缀表达式 SqStack r;initStack(r);/初始化栈push(r,);/给栈底放入字符，它具有最低优先级 int i,j;i=0;j=0;char ch=s1i;while(ch!=)if(ch= )ch=s1+i;else if(ch=()push(r,ch);ch=s1+i;else if(ch=)while(peek(r)!=()s2j+=pop(r);pop(r);ch=s1+i;else if(ch=+|ch=-|ch=*|ch=/)char w=peek(r);while(precede(w)=precede(ch)s2j+=w;pop(r);w=peek(r);

17、push(r,ch);ch=s1+i;elsewhile(isdigit(ch)|ch=.)s2j+=ch;ch=s1+i;s2j+= ;ch=pop(r);while(ch!=)if(ch=()cerrexpression error!endl;exit(1);elses2j+=ch;ch=pop(r);s2j+=;s2j+=0;compute.cpp#include sqstack.h#include double compute(char* str)SqStack s;initStack(s);istringstream ins(str); /把str定义为string流对象ins，P8

18、2 char ch; /用于输入字符double x; /用于输入浮点数insch;while(ch!=)switch(ch)case +:x=pop(s)+pop(s);break;case -:x=pop(s); /pop(s)弹出减数x=pop(s)-x; /pop(s)弹出被减数break;case *:x=pop(s)*pop(s);break;case /:x=pop(s);if(x!=0.0)x=pop(s)/x;cerrDivide by 0!x; /从字符串输入流中读入一个浮点数 push(s,x); /把读入的数或进行相应运算的结果压入到s栈中 insch;if(!isEm

19、pty(s)x=pop(s);if(isEmpty(s)return x;elsecerrexpression error!endl;exit(1);elsecerrStack is emppty!endl;exit(1);main.cpp#include using namespace std;int precede(char op);void change(char* s1,char* s2);double compute(char* str);int main()char s1=34*(2+5)+3;char s230;change(s1,s2);couts2endl;double r=

20、compute(s2);coutrendl;4.迷宫的递归求解main.cpp#include #include #include using namespace std;const int MAXLENGTH=25; / 设迷宫的最大行列为25typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宫数组行列 struct PosType / 迷宫坐标位置类型int x; / 行值int y; / 列值;struct Elem / 栈的元素类型int ord; / 通道块在路径上的序号PosType seat; / 通道块在迷宫中的坐标位置int di; / 从

21、此通道块走向下一通道块的方向(03表示东北) ;MazeType m; / 迷宫数组int curstep=0; / 当前足迹,初值为1/ 定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹bool pass(PosType b)/ 当迷宫m的b点的序号为1(可通过路径)，return true; 否则，return false。 if(mb.xb.y=1)return true;elsereturn false;void footPrint(PosType a) / 使迷宫m的a点的序号变为足迹(curstep)ma.xa.y=curstep;PosType nextPos

22、(PosType c,int di) / 根据当前位置及移动方向，返回下一位置 PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量,列增量/ 移动方向,依次为东南西北c.x+=direcdi.x;c.y+=direcdi.y;return c;void markPrint(PosType b) / 使迷宫m的b点的序号变为-1(不能通过的路径) mb.xb.y=-1;void print(int x,int y) / 输出迷宫的解for(int i=0;ix;i+)for(int j=0;jy;j+)coutsetw(3)mij;coutendl;bool maze

23、Path(PosType curpos,PosType end)/若迷宫maze中存在从入口start到出口end的通道，则求得一条 /存放在栈中(从栈底到栈顶)，并返回TRUE；否则返回FALSE if(curpos.x=end.x&curpos.y=end.y) / 到达终点(出口)return true;PosType nextpos;for(int i=0;i4;+i)nextpos=nextPos(curpos,i);if(pass(nextpos)markPrint(nextpos);if(mazePath(nextpos,end)curstep+; / 足迹加1footPrint

24、(nextpos);return true;return false;int main()PosType begin,end;int x=8,y=10;begin.x=1;begin.y=1;end.x=6;end.y=8;ifstream infile;infile.open(data.txt); /打开文件for(int i=0;i8;i+)for(int j=0;jmij;infile.close(); /关闭文件if(mazePath(begin,end) / 求得一条通路cout此迷宫从入口到出口的一条路径如下:n; print(x,y); / 输出此通路elsecout此迷宫没有从

25、入口到出口的路径n; 5. 链队列linkqueue.h#include using namespace std;struct ElemTypeint d;struct QNodeElemType data;QNode* next;struct LinkQueueQNode* front;QNode* rear;void initQueue(LinkQueue& q);void destroyQueue(LinkQueue& q);void clearQueue(LinkQueue& q);bool isEmpty(LinkQueue q);int getLength(LinkQueue q)

26、;ElemType getHead(LinkQueue q);void insertElem(LinkQueue& q,ElemType e);ElemType deleteElem(LinkQueue& q);void traverseQueue(LinkQueue q,void (*visit)(ElemType&);linkqueue.cpp#include linkqueue.hvoid initQueue(LinkQueue& q)q.front=q.rear=new QNode;if(!q.front)exit(1);q.front-next=NULL;void destroyQu

27、eue(LinkQueue& q) while(q.front)q.rear=q.front-next;delete q.front;q.front=q.rear;void clearQueue(LinkQueue& q) QNode* p=q.front-next;while(p)q.rear=p-next;delete p;p=q.rear;bool isEmpty(LinkQueue q)return q.front=q.rear;int getLength(LinkQueue q)int n=0;QNode* p=q.front-next;while(p)+n;p=p-next;ret

28、urn n;ElemType getHead(LinkQueue q) if(q.front=q.rear)cerrQueue is empty!next-data;void insertElem(LinkQueue& q,ElemType e) 15QNode* p=new QNode;p-data=e;p-next=NULL;q.rear-next=p;q.rear=p;ElemType deleteElem(LinkQueue& q)if(q.front=q.rear)cerrQueue is empty!next;ElemType e=p-data;q.front-next=p-nex

29、t;if(q.rear=p) /若链队为空，则需同时使队尾指针指向头结点 q.rear=q.front;delete p;return e;void traverseQueue(LinkQueue q,void (*visit)(ElemType&) QNode* p=q.front-next;while(p)visit(p-data);p=p-next;coutendl;main.cpp#include linkqueue.hvoid print(ElemType& e)coute.d ;int main()LinkQueue q;initQueue(q);ElemType a=3;Elem

30、Type b=5;insertElem(q,a);insertElem(q,b);coutgetLength(q)endl;traverseQueue(q,print);ElemType c=getHead(q);coutc.dendl;deleteElem(q);coutgetLength(q)endl;traverseQueue(q,print);6.循环队列sqqueue.h#include using namespace std;const int MAXSIZE=3;struct ElemTypeint d;struct SqQueueElemType* base;int front

31、;int rear;void initQueue(SqQueue& q);void clearQueue(SqQueue& q);bool isEmpty(SqQueue& q);bool isFull(SqQueue& q);int getLength(SqQueue& q);ElemType getHead(SqQueue& q);bool insertElem(SqQueue& q,ElemType e);ElemType deleteElem(SqQueue& q);void traverseQueue(SqQueue& q,void (*visit)(ElemType&);sqqueue.cpp#include sqqueue.hvoid initQueue(SqQueue& q)q.base=new ElemTypeMAXSIZE;if(!q.base)exit(1);q.front=q.rear=0;void clearQueue(SqQueue& q)q.front=q.rear=0;bool isEmpty(SqQueue& q)return q.front=q.rear;bool isFull(SqQueue& q)retur