数据结构实训.docx
《数据结构实训.docx》由会员分享，可在线阅读，更多相关《数据结构实训.docx（63页珍藏版）》请在冰点文库上搜索。
数据结构实训
高职学院
计算机专业类
课程设计报告
（2012-2013学年第1学期）
课程设计类型：
数据结构
题目：
栈+串+队列+线性表+后缀表达式求值
学号：
姓名：
专业：
计算机应用技术
指导教师：
课程设计日期：
2012.12.17~2012.12.21
高职学院制
1.问题分析
1.1问题描述
1.栈子系统
（1）设计一个字符型的链栈。
（2）编写进栈、出栈、显示栈中全部元素的程序。
（3）编写一个把十进制整数转换成二进制数的应用程序。
（4）编写一个把中缀表达式转换成后缀表达式（逆波兰式）的应用程序。
（5）设计一个选择式菜单，以菜单方式选择上述操作。
2.串子系统
（1）由用户通过键盘输入建立一个字符串。
（2）编写插入、删除、查找、比较、取子字符串、连接字符串、显示、模式匹配等程序。
（3）设计如下所示的选择式菜单，以菜单方式选择上述操作。
3.队列子系统
（1）掌握队列的特点及其描述方法。
（2）用链式结构实现一个队列。
（3）掌握队列的各种基本操作。
（4）掌握队列的简单应用程序。
4.线性表子系统
（1）用结构体描述一个字符型的单项列表。
（2）创建线性表；在线性表中插入元素、删除元素；显示线性表中所有元素等基本操作。
（3）用if语句设计一个选择式菜单。
5.后缀表达式求助子系统
（1）后缀表达式求值子系统。
（2）用键盘输入一个整数后缀表达式（操作数的范围是0~9，运算符只含+、—、*、/、，而且中间不可以有空格），使用循环程序从左向右读入表达式。
（3）如果读入的是操作数，直接进入操作数栈。
（4）如果读入的是运算符，立即从操作数栈取出所需的操作数，计算操作数运算的值，并将计算结果存回操作数栈。
（5）检验程序运行结果。
1.2要求分析
1.栈子系统：
使用栈的基本算法。
2.串子系统：
使用串的基本算法。
3.队列子系统：
使用队列的基本算法。
4.线性表子系统：
使用线性表的基本算法。
5.后缀表达式求值子系统：
利用栈进行计算
2.总体设计
2.1功能分析
1.栈子系统
栈的基本操作
2.串子系统
串的基本操作
3.队列子系统
队列的基本操作
4.线性表子系统
线性表的基本操作
5.后缀表达式求值子系统
对后缀表达式进行求值
3.详细设计
3.1程序结构图
3.2程序流程图
4.功能测试
4.1本系统的主界面
4.2栈子系统界面
1.输入选项‘1’,进入“栈子系统”
2.输入选项‘1’，选择“进栈”功能
3.输入选项‘2’，选择“出栈”功能
4.输入选项‘3’，选择“显示”功能
5.输入选项‘4’，选择“数值转换”功能
6.输入选项‘5’，选择“逆波兰式”功能
7.输入选项‘0’，选择“退出”功能
4.3串子系统界面
1.输入‘1’，进入“串子系统”
2.输入‘1’，选择“输入字串”功能
3.输入‘2’，选择“连接字串”功能
4.输入‘3’，选择“取出字串”功能
5.输入‘4’，选择“删除字串”功能
6.输入‘5’，选择“插入字串”功能
7.输入‘6’，选择“查找字串”功能
8.输入‘7’，选择“比较串大小”功能
9.输入‘8’，选择“显示字串”功能
10.输入‘0’，选择“退出”功能
4.4队列子系统界面
1.输入‘1’，进入“队列子系统”
2.输入‘1’，选择“进队”功能
3.输入‘2’，选择“出队”功能
4.输入‘3’，选择“读队头元素”功能
5.输入‘4’，选择“显示”功能
6.输入‘5’，选择“双队列”功能
7.输入‘0’，选择“退出”功能
4.5线性表子系统界面
1.输入‘1’，进入“线性表系统”
2.输入‘1’，选择“建表”功能
3.输入‘2’，选择“插入”功能
4.输入‘3’，选择“删除”功能
5.输入‘4’，选择“显示”功能
6.输入‘5’，选择“查找”功能
7.输入‘6’，选择“求表长”功能
8.输入‘0’，选择“退出”功能
4.6后缀表达式求值子系统界面
1.输入‘5’，进入“后缀表达式求值子系统”
2.选择界面
4.7退出系统
1.输入选项‘0’，选择“退出”功能，此功能下可以退出并关闭本程序
5.课程设计小结
在这次课程设计之前总觉得自己学的还可以。
但通过这次的课程设计让自己知道了自己有许多不懂的地方和还需要学习的知识点。
当然在这次课程中也遇到许多的困难尤其是在编完程序后调试遇到的困难令我难忘。
通过这次课程设计也让我认识到了自己实践自己编程、自己调试的重要性。
通过自己动手实践不仅可以增强自己自己的动手实践能力也可以加深自己对数据结构算法的理解。
对我们学好数据结构这门课程具有很大的意义。
除此之外我和认识到了和同学之间的合作的重要性。
通过讨论不仅可以融洽同学之间的关系也可以更好的得出结论在调试中遇到的困难通过同学间的讨论也可以得到更好的改进方法。
总之，这次的课程设计让我受益匪浅也可以增加我对数据结构这门课程设计的兴趣。
让对以后数据结构的学习充满了信心。
参考文献
（1）李龙澍．C++程序设计实训清华大学出版社，2003年
（2）伍俊良．VISUALC++课程设计与系统开发案例，清华大学出版社2003年
（3）乌尼尔．VisualC++经典例程分析中国电力出版社，2000年
（4）张曜．VISUALC++程序开发案例解析清华大学出版社，1999年
（5）宋晓宇、王永会．VISUALC++高级编程技术与实例中国水利水电出版社，2003年
附录：
源代码清单
//开始.cpp
#include"串.h"
#include"栈.h"
#include"队列.h"
#include"线性表.h"
#include"后缀.h"
voidmain（）
{
intchoice;
charch;
ch='y';
while（ch=='y'||ch=='Y'）
{
printf（"\n\n\n"）;
printf（"\n\t\t数据结构主系统"）;
printf（"\n\t\t主菜单"）;
printf（"\n\t\t*************************************"）;
printf（"\n\t\t*1----栈*"）;
printf（"\n\t\t*2----串*"）;
printf（"\n\t\t*3----队列*"）;
printf（"\n\t\t*4----线性表*"）;
printf（"\n\t\t*5----自主实验*"）;
printf（"\n\t\t*0----退出*"）;
printf（"\n\t\t*************************************"）;
printf（"\n\t\t请选择菜单号（0--5）:
"）;
scanf（"%d",&choice）;
getchar（）;
switch（choice）
{
case1:
Stack（）;
break;
case2:
String（）;
break;
case3:
Queue（）;
break;
case4:
LineList（）;
break;
case5:
Postfix（）;
break;
case0:
ch='n';
break;
default:
{
printf（"菜单选择错误!
请重输"）;
system（"cls"）;
}
}
}
}
//栈.cpp
#include
#include
#defineSTACKMAX100
typedefstructstacknode
{
intdata;
structstacknode*next;
}StackNode;
typedefstruct
{
StackNode*top;
}LinkStack;
voidPush（LinkStack&s,intx）
{
StackNode*p=newStackNode;
p->data=x;
p->next=s.top;
s.top=p;
}
intPop（LinkStack&s,int&x）
{
StackNode*p;
if（s.top!
=NULL）
{
p=s.top;
x=p->data;
s.top=p->next;
deletep;
return1;
}
else
return0;
}
voidShowStack（LinkStacks）
{
system（"cls"）;
StackNode*p=s.top;
if（p==NULL）
printf（"\n\t\t栈为空."）;
else
{
printf（"\n\t\t栈元素为:
"）;
while（p!
=NULL）
{
printf（"%6d",p->data）;
p=p->next;
}
printf（"\n"）;
}
}
voidConversion（intn）
{
LinkStacks;
intx;
s.top=NULL;
do
{x=n%2;
n=n/2;
Push（s,x）;
}while（n）;
printf（"\n\t\t转换后的二进制数值为:
"）;
while（Pop（s,x））
printf（"%d",x）;
printf（"\n"）;
}
voidSuffix（）
{
system（"cls"）;
charstr[STACKMAX];
charstack[STACKMAX];
charexp[STACKMAX];
charch;
intsum,i,j,t,top=0;
printf（"\n\t\t输入算术表达式（运算符只能包含+,-,*,/）,以#结束:
\n\t\t"）;
fflush（stdin）;
i=0;
do
{
i++;
scanf（"%c",&str[i]）;
}
while（str[i]!
='#'&&i!
=STACKMAX）;
sum=i;
t=1;
i=1;
ch=str[i];
i++;
while（ch!
='#'）
{switch（ch）
{case'（':
top++;
stack[top]=ch;
break;
case'）':
while（stack[top]!
='（'）
{
exp[t++]=stack[top--];
exp[t++]=',';
}
top--;
break;
case'+':
case'-':
while（top!
=0&&stack[top]!
='（'）
{
exp[t++]=stack[top--];
exp[t++]=',';
}
stack[++top]=ch;
break;
case'*':
case'/':
while（stack[top]=='*'||stack[top]=='/'）
{exp[t++]=stack[top--];
exp[t++]=',';
}
stack[++top]=ch;
break;
case'':
break;
default:
while（ch>='0'&&ch<='z'）
{exp[t++]=ch;
ch=str[i++];
}
i--;
exp[t++]=',';
}
ch=str[i++];
}
while（top!
=0）
{exp[t++]=stack[top--];
if（top!
=0）
exp[t++]=',';
}
printf（"\n\t\t输入的中缀表达式:
"）;
for（j=1;jprintf（"%c",str[j]）;
printf（"\n\n\t\t后缀表达式:
"）;
for（j=1;jprintf（"%c",exp[j]）;
printf（"\n"）;
}
voidStack（）
{
system（"cls"）;
LinkStacks;
inti=1,j=1,val,n;
charchoice;
s.top=NULL;
while
（1）
{
printf（"\n\n\n"）;
printf（"\n\t\t栈子系统"）;
printf（"\n\t\t*************************************"）;
printf（"\n\t\t*1----进栈*"）;
printf（"\n\t\t*2----出栈*"）;
printf（"\n\t\t*3----显示*"）;
printf（"\n\t\t*4----数制转换*"）;
printf（"\n\t\t*5----逆波兰式*"）;
printf（"\n\t\t*0----退出*"）;
printf（"\n\t\t*************************************"）;
printf（"\n\t\t请选择菜单号（0--5）:
"）;
fflush（stdin）;
choice=getchar（）;
switch（choice）
{
case'1':
while
（1）
{
printf（"\n\t\t键入一个整数（'0'表示结束）并按回车:
"）;
scanf（"%d",&val）;
if（val!
=0）
Push（s,val）;
else
{
system（"cls"）;
break;
}
}
break;
case'2':
if（Pop（s,val））
{
system（"cls"）;
printf（"\n\t\t出栈元素为:
%6d\n",val）;
}
else
{
system（"cls"）;
printf（"\n\t\t栈为空，没有元素可以出栈!
\n"）;
}
break;
case'3':
ShowStack（s）;
break;
case'4':
{
system（"cls"）;
printf（"\n\t\t请输入一个十进制正整数:
"）;
scanf（"%d",&n）;
Conversion（n）;
}
break;
case'5':
Suffix（）;
break;
case'0':
exit（0）;
break;
default:
printf（"\n\t\t输入菜单错误，请重新输入!
\n"）;
}
}
}
//串.cpp
#include
#include
#defineSTRINGMAX100
typedefstruct
{
charvec[STRINGMAX];
intlen;
}str;
voidConcatStr（str*r1,str*r2）
{
inti;
printf（"\n\t\tr1=%sr2=%s\n",r1->vec,r2->vec）;
if（r1->len+r2->len>STRINGMAX）
printf（"\n\t\t两个串太长,溢出!
\n"）;
else
{
for（i=0;ilen;i++）
r1->vec[r1->len+i]=r2->vec[i];
r1->vec[r1->len+i]='\0';
r1->len=r1->len+r2->len;
}
}
voidSubStr（str*r,inti,intj）
{
intk;
stra;
str*r1=&a;
if（i+j-1>r->len）
{
printf（"\n\t\t子串超界!
\n"）;
return;
}
else
{
for（k=0;kr1->vec[k]=r->vec[i+k-1];
r1->len=j;
r1->vec[r1->len]='\0';
}
printf（"\n\t\t取出字符为:
"）;
puts（r1->vec）;
}
voidDelStr（str*r,inti,intj）
{
intk;
if（i+j-1>r->len）
printf（"\n\t\t所要删除的子串超界!
\n"）;
else
{
for（k=i+j;klen;k++,i++）
r->vec[i]=r->vec[k];
r->len=r->len-j;
r->vec[r->len]='\0';
}
}
str*InsStr（str*r,str*r1,inti）
{
intk;
if（i>=r->len||r->len+r1->len>STRINGMAX）
printf（"\n\t\t不能插入！
\n"）;
else
{
for（k=r->len-1;k>=i;k--）
r->vec[r1->len+k]=r->vec[k];
for（k=0;klen;k++）
r->vec[i+k]=r1->vec[k];
r->len=r->len+r1->len;
r->vec[r->len]='\0';
}
returnr;
}
intIndexStr（str*r,str*r1）
{
inti,j,k;
for（i=0;r->vec[i];i++）
for（j=i,k=0;r->vec[j]==r1->vec[k];j++,k++）
if（!
r1->vec[k+1]）
returni;
return-1;
}
intLenStr（str*r）
{
inti=0;
while（r->vec[i]!
='\0'）
i++;
returni;
}
str*CreateStr（str*r）
{
gets（r->vec）;
r->len=LenStr（r）;
returnr;
}
intEqualStr（str*r1,str*r2）
{
for（inti=0;r1->vec[i]&&r2->vec[i]&&r1->vec[i]==r2->vec[i];i++）;
returnr1->vec[i]-r2->vec[i];
}
voidString（）
{
system（"cls"）;
stra,b,c,d;
str*r=&a,*r1;
r->vec[0]='\0';
charchoice,p;
inti,j,ch=1;
while（ch!
=0）
{
printf（"\n\n\n"）;
printf（"\n\t\t串子系统"）;
printf（"\n\t\t**********************************"）;
printf（"\n\t\t*1----输入字串*"）;
printf（"\n\t\t*2----连接字串*"）;
printf（"\n\t\t*3----取出字串*"）;
printf（"\n\t\t*4----删除字串*"）;
printf（"\n\t\t*5----插入字串*"）;
printf（"\n\t\t*6----查找字串*"）;
printf（"\n\t\t*7----比较串大小*"）;
printf（"\n\t\t*8----显示字串*"）;
printf（"\n\t\t*0----退出*"）;
printf（"\n\t\t**********************************"）;
printf（"\n\t\t请选择菜单号（0--8）:
"）;
scanf（"%c",&choice）;
getchar（）;
if（choice=='1'）
{
system（"cls"）;
printf（"\n\t\t请输入一个字符串:
"）;
gets（r->vec）;
r->len=LenStr（r）;
}
elseif（choice=='2'）
{
system（"cls"）;
printf（"\n\t\t请输入所要连接的串:
"）;
r1=CreateStr（&b）;
ConcatStr（r,r1）;
printf（"\n\t\t连接以后的新串值为:
\n"）;
puts（r->vec）;
}
elseif（choice=='3'）
{
system（"cls"）;
printf（"\n\t\t请输入从第几个字符开始:
"）;
scanf（"%d",&i）;getchar（）;
printf（"\n\t\t请输入取出的连续字符数:
"）;
scanf（"%d",&j）;
getchar（）;
SubStr（r,i,j）;
}
elseif（choice=='4'）
{
system（"cls"）;
printf（"\n\t\t请输入从第几个字符开始:
"）;
scanf（"%d",&i）;getchar（）;
printf（"\n\t\t请输入删除的连续字符数:
"）;
scanf（"%d",&j）;
getchar（）;
DelStr（r,i-1,j）;
}
elseif（choice=='5'）
{
system（"cls"）;
printf（"\n\t\t请输入在第几个字符前插入:
"）;
升级会员 