数据结构课程设计__24点游戏设计报告

1、摘要题目：80年代全世界流行一种数字游戏,在中国我们把这种游戏称为“24点.用扑克牌实现24点,就是从扑克牌中任意抽出四张数字表示为113,用加、减、乘、除的方法使结果成为 24o程序要实现由系统随机产生四张牌,玩家输入表达式,然后判断表达式是否合法且等于24.如果玩家认为这四张牌算不出24点如：1, 1, 1, 1,可只输入？,程序将判断这四张牌是否能得出24点,如果能,那么程序将给出算式,如果不能那么做出说明.关键词：24点,13张牌,随机发牌,数据结构1、需求分析1.1 程序的功能程序运行后产生4个扑克牌,对应4个整数,其中每个数字只能使用一次； 任意使用+ - * / ,构造出一个表达

2、式,使得最终结果为 24,这就是常见的 算24点的游戏.在输入表达式时程序会自动检测用户输入的数据是否为程序产 生的那4个整数,如果不是就提醒用户输入有误,重新输入或退出程序.有的时 候程序随机产生的扑克牌对应的整数可能不能算成24,如产生了 4个1,这个时候用户只要点击无解程序就会自动退出了.1.2 输入输出的要求输入的运算符只能是+、-、*、/、这六个,输入的整数必须是程序随机产生的那四个数,而且每个数只能用一次.当用户正确输入算式后,用“堆栈来求表达式的值 的原理,求出结果并判断是否为24,得出用户是输是赢的结果.输出结果后,询问用户是否继续,是那么重新启动程序,否那么结束程序.2、概要

3、设计2.1 模块分析24算法游戏的功能模块不多,也比拟容易实现.根本思想就是由程序先随机产生4张扑克牌,每张扑克牌对应一个整数,所以首先要有一个随机产生扑 克牌的模块.接下来就是用户用程序产生的扑克牌来算24点了,所以要有一个输入用户去接表达式的模块.用户输入完成后,判断输入表达式是否合法,所以 要有一个判断表达式合法与否的模块.如果表达式合法程序就开始计算表达式 了,所以要有一个计算表达式的模块.程序计算完表达式后就要判断用户输入的 表达式是不是为24点了,所以还有一个判断表达式正误的模块.这 5个模块是 逐步递进的,是要前一个模块的功能完成后,才能执行后一个模块,否那么程序就 将出错.程序

4、所涉及的数据结构主要为整形和字符型,整形数据结构主要是用来 计算表达式的,字符型数据结构主要是用来输入表达式的. 程序所涉及的数据库 结构主要有数组和栈,数组在计算表达式和产生扑克牌是都要用到, 栈只是用来 计算表达式的.2.2 根据对24点游戏的模块分析,功能模块图如图 1所示图12.3流程图2.3.1 24游戏算法整个流程图如图2所示不符合4,启动程序符 合判断输入表达式 是否符合要求一判断表达式的结果是否为24捌由“你赢了'捌由 “你输了图22.3.2 将输入求解的算术表达式转换成后缀表达式的流程图如图3所示将算术表达式转 换为后缀表达式否开始将op中未扫描完的字符存至U pos

5、texp 中结束2.3.3 计算后缀表达式的流程图如图4所示开始图43、详细设计3.1 各模块的类C码算法随机产生扑克牌函数for循环4次随机产生一个1到13之间的数,用swLh语句输出产生的数,作为 扑克牌的数,再随机产生一个数,也用 switch语句输出,作为扑克牌 的花色.把产生的数和花色组装成一个扑克牌用图形的方式显示出来；将算术表达式转换为后缀表达式While从 exp 读取字符 ch , ch!= ' 0' ch为数字:将后续的所有数字均依次存放到postexp中,并以字符“#标志数值用的结束；ch为做括号“：将次括号进栈道运算式栈op中；ch为右括号“：将运算符栈

6、 op中的左括号“以前的运算 符依次出栈并存放到postexp中,然后将左括号“删除；ch为“ +或-"：将运算符栈op中的左括号“以前的运算符依次出栈并存放到postexp中,然后将+或ch为 f 或“ /将运算符栈op中 f 或“ /运算符依次出栈 并存放到postexp中,然后将“*或“ /闻此假设字符串exp扫描完毕,那么将运算符栈op中的所有运算符依次出栈并存放到postexp 中.计算后缀表达式While从 postexp 读取字符 ch,ch!= ' 0' ch为“ + ：从栈st中出栈两个数值a和b ,计算c=a+b ；将c 进栈；ch为“-"

7、;：从栈st中出栈两个数值a和b ,计算c=b-a ;将c进 栈；ch为“* "：从栈st中出栈两个数值a和b ,计算c=a*b ;将c进 栈；ch为“ /从栈st中出栈两个数值a和b,假设a不为零,计算c=b/a ； 将c进栈；ch为数字等：将连续的数字用转换成数值 d,将d进栈；3.2 C程序代码如下：#include<stdio.h>#include<string.h>#include<stdlib.h>#include<time.h># define MAX 13# define OK 1# define TRUE 1# def

8、ine FALSE 0# define ERROR 0# define OVERFLOW -2# define OPSETSIZE 7# define STACK_INIF_SIZE 50# define STACKINCREMENT 10typedef int status;int number24;enumeNumber = 0,/ 操作数eOperator = 1/ 算子;int oper7=43,45,42,47,40,41,35;typedef struct sqlistint bol;bol is 0 when num_ch is a number;bol is 1 when th

9、e num_ch is a opraterint num_ch;struct sqlist *next;sqlist;typedef struct sqstackint *base;int *top;int stacksize;sqstack;unsigned char Prior77 = 表 3.1 算符间的优先关 系'>','>','<','<','<','>','>','>','>','

10、;<','<','<','>','>','>','>','>','>','<','>','>','>','>','>','>','<','>','>','<'.'

11、;<'.'<'.'<'.'<'.'='.''.'>','>','>','>',' ','>','>','<','<','<','<','<',' ','='char OPSETOPSETSIZE=&

12、#39;+' , '-' , '*' , '/' ,'(' , ')' ,'#'status init_sq(sqlist *l)/ 初始化链表l=(sqlist*)malloc(sizeof(sqlist);if(l=NULL)exit(OVERFLOW);l->next=NULL;return OK;)status insert_sq(sqlist *p,int e,int bl)/链表插入操作sqlist *q;q=(sqlist*)malloc(sizeof(sqlist);q

13、->num_ch=e;q->bol=bl;q->next=NULL;(*p)->next=q;(*p)=(*p)->next;/ printf("insert %d ,%dis succssed!n",e,bl);return OK;)int check(sqlist l)/保证输入的数字是给出的四个数字int right=1,find=0,i;sqlist *q=&l;q=q->next ;for (;q->next!=NULL;q=q->next)if(q->bol=1)if(q->num_ch<

14、=39|q->num_ch>57|q->num_ch=44|q->num_ch=46)right=O;printf("%c不是有效的运算符!n");else find=O;for(i=0;i<4;i+)if(number1i=0&&number0i=q->num_ch)number1i=1;find=1;break;if(find=O)printf("%d 不在给出的四个数字 中!n",q->num_ch);right=O;/end forfor (i=0;i<4;i+)if(number1

15、i=0)printf("%d 没有用上!n",number0i);right=0;return right;int chang(char *s,sqlist *l)/将用户的输入转化为单链表int t=0;unsigned int i=0;int bl,ch;int a1,a2,a;sqlist *p=l;for (;i<strlen(s);i+)if(si>47&&si<58&&t=0)a1=(int)si-48;t+;else if(si>47&&si<58&&t=1)a2=(

16、int)si-48;a=a1*10+a2;t+;)else if(si<48&&si>39&&si!=44&&si!=46)if(t=1)bl=0;insert_sq(&p,a1,bl);t=0;)else if(t=2)bl=0;insert_sq(&p,a,bl);t=0;)bl=1;ch=(int)si;insert_sq(&p,ch,bl);t=0;)else printf("%c不是有效的运算符!n",si);) /end fori=strlen(s)-1;if(si>47&

17、amp;&si<58)if(si-1>47&&si-1<58)bl=0;insert_sq(&p,a,bl);else bl=0;insert_sq(&p,a1,bl);bl=1;a=35;insert_sq(&p,a,bl);/ printf("chang is OK'n");return (check(*l);int Operate(int a,int theta, int b) / 计算/ printf("a=%d,theta=%c,b=%dn",a,theta,b);swi

18、tch(theta) case 43: return a+b;case 45: return a-b;case 42: return a*b;case 47:(if(b=0)return -2000;)if (a%b=0)return a/b;)else /printf(" 不能为小数 n");return -10000;)default : return 0;)int ReturnOpOrd(char op,char* TestOp) / 被 char precede(char Aop, char Bop)所调用来求优先级int i;for(i=0; i< OPSE

19、TSIZE; i+) if (op = TestOpi) return i;)return 0;char precede(char Aop, char Bop) returnPriorReturnOpOrd(Aop,OPSET)ReturnOpOrd(Bop,OPSET) ；)status initstack(sqstack *s)(s)->base = (int*)malloc(STACK_INIF_SIZE*sizeof(int);if(s)->base=NULL) exit(OVERFLOW);(s)->top=(s)->base;(s)->stacksiz

20、e = STACK_INIF_SIZE;/ printf("栈初始化完成！n");return OK;)int gettop(sqstack *s)int e;if(s->top=s->base)printf("栈空,无法取得栈顶元素!n");return 0;)e=*(s->top-1);/printf("取得栈顶元素：%d n",e);return e;)status push(sqstack *s,int e)if(s->top-s->base>=s->stacksize)s->b

21、ase=(int*)realloc(s->base,(s->stacksize+STACKINCR EMENT)*sizeof(int);if(!s->base) exit(OVERFLOW);s->stacksize+= STACKINCREMENT;)*(s->top+)=e;/printf("把 %d 压栈 is OKn",e);return OK;)status pop(sqstack *s,int *e)if(s->top=s->base)printf("栈空,出栈错误!n");return ERROR

22、;)*e=*(-s->top);/printf("%d 出栈成功！n,*e);return OK;)int EvaluateExpression(char* MyExpression) /算法3.4/算术表达式求值的算符优先算法./设OPTR和&&OPND分别为运算符栈和运算数栈,OP为 运算符集合.int result;sqstack OPTR; /运算符栈,字符元素sqstack OPND; /运算数栈,实数元素int c,bl,a,b,theta,top;sqlist *q,l;char *s=MyExpression;init_sq(&l);if

23、(chang(s,&l)!=0)q=&l;initstack(&OPTR);push(&OPTR, 35);initstack (&OPND);q=q->next;c=q->num_ch;bl=q->bol;while (c!= 35 | gettop(&OPTR)!=35)if (bl!=1) push(&OPND, c);q=q->next;c=q->num_ch;bl=q->bol; 不是运算符那么进栈else top=gettop(&OPTR);/ printf("top %c

24、",top);switch (precede(top, c) case '<': /栈顶元素优先权低push(&OPTR, c);q=q->next;c=q->num_ch;bl=q->bol;break;case '=':/脱括号并接收下一字符pop(&OPTR, &c);q=q->next;c=q->num_ch;bl=q->bol;break;case '>':/退栈并将运算结果入栈pop(&OPTR, &theta);pop(&OPN

25、D, &b);pop(&OPND, &a);/printf("q->num_ch is %dn",q->num_ch);push(&OPND, Operate(a, theta, b);break;default :printf("没有这个运算符!n");return 0; / switch/else / whileresult=gettop(&OPND);return result;else printf("你的输入有错误！n");return 0; / EvaluateExpre

26、ssion int randomm()/ 产生四个随机数int i=0;srand(unsigned)time(NULL);for (;i<4;i+)number0i=0;number0i=rand();number0i%=13;number0i+;number1i=0;return number24;int CalcOneExpress(int expression2)/算术表达式求值的算符优先算法.OP为/设OPTR和&&OPND分别为运算符栈和运算数栈, 运算符集合.int index=0,result,c,theta,a,b;sqstack OPTR; /运算符栈

27、,字符元素sqstack OPND; /运算数栈,实数元素initstack(&OPTR);push(&OPTR, 35);initstack (&OPND);c=expressionindex0;while (c!= 35 | gettop(&OPTR)!=35)if (expressionindex1!=1) push(&OPND, c);index+;c=expressionindex0;/不是运算符那么进栈else switch (precede(gettop(&OPTR), c) case '<':/栈顶元素优先权

28、低push(&OPTR, c);index+;c=expressionindex0;break;case '=':/脱括号并接收下一字符pop(&OPTR, &c);index+;c=expressionindex0;break;/退栈并将运算结果入栈pop(&OPTR, &theta);pop(&OPND, &b);pop(&OPND, &a);push(&OPND, Operate(a, theta, b);break;default :printf("没有这个运算符n");

29、return 0; / switch/else / whileresult=gettop(&OPND);return result; / EvaluateExpressionint Equal24(int n)if(n=24)/ printf("the result is %dn",n);return TRUE;elsereturn FALSE;括号的几种情况下省略/1无括号/2 (a b) c d 同 a b (c d),/3 (a b c) d/4 a (b c) d/5 (a b) (c d)/6 (a b) c) d/7 (a (b c) dint Calc

30、Array1(int iNumInput24)/ a * b * c * d /7 numberint expression82,ii,jj,kk;int i,j,k,l,dRes;for(i=0;i<4;i+)for(j=0;j<4;j+)if(j=i)continue;)for(k=0;k<4;k+)(if(k=i|k=j)(continue;)for(l=0;l<4;l+)(if(l=i|l=j|l=k)(continue;)expression00=iNumInput0i;expression20=iNumInput0j;expression40=iNumInp

31、ut0k;expression60=iNumInput0l;expression01=eNumber;expression21=eNumber;expression41=eNumber;expression61=eNumber;for (ii=0;ii<4;ii+)for (jj=0；jj<4;jj+)(for (kk=0;kk<4;kk+)(expression10 = operii;expression11 = eOperator;expression30 = operjj;expression31 = eOperator;expression50 = operkk;ex

32、pression51 = eOperator;expression70 = oper6;expression71 = eOperator;dRes=CalcOneExpress(expression);if(Equal24(dRes)(printf(" 可以这样运 算：d%c%d%c%d%c%dn",expression00,operii,express ion20,operjj,expression40,operkk,expression60);return TRUE;)/end of for oper)return FALSE;int CalcArray2(int iN

33、umInput24)(/ (a * b) * c * d /9 numberint expression102;int ii,jj,i,j,k,l,kk;int dRes;/ printf("CalcArray2n");for(i=0;i<4;i+)(for(j=0;j<4;j+)(if(j=i)continue;)for(k=0;k<4;k+)(if(k=i|k=j)(continue;)for(l=0;l<4;l+)(if(l=i|l=j|l=k)(continue;)expression10=iNumInput0i;expression30=i

34、NumInput0j;expression60=iNumInput0k;expression80=iNumInput0l;expression11=eNumber;expression31=eNumber;expression61=eNumber;expression81=eNumber;for (ii=0;ii<4;ii+)(for (jj=0;jj<4;jj+)(for (kk=0;kk<4;kk+)(expression20 = operii;expression21 = eOperator;expression50 = operjj;expression51 = eO

35、perator;expression70 = operkk;expression71 = eOperator;expression90 = oper6;expression91 = eOperator;expression00 = oper4;expression01 = eOperator;expression40 = oper5;expression41 = eOperator;dResCalcOneExpress(expression);if(Equal24(dRes)(printf(" 可以这样运 算:%c%d%c%d%c%c%d%c%dn",oper4,expre

36、ssion10,operii,expression30,oper5,operjj,expression60,op erkk,expression80);return TRUE;/end of for operreturn FALSE;int CalcArray3(int iNumInput24)(/ (a * b * c) * d 9 numberint expression102;int ii,jj,i,j,k,l,kk;int dRes;/ printf("CalcArray3n");for(i=0;i<4;i+)for(j=0;j<4;j+)ifO=i)(

37、continue;for(k=0;k<4;k+)if(k=i|k=j)continue;for(l=0;l<4;l+)if(l=i|l=j|l=k)continue;expression10=iNumlnput0i;expression30=iNumInput0j;expression50=iNumInput0k;expression80=iNumInput0l;expression11=eNumber;expression31=eNumber;expression51=eNumber;expression81=eNumber;for (ii=0;ii<4;ii+)for (

38、jj=0;jj<4;jj+)for (kk=0;kk<4;kk+)expression20expression21expression40expression41expression70expression71expression90operii;eOperator;operjj;eOperator;operkk;eOperator;oper6;eOperator;expression91 expression00 = oper4;expression01 = eOperator;expression60 = oper5;expression61 = eOperator;dRes=

39、CalcOneExpress(expression);if(Equal24(dRes)printf(" 可以这样运 算：c%d%c%d%c%d%c%c%dn",oper4,expression10,operii,expression30,operjj,expression50,oper5,op erkk,expression80);return TRUE;/end of for operreturn FALSE;int CalcArray4(int iNumInput24) (/ (a * b * c) * d 9 numberint expression102;int i

40、i,jj,i,j,k,l,kk;int dRes;/ printf("CalcArray4n");for(i=0;i<4;i+)(for(j=0;j<4;j+)(if(j=i)(continue;)for(k=0;k<4;k+)(if(k=i|k=j)(continue;for(l=0;l<4;l+)(if(l=i|l=j|l=k)(continue;)expression00=iNumInput0i;expression30=iNumInput0j;expression50=iNumInput0k;expression80=iNumInput0l;

41、expression01=eNumber;expression31=eNumber;expression51=eNumber;expression81=eNumber;for (ii=0;ii<4;ii+)(for (jj=0;jj<4;jj+)(for (kk=0;kk<4;kk+)(expression10 = operii;expression11 = eOperator;expression40 = operjj;expression41 = eOperator;expression70 = operkk;expression71 = eOperator;expres

42、sion90 = oper6;expression91 = eOperator;expression20 = oper4;expression21 = eOperator;expression60 = oper5;expression61 = eOperator;dRes=CalcOneExpress(expression);if(Equal24(dRes)printf(" 可以这样运 算:d%c%c%d%c%d%c%c%dn",expression00,operii,o per4,expression30,operjj,expression50,oper5,ope rkk

43、,expression80);return TRUE;/end of for oper)return FALSE;int CalcArray5(int iNumInput24)(/ (a * b) * (c * d) /11 numberint expression122;int ii,jj,i,j,k,l,kk;int dRes;/ printf("CalcArray5n");for(i=0;i<4;i+)(for(j=0;j<4;j+)(if(j=i)(continue;for(k=0;k<4;k+)(if(k=i|k=j)(continue;)for

44、(l=0;l<4;l+)(if(l=i|l=j|l=k)(continue;)expression10=iNumInput0i;expression30=iNumInput0j;expression70=iNumInput0k;expression90=iNumInput0l;expression11=eNumber;expression31=eNumber;expression71=eNumber;expression91=eNumber;for (ii=0;ii<4;ii+)(for (kk=0;kk<4;kk+)(expression20 = operii;expres

45、sion21 = eOperator;expression50 = operjj;expression51 = eOperator;expression80 = operkk;expression81 = eOperator;expression110 = oper6;expression111 = eOperator;expression00 = oper4;expression01 = eOperator;expression60 = oper4;expression61 = eOperator;expression40 = oper5;expression41 = eOperator;e

46、xpression100 = oper5;expression101 = eOperator;dResCalcOneExpress(expression);if(Equal24(dRes)(printf(" 可以这样运 算:c%d%c%d%c%c%c%d%c%d%cn",oper4,expression 10,operii,expression30,oper5,operjj,oper4,expre ssion70,operkk,expression90,oper5);return TRUE;/end of for operreturn FALSE;int CalcArray

47、6(int iNumInput24)(/ (a * b) * c) * d 11 number int expression122;int ii,jj,i,j,k,l,kk;int dRes;/ printf("CalcArray6n");for(i=0;i<4;i+)(for(j=0;j<4;j+)if(j=i)continue;for(k=0;k<4;k+)if(k=i|k=j)continue;for(l=0;l<4;l+)if(l=i|l=j|l=k)continue;expression20=iNumInput0i;expression40

48、=iNumInput0j;expression70=iNumInput0k;expression100=iNumInput0l;expression21=eNumber;expression41=eNumber;expression71=eNumber;expression101=eNumber;for (ii=0;ii<4;ii+)for (jj=0;jj<4;jj+)for (kk=0;kk<4;kk+)expression30 = operii;expression31 = eOperator;expression60 = operjj;expression61 = e

49、Operator;expression90 = operkk;expression91 = eOperator;expression110 = oper6;expression111 = eOperator;expression00 = oper4;expression01 = eOperator;expression10 = oper4;expression11 = eOperator;expression50 = oper5;expression51 = eOperator;expression80 = oper5;expression81 = eOperator;dRes=CalcOne

50、Express(expression);if(Equal24(dRes)printf(" 可以这样运 算：c%c%d%c%d%c%c%d%c%c%dn",oper4,oper4,ex pression20,operii,expression40,oper5,operjj,expr ession70,oper5,operkk,expression100);return TRUE;/end of for oper)return FALSE;)int CalcArray7(int iNumInput24)(/ (a * b * c) * d 9 numberint express

51、ion122;int ii,jj,i,j,k,l,kk;int dRes;/ printf("CalcArray7n");for(i=0;i<4;i+)(for(j=0;j<4;j+)(if(j=i)(continue;)for(k=0;k<4;k+)if(k=i|k=j)(continue;)for(l=0;l<4;l+)(if(l=i|l=j|l=k)(continue;)expression10=iNumInput0i;expression40=iNumInput0j;expression60=iNumInput0k;expression100

52、=iNumInput0l;expression11=eNumber;expression41=eNumber;expression61=eNumber;expression101=eNumber;for (ii=0;ii<4;ii+)(for (jj=0;jj<4;jj+)for (kk=0;kk<4;kk+)(expression20 = operii;expression21 = eOperator;expression50 = operjj;expression51 = eOperator;expression90 = operkk;expression91 = eOp

53、erator;expression110 = oper6;expression111 = eOperator;expression00 = oper4;expression01 = eOperator;expression30 = oper4;expression31 = eOperator;expression70 = oper5;expression71 = eOperator;expression80 = oper5;expression81 = eOperator;dResCalcOneExpress(expression);if(Equal24(dRes)printf(" 可以这样运 算:%c%d%c%c%d%c%d%c%c%c%dn",oper4,expression 10,operii,oper4,expres