数据结构课程设计报告

作者：panhongliang

仅供个人学习。

数据结构课程设计。

题目：赫夫曼树的建立。

运动会分数统计。

订票系统。猴子选大王。

姓名：**学号： *

专业： *指导教师： *

一：绪言31.1课题设计背景3

1.2课题研究的目的和意义3.

1.3课题研究的内容4

二：具体程序设计62.1赫夫曼树的建立6

2.2运动会设计8

2.3订票系统12

2.4猴子选大王15

三：总结与展望15

四：参考文献15

附：程序源**。

1. 绪言。

1．1 课题背景。

数据结构》作为一门独立的课程最早是美国的一些大学开设的，2024年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们就越来越重视数据结构，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。从70年代中期到80年代初，各种版本的数据结构著作就相继出现。

目前在我国，《数据结构》也已经不仅仅是计算机专业的教案计划中的核心课程之一，而且是其它非计算机专业的主要选修课程之一。

数据结构》在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。

因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据系统及其它系统程序和大型应用程序的重要基础。值得注意的是，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来论数据结构，已成为一种新的趋势，越来越被人们所重视。

1．2课题研究的目的和意义

通过对此次数据结构大型作业内容的实际操作及分析，加深对数据结构丰富功能的理解及增强实际动手能力，在实践中不断提高对汇编语言的运用能力。锻炼学生分析与编写大型软件**的能力。通过与同组同学的合作，锻炼协作的能力。

二：具体程序设计。

2．1 赫夫曼树的建立。

1．任务：建立建立最优二叉树函数

2．要求：可以建立函数输入二叉树，并输出其赫夫曼树。

3．概要设计。

程序流程图如下：

4．调试分析。

运行时显示：

输入 a b c d e时：

输入110时：

这时按任意键则返回编辑窗口。

2．2运动会分数统计。

1．任务：参加运动会有n个学校，学校编号为1……n.比赛分成m个男子工程，和w个女子工程。

工程编号为男子1……m，女子m+1……m+w.不同的工程取前五名或前三名积分；取前五名的积分分别为，前三名的积分分别为；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20）.

2．功能要求：1).可以输入各个工程的前三名或前五名的成绩； 2)．能统计各学校总分， 3)．可以按学校编号、学校总分、男女团体总分排序输出；4).

可以按学校编号查询学校某个工程的情况；可以按工程编号查询取得前三或前五名的学校。

3. 规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动工程的名称）

4.抽象数据类型结构体数组的定义如下：

#define m 66 个男子工程 */

#define w 44 个女子工程 */

#define n 10

typedef struct{

int man[5+1排名，此数组中存放学校** */

int women[3+1]。

char iname[m+w+1工程名称 */

item工程**，m的为女子 */

typedef struct{

int scoret学校总分 */

int scorem男子总分 */

int scorew女子总分 */

int man[m+1男子工程 */

int women[w+1女子工程 */

int flag排序用旗帜*/

school。

item item[m+w+1m+w个工程 */

school sch[n+1n个学校，0不用 */

char name[n+1][100]。

void input输入函数。

void initial初始化函数。

void school_f按学校**查询函数。

void item_f运动工程查询函数。

void find查询菜单函数。

void order_st总分排序函数。

void order_sm男子总分排序函数。

void order_sw女子总分排序函数。

void find_o排序菜单函数。

void output输出到文件函数。

void 5．本程序包括5个模块。

a.主程序模块：

void main()

do接受命令；

处理命令。while(“命令”=退出)；

b.信息输入模块——实现信息的输入；

c.信息查询模块——实现信息的查询；

d.信息排序查询模块——实现各种的有序输出；

e.信息存盘模块——实现输出到文件。

各模块的关系如下：

主程序模块——信息输入模块——信息查询——信息排序查询模块—信息存盘模块。

6.流程图。

7．调试分析。

a. 本程序在工程上采用了数字**操作，并且能同步输入输出工程名和学校名。实现方法为在学校结构体内增加字符数组用来存储学校的名称。

缺点就是没有考虑有一个学生参加两项比赛的情况，这就要再次增加循环参加比赛的数目。

b.算法的时空分析。

1）本程序时间复杂度为n*n主要集中在按积分排序的过程，在排序时采用了冒泡排序，而且在交换数据时也较大地耗费内存，至今未能解决。

2）另外一点在于工程查询时，会增加时间复杂度，为了减少时间复杂度，我把按工程查找分为按女子和按男子查找，这样在查询工程时可先判断是男子工程还是女子工程，再查找，这样就减少时间复杂度。

3）在空间复杂度方面，本程序几乎没有用到辅助空间，只是未用到所有的数组，会浪费一些存储空间。

8.测试结果。

这是在学校个数为1，工程数为2（包括一个男子工程一个女子工程）时的输出文件情况：

1 a 学校。

总分： 7 ，男子总分： 7，女子总分： 0

2 b 学校。

总分： 7 ，男子总分： 5，女子总分： 2

3 c 学校。

总分： 6 ，男子总分： 3，女子总分： 8

4 d 学校。

总分： 2 ，男子总分： 2，女子总分： 8

5 e 学校。

总分： 6 ，男子总分： 1，女子总分： 5

6 学校。总分： 0 ，男子总分： 0，女子总分： 8

7 学校。总分： 0 ，男子总分： 0，女子总分： 0

8 学校。总分： 0 ，男子总分： 0，女子总分： 0

9 学校。总分： 0 ，男子总分： 0，女子总分： 0

10 学校。

总分： 0 ，男子总分： 0，女子总分： 0

男子工程1排名：

第1名： 1 第2名： 2 第3名： 3 第4名： 4 第5名： 5

男子工程2排名：