数据结构课程设计.docx
- 文档编号:13753504
- 上传时间:2023-06-17
- 格式:DOCX
- 页数:25
- 大小:99.99KB
数据结构课程设计.docx
《数据结构课程设计.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计.docx(25页珍藏版)》请在冰点文库上搜索。
数据结构课程设计
计算机科学与技术学院课程设计成绩单
课程名称:
数据结构课程设计
姓名
性别
学号
班级
电话
综合成绩
成绩等级
程序运行情况
(占总成绩20%)
□能正确运行□基本能正确运行□能运行但结果不完善
(20分)(15分)(10分)
程序功能完善程度
(占总成绩10%)
□完善□基本完善□不完善
(10分)(8分)(5分)
程序结构的合理性
(占总成绩10%)
□合理□基本合理□不太合理
(10分)(8分)(5分)
对问题的答辩情况
(占总成绩40%)
□概念正确有创新(40分)
□能正确回答所有问题(35分)
□基本能正确回答(30分)
□部分问题回答概念不清晰(20分)
学生的工作态度与独立工作能力
(占总成绩10%)
□工作态度认真能独立完成任务(10分)
□工作态度基本认真,独立性尚可(8分)
□工作态度和独立性较差(5分)
设计报告的规范性
(占总成绩10%)
□符合规范□基本符合规范□规范性较差
(10分)(8分)(5分)
A:
90~100分A-:
85~89分B+:
82~84分B:
78~81分B-:
75~77分
C+:
72~74分C:
68~71分C-:
64~67分D:
60~63分F:
<60分
武汉科技大学计算机科学与技术学院制表
一、概要设计
拟采用两种类型的展分别对操作数和操作符进行操作。
程序中将涉及下列两个抽象数据类型:
1、设定“操作数”的栈的抽象数据类型定义:
ADTSqStack_f{
数据对象:
D={
数据关系:
R1={<
>|
i=2,…,n}
约定
端为栈顶,
端为栈底。
基本操作:
InitStack_f(&S)
操作结果:
构造一个空栈S。
GetTop_f(&S,&e)
初始条件:
栈S已存在。
操作结果:
用e返回S的栈顶元素。
Push_f(&S,ch)
初始条件:
栈S已存在。
操作结果:
插入元素ch为新的栈顶元素。
Pop_f(&S,&e)
初始条件:
栈S已存在。
操作结果:
删除S的栈顶元素,并以e返回其值。
}ADTSqStack_f
2、设定“操作符”的栈的抽象数据类型定义:
ADTSqStack_c{
数据对象:
D={
数据关系:
R1={<
>|
i=2,…,n}
约定
端为栈顶,
端为栈底。
基本操作:
InitStack_c(&S)
操作结果:
构造一个空栈S。
GetTop_c(&S,&e)
初始条件:
栈S已存在。
操作结果:
用e返回S的栈顶元素。
Push_c(&S,ch)
初始条件:
栈S已存在。
操作结果:
插入元素ch为新的栈顶元素。
Pop_c(&S,&e)
初始条件:
栈S已存在。
操作结果:
删除S的栈顶元素,并以e返回其值。
}ADTSqStack_c
3、本程序包含六个模块
1)主程序模块
voidmain()
{
初始化;
while(命令==“继续”)
{
接受数据;
处理数据;
接受命令;
}
}
2)栈模块——实现栈抽象数据类型
3)判断运算符优先级模块——判断运算符的优先级别
4)后缀表达式转换模块——将中缀表达式转换为后缀表达式,方便操作
5)无括号表示式求值运算模块——根据后缀表达式求值,并输出中间和最终结果
6)运算结果输出模块——以正确形式输出表达式的值
二、详细设计
1、主程序中需要的全程量
#defineTTACK_INIT_SIZE100//初始分配最大空间量
#defineSTACKINCREMENT10//(默认)增补空间量
2、结点类型、指针类型
typedefstruct{
float*base;//存储实型数据元素的一位数组
float*top;//栈顶指针
intstacksize;//栈数组容量
}SqStack_f;//有序存储实型的顺序表类型
typedefstruct{
char*base;//存储字符数据元素的一位数组
char*top;//栈顶指针
intstacksize;//栈数组容量
}SqStack_c;//有序存储字符型的顺序表类型
voidInitStack_f(SqStack_f*s)
voidInitStack_f(SqStack_f*s)
//构造一个存储实型(字符型)的空栈,预设空间为100,分配失败就退出
voidGetTop_f(SqStack_f*s,float*e)
voidGetTop_c(SqStack_c*s,char*e)
//若栈s不空,则以e带值返栈顶元素,否则显示错误“ERROR”,并退出程序
voidPush_f(SqStack_f*s,floate)
voidPush_c(SqStack_c*s,chare)
//在s的栈顶插入新的栈顶元素e,若栈的当前空间已满,则追加存储空间
voidPop_f(SqStack_f*s,float*e)
voidPop_c(SqStack_c*s,char*e)
//若栈s不空,则删除栈s的栈顶元素,用e带值返回,否则退出程序
其中部分操作的伪码算法(由于比较类似,以浮点型的栈为例)
voidInitStack_f(SqStack_f*s)
{//构造一个存储实型的空栈,预设空间为100,分配失败就退出
s->base=(float*)malloc(TTACK_INIT_SIZE*sizeof(float));
if(!
s->base)
exit
(1);
s->top=s->base;
s->stacksize=TTACK_INIT_SIZE;
}
voidGetTop_f(SqStack_f*s,float*e)
{//若栈s不空,则以e带值返栈顶元素,否则显示错误“ERROR”,并退出程序
if(s->top==s->base)
{
printf("ERROR!
\n");
exit
(1);
}
*e=*(s->top-1);
}
voidPush_f(SqStack_f*s,floate)
{//在s的栈顶插入新的栈顶元素e,若栈的当前空间已满,则追加存储空间
if(s->top-s->base>=s->stacksize)
{
s->base=(float*)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float));
if(!
s->base)
{
printf("OVERFLOW!
\n");
exit
(1);
}
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}
*s->top++=e;
}
voidPop_f(SqStack_f*s,float*e)
{//若栈s不空,则删除栈s的栈顶元素,用e带值返回,否则退出程序
if(s->top==s->base)
exit
(1);
*e=*--s->top;
}
3、判断运算符优先级的算法:
算符间的优先关系如下:
+
-
*
/
(
)
#
+
>=
<
<
<
<
>
>
-
>
>=
<
<
<
>
>
*
>
>
>=
>
<
>
>
/
>
>
>
>=
<
>
>
(
<
<
<
<
<
=
)
>
>
>
>
>
>
#
<
<
<
<
<
=
伪码算法:
intprecede(charTop_char,chars1_char)
{//栈顶的运算符赋给Top_char,新读入的运算符赋给s1_char。
判断它们的优先级
//若栈顶运算符优先级高,则返回1,否则返回0
inti,pre[2];
charop[2];
op[0]=Top_char;//栈顶的运算符赋给op[0]
op[1]=s1_char;//新读入的运算符赋给op[1]
for(i=0;i<2;i++)
switch(op[i])
{
case'(':
case')':
pre[i]=0;break;//将括号的优先级设为0
case'+':
case'-':
pre[i]=1;break;//将+-运算符的优先级设为1
case'*':
case'/':
pre[i]=2;break;//将*/运算符的优先级设为2
case'^':
pre[i]=3;break;//将^运算符的优先级设为3
}
if(pre[0]>=pre[1])//栈顶元素优先级高返回1
return1;
else
return0;//否则返回0
}
4、中缀表达式转换为后缀表达式的算法:
算法过程描述:
1)首先将左括号“(”压进栈,作为栈底元素;
2)从左而右对算数表达式进行扫描,每次读入一个字符s1[i];
3)若遇到数字或小数点,则立即写入s2[i],若遇算数运算符,将“”(空格)写入s2[i];
4)遇到左括号“(”则压栈;
5)若遇算术运算符,如果它们的优先级比栈顶元素高,则直接进栈,否则弹出栈顶元素输出到s2[i],直到新栈顶元素的优先级比它低,然后将它压栈;
6)若遇到右括号“)”,则将栈顶元素输出到s2[i],直到栈顶元素为“(”,然后相互抵消;
7)当扫描到“#”符号,表明表达式串已全部输入,将栈中的运算符全部输出到s2[i],并删除栈顶元素。
伪码算法:
voidTranslate(char*s1)
{//中缀表达式转换为后缀表达式
chars2[80];
SqStack_cOptr;
inti=0,j=0;
chart;
InitStack_c(&Optr);//初始化一个存储字符型的空栈,便于存储运算符
Push_c(&Optr,'(');//首先将左括号“(”压进栈,作为栈底元素
while(s1[i]!
='#')//当扫描到的不是“#”,即表达式串没结束时
{
if(s1[i]>='0'&&s1[i]<='9'||s1[i]=='.')//若果是数字或小数点则将其输出给s2[i]
{
s2[j++]=s1[i];
if((s1[i+1]<'0'||s1[i+1]>'9')&&s1[i+1]!
='.')
s2[j++]='';
}
else
switch(s1[i])//扫描到的是运算符
{
case'(':
Push_c(&Optr,s1[i]);break;//遇到左括号“(”则压栈
case')':
Pop_c(&Optr,&t);//若遇到右括号“)”,则将栈顶元素输出到s2[i]
while(t!
='(')//直到栈顶元素为“(”,然后相互抵消
{
s2[j++]=t;
Pop_c(&Optr,&t);
}
break;
default:
while(GetTop_c(&Optr,&t),precede(t,s1[i]))
{//遇到算数运算符则比较优先级
Pop_c(&Optr,&t);//栈顶元素优先级高,则弹出到s2[i]
s2[j++]=t;
}
Push_c(&Optr,s1[i]);//栈顶元素优先级低,直接压栈
}
i++;
}
Pop_c(&Optr,&t);
while(t!
='(')//表达式串已结束,栈中的运算符全部输出到s2[i],并删除栈顶元素
{
s2[j++]=t;
Pop_c(&Optr,&t);
}
for(i=0;i s1[i]=s2[i]; s1[i]='#'; s1[i+1]='\0';//为了方便打印后缀表达式,在字符串结尾加‘\0’ } 5、表示式求值运算的算法: 算法描述: 1)读入无括号的后缀表达式; 2)若为数值和小数点则将其联合转换为浮点型后进栈(存放操作数); 3)若为运算符,让栈顶元素和次顶元素与次运算符进行相应的运算,运算结果打印并进栈; 4)重复2)3)步骤,直到输入为“#”,则此时栈中的结果便是所追求的表达式的值。 数值转换为实数的算法描述: 1)若为数字,则将其减去'0'的ASCII码后就得到该数的数值,并暂存于一个变量m上; 2)若继续为数字,也将其减去'0'的ASCII码后就得到该数的数值,并将其值加上已存的m*10后的值再存于m; 3)重复2)步骤直到遇到小数点,从小数点后的数开始,在重复2)步骤的通知,也记下小数点后的位数n; 4)当遇到“”(空格)后,即表示此轮需转换的数已读入完毕,则将m除以10的你次方,则此时的之记为转换后的实数。 伪码算法: voidCalculate(SqStack_f*s,char*s2) { floatm,x,y,z; inti=0,j=0; while(s2[i]! ='#')//读入后缀表达式直到“#”符号为止 { if(s2[i]>='0'&&s2[i]<='9'||s2[i]=='.')//若为数值和小数点 //则将其联合转换为浮点型后进栈 {//数值转换为实数 m=0; while(s2[i]! =''&&s2[i]! ='.')//读入的只为数字 m=m*10+(float)(s2[i++]-'0');//转换为十进制的整数 if(s2[i]=='.')//遇到小数点后 { j=0;i++; while(s2[i]! ='') { m=m*10+(float)(s2[i++]-'0');//转换为十进制的整数 j++;//记录小数点后的位数 } while(j>0)//转换为实数 { m/=10; j--; } } i++; Push_f(s,m); GetTop_f(s,&m); printf("Theresultis: %g\n",m); } else//读入的为运算符 { Pop_f(s,&x);//弹出栈顶元素 Pop_f(s,&y);//弹出次顶元素 switch(s2[i]) {//让栈顶和次顶元素与次运算符进行相应的运算,运算结果打印并进栈 case'+': z=y+x;printf("Theresultis: %g\n",z);break; case'-': z=y-x;printf("Theresultis: %g\n",z);break; case'*': z=y*x;printf("Theresultis: %g\n",z);break; case'/': if(x==0) {//报错功能 printf("表达式出错,除数为‘0’,无意义\n"); exit (1); } else { z=y/x; printf("Theresultis: %g\n",z);break; } case'^': z=1;for(j=1;j<=x;j++) {//乘方的运算 z=z*y; printf("Theresultis: %g\n",z); } } Push_f(s,z); i++; } } } 6、结果输出的伪码算法: voidresult(SqStack_f*s) { floatv; GetTop_f(s,&v); printf("Thefinalresultis: %g\n",v);//以合适的形式输出结果,省去不必要的小数点 } 7、主程序的伪码算法: voidmain() { SqStack_fstack; charstr[80],c='Y'; while(c=='y'||c=='Y')//判断是否继续本程序 { printf("请输入算术表达式[本程序支持实数的加减乘除乘方运算],结束前请输入‘#’号! \n"); gets(str);//输入表达式 InitStack_f(&stack);//初始化一个存储运算结果(实型)的栈 Translate(str);//调用“中缀表达式转换为后缀表达式函数” printf("转化后的后缀表达式为: \n");//检验后缀表达式是否转换正确 puts(str);//输出后缀表达式 Calculate(&stack,str);//计算无括号表达式的值 result(&stack);//调用“结果输出函数” printf("你想继续吗? 'Y'或'y'为继续,其余为退出程序\n");//增加程序的连续输入功能 c=getchar(); getchar();//吞噬掉输入判断符后的‘\n’ } } 三、测试结果 四、附录 “表达式求值”源程序代码: #include #include #include #defineTTACK_INIT_SIZE100 #defineSTACKINCREMENT10 typedefstruct{ float*base; float*top; intstacksize; }SqStack_f; typedefstruct{ char*base; char*top; intstacksize; }SqStack_c; voidInitStack_f(SqStack_f*s) { s->base=(float*)malloc(TTACK_INIT_SIZE*sizeof(float)); if(! s->base) exit (1); s->top=s->base; s->stacksize=TTACK_INIT_SIZE; } voidInitStack_c(SqStack_c*s) { s->base=(char*)malloc(TTACK_INIT_SIZE*sizeof(char)); if(! s->base) exit (1); s->top=s->base; s->stacksize=TTACK_INIT_SIZE; } voidGetTop_f(SqStack_f*s,float*e) { if(s->top==s->base) { printf("ERROR! \n"); exit (1); } *e=*(s->top-1); } voidGetTop_c(SqStack_c*s,char*e) { if(s->top==s->base) { printf("ERROR! \n"); exit (1); } *e=*(s->top-1); } voidPush_f(SqStack_f*s,floate) { if(s->top-s->base>=s->stacksize) { s->base=(float*)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float)); if(! s->base) { printf("OVERFLOW! \n"); exit (1); } s->top=s->base+s->stacksize; s->stacksize+=STACKINCREMENT; } *s->top++=e; } voidPush_c(SqStack_c*s,chare) { if(s->top-s->base>=s->stacksize) { s->base=(char*)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char)); if(! s->base) { printf("OVERFLOW! \n"); exit (1); } s->top=s->base+s->stacksize; s->stacksize+=STACKINCREMENT; } *s->top++=e; } voidPop_f(SqStack_f*s,float*e) { if(s->top==s->base) exit (1); *e=*--s->top; } voidPop_c(SqStack_c*s,char*e) { if(s->top==s->base) exit (1); *e=*--s->top; } intprecede(charTop_char,chars1_char) { inti,pre[2]; charop[2]; op[0]=Top_char; op[1]=s1_char; for(i=0;i<2;i++) switch(op[i]) { case'(': case')': pre[i]=0;break; case'+': case'-': pre[i]=1;break; case'*': case'/': pre[i]=2;break; case'^': pre[i]=3;break; } if(pre[0]>=pre[1]) return1; else return0; } voidTranslate(char*s1) { chars2[80]; SqStack_cOptr; inti=0,j=0; chart; InitStack_c(&Optr); Push_c(&Optr,'('); while(s1[i]! ='#') { if(s1[i]>='0'&&s1[i]<='9'||s1[i]=='.') { s2[j++]=s1[i]; if((s1[i+1]<
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计