1、 实验难度： A B C 序号 学号 姓名 成绩指导教师 （签名）学 期： 2017 秋季学期 任课教师: 实验题目: 组员及组长: 承担工作： 联系电话: 电子邮件: 完成提交时间： 年 月 日云南大学软件学院 数据结构实验报告一、 【实验构思（Conceive ） 】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计等相关知识，对问题进行概要性地分析）魔王语言的解释规则：大写字母表示魔王语言的词汇，小写字母表示人的词汇语言,魔王语言中可以包含括号，魔王语言的产生式规则 在程序中给定，当接收用户输入的合法的魔王语言时，通过调用魔王语言翻译函数来实现翻译
2、。在 A 的基础上， （根据产生式）自定义规则，将一段魔王的话翻译为有意义的人类语言（中文）：输入 wasjg,则魔王语言解释为“我爱数据 结构” 。运用了离散数学的一些基本知识及程序设计知识。二、 【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功能说明等）/-抽象数据类型的定义-/#define STACK_INIT_SIZE 50#define STACKINCREMENT 10#define OVERLOW -2#define ERROR -1type
3、def struct char *base; /顺序栈的栈底指针int top; /顺序栈的栈顶int size; /栈元素空间的大小SqStack; /结构体类型顺序栈typedef struct char *base;int front;int rear;SqQueue; /结构体类型队列/-各个模块功能的描述-/void Init_SqStack(SqStack char ch1100;char ch2100;char e;/*英文解密printf(“请输入魔王语言： “);gets(ch);SqStack s;SqQueue q;Init_SqStack(s);Init_SqQueue
4、(q);if(Execute(ch,s,q) = 1)while(De_SqQueue(q,e) = 1)Translate(e);elseprintf(“输入的括号不匹配!“); /左括号比右括号多，不匹配/*中文解密printf(“n“);printf(“请输入魔王语言： “);gets(ch1);Init_SqStack(s);Init_SqQueue(q);Reverse(ch1,ch2);for(int i=0;ch2i!=0;i+)Push_SqStack(s,ch2i);while(Pop_SqStack(s,e) = 1)switch(e)casew:printf(“我“);b
5、reak;casea:printf(“爱“);break;cases:printf(“数据“);break;casej:printf(“结“);break;caseg:printf(“构“);break;return 0;其他函数实现代码见七、 【代码】部分。时间复杂复分析：o(n)。四、 【测试结果（Testing） 】(10%)（本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析，可附截图）输入的魔王语言为：B(ehnxgz)B 翻译的结果为： tsaedsaeezegexenehetsaedsae 错误模式：括号匹配错误提示。输入的魔王语言
6、为：wasjg翻译为汉语的结果为： 我爱数据结构结论：此程序能够按照给定的翻译规则解释魔王语言。五、 【实验总结】(10%)（本部分应包括：自己在实验中完成的任务，及存在的问题，所完成实验过程中的具体经验总结、心得）问题关键：1.栈的初始化，入栈出栈操作，栈为空的判断条件，队列的初始化，入队和出队操作，队列为空的判断。以及队列中最后一个元素被删除后尾指针的修改。2.主函数的操作。由于队列和栈的操作始终为同一个，所以在主函数中，采用指 针函数的调用，确保操作在同一个队列和栈上。3.一些细节处理，比如数组操作等。4.另在查阅资料时候发现：将魔王语言作为一个字符串读入进来，首先检查括号是否匹配，如果
7、不匹配就无法解释。如果匹配，然后将字符串从尾到 头依次压入栈 S 中，将栈 S 中的内容依次 弹出 压入栈 S2 中，直至遇到右括号，将其压入栈 S1 中，并将栈 S2弹出依次压入栈 S1 中，直至遇到左括号压入栈 S1 中， 这样栈 S1 中存放的内容就是匹配的第一个内重括号，将栈 S1 栈顶元素左括号弹出，将左括号下面的那个元素保存在e1 变量中，然后将其他元素弹出依次压入栈 S3 中，在将 e1 与栈 S3 中依次弹出的元素压入栈 S2 中，重复 这个过程，直至将魔王语言中所有的括号都处理完为止，所以这个思路可以处理多重括号嵌套的问题。六、思考题或【项目运作描述（Operate） 】(1
8、0%)（注：选择 C 难度的才需要填写“项目运作描述” ，其他难度的只需完成思考题）（项目运作描述应包括：项目的成本效益分析，应用效果等的分析。 ）1.栈：特点就是一个先进后出的结构。主要用途：函数调用和返回，数字转字符，表达式求值，走迷 宫等等。在 CPU 内部栈主要是用来进行子程序调用和返回，中断时数据保存和返回。在编程语言中：主要用来进行函数的调用和返回。可以 说在计算机中，只要数据的保存满足先进后出的原理，都优先考虑使用栈，所以栈是 计算机中不可缺的机制。队列：特点就是一个先进先出的结构。只要满足数据的先进先出原理就可以使用队列。2. 可以采用顺序存储结构和链式存储结构，因为他们都是线
9、性表，就像一排站在一条线上的人，位置关系是一个挨一个的，这样的顺序不会改变，而改 变点都在头或者尾，仍然保持形态不变的。七、 【代码】(10%)（本部分应包括：完整的代码及充分的注释。 注意纸质的实验报告无需包括此部分。格式统一为，字体: Georgia , 行距: 固定行距 12，字号: 小五）#include#include#include#define STACK_INIT_SIZE 50#define STACKINCREMENT 10#define OVERLOW -2#define ERROR -1typedef struct char *base;int top;int size
10、;SqStack;typedef struct char *base;int front;int rear;SqQueue;void Init_SqStack(SqStack if(!s.base) exit(OVERLOW);s.top = 0;s.size = STACK_INIT_SIZE;void Push_SqStack(SqStack s.size += STACKINCREMENT;s.bases.top = c;s.top +;int Pop_SqStack(SqStack s.top -;e = s.bases.top;return 1;char GetTop_SqStack
11、(SqStack s)return s.bases.top - 1;int IsEmpty_SqStack(SqStack s)if(s.top = 0)return 1;elsereturn 0;void Init_SqQueue(SqQueue if(!q.base)exit(OVERLOW);q.front = 0;q.rear = 0;void En_SqQueue(SqQueue q.baseq.rear = c;q.rear = (q.rear + 1) % STACK_INIT_SIZE;int De_SqQueue(SqQueue e = q.baseq.front;q.fro
12、nt = (q.front + 1) % STACK_INIT_SIZE;return 1;void Translate(char c) /打印字符printf(“%c“,c);void Reverse(char str,char strtmp)/将字符串反向int len = strlen(str);int i,t=0;for(i=len - 1;i=0;i-)strtmpt+ = stri;strtmpt = 0;int Execute(char ch, SqStack Init_SqStack(ss);char ch1100;char ch2100;char ch3100;char c1
13、,e,c;int flag=0,t = 0,i=0,len;Reverse(ch,ch1); /将输入进来的 ch 反向for(i=0;ch1i!=0;i+)Push_SqStack(s,ch1i);while(Pop_SqStack(s,e) = 1)if(flag != 0 if(GetTop_SqStack(ss) = () /遇到左括号 ( flag 加 1flag +;continue;if(e = B) /如果是字符B 就进桟Push_SqStack(s,A);Push_SqStack(s,d);Push_SqStack(s,A);Push_SqStack(s,t);else if
14、(e = A) /如果是字符 A就相对应的字符进队列En_SqQueue(q,s);En_SqQueue(q,a);En_SqQueue(q,e);else if(e = ()Push_SqStack(ss,e);flag +; /flag 每加一次，都有一个左括号,用 flag 来表示左括号的数量else if(e = )if(flag = 0)printf(“输入的括号不匹配!n“); /左括号和右括号不匹配，右括号比左括号多exit(-1);t=0;while(GetTop_SqStack(ss) != ()Pop_SqStack(ss,c);ch2t+ = c;Pop_SqStack(
15、ss,c); /弹出左括号 (flag -; /每弹出一个左括号就 flag 减少 1ch2t = 0;len = strlen(ch2);if(len = 0) /此处是处理空括号的情况continue;c1 =ch2len - 1;t = 0;for(i=0;ilen - 1;i+) /此步是对括号中的操作ch3t+ = c1;ch3t+ =ch2i;ch3t+ = c1; /对第一个字符的操作(在最后一个字符处加上第一个字符:上一步的操作时只操作到最后第二个字符)ch3t = 0;if(IsEmpty_SqStack(ss) = 1) /如果操作括号的 ss 桟里面为空，则说明处理过程结
16、束， ch3 字符串现在是标准处理好的字符串，将 ch3 字符串倒着进入原来的桟 sReverse(ch3,ch2);for(i=0;ch2i!=0;i+)Push_SqStack(s,ch2i); /进入之前操作的桟else /如果括号操作 桟 ss 不空，则将操作好的一个括号中的字符压入字符操作 桟 ss 等待下一个右括号字符 )的输入for(i=0;ch3i!=0;i+)Push_SqStack(ss,ch3i);elseEn_SqQueue(q,e);if(flag != 0)return 0;elsereturn 1;int main()char ch100;char ch1100;
17、char ch2100;char e;printf(“请输入魔王语言： “);gets(ch);SqStack s;SqQueue q;Init_SqStack(s);Init_SqQueue(q);if(Execute(ch,s,q) = 1)while(De_SqQueue(q,e) = 1)Translate(e);elseprintf(“输入的括号不匹配!“); /左括号比右括号多，不匹配/*中文解密printf(“n“);printf(“请输入魔王语言： “);gets(ch1);Init_SqStack(s);Init_SqQueue(q);Reverse(ch1,ch2);for(int i=0;ch2i!=0;i+)Push_SqStack(s,ch2i);while(Pop_SqStack(s,e) = 1)
