《2022年栈和队列资料 .pdf》由会员分享，可在线阅读，更多相关《2022年栈和队列资料 .pdf（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 栈和队列1.顺序栈sqstack.h #include using namespace std; const int MAXSIZE=50; struct Elem int data; ; typedef int ElemType; struct SqStack ElemType baseMAXSIZE; int top; ; void initStack(SqStack& s); void clearStack(SqStack& s); bool isEmpty(SqStack& s); bool isFull(SqStack& s); ElemType peek(SqStack& s)
2、; void push(SqStack& s,const ElemType& e); ElemType pop(SqStack& s); sqstack.cpp #include sqstack.h void 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -
3、 - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 19 页 - - - - - - - - - 2 ElemType peek(SqStack& s) if(s.top=0) cerrStack is empty!endl; exit(1); 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
4、& s) if(s.top=0) cerrStack is empty!endl; exit(1); -s.top; ElemType temp=s.bases.top; return temp; main.cpp #include sqstack.h void conversion(int n,int r) 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
5、); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 19 页 - - - - - - - - - 3 for(int i=0;ci!=0;+i) switch(ci) case : case (: push(s,ci); break; case : if(peek(s)=) pop(s); else return false; break; case ): if(peek(s)=() pop(s); else return false; break; if(isEmpt
6、y(s) return true; else return 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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - -
7、 - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 19 页 - - - - - - - - - 4 2.迷宫求解sqstack.h #include using namespace std; const int MAXSIZE=100; struct PosType / 迷宫坐标位置类型int x; / 行值int y; / 列值; struct Elem / 栈的元素类型int ord; / 通道块在路径上的序号PosType seat; / 通道块在迷宫中的坐标位置int di; / 从此通道块走向下一通道块的方向(03 表示东北 ) ;
8、typedef Elem ElemType; struct SqStack ElemType 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& s,const ElemType& e); ElemType pop(SqStack& s); sqstack.cpp 同前main.cpp #inc
9、lude #include #include sqstack.h const int MAXLENGTH=25; / 设迷宫的最大行列为25 typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宫数组 行 列 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 19 页 - - - - - - - - - 5 MazeType m; / 迷宫数组int curstep=1; / 当前足迹 ,初值为 1 / 定义墙元素值为0,可通过路径为1,不
10、能通过路径为-1,通过路径为足迹bool pass(PosType b) / 当迷宫 m 的 b 点的序号为1(可通过路径 )，return OK; 否则， return ERROR 。if(mb.xb.y=1) return true; else return false; void footPrint(PosType a) / 使迷宫 m 的 a点的序号变为足迹(curstep) ma.xa.y=curstep; PosType nextPos(PosType c,int di) / 根据当前位置及移动方向，返回下一位置PosType direc4=0,1,1,0,0,-1,-1,0; /
11、 行增量 ,列增量 / 移动方向 ,依次为东南西北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；否则返回FALSE SqStack s; PosType curpos; ElemType e; initStack(s
12、); curpos=start; do if(pass(curpos) / 当前位置可以通过，即是未曾走到过的通道块footPrint(curpos); / 留下足迹e.ord=curstep; e.seat.x=curpos.x; e.seat.y=curpos.y; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 19 页 - - - - - - - - - 6 e.di=0; push(s,e); / 入栈当前位置及状态curstep+; / 足迹加 1 if(cu
13、rpos.x=end.x&curpos.y=end.y) / 到达终点 (出口 ) return true; curpos=nextPos(curpos,e.di); else / 当前位置不能通过if(!isEmpty(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);
14、curstep+; curpos=nextPos(e.seat,e.di); / 设定当前位置是该新方向上的相邻块 while(!isEmpty(s); return false; void print(int x,int y) / 输出迷宫的解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; 名师资料总结 - - -
15、精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 19 页 - - - - - - - - - 7 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 此迷宫从入口到出口的一条路径如下:n; print(x,y); / 输出此通路 else cout 此迷宫
16、没有从入口到出口的路径n; 3.表达式求值sqstack.h 应用函数模板#include using namespace std; const int MAXSIZE=100; template struct SqStack ElemType baseMAXSIZE; int top; ; template void initStack(SqStack& s) s.top=0; template void clearStack(SqStack& s) s.top=0; template bool isEmpty(SqStack& s) return s.top=0; template 名师资
17、料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 19 页 - - - - - - - - - 8 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&
18、 e) if(s.top=MAXSIZE) cerrStack overflow!endl; exit(1); s.bases.top=e; +s.top; template 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.h int precede(char op) switch(op) case +: case -: return 1; case
19、*: case /: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 19 页 - - - - - - - - - 9 return 2; case (: case : default: return 0; void change(char* s1,char* s2) /将字符串s1 中的中缀表达式转换为在于s2 中的后缀表达式SqStack r; initStack(r);/ 初始化栈push(r,);/给栈底放入 字符，它具有最低优先级int i,j; i=0; j=
20、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); push(r,ch); ch=s1+i; else while(isdigit(ch)|ch=.) s2j+=ch
21、; ch=s1+i; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 19 页 - - - - - - - - - 10 s2j+= ; ch=pop(r); while(ch!=) if(ch=() cerrexpression error!endl; exit(1); else s2j+=ch; ch=pop(r); s2j+=; s2j+=0; compute.cpp #include sqstack.h #include double compute(char*
22、str) SqStack s; initStack(s); istringstream ins(str); / 把 str 定义为 string 流对象 ins，P82 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); 名师资料总结
23、- - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 19 页 - - - - - - - - - 11 if(x!=0.0) x=pop(s)/x; cerrDivide by 0!x; / 从字符串输入流中读入一个浮点数 push(s,x); /把读入的数或进行相应运算的结果压入到s 栈中insch; if(!isEmpty(s) x=pop(s); if(isEmpty(s) return x; else cerrexpression error!endl; exit(1); els
24、e cerrStack 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=compute(s2); coutrendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -
25、- - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 19 页 - - - - - - - - - 12 4.迷宫的递归求解main.cpp #include #include #include using namespace std; const int MAXLENGTH=25; / 设迷宫的最大行列为25 typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宫数组 行 列 struct PosType / 迷宫坐标位置类型int x; / 行值int y; / 列值; struct Elem / 栈的元素类型int
26、ord; / 通道块在路径上的序号PosType seat; / 通道块在迷宫中的坐标位置int di; / 从此通道块走向下一通道块的方向(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; else return false; void footP
27、rint(PosType a) / 使迷宫 m 的 a点的序号变为足迹(curstep) ma.xa.y=curstep; PosType nextPos(PosType c,int di) / 根据当前位置及移动方向，返回下一位置PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量 ,列增量 / 移动方向 ,依次为东南西北c.x+=direcdi.x; c.y+=direcdi.y; return c; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12
28、 页，共 19 页 - - - - - - - - - 13 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 mazePath(PosType curpos,PosType end) /若迷宫 maze 中存在从入口start 到出口 end 的通道，则求得一条/存放在栈中 (从栈底到栈顶 )，并返回TRUE
29、；否则返回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+; / 足迹加 1 footPrint(nextpos); return true; return false; int main() PosType begin,end; int x=8,y
30、=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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 19 页 - - - - - - - - - 14 infile.close(); /关闭文件if(mazePath(begin,end) / 求得一条通路cout 此迷宫
31、从入口到出口的一条路径如下:n; print(x,y); / 输出此通路 else cout 此迷宫没有从入口到出口的路径n; 5. 链队列linkqueue.h #include using namespace std; struct ElemType int d; ; struct QNode ElemType data; QNode* next; ; struct LinkQueue QNode* front; QNode* rear; ; void initQueue(LinkQueue& q); void destroyQueue(LinkQueue& q); void clearQ
32、ueue(LinkQueue& q); bool isEmpty(LinkQueue q); int getLength(LinkQueue q); 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.h void initQueue(LinkQueue&
33、 q) q.front=q.rear=new QNode; if(!q.front) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 19 页 - - - - - - - - - 15 exit(1); q.front-next=NULL; void destroyQueue(LinkQueue& q) while(q.front) q.rear=q.front-next; delete q.front; q.front=q.rear; void clearQueue(
34、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; return n; ElemType getHead(LinkQueue q) if(q.front=q.rear) cerrQueue is empty!next-data;
35、 void insertElem(LinkQueue& q,ElemType e) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 19 页 - - - - - - - - - 16 QNode* 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;
36、 ElemType e=p-data; q.front-next=p-next; 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.h void print(ElemType& e) coute.d ; in
37、t main() LinkQueue q; initQueue(q); ElemType a=3; ElemType b=5; insertElem(q,a); insertElem(q,b); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 19 页 - - - - - - - - - 17 coutgetLength(q)endl; traverseQueue(q,print); ElemType c=getHead(q); coutc.dendl; deleteE
38、lem(q); coutgetLength(q)endl; traverseQueue(q,print); 6.循环队列sqqueue.h #include using namespace std; const int MAXSIZE=3; struct ElemType int d; ; struct SqQueue ElemType* base; int front; int rear; ; void initQueue(SqQueue& q); void clearQueue(SqQueue& q); bool isEmpty(SqQueue& q); bool isFull(SqQue
39、ue& 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.h void initQueue(SqQueue& q) q.base=new ElemTypeMAXSIZE; if(!q.base) exit(1);
40、 q.front=q.rear=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 19 页 - - - - - - - - - 18 void clearQueue(SqQueue& q) q.front=q.rear=0; bool isEmpty(SqQueue& q) return q.front=q.rear; bool isFull(SqQueue& q) return (q.rear+1)%MAXSIZE=q.front; int getLength(S
41、qQueue& q) return (q.rear-q.front+MAXSIZE)%MAXSIZE; ElemType getHead(SqQueue& q) if(q.front=q.rear) coutQueue is empty!endl; exit(1); return q.baseq.front; bool insertElem(SqQueue& q,ElemType e) if(q.rear+1)%MAXSIZE=q.front) coutQueue overflow!endl; return false; q.baseq.rear=e; q.rear=(q.rear+1)%MA
42、XSIZE; return true; ElemType deleteElem(SqQueue& q) if(q.front=q.rear) coutQueue is empty!endl; exit(1); ElemType e=q.baseq.front; q.front=(q.front+1)%MAXSIZE; return e; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 19 页 - - - - - - - - - 19 void traverseQueu
43、e(SqQueue& q,void (*visit)(ElemType&) if(q.front=q.rear) coutQueue is empty!endl; else int t=q.front; while(t!=q.rear) visit(q.baset); t=(t+1)%MAXSIZE; coutendl; main.cpp #include sqqueue.h void print(ElemType& e) coute.d ; int main() SqQueue q; initQueue(q); coutisEmpty(q)endl; ElemType a=3; ElemTy
44、pe b=5; insertElem(q,a); insertElem(q,b); coutgetLength(q)endl; coutisEmpty(q)endl; traverseQueue(q,print); ElemType c=getHead(q); coutHead:c.dendl; coutfull:isFull(q)endl; deleteElem(q); coutgetLength(q)endl; traverseQueue(q,print); deleteElem(q); traverseQueue(q,print); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 19 页 - - - - - - - - -