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

实验难度： A □ B □ C □

序号 指导教师 学号 姓名 成绩 （签名）

学 期： 2017秋季学期 任课教师: 实验题目: 组员及组长:

承担工作： 联系电话: 电子邮件: 完成提交时间： 年 月 日

.

.

一、【实验构思（Conceive）】(10%)

（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计等相关知识，对问题进行概要性地分析）

魔王语言的解释规则：

大写字母表示魔王语言的词汇，小写字母表示人的词汇语言,魔王语言中可以包含括号，魔王语言的产生式规则在程序中给定，当接收用户输入的合法的魔王语言时，通过调用魔王语言翻译函数来实现翻译。

在 A 的基础上，（根据产生式）自定义规则，将一段魔王的话翻译为有意义的人类语言（中文）：输入wasjg,则魔王语言解释为“我爱数据结构”。

运用了离散数学的一些基本知识及程序设计知识。 二、【实验设计(Design)】(20%)

（本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功能说明等）

//---------------抽象数据类型的定义------------------// #define STACK_INIT_SIZE 50 #define STACKINCREMENT 10 #define OVERLOW -2 #define ERROR -1 typedef 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 ch[100]; char ch1[100]; char ch2[100]; 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;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; } } }

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 -1

typedef 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.base[s.top] = c; s.top ++; }

int Pop_SqStack(SqStack &s, char &e) //出桟 {

if(s.top == 0) return 0; s.top --;

e = s.base[s.top]; return 1; }

char GetTop_SqStack(SqStack s) {

return s.base[s.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.base[q.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.base[q.front];

q.front = (q.front + 1) % STACK_INIT_SIZE; return 1; }

void Translate(char c) //打印字符 {

printf(\"%c\}

void Reverse(char str[],char strtmp[])//将字符串反向 {

int len = strlen(str); int i,t=0;

for(i=len - 1;i>=0;i--) strtmp[t++] = str[i]; strtmp[t] = '\\0'; }

int Execute(char ch[], SqStack &s, SqQueue &q) {

SqStack ss;

Init_SqStack(ss); char ch1[100]; char ch2[100]; char ch3[100]; char c1,e,c;

int flag=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) == '(') //遇到左括号 '(' 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); ch2[t++] = c; }

Pop_SqStack(ss,c); //弹出左括号 '('

flag --; //每弹出一个左括号就flag减少 1 ch2[t] = '\\0';

len = strlen(ch2);

if(len == 0) //此处是处理空括号的情况 continue; c1 =ch2[len - 1]; t = 0;

for(i=0;ich3[t++] = c1; ch3[t++] =ch2[i]; }

ch3[t++] = c1; //对第一个字符的操作(在最后一个字符处加上第一个字符:上一步的操作时只操作到最后第二个字符)

ch3[t] = '\\0';

if(IsEmpty_SqStack(ss) == 1) //如果操作括号的ss桟里面为空，则说明处理过程结束， ch3字符串现在是标准处理好的字符串，将ch3字符串倒着进入原来的桟s {

Reverse(ch3,ch2);

for(i=0;ch2[i]!='\\0';i++)

.

.

{

Push_SqStack(s,ch2[i]); //进入之前操作的桟 } }

else //如果括号操作 桟ss 不空，则将操作好的一个括号中的字符压入字符操作 桟ss 等待下一个右括号字符 ')'的输入 {

for(i=0;ch3[i]!='\\0';i++) {

Push_SqStack(ss,ch3[i]); } } } else

En_SqQueue(q,e); }

if(flag != 0) return 0; else

return 1; }

int main() {

char ch[100]; char ch1[100]; char ch2[100]; 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;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; } } }

return 0; }

.