数据结构试验报告.docx
- 文档编号:17935407
- 上传时间:2023-08-05
- 格式:DOCX
- 页数:15
- 大小:36.69KB
数据结构试验报告.docx
《数据结构试验报告.docx》由会员分享,可在线阅读,更多相关《数据结构试验报告.docx(15页珍藏版)》请在冰点文库上搜索。
数据结构试验报告
数据结构试验报告
姓名:
陶然班级:
医电11学号:
2111201006
第一题:
试采用逻辑算式的后缀(逆波兰)表示法来实现对下列算式的计算并输出计算结果:
8+6×(24-3÷(5+6×2)-6)-12
●程序:
#include
#include
#include
#include
typedefdoubleElemType;
#definem100
structstacksq{
ElemType*stack;
inttop;
intmaxsize;
};
//对栈的一些基本函数的定义
voidinitstack(structstacksq*s,intms)//栈的初始化
{
if(ms<=0)
{
printf("ms的值非法!
\n");
exit
(1);
}
s->maxsize=ms;
s->stack=(double*)malloc(ms*sizeof(ElemType));
if(!
s->stack)
{
printf("动态存储分配失败!
\n");
exit
(1);}
s->top=-1;}
//再分配空间
voidagainmalloc(structstacksq*s)
{
ElemType*p=(double*)realloc(s->stack,2*s->maxsize*sizeof(ElemType));
if(!
p)
{
printf("存储空间用完!
\n");
exit
(1);
}
s->stack=p;
s->maxsize=2*s->maxsize;
}
voidpush(structstacksq*s,ElemTypex)//新元素进栈
{
if(s->top==s->maxsize-1)
againmalloc(s);
s->top++;
s->stack[s->top]=x;
}
ElemTypepop(structstacksq*s)//栈顶元素退栈
{
if(s->top==-1)
{
printf("栈空,无元素出栈!
\n");
exit
(1);
}
s->top--;
returns->stack[s->top+1];
}
ElemTypepeek(structstacksq*s)//读取栈顶元素
{
if(s->top==-1)
{
printf("栈空,无元素出栈!
\n");
exit
(1);
}
returns->stack[s->top];
}
intemptystack(structstacksq*s)//判断栈是否为空,是则返回1,否则返回0
{
if(s->top==-1)
return1;
else
return0;
}
intPrecedence(charop)//op是单字符
{
switch(op){//将运算符分级,分别赋矛不同的数值
case'+':
case'-':
return1;
case'*':
case'/':
return2;
case'(':
case'@':
default:
return0;
}
}
voidchange(chars1[m],chars2[m])//将中缀表达式表示为后缀表达式
{
structstacksqR;//暂存运算符
initstack(&R,5);
push(&R,'@');
inti=0,j=0;
charch;//扫描S1得到的字符
ch=s1[i];
while(ch!
='\0')
{
if(ch=='')
ch=s1[++i];//跳过空格
elseif(ch=='(')
{
push(&R,ch);
ch=s1[++i];//有左括号,存进栈
}
elseif(ch==')')//见右括号依次退栈直至左
{
while(peek(&R)!
='(')
{
s2[j++]=pop(&R);
}
pop(&R);//删除栈顶的左括号
ch=s1[++i];
}
elseif(ch=='+'||ch=='-'||ch=='*'||ch=='/')
{
charw=peek(&R);//保持R顶元素的优先级最高,且无同级
while(Precedence(w)>=Precedence(ch))
{
s2[j++]=w;
pop(&R);
w=peek(&R);
}
push(&R,ch);
ch=s1[++i];
}
else
{
if((ch<'0'||ch>'9')&&ch!
='.')//若字符即不是运算符,又不是数字或小数点字符则非法
{
printf("中缀表达式错误!
\n");
exit
(1);
}
while((ch>='0'&&ch<='9')||ch=='.')
{
s2[j++]=ch;
ch=s1[++i];
}
s2[j++]='';
}
}
ch=pop(&R);
while(ch!
='@')
{
if(ch=='(')
{
printf("表达式错误!
\n");
exit
(1);
}
else
{
s2[j++]=ch;
s2[j++]='';
ch=pop(&R);
}
}
s2[j++]='\0';//写入结束符
}
doublecompute(charstr[m])
{
structstacksqs;
doublex,y;
inti=0;
initstack(&s,5);
while(str[i])
{
if(str[i]=='')
{
i++;
continue;
}
switch(str[i])
{
case'+':
x=pop(&s)+pop(&s);
i++;
break;
case'-':
x=pop(&s);
x=pop(&s)-x;
i++;
break;
case'*':
x=pop(&s)*pop(&s);
i++;
break;
case'/':
x=pop(&s);
if(x!
=0.0)
x=pop(&s)/x;
else
{
printf("除数为0!
\n");
exit
(1);
}
i++;
break;
default:
//x保存整数部分
x=0.0;
while(str[i]>=48&&str[i]<=57)
{
x=x*10+str[i]-48;
i++;
}
if(str[i]=='.')
{
doublej=10.0;
i++;
y=0;
while(str[i]>=48&&str[i]<=57)
{
y=y+(str[i]-48)/j;//'0'=48,(str[i]-48)/j=0.(str[i])
i++;
j*=10;
x+=y;
}}}
push(&s,x);//将结果压入栈顶
}
if(emptystack(&s))
{
printf("后缀表达式格式错误!
\n");
exit
(1);
}
x=pop(&s);
if(emptystack(&s))
returnx;
else
{
printf("后缀表达式格式错误!
\n");
exit
(1);
}}
voidmain()
{
chars1[m];
chars2[m];
printf("输入中缀表达式:
\n");
scanf("%s",s1);
change(s1,s2);
printf("%f\n",compute(s2));}
●程序运行结果:
●程序设计思路:
1.难点分析:
1)如何体现运算符号之间的优先级,如何处理括号的问题
2)有连续运算时,如何确定对于该运算符号实际参与运算的元素,比如6+8*4,对于“+”,参与其运算的实际为6和“8*4=32”这两个数
3)元算符号的按运算顺序、对应于运算数字的写入
4)一定要从整数和小数两个方面来考虑,对于小数的处理要根据小数点区别对待
2.解决方法
1)定义符号之间的优先级(即precedence函数),确保在转换过程中,按照符号运算的优先级对符号排序。
2)对于括号的读取,符号优先级之间的比较,定义栈,栈的作用主要是用于临时保存数据,以便进行比较。
起到了过渡的作用。
3.程序设计的注意事项:
1)定义栈后,需要定义一系列在栈的使用上需要的函数,即栈的初始化,存储空间的动态分配,出栈,入栈,栈首元素的判断等。
2)在定义函数时,一定要注意存储空间的分配,以及栈顶指针的应用
3)输入是字符串,在字符串转换为数字等的过程中要利用阿斯科码的关系。
●心得体会:
1.对于栈的使用,进一步地体会了先进后出的优势,同时栈可以临时存放数据,在连续读取的过程中,可以进行两两比较等工作。
2.对于swith的应用,要全面考虑不同的方面,灵活用case进行划分。
3.对于该表达式转换问题,亮点是运算符号优先级的定义,以及出栈入栈的使用。
第二题:
迷宫问题
由0和1构成的n维方阵M表示一个迷宫,其中0表示通路,1表示墙壁。
迷宫入口为(1,1),出口为(n,n)。
迷宫随机产生。
试编一算法求出从入口点到出口点可沿八个方向前进进行自动寻路的递归程序,并显示所找到的路径。
●程序:
#include
#include
#include"malloc.h"
#definen5
intmaze[n+2][n+2];
intmark[n+2][n+2];
intmove[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
//intmove[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
intSeekPath(intx,inty)
/*从迷宫中坐标点(x,y)的位置寻找通向终点(m,n)的路径,
若找到则返回1,否则返回0,(x,y)的初始值通常为(1,1)*/
{
inti;
intg,h;
if((x==n)&&(y==n))return1;
for(i=0;i<8;i++)
{
/*求出下一个位置的行坐标和列坐标*/
g=x+move[i][0];
h=y+move[i][1];
/*若下一位置可通行同时没有被访问过,则从该位置起寻找*/
if((maze[g][h]==0)&&(mark[g][h]==0))
{
/*置mark数组中对应位置为1,表明已访问过*/
mark[g][h]=1;
if(SeekPath(g,h))//r2返回点
{
printf("(%d,%d),",g,h);
return1;
}
}
}//for循环结束位置
/*从当前位置(x,y)没有通向终点的路径,应返回0*/
return0;
}
voidmain(void)
{
inti,j;
printf("请输入迷宫:
\n");
for(i=0;i { for(j=0;j { scanf("%d",&maze[i][j]); } } printf("显示迷宫: \n"); for(i=0;i { for(j=0;j { printf("%d",maze[i][j]); } printf("\n"); } for(i=0;i { for(j=0;j { mark[i][j]=0; } } printf("路径为: \n"); mark[1][1]=1; if(SeekPath(1,1)) printf("(1,1)\n"); elseprintf("此迷宫无通路! \n"); } 程序运行结果: ●程序设计思路: 1.难点分析: 1)对于每一点而言,有八个行走方向可供选择 2)如何确定已走过的路线和确保不走回头路 3)迷宫四周的方格跟迷宫中的方格是不一样的,怎样将条件进行统一 4)如何将该循环进行下去,并且保证能够找到正确的路径 2.解决方法: 1)将八个行走方向建立为8*2的矩阵,实际上是用行走方向在坐标系中的相对坐标来表征该方向。 设置该数组元素进行循环来依次考察每一点各方向的行走路径 2)设置矩阵,将走过的点进行0-1标记,以确保不会走回头路 3)将表示迷宫每个点的矩阵扩大为在边界又加了一圈,均是走不通的;这样就将四周的点与迷宫中间的点进行了条件上的统一。 4)对寻路的函数加入循环 ●心得体会 该程序最关键的是循环的使用,记录路径矩阵的建立,以及表示方向的数组的建立,在这些条件都定义好之后,该问题也就迎刃而解。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 试验报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)