《云南大学软件学院大数据结构实验3》由会员分享，可在线阅读，更多相关《云南大学软件学院大数据结构实验3（12页珍藏版）》请在金锄头文库上搜索。
1、实验难度： A B 学 期：2017秋季学期任课教师:实验题目：组员及组长:承担工作：联系电话：电子邮件：完成提交时间：年月一、【实验构思(Conceive)】(10%)(本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程 序设计等相关知识，对问题进行概要性地分析)魔王语言的解释规则：B -*tAdA ； A sae ； (elmxgz) ezegexenehe则魔王语言 B(eluixgz)B 解释成Isa 匕 dsatxz 巳大写字母表示魔王语言的词汇，小写字母表示人的词汇语言 ,魔王语言中可以包 含括号，魔王语言的产生式规则在程序中给定，当接收用户输入的合法的魔王语
2、言时， 通过调用魔王语言翻译函数来实现翻译。在 A 的基础上，(根据产生式)自定义规则，将一段魔王的话翻译为有意义的人 类语言(中文)：输入wasjg，则魔王语言解释为“我爱数据结构”运用了离散数学的一些基本知识及程序设计知识。二、【实验设计(Design)】 (20%)(本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块 间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功 能说明等)/抽象数据类型的定义/#define STACK_INIT_SIZE 50#define STACKINCREMENT 10#define OVERLOW -2#de
3、fine 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， char &e) /出桟ch
4、ar GetTop_SqStack(SqStack s)/或得栈顶int IsEmpty_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, SqQueue & q
5、)/魔王语言操作 调用关系：Main)函数输入魔王吋M初始化栈初始化队列翻译魔王语言三、【实现(Implement)】(30%)(本部分应包括：抽象数据类型各操作的具体实现代码、 关键操作的具体算法实现、 函数实现，主程序实现等，并给出关键算法的时间复杂度分析。如有界面则需包括界 面的关键实现方法等。)主程序模块：int main()char ch100;char ch1100;char ch2100;char e;/*英文解密printf(请输入魔王语言：)；gets(ch);SqStack s；SqQueue q；Init_SqStack(s)；Init_SqQueue(q)；if(Exe
6、cute(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(我)； break；casea:pr
7、intf (爱“)； break；cases:printf(数据”)； break；casej:printf (结“)； break；caseg:printf (构“)； break；return 0；其他函数实现代码见七、【代码】部分。时间复杂复分析：o（n）。四、【测试结果（Testing）】（10%）（本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析，可附截图）D:IDEcodebl0ckc4- +_code 王语言巳站输入魔王语言：B(ehbxgz)Bsaedsaeezegexebehetsaedsae请输入魔王讥言:wasjg我爱数据
8、结构Process :rEturned 0 (0x0)execution timE : 15. 150 sPress any key to continue.D:IDEcodeblockc+ +_cod 已幢王语言.exeI请输入魔I沁:B(ehbxgz)B；输入的拆号不匹配！|请输入魔语用输入的魔王语言为：B(ehnxgz)B翻译的结果为： tsaedsaeezegexenehetsaedsae 错误模式：括号匹配错误提示。输入的魔王语言为： wasjg翻译为汉语的结果为： 我爱数据结构 结论：此程序能够按照给定的翻译规则解释魔王语言。五、【实验总结】(10%) (本部分应包括：自己在实验中
9、完成的任务，及存在的问题，所完成实验过程中的具 体经验总结、心得)问题关键：1. 栈的初始化，入栈出栈操作，栈为空的判断条件，队列的初始化，入队和出队 操作，队列为空的判断。以及队列中最后一个元素被删除后尾指针的修改。2. 主函数的操作。由于队列和栈的操作始终为同一个，所以在主函数中，采用指 针函数的调用，确保操作在同一个队列和栈上。3. 一些细节处理，比如数组操作等。4. 另在查阅资料时候发现：将魔王语言作为一个字符串读入进来，首先检查括号 是否匹配，如果不匹配就无法解释。如果匹配，然后将字符串从尾到头依次压入栈 S 中，将栈S中的内容依次弹出压入栈S2中，直至遇到右括号，将其压入栈S1中，
10、并将栈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 Init_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;
14、s.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_INIT_SIZE); if(!q.base)exit(OVERLOW);q.front = 0;q.rear = 0;
