1、数据结构课程设计 24点游戏一、课程设计的目的和要求本课程设计是为了配合数据结构课程的开设，通过设计一完整的程序，使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法。使学生了解并掌握数据结构与算法的设计方法，并且具备初步的独立分析和设计能力。通过这个课程的学习，让学生们初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能，还可以提高综合运用所学的理论知识和方法独立分析和解决问题的能力。课程设计的要求即为：1、要充分认识课程设计对自己的重要性，认真做出设计前的各项准备工作。2、既要虚心接受老师的指导，又要充分发挥主观能动性相结合课题，独
2、立思考，努力钻研，勤于实践，勇于创新。3、独立按时完成规定的工作任务，不得弄虚作假，不准抄袭他人内容。则成绩以不及格计。4、在设计过程中，要严格要求自己，树立严肃、严密、严谨的科学态度，必须按时、按质、按量完成课程设计。二、设计的主要内容24点游戏是一种简单的益智类游戏 游戏内容为：从113中，任意抽取4个数字，运用加、减、乘、除和括号等运算符把这些数字进行一系列的运算，运算得到的结果应为24。并且每个数都必须参与运算，每个数字只能运算一次，运算符可多次重复使用。当用户正确输入算式后，程序根据“堆栈来求表达式的值” 的原理，求出结果并判断是否为24，得出用户是输是赢的结论。输出结果后，询问用户
3、是否继续，是则重新启动程序，否则结束程序。 三、概要设计1.模块分析24算法游戏的功能模块不多，也比较容易实现。基本思想就是由程序先随机产生4张扑克牌，每张扑克牌对应一个整数，所以首先要有一个随机产生扑克牌的模块。接下来就是用户用程序产生的扑克牌来算24点了，所以要有一个输入用户去接表达式的模块。用户输入完成后，判断输入表达式是否合法，所以要有一个判断表达式合法与否的模块。如果表达式合法程序就开始计算表达式了，所以要有一个计算表达式的模块。程序计算完表达式后就要判断用户输入的表达式是不是为24点了，所以还有一个判断表达式正误的模块。这5个模块是逐步递进的，是要前一个模块的功能完成后，才能执行后
4、一个模块，否则程序就将出错。程序所涉及的数据结构主要为整形和字符型，整形数据结构主要是用来计算表达式的，字符型数据结构主要是用来输入表达式的。程序所涉及的数据库结构主要有数组和栈，数组在计算表达式和产生扑克牌是都要用到，栈只是用来计算表达式的。判断表达式是否合法。2.功能模块图24点游戏判断表达式的正误计算表达式判断表达式是否合法输入求解表达式随机取数 图1.功能模块图四、运行环境硬件环境：PC机 软件环境：Windows XP Microsoft Visual C+ 6.0五、详细设计1.运行程序：enum eNumber = 0, /操作数 eOperator = 1 /算子 ; int
5、oper7=43,45,42,47,40,41,35; typedef struct sqlist int bol;/bol is 0 when num_ch is a number;bol is 1 when the num_ch is a oprater int num_ch; struct sqlist *next; sqlist; typedef struct sqstack int *base; #include #include #include #include #define MAX 13 #define OK 1 #define TRUE 1 #define FALSE 0
6、#define ERROR 0 #define OVERFLOW -2 #define OPSETSIZE 7 #define STACK_INIF_SIZE 50 #define STACKINCREMENT 10 typedef int status; int number24; int *top; int stacksize; sqstack; unsigned char Prior77 = / 表3.1 算符间的优先关系 , , , , , , ,next=NULL; return OK; status insert_sq(sqlist *p,int e,int bl)/链表插入操作
7、sqlist *q; q=(sqlist*)malloc(sizeof(sqlist); q-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 nu
8、m_ch57|q-num_ch=44|q-num_ch=46) right=0; printf(%c不是有效的运算符!n); else find=0; for(i=0;inum_ch ) number1i=1; find=1; break; if(find=0) printf(%d 不在给出的四个数字中!n,q-num_ch ); right=0; /end for for (i=0;i4;i+) if(number1i=0) printf(%d没有用上!n,number0i); right=0; return right; int chang(char *s,sqlist *l)/将用户的输
9、入转化为单链表 int t=0; unsigned int i=0; int bl,ch; int a1,a2,a; sqlist *p=l; for (;i47&si47&si58&t=1) a2=(int)si-48; a=a1*10+a2; t+; else if(si39&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不是
10、有效的运算符!n,si); /end for i=strlen(s)-1; if(si47&si47&si-158) 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 OKn); return (check(*l); int Operate(int a,int theta, int b) /计算 / printf(a=%d,theta=%c,b=%dn,a,theta,b); switch(theta) case 43: retu
11、rn 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; ibase = (int*)malloc(STACK_INIF_SIZE*sizeo
12、f(int); if(s)-base=NULL) exit(OVERFLOW); (s)-top=(s)-base; (s)-stacksize = 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
13、-stacksize) s-base=(int*)realloc(s-base,(s-stacksize+STACKINCREMENT)*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; *e=*(-s-top); / printf( %d出栈成功
14、!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(chang(s,&l)!=0) q=&l; initstack(&OPTR)
15、; 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,top); switch (precede(top, c) case next; c=q-num_ch; bl=q-bol; break; case =: / 脱括号并接
16、收下一字符pop(&OPTR, &c); q=q-next; c=q-num_ch; bl=q-bol; break; case : / 退栈并将运算结果入栈 pop(&OPTR, &theta); pop(&OPND, &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 / while result=gettop(&OPND); return
17、result; else printf(你的输入有错误!n); return 0; / EvaluateExpression int randomm()/产生四个随机数 int i=0; srand(unsigned)time(NULL); for (;i4;i+) number0i=0; number0i=rand(); number0i%=13; number0i+; number1i=0; return number24; int CalcOneExpress(int expression2) / 算术表达式求值的算符优先算法。 / 设OPTR和&OPND分别为运算符栈和运算数栈，OP为
18、运算符集合。 int index=0,result,c,theta,a,b; sqstack OPTR; / 运算符栈，字符元素 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
19、(gettop(&OPTR), c) case : / 退栈并将运算结果入栈 pop(&OPTR, &theta); pop(&OPND, &b); pop(&OPND, &a); push(&OPND, Operate(a, theta, b); break; default : printf(没有这个运算符n); return 0; / switch /else / while result=gettop(&OPND); return result; / EvaluateExpression int Equal24(int n) if(n=24) / printf(the result i
20、s %dn,n); return TRUE; else return 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) d int CalcArray1(int iNumInput24) / a * b * c * d /7 number int expression82,ii,jj,kk; int i,j,k,l,dRes; for(i=0;i4;i+) for(j=0;j4;j+) if(j=i) con
21、tinue; for(k=0;k4;k+) if(k=i|k=j) continue; for(l=0;l4;l+) if(l=i|l=j|l=k) continue; expression00=iNumInput0i; expression20=iNumInput0j; expression40=iNumInput0k; expression60=iNumInput0l;expression01=eNumber; expression21=eNumber; expression41=eNumber; expression61=eNumber; for (ii=0;ii4;ii+) for (
22、jj=0;jj4;jj+) for (kk=0;kk4;kk+) expression10 = operii; expression11 = eOperator; expression30 = operjj; expression31 = eOperator; expression50 = operkk; expression51 = eOperator; expression70 = oper6; expression71 = eOperator; dRes = CalcOneExpress(expression); if(Equal24(dRes) printf( 可 以 这 样 运 算:
23、%d%c%d%c%d%c%dn,expression00,operii,expression20,operjj,expression40,operkk,expression60); return TRUE; /end of for oper return FALSE; int CalcArray2(int iNumInput24) / (a * b) * c * d /9 number int expression102; int ii,jj,i,j,k,l,kk; int dRes; / printf(CalcArray2n); for(i=0;i4;i+) for(j=0;j4;j+) if(j=i) continue; for(k=0;k4;k+) if(k=i|k=j) continue; for(l=0;l4;l+) if(l=i|l=j|l=k) continue; expression10=iNumInput0i; expres
