数据结构课程设计报告

1、华南师范大学增城学院 课程设计报告册2011 2012 学年度 二 学期 院/系 专业 年级课程名称：数据结构课程设计姓 名： 学 号： 一：学生成绩管理系统1、 课题功能要求：1、形式：c语言程序设计编写学生信息管理程序，能实现对学生信息的简单管理。2、要求：建立一个5个学生的信息登记表，每个学生的信息包括：学号，姓名，和总分。该程序运行时显示的菜单，如下： （1）信息录入（input） （2）总分排序（sort） （3）查询(query） （4）退出（esc） 其中：（1）对5个学生的信息进行输入，包括：学生的学号、姓名、3门课程成绩；（2） 对5个学生的总分按降序排序并显示出来；（3）

2、查询输入一个学号后，显示出该学生的有关信息； （4）退出系统：退出整个系统二、课题需求分析1、数据需求： （1）学生姓名，字符型（char） （2）学号，字符型（char） （3）成绩，浮点型（float） （4）总分，整型（int） （5）排名，整型（int） 2、功能需求： （1）信息录入（input）：学生姓名、学号、成绩 （2）总分排序 （3）查询：输入姓名或者相应的学号可查询该学生的成绩，包括各科成绩、总分和排名。3、 概要分析1、 定义所需的数据结构：由于一个学生的学号、姓名、各科成绩等项是不一样的数据类型，如图3-1，因此我使用一种结构体定义这些数据。 num name chin

3、ese math english ave sum1001张三90989995287定义结构体如下：struct student /定义结构体 student int num; / 学号 char name8; / 名字 int chinese; / 语文成绩 int math; /数学成绩 int english; / 英语成绩 int ave; / 平均成绩 int count; /总分struct student *next; /定义一个指针变量，指针指向结构体stu5; /定义了五个struct student类型的变量2、 系统模块设计：根据学生管理系统的功能我将程序分为6个模块 （1

4、）菜单模块：该模块提供该程序的各种功能选择，其中包括建立链表、插入新的信息、查找学生成绩、删除学生信息、查看成绩单、退出程序。 （2）建立空链表模块：通过主函数调用struct student *create_list()空链表函数，用于开辟一段足够大的空间存放学生信息。如果建立的链表为空则建立成功，否则出现错误，将会再次回到菜单重新建立。 （3）录入学生信息模块：该没模块主要通过调用函数int insert_list(struct student *head,struct student *std,int n)，将学生的各项信息保存到刚刚建立的空链表中。录入学生信息时会提示各种提示，按提示便

5、可完成各项信息的录入，若输入信息完后便可“0”退出，效果如图所示： （4） 删除学生信息模块：该模块在已建立学生系统的前提下才可生效，通过调用函数int del_list(struct student *head,struct student *std)，通过寻找匹配的学生信息即可删除，若没有匹配则显示“no this people”。（5） 查找学生信息模块：该模块的功能同样也需要在已建立学生链表的前提下才可执行，通过调用函数struct student *find_list(struct student *head,struct student *std)，而且该函数的功能只能查找一个学生

6、信息。（6） 浏览学生信息模块：该模块的功能同样也需要在已建立学生链表的前提下才可执行，通过调用函数void brow_list(struct student *head)，该函数可以浏览所有的学生信息，如图所示：4、 详细设计1、 程序流程： 1）建立空链表 2）根据需要选择操作（第一次进入该程序，必需要新建学生信息，才可执行以下操作），按“0”可结束操作 3）可执行查找、删除、浏览成绩单等操作，这些操作均通过调用每个功能模块的函数实现。2、函数调用关系： 通过main函数调用个个功能模块/*函数说明*/struct student *create_list(); /此函数建立空链表 int

7、 insert_list(struct student *head,struct student *std,int n); /此函数插入新链表，用于录入学生信息int del_list(struct student *head,struct student *std); /此函数为删除链表结点，用于删除一个学生信息struct student *find_list(struct student *head,struct student *std); /此函数为查找指定的结点void brow_list(struct student *head); /此函数用于浏览链表3、 各模块功能函数的设计

8、与实现 1）菜单（主函数） 方法：用switch语句控制，调用各模块函数 程序清单：void main() /主函数struct student *head; /定义头指针struct student newted; int choice;head=null; /初始化头指针printf( 学生管理系统n);/菜单printf(1.建立链表n);printf(2.插入新的信息n);printf(3.查找学生成绩n);printf(4.删除学生信息n);printf(5.查看成绩单n);printf(0.退出程序n);doprintf(请选择操作（输入05）：);scanf(%d,&choice

9、);if(choice5|choicenext=null; head-num=0; return head;3） 建立新链表 方法：指针 程序清单： int insert_list(struct student *head,struct student *std,int n) /插入链表，用于录用学生信息 struct student *p,*q; struct student *s; s=(struct student *)malloc(sizeof(struct student);/申请结点 if(s=null) printf(error!n); return 0; q=head; p=h

10、ead-next; while(p!=null & n!=q-num) q=p; p=p-next; q-next=s; s-next=p; strcpy(s-name,std-name); s-num=std-num; s-chinese=std-chinese; s-math=std-math; s-english=std-english; s-count=std-count; s-ave=std-ave; return 1; /返回1，即真值4） 查找学生信息模块 程序清单：struct student *find_list(struct student *head,struct stu

11、dent *std) struct student *p; p=head; while(p!=null & strcmp(p-name,std-name) p=p-next; if(p!=null) printf(学号： %d 姓名： %s 语文：%d 数学： %d 英语： %d 总分： %d 平均分： %dn,p-num,p-name,p-chinese,p-math,p-english,p-count,p-ave); else printf(no this people!n); return p;5） 删除学生信息模块 程序清单：int del_list(struct student *h

12、ead,struct student *std)struct student *p,*q;/定义指针变量，指向结构体q=head;/将头指针指向qp=head-next;/头指针的下一结点指向pwhile(p!=null & strcmp(p-name,stu-name)/判断信息是否匹配q=p;p=p-next;/不匹配则指向下一个结点，继续比较if (p!=null)q-next=p-next;/信息匹配，则删除free(p);/释放结点printf(删除完成n);return 1; else printf(no this peoplen); return 0;6） 浏览学生信息链表 程序

13、设计:void brow_list(struct student *head) struct student *p; p=head-next; while(p!=null) printf(学号： %d 姓名： %s 语文：%d 数学： %d 英语： %d 总分： %d 平均分： %dn,p-num,p-name,p-chinese,p-math,p-english,p-count,p-ave); p=p-next; 5、 程序调试由于是按模块进行编写程序的，这样便有一个优点，可以按模块进行调试和分析程序。1）菜单模块：在编写程序时，菜单模块是相对比较简单的，通过switch语句实现，调用子程序

14、即可，主要是对输出的设置比较繁琐，需要一点一点的调试以达到较为美观的效果。如图 2）新建空链表模块：运行该模块时出现错误error c2440: type cast : cannot convert from void * to struct studentno constructor could take the source type, or constructor overload resolution was ambiguous，经查阅发现在申请结点时，由于定义结构体时定义指针类型，因此申请结点时应该 head=(struct student *)malloc(sizeof(struc

15、t student)，其中的“*”不可省略。该模块运行的结果如下：3）建立学生成绩单，录入学生信息模块：该函数在设计初期，是无参数的，但发现无法返回值，通过查阅相关的书籍，发现其参数是设为结构体的指针，将std所指向的值赋给函数定义的指针变量，然后通过return返回。调试结果如图：4） 浏览学生成绩单模块：6） 查找学生信息： 二运动会分数统计（1） 需求分析不少学校都要定期联合举行运动会，这个程序能让管理者更方便的把各个学校的总分统计出来并排上名次，同时也比纸张等媒介更方便的存储和取出数据。（2） 概要设计这个程序实现的功能如下：1. 输入项目1到5的前5名学校的编号，并按7，5,3,2,

16、1的分数加在相应的学校上。2. 按学校的编号顺序输出学校的总分，名次3. 按照排名的顺序输入学校的总分，编号其中包括 chushihua():用for对结构体数组进行初始化。input1()-input5():用2个for循环来输入项目1-5的前5名学校编号。jifen（）：用for循环加出学校总分。paiming（）：利用比较大小方式记录排名。bianhao（）：按学校编号输出信息。mingci（）：按名次输出信息。chazhao（）：用学校编号来查找学校信息。（3）详细设计struct xuexiao /*定义结构体数组*/int num;int score1;int score2;int

17、 score3;int score4;int score5;int score;int mingci;xuexiao10;int i,s,j,k;chushihua() /*初始化数组*/for(i=0;i10;i+)xuexiaoi.num=i+1;xuexiaoi.score1=0;xuexiaoi.score2=0;xuexiaoi.score3=0;xuexiaoi.score4=0;xuexiaoi.score5=0;xuexiaoi.score=0;input1() /*输入项目1前5学校编号*/printf(input score1;an zhao shun xu shu ru

18、qian 5 ge xue xiao bian hao;n);for(i=0;i5;i+)scanf(%d,&s);for(j=0;j10;j+)if(xuexiaoj.num=s) if(i=0) (xuexiaoj.score1=7);if(i=1) (xuexiaoj.score1=5);if(i=2) (xuexiaoj.score1=3);if(i=3) (xuexiaoj.score1=2);if(i=4) (xuexiaoj.score1=1);input2() /*输入项目2前5学校编号*/printf(input score2;an zhao shun xu shu ru q

19、ian 5 ge xue xiao bian hao;n);for(i=0;i5;i+)scanf(%d,&s);for(j=0;j10;j+)if(xuexiaoj.num=s) if(i=0) (xuexiaoj.score2=7);if(i=1) (xuexiaoj.score2=5);if(i=2) (xuexiaoj.score2=3);if(i=3) (xuexiaoj.score2=2);if(i=4) (xuexiaoj.score2=1);input3() /*输入项目3前5学校编号*/printf(input score3;an zhao shun xu shu ru qi

20、an 5 ge xue xiao bian hao;n);for(i=0;i5;i+)scanf(%d,&s);for(j=0;j10;j+)if(xuexiaoj.num=s) if(i=0) (xuexiaoj.score3=7);if(i=1) (xuexiaoj.score3=5);if(i=2) (xuexiaoj.score3=3);if(i=3) (xuexiaoj.score3=2);if(i=4) (xuexiaoj.score3=1);input4() /*输入项目4前5学校编号*/printf(input score4;an zhao shun xu shu ru qia

21、n 5 ge xue xiao bian hao;n);for(i=0;i5;i+)scanf(%d,&s);for(j=0;j10;j+)if(xuexiaoj.num=s) if(i=0) (xuexiaoj.score4=7);if(i=1) (xuexiaoj.score4=5);if(i=2) (xuexiaoj.score4=3);if(i=3) (xuexiaoj.score4=2);if(i=4) (xuexiaoj.score4=1);input5() /*输入项目5前5学校编号*/printf(input score5;an zhao shun xu shu ru qian

22、 5 ge xue xiao bian hao;n);for(i=0;i5;i+)scanf(%d,&s);for(j=0;j10;j+)if(xuexiaoj.num=s) if(i=0) (xuexiaoj.score5=7);if(i=1) (xuexiaoj.score5=5);if(i=2) (xuexiaoj.score5=3);if(i=3) (xuexiaoj.score5=2);if(i=4) (xuexiaoj.score5=1);jifen()for(j=0;j10;j+) /*计算各学校总分*/xuexiaoj.score=xuexiaoj.score1+xuexiao

23、j.score2+xuexiaoj.score3+xuexiaoj.score4+xuexiaoj.score5;paiming() /*按照各学校总分大小排名次*/for(i=0;i10;i+)k=1;for(j=0;j10;j+)if(xuexiaoi.scorexuexiaoj.score) k+;xuexiaoi.mingci=k;bianhao() /*按照各学校编号输出信息*/for(j=0;j10;j+)for(i=0;i10;i+)if(xuexiaoi.num=j+1)printf(n %d xue xiao zong fen wei %d,ming ci wei %d,xu

24、exiaoi.num,xuexiaoi.score,xuexiaoi.mingci);mingci() /*按照名次输出信息*/for(j=0;j10;j+)for(i=0;i10;i+)if(xuexiaoi.mingci=j+1)printf(nno.%d xue xiao zong fen wei %d,bian hao wei %d,xuexiaoi.mingci,xuexiaoi.score,xuexiaoi.num);chazhao() /*查找学校编号输出信息*/printf(nshu ru xuexiao bian haon);scanf(%d,&s);for(i=0;i10;

25、i+)if(xuexiaoi.num=s) printf( %d xue xiao score1=%d,score2=%d,score3=%d,scorc4=%d,scorc5=%d,xuexiaoi.num,xuexiaoi.score1,xuexiaoi.score2,xuexiaoi.score3,xuexiaoi.score4,xuexiaoi.score5);main()chushihua();input1();input2();input3();input4();input5();jifen();paiming();printf(1:an xue xiao bian hao shu

26、chu chengjin2:an mingzi shuchu chengjin3:cha zhao );scanf(%d,&k);if(k=1) bianhao();if(k=2) mingci();if(k=3) chazhao();getch();（4）调试报告输入第一个项目前5名学校输入第二个项目前5名学校输入第三个项目前5名学校输入第四个项目前5名学校输入第五个项目前5名学校输入完毕，选择1：按编号输出。2：按名次输出。3：查找选择1选择2选择3后查找1号学校。课题三：哈夫曼树一、需求分析1、输入叶子个数及初始化。如叶子结点个数为4，数组长度就为20。2、输入各个叶子的值、权值，并对数

27、组初步赋值。如各个叶子值分别为a、b、c、d、e，各个权值分别为1，3，5，7。3、计算二叉树其余结点信息。由于4个叶子结点，要合并3次。每次从还无双亲（无双亲代表还未合并过）的叶子结点中选择权值最小的两个叶子结点进行合并，新结点下标为这两个叶子的双亲，新结点的权值为这两个叶子权值之和，左孩子为最小结点下标，右孩子为次小结点下标，叶子值不需要，双亲为0。4、输出二叉树（即输出数组）将二叉树按上表以表格形式在屏幕上输出即可。5、输出编码按从叶子到根结点反向生成编码，如该结点为其双亲的左孩子，编码0，否则编码1。最后正向输出所有叶子编码。二、概要设计1、构造哈夫曼树的方法：（1)由给定的n个权值w

28、1, w2, , wn，构造n棵扩充二叉树的集合f = t1, t2, , tn，其中每棵扩充二叉树中均只含一个带权值wi的根结点,其左、右子树均为空;（2) 重复下列步骤，直到f中只含一棵树为止：在f中选取其根结点的权值为最小的两棵扩充二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;从f中删去这两棵树，同时加入刚生成的新树;（3）按上述步骤得到的二叉树就是哈夫曼树。例如：给定一组权值1、3、5、7，他们的叶子名字分别为a、b、c、d，构造出相应的哈夫曼树。如图所示： （a） （b） （c） 13 （d） 以下对哈夫曼树用表格进行说明

29、：由于叶子结点个数n已知，根据二叉树性质得知，整棵二叉树结点总数为（2n-1）个，故可建立长度为（2n-1）的数组。数组每个元素为二叉树的一个结点，由5个域组成，所以应采用结构体类型，包括结点值，权值，左孩子，右孩子，双亲。struct tree1 char value; int weight; int rch; int lch; int parent;tree20;三、详细设计#includestruct node /*单链表结点类型*/ int weight; int parent,lch,rch; /*指向双亲，左孩子，右孩子*/ char value; int bianma; main

30、() struct node tree20; /*定义树的容量为20*/ int i,j,n,min1,min11,min2,min22; int s,p; printf(n input the count of leaves10:); /*先将全部的变量赋值为-1*/ scanf(%d,&n) ; for(i=0;i2*n-1;i+) treei.value=0; treei.parent=-1; treei.lch=-1; treei.rch=-1; printf(ninput the leaves weight: n) ; for(i=0;in;i+) scanf(%d,&treei.w

31、eight); printf(input the leavesname:n); getchar(); for(i=0;in;i+) scanf(%c,&treei.value); printf(%c,treei.value); for (i=n;i2*n-1;i+) min2=min1=100; /*控制权值少于100*/ min11=min22=0; /*先将左右孩子赋值为0*/ for(j=0;ji;j+) if(treej.parent=-1)/*如果父母为-1，则进行以下的操作，找出最小和次小的两个权值*/ if(treej.weightmin1)/*最小的权值*/ min22=min11; min2=min1; min11=j; min1=treej.weight; else if(treej.weightmin2)/*次小权值*/ min22=j; min2=treej.weight; printf(min11=%d,min22=%dn,min11,min22); treemin11.parent=i