实验二 栈和队列其应用.doc

《实验二 栈和队列其应用.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验二栈和队列其应用题目：利用栈的深度优化进行迷宫求解班级：姓名：杨欢学号：完成日期：2011.12.1一、需求分析1、 进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2、掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3、掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。本课程设计的目的1、使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2、使学生掌握软件设计

2、的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。本课程设计的内容栈和队列其应用目的在于使读者深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对这两种结构的构造方法的掌握，接触较复杂问题的递归算法设计。（1）：算术表达式转波兰表达式和逆波兰表达式（2）：栈列操作的验证（建栈、入栈、出栈、销毁栈）（3）：判断表达式中括弧是否正确配对（4）：队列元素倒置（5）：判断字符串是否回文（6）：字符串的基本操作（5个基本函数实现）二、概

3、要设计栈和队列及其应用目的在于使读者深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对这两种结构的构造方法的掌握，接触较复杂问题的递归算法设计ADTStack的表示和实现#include#defineSTACK_INIT_SIZE30#defineSTACKINCREMENT5typedefstruct{char*base;char*top;intstacksize;}sqstack;voidInitStack(sqstack&s){s.base=(char*)malloc(STACK_IN

4、IT_SIZE*sizeof(char));//if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;}voidpush(sqstack&s,char&c){if(s.top-s.base>=s.stacksize){s.base=(char*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char));//if(!s.base)exit(OVERFLOW);s.top=s.base+s.stack

5、size;s.stacksize+=STACKINCREMENT;}*s.top++=c;}voidpop(sqstack&s,char&c){if(!(s.top==s.base))c=*--s.top;}intstackEmpty(sqstacks){if(s.base==s.top)return(1);return(0);}算术表达式转波兰表达式和逆波兰表达式#include#includevoidtransform(char*str,inta[][2],int*n){inti;*n=1;a

6、[0][0]=1;a[0][1]='(';for(i=0;str[i];){if(isdigit(str[i])){a[*n][0]=0;a[*n][1]=0;while(isdigit(str[i])){a[*n][1]=a[*n][1]*10+str[i]-'0';i++;}}else{if(str[i]=='(')a[*n][0]=1;elseif(str[i]==')')a[*n][0]=2;elseif(str[i]=='*')a[*n][0]=3;elseif(str[i]=='/')a[*n][0]=4;elseif(

7、str[i]=='+'

8、

9、str[i]=='-'){if(i==0

10、

11、(!isdigit(str[i-1])&&str[i-1]!=')')){a[*n][0]=0;a[*n][1]=0;(*n)++;}if(str[i]=='+')a[*n][0]=5;elsea[*n][0]=6;}a[*n][1]=str[i];i++;}(*n)++;}a[*n][0]=2;a[*n][1]=')';(*n)++;}voidpoland(inta[][2],intn,intp[][2],int*m){inti;intstack[1000];/

12、/转化所用的栈intdepth;//栈的深度depth=0;*m=0;for(i=0;i