数据结构课程设计报告

1*****数据结构课程设计题目:赫夫曼树的建立运动会分数统计订票系统猴子选大王图的建立与输出姓名：***学号****专业：计算机科学与技术指导教师：****2006年9月20日2目录一：绪言………………………………………………............31.1课题设计背景…………………………………..........31.2课题研究的目的和意义…………………………….3.1.3课题研究的内容……………………………………..4二：主菜单设计………………………………………………..42.1主菜单……………………………………………….42.2主菜单源代码………………………………………..42.3主菜单流程图………………………………………5三：具体程序设计……………………………………………63.1赫夫曼树的建立……………………………………………63.2运动会设计………………………………………………..83.3订票系统………………………………………………….123.4猴子选大王……………………………………………….153.5图的建立及输出…………………………………………16四：总结与展望………………………………………………………19五：参考文献…………………………………………………………19.31.绪言1．1课题背景《数据结构》作为一门独立的课程最早是美国的一些大学开设的，1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们就越来越重视数据结构，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。从70年代中期到80年代初，各种版本的数据结构著作就相继出现。目前在我国，《数据结构》也已经不仅仅是计算机专业的教学计划中的核心课程之一，而且是其它非计算机专业的主要选修课程之一。《数据结构》在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据系统及其它系统程序和大型应用程序的重要基础。值得注意的是，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来论数据结构，已成为一种新的趋势，越来越被人们所重视。1．2课题研究的目的和意义通过对此次数据结构大型作业内容的实际操作及分析，加深对数据结构丰富功能的理解及增强实际动手能力，在实践中不断提高对汇编语言的运用能力。锻炼学生分析与编写大型软件代码的能力。通过与同组同学的合作，锻炼协作的能力。1．3主要研究内容4这次课程设计我们一共选拉赫夫曼树的建立、运动会分数统计、订票系统、猴子选大王、图的建立与输出五个课程为主要研究对象，在分步运行的情况下最后用一个主菜单进行调用，所有的程序都是在WIN-TC的环境下运行的。2.主菜单设计运行程序后首先进入主菜单界面，进行选择。共五个功能模块，输入相应选项，进入各个模块界面。2．1主菜单1．赫夫曼树的建立2．运动会分数统计3．订票系统4．猴子选大王5．图的建立与输出2.2主控菜单源代码voidmain(){inti;printf(\n\t\t********学院*****班\n\n);printf(\t\t\t制作人:****************\n\n\n);printf(\t1--------哈夫曼树的建立\t2---------运动会分数统计\n\n\n);printf(\t3--------订票系统\t4---------猴子选大王\n);printf(\n\n\t5--------图的建立与输出);B:printf(\n\n\n\t\t\t\t请选择要:);scanf(%d,&i);if(i=1&&i=5)switch(i){case1:Huffman();case2:sports();case3:booktic();case4:monkey();case5:Graphics();default:printf(输入错误!);gotoB;}elseexit(0);getch();}52．3主控调用菜单流程图赫夫曼树的建立运动会分数统计订票系统猴子选大王图的建立与输出开始输入数字I是否为1－5执行相应操作结束YN63．具体程序设计3．1赫夫曼树的建立1．任务：建立建立最优二叉树函数2．要求：可以建立函数输入二叉树，并输出其赫夫曼树3．概要设计程序流程图如下：审请新的结点作为霍夫曼树的中间结点将新结点插入原链表的相应位置用排完序的字符串建立霍夫曼树将被操作结点插入相应位置取链表头结点后的两个结点作为新结点的左右儿子创建单链表创建新链表的头结点（头结点为空,后续结点也为空）取被操作链表的首元结点创建当前操作链表首元结点将整理完的字符串按出现次数从小到大的顺序排列74．调试分析运行时显示：输入abcde时：输入110时：释放霍夫曼树所占空间对霍夫曼树进行编码和解码一，编码：请输入要测试的字符串Abcde字符以及它的相应权数---------霍夫曼编码W[e]-1W[d-1W[a-1W[c-1W[b-1二，调码请输入用于解码的0，1序列：110赫夫曼编码-----相应字符110Pressanykeytocontinue……8这时按任意键则返回编辑窗口3．2运动会分数统计1．任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）。2．功能要求：1).可以输入各个项目的前三名或前五名的成绩；2)．能统计各学校总分，3)．可以按学校编号、学校总分、男女团体总分排序输出；4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。3.规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）4.抽象数据类型结构体数组的定义如下：#defineM6/*6个男子项目*/#defineW4/*4个女子项目*/#defineN10typedefstruct{intman[5+1];/*排名，此数组中存放学校代码*/intwomen[3+1];charIname[M+W+1];/*项目名称*/}Item;/*项目代码，M的为男子，M的为女子*/typedefstruct{intscoreT;/*学校总分*/intscoreM;/*男子总分*/intscoreW;/*女子总分*/intman[M+1];/*男子项目*/intwomen[W+1];/*女子项目*/intflag;/*排序用旗帜*/}School;ItemiteM[M+W+1];/*M+W个项目*/9Schoolsch[N+1];/*n个学校，0不用*/charname[N+1][100];voidInput()//输入函数voidInitial()//初始化函数voidSchool_F()//按学校代码查询函数voidItem_F()//运动项目查询函数voidFind()//查询菜单函数voidOrder_ST()//总分排序函数voidOrder_SM()//男子总分排序函数voidOrder_SW()//女子总分排序函数voidFind_O()//排序菜单函数voidOutput()//输出到文件函数void5．本程序包括5个模块a.主程序模块：Voidmain(){Do{接受命令；处理命令;}while(“命令”=退出)；}b.信息输入模块——实现信息的输入；c.信息查询模块——实现信息的查询；d.信息排序查询模块——实现各种的有序输出；e.信息存盘模块——实现输出到文件。各模块的关系如下：主程序模块——信息输入模块——信息查询——信息排序查询模块—信息存盘模块.6.流程图主函数欢迎界面选择功能scanf(%d,&a)If(i=1)If(i=2)If(i=3)10成绩输入查询排序查询成绩输入选择功能For(i=1;i=N;i++)项目个数输入项目代码及名称输入男子项目前五名输入女子项目前三名查询Scanf(“%d”,&a);T=1t=2T=3按学校代码按项目编号返回上一级菜单排序查询选择功能Scanf(“%d”,&a);选canf(“%d”,&a);11a=1a=2按学校总分查询按男团总分查询7．调试分析a.本程序在项目上采用了数字代码操作，并且能同步输入输出项目名和学校名。实现方法为在学校结构体内增加字符数组用来存储学校的名称。缺点就是没有考虑有一个学生参加两项比赛的情况，这就要再次增加循环参加比赛的数目。b.算法的时空分析（1）本程序时间复杂度为N*N主要集中在按积分排序的过程，在排序时采用了冒泡排序，而且在交换数据时也较大地耗费内存，至今未能解决。。（2）另外一点在于项目查询时，会增加时间复杂度，为了减少时间复杂度，我把按项目查找分为按女子和按男子查找，这样在查询项目时可先判断是男子项目还是女子项目，再查找，这样就减少时间复杂度。（3）在空间复杂度方面，本程序几乎没有用到辅助空间，只是未用到所有的数组，会浪费一些存储空间。8.测试结果这是在学校个数为1，项目数为2（包括一个男子项目一个女子项目）时的输出文件情况：1a学校总分：7，男子总分：7，女子总分：02b学校总分：7，男子总分：5，女子总分：23c学校总分：6，男子总分：3，女子总分：84d学校总分：2，男子总分：2，女子总分：85e学校总分：6，男子总分：1，女子总分：56学校总分：0，男子总分：0，女子总分：87学校总分：0，男子总分：0，女子总分：08学校总分：0，男子总分：0，女子总分：09学校总分：0，男子总分：0，女子总分：010学校总分：0，男子总分：0，女子总分：012男子项目1排名:第1名:1第2名:2第3名:3第4名:4第5名:5男子项目2排名:第1名:0第2名:0第3名:0第4名:0第5名:0男子项目3排名:第1名:0第2名:0第3名:0第4名:0第5名:0男子项目4排名:第1名:0第2名:0第3名:0第4名:0第5名:0男子项目5排名:第1名:0第2名:0第3名:0第4名:0第5名:0男子项目6排名:第1名:0第2名:0第3名:0第4名:0第5名:0女子项目7排名:第1名:0第2名:0第3名:0女子项目8排名:第1名:5第2名:3第3名:2女子项目9排名:第1名:0第2名:0第3名:0女子项目10排名:第1名:0第2名:0第3名:03．3订票系统1．任务：通过此系统可以实现如下功能：a.录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）b.查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；c.订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；d.退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件2.要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序