云南大学软件学院数据结构实验

..WORD.格式整理....专业.知识.分享..实验难度：A□B□C□序号学号姓名成绩指导教师（签名）学期：2017秋季学期任课教师:实验题目:组员及组长:承担工作：联系电话:电子邮件:完成提交时间：年月日云南大学软件学院数据结构实验报告..WORD.格式整理....专业.知识.分享..一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计等相关知识，对问题进行概要性地分析）魔王语言的解释规则：大写字母表示魔王语言的词汇，小写字母表示人的词汇语言,魔王语言中可以包含括号，魔王语言的产生式规则在程序中给定，当接收用户输入的合法的魔王语言时，通过调用魔王语言翻译函数来实现翻译。在A的基础上，（根据产生式）自定义规则，将一段魔王的话翻译为有意义的人类语言（中文）：输入wasjg,则魔王语言解释为“我爱数据结构”。运用了离散数学的一些基本知识及程序设计知识。二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功能说明等）//---------------抽象数据类型的定义------------------//#defineSTACK_INIT_SIZE50#defineSTACKINCREMENT10#defineOVERLOW-2#defineERROR-1typedefstruct{char*base;//顺序栈的栈底指针inttop;//顺序栈的栈顶intsize;//栈元素空间的大小}SqStack;//结构体类型顺序栈typedefstruct{char*base;intfront;intrear;}SqQueue;//结构体类型队列//---------------各个模块功能的描述------------------//voidInit_SqStack(SqStack&s)//初始化顺序桟voidPush_SqStack(SqStack&s,charc)//压入数据intPop_SqStack(SqStack&s,char&e)//出桟charGetTop_SqStack(SqStacks)//或得栈顶..WORD.格式整理....专业.知识.分享..intIsEmpty_SqStack(SqStacks)//判断是否空栈voidInit_SqQueue(SqQueue&q)//初始化voidEn_SqQueue(SqQueue&q,charc)//进队列intDe_SqQueue(SqQueue&q,char&e)//出队列voidTranslate(charc)//打印字符voidReverse(charstr[],charstrtmp[])//将字符串反向intExecute(charch[],SqStack&s,SqQueue&q)//魔王语言操作调用关系：三、【实现（Implement）】(30%)（本部分应包括：抽象数据类型各操作的具体实现代码、关键操作的具体算法实现、函数实现，主程序实现等，并给出关键算法的时间复杂度分析。如有界面则需包括界面的关键实现方法等。）主程序模块：intmain(){charch[100];charch1[100];charch2[100];chare;//********************************************************英文解密printf(请输入魔王语言：);gets(ch);SqStacks;SqQueueq;Init_SqStack(s);Init_SqQueue(q);if(Execute(ch,s,q)==1)..WORD.格式整理....专业.知识.分享..{while(De_SqQueue(q,e)==1){Translate(e);}}elseprintf(输入的括号不匹配!);//左括号比右括号多，不匹配//********************************************************中文解密printf(\n);printf(请输入魔王语言：);gets(ch1);Init_SqStack(s);Init_SqQueue(q);Reverse(ch1,ch2);{for(inti=0;ch2[i]!='\0';i++)Push_SqStack(s,ch2[i]);while(Pop_SqStack(s,e)==1){switch(e){case'w':printf(我);break;case'a':printf(爱);break;case's':printf(数据);break;case'j':printf(结);break;case'g':printf(构);break;}}}return0;}其他函数实现代码见七、【代码】部分。时间复杂复分析：o(n)。四、【测试结果（Testing）】(10%)（本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析，可附截图）..WORD.格式整理....专业.知识.分享..输入的魔王语言为：B(ehnxgz)B翻译的结果为：tsaedsaeezegexenehetsaedsae错误模式：括号匹配错误提示。输入的魔王语言为：wasjg翻译为汉语的结果为：我爱数据结构结论：此程序能够按照给定的翻译规则解释魔王语言。五、【实验总结】(10%)（本部分应包括：自己在实验中完成的任务，及存在的问题，所完成实验过程中的具体经验总结、心得）问题关键：1.栈的初始化，入栈出栈操作，栈为空的判断条件，队列的初始化，入队和出队操作，队列为空的判断。以及队列中最后一个元素被删除后尾指针的修改。2.主函数的操作。由于队列和栈的操作始终为同一个，所以在主函数中，采用指针函数的调用，确保操作在同一个队列和栈上。3.一些细节处理，比如数组操作等。4.另在查阅资料时候发现：将魔王语言作为一个字符串读入进来，首先检查括号是否匹配，如果不匹配就无法解释。如果匹配，然后将字符串从尾到头依次压入栈S中，将栈S中的内容依次弹出压入栈S2中，直至遇到右括号，将其压入栈S1中，并..WORD.格式整理....专业.知识.分享..将栈S2弹出依次压入栈S1中，直至遇到左括号压入栈S1中，这样栈S1中存放的内容就是匹配的第一个内重括号，将栈S1栈顶元素左括号弹出，将左括号下面的那个元素保存在e1变量中，然后将其他元素弹出依次压入栈S3中，在将e1与栈S3中依次弹出的元素压入栈S2中，重复这个过程，直至将魔王语言中所有的括号都处理完为止，所以这个思路可以处理多重括号嵌套的问题。六、思考题或【项目运作描述（Operate）】(10%)（注：选择C难度的才需要填写“项目运作描述”，其他难度的只需完成思考题）（项目运作描述应包括：项目的成本效益分析，应用效果等的分析。）1.栈：特点就是一个先进后出的结构。主要用途：函数调用和返回，数字转字符，表达式求值，走迷宫等等。在CPU内部栈主要是用来进行子程序调用和返回，中断时数据保存和返回。在编程语言中：主要用来进行函数的调用和返回。可以说在计算机中，只要数据的保存满足先进后出的原理，都优先考虑使用栈，所以栈是计算机中不可缺的机制。队列：特点就是一个先进先出的结构。只要满足数据的先进先出原理就可以使用队列。2.可以采用顺序存储结构和链式存储结构，因为他们都是线性表，就像一排站在一条线上的人，位置关系是一个挨一个的，这样的顺序不会改变，而改变点都在头或者尾，仍然保持形态不变的。七、【代码】(10%)（本部分应包括：完整的代码及充分的注释。注意纸质的实验报告无需包括此部分。格式统一为，字体:Georgia,行距:固定行距12，字号:小五）#includestdio.h#includestdlib.h#includestring.h#defineSTACK_INIT_SIZE50#defineSTACKINCREMENT10#defineOVERLOW-2#defineERROR-1typedefstruct{char*base;inttop;intsize;..WORD.格式整理....专业.知识.分享..}SqStack;typedefstruct{char*base;intfront;intrear;}SqQueue;voidInit_SqStack(SqStack&s)//初始化顺序桟{s.base=(char*)malloc(sizeof(char)*STACK_INIT_SIZE);if(!s.base)exit(OVERLOW);s.top=0;s.size=STACK_INIT_SIZE;}voidPush_SqStack(SqStack&s,charc)//压入数据{if(s.top=s.size){s.base=(char*)realloc(s.base,(sizeof(char)*(s.size+STACKINCREMENT)));s.size+=STACKINCREMENT;}s.base[s.top]=c;s.top++;}intPop_SqStack(SqStack&s,char&e)//出桟{if(s.top==0)return0;s.top--;e=s.base[s.top];return1;}charGetTop_SqStack(SqStacks){returns.base[s.top-1];}intIsEmpty_SqStack(SqStacks){if(s.top==0)return1;elsereturn0;}voidInit_SqQueue(SqQueue&q)//初始化{q.base=(char*)malloc(sizeof(char)*STACK_INIT_SIZE);if(!q.base)exit(OVERLOW);q.front=0;..WORD.格式整理....专业.知识.分享..q.rear=0;}voidEn_SqQueue(SqQueue&q,charc)//进队列{if((q.rear+1)%STACK_INIT_SIZE==q.front)exit(ERROR);q.base[q.rear]=c;q.rear=(q.rear+1)%STACK_INIT_SIZE;}intDe_SqQueue(SqQueue&q,char&e)//出队列{if(q.front==q.rear)return0;e=q.base[q.front];q.front=(q.front+1)%STACK_INIT_SIZE;return1;}voidTranslate(charc)//打印字符{printf(%c,c);}voidReverse(charstr[],charstrtmp[])//将字符串反向{intlen=strlen(str);inti,t=0;for(i=len-1;i=0;i--)strtmp[t++]=str[i];strtmp[t]='\0';}intExecute(charch[],SqStack&s,SqQueue&q){SqStackss;Init_SqStack(ss);charch1[100];charch2[100];charch3[100];charc1,e,c;intflag=0,t=0,i=0,len;Reverse(ch,ch1);//将输入进来的ch反向for(i=0;ch1[i]!='\0';i++)Push_SqStack(s,ch1[i]);while(Pop_SqStack(s,e)==1){if(flag!=0&&e!=')')//此处是为了将找到第一个左括号之后的字符全部进入括号操作桟ss中{Push_SqStack(ss,e);if(GetTop_SqStack(ss)=='(')