《数据结构》课程设计
题目：
1、编写程序实现三色球问题。有红、黄、绿3种颜色的球，其中红球3个，黄球3个，绿球6个，先将这12个球混放在一个盒子中，从中任意摸出8个球，编程计算摸出球的各种颜色搭配。
2、设计算法并实现，判断某输入字符串是否具有中心对称关系，例如ababbaba，baxzxab皆具有对称性。
3、求复杂表达式的值
一、课程设计的目的
1、对题目的理解，以及了解题目和实际情况所存在的意义、联系。
2、课程设计的进行可以加强团队的配合，而今社会软件开发团队的就不太尽如人意，在校培
养我们的团队精神更加有利于我们走向社会。
3、降低毕业生的就业难度,当今毕业面临着一个严重的问题，就是编程的经验经历太少，认
真完成课程设计，可以丰富我们的经验，弥补自身的不足。
4、课程设计，更是我们巩固基础，加强动手能力、独立思考的能力的较优途经。
5、课程设计是优于理论实验理论的最佳途经，不论基础好坏，成功与否，结果都已经不再重
要，最重要的是这个独立思考的过程和认真完成的态度。
二、课程设计内容与实现
1、算法设计
1、编写程序实现三色球问题。
有红、黄、绿3种颜色的球，其中红球3个，黄球3个，绿球6个，先将这12个球混放在 一个盒子中，从中任意摸出8个球，编程计算摸出球的各种颜色搭配。
算法设计：
设任取的红球个数为a，黄球个数为b，则绿球个数为c-a-b，根据题意红球和黄球个数的
取值范围是0~3个，在红球和黄球个数确定的条件下，绿球个数取值应为a+b+c==6。
2、设计算法并实现，判断某输入字符串是否具有心对称关系，例如 ababbaba，baxzxab皆具有对称性。
算法设计：
利用栈来实现字符串是否有对称性。
（1）创建数组，赋予字符。
（2）创建栈，将数组中的一半字符入栈。
（3）从栈顶开始一次匹配剩余数组中字符。
(4 ) 是中心对称就输出1，不是则为0,。
注意，输入字符必须为偶数。
3、求复杂表达式的值
设计一个程序，计算含有如下标识符的表达式的值。 (1) 数值：包括整数和实数，数值可带正、负号。
(2) 一般运算符：正号、负号、加、减、乘、除、求模和乘方，其中可以包含括号。 (3) 单词(即运算函数)：abs、sqrt、exp、ln、log
10、sin、cos和tanh。 算法设计：
首先，判断数值的正负号、还有运算符号以及函数，然后利用栈对数值的获取和输出进
行处理，再用switch语句进行分类运算；
主要参考： http://zhidao.baidu.com/?si=1
2、程序实现
1、编写程序实现三色球问题。
有红、黄、绿3种颜色的球，其中红球3个，黄球3个，绿球6个，先将这12个球混放在一个盒子中，从中任意摸出8个球，编程计算摸出球的各种颜色搭配。
源程序： #include void main() {
int a,b,c; printf(\"红，黄，绿\\n\"); for(a=0;a
2、设计算法并实现，判断某输入字符串是否具有心对称关系，例如 ababbaba，baxzxab皆具有对称性。
#include #include #include int IsPalindrome(const char *cScr); void main(void) { char cStr[21]; while(1) { gets(cStr); printf(\"%d\\n\",IsPalindrome(cStr)); } } int IsPalindrome(const char *cScr) { int iLen = strlen(cScr); //预留数组首元素,栈顶从第二元素开始 int top = 1; char *cMyStack = (char *)malloc( (iLen/2+1)*sizeof(char) ); //定位对原始数组的检测索引初始位置 cMyStack[0] = iLen/2; if ( 1 == iLen%2 ) { ++cMyStack[0]; } //将原始数组的一半元素入栈 for ( top=1; top
while ( *(cScr+cMyStack[0]) == cMyStack[--top] && cMyStack[0]++
3、求复杂表达式的值
设计一个程序，计算含有如下标识符的表达式的值。 (1) 数值：包括整数和实数，数值可带正、负号。
(2) 一般运算符：正号、负号、加、减、乘、除、求模和乘方，其中可以包含括号。 (3) 单词(即运算函数)：abs、sqrt、exp、ln、log
10、sin、cos和tanh。
源程序：
#include \"iostream\" #include \"math.h\" #include \"cstring\" using namespace std;
const int MaxSize=300;
int trans(char *exp, char postexp[]); double compvalue(char *postexp);
int main(int argc, char* argv[]) { char exp[300],postexp[400];
cout
cout
cout
cout
while (1) { cout >exp; if (strcmp(exp,\"0\")==0) return 0;
if (trans(exp,postexp)==1) { double res=compvalue(postexp); cout
int trans(char *exp, char postexp[]) /*将算术表达式exp转换成后缀表达式postexp */ { struct { char data[MaxSize]; /*存放运算符*/ int top; /*栈指针*/ } op; /*定义运算符栈*/
int i=0; /* i作为postexp的下标*/ int dh=1; /* dh==1表示是负号 */ op.top=-1; while (*exp!=\'\\0\') /* exp表达式未扫描完时循环 */ { switch(*exp) { case \'(\': /*判定为左括号*/ op.top++;op.data[op.top]=*exp; dh=1; exp++;break; case \')\': /*判定为右括号*/ while (op.data[op.top]!=\'(\') { postexp[i]=op.data[op.top]; op.top--; i++; } op.top--; exp++; dh=0; break; case \'+\': case \'-\': /*判定为加或减号*/ if (dh==1) /* +,-是正负号 */ { if (*exp==\'-\') op.top++;op.data[op.top]=\'@\'; exp++; break; } while (op.top!=-1 && op.data[op.top]!=\'(\') { postexp[i]=op.data[op.top]; op.top--; i++; } op.top++;op.data[op.top]=*exp; exp++; dh=0; break; case \'*\': case \'/\': /*判定为\'*\'或\'/\'号*/ while (op.data[op.top]==\'*\' || op.data[op.top]==\'/\'|| op.data[op.top]==\'s\') { postexp[i]=op.data[op.top]; op.top--; i++; } op.top++;op.data[op.top]=*exp; exp++; dh=0; break; case \'^\': while (op.data[op.top]==\'^\') { postexp[i]=op.data[op.top]; op.top--;i++; } op.top++;op.data[op.top]=*exp;exp++;dh=0;break; case \'%\': while (op.data[op.top]==\'%\') { postexp[i]=op.data[op.top]; op.top--;i++; } op.top++;op.data[op.top]=*exp;exp++;dh=0;break; case \' \': exp++; break; /*过滤掉空格*/ case \'s\': case \'S\': if((*(exp+1)==\'i\' || *(exp+1)==\'I\')&&(*(exp+2)==\'n\' || *(exp+2)==\'N\')) { op.top++;op.data[op.top]=\'s\'; exp+=3; dh=0; break; } else if((*(exp+1)==\'q\'|| *(exp+1)==\'Q\')&&(*(exp+2)==\'r\' || *(exp+2)==\'R\')&&(*(exp+3)==\'t\' || *(exp+3)==\'T\')) { op.top++;op.data[op.top]=\'q\'; exp+=4;dh=0; break; } else { printf(\"\\n有错误符号s\"); return 0; }
case \'c\': case \'C\': if((*(exp+1)==\'o\' || *(exp+1)==\'O\')&&(*(exp+2)==\'s\' || *(exp+2)==\'S\')) { op.top++;op.data[op.top]=\'c\'; exp+=3; dh=0; break; } else { printf(\"\\n有错误符号s\"); return 0; } case \'T\': case \'t\': if((*(exp+1)==\'a\'|| *(exp+1)==\'A\')&&(*(exp+2)==\'n\' || *(exp+2)==\'N\')) { op.top++;op.data[op.top]=\'t\'; exp+=3;dh=0; break; } else { printf(\"\\n有错误符号s\"); return 0; } case \'e\': case \'E\': if((*(exp+1)==\'x\'|| *(exp+1)==\'X\')&&(*(exp+2)==\'p\' || *(exp+2)==\'P\')) { op.top++;op.data[op.top]=\'e\'; exp+=3;dh=0; break; } else { printf(\"\\n有错误符号s\"); return 0; } case \'a\': case \'A\': if((*(exp+1)==\'b\'|| *(exp+1)==\'B\')&&(*(exp+2)==\'s\' || *(exp+2)==\'S\')) { op.top++;op.data[op.top]=\'a\'; exp+=3;dh=0; break; } else { printf(\"\\n有错误符号s\"); return 0; } case \'l\': case \'L\': if((*(exp+1)==\'o\'|| *(exp+1)==\'O\')&&(*(exp+2)==\'g\' || *(exp+2)==\'G\')) { op.top++;op.data[op.top]=\'g\'; exp+=3;dh=0; break; } else if((*(exp+1)==\'n\'|| *(exp+1)==\'N\')) { op.top++;op.data[op.top]=\'n\'; exp+=2;dh=0; break; } else { printf(\"\\n有错误符号s\"); return 0; } default: while (*exp>=\'0\' && *exp=\'0\' && *exp
double compvalue(char *postexp) /*计算后缀表达式的值*/ { struct { float data[MaxSize]; /*存放数值*/ int top; /*栈指针*/ } st; /*定义数值栈*/
double d,x;
st.top=-1; while (*postexp!=\'\\0\') /* postexp字符串未扫描完时循环*/ { switch (*postexp) { case \'+\':st.data[st.top-1]=st.data[st.top-1]+st.data[st.top]; st.top--;break; case \'-\':st.data[st.top-1]=st.data[st.top-1]-st.data[st.top]; st.top--;break; case \'*\':st.data[st.top-1]=st.data[st.top-1]*st.data[st.top]; st.top--;break; case \'/\': if (st.data[st.top]!=0) st.data[st.top-1]=st.data[st.top-1]/st.data[st.top]; else { printf(\"\\n\\t除数不能为零!\\n\"); return 0; } st.top--;break; case \'^\':st.data[st.top-1]=pow(st.data[st.top-1],st.data[st.top]); st.top--;break; case \'%\':st.data[st.top-1]=fmod(st.data[st.top-1],st.data[st.top]); st.top--;break; case \'@\':st.data[st.top]=-(st.data[st.top]); break; case \'s\':st.data[st.top]=sin(st.data[st.top]); break; case \'c\':st.data[st.top]=cos(st.data[st.top]); break; case \'q\': if(st.data[st.top]>=0) st.data[st.top]=sqrt(st.data[st.top]); else { printf(\"\\n\\t开方内的数不能小于零!\\n\"); return 0; } break; case \'e\':st.data[st.top]=exp(st.data[st.top]); break; case \'t\':st.data[st.top]=tan(st.data[st.top]); break; case \'a\':st.data[st.top]=abs(st.data[st.top]); break; case \'g\': if(st.data[st.top]>0) st.data[st.top]=log10 (st.data[st.top]); else { printf(\"\\n\\tlog10内的数不能小于等于零!\\n\"); return 0; } break; case \'n\': if(st.data[st.top]>0) st.data[st.top]=log(st.data[st.top]); else { printf(\"\\n\\tln内的数不能小于等于零!\\n\"); return 0; } break; default: d=0; /*将数字字符转换成数值存放到d中*/ while (*postexp>=\'0\' && *postexp=\'0\' && *postexp
三、课程设计总结内容
本次数据结构课程设计，总体来说是获益匪浅的。
第一题，运用C语言编程，熟练C语言在实际生活中的应用。三色球问题在超市抽奖比较常见，不懂得概率多少，总觉得很好中奖。其实连1/10的机会都没有。
第二题，第二题我选了判断中心对称问题。遇到很多难点。即使写出来了也还有很多问题忽略掉了。比如判断输入字符奇偶性等。我利用栈的先进后出原则来进行字符串的判断。想过很多方法来简化数据结构步骤，在寻找中不断进步。
第三题，团队合作很重要。我们小组从起初的一点都没头绪，到后来一起查找资料慢慢找到答案。一步步的完善程序。这种过程很开心。知识，团队的合作让我们有了学习的兴趣。
四、教材及主要参考资料：
《数据结构（C语言版）》，清华大学出版社，严蔚敏等编。 《C程序设计》，清华大学出版社，李春葆编。
《数据结构（C）实验教程》第一章 实验三 ，北京理工大学出版社，李业丽等编
