数据结构课程设计+24点游戏源代码.doc

课 程 设 计课程设计名称： 数据结构课程设计 专 业 班 级 ： 学 生 姓 名 ： 学 号 ： 指 导 教 师 ： 课程设计时间： 计算机科学与技术专业课程设计任务书学生姓名 专业班级 学号 题 目24点游戏课题性质其它课题来源自拟课题指导教师 同组姓名 主要内容一副牌共54张，除去大小King，还剩52张，从中任意取四张加入括号和加减乘除运算符，组成表达式，并使表达式的值等于24。（注：1. 每张牌只能用一次; 2.有些数字组合不能是表达式的值为24）任务要求1.程序产生四个随机的数字（在1-13之间），由用户计算24点2.用户输入四个数字（在1-13之间），由程序计算24点参考文献1 张凤琴,张青凤.数据结构学习指导与习题详解,清华大学出版社,20072 严蔚敏,吴伟民.数据结构(C语言版). 清华大学出版社,20083 潭浩强.C语言程序设计（第三版）. 清华大学出版社,20054 潭浩强.C语言程序设计题解与上机指导（第三版）. 清华大学出版社,20055张 曼,朱小谷,吕士俊.数据结构习题与解答 . 北京希望电子出版社.2005审查意见指导教师签字：教研室主任签字： 年 月 日 1需求分析24点游戏主要有两个功能：(1)用户记算24点程序随机产生四个1-13的数，分别代表4张牌, 提示用户输入算式。如果用户认为程序给出的一组数字不能算出24点（如1，1，2，2），则输入？，然后程序对这四个数字进行计算，如果真的不能算出24点，则输出用户正确的信息，否则给出一个正确的算式，并显示用户错误的信息。(2).程序计算24点用户输入四个1-13的数，代表4张牌，程序需要通过一定的规则添加括号和运算符来使算式的值等于24，如果用户给出的四个数字不能算出24点，则输出错误信息！2概要设计抽象数据结构定义：ADT数据对象：D=a|a为大于0小于14的整数push(sqstack *s,int e) /压栈gettop(sqstack *s) /取得栈顶元素pop(sqstack *s,int *e) /出栈randomm() /产生四个随机数EvaluateExpression(char* MyExpression) /课本算法3.4-计算表达式的值init_sq(sqlist *l) /初始化链表insert_sq(sqlist *p,int e,int bl) /链表插入操作chang(char *s,sqlist *l) /将用户的输入转化为单链表check(sqlist l) /保证输入的数字是给出的四个数字Operate(int a,int theta, int b) /计算precede(char Aop, char Bop) /求运算符优先级ReturnOpOrd(char op,char* TestOp) /返回运算符优先级CalcOneExpress(int expression2)/课本算法3.4-计算表达式的值Calc24(int number24)/包含下面五个函数，即表达式的五种形式CalcArray1(int iNumInput24)/ a * b * c * d /7 个字符CalcArray2(int iNumInput24)/ (a * b) * c * d /9 numberCalcArray3(int iNumInput24)/ (a * b * c) * d /9 numberCalcArray4(int iNumInput24)/ (a * b) * (c * d) /11 numbersCalcArray5(int iNumInput24)/ (a * b) * c) * d /11 numbersEqual24(int n) /判定结果是否等于24gameinformation() /游戏介绍menu() /菜单main() /主函数ADT模块划分Main()游戏介绍人算24点程序算24点计算24点并输出算式用户输入算式用户认为无法算出24点程序验证，输出正确或错误信息，用户继续玩程序验证，若能算出24点，则输出正确算式无法算出24点，输出错误信息3 运行环境硬件环境：PC机软件环境：Windows XPMicrosoft Visual C+ 6.04 开发工具和编程语言开发工具：Microsoft Visual C+ 6.0 编程语言：C语言5 详细设计（1）全局变量和栈，链表的定义int number24;enumeNumber = 0,/操作数eOperator = 1/算子;int oper7=43,45,42,47,40,41,35;课本 表3.1 算符间的优先关系：unsigned char Prior77 = , , , , , , , ,=;线性表的定义：typedef struct sqlist int bol; /bol是0时,num-ch是数字;bol是1时num_ch是运算符int num_ch;struct sqlist *next;sqlist;栈的定义：typedef struct sqstack int *base;int *top;int stacksize;sqstack; （2）main（）函数及用户界面void main()gameinformation(); /输出作者信息menu(); /输出功能菜单，游戏开始用户界面如 图1 所示。（3）由程序计算24点的算法分析:用户输入四个1-13的数，代表4张牌，程序算24点。这要考虑到各种情况。首先是加入括号，有以下5种可能的形式：. a b c d. (a b) c d同 a b (c d) 和 a (b c) d. (a b c) d. (a b) (c d). ( (a b) c) d同 (a (b c) d然后根据上述 5 种情况加入运算符。对于每种不同的算式形式，先在固定的位置加入括号。程序通过4层循环对四个数字进行赋值，并对循环加以控制，使每个数字只用一次，然后再通过三层循环对三个位置的运算符赋值。每一次循环都会产生一个数组，别调用下面的CalcOneExpress函数求算式的值！结果可能算出24点，或者算不出24点 (如图2，图3)。以下两段代码是对针对第一种形式的算式求24点。过程为：对四个数字和三个运算符赋值（CalcArray1(int iNumInput24)）-计算算式的值（CalcOneExpress(int expression2)）-验证是否等于24-输出结果：代码1. / a * b * c * d7 个字符int CalcArray1(int iNumInput24)int expression82,ii,jj,kk;int i,j,k,l,dRes;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;expression00=iNumInput0i;expression20=iNumInput0j;expression40=iNumInput0k;expression60=iNumInput0l;expression01=eNumber;expression21=eNumber;expression41=eNumber;expression61=eNumber;for (ii=0;ii4;ii+)for (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);/对每一个算式求值，直到算出24点if(Equal24(dRes)/判定表达式的值是否为24printf(可以这样运算:%d%c%d%c%d%c%dn,expression00,operii,expression20,operjj,expression40,operkk,expression60);return 1;return 0;代码2./课本算法3.4-计算 算式的值int CalcOneExpress(int expression2)/ 算术表达式求值的算符优先算法。/ 设OPTR和&OPND分别为运算符栈和运算数栈，OP为运算符集合。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; / 不是运算符则进栈elseswitch ( precede(char)gettop(&OPTR), (char)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 / whileresult=gettop(&OPND);return result; / end CalcOneExpress（4）由用户计算24点的算法分析:先由程序产生4个随机数；int randomm()int i=0;srand(unsigned)time(NULL);for(;inext;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; / 不是运算符则进栈elsetop=gettop(&OPTR);switch (precede(char)top, (char)c)case 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(&OPND, &b);pop(&OPND, &a);push(&OPND, Operate(a, theta, b);break;default :printf(没有这个运算符!n);return 0;result=gettop(&OPND);return result;else printf(你的输入有错误!n);return 0;代码2. 将用户的输入转化为单链表：int chang(char *s,sqlist *l) 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不是有效的运算符!n,si);i=strlen(s)-1;if(si47&si47&si-1num_ch=e;q-bol=bl;q-next=NULL;(*p)-next=q;(*p)=(*p)-next;return 1;6.调式分析1在解决某一个问题之前一定要把算法想清楚，考虑到全局，以免造成大量不必要的改动。2用scanf输入数据时，一定要注意格式，否则就会出错！3在函数调用时，参数类型一定要一致，否者会产生警告信息，甚至导致结果出错。4.如果不使用time函数，则产生的随机数是重复出现的。5.用户输入的算式，也可以转化为数组进行操作，但算式的形式不确定，转化为链表似乎省去了很多麻烦。6.刚开始没有对CalcArray(int iNumInput24)函数中的循环加以控制，结果造成数字重复使用。7.在单链表形成之后，在其中取数据元素，要从q-next开始，其头结点中不含要用的数据，应跳过，否则结果不可预料。8.如果想通过调用函数来改变几个变量的值，那么用指针应该是很方便的。9.要改变指针值，需要使用二级指针10由于在C语言中函数都是全局作用域的，因此不要使用和库中的函数名相同的标识符，否则会出现错误。包括宏标识符也有这样的问题。7测试结果图（1）用户界面图1（2）用户输入数据，程序算出结果图2（3）用户输入的数据算不出24点图3（4）程序给出数字，用户认为算不出24点图4（5）用户计算出错图5（6）程序给出数字，用户算出正确结果图68.参考文献1 张凤琴,张青凤.数据结构学习指导与习题详解,清华大学出版社,20072 严蔚敏,吴伟民.数据结构(C语言版). 清华大学出版社,20083 潭浩强.C语言程序设计（第三版）. 清华大学出版社,20054 潭浩强.C语言程序设计题解与上机指导（第三版）. 清华大学出版社,20055张 曼,朱小谷,吕士俊.数据结构习题与解答 . 北京希望电子出版社.2005课程设计总结源代码：（此为可运行的源代码直接复制粘贴过来的，如直接复制不能运行，可粘贴到文本中进行字符过滤，然后自粘贴到编译器中）#include#include#include#include#define OPSETSIZE 7#define STACK_INIF_SIZE 50#define STACKINCREMENT 10int number24;enumeNumber = 0,/操作数eOperator = 1/算子;int oper7=43,45,42,47,40,41,35;char OPSETOPSETSIZE=+ , - , * , / ,( , ) , #;typedef struct sqlistint bol;/bol 是 0 时,num-ch是一个数字;bol 是 1 时 num_ch 运算符int num_ch;struct sqlist *next;sqlist;/线性表typedef struct sqstackint *base;int *top;int stacksize;sqstack;/栈的定义unsigned char Prior77 = / 课本 表3.1 算符间的优先关系 , , , , , , ,next=NULL;return 1;int insert_sq(sqlist *p,int e,int bl)/链表插入操作sqlist *q;q=(sqlist*)malloc(sizeof(sqlist);q-num_ch=e;q-bol=bl;q-next=NULL;(*p)-next=q;(*p)=(*p)-next;return 1;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 num_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 forfor (i=0;i4;i+)if(number1i=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 (;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不是有效的运算符!n,si); /end fori=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);return (check(*l);int Operate(int a,int theta, int b)/计算switch(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)/ precede()函数调用求优先级int i;for(i=0; ibase = (int*)malloc(STACK_INIF_SIZE*sizeof(int);if(s)-base=NULL) exit(-2);(s)-top=(s)-base;(s)-stacksize = STACK_INIF_SIZE;return 1;int gettop(sqstack *s) /取得栈顶元素int e;if(s-top=s-base)printf(栈空,无法取得栈顶元素!n);return 0;e=*(s-top-1);return e;int push(sqstack *s,int e) /压栈if(s-top-s-base=s-stacksize)s-base=(int*)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(int);if(!s-base) exit(-2);s-stacksize+= STACKINCREMENT;*(s-top+)=e;return 1;int pop(sqstack *s,int *e) /出栈if(s-top=s-base)printf(栈空,出栈错误!n);return 0;*e=*(-s-top);return 1;int EvaluateExpression(char* MyExpression) / 算法3.4-计算表达式的值 / 算术表达式求值的算符优先算法。 / 设OPTR和&OPND分别为运算符栈和运算数栈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);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; / 不是运算符则进栈elsetop=gettop(&OPTR);switch (precede(char)top, (char)c)case 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(&OPND, &b);pop(&OPND, &a);push(&OPND, Operate(a, theta, b);break;default :printf(没有这个运算符!n);return 0; / switch/else / whileresult=gettop(&OPND);return result;else printf(你的输入有错误!n);return 0;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为运算符集合。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; / 不是运算符则进栈elseswitch ( precede(char)gettop(&OPTR), (char)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 / whileresult=gettop(&OPND);return result;int Equal24(int n) if(n=24)return 1;elsereturn 0;/括号的几种情况/1无括号/2 (a b) c d同a b (c d), 下省略/3 (a b c) d/4 (a b) (c d)/5 (a b) c) dint CalcArray1(int iNumInput24)/ a * b * c * d7 个字符int expression82,ii,jj,kk;int i,j,k,l,dRes;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;expression00=iNumInput0i;expression20=iNumInput0j;expression40=iNumInput0k;expression60=iNumInput0l;expression01=eNumber;expression21=eNumber;expression41=eNumber;expression61=eNumber;for (ii=0;ii4;ii+)for (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(可以这样运算:%d%c%d%c%d%c%dn,expression00,operii,expression20,operjj,expression40,operkk,expression60);ret