栈的应用举例
- 格式：doc
- 大小：317.50 KB
- 文档页数：10
内容：数据结构实验报告 课程：数据结构 班级：13物联网工程 姓名：* * * 学号：----------------- 日期：2014.10.21 实验目的： 1.熟悉C语言的基本编程方法，掌握集成编译环境的调试方法 。 2.学习栈的使用方法。 3.掌握栈操作的实现方法。 4.学习使用栈解决实际问题的能力。
实验内容： 利用栈完成：1.数制转换 2.括号匹配的检验 3.行编辑程序 4.迷宫求解 5.表达式求解 五大功能模块。 **********基本操作的函数原型说明********** Status InitStack(SqStack &s); //构造一个空栈S Status Destory(SqStack &s); //销毁栈S，S不再存在 Status ClearStack(SqStack &s); //把栈设置为空 Status StackEmpty(SqStack &s) ; //判断栈是否为空 int StackLength(SqStack &s) //返回栈的长度 Status GetTop(SqStack &s,SElemType &e); //若栈不空，则用e返回S的栈顶元素，并返回OK。否则返回ERROR Status Push(SqStack &s,SElemType e) //插入元素e为新的栈顶元素 Status Pop(SqStack &s,SElemType &e) //若栈不空，则删除s的栈顶元素，用e返回其值，并返回ok；否则返回error Status StackTraverse(SqStack S,Status(*visit)(SElemType)) //从栈底到栈顶依次对栈中每个元素调用函数visit()。 一旦visit()失败，则操作失败
核心代码： 数制转换： void S_B() { int n; SqStack S; InitStack(S); printf("请输入十进制整数n："); scanf("%d",&n); SElemType e; while (n>0) { Push(S, n % 8); n = n/8; } printf("该数的八进制数："); while (!StackEmpty(S)) { Pop(S,e); printf("%d",e); } printf("\n"); }
括号的匹配检验： Status EnterString(SqStack &s) { SElemType e; while (1) { scanf("%c",&e); if(e=='('||e=='['||e=='{') Push(s,e); else if(e==')'||e==']'||e=='}') { if(!Check(s,e)) { return FALSE; break; } } else if(e!='\n') { x=1; return FALSE; break; } else break; } }
行编辑程序： void LineEdit() { // 利用字符栈s，从终端接收一行并送至调用过程的数据区。 char ch,c; SqStack s; InitStack(s); InitStack(s);
printf(" 欢迎进入行编辑模块\n"); printf(" '#'为退格符\n"); printf(" '@'表示当前行中字符均无效\n\n"); printf(" 请输入字符：\n"); ch=getchar(); while(ch!=EOF) { while(ch!='\n') { switch(ch) { case '#':Pop(s,c); break; // 仅当栈非空时退栈 case '@':ClearStack(s); break; // 重置s为空栈 default :Push(s,ch); // 有效字符进栈 } ch=getchar(); // 从终端接收下一个字符 } StackTraverse(s,visit); // 将从栈底到栈顶的栈内字符输出 ClearStack(s); // 重置s为空栈 if(ch !=EOF) ch = getchar(); } Destory(s); }
迷宫求解： Status MazePath(int maze[12][12],SqStack1 &S, PosType start, PosType end) { PosType curpos; int curstep; SET e; InitStack(S); curpos = start; curstep = 1; do { if (Pass(maze,curpos)) { Markfoot(maze,curpos); e.di =1; e.ord = curstep; e.seat= curpos; Push1(S,e); if (curpos.row==end.row && curpos.line==end.line) return OK; curpos = NextPos(curpos, 1); curstep++; } else { if (!StackEmpty(S)) { Pop1(S,e); while (e.di==4 && !StackEmpty(S)) { Markfoot(maze,e.seat); Pop1(S,e); } if (e.di<4) { e.di++; Push1(S, e); curpos = NextPos(e.seat, e.di); } } } } while (!StackEmpty(S)); return ERROR; }
表达式求值： float EvaluateExpression(char* MyExpression) { // 算术表达式求值的算符优先算法 // 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合 SC *OPTR=NULL; // 运算符栈，字符元素 SF *OPND=NULL; // 运算数栈，实数元素 char TempData[20]; float Data,a,b; char theta,*c,x,Dr[]={'#','\0'}; OPTR=Push(OPTR,'#'); c=strcat(MyExpression,Dr); strcpy(TempData,"\0");//字符串拷贝函数 while (*c!= '#' || OPTR->c!='#') { if (!In(*c, OPSET)) { Dr[0]=*c; strcat(TempData,Dr);//字符串连接函数 c++; if (In(*c, OPSET)) { Data=atof(TempData);//字符串转换函数(double) OPND=Push(OPND, Data); strcpy(TempData,"\0"); } } else { // 不是运算符则进栈 switch (precede(OPTR->c, *c)) { case '<': // 栈顶元素优先级低 OPTR=Push(OPTR, *c); c++; break; case '=': // 脱括号并接收下一字符 OPTR=Pop(OPTR); c++; break; case '>': // 退栈并将运算结果入栈 theta=OPTR->c;OPTR=Pop(OPTR); b=OPND->f;OPND=Pop(OPND); a=OPND->f;OPND=Pop(OPND); OPND=Push(OPND, Operate(a, theta, b)); break; } } } return OPND->f; }
运行结果： 实验总结： 通过一周的学习和实践，解决实际问题，让我对数据结构有了更深的了解，对数据结构产生了浓厚的兴趣，同时也让我提高了解决实际问题的能力。 在这次课程设计的实验中，我收获了许多知识，培养了独立思考、动手操作的能力。这对我来说是一种锻炼，一个知识积累的过程，一种能力的提高。要打好基础，才能用更好的办法，更简洁明了的程序解决实际问题，只有这样才能进一步的取得更好的成绩。我会更加努力，努力的去弥补自己的缺点，发展自己的优点，去充实自己，只有在了解了自己的长短之后，才会更加珍惜拥有的，更加努力的去完善它，增进它。 虽然我现在的水平还很差，但我还会继续努力的，在解决实际问题时如果遇到了难题，我要学会去查找大量的有关这方面的资料，还要借助于网络不断扩大自己的知识面和阅读量。这样也可以锻炼我们的自主学习能力和解决问题的能力，学到许多以前没学到的东西。
