数据结构课程设计报告1

《数据结构课程设计报告1》由会员分享，可在线阅读，更多相关《数据结构课程设计报告1（28页珍藏版）》请在装配图网上搜索。

1、数据结构课程设计报告一、 问题描述与分析1、 课程设计目的：数据结构主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法、并对算法的效率进行简单的分析和讨论。数据结构时介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等重要基础，广泛的应用于信息学、系统工程学等各种领域。 数据结构课程设计是为数据结构课程独立开发的实践性教学环节。数据结构课程设计对于巩固数据结构知识，加强学生的实际动手能力和提高学生综合素质是十分必要的。 课程设计的目的：1 要求学生达到

2、熟练掌握C语言的基本知识和技能。2 了解并掌握数据结构与算法的实际方法，具备初步的独立分析和设计能力。3 提高程序设计和调试能力。学生通过上机实习，验证自己实际的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。4 培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。5 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。二、课程设计内容课题一：一元多项式计算1、问题描述1）、能够按照指数降序排列建立并输出多项式；2）、能够完成两个多项式的相加、相减，并将结果输入。2、要求在上交资料中请写明：存储结构、多项式相加的基本

3、过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。3、运行环境： Microsoft Visual C+ 6.0。Visual C+(简称VC)是Microsoft公司推出的目前使用极为广泛的基于Windows平台的C+可视化开发环境。Visual C+ 6.0提供的控制台应用程序对学习和掌握标准C+内容非常有利。“可视”的资源编辑器与MFC类以及应用程序向导，为快速高效地开发出功能强大的Windows应用程序提供了极大的方便。利用Visual C+ 6.0进行Internet、数据库及多媒体等多方面的程序开发也很容易。4、源程序：#in

4、clude iostreamusing namespace std;#define MAXSIZE 10typedef structint xi;int zhi;DataType;typedef struct nodeDataType dataMAXSIZE;int length;Dx,*PDx;PDx Init_List()Dx *S;S=(Dx *)malloc(sizeof(Dx);if(S)S-length=0;return S;int Empty(Dx *S)if(S-length=0)return 1;else return 0;int In_list(Dx *S,DataType

5、 a)/建立多项式存储结构if(S&S-lengthlength+;S-dataS-length-1=a;return 1;else return 0;int Insert_list(Dx *S,int j,DataType e)/插入if(S&S-lengthlength+;for(int i=S-length-1;ij;i-)S-datai=S-datai-1; S-dataj=e;return 1;else return 0;int Delete_list(Dx *S,int m)/m就是数组下标if(!S)cout多项式不存在！endl;return -1;if(mS-length)c

6、out删除位置不合法！endl;return 0;for(int j=m;jlength;j+)S-dataj-1=S-dataj;S-length-;return 1;PDx Luru(int n)/录入多项式，并存储起来,n为多项式的项数！Dx *S;S=Init_List();DataType e;cout按从高指数到低指数，输入一元多项式的系数和指数；endl;for(int i=0;in;i+)coute.zhi;if(S-length-1=0&e.zhi=S-dataS-length-1.zhi)|e.zhi0)i-;cout输入指数大于前一项错误请重输或小于0！endl;cont

7、inue;coute.xi;In_list(S,e);return S;void print(Dx *S)for(int i=0;ilength;i+)if(i0&S-datai.xi=0)cout+;coutdatai.xiXdatai.zhi;coutendl;PDx Add(Dx *S1,Dx *S2)Dx *S3;S3=Init_List();for(int x=0;xlength;x+)S3-length+;S3-dataS3-length-1=S1-datax;for(int i=0;ilength;i+) for(int j=0;jlength;j+) if(S2-datai.z

8、hi=S3-dataj.zhi)S3-dataj.xi+=S2-datai.xi;break;else if(S2-datai.zhiS3-dataj.zhi)Insert_list(S3,j,S2-datai);break;if(S2-datai.zhidataS3-length-1.zhi)In_list(S3,S2-datai);return S3;PDx Sub(Dx *S1,Dx *S2)/S1-S2Dx *S3;S3=Init_List();DataType e;for(int x=0;xlength;x+)S3-length+;S3-dataS3-length-1=S1-data

9、x;for(int i=0;ilength;i+) for(int j=0;jlength;j+) if(S2-datai.zhi=S3-dataj.zhi)S3-dataj.xi-=S2-datai.xi;if(S3-dataj.xi=0)Delete_list(S3,j+1);break;else if(S2-datai.zhiS3-dataj.zhi)e=S2-datai;e.xi=-1*e.xi;Insert_list(S3,j,e);break;if(S2-datai.zhidataS3-length-1.zhi)e=S2-datai;e.xi=-1*e.xi;In_list(S3,

10、e);return S3;PDx Bin(Dx *S1,Dx *S2)Dx *S3;S3=Init_List();DataType e,a;a.xi=0;a.zhi=0;In_list(S3,a);for(int i=0;ilength;i+)for(int j=0;jlength;j+)e.xi=S1-datai.xi*S2-dataj.xi;e.zhi=S1-datai.zhi*S2-dataj.zhi;for(int k=0;klength;k+)if(e.zhi=S3-datak.zhi)S3-datak.xi+=S2-dataj.xi;break;else if(e.zhiS3-da

11、tak.zhi)Insert_list(S3,k,e);break;if(S3-length-2=0&e.zhidataS3-length-2.zhi)Insert_list(S3,S3-length-1,e);return S3; int main(int argc,int _TCHAR,int argv)Dx *S1,*S2,*S3,*S4,*S5;int i,j;couti;S1=Luru(i);coutj;S2=Luru(j);S3=Add(S1,S2);S4=Sub(S1,S2);S5=Bin(S1,S2);cout第一个多项式:endl;print(S1);cout第二个多项式:e

12、ndl;print(S2);cout两多项式的和:endl;print(S3);cout两多项式的差endl;print(S4);return 0;5、调试结果:(1) 首先运行文件一元多项式kl.exe （2）输入信息即输入两一元个多项式：y1=x3+2x2+3x+1 y2=4x3+5x2+6x+8（3）输出结果：课程二：运动会分数统计1、问题描述参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自

13、己设定。（m=20,nm+w|s=0)printf(此次运动会不包括这个项目.nnn); 想在每次查询结束想返回主菜单进行其它项时，应在main( )函数中调用其它函数时再调用main( )函数，如： switch(choice) case 1: inputinformation();writedata();readdata();main(); case 2: output();main(); case 3: inquiry();main(); case 4: readdata();main(); 程序出现语法错误，发现是输入名次信息的地方忘带地址符&，或是程序不完整，只写了一个大括号。如：

14、printf(*名次:); scanf(%d,&hi.cj.ranges);6.2调试分析：(1).函数调用。函数调用是语言中一块十分重要部分，它可以把一个程序分成若干部分，然后进行配置，所以这块内容对我们很重要。(2).对结构体的不熟练。刚开始对结构体不太了解，使调试程序时费了我不少的时间。结构体的嵌套使我很费力气，通过长时间的运用，终于可以得心应手。结构体在我的实习中站了很大的比重，我也很重视它。通过与线性表，循环等的有机搭配，我完成了实习任务。(3).循环的问题。这是我很苦恼，大量的循环语句的应用，分析。使我很头疼，循环是计算机语言中很重要的部分，什么程序也离不开循环，这个问题的解决使我

15、有了坚实的基础。对多层循环的应用也有了深刻的理解。6.3调试结果：(1)首先运行文件运动会统计分数7.exe(2) 输入信息：程序首先赋初值，定义学校的个数为2，男生项目为1，女生项目为1。输入1得到进入输入信息模块。按回车键可得到学校的得分信息和按编号获得的所以信息。(3)输出信息：输入2进入输出信息模块，该模块分四项: 按学校编号输出: 按学校总分输出： 按男团总分输出： 按女团总分输出： 输入2返回输出信息模块，输入0返回主菜单。(4)查询信息：输入3进入信息查询模块： 按学校编号查询 按项目编号查询 输入错误信息时给出提示： 输入2继续查询，输入0返回主菜单(5) 调用信息输入4时显示

16、出所有的信息：7源程序：#include#include#include #include #define n 2/学校数目 #define m 1/男子项目数目 #define w 1/女子项目数目#define null 0typedef struct int itemnum; /项目编号 int top; /取名次的数目 int range5; /名次 int mark5; /分数itemnode; /定义项目结点的类型typedef structint schoolnum; /学校编号 int score; /学校总分 int mscore; /男团体总分 int wscore; /女

17、团体总分 itemnode cm+w; /项目数组headnode;/定义头结点类型headnode hn;/定义一个头结点数组void inputinformation() /输入信息，建立系统int i,j,k,s; for(i=0;in;i+) hi.score=0; hi.mscore=0; hi.wscore=0; /初始化头结点 for(i=0;in;i+) printf(*学校编号:); scanf(%d,&hi.schoolnum); /输入头结点信息 for(j=0;jm+w;j+) printf(*项目编号:); scanf(%d,&hi.cj.itemnum); prin

18、tf(*取前3名or前5名:); scanf(%d,&hi.cj.top); printf(*获得几个名次：); scanf(%d,&k); /输入项目信息 for(s=0;s5;s+) hi.cj.ranges=0, hi.cj.marks=0; /初始化排名和分数 for(s=0;sk;s+) printf(*名次:); scanf(%d,&hi.cj.ranges); /输入所获名次信息 if(hi.cj.top=3) switch(hi.cj.ranges) case 0: hi.cj.marks=0; break; case 1: hi.cj.marks=5; break; case

19、 2: hi.cj.marks=3; break; case 3: hi.cj.marks=2; break; else switch(hi.cj.ranges) case 0: hi.cj.marks=0; break; case 1: hi.cj.marks=7; break; case 2: hi.cj.marks=5; break; case 3: hi.cj.marks=3; break; case 4: hi.cj.marks=2; break; case 5: hi.cj.marks=1; break; hi.score=hi.score+hi.cj.marks;/按取前三名还是

20、取前五名分别记分 if(j=m-1)hi.mscore=hi.mscore+hi.cj.marks;/是男子项目则记到男子分数里面去 else hi.wscore=hi.wscore+hi.cj.marks;/是女子项目则记到女子项目里面去 printf(n); void output() /输出函数 int choice,i,j,k;int remembern;int sign; do printf(*1.按学校编号输出.*n); printf(*2.按学校总分输出.*n); printf(*3.按男团总分输出.*n); printf(*4.按女团总分输出.*n); printf(nn* 请

21、选择编号*nn:); scanf(%d,&choice); switch(choice) case 1:for(i=0;in;i+) printf(nn*学校编号:%dn,hi.schoolnum); printf(*学校总分:%dn ,hi.score); printf(*男团总分:%dn,hi.mscore); printf(*女团总分: %dnnn,hi.wscore); /按编号顺序输出 break; case 2: for(i=0;in;i+)rememberi=i; for(i=0;in;i+) for(j=i+1;jn;j+)if(hrememberi.scorehj.score

22、) k=rememberi;rememberi=rememberj,rememberj=k; / 用冒泡排序方法，用辅助数组记住头结点下标 for(i=0;in;i+) printf(nn*学校编号：%dn,hrememberi.schoolnum); printf(*学校总分:%dn ,hrememberi.score); printf(*男团总分:%dn,hrememberi.mscore); printf(*女团总分: %dnnn,hrememberi.wscore);/按所记下标顺序输出 /按学校总分输出 break; case 3: for(i=0;in;i+) rememberi=

23、i; for(i=0;in;i+) for(j=i+1;jn;j+)if(hrememberi.mscorehj.mscore)k=rememberi;rememberi=rememberj;rememberj=k; for(i=0;in;i+) printf(nn*学校编号:%dn,hrememberi.schoolnum); printf(*学校总分:%dn ,hrememberi.score); printf(*男团总分:%dn,hrememberi.mscore); printf(*女团总分: %dnnn,hrememberi.wscore); /按男团总分输出 break; case

24、 4: for(i=0;in;i+) rememberi=i; for(i=0;in;i+) for(j=i+1;jn;j+) if(hrememberi.wscorehj.wscore) k=rememberi;rememberi=rememberj;rememberj=k; for(i=0;in)printf(错误：这个学校没有参加此次运动会!nnn); elseprintf(要查询的项目编号:); scanf(%d,&j); if(jm+w|j=0) printf(此次运动会没有这个项目nnn);/学校编号超出范围，则输出警告 else printf(这个项目取前 %d名,该学校的成绩如

25、下:n, h0.cj-1.top); for(k=0;km+w|s=0)printf(此次运动会不包括这个项目.nnn);/项目编号超出范围则输出警告elseprintf(该项目取前 %d名,取得名次的学校n,h0.cs-1.top);for(i=0; in;i+) for(j=0;j5;j+) if(hi.cs-1.rangej!=0) printf(学校编号:%d,名次:%dn,hi.schoolnum,hi.cs-1.rangej); /输出该项目取得名次学校的成绩 printf(nnn继续 2,跳出 0n);scanf(%d,&i);printf(nnn);while(i=2); br

26、eak;void writedata() /把数据存储在文件中 FILE *report; int i; if(report=fopen(sportsdata.txt,w)=null) printf(不能打开文件n); exit(1); for(i=0;in;i+)fwrite(&hi,sizeof(headnode),1,report); fclose(report); /按头结点块写入 void readdata() /读出文件中数据的函数 FILE *report; int i,j,k,s; if(report=fopen(sportsdata.txt,r)=null) printf(f

27、ile can not be openedn); exit(1); for(i=0;in;i+) printf(*学校编号:); fread(&k,sizeof(int),1,report); printf(%dn,k); printf(*学校总分:); fread(&k,sizeof(int),1,report); printf(%dn,k); printf(*男团总分:); fread(&k,sizeof(int),1,report); printf(%dn,k); printf(*女团总分:); fread(&k,sizeof(int),1,report); printf(%dn,k);

28、 printf(nnn); getch(); for(j=0;jm+w;j+) printf(*项目编号:); fread(&k,sizeof(int),1,report); printf(%dn,k); printf(*所取名次数量:); fread(&k,sizeof(int),1,report); printf(%dn,k); for(s=0;s5;s+) fread(&k,sizeof(int),1,report); if(k!=0) printf(*名次:), printf(%dn,k); for(s=0;s5;s+) fread(&k,sizeof(int),1,report);

29、if(k!=0) printf(*分数:), printf(%dn,k); printf(nnn); getch(); fclose(report); /关闭文件 /按照读一个数据就输出一个数据的方式显示数据内容void main() int choice;printf(=欢迎使用=n); printf(nn*运动会分数统计系统*n); printf(nn*1.输入信息*n);printf(*2.输出信息*n);printf(*3.查询信息*n); printf(*4.调用信息*n); printf(*5.退出系统*nnn);printf(=nn);printf(*请选择要实现步骤的编号:nn

30、);scanf(%d,&choice);switch(choice) case 1: inputinformation();writedata();readdata();main(); case 2: output();main(); case 3: inquiry();main(); case 4: readdata();main(); case 5: exit(0); default: exit(0); 8总结(1).调试中所遇到的较重要问题的回顾：1) 提出问题：所有输入输出内容只能在一屏内显示，学过c语言，很知道”n”是换行，”f”是换屏的，可是在这里就是无法实现。解决问题: 输入cl

31、rscr();2)提出问题：设置选项，供用户输入选择时，当按任意键时都会跳入下一步操作，或者直接退出系统。分析问题：在供用户选择时，提供了几个选项，就写几个case语句，但是当用户输入的并不是这几个数字时，系统就不能做出正确判断。解决问题：修改case语句，添加default语句提示出错，要求重新输入； Default： clrscr(); /*清屏*/ printf(输入错误，请重新选择); 3)提出问题：当同一项目中有同一学校的两个人时，便不能正确输出或者输出相同人名。 分析问题：由于同时有两个相同学校编号的人存在，系统在输出时，不能确定那个是正确的，或者用后来的覆盖以前的。 解决问题：用

32、for函数实现从开始到结尾的遍历。(2).算法的效率及改进设想算法的效率：总的来讲，严重引响执行速度的便是查找，查找任意一个数据，便要将其所在的结构从头至尾遍历一次，耗费大量的时间。 改进设想：因大部分显示均是以学校为单位，所以将以由有关人的各种信息为集合的结构改为以由有关学校的各种信息为集合的结构。在这次上机过程中遇到过一些问题，但经过我们不懈努力，解决了部分，还有的现在不能解决，留着我们日后思考和解决。比如说在运用数据结构排序的时候，方法的选择上，总是想用时间复杂度小的算法，但结果出了问题，最后还是用了我们熟悉的选择法排序。结构体的运用上感觉不是很熟悉，遇到结构体的时候很陌生，这是以后必须

33、要加强的。在我们的这个程序中用了两个结构体：struct node int num; ; struct node *f22; 我们同样遇到了一些还不能很好解决的问题，在输出的时候不能得到我们想要的效果，在按学校编号排序查询输出的时候，发生了重叠在做了几次修改之后都能使之满意，这有待学习和修改。28一周的数据结构上机实习已经结束了，留给我们的路却漫长而幽远。本次集中上机实验，对我们来说可以算是一次挑战，因为在理论学习中没有好好的掌握，现在要独立完成一个较复杂的程序编写，确实有一点困难。但我们对于难度一向是以积极迎战的态度来面对，认真积极努力完成这次集中上机的任务。对我们来说这是一次很好的机会，同时我们也很好的把握了这次机会，认真的完成了此次上机学习的任务，对自己今后在程序编写方面相信会有很大的帮助，在此也对学校安排这样一次学习表示感谢，最后希望自己在数据结构以及计算机的其他学习方面能够得到很好的提高。今后我们必需认真思考，而且要践行我们的承诺，一步一个脚印的走下去，才可以达到我们预期的彼岸！仔细回顾数据结构的学习过程，发现其实他也并不是想象中的那么难。