第一篇：数据结构课程设计
数据结构课程设计
利用栈求表达式的值
2013级计算机科学与技术系
数据结构课程设计
目 录
目 录..................................................................................................................................2 摘要......................................................................................................................................3 1 引言..................................................................................................................................4 1.1问题的提出.............................................................................................................4 1.2 任务与分析............................................................................................................4 2 程序的主要功能................................................................................................................5 2.1 程序功能设计.........................................................................................................5 2.2 附加功能................................................................................................................5 2.3功能函数.................................................................................................................5 3 程序运行平台....................................................................................................................6 4总体设计............................................................................................................................6 4.1 方案总体设计.........................................................................................................6 4.2程序流程图.............................................................................................................7 5程序类的说明....................................................................................................................8 5.1主要函数.................................................................................................................8 5.2 函数间的调用关系..................................................................................................9 5.2.1函数调用流程................................................................................................9 5.2.2函数调用说明................................................................................................9 6系统测试分析..................................................................................................................10 7程序源代码......................................................................................................................13 8心得体会..........................................................................................................................25 9参考文献..........................................................................................................................25
数据结构课程设计
摘要
随着计算机科学与技术的迅猛发展，计算机应用层面的不断普及，利用计算机及相关的计算机编程技术实现对现实生活中一些问题的处理，可以简化生活中的某些问题，给人民生活带来方便。数据结构是一门基于数据类型处理的学科，利用数据结构相关知识处理表达式的合法性及表达式的处理结果可以简化计算、判断表达式。
此软件可以实现判断表达式的合法性，如果表达式合法则进行计算，如果不合法则提醒用户表达式错误，请用户重新输入。在合法的基础上会对表达式进行计算，在计算完成的同时会提醒用户是否继续进行计算，不进行计算则进入是否保存界面。用户可以保存多次记录，并可以随时查看，也可以清楚全部记录，根据用户需求而定。
关键词：表达式的值，数据结构,栈；
数据结构课程设计 引言
1.1问题的提出
数据结构是一门理论性很强的学科、思维抽象、难度较大的课程，是专业课和基础课之间的桥梁。该课程的先行课是计算机基础，c语言程序设计，离散数学等，后续课程有操作系统，数据库原理，软件工程等。通过本门课程的学习，我们应该能够透彻的理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力，而且该课程的研究方法对我们学生在校及工作学习都是很有帮助，意义重大。数据结构是计算机科学与技术的一门专门的核心专业基础课，在该专业起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力都有着极为重要的作用。学好数据结构的最终目的是为了获得新的解决问题的办法。对于现实世界的问题，应该能抽象出一个适当的数学模型，该数学模型在计算机内部的数据结构表示，然后设计一个解决此数学模型的算法，在进行程序编写调试，最后得到问题的解答。
1.2 任务与分析
基于上述数据结构的分析，我们开设了数据结构课程设计这门课。针对这门课程的特点，着重培养我们的动手实践能力，我们的任务是基于visual c++ 6.0运行平台设计出一套完整的c语言算法，解决表达是求值问题。表达式的求值分为几个阶段：首先判断表达式是否正确，针对出现的符号是否是合法字符以及是否是字符重复出现进行判断，此过程运用数据结构中栈的基本原理。然后对于检查过的表达式进行计算，运用数学中的先乘后除再加减，有括号先计算括号的运算规则进行四则运算。最后，在计算完整的基础上询问是否保存本次运行记录，根据相应提示即可进行操作。利用栈求表达式的值，虽然是很简单的程序算法，但是在编写过程中可能也会遇到很多问题，我们组的成员也会通过各种途径进行排难，达到成功运行并解决问题的办法。
数据结构课程设计 程序的主要功能
2.1 程序功能设计
编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。主要功能描述如下：
1、从键盘上输入表达式，以“=” 号结束表达式。
2、分析该表达式是否合法：
（1）是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。（2）是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。
（3）若是其它字符，则返回错误信息。
3、若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。
2.2 附加功能
1、规定表达式的合法性
2、小数计算
3、计算记录的保存与查看
4、其他
（1）规定表达式的合法性，括号配对，不能出现“6++3”、“6+－3”等符号重叠的情况。
（2）表达式开头只能是数字或“（”，表达式中只能有一个“=”。
2.3功能函数
程序中主要包含下面几个功能函数： void initstack()：初始化堆栈 int make_str()：语法检查并计算
int push_num(double num)：将操作数压入堆栈 char procede(char top,char code)：处理操作码
数据结构课程设计
int change_opnd(int operate)：将字符型操作码转换成优先级 int change_opnd(char code)：将操作码压入堆栈 char pop_opnd(opnd *op)：将操作码弹出堆栈 int caculate(int cur_opnd)：简单计算+，-，*，/ double pop_num(num *nu)：弹出操作数 程序运行平台
硬件系统：Intel（R）Core(TM)i3-3240 CPU @ 3.40GHz 3.39GHz, 4GB内存，500GB硬盘。
软件系统：windows xp操作系统，visual c++ 6.0 编译软件。
4总体设计
4.1 方案总体设计
（1）定义一个expression全局表达式结构体expr[1000]存放计算过的表达式(expstr[MAXSIZE])和计算结果(result)、一个计量器(i)、一个表达式字符串、一个操作码栈和一个操作数栈；
（2）把表达式字符串从头到尾逐一扫描，将输入的表达式进行语法检查；（3）第一个字符只能是数字或“（”，最重一个字符只能是“=”；（4）表达式括号必须配对，中间不能出现“=”；
（5）在“（”前面只能是“+、－、*、/、(”，在“+、－、*、/、=、)”前面只能是数字或“）”；
（6）把表达式字符串从头到尾逐一扫描，直到表达式扫描完毕，操作码栈为空；
（7）把字符根据运算优先级别选择操作；
（8）把表达式中的数值部分字符串转成数值压入操作数栈；
（9）是“(”直接压入到操作码栈，级别比操作码栈顶元素高的，把运算符压入操作码栈；
数据结构课程设计
（10）级别比操作码栈低的，弹出操作码栈的栈顶元素和操作数栈的两个栈顶元素，进行运算后再压入操作数栈；
（11）是“)”，若操作码栈顶是“(”，把弹出操作码栈顶元素，否则“)”视为级别最低的元素，重复7；
（12）最后计算出结果并将其存放在expr[i]，计量器加1；（13）重复计算后，将结果保存在文件里，并统计计算次数；（14）查看多次计算结果，以表形式输出；（15）查看本次计算记录，以表形式输出；（16）清除计算记录，重新计算。
4.2程序流程图
main Exit()start()load()ClearFile result()check()
Start2()save()7
数据结构课程设计
5程序类的说明
5.1主要函数
void start(opnd *op,num *nu)//程序主菜单
void start2(opnd *op,num *nu)//第二层计算选择，子菜单 void load()//显示所有计算记录 void save()//保存计算结果 void check()//显示本次计算结果 void result(opnd *op,num *nu)//计算结果
double caculate(opnd *op,num *nu)//简单计算+，-，*，/ 表达式处理函数： int make_str()//语法检查
double change_num(char str[])//数字字符串转成double型数字 char procede(char top,char code)//处理操作码，判断栈的操作 int change_opnd(char code)//字符型操作码转换优先级，非表达式字符返回-2 栈操作函数：
double get_num(num *nu)//查看操作数栈栈顶 double pop_num(num *nu)//操作数栈出栈
int push_num(num *nu,double da)//压入操作数栈 int empty_num(num *nu)//判空 void initstack(num *nu)char get_opnd(opnd *op)//查看栈顶 char pop_opnd(opnd *op)//出栈 int push_opnd(opnd *op,char co)//压栈 int empty_opnd(opnd *op)//判空 void initstack(opnd *op)//初始化栈
数据结构课程设计
5.2 函数间的调用关系 5.2.1函数调用流程
main()：主函数 → start();↗load()→start();start()程序模式函数→清空文件→exit();↘make_str()→result(op,nu)→start2()→start();↗ load → start();start2()子菜单 → save()→ start2();↘ check()→ start2();result(op,nu)计算结果→initstack(op)→initstack(nu)→push_opnd(op,'=')→
↗push_num(nu,change_num(str2));→change_opnd(*ps)↗push_opnd(op,*ps)； ↘procede(get_opnd(op),*ps)→pop_opnd(op);↘push_num(nu,caculate(op,nu))caculate(op,nu)→b=pop_num(nu)→a=pop_num(nu)→pop_opnd(op)
5.2.2函数调用说明
main()函数：调用了一个函数start()，start()判断执行查看所有计算记录函数load()，或是清空以往的所有计算记录，或是退出程序，或是检查输入表达式语法make_str()并计算表达式result(op,nu)的操作。
result(op,nu)函数：是计算表达式，调用了初始化栈函数和字符级别判断change_opnd(*ps)，若是数字，则调用转化数字change_num(str2)然后压入操作数栈，若是运算符，刚调用判断操作procede(get_opnd(op),*ps)，若是“<”,则压入操作码栈push_opnd(op,*ps)，若是“=”，则弹出操作码栈顶pop_opnd(op)，若是“>”，则弹出操作码栈的栈顶元素和操作数栈的两个栈顶元素，进行运算caculate(op,nu)后再压入操作数栈，计算完毕后按start()顺序
数据结构课程设计
运行。
start2()函数：在计算结果后调用跟随的选择菜单，进行查看结果check()、保存结果save()、查看计算记录load()、回到主菜单的操作。
6系统测试分析
(1)程序主界面，根据提示选择相应的输入字母选择相应菜单。在系统第一次运行的时候，查看记录是不会有结果的，应当首先进行计算式子，然后进行保存过，才会有结果。
数据结构课程设计
（2）计算式子，根据需要输入了以上三个式子，计算结果都正确无误。计算完毕，输入e结束计算，程序进入子菜单。
（3）在计算完式子以后进入子菜单选择界面，我们对式子进行保存处理。进入（4）。
（4）对刚刚输入计算的式子进行保存，选择s，提示式子已经被保存下来了。接下来我们回到主界面，查看记录。
数据结构课程设计
（5）我们输入了l，程序返回我们刚刚保存的计算记录，并且进行个数统计。
（6）我们对刚才的保存的记录进行清空处理，按c，确定后，返回结果为所有记录为空，我们也可以对此事的系统进行再次查询处理，结果也会发现是没有记录的。最后我们按e，则整个系统退出。
数据结构课程设计
7程序源代码
#include
#define MAXSIZE 100 #define N 1000 int i=0;
//表达式数
typedef struct expression//表达式结构
{ long double result;
char expstr[MAXSIZE];}expression;expression expr[N];//表达式的一个整体容器s
typedef struct//操作码栈定义
{ char code[MAXSIZE];int top;}opnd;
typedef struct//操作数栈定义
{ double date[MAXSIZE];int top;}num;//《——opnd栈操作——》：
void initstack(opnd *op)//初始化栈
{ op->top=-1;} int empty_opnd(opnd *op)//判断是否为空栈
{ if(op->top==-1)
return 0;else return 1;}
int push_opnd(opnd *op,char co)//入栈
{
数据结构课程设计
if(op->top==MAXSIZE-1)
{
printf(“The ”opnd“ stack is full.”);
return 0;
} op->top++;op->code[op->top]=co;return 1;} char pop_opnd(opnd *op)//出栈
{ char a=' ';if(op->top==-1)
{
printf(“error:The ”opnd“ stack is empty.”);
return a;
} a=op->code[op->top];op->top--;return a;} char get_opnd(opnd *op)//查看栈顶
{ char a=' ';if(op->top==-1)
{
printf(“error:The ”opnd“ stack is empty.”);
return a;
} else
return op->code[op->top];} //《——num栈操作——》： void initstack(num *nu){ nu->top=-1;} int empty_num(num *nu)//判空
{ if(nu->top==-1)
return 0;else return 1;}
数据结构课程设计
int push_num(num *nu,double da)//入栈
{ if(nu->top==MAXSIZE-1)
{
printf(“error:The ”date“ stack is full.”);
return 0;
} nu->top++;nu->date[nu->top]=da;return 1;} double pop_num(num *nu)//出栈
{ double a=' ';if(nu->top==-1)
{
printf(“error:The ”date“ stack is empty.”);
return a;
} a=nu->date[nu->top];nu->top--;return a;} double get_num(num *nu)//查看栈顶
{ if(nu->top!=-1)
return nu->date[nu->top];} //《——结束栈定义操作——》 //《——函数操作——》：
int change_opnd(char code)//将字符型操作码转换成优先级，非表达式字符反回-2 { switch(code)
{
case '=':return 1;break;
case ')':return 2;break;
case '+':return 3;break;
case '-':return 3;break;
case '*':return 4;break;
case '/':return 4;break;
case '(':return 0;break;//操作码级别>=0;
case '1':case '2':case '3':case '4':case '5':case '6':case '7':
case '8':case '9':case '0':case '.': return-1;//操作数级别=-1；
default: return-2;//其它符号级别=-2
数据结构课程设计
} } char procede(char top,char code)//处理操作码，判断栈的操作
{ if(change_opnd(code)==0)//“（”入栈
return('<');else
if(change_opnd(code)==2&&change_opnd(top)==0)//“（”和“）”同时出现，“（”出栈，“）”不入栈
return('=');
else
if(change_opnd(code)<=change_opnd(top))//弹出两个数字和一个符号进行计算
return('>');
else
return('<');//入栈
} double change_num(char str[])//数字字符串转成double型数字
{ char *s=str;int p=1,q=0;//p=小数点前位数，q=小数点后位数
char d[]=“.”,z[]=“0”;double da=0,p1;if(strstr(str,d)==0)//判断是否有小数点
p=strlen(str);else
if(strstr(str,d)==str)//没有输入小数点前的数，如“.032”
{
p=1;
q=strlen(str)-1;
strcpy(str,strcat(z,str));
}
else
{
p=strstr(str,d)-str;
q=strlen(str)-p-1;
}
for(int i=0;i
//小数点前的各位数乘以各自的阶数，然后叠加：123=1*100+2*10+3*1
da=da+((int)str[i]-48)*pow(10,p-i-1);
for(int j=0;j //小数点后的各位数乘以各自的阶数，然后叠加：0.123=1*0.1+2*0.01+3*0.001 da=da+((int)str[strlen(str)-1-j]-48)*pow(0.1,q-j); return da;} 数据结构课程设计 int make_str()//语法检查 { char *p,*p1;int n=0;printf(“n请输入表达式，以“=”结尾：”);gets(expr[i].expstr);p=expr[i].expstr;p1=p; while(1) { if(*p==' ') if(*(p-1)=='=')//语法检查结束 break; else {//没有以“=”结尾 printf(“n表达式以”=“结尾。请重新输入：”); gets(expr[i].expstr); p=expr[i].expstr; n=0; continue; } if(change_opnd(*p)==2)//一个“)”，n-1 n--; if(change_opnd(*p)==0)//一个“(”，n+1 n++; if(*p1==*p)//第一个字符的判断，只能以“数字”或“(”开头，不能有非法字符 if(change_opnd(*p)>0) { printf(“n表达式只能以“数字”或“(”开头。请重新输入：”); gets(expr[i].expstr); p=expr[i].expstr; n=0; continue; } else if(change_opnd(*p)==-2) { printf(“n表达式”%c“为非法字符。请重新输入：”,*p); gets(expr[i].expstr); 数据结构课程设计 p=expr[i].expstr; n=0; continue; } else {//合法刚跳到下一个字符 p=p+1; continue; } if(change_opnd(*p)==-2)//非法字符判断 { printf(“n表达式”%c“为非法字符。请重新输入：”,*p); gets(expr[i].expstr); p=expr[i].expstr; n=0; continue; } if(change_opnd(*p)==0)//“(”前一个字符只能是“+、-、*、/、(” { if(change_opnd(*(p-1))<3&&change_opnd(*(p-1))>4) if(change_opnd(*(p-1))!=0) { printf(“n表达式”%c“或”%c“不符合语法。请重新输入：”,*(p-1),*p); gets(expr[i].expstr); p=expr[i].expstr; n=0; continue; } } if(change_opnd(*p)>0)//“+、-、*、/、=、)”前一个字符只能是数字和“)” if(change_opnd(*(p-1))!=-1) if(change_opnd(*(p-1))!=2) { printf(“n表达式”%c“或”%c“不符合语法。请重新输入：”,*(p-1),*p); gets(expr[i].expstr); p=expr[i].expstr; n=0; continue; } if(change_opnd(*p)==1)//判断表达式中是否有“=”重复出现，最后括号是否配对 数据结构课程设计 { if(*(p+1)!=' ') { printf(“n表达式中”=“，只能出现在表达式结束处。请重新输入：”); gets(expr[i].expstr); p=expr[i].expstr; n=0; continue; } if(n!=0) { printf(“n表达式括号不配。请重新输入：”); gets(expr[i].expstr); p=expr[i].expstr; n=0; continue; } } p=p+1; } return 1;} double caculate(opnd *op,num *nu)//简单计算+，-，*，/ { double b=pop_num(nu),a=pop_num(nu);switch(pop_opnd(op)) { case '+':return(a+b);break; case '-':return(a-b);break; case '*':return(a*b);break; case '/':return(a/b);break; } } void result(opnd *op,num *nu)//计算结果 { char str2[MAXSIZE]=“",str3[2]=”0“;char *ps=expr[i].expstr;initstack(op);//初始化栈 initstack(nu);push_opnd(op,'='); 数据结构课程设计 while(!((*ps=='=')&&(get_opnd(op)=='=')))//检查是表达式和操作码是否到尾 if(change_opnd(*ps)==-1)//操作数处理 { while(change_opnd(*ps)==-1) { strncpy(str3,ps,1);//数字字符一个个取出放在str2 strcat(str2,str3); ps++; } push_num(nu,change_num(str2)); strcpy(str2,”“); } else //操作码处理 { switch(procede(get_opnd(op),*ps)) { case '<':push_opnd(op,*ps);break; case '=':pop_opnd(op);break; case '>':push_num(nu,caculate(op,nu));continue;break; } if(*ps==')'&&get_opnd(op)=='=') { ps++; continue; } if(*ps=='='||get_opnd(op)=='=') continue;//表达式和操作码有一个到尾，则跳出继续循环 ps++; } expr[i].result=get_num(nu); printf(”nt 表达式：%st计算结果：%lfn“,expr[i].expstr,expr[i].result); printf(”t--n“); i++;//表达式个数加1； } void check()//显示计算结果 { for(int n=0;n { printf(”n“); printf(”t%d n“,n+1); 数据结构课程设计 printf(”t 表达式：%s“,expr[n].expstr); printf(”t计算结果：%.2lfn“,expr[n].result); if(expr[n].expstr[0]=='#')break;//只显示当次计算的记录 } printf(”t--n“);} void save()//保存计算结果 { FILE *fp;int m,n;if((fp=fopen(”calculate.dat“,”ab“))==NULL)//创建文件 { printf(”cannot open filen“); return; } if(expr[i-1].expstr[0]=='#')//不能重复保存 { printf(”*提醒：记录已保存过，不需要再次保存。n“); return; } for(n=i;n>0;n--)//记录最后一个#号位置，即未保存的结果的开始位置,重复保存只会追加 if(expr[n-1].expstr[0]=='#') break;strcpy(expr[i].expstr,”#表达式个数：“);//每次保存都统计计算次数 expr[i].result=i-n;i++;for(m=n;m if(fwrite(&expr[m],sizeof(struct expression),1,fp)!=1)//将表达式和计算结果存到文件中 printf(”file write errornn“);fclose(fp);printf(”*提醒：计算记录已经保存nn“);} void load()//显示所有计算记录 { int m;expression e[N];FILE *fp;printf(”n“);if((fp=fopen(”calculate.dat“,”rb“))==NULL)//空文件 { printf(”t--n“); printf(”*提醒：没有记录信息，请进行计算并保存信息:nn“); 数据结构课程设计 return; } for(m=0;fread(&e[m],sizeof(struct expression),1,fp);m++)//按照expression结构一个个读取 { printf(”t%d n“,m+1); printf(”t 表达式：%st计算结果：%.2lfn“,e[m].expstr,e[m].result); if(e[m].expstr[0]=='#')//控制输出不同次计算的记录 { m=-1; printf(”n“); } } printf(”t--n“);fclose(fp);printf(”n“);} void help(){ printf(”t| |n“);printf(”t| 1、请用户正确输入表达式，不得出现非法字符及重复出现。|n“);printf(”t| 2、表达式以 “=”号结尾，负数用（0-X）形式表示。 |n“);printf(”t| 3、请用户及时保存计算结果，否则计算结果会被清除。 |n“);printf(”t| |n“); } //void start(opnd *op,num *nu); void start2(opnd *op,num *nu)//第二层计算选择菜单 { void start(opnd *op,num *nu);char r;while(1) { printf(”t*************************计算表达式的值**********************n“); printf(”t*** ***n“); printf(”t*** 一、查看本次计算记录，请输入“r”或“R” ***n“); printf(”t*** ***n“); printf(”t*** 二、保存本次计算记录，请输入“s”或“S” ***n“); printf(”t*** ***n“); printf(”t*** 三、查看所有计算记录，请输入“l”或“L” ***n“); printf(”t*** ***n“); printf(”t*** 四、回到主菜单，请输入“E”或“e” ***n“); 数据结构课程设计 printf(”t*** ***n“); printf(”t*************************************************************n“); printf(”t请输入： “); scanf(”%s“,&r); if(r=='r'||r=='R') check(); else if(r=='s'||r=='S') save(); else if(r=='l'||r=='L') load(); else { i=0; start(op,nu); } } } void start(opnd *op,num *nu)//程序主导 { char ch,c,g; g='Y'; printf(”t*************************计算表达式的值**********************n“); printf(”t*** ***n“); printf(”t*** 一、计算式子，请输入“Y”或“y” ***n“); printf(”t*** ***n“); printf(”t*** 二、查看记录，请输入“l”或“L” ***n“); printf(”t*** ***n“); printf(”t*** 三、清空记录，请输入“C”或“c” ***n“); printf(”t*** ***n“); printf(”t*** 四、退出程序，请输入“E”或“e” ***n“); printf(”t*** ***n“); printf(”t*************************************************************n“); printf(”t请输入:“); scanf(”%s“,&c); getchar(ch); if(c=='l'||c=='L') { load(); start(op,nu); } else if(c=='Y'||c=='y') 数据结构课程设计 { while(1) { if(g=='Y'||g=='y') { if(make_str())//语法检查 { printf(”t--n“); result(op,nu);//计算 } } else { printf(”nt*提醒：计算结束！nn“); break; } printf(”n继续计算，请输入“Y”或“y”，否则按“E”或“e”键结束计算:“); scanf(”%s“,&g); getchar(ch); } start2(op,nu); } else if(c=='C'||c=='c')//清空文件 { printf(”t--n“); remove(”calculate.dat“); printf(”*提醒：所有记录已经清空。nn“); start(op,nu); } else{ printf(”nt*提醒：结束！nn“); exit(0); } } void main(){ system(”color 1A“);opnd op;//操作码栈 num nu;//操作数栈 printf(”nt ——————————————请注意—————————————n");help();start(&op,&nu);//启动程序 } 数据结构课程设计 8心得体会 （1）设计中遇到的问题及解决过程 调试过程中出现一些逻辑和语法错误，但是语法错误容易纠正，而 逻辑错误则比较难纠正，需要通过多次调试，找出过程中的漏洞。在设计数值转换时，只有抓住小数点为中界条件，找出整数位数和小数位数；在保存计算记录时，不能重复保存，需要断点。这些问题都是靠仔细分析，逐步琢磨出来的，要勤动手，先设计，后实现。 （2）设计体会和收获。 发现自己也能解决有点复杂的问题,程序设计思想上有了很大的提高，学会了仔细分析问题的关键和辅助功能，在应用上设计程序要符合大众化的思维方式。 （3）因为时间问题，只能做出表达式基本运算，在以后的时间里，我会改善这个计算程序，让它能计算更复杂的表达式，如加上sin,cos时的运算。 9参考文献 【1】．[美] Gary Bronson 著，刘勇译．Programming Development and Design Using C++, Second Edition（C++程序开发与设计，第2版）．北京：人民邮电出版社，2002 【2】．王萍．C++面向对象程序设计．北京：清华大学出版社．2002 【3】．罗建军等．C++程序设计教程（第2版）．北京：高等教育出版社，2004 【4】．谭浩强．C++程序设计．北京：清华大学出版社．2004 【5】．黄维通．Visual C++面向对象与可视化程序设计（第2版）．北京：清华大学出版社，2007 【6】．张基温．C++程序设计基础．北京：高等教育出版社，2001 【7】．刁成嘉．面向对象C++程序设计．北京：机械工业出版社，2004 【8】．郑莉等．C++语言程序设计（第2版）．北京：清华大学出版社，2001 数 据 结 构 课程设计报告 题 目： 一元多项式计算 专 业： 信息管理与信息系统 班 级： 2012级普本班 学 号： 201201011367 姓 名： 左帅帅 指导老师： 郝慎学 时 间： 一、课程设计题目分析 本课程设计要求利用C语言或C++编写，本程序实现了一元多项式的加法、减法、乘法、除法运算等功能。 二、设计思路 本程序采用C语言来完成课程设计。 1、首先，利用顺序存储结构来构造两个存储多项式A(x)和 B(x)的结构。 2、然后把输入，加，减，乘，除运算分成五个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块。 3、然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能，尽量减少程序运行时错误的出现。 4、最后编写main()主函数以实现对多项式输入输出以及加、减、乘、除，调试程序并将不足的地方加以修改。 三、设计算法分析 1、相关函数说明： (1)定义数据结构类型为线性表的链式存储结构类型变量 typedef struct Polynomial{} (2)其他功能函数 插入函数void Insert(Polyn p,Polyn h) 比较函数int compare(Polyn a,Polyn b) 建立一元多项式函数Polyn Create(Polyn head,int m) 求解并建立多项式a+b，Polyn Add(Polyn pa,Polyn pb) 求解并建立多项式a-b，Polyn Subtract(Polyn pa,Polyn pb)2 求解并建立多项式a*b，Polyn Multiply(Polyn pa,Polyn pb) 求解并建立多项式a/b，void Device(Polyn pa,Polyn pb) 输出函数输出多项式，void Print(Polyn P) 销毁多项式函数释放内存，void Destroy(Polyn p) 主函数，void main（） 2、主程序的流程基函数调用说明(1)typedef struct Polynomial { float coef; int expn; struct Polynomial *next;} *Polyn,Polynomial; 在这个结构体变量中coef表示每一项前的系数，expn表示每一项的指数，polyn为结点指针类型，属于抽象数据类型通常由用户自行定义，Polynomial表示的是结构体中的数据对象名。 (2)当用户输入两个一元多项式的系数和指数后，建立链表，存储这两个多项式，主要说明如下： Polyn CreatePolyn(Polyn head,int m)建立一个头指针为head、项数为m的一元多项式 p=head=(Polyn)malloc(sizeof(struct Polynomial));为输入的多项式申请足够的存储空间 p=(Polyn)malloc(sizeof(struct Polynomial));建立新结点以接收数据 Insert(p,head);调用Insert函数插入结点 这就建立一元多项式的关键步骤 (3)由于多项式的系数和指数都是随即输入的，所以根据要求需要对多项式按指数进行降幂排序。在这个程序模块中，使用链表，根据对指数大小的比较，对各种情况进行处理，此处由于反复使用指针对各个结点进行定位，找到合适的位置再利用void Insert(Polyn p,Polyn h)进行插入操作。(4)加、减、乘、除、的算法实现： 在该程序中，最关键的一步是实现四则运算和输出，由于加减算法原则是一样，减法可通过系数为负的加法实现；对于乘除算法的大致流程都是：首先建立多项式a*b，a/b，然后使用链表存储所求出的乘积，商和余数。这就实现了多项式计算模块的主要功能。 (5)另一个子函数是输出函数 PrintPolyn（）； 输出最终的结果，算法是将最后计算合并的链表逐个结点依次输出，便得到整链表，也就是最后的计算式计算结果。由于考虑各个结点的指数情况不同，分别进行了判断处理。 四、程序新点 通过多次写程序，发现在程序在控制台运行时总是黑色的，本次写程序就想着改变一下，于是经过查资料利用system(“Color E0”);可以函数解决，这里“E0，”E是控制台背景颜色，0是控制台输出字体颜色。 五、设计中遇到的问题及解决办法 首先是，由于此次课程设计里使用指针使用比较多，自己在指针多的时候易脑子混乱出错，对于此问题我是采取比较笨的办法在稿纸上写明白后开始进行 4 代码编写。 其次是，在写除法模块时比较复杂，自己通过查资料最后成功写出除法模块功能。 最后是，前期分析不足开始急于写代码，中途出现各种问题，算是给自己以后设计时的一个经验吧。 六、测试（程序截图） 1.数据输入及主菜单 2.加法和减法模块 3.乘法和除法模块 七、总结 通过本次应用C语言设计一元多项式基本计算程序，使我更加巩固了C语言程序设计的知识，以前对指针这一点使用是比较模糊，现在通过此次课程设计对指针理解的比较深刻了。而且对于数据结构的相关算法和函数的调用方面知识的加深。本次的课程设计，一方面提高了自己独立思考处理问题的能力；另一方面使自己再设计开发程序方面有了一定的小经验和想法，对自己以后学习其他语言程序设计奠定了一定的基础。 八、指导老师评语及成绩 附录：（课程设计代码） #include float coef;6 int expn; struct Polynomial *next;} *Polyn,Polynomial; //Polyn为结点指针类型 void Insert(Polyn p,Polyn h){ if(p->coef==0)free(p); //系数为0的话释放结点 else { Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn { q1=q2;q2=q2->next;} if(q2&&p->expn==q2->expn)//将指数相同相合并 { q2->coef+=p->coef; free(p); if(!q2->coef)//系数为0的话释放结点 { q1->next=q2->next;free(q2);} } else { p->next=q2;q1->next=p; }//指数为新时将结点插入 } 7 } //建立一个头指针为head、项数为m的一元多项式 Polyn Create(Polyn head,int m){ int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立新结点以接收数据 printf(“请输入第%d项的系数与指数:”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //调用Insert函数插入结点 } return head;} //销毁多项式p void Destroy(Polyn p){ Polyn q1,q2; q1=p->next;8 q2=q1->next; while(q1->next) { free(q1); q1=q2;//指针后移 q2=q2->next; } } //输出多项式p int Print(Polyn P){ Polyn q=P->next; int flag=1;//项数计数器 if(!q)//若多项式为空，输出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系数大于0且不是第一项 9 if(q->coef!=1&&q->coef!=-1)//系数非1或-1的普通情况 { printf(“%g”,q->coef); if(q->expn==1)putchar('X'); else if(q->expn)printf(“X^%d”,q->expn); } else { if(q->coef==1){ if(!q->expn)putchar('1'); else if(q->expn==1)putchar('X'); else printf(“X^%d”,q->expn);} if(q->coef==-1){ if(!q->expn)printf(“-1”); else if(q->expn==1)printf(“-X”); else printf(“-X^%d”,q->expn);} } q=q->next; flag++; } printf(“n”);} int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn)return 1; else if(!a||a->expn else return 0; } else if(!a&&b)return-1;//a多项式已空，但b多项式非空 else return 1;//b多项式已空，但a多项式非空 } //求解并建立多项式a+b，返回其头指针 Polyn Add(Polyn pa,Polyn pb){ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 11 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case-1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break;12 } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//当相加系数为0时，释放该结点 } return headc;} //求解并建立多项式a-b，返回其头指针 Polyn Subtract(Polyn pa,Polyn pb){ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p)//将pb的系数取反 { p->coef*=-1;p=p->next;} pd=Add(pa,h); for(p=h->next;p;p=p->next) //恢复pb的系数 p->coef*=-1;13 return pd;} //求解并建立多项式a*b，返回其头指针 Polyn Multiply(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hf->next=NULL; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//调用Insert函数以合并指数相同的项 } } return hf;} //求解并建立多项式a/b，返回其头指针 void Device(Polyn pa,Polyn pb){ Polyn hf,pf,temp1,temp2; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点,存储商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点，存储余数 pf->next=NULL; temp1=(Polyn)malloc(sizeof(struct Polynomial)); temp1->next=NULL; temp2=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next=NULL; temp1=Add(temp1,pa); while(qa!=NULL&&qa->expn>=qb->expn) { temp2->next=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next->coef=(qa->coef)/(qb->coef); temp2->next->expn=(qa->expn)-(qb->expn); Insert(temp2->next,hf); pa=Subtract(pa,Multiply(pb,temp2));15 qa=pa->next; temp2->next=NULL; } pf=Subtract(temp1,Multiply(hf,pb)); pb=temp1; printf(“商是:”); Print(hf); printf(“余数是:”); Print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“Color E0”);Polyn pa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值NULL printf(“请输入A(x)的项数:”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多项式A printf(“n”);printf(“请输入B(x)的项数:”);16 scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多项式B printf(“n”);printf(“**********************************************n”);printf(“* 多项式操作菜单 printf(”**********************************************n“);printf(”tt 1.输出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.减法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){ printf(”执行操作:“); scanf(”%d“,&flag); switch(flag) { case 1: printf(”多项式A(x):“);Print(pa);*n”); printf(“多项式B(x):”);Print(pb); break; case 2: pc=Add(pa,pb); printf(“多项式A(x)+B(x):”);Print(pc); Destroy(pc);break; case 3: pd=Subtract(pa,pb); printf(“多项式A(x)-B(x):”);Print(pd); Destroy(pd);break; case 4: pf=Multiply(pa,pb); printf(“多项式A(x)*B(x):”); Print(pf); Destroy(pf); break; case 5: Device(pa,pb);18 break; case 6: exit(0); break; } } Destroy(pa); Destroy(pb);} 数据结构课程设计 1.赫夫曼编码器 设计一个利用赫夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。要求： 1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2)初始化：键盘输入字符集大小26、26个字符和26个权值（统计一篇英文文章中26个字母），建立哈夫曼树； 3)编码：利用建好的哈夫曼树生成哈夫曼编码； 4)输出编码（首先实现屏幕输出，然后实现文件输出）； 5)界面优化设计。 代码如下： #include typedef struct HTNode //结构体 { int Weight; char ch;int Parent,Lchild,Rchild;}HTNode;typedef char * * HCode; void Save(int n,HTNode *HT) //把权值保存到文件 { FILE * fp; int i; if((fp=fopen(“data.txt”,“wb”))==NULL) { printf(“cannot open filen”); return; } for(i=0;i if(fwrite(&HT[i].Weight,sizeof(struct HTNode),1,fp)!=1) printf(“file write errorn”); fclose(fp); system(“cls”); printf(“保存成功！”); } void Create_H(int n,int m,HTNode *HT) //建立赫夫曼树，进行编码 { int w,k,j;char c;for(k=1;k<=m;k++){ if(k<=n) { printf(“n请输入权值和字符(用空格隔开): ”); scanf(“%d”,&w); scanf(“ %c”,&c);HT[k].ch=c; HT[k].Weight=w; } else HT[k].Weight=0; HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;} int p1,p2,w1,w2; for(k=n+1;k<=m;k++){ p1=0;p2=0; w1=32767;w2=32767; for(j=1;j<=k-1;j++) { if(HT[j].Parent==0) { if(HT[j].Weight { w2=w1;p2=p1; w1=HT[j].Weight; p1=j; } else if(HT[j].Weight { w2=HT[j].Weight; p2=j; } } } HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].Weight=HT[p1].Weight+HT[p2].Weight; HT[p1].Parent=k;HT[p2].Parent=k; } printf(“输入成功！”);} void Coding_H(int n,HTNode *HT) //对结点进行译码 { int k,sp,fp,p;char *cd;HCode HC; HC=(HCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char));cd[n-1]=' '; printf(“************************n”);printf(“Char Codingn”); for(k=1;k<=n;k++) { sp=n-1;p=k;fp=HT[k].Parent; for(;fp!=0;p=fp,fp=HT[fp].Parent) if(HT[fp].Lchild==p) cd[--sp]='0'; else cd[--sp]='1'; HC[k]=(char *)malloc((n-sp)*sizeof(char)); strcpy(HC[k],&cd[sp]); printf(“%c %sn”,HT[k].ch,HC[k]); } printf(“************************n”);free(cd);} void Read(int n,HTNode *HT) //从文件中读出数据 { int i;FILE * fp;if((fp=fopen(“data.txt”,“rb”))==NULL){ printf(“cannot open filen”); exit(0);} for(i=0;i fread(&HT[i].Weight,sizeof(struct HTNode),1,fp);// printf(“%d n”,HT[i].Weight); } Coding_H(n,HT); fclose(fp);} void Print_H(int m,HTNode *HT) //输出赫夫曼造树过程 { int k;printf(“************************n”);printf(“Num Weight Par LCh RCh n”);for(k=1;k<=m;k++){ printf(“%d ”,k); printf(“ %d”,HT[k].Weight); printf(“ %d”,HT[k].Parent); printf(“ %d”,HT[k].Lchild); printf(“ %dn”,HT[k].Rchild); } printf(“************************n”);} void Decode(int m,HTNode *HT) //对输入的电文进行译码 { int i,j=0;char a[10];char endflag='2';i=m;printf(“输入发送的编码，以‘2’结束:”);scanf(“%s”,&a);printf(“译码后的字符：”);while(a[j]!='2'){ if(a[j]=='0') i=HT[i].Lchild; else i=HT[i].Rchild; if(HT[i].Lchild==0) //HT[i]是叶结点 { printf(“%c”,HT[i].ch); i=m; //回到根结点 } j++;} printf(“n”);if(HT[i].Lchild!=0&&a[j]!='2') printf(“ERROR”);} int main() //主函数 { int n,m,c;HTNode HT[N];do { system(“color 2f”); //运行环境背景颜色.printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt 赫夫曼编译码系统 ttt”); printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt1.输入权值、字母nttt2.把数据写入文件nttt3.输出赫夫曼编码表nttt”); printf(“4.输出赫夫曼译码表nttt5.输入编码并译码.nttt6.从文件中读出数据nttt7.退出”); printf(“nnttt请选择:”); scanf(“%d”,&c); switch(c) { case 1:system(“cls”);printf(“输入多少结点:”); scanf(“%d”,&n);m=2*n-1;Create_H(n,m,HT);break; case 2:system(“cls”);Save(n,HT);break; case 3:system(“cls”);Print_H(m,HT);break; case 4:system(“cls”);Coding_H(n,HT);break; case 5:system(“cls”);Decode(m,HT);break; case 6:system(“cls”);Read(n,HT);break; case 7:system(“cls”);exit(0); } }while(1);return 0;} 运行界面如下： 2.学生成绩管理（链表实现）要求： 实现如下功能：增加、查找、删除、输出、退出。 代码如下： #include //定义成绩信息结构体 { char Number[20];char Name[20];char Chinese[20];char English[20];char Math[20];}score;typedef struct node_score //定义成绩信息链表结点，包括数据域和指针域 { score data;struct node_score *next;}node_score,*p_node_score;p_node_score headScore;//定义链表的头指针为全局变量 void PrintScore(score s)//输出信息函数 { printf(“ %10s”,s.Number);printf(“ | %-6s”,s.Name);printf(“ | %-3s”,s.Chinese);printf(“ | %-3s”,s.English); printf(“ | %-3sn”,s.Math);} void View()//输出函数 { p_node_score pNodeScore; pNodeScore=headScore;printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”);while(pNodeScore!= NULL){ PrintScore(pNodeScore->data);//输出学生信息和成绩信息 pNodeScore=pNodeScore->next;} } void Add(){ p_node_score pNodeScore;// 定义一个节点 pNodeScore=(p_node_score)malloc(sizeof(node_score));//为节点分配存储空间 printf(“请输入学号：”);scanf(“%s”,pNodeScore->data.Number);printf(“请输入姓名：”);scanf(“%s”,pNodeScore->data.Name);printf(“请输入语文成绩：”);scanf(“%s”,pNodeScore->data.Chinese);printf(“请输入英语成绩：”);scanf(“%s”,pNodeScore->data.English);printf(“请输入高数成绩：”);scanf(“%s”,pNodeScore->data.Math);if(headScore==NULL){ //如果头结点为空 headScore=pNodeScore; pNodeScore->next=NULL;} else { //如果头结点不为空 pNodeScore->next=headScore; headScore=pNodeScore;//将头结点新结点 } } void Input(){ int n,i;printf(“输入几个学生的数据：”);scanf(“%d”,&n);for(i=0;i Add();printf(“输入成功！”);} int Delete(){ p_node_score pNodeScore,p1;//p1为pNodeScore的前驱 p1=headScore;if(p1==NULL){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char DeleteNumber[20]; printf(“请数入要删除的学生学号:”);scanf(“%s”,DeleteNumber);if(strcmp(p1->data.Number,DeleteNumber)==0) { //如果要删除的结点在第一个 headScore=p1->next; pNodeScore=p1; printf(“学号为%s的学生信息已经删除！n”,DeleteNumber); return 0;} else { pNodeScore=p1->next; while(pNodeScore!=NULL) { if(strcmp(pNodeScore->data.Number,DeleteNumber)==0) { p1->next=pNodeScore->next; printf(“学号为%s的学生信息已经删除！n”,DeleteNumber); return 0; } else { //否则，结点向下一个，p1仍为pNodeScore的前驱 p1=pNodeScore; pNodeScore=pNodeScore->next; } } } printf(“没有此学号的学生！”);} int Change(){ p_node_score pNodeScore; pNodeScore=headScore;if(pNodeScore==NULL){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char EditNumber[20];printf(“请输入你要修改的学生学号：”);scanf(“%s”,EditNumber);while(pNodeScore!=NULL){ if(strcmp(pNodeScore->data.Number,EditNumber)==0) { //用strcmp比较两字符串是否相等，相等则返回0 printf(“原来的学生成绩信息如下：n”);//输出原来的成绩信息 printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”); PrintScore(pNodeScore->data); printf(“语文新成绩:”); scanf(“%s”,pNodeScore->data.Chinese); printf(“英语新成绩:”); scanf(“%s”,pNodeScore->data.English); printf(“高数新成绩:”); scanf(“%s”,pNodeScore->data.Math); printf(“成绩已经修改！”); return 0; } pNodeScore=pNodeScore->next;//如果不相等，pNodeScore则指向下一个结点 } printf(“没有此学号的学生！n”);//如果找到最后都没有，则输出没有此学号的学生 } int Find(){ p_node_score pNodeScore; pNodeScore=headScore;if(pNodeScore==NULL){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char FindNumber[20];printf(“请输入你要查找的学生学号：”);scanf(“%s”,FindNumber);while(pNodeScore!=NULL){ if(strcmp(pNodeScore->data.Number,FindNumber)==0) { printf(“你要查找的学生成绩信息如下：n”); printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”); PrintScore(pNodeScore->data); return 0; } pNodeScore=pNodeScore->next;} printf(“没有此学号的学生！n”);} int main() //主函数 { int choice=0;headScore=NULL;int c;do { system(“color 2f”); //运行环境背景颜色.printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt 学生成绩管理系统 ttt”); printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt1.输入成绩信息nttt2.输出成绩信息nttt3.添加成绩信息nttt”); printf(“4.修改成绩信息nttt5.删除成绩信息nttt6.查询成绩信息nttt7.退出”); printf(“nnttt请选择:”); scanf(“%d”,&c); switch(c) { case 1:system(“cls”);Input();break; case 2:system(“cls”);View();break; case 3:system(“cls”);Add();break; case 4:system(“cls”);Change();break; case 5:system(“cls”);Delete();break; case 6:system(“cls”);Find();break; case 7:system(“cls”);exit(0); } }while(1);return 0;} 运行界面如下： 课程设计报告的内容 设计结束后要写出课程设计报告,以作为整个课程设计评分的书面依据和存档材料.设计报告以规定格式的电子文档书写,打印并装订,排版及图,表要清楚,工整.装订顺序如下:封面、目录、正文.正文包括以下7个内容: 1.需求分析 陈述说明程序设计的任务,强调的是程序要做什么，需要什么结果、所能达到的功能.2.概要设计 说明本程序中用到的所有抽象数据类型的定义,主程序的流程以及各程序模块之间的层次(调用)关系.3.详细设计 实现概要设计中定义的所有数据类型,对每个操作只需要写出伪码算法;对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为:按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);可采用流程图、N S 图进行描述,画出函数和过程的调用关系图.4.调试分析 内容包括: a.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析;b.算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和 改进设想; c.经验和体会等.5.测试结果 列出你的测试结果,包括输入和输出.这里的测试数据应该完整和严格,最好多于需求分析中所列.6.参考文献 列出参考的相关资料和书籍.封面格式如下： 数据结构课程设计报告 班级：_____ _____ _____ _________ 姓名：____________________ 指导教师：___________________ 成绩：__________________________ 信息工程学院 年月日 目录 1.需求分析 ……………………………………………… 22．概要设计………………………………………………2 3.详细设计 ………………………………………………2 4.调试分析 ………………………………………………2 5.测试结果… ……………………………………………2 参考文献 …………………………………………………6 附录…………………………………………………… 一、需求分析 二、概要设计 三、详细设计 四、调试分析 五、测试结果 六、参考文献 七、附录 附录为程序代码！4 课程设计题目 1、运动会分数统计 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=10 , w=8 , n=15）功能要求： 1).可以输入各个项目的前三名或前五名的成绩； 2).能统计各学校总分（用链表）； 3).可以按学校编号、学校总分、男女团体总分排序输出（快速、基数）； 4).可按学校编号查询学校某个项目的情况；可按项目编号查询取得前三或前五名的学校。 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。 测试数据：要求使用 1、全部合法数据； 2、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明； 2、迷宫求解 任务：可以读入一个任意大小的迷宫数据，分别用广度和深度搜索的方法求出一条走出迷宫的路径，并将路径输出（最佳路径）； 要求：以较为直观的方式显示结果 3、Huffman编码 任务 ：对一篇英文文章，统计各字符出现的次数，实现Huffman编码； 要求：输出每个字符出现的次数和编码，其中求最小权值要求用堆实现； 4、营业窗口队列模拟 任务：实现具有n（n=3）个窗口的现实队列模拟，统计每人的等待时间。要求： 1).随机产生顾客的到达时间和服务时间存盘。2).利用存盘数据实现队列的插入和删除。2).当有顾客离开时，根据队列长度调整队尾。3).考虑顾客中途离队的情况。4).考虑顾客具有优先级的情况。 5、公交线路提示 任务：建立南京主要公交线路图。要求：输入任意两站点，给出最佳的乘车线路和转车地点。 6、家谱管理系统 任务：实现具有下列功能的家谱管理系统 功能要求： 1).输入文件以存放最初家谱中各成员的信息，成员的信息中均应包含以下内容：姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡），也可附加其它信息、但不是必需的。 2).实现数据的存盘和读盘。3).以图形方式显示家谱。 4).显示第n 代所有人的信息。 5).按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）。6).按照出生日期查询成员名单。7).输入两人姓名，确定其关系。8).某成员添加孩子。 9).删除某成员（若其还有后代，则一并删除）。10).修改某成员信息。 11).按出生日期对家谱中所有人排序。 12).打开一家谱时，提示当天生日的健在成员。 要求：建立至少30个成员的数据，以较为直观的方式显示结果，并提供文稿形式以便检查。 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求相关数据要存储在数据文件中。测试数据：要求使用 1、全部合法数据； 2、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明； 7、排序算法比较 设计要求：利用随机函数产生10个样本，每个样本有50000随机整数，利用直接插入排序、折半插入排序，表插入排序，希尔排序，起泡排序、快速排序、选择排序、堆排序，归并排序，基数排序十种排序方法进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的平均时间（统计为图表坐标形式）。 8、算术表达式求值 [问题描述] 一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。[基本要求]（1）从键盘读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。 9、电子小字典 基本要求：建立一个微型电子字典，实现生词的加入，单词的查找、删除，修改等操作。 数据结构：键树 10、校园导游程序 [问题描述]用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。[基本要求]（1）查询各景点的相关信息； （2）查询图中任意两个景点间的最短路径。（3）查询图中任意两个景点间的所有路径。 （4）增加、删除、更新有关景点和道路的信息。 11、稀疏矩阵相乘 任务：以三元组形式存储稀疏矩阵，实现矩阵相乘。 12、平衡二叉树 任务：平衡二叉树的建立、结点的插入和删除。 13、B-树 任务：3阶B-树的结点的插入和删除。 14、HASH表 任务：以班级学生姓名（拼音）为关键字，建立HASH涵数，实现HASH表存储，用链地址方法解决冲突。 15、„„（自选合适的题目） 成绩评定细则： 1.正确性：程序是否可以运行，结果是否正确（20分）2.功能的完备性：是否实现要求的所有子功能（20分） 3.课程设计报告中的算法说明的清晰程度，课程设计报告中总结的深刻程度（20分）4.独立完成情况(40分）总计：100分 加分项目： 1.健壮性：异常处理的情况 2.可读性：代码编写是否规范，是否便于阅读。如函数、变量命名，‘{ }’的缩进，关键位置适量注释等 3.功能的完善：除要求实现的功能外，完成了其它的功能，实现了功能的完善 4.界面的设计：可视化界面，或者交互良好的DOS界面 5.……（自荐加分项目） 代码量要求：>=1000行。 代码总量 = 课设题目1 代码量 + 课设题目2 代码量…… 若代码总量低于1000行，则成绩按比例打折。 编程语言：C或C++语言 编程环境：Microsoft Visual C++ 6.0 检查方式: 1.总体上检查程序的代码量，正确性，可读性，健壮性，功能的完备性,代码量，程序的结构是否合理；局部检查三个以上函数块 2.检查程序时同时检查课程设计报告的电子文档 时间安排： 上机时间安排 课程设计报告上交时间 3 课程设计检查时间 课程设计报告要求： 1.所有的课程设计报告，均要有封面，包括：课题名称、班级、学号、学生姓名、成绩和指导教师； 2.给出自己采用的数据结构； 3.给出算法设计思想； 4.给出实现的源程序，并在必要的代码处给出注释； 5.给出测试数据和结果； 6.给出算法的时间复杂度、另外可以提出算法的改进方法； 7.给出结束语：说明完成课程设计的情况，心得体会；课程设计报告的电子文档在上机检查程序时一并检查；书面文档在指定的时间内上交。第二篇：2012数据结构课程设计
第三篇：数据结构课程设计
第四篇：《数据结构》课程设计文档格式（定稿）
第五篇：课程设计(数据结构)
点击咨询 