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

1、实验难度：A B C 序号学号姓名成绩指导教师（签名）学 期：2017秋季学期任课教师：实验题目：组员及组长:承担工作：联系电话：电子邮件:完成提交时间：年 月 日一、【实验构思(Conceive )】(10%)(本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程 序设计等相关知识，对问题进行概要性地分析)魔王语言的解释规则：B tAdA ； sae ； (cluixgz) _* ezegexenehe贝lj盧王语百解释成UnegzzugCK切灯hWMchaj大写字母表示魔王语言的词汇，小写字母表示人的词汇语言，魔王语言中可以包含括号，魔王语言的产生式规则在程序中给定，当

2、接收用户输入的合法的魔王语言时， 通过调用魔王语言翻译函数来实现翻译。在A的基础上，(根据产生式)自定义规则，将一段魔王的话翻译为有意义的人 类语言(中文)：输入wasjg,则魔王语言解释为“我爱数据结构”。运用了离散数学的一些基本知识及程序设计知识。二、【实验设计(Design)】(20%)(本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块 间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功 能说明等)/ 抽象数据类型的定义 /#define STACK_INIT_SIZE 50#define STACKINCREMENT 10#define

3、OVERLOW -2#define ERROR -1typedef struct char *base; /顺序栈的栈底指针int top; / 顺序栈的栈顶int size; /栈元素空间的大小SqStack; / 结构体类型顺序栈typedef struct char *base;int front;int rear;SqQueue; /结构体类型队列/ 各个模块功能的描述/void Init_SqStack(SqStack & s) /初始化顺序桟void Push_SqStack(SqStack &s, char c) /压入数据int Pop_SqStack(SqStack &s,

4、char &e) /出桟char GetTop_SqStack(SqStack s)/或得栈顶int lsEmpty_SqStack(SqStack s)/判断是否空栈void Init_SqQueue(SqQueue & q)初始化void En_SqQueue(SqQueue &q, char c)/进队歹int De_SqQueue(SqQueue &q, char & e) / 出队列 void Translate(char c) / 打印字符void Reverse(char str,char strtmp)/将字符串反向int Execute(char ch, SqStack &s

5、, SqQueue & q)魔王语言操作调用关系：初始化栈初始化从列进仃魔卫语言的操作出队列逬栈出栈操作将魔王语言翻详再中文三、【实现(Implement)】(30%)(本部分应包括：抽象数据类型各操作的 具体实现代码、关键操作的具体算法实现、 函数实现，主程序实现等，并给出关键算法的时间复杂度分析。如有界面则需包括界面的关键实现方法等。)主程序模块：int main()char ch100;char ch1100;char ch2100;char e;/* printf(”请输入魔王语言：);gets(ch);SqStack s;SqQueue q;lnit_SqStack(s);Init_

6、SqQueue(q);if(Execute(ch,s,q) = 1)英文解密while(De_SqQueue(q,e) = 1)Translate(e);不匹配 中文解密elseprintf(”输入的括号不匹配！)； /左括号比右括号多,*printf(n);printf(请输入魔王语言：);gets(chl);lnit_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(我

7、);break;casea:printf(爱)；break;cases:printf(数据);break;casej:printf(结);break;caseg:printf(构);break;return 0;其他函数实现代码见七、【代码】部分。时间复杂复分析：o(n)。四、【测试结果（Testing ）】（10%）（本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析，可附截图）a D:IDEcodebl o 匚 kc+_codeMBS-2.exe请输入魔王语言:B(ehbxgz)Btsaedsaeezegexebehetsaedsae 谙输入

8、魔王语言：wasjg我爱数据结构Process returned 0 (0x0) execution time : 15.150 s Press anv kev to continue. D:IDEcodeblockc + + codeHiiB.exe浦输入魔王语言:B(ehbxgz)B；输入的话号不匹配！谱输入歳工语言:输入的魔王语言为：B(eh nxgz)B翻译的结果为： tsaedsaeezegexe nehetsaedsae错误模式：括号匹配错误提示。输入的魔王语言为：wasjg翻译为汉语的结果为：我爱数据结构结论：此程序能够按照给定的翻译规则解释魔王语言。五、【实验总结】(10%)(

9、本部分应包括：自己在实验中完成的任务，及存在的问题，所完成实验过程中的具体经验总结、心得)问题关键：1. 栈的初始化，入栈出栈操作，栈为空的判断条件，队列的初始化，入队和出队操作，队列为空的判断。以及队列中最后一个元素被删除后尾指针的修改。2. 主函数的操作。由于队列和栈的操作始终为同一个，所以在主函数中，采用指针函数的调用，确保操作在同一个队列和栈上。3. 一些细节处理，比如数组操作等。4. 另在查阅资料时候发现：将魔王语言作为一个字符串读入进来，首先检查括号是否匹配，如果不匹配就无法解释。如果匹配，然后将字符串从尾到头依次压入栈S中，将栈S中的内容依次弹出压入栈 S2中，直至遇到右括号，将

10、其压入栈 S1中，并将栈S2弹出依次压入栈S1中，直至遇到左括号压入栈S1中，这样栈S1中存放的内 容就是匹配的第一个内重括号，将栈S1栈顶元素左括号弹出，将左括号下面的那个元素保存在el变量中，然后将其他元素弹出依次压入栈 S3中，在将el与栈S3中依 次弹出的元素压入栈S2中，重复这个过程，直至将魔王语言中所有的括号都处理完 为止，所以这个思路可以处理多重括号嵌套的问题。六、思考题或【项目运作描述（Operate ）】（10%）（注：选择C难度的才需要填写“项目运作描述”，其他难度的只需完成思考题）（项目运作描述应包括：项目的成本效益分析，应用效果等的分析。）1. 栈：特点就是一个先进后出

11、的结构。主要用途：函数调用和返回，数字转字符，表达式求值，走迷宫等等。在CPU内部栈主要是用来进行子程序调用和返回，中断时数据保存和返回。在编程语言中：主 要用来进行函数的调用和返回。可以说在计算机中，只要数据的保存满足先进后出的 原理，都优先考虑使用栈，所以栈是计算机中不可缺的机制。队列：特点就是一个先进先出的结构。只要满足数据的先进先出原理就可以使用 队列。2. 可以采用顺序存储结构和链式存储结构，因为他们都是线性表，就像一排站 在一条线上的人，位置关系是一个挨一个的，这样的顺序不会改变，而改变点都在头 或者尾，仍然保持形态不变的。七、【代码】（10%）（本部分应包括：完整的代码及充分的注

12、释。注意纸质的实验报告无需包括此部分。格式统一为，字体：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;SqStack;typedef struct char *base;int front;int rear;SqQueue;void lnit_SqStack(SqStack & s) /初

13、始化顺序桟s.base = (char *)malloc(sizeof(char) * STACK_INIT_SIZE);if(!s.base) exit(OVERLOW);s.top = 0;s.size = STACK_INIT_SIZE;void Push_SqStack(SqStack &s, char c) /压入数据if(s.top = s.size)s.base = (char *)realloc(s.base,(sizeof(char) * (s.size + STACKINCREMENT); s.size += STACKINCREMENT;s.bases.top = c;s

14、.top +;int Pop_SqStack(SqStack &s, char &e) /出桟if(s.top = 0)return 0;s.top -;e = s.bases.top;return 1;char GetTop_SqStack(SqStack s)return s.bases.top - 1;int IsEmpty_SqStack(SqStack s)if(s.top = 0)return 1;elsereturn 0;void Init_SqQueue(SqQueue & q)初始化q.base = (char *)malloc(sizeof(char) * STACK_IN

15、IT_SIZE);if(!q.base)exit(OVERLOW);q.front = 0;q.rear = 0;void En_SqQueue(SqQueue &q, char c)进队歹if(q.rear + 1) % STACK_INIT_SIZE = q.front) exit(ERROR);q.baseq.rear = c;q.rear = (q.rear + 1) % STACK_INIT_SIZE;int De_SqQueue(SqQueue &q, char & e) / 出队列if(q.front = q.rear)return 0;e = q.baseq.front;q.f

16、ront = (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 &s, SqQueue &q)SqStack ss;Init_SqStack(ss);char ch1100;char

17、 ch2100;char ch3100;char c1,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 & e != ) /此处是为了将找到第一个左括号之后的字符全部进入括号操作桟ss中Push_SqStack(ss,e);if(GetTop_SqStack(ss) = () /遇到左括号(flag力口 1flag +;continue;if(e = B) /如果是字符B就进

18、桟Push_SqStack(s,A);Push_SqStack(s,d);Push_SqStack(s,A);Push_SqStack(s,t);else if(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 =) printf(” exit(-1);if(flag = 0)输入的括号不匹配!n); /左括号和右括号不匹配，右括号比

19、左括号多 t=0;while(GetTop_SqStack(ss) !=() Pop_SqStack(ss,c); ch2t+ = c;Pop_SqStack(ss,c); / flag -;/ch2t = 0;len = strlen(ch2);if(len = 0)/continue;cl =ch2len - 1;t = 0;for(i=0;ilen - 1;i+) /ch3t+ = c1;ch3t+ =ch2i;ch3t+= c1; /作到最后第二个字符)弹岀左括号(每弹岀一个左括号就flag减少1此处是处理空括号的情况此步是对括号中的操作对第一个字符的操作(在最后一个字符处加上第一个字符：上一步的操作时只操ch3t = 0;if(lsEmpty_SqStack(ss) = 1) /如果操作括号的ss桟里面为空，则说明处理过程结束，ch3字符串现在是标准处理好的字符串，将ch3字符串倒着进入原来的桟sReverse(ch3,ch2);for(i=0;ch2i!=0;i+)Push_SqStack(s,ch2i); /进入之前操作的桟else /如果括号操作 桟ss不空，则将操作好的一个括