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

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