数据结构课程设计1

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(password);/输入密码 if(strcmp(password,wang)/原始校对密码为”wang“ return;printf(n所有入住者信息:n);for(i=0;inext;/头指针 while(p) if(p-canstay=0)/若有人入住显示入住者信息 printf(t房间号:%dn,p-roomnumber); prin