数据结构课程设计报告书.docx
- 文档编号:16074221
- 上传时间:2023-07-10
- 格式:DOCX
- 页数:24
- 大小:116.15KB
数据结构课程设计报告书.docx
《数据结构课程设计报告书.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计报告书.docx(24页珍藏版)》请在冰点文库上搜索。
数据结构课程设计报告书
1引言
本设计使用C语言编写程序,以栈为主体实现功能,所以首先我们要认识一下栈。
栈是限定仅在表尾进行插入或删除操作的线性表,其存取数据时按照后进先出的原则进行。
而此次课程设计就是利用栈的这一特性并结合栈的输入、输出、判空等基本操作,来实现栈的三种实际应用:
数制转换,行编辑和括号匹配。
2问题分析
2.1设计内容的分析
本次课程设计的目标是使用C语言编写一个程序,当使用者进入程序时,首先出现一个菜单项,使用者可以选择所要实现的功能,从而进入相应的程序模块:
数制转换:
进入此模块后,程序提示输入任意一个十进制数和所要转换的进制,程
序运行后得到相应进制的数据。
行编辑:
进入模块后,程序提示输入原始数据,运行时当遇到#时退格一个,当遇到
@时,清空所在行中之前的所有数据;当遇到\n时,完成前一行的输入处理,进行下一行的输入;当遇到¥时,全文输入编辑结束。
括号匹配:
进入模块后,程序提示输入所要检验的括号以#为结束符,当括号匹配不
正确时,程序输出相应的:
左右括号匹配次序不正确,左括号多于右括号,右括号多于左括号。
当左右括号匹配无误时,输出左右括号匹配正确。
2.2程序中用到的数据结构
本程序主要是运用栈的相关知识,所以为了实现上述的三种功能,需要定义栈的结构用于储存数据:
typedefcharElemType;//定义用户变量,代替char,便于以后修改ding__________________________________________________________________________________________________________________________
typedefstruct{
ElemType*base;//在栈构造之前和销毁之后,base的值为NULL
ElemType*top;//栈顶指针
intstacksize;//当前已分配的存储空间,以元素为单位
}SqStack;
实现第一个模块功能时,需要使用while语句进行栈的输入输出。
实现第二个模块功能时,需要使用while语句和swicth语句的嵌套来进行文本编辑
实现第三个模块功能时,需要使用if、else语句的多重嵌套来判断匹配
_______________________________________________________________________________________________________________________________yuju_____________________________________________________________________________________________________________________
3总体设计
3.1总体设计思路
本程序主要首先在主函数通过调用switch语句来选择需要实现的功能,从而进入相应的函数模块。
进入数值转换模块,此函数使用了两个while语句并调用了Pop、Push等栈的自定义函数来实现数据的进出栈从而将数制转换。
进入行编辑模块,此函数使用了while语句与switch语句的嵌套来判断是否是“#”、“\n”等处理字符进而处理原始数据,然后使用两个栈来储存数据,进行两次输入输出以确保数据的原始顺序不被改变。
进入括号匹配模块,此函数使用了if与else语句的多重嵌套来对输入括号匹配的检验,其中调用了Gettop、StackEmpty等栈的自定义函数。
若在主函数选择时输入错误,则需要重新输入,这时就需要添加一个返回作用的函数goto函数,使其能够返回原来的选择输入界面,当然每次实现一个功能后也需要返回重新选择,同样的使用一个goto函数。
当需要退出时,又需要在输入处设定一个特定的退出含义的数值,并加一条退出语句如return0;。
这样总体来看就需要在主函数中在switch体外加一个if的判断语句用于判断是否进入功能区域,是否需要重新输入,是否退出程序。
3.2总体模块结构图
菜单界面
进行括号匹配操作
进行行编辑操作
进行数制转化操作
图1系统模块结构图
3.3总体流程图
流程图见下页图3.3:
开始
输入选项
选择模块功能
表达式1
判断输入项
括号匹配
行编辑
数值转换
N=1
重新输入
结束
跳转返回
跳转返回
图3.3
4详细设计
4.1数值转换模块
输入任意一个十进制数将其转换成其它进制的数
4.1.1设计思路
C语言中数制转换的基本思路为:
将原始数据作为被除数,所要转换数制的基数为除数,进行长除求余并倒序输出。
首先要定义两个整形变量n、m用于存储十进制数和所要转换数制的基数,因为要长除求余,所以需要while语句来实现多次存储和输出,以n!
=0为循环条件;并且循环体中加n=n/m;语句来改变n的值。
又因为需要倒序输出,则很自然地联系到栈“后进先出”的特性,所以要定义一个栈的结构SqStackS;用于储存余数。
另外输出时考虑到十六进制与其它进制的不同,所以在输出的while语句的循环体中加一个if的判断语句以判断基数m是否为16,当m为16时,使用printf("%X",e);使之以十六进制数输出,其他数制则只需使用printf("%d",e):
既可完成功能。
4.1.2数值转换的流程图
流程图见下图4.1:
开始
输入数据
余数进栈
循环进栈
数据输出
出栈
假
真
两种输出情况:
其它进制输出
十六进制输出
换行
结束
图4.1
4.2行编辑模块
这个简单的行编辑程序的功能是:
接受用户从终端输入的程序或数据,并加以简单处理后输出到输出终端。
4.2.1设计思路
由于此模块功能是对输入的一定量的字符数据进行编辑处理,显然需要多次输入数据,那么这样就要涉及到循环语句的使用,这里暂定为while语句。
此外,还需考虑三点:
第一,输入数据要存在全文结束标志,以结束全文数据的输入;第二,输入“\n”时要从起一行输入,以符合行编辑的本意;第三,编辑中出现的“#”等带有编辑处理含义的字符要一一予以识别。
综上所述,此模块实现功能时就需要三层的嵌套,第一层为while循环,判断条件为输入字符是否为“¥”(我设定“¥”为编辑的全文结束符),内嵌的第二层while循环,循环执行条件为输入的字符不为“\n”且不为“¥”,第三层嵌套因为要用于识别一些特殊字符,需要有多种选择,则应用一个swicth语句进行筛选,使当输入“#”时退格即出栈一次,当输入“@”时退一行,即清空栈一次,其他情况则使输入的字符进栈。
另外为保证输入操作进行,则需在第一层while循环外加ch=getchar();来接受第一个字符,在第二层while循环体中swicth语句后加ch=getchar();用于接受下一个字符,最后在第一层while循环体中整个第二个while循环后加if(ch!
='$')ch=getchar();用于最外层循环的输入字符的接收。
在输出编辑好的字符时依然要使用while循环、Pop出栈函数和printf输出函数,不过考虑到栈的“后进先出”特点,需要定义两个栈来进行两次栈的进栈和出栈来保持数据的原始顺序。
此外为了突现行编辑中的行的含义,需要在第一层while循环体中输出部分的后面加if(ch=='\n')printf("\n");语句来判断是否需要换行输入。
4.2.2行编辑的流程图
流程图见下页图4.2:
开始
输入数据
是否结束全文输入
是否结束本行输入
编辑输入的数据
退行
进栈
退格
倒序输出到另一个栈
正序输出
换行
继续输入数据
换行
结束
图4.2
4.3括号匹配
假设表达式中有三种括号:
花括号、圆括号何妨括号,其嵌套顺序随意,根据函数判定会出现以下四种情况:
括号匹配次序不正确,右括号多于左括号,左括号多于右括号,括号匹配正确。
4.3.1设计思路
本模块实现的功能是检验输入的括号是否匹配,当程序接受了第一个括号后(本程序默认接受的第一个括号均为左括号),它期待着和最后一个或者是其间的一个匹配,当随后接受的第二个括号很可能不能与之匹配,它所期待的是和倒数第二个或期间的一个匹配……这样就需要先将前面未能匹配的括号储存起来,直到第n-1个括号和第n个括号匹配时,将第n-1个括号从存储中取出,在继续比较……可以看出这和栈的特点相符合,因此可以定义栈S作为储存结构。
此外为了可以检测的方便,还需要定义一个字符型的数组exp[]来暂时存储从计算机终端输入的括号符号,exp[]初始时置为空。
终端输入时可在最后加一个“#”作为输入结束符号,并用while(exp[i++]!
='#')来体现其截止输入的作用。
初始输入完毕后使用字符串专用函数求出输入的括号数量n=strlen(exp)。
完成初始终端输入后,进行括号的匹配检验:
首先,外层使用一个for语句来依次取出exp[]中的括号字符,然后再在循环体中使用if、else的嵌套来判断检验匹配情况,循环体:
if((exp[i]=='(')||(exp[i]=='[')||(exp[i]=='{'))
Push(myStack,exp[i]);//如果是左括号则进栈
elseif(exp[i]==')'&&!
StackEmpty(myStack)
&&GetTop(myStack,c)&&c=='(')
Pop(myStack,c);//在栈不空时如果是右括号且与栈顶储存的括号匹配则将栈顶括号出栈
elseif(exp[i]==')'&&!
StackEmpty(myStack)
&&GetTop(myStack,c)&&c!
='(')
{
printf("左右括号匹配次序不正确!
\n");
return;
}//在栈不空时如果是右括号但与栈顶储存的括号不匹配则输出相应提示语
elseif(exp[i]==']'&&!
StackEmpty(myStack)
&&GetTop(myStack,c)&&c=='[')
Pop(myStack,c);//在栈不空时如果是右括号且与栈顶储存的括号匹配则将栈顶括号出栈
elseif(exp[i]==']'&&!
StackEmpty(myStack)
&&GetTop(myStack,c)&&c!
='[')
{
printf("左右括号匹配次序不正确!
\n");
return;
}//在栈不空时如果是右括号但与栈顶储存的括号不匹配则输出相应提示语
elseif(exp[i]=='}'&&!
StackEmpty(myStack)
&&GetTop(myStack,c)&&c=='{')
Pop(myStack,c);//在栈不空时如果是右括号且与栈顶储存的括号匹配则将栈顶括号出栈
elseif(exp[i]=='}'&&!
StackEmpty(myStack)
&&GetTop(myStack,c)&&c!
='{')
{
printf("左右括号匹配次序不正确!
\n");
return;
}//在栈不空时如果是右括号但与栈顶储存的括号不匹配则输出相应提示语
elseif(((exp[i]==')')||(exp[i]==')')||(exp[i]=='}'))
&&StackEmpty(myStack))
{
printf("右括号多于左括号!
\n");
return;
}
}//在栈为空时如果是右括号则输出“右括号多于左括号!
”
if(!
StackEmpty(myStack))
printf("左括号多于右括号!
\n");//之前判断完毕之后都不符合,栈不为空说明一开始进栈的左括号没有与之匹配的右括号,则输出“左括号多于右括号!
”
else
printf("左右括号匹配正确!
\n");//之前判断完毕之后都不符合,栈为空说明左右括号完全匹配正确,则输出“左右括号匹配正确!
”
4.3.2括号匹配的流程图
流程图见下页图4.3:
开始
输入数据
表达式1
表达式2
数据进栈
判断式1
数据出栈
判断式2
次序不正确
结束
判断式3
数据出栈
判断式4
次序不正确
判断式5
结束
次序不正确
判栈空
判断式6
结束
右多于左
匹配正确
左多于右
结束
结束
图4.3
5运行测试
当进入程序时,会出现菜单界面便于用户选择下面所要进行的操作,详见图1,截图如下:
图1
当输入1时,进入数制转化功能模块。
按照提示语句,用户输入要转换的十进制数和所要转换数制的基数,详见图2,例如:
15和16.经过运行之后转换之后的结果为:
F,即15在十六进制下的表示形式。
并且程序自动跳转回初始的菜单界面,以便于用户的再次选择。
详见图3,截图如下:
图2
图3
当输入2时,进入行编辑功能模块。
按照提示语句,用户输入需要编辑的原始数据,加#符号退一个,加@退一行,单击回车,进行之前一行的编辑,并且光标跳至下行等待新一行的输入编辑。
当输入¥时,结束全文输入与编辑,界面跳回初始菜单。
例如:
输入xuu#’\n’时,输出为xu详见图4;接着输入hhhhh@’\n’时,输出为空行详见图5;输入cong$’\n’时,接着输出为cong详见图6。
截图如下:
图4
图5
图6
当输入3时,进入括号匹配功能模块。
按照提示语句,用户输入需要检验的一系列括号,并以#符号位输入结束符。
例如:
依次输入左花括号、左中括号、左圆括号、右中括号、右中括号、右花括号#后,程序运行结果为“括号匹配次序不正确!
”详见图7;依次输入{()}}[]#时,程序运行结果为“右括号多于左括号!
”详见图8;依次输入{[]}{#时,程序运行结果为“左括号多于右括号!
”详见图9;依次输入{[()]}[]#时,程序运行结果为“括号匹配正确!
”详见图10。
每次程序运行完毕都会自动跳转回菜单界面。
截图如下:
图7
图8
图9
图10
当输入0时,出现提示语句,并退出程序,详见图11。
截图如下:
图11
当输入其他数值时,出现“输入有误,请重新输入:
”的提示语句,并且程序跳转回输入选项处,光标等待输入。
详见图12,截图如下:
图12
6总结
本设计实现的主要功能:
此程序集结了三个模块,通过对栈结构的使用分别实现了十进制数的数制转换,对于字符文本的行编辑和对字符文本中括号匹配情况的检验三种功能。
缺点与不足:
有些功能实现的过程中存在空间使用的浪费,比如:
行编辑模块中的两个栈空间的开辟。
另外有些算法效率不高,如括号匹配模块中的多层if-else语句的嵌套。
最后就是,功能具有一定的局限性,如数制转化模块只能实现十进制到其它进制的转换,行编辑模块只能实现退格功能,括号匹配模块默认首个输入项必须为左括号等。
收获和总结:
通过这次课程设计,巩固和加深了对栈结构和相关函数知识的理解;掌握实现复杂问题的分析建模和解决方法(包括问题描述、系统分析,设计建模、代码实现、调试和结果分析等);提高了计算机分析解决问题的基本能力。
在细节问题的分析上,较以往有了很大的提高,如:
在行编辑模块处为体现出行的含义,尝试着在输出语句后加判断语句并输出一个“\n”来实现。
在括号匹配模块处,使用字符串专用函数来计算输入括号的个数等。
另外在此次设计中我大量使用了课本上的原始程序,对于书上给出标准程序有了一定的理解,并能加以改造运用,如数制转换模块和行编辑模块。
在这个课程设计中,运用到的数据结构知识主要是栈的知识。
栈在各种软件系统中,应用非常广泛。
栈的存储特性(LIFO先进后出),使得在用栈编程时,思路清晰明了。
此外,这次的课程设计进一步加强了我们运用C语言进行编程、调试、处理问题的能力,加深了我们对算法及数据结构的认识。
同时我也意识到,开发程序的早期计划要做的充分,以免出现程序完成后发现而不足带来的修改麻烦。
虽然这只是一个很小的程序,当对我们之后的影响确实会很大的。
参考文献
[1]严蔚敏,吴伟民.数据结构.北京:
清华大学出版社,2008.
[2]徐孝凯.数据结构.北京:
清华大学出版社,2006
附录
源文件:
#include"iostream"
#include"string.h"
#include"stdio.h"
#defineSTACK_INIT_SIZE100//存储空间初始分配量
#defineSTACKINCREMENT10//存储空间分配增量
#defineOK1
#defineERROR0
#defineOVERFLOW-2
#defineTRUE1
#defineFALSE0
typedefcharElemType;
typedefstruct{
ElemType*base;//在栈构造之前和销毁之后,base的值为NULL
ElemType*top;//栈顶指针
intstacksize;//当前已分配的存储空间,以元素为单位
}SqStack;
ElemTypeInitStack(SqStack&S){//构造一个空栈S
S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!
S.base)returnOVERFLOW;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}//--------------------------------------------------------------------InitStack
ElemTypeDestroyStack(SqStack&S){//销毁栈S,S不再存在
if(!
S.base)returnERROR;
S.stacksize=0;
free(S.base);
free(S.top);
returnOK;
}//-----------------------------------------------------------------DestroyStack
ElemTypeClearStack(SqStack&S){//把栈S置为空栈
if(!
S.base)returnERROR;
if(S.top==S.base)returnOK;
S.stacksize=0;
S.top=S.base;
returnOK;
}//-------------------------------------------------------------------ClearStack
ElemTypeGetTop(SqStackS,ElemType&e){//若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
if(S.top==S.base)returnERROR;
e=*(S.top-1);
returnOK;
}//-----------------------------------------------------------------------GetTop
ElemTypePush(SqStack&S,ElemTypee){//插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize){
S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!
S.base)returnOVERFLOW;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}//if
*S.top++=e;
returnOK;
}//-------------------------------------------------------------------------Push
ElemTypePop(SqStack&S,ElemType&e){
//若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
if(!
S.base)returnERROR;
if(S.top==S.base)returnERROR;
e=*--S.top;
returnOK;
}//--------------------------------------------------------------------------Pop
ElemTypeStackEmpty(SqStackS){
//若栈为空栈,则返回TUER,否则返回FALSE
if(S.top==S.base)returnTRUE;
elsereturnFALSE;
}//--------------------------------------------------------------------------StackEmpty
voidconversion();
voidLineEdit();
voidexplscorrect();
main()
{
intn;
lip:
printf("输入1进行数制转换,输入2进行行编辑,输入3进行括号匹配,输入0退出程序\n");
loop:
scanf("%d",&n);
if(n==1||n==2||n==3)
switch(n)
{
case1:
printf("开始进行数值转换:
\n");conversion();gotolip;;
case2:
printf("开始进行行编辑,请输入原始数据以$为结束符:
\n");LineEdit();gotolip;
case3:
printf("开始进行括号匹配,请输入检查项以#为结束符:
\n");explscorrect();gotolip;
}
elseif(n==0){
printf("退出程序,谢谢使用!
\n");
return0;
}
else{printf("输入有误!
请重新输入:
");
gotoloop;
}
return0;
}
voidconversion(){
intn,m;
chare;
SqStackS;
InitStack(S);
printf("输入十进制数:
");
scanf("%d",&n);
printf("输入所要转换的进制数:
");
scanf("%d",&m);
while(n){
Push
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 报告书
![提示](https://static.bingdoc.com/images/bang_tan.gif)