云南大学软件学院数据结构实验.docx
《云南大学软件学院数据结构实验.docx》由会员分享,可在线阅读,更多相关《云南大学软件学院数据结构实验.docx(18页珍藏版)》请在冰点文库上搜索。
云南大学软件学院数据结构实验
云南大学软件学院数据结构实验报告
实验难度:
A□B□C□
序号
学号
姓名
成绩
指导教师
(签名)
学 期:
2017秋季学期
任课教师:
实验题目:
组员及组长:
承担工作:
联系电话:
电子邮件:
完成提交时间:
年月日
一、【实验构思(Conceive)】(10%)
(本部分应包括:
描述实验实现的基本思路,包括所用到的离散数学、工程数学、程序设计等相关知识,对问题进行概要性地分析)
魔王语言的解释规则:
大写字母表示魔王语言的词汇,小写字母表示人的词汇语言,魔王语言中可以包含括号,魔王语言的产生式规则在程序中给定,当接收用户输入的合法的魔王语言时,通过调用魔王语言翻译函数来实现翻译。
在A的基础上,(根据产生式)自定义规则,将一段魔王的话翻译为有意义的人类语言(中文):
输入wasjg,则魔王语言解释为“我爱数据结构”。
运用了离散数学的一些基本知识及程序设计知识。
二、【实验设计(Design)】(20%)
(本部分应包括:
抽象数据类型的定义和基本操作说明,程序包含的模块以及各模块间的调用关系,关键算法伪码描述及程序流程图等,如有界面则需包括界面设计,功能说明等)
//---------------抽象数据类型的定义------------------//
#defineSTACK_INIT_SIZE50
#defineSTACKINCREMENT10
#defineOVERLOW-2
#defineERROR-1
typedefstruct{
char*base;//顺序栈的栈底指针
inttop;//顺序栈的栈顶
intsize;//栈元素空间的大小
}SqStack;//结构体类型顺序栈
typedefstruct{
char*base;
intfront;
intrear;
}SqQueue;//结构体类型队列
//---------------各个模块功能的描述------------------//
voidInit_SqStack(SqStack&s)//初始化顺序桟
voidPush_SqStack(SqStack&s,charc)//压入数据
intPop_SqStack(SqStack&s,char&e)//出桟
charGetTop_SqStack(SqStacks)//或得栈顶
intIsEmpty_SqStack(SqStacks)//判断是否空栈
voidInit_SqQueue(SqQueue&q)//初始化
voidEn_SqQueue(SqQueue&q,charc)//进队列
intDe_SqQueue(SqQueue&q,char&e)//出队列
voidTranslate(charc)//打印字符
voidReverse(charstr[],charstrtmp[])//将字符串反向
intExecute(charch[],SqStack&s,SqQueue&q)//魔王语言操作
调用关系:
三、【实现(Implement)】(30%)
(本部分应包括:
抽象数据类型各操作的具体实现代码、关键操作的具体算法实现、函数实现,主程序实现等,并给出关键算法的时间复杂度分析。
如有界面则需包括界面的关键实现方法等。
)
主程序模块:
intmain()
{
charch[100];
charch1[100];
charch2[100];
chare;
//********************************************************英文解密
printf("请输入魔王语言:
");
gets(ch);
SqStacks;
SqQueueq;
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(inti=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;
}
}
}
return0;
}
其他函数实现代码见七、【代码】部分。
时间复杂复分析:
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
#defineSTACK_INIT_SIZE50
#defineSTACKINCREMENT10
#defineOVERLOW-2
#defineERROR-1
typedefstruct{
char*base;
inttop;
intsize;
}SqStack;
typedefstruct{
char*base;
intfront;
intrear;
}SqQueue;
voidInit_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;
}
voidPush_SqStack(SqStack&s,charc)//压入数据
{
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++;
}
intPop_SqStack(SqStack&s,char&e)//出桟
{
if(s.top==0)
return0;
s.top--;
e=s.base[s.top];
return1;
}
charGetTop_SqStack(SqStacks)
{
returns.base[s.top-1];
}
intIsEmpty_SqStack(SqStacks)
{
if(s.top==0)
return1;
else
return0;
}
voidInit_SqQueue(SqQueue&q)//初始化
{
q.base=(char*)malloc(sizeof(char)*STACK_INIT_SIZE);
if(!
q.base)
exit(OVERLOW);
q.front=0;
q.rear=0;
}
voidEn_SqQueue(SqQueue&q,charc)//进队列
{
if((q.rear+1)%STACK_INIT_SIZE==q.front)exit(ERROR);
q.base[q.rear]=c;
q.rear=(q.rear+1)%STACK_INIT_SIZE;
}
intDe_SqQueue(SqQueue&q,char&e)//出队列
{
if(q.front==q.rear)
return0;
e=q.base[q.front];
q.front=(q.front+1)%STACK_INIT_SIZE;
return1;
}
voidTranslate(charc)//打印字符
{
printf("%c",c);
}
voidReverse(charstr[],charstrtmp[])//将字符串反向
{
intlen=strlen(str);
inti,t=0;
for(i=len-1;i>=0;i--)
strtmp[t++]=str[i];
strtmp[t]='\0';
}
intExecute(charch[],SqStack&s,SqQueue&q)
{
SqStackss;
Init_SqStack(ss);
charch1[100];
charch2[100];
charch3[100];
charc1,e,c;
intflag=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');
}
elseif(e=='A')//如果是字符'A'就相对应的字符进队列
{
En_SqQueue(q,'s');
En_SqQueue(q,'a');
En_SqQueue(q,'e');
}
elseif(e=='(')
{
Push_SqStack(ss,e);
flag++;//flag每加一次,都有一个左括号,用flag来表示左括号的数量
}
elseif(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;i{
ch3[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)
return0;
else
return1;
}
intmain()
{
charch[100];
charch1[100];
charch2[100];
chare;
printf("请输入魔王语言:
");
gets(ch);
SqStacks;
SqQueueq;
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(inti=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;
}
}
}
return0;
}