《数据结构课程设计1.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计1.doc（35页珍藏版）》请在三一办公上搜索。
1、数据结构课程设计一、 表达式求值二、 多项式相乘三、 宾馆系统129074235汪帅天一、 表达式求值1. 问题描述表达式求值是程序设计语言编译中一个最基本的问题。它的实现也是栈的应用中的一个典型的例子。本程序可输入一个中缀表达式，以#为结束符号，则可求出其值。2. 设计思路表达式可以分为两部分，一个是操作符，本程序定义了7个操作符，+，-，（，），*，#，/。另一个是操作数，即是普通的整数。按顺序扫描表达式字符串，遇到操作数则将操作数压入数值栈。遇到操作符则判断算符栈的栈顶元素与当前操作符的关系，来进行其他操作，比如计算，压栈，出栈等。在计算时将数值栈栈顶前两个元素取出来进行计算。3. 数据
2、结构设计typedef structint numMAXSIZE;int top;NumStack,*PNumStack;/定义一个数值栈，用于存放操作数typedef structchar opeMAXSIZE;int top;OperatorStack,*POperatorStack;/定义一个算符栈，用于存放运算符char exp30;4. 功能函数设计（1）辅助函数int isOperator(char c)：判断当钱字符是否为操作符int priority(char op)：给每个运算符定义优先级（2）数值栈及其操作函数（3）算符栈及其操作函数（4）核心函数，中缀表达式求值函数5.程
3、序代码#includestdio.h#includestdlib.h#includemalloc.h#includestring.h#define MAXSIZE 100/*定义栈及其操作函数*/数值栈 typedef structint numMAXSIZE;int top;NumStack,*PNumStack;/定义一个数值栈，用于存放操作数/数值栈操作函数PNumStack Init_NumStack(void)/数值栈初始化 PNumStack S;S=(PNumStack)malloc(sizeof(NumStack);if(S)S-top=-1;return S;int Push
4、_NumStack(PNumStack S,int x)/数值栈入栈 if(S-top=MAXSIZE-1)return(0);elseS-top+;S-numS-top=x;return(1);int Pop_NumStack(PNumStack S,int *x)/数值栈出栈if(S-top=-1)return(0);else*x=S-numS-top;S-top-;return(1);int GetTop_NumStack(PNumStack S,int *x)/取栈顶元素 if(S-top=-1)return(0);else*x=S-numS-top;return(1); void D
5、estroy_NumStack(PNumStack *S)/销毁 if(*S) free(*S); *S=NULL; return; /*/ /运算符栈 typedef structchar opeMAXSIZE;int top;OperatorStack,*POperatorStack;/定义一个算符栈，用于存放运算符/操作栈操作函数POperatorStack Init_OperatorStack(void)/算符栈初始化 POperatorStack S;S=(POperatorStack)malloc(sizeof(OperatorStack);if(S)S-top=-1;return
6、 S;int Push_OperatorStack(POperatorStack S,char x)/算符栈入栈 if(S-top=MAXSIZE-1)return(0);elseS-top+;S-opeS-top=x;return(1);int Pop_OperatorStack(POperatorStack S,char *x)/算符栈出栈 if(S-top=-1)return(0);else*x=S-opeS-top;S-top-;return(1);int GetTop_OperatorStack(POperatorStack S,char *x)/算符栈取栈顶 if(S-top=-1
7、)return(0);else*x=S-opeS-top;return(1); void Destroy_OperatorStack(POperatorStack *S)/销毁 if(*S) free(*S); *S=NULL; return; /*辅助函数*/int isOperator(char c)/判断字符是否为操作符，（注意是判断是否为操作数，不是是否为数值 /）若是返回1，否则返回0 if(c=#|(c=(&c=+)|c=-|c=/)return(1);else return(0); int priority(char op)/给每个运算符定义优先级 switch(op)case
8、#:return(1);case ):return(2);case +:case -:return(3);case *:case /:return(4);case (:return(5);default :return(0); /*中缀表达式求值*/ int EXP(char exp)int i=0,integer=0,result,a,b,s;/i是字符型数组下标，用于扫描下一字符，/integer是用于合成操作数，操作数不仅仅是个位数，可以使任意整数/result是最后的计算结果/a,b,s分别是出栈用于计算的，s是计算结果 char c,w,temp;/c是出栈元素暂时存放在c中，用于比
9、较/w是当前字符，也用于循环结束条件/temp是出栈元素暂时存放在temp中，用于计算 PNumStack Np;/分别定义两个栈并初始化 POperatorStack Op;Np=Init_NumStack();Op=Init_OperatorStack();if(!Np|!Op)printf(栈初始化失败n);return(0);Push_OperatorStack(Op,#);/先在运算符栈中放入#w=exp0;/w先取字符串首元素 while(temp!=#|(GetTop_OperatorStack(Op,&c),c)!=#)/栈顶元素不是#或者temp不是# if(isOperat
10、or(w)/若w是运算符 if(integer!=0)/巧妙之点,若integer不为0说明，该运算符之前是一整数，且是一位完整的/整数，不是一位数，此时将integer压入数值栈，并让integer归0 Push_NumStack(Np,integer);integer=0;if(GetTop_OperatorStack(Op,&c),c)=(&w=)/栈顶是(并且栈外是),脱括号 Pop_OperatorStack(Op,&temp);i+;/扫描下一字符 else if(GetTop_OperatorStack(Op,&c),c)=(|/栈顶是(或者栈顶优先级小于当前算符 priorit
11、y(GetTop_OperatorStack(Op,&c),c)priority(w)Push_OperatorStack(Op,w);/将w压入栈 i+;elsePop_OperatorStack(Op,&temp);/此时不是输出运算符而是直接运算 Pop_NumStack(Np,&b); Pop_NumStack(Np,&a);/取出数值栈栈顶两个元素 switch(temp)case +:s=a+b;break;/计算 case -:s=a-b;break;case *:s=a*b;break;case /:s=a/b;break;Push_NumStack(Np,s);/将输出的运算
12、符直接运算出结果并入数值栈/当前运算符继续与栈顶比较/i不+ else integer=integer*10+(w-0);/合成多位整数座位操作数 i+;w=expi;/扫描下一位字符 Pop_NumStack(Np,&result);/此时数值栈栈顶元素即是结果 Destroy_OperatorStack(&Op); Destroy_NumStack(&Np);/销毁栈 return(result);/返回结果 /*主函数*/int main()int result;char exp30;while(1) printf(tt数据结构课程设计1表达式求值n); printf(ttttt1290
13、74235 汪帅天nnn); printf(请输入数学四则运算表达式，以#为结束字符n); gets(exp);/定义原始字符串 result=EXP(exp); printf(n运算结果为%dn,result); system(pause); system(cls);return 0;6.运行与测试初始界面，可多次完成表达式求值计算书上例题，但是都是个位数的四则运算自己的测试，不仅仅可以使用个位数，还可以使用多位整数来四则运算。 7.设计心得1.本程序的主要难点便是对两个栈的操作，参考书本上先将中缀表达式转化成后缀表达式，再利用后缀表达式来计算结果，本程序是直接利用中缀表达式来计算结果2.判
14、断多位整数时，需判断下一位是否也是数值，若是数值则两个数为一整体，加一块才算做操作数。若是运算符，说明之前的操作数已结束，则压入数值栈。3.在算符栈栈顶运算符大于当前运算符时，不是直接输出运算符。而是利用计算后缀表达式的思想，直接从数值栈中取出两个数值来直接计算，计算出结果后再将结果压入数值栈。4.当取出数值栈的元素进行计算时，运算符栈顶的元素用过之后，还应将当前运算符继续与算符栈顶元素继续比较。二、多项式相乘1.问题描述多项式相乘是指用户按一定格式输入两个一元多项式，程序求出其乘积并输出给用户。2.设计思路本程序主要有以下几个方面需要思考。怎么样接受用户输入的一元多项式并合适的储存起来，以便
15、计算时不会过于复杂。一元多项式可以分解为每个项相加，一个项包括两个因素，系数与幂数。可以用结构体和数组储存起来。另一个问题，怎么样把所乘结果保存并输出。结果按照两两相乘，系数相乘、幂数相加的保存在一个数组里，该数组结构同乘积因子一样，但是不一样的地方就是乘积项的幂数即是数组下标。3.数据结构设计typedef structint coefficient;/多项式系数int power;/多项式幂数 polynomial;/一个多项式的基本结构 typedef structpolynomial pol;/多项式的一个项dxs;4.功能函数设计由于本程序比较简单，故只有一个主函数。但主函数可大致分
16、为定义数据结构、输入乘积因子信息，计算乘积并输出。5.程序代码#includestdio.h#includemalloc.h#define MAXSIZE 100typedef structint coefficient;/多项式系数int power;/多项式幂数 polynomial;/一个多项式的基本结构 typedef structpolynomial pol;/多项式dxs;int main()dxs Factor1MAXSIZE=0,Factor2MAXSIZE=0,/定义两个相乘因子 ProductMAXSIZE=0;/定义乘积 int i,j;int Coefficient,P
17、ower,Several1,Several2;/多项式的系数，幂数，两个多项的项数int ProPower,ProCoefficient;/乘积的系数幂数 printf(tt数据结构课程设计2多项式相乘n);printf(ttttt129074235 汪帅天nnn);/*先输入因子的两个多项式信息*/printf(n程序解决两个多项式相乘问题，请分别输入两个多项式的项数(空格键开)n);scanf(%d %d,&Several1,&Several2);/分别输入两个多项式的项数 printf(请输入第一个多项式各个项的系数和幂数(空格键开)n);for(i=0;iSeveral1;i+)pri
18、ntf(%d. ,i+1);scanf(%d %d,&Coefficient,&Power);Factor1i.pol.coefficient=Coefficient;/输入该多项式各个项的项数与系数 Factor1i.pol.power=Power;printf(请输入第二个多项式各个项的系数和幂数(空格键开)n);for(j=0;jSeveral2;j+)printf(%d. ,j+1);scanf(%d %d,&Coefficient,&Power);/输入该多项式各个项的项数与系数Factor2j.pol.coefficient=Coefficient;Factor2j.pol.pow
19、er=Power;/*求多项式乘积*/printf(多项式乘积的系数和幂数：n);for(i=0;iSeveral1;i+) for(j=0;jSeveral2;j+) ProPower=(Factor1i.pol.power)+(Factor2j.pol.power);/多项式相乘幂数相加，系数相乘 ProCoefficient=(Factor1i.pol.coefficient)*(Factor2j.pol.coefficient); ProductProPower.pol.power=ProPower;/该乘积利用系数与下标相同来记录数据 ProductProPower.pol.coef
20、ficient+=ProCoefficient;/两个幂数相同的多项式，系数相加 for(i=0;iMAXSIZE;i+) if(Producti.pol.power)/遍历乘积数组，若幂数不为0，则按照升序输出 printf(%dC%d+,Producti.pol.coefficient,Producti.pol.power); return(0);/完成 6.运行与测试7.设计心得1.本程序主要难点在于如何储存多项式，要考虑到多项式的本身特点，像面向对象设计一样，抽象出多项式的特点，遵循数学原理编写函数。2.在储存多项式时，既要考虑的物理结构也要考虑储存结构。在储存乘积因子多项式时不用考虑
21、输出，可按顺序将多项式各个项储存起来。但是储存乘积时不同，要考虑其输出。所以在设计时将每个项的幂数作为数组下标来储存。三、宾馆系统1.问题描述宾馆的基本业务活动可大致分为入住和退房。其他的比如查询房间信息，后勤服务等等。该程序主要功能包括宾馆的基本功能，订房入住、退房离开，房间查询等，除此之外，还有可查询所有入住者详细信息的功能，由于旅客私人信息的保密性，所以在查看时需输入密码。2.设计思路主要有四个方面的内容1. 房间查询。查询该宾馆房间信息，房间类型，价格，房间总数以及每个类型可入住房间数目。2.订房入住。入住者选择入住，首先确定入住房间类型。分为四种，普通间、标准间、商务间以及豪华间。然
22、后输入入住者信息，比如身份证信息，以及备注信息。随后生成房间号，旅客入住成功。3.退房离开。旅客选择退房，首先输入所退房间的房间号。然后搜到该房间，将入住者信息删除并恢复房间的可入住性。4.警察模式。查看所有入住者的所有详细信息。3.数据结构设计/*数据结构设计*/typedef struct nodeint roomnumber;/房间号 int canstay;/可否入住,可入住为1，否则为0 char information40;/入住者信息 char remark40;/，入住者说明、要求等，备注 struct node *next;/指针 room,*Proom;typedef st
23、ruct int typenum;/房间类型序号 char type20;/房间类型 int price;/价格 int sum;/该房间类型总数 int over;/剩余可入住房间数 Proom point;/头指针，指向该类型的房间 roomtype;4.功能函数设计（1）辅助函数void initialize(roomtype rt)：初始化宾馆所有房间的基本信息int menu( )：菜单选项函数，返回选择功能，退出功能（2）查询函数void RoomQuery(roomtype rt)：房间查询函数（3）订房入住void BookingHotel(roomtype rt)：订房入住函
24、数（4）退房函数void Checkingout(roomtype rt)：退房离开函数（5）警察模式void Police(roomtype rt)：警察查看信息模式函数5.程序代码#includestdio.h#includestdlib.h#includemalloc.h#includestring.h#includestdbool.h#define MAXSIZE 100/*数据结构设计*/typedef struct nodeint roomnumber;/房间号 int canstay;/可否入住,可入住为1，否则为0 char information40;/入住者信息 char
25、remark40;/，入住者说明、要求等，备注 struct node *next;/指针 room,*Proom;typedef struct int typenum;/房间类型序号 char type20;/房间类型 int price;/价格 int sum;/该房间类型总数 int over;/剩余可入住房间数 Proom point;/头指针，指向该类型的房间 roomtype;/*主要功能函数设计*/*(1).辅助函数*/ void initialize(roomtype rt)/初始化宾馆房间信息rt0.typenum=0; strcpy(rt0.type,普通间);rt0.pr
26、ice=88;/房间类型，名称，价格，剩余 rt0.sum=8;rt0.over=8;rt1.typenum=1; strcpy(rt1.type,标准间);rt1.price=128;rt1.sum=8;rt1.over=8; rt2.typenum=2; strcpy(rt2.type,商务间);rt2.price=168;rt2.sum=8;rt2.over=8; rt3.typenum=3; strcpy(rt3.type,豪华间);rt3.price=268;rt3.sum=8;rt3.over=8;int i,j;Proom p;for(i=0;inext=NULL;/创建头结点
27、for(j=0;jroomnumber=(i+1)*100+(j+1);/生成三位数字表示房间号，首数字-1表示房间类型 p-canstay=1;/可否入住均为1，可入住 strcpy(p-information,无);/入住者信息和备注均为“无” strcpy(p-remark,无); p-next=rti.point-next; rti.point-next=p; int menu()/主菜单选择界面int select;printf(tt数据结构课程设计3宾馆系统n);printf(ttttt129074235 汪帅天nnn);printf(ttThe Hotel Systemn);pr
28、intf(*n);printf(1.房间查询n);printf(2.订房入住n);printf(3.退房离开n);printf(4.警察模式n);printf(5.退出系统n);printf(*n);doprintf(please select:);scanf(%d,&select);while(select5);/接受功能选择 return select; /*(2).查询系列函数*/ void RoomQuery(roomtype rt) int i; printf(tt查询房间n); printf(序号 房间类型 价格 剩余n);/显示有的类型房间的价格和剩余 for(i=0;i4;i+
29、) printf( %d %s %-5d %dn,rti.typenum,rti.type,rti.price,rti.over); system(pause); /*(3).订房入住函数*/ void BookingHotel(roomtype rt) int select,i; char c; printf(tt订房入住n); printf(序号 房间类型 价格 剩余n); for(i=0;inext;while(!p-canstay) p=p-next;printf(房间号：%dt价格：%dn请输入入住者信息：,p-roomnumber,rtselect.price);c=getchar
30、();gets(p-information);/接受入住者身份信息 printf(n请输入备注信息:);gets(p-remark);/接受备注信息 p-canstay=0;/可否入住改变rtselect.over-;/剩余量-1 printf(n入住成功！房间号：%d,欢迎入住！n,p-roomnumber);system(pause); /*(4).退房函数*/ void Checkingout(roomtype rt)int k,type,number,proomnumber;char c,YorN;printf(tt退房离开n);c=getchar();printf(请输入退房房间号:
31、);/根据房间号来退房 scanf(%d,&proomnumber);type=proomnumber/100-1;/找到房间类型Proom p=rttype.point-next;/头指针 while(p-roomnumber!=proomnumber)/找到相同房间号p=p-next;if(p-canstay=1)printf(该房间没有人入住!不要吓我咩，请检查房间号n);system(pause); return; printf(房间号:%d,入住者信息:%s,备注信息:%sn,p-roomnumber,p-information,p-remark);printf(t确定退房？(y/n
32、);c=getchar();YorN=getchar();if(YorN=y)/若确定退房，信息清空 strcpy(p-information,无); strcpy(p-remark,无); p-canstay=1;/可以继续入住 rttype.over+;/该类型房间剩余量+1 printf(退房成功，欢迎再来哦nn);system(pause); /*(5).警察模式*/ void Police(roomtype rt)int i;char c,password20;Proom p;printf(tt警察模式n想看啊，想看你就说啊，请输入查看密码:n);c=getchar();gets(p
33、assword);/输入密码 if(strcmp(password,wang)/原始校对密码为”wang“ return;printf(n所有入住者信息:n);for(i=0;inext;/头指针 while(p) if(p-canstay=0)/若有人入住显示入住者信息 printf(t房间号:%dn,p-roomnumber); printf(tt入住者信息:%sn,p-information); printf(tt备注信息:%sn,p-remark); p=p-next;system(pause); /*主函数*/int main()roomtype rt4;initialize(rt)
34、;/初始化所有房间信息 while(1)system(cls);switch(menu()/选择序号 case 1:system(cls);RoomQuery(rt);break;/房间查询 case 2:system(cls);BookingHotel(rt);break;/入住 case 3:system(cls);Checkingout(rt);break;/退房 case 4:system(cls);Police(rt);break;/警察模式 case 5:system(cls);printf(n感谢使用，再见！nn);exit(0);/退出系统 default:system(cls
35、);return(0);6.运行与测试查询房间测试订房入住测试，选择标准间，生成房间号订房入住测试，选择标准间，生成房间号退房离开测试，退房208警察模式测试，查看所有的入住者信息退出系统测试7.设计心得（1）本程序的储存结构用的是图的邻接表表示法。将每一种房间类型的信息，比如价格，房间类型名称，剩余量等，储存在顶点结点中，最后用一个边表头指针将每种类型的所有房间用链表连接起来。（2）每一个房间包括了该房间的类型，房间号，可否入住入住者信息，备注信息等。（3）本程序主要困扰学生的难点是宾馆房间信息的连接。即链表的初始化和操作。带个头结点将会使链表结点的插入、遍历等变得容易。（4）细节问题，可能
36、第一次测试发现不了，细心思考旅馆运行的流程，不仅仅是主要的业务，还有一些细节同样需要考虑进去。比如，入住后，剩余量1，可入住性改变，退房时，若输入的退房房间号里没有入住者怎么办，或者更甚者宾馆里没有该房间怎么办，比如输入退房房间号109。退房后，可入住性改变，剩余量+1.考虑复杂时还需要考虑刚退房的房间需要重新打扫，不能理解住人，同样需要延迟新旅客入住。（5）警察模式为该程序一创新点。具体考虑到需要宾馆店主或者警察在特定情况下，需要了解所有入住者信息。本质为所有类型房间的遍历，在可入住性为否，即已有旅客的房间，输入房间以及入住者的详细信息。（6）在输入一些选择信息是，需要注意getchar( )的合理应用，避免输入的为回车。在显示一些信息时，用system(pause); 函数来使程序暂停，观察输出信息。
