数据结构课程设计 赫夫曼树的建立 运动会分数统计 订票系统.doc

*数据结构课程设计 题目: 赫夫曼树的建立 运动会分数统计 订票系统 猴子选大王 图的建立与输出姓名：*学号 *专业： 计算机科学与技术指导教师： * 2010年9月20日目录一：绪言.3 1.1课题设计背景.3 1.2课题研究的目的和意义.3. 1.3课题研究的内容.4二：主菜单设计.4 2.1主菜单.4 2.2主菜单源代码.4 2.3主菜单流程图 5三：具体程序设计6 3.1赫夫曼树的建立63.2运动会设计.83.3订票系统.123.4猴子选大王.153.5图的建立及输出16四：总结与展望19五：参考文献19.1. 绪言11 课题背景数据结构作为一门独立的课程最早是美国的一些大学开设的，1968年美国唐欧克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们就越来越重视数据结构，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。从70年代中期到80年代初，各种版本的数据结构著作就相继出现。目前在我国，数据结构也已经不仅仅是计算机专业的教学计划中的核心课程之一，而且是其它非计算机专业的主要选修课程之一。数据结构在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据系统及其它系统程序和大型应用程序的重要基础。值得注意的是，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来论数据结构，已成为一种新的趋势，越来越被人们所重视。12 课题研究的目的和意义 通过对此次数据结构大型作业内容的实际操作及分析，加深对数据结构丰富功能的理解及增强实际动手能力，在实践中不断提高对汇编语言的运用能力。锻炼学生分析与编写大型软件代码的能力。通过与同组同学的合作，锻炼协作的能力。13主要研究内容 这次课程设计我们一共选拉赫夫曼树的建立、运动会分数统计、订票系统、猴子选大王、图的建立与输出五个课程为主要研究对象，在分步运行的情况下最后用一个主菜单进行调用，所有的程序都是在WIN-TC的环境下运行的。2.主菜单设计运行程序后首先进入主菜单界面，进行选择。共五个功能模块，输入相应选项，进入各个模块界面。21 主菜单1赫夫曼树的建立2运动会分数统计3订票系统4猴子选大王5图的建立与输出 2. 2 主控菜单源代码void main() int i; printf(ntt* *学院 *班nn); printf(ttt制作人:* * * *nnn); printf(t1-哈夫曼树的建立t2-运动会分数统计nnn); printf(t3-订票系统t 4-猴子选大王n); printf(nnt5-图的建立与输出); B: printf(nnntttt请选择要:); scanf(%d,&i); if(i=1&i=5) switch(i) case 1: Huffman(); case 2: sports(); case 3: booktic(); case 4: monkey(); case 5: Graphics(); default: printf(输入错误!);goto B; else exit(0); getch(); 23 主控调用菜单流程图 开 始输入数字NI是否为15 Y执行相应操作 赫夫曼树的建立运动会分数统计订 票 系 统猴子 选 大 王图的建立与输出结 束3具体程序设计31 赫夫曼树的建立1任务 ：建立建立最优二叉树函数 2要求：可以建立函数输入二叉树，并输出其赫夫曼树3概要设计 程序流程图如下：创建单链表将整理完的字符串按出现次数从小到大的顺序排列创建新链表的头结点（头结点为空,后续结点也为空）取被操作链表的首元结点创建当前操作链表首元结点将被操作结点插入相应位置用排完序的字符串建立霍夫曼树审请新的结点作为霍夫曼树的中间结点取链表头结点后的两个结点作为新结点的左右儿子将新结点插入原链表的相应位置对霍夫曼树进行编码和解码释放霍夫曼树所占空间4调试分析运行时显示：一， 编码：请输入要测试的字符串输入 a b c d e时：Abcde字符以及它的相应权数-霍夫曼编码We-1Wd-1Wa-1Wc-1Wb-1二，调码请输入用于解码的0，1序列： 输入110时：110赫夫曼编码-相应字符110Press any key to continue这时按任意键则返回编辑窗口32运动会分数统计 1任务：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）。2功能要求：1).可以输入各个项目的前三名或前五名的成绩；2)能统计各学校总分，3)可以按学校编号、学校总分、男女团体总分排序输出；4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 3. 规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）4.抽象数据类型结构体数组的定义如下：#define M 6 /* 6 个男子项目 */#define W 4 /* 4 个女子项目 */#define N 10typedef struct int man5+1; /* 排名，此数组中存放学校代码 */ int women3+1; char InameM+W+1; /* 项目名称 */Item; /* 项目代码，M的为女子 */typedef struct int scoreT; /* 学校总分 */ int scoreM; /* 男子总分 */ int scoreW; /* 女子总分 */ int manM+1; /* 男子项目 */ int womenW+1; /* 女子项目 */ int flag; /* 排序用旗帜*/School;Item iteMM+W+1; /* M+W个项目 */School schN+1; /* n个学校，0不用 */char nameN+1100;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.流程图主函数欢迎界面选择功能scanf(%d,&a)If(i=1)If(i=2)If(i=3)成绩输入查询排序查询成绩输入选择功能For(i=1;i:); 输入航班号；for(p1=head1-next;p1-next!=NULL;p1=p1-next)if(p1!=NULL)输出所查询航班的信息航班信息修改模块 while() p1=p1-next; print(请选择功能:);输入功能号Cas1Cas2 Cas3Case4Case5Case6 Case7Case8起飞时间抵达时间起飞地目的地 票 价折扣总座 位数跳出 5.调试分析原始信息 ： 航班：ca1 12:50 13:10 长沙 广州 134 0.3 10 ca2 15:45 01:50 南京 香港 214 0.4 3ca3 19:21 04:31 长沙 广州 431 0.8 5 ca4 01:30 07:04 重庆 长春 310 0.7 6ca5 02:08 10:56 上海 汉城 126 0.4 10 ca6 20:18 22:47 东京 纽约 987 0.9 76ca10 14:01 23:59 重庆 长春 875 0.8 12 ca11 05:09 22:12 南京 香港 422 0.3 43ca12 12:04 16:54 东京 纽约 986 0.6 32 客户：ray xy3 2 ca1 rayxy3 sam gh4 3 ca3 samgh4 Andy bo5 1 ca4 Andybo5姚明 Rockets 10 ca10 姚明Rockets Kobe Lakers 6 ca5 KobeLakers曼联 英格兰 10 ca12 曼联英格兰运行后： 航班：ca1 1250 13:10 长沙 广州 134 0.3 6 ca2 15:45 01:50 南京 香港 214 0.4 3 ca3 19:21 04:31 长沙 广州 431 0.8 5 ca134e 01:30 07:04 重庆 长春 310 0.7 6 ca5 02:08 10:56 上海 汉城 126 0.4 10 ca6 20:18 22:47 东京 纽约 345 0.9 76 ca10 14:01 23:59 重庆 长春 875 0.8 0 ca11 05:09 22:12 南京 香港 422 0.3 43 ca12 12:04 16:54 东京 纽约 986 0.6 32 客户： ray xy3 2 ca1 rayxy3 sam gh4 3 ca3 samgh4 Andy bo5 1 ca4 Andybo5 姚明 Rockets 10 ca10 姚明Rockets Kobe Lakers 6 ca5 KobeLakers 曼联 英格兰 10 ca12 曼联英格兰34 猴子选大王 1任务：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 2要求：输入数据：输入m,n 为整数，nm输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能 3概要设计：基本思路是以链表顺序储存猴子的信息，利用计数器完成操作，最后打印出是第几个猴子存储结构: 循环链表定义:表中最后一个结点的指针指向第一个结点4调试分析运行时显示：输入10时：这时再输入5：5the king of the monkey is : 3Press any key to continue . . .这时按任意键则返回编辑窗口3.5 图的建立与输出 1任务：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 2概要设计基本思路为输入顶点数边数和顶点信息，建立连接矩阵，然后以四种算法深度优先递归遍历算法 深度优先非递归遍历算法 广度递归搜索遍历算法 广度非递归搜索遍历算法完成操作 3调试分析运行时显示：图的建立及输出 03041计算机 设计者：李宝玉1-建立连接矩阵2-深度优先递归遍历算法3-深度优先非递归遍历算法4-广度递归搜索遍历算法5-广度非递归搜索遍历算法0-退出 请你选择所需的操作： 设计时间：-2006.9.20 4选择1-建立连接矩阵并输入相关信息时显示：请输入顶点数和边数:4 6请输入顶点信息:0 1 2 3请输入i和j:0 1请输入i和j:0 2请输入i和j:0 3请输入i和j:1 2请输入i和j:1 3请输入i和j:2 30111101111011110Select: :0-退出 2-继续：这时选择2-继续返回主界面再选择2-深度优先递归遍历算法时显示：0 1 2 3Select: :0-退出 2-继续这时选择2-继续返回主界面再选择3-深度优先非递归遍历算法时显示：0 3 2 1Select: :0-退出 2-继续这时选择2-继续返回主界面再选择4-广度递归搜索遍历算法时显示：0 1 2 3Select: :0-退出 2-继续这时选择2-继续返回主界面0 1 2 3Select: :0-退出 2-继续再选择5-广度非递归搜索遍历算法时显示:这时选择2-继续返回主界面这时选择0-退出再按任意键则返回编辑窗口3.总结与展望通过为期半个月的课程设计，我们对数据结构这门课程有了更深一步的了解。它是计算机程序设计的重要理论技术基础，在我们计算机专业的学习中占据着十分重要的地位。同时也使我们知道，要学好这门课程，仅学习书本上的知识是不够的，还要有较强的实践能力。因为我们学习知识就是为了实践。而只有多实践，多编写程序，才能更好的理解与掌握书本上的东西。这次课程设计也让我们明白拉“团结就是力量”的魅力。大家一起合作，一起讨论、一起研究，充分发挥团队精神，各尽其责，按时，按进度完成各自的任务，是我们能够把这个程序按时做出来的关键！在我们组员的通力合作下，我们按照制定的计划，终于顺利地完成了这个程序。这使得我们相信：无论是在以后的学习还是生活中，只要我们充分发挥团队合作的精神，一定可以克服种种困难，争取更大的成功！本次设计我们也首次使用拉WIN-TC进行编译，摆脱拉TC环境下编译的弊端，WIN-TC的编译使我们的本次课程设计更加美观。但是也有不如意的地方，做的不好的地方，望老师谅解，我们会在以后的学习、设计中努力改进，做得更加完美。4.参考文选3姚诗斌，数据库系统基础，计算机工程与应用，2006年第8期4严蔚敏，吴伟民编著，数据结构（C语言版），北京；清华大学出版社，20055 严蔚敏，陈文博编著，数据结构及应用算法教程，北京；清华大学出版社，20066 李云清，杨庆红，揭安全编著，数据结构（C语言版），北京；人民邮电出版社，20067 谭浩强编著， C语言程序设计（第二版），北京；清华大学出版社，20038 苏仕华等编著，数据结构课程设计，上海；机械工业出版社，20049 各大网站# include#include#define MAXLEN 100typedef struct Huffmantree char ch; /*键值*/int weight,mark; /*weight为权值,mark为标志域*/struct Huffmantree *parent,*lchild,*rchild,*next;Hftree,*linktree;/*整理输入的字符串，合并相同的项，并求出每个字符在数组中出现的次数 */linktree tidycharacter(char character)int i=0;linktree tree,ptr,beforeptr,node; /*链式 ,tree为头结点,beforeptr为ptr的前一结点,node为新申请的结点*/tree=(linktree)malloc(sizeof(Hftree);/*创建单链表的头结点*/if(!tree)return NULL;tree-next=NULL; /* 头结点为空,且后续结点为空*/for(i=0;characteri!=0&characteri!=n;i+) /*遍历直到字符串结束为止*/ptr=tree;beforeptr=tree;node=(linktree)malloc(sizeof(Hftree); /*新申请结点node*/if(!node)return NULL;node-next=NULL;node-parent=NULL;node-lchild=NULL;node-rchild=NULL; /*置空*/node-mark=0;node-ch=characteri;node-weight=1;if(tree-next=NULL)tree-next=node; /*头结点的下一结点为空,连接node*/else ptr=tree-next;while(ptr&ptr-ch!=node-ch) /*将指针移至链表尾*/ ptr=ptr-next;beforeptr=beforeptr-next; /*后移*/if(ptr&ptr-ch=node-ch) /*如果链表中某结点的字符与新结点的字符相同*/*将该结点的权加一*/ ptr-weight=ptr-weight+1;free(node); /*释放node结点的存储空间*/else /*新结点与表中结点不相同,将新结点插入链表后*/node-next=beforeptr-next;beforeptr-next=node; /*node连接在beforeptr之后*/return tree;/*将整理完的字符串按出现次数从小到大的顺序排列 */linktree taxisnode(linktree tree) linktree head,ph,pt,beforeph; /*head为新链表的表头结点*/head=(linktree)malloc(sizeof(Hftree);/*创建新链表的头结点*/if(!head)return NULL;head-next=NULL; /*新结点的头结点为空,后续结点也为空*/ph=head;beforeph=head;while(tree-next) pt=tree-next;/*取被操作链表的首元结点*/tree-next=pt-next;pt-next=NULL; /*取出pt所指向的结点*/ph=head-next;beforeph=head;if(head-next=NULL)head-next=pt;/*创建当前操作链表首元结点*/else while(ph&ph-weightweight) /*将被操作结点插入相应位置*/ ph=ph-next;beforeph=beforeph-next;pt-next=beforeph-next;beforeph-next=pt;free(tree);return head;/*用排完序的字符串建立霍夫曼树 */linktree createHftree(linktree tree) linktree p,q,newnode,beforep;for(p=tree-next,q=p-next;p!=NULL&q!=NULL;p=tree-next,q=p-next) tree-next=q-next;q-next=NULL;p-next=NULL;newnode=(linktree)malloc(sizeof(Hftree);/*申请新结点作为霍夫曼树的中间结点*/if(!newnode)return NULL;newnode-next=NULL;newnode-mark=0;newnode-lchild=p;/*取链表头结点后的两个结点作为新结点的左、右儿子*/newnode-rchild=q;p-parent=newnode;q-parent=newnode;newnode-weight=p-weight+q-weight;p=tree-next;beforep=tree;if(p!=NULL&p-weight=newnode-weight) /*将新结点插入原链表的相应位置*/ newnode-next=beforep-next;beforep-next=newnode;else while(p!=NULL&p-weightweight) p=p-next;beforep=beforep-next;newnode-next=beforep-next;beforep-next=newnode;return (tree-next);/*对霍夫曼树进行编码 */void Huffmancoding(linktree tree) int index=0;char *code;linktree ptr=tree;code=(char *)malloc(10*sizeof(char);/*此数组用于统计霍夫曼编码*/printf(字符以及它的相应权数-霍夫曼编码nn);if(ptr=NULL) printf(霍夫曼树是空的!n);exit(0);else while(ptr-lchild&ptr-rchild&ptr-mark=0) while(ptr-lchild&ptr-lchild-mark=0) codeindex+=0;ptr=ptr-lchild;if(!ptr-lchild&!ptr-rchild) ptr-mark=1;codeindex=0;printf(tw%c=%dttt,ptr-ch,ptr-weight);for(index=0;codeindex!=0;index+)printf(%c,codeindex);printf(n);ptr=tree;index=0;if(ptr-rchild&ptr-rchild-mark=0) ptr=ptr-rchild;codeindex+=1;if(!ptr-lchild&!ptr-rchild) ptr-mark=1;codeindex+=0;printf(tw%c=%dttt,ptr-ch,ptr-weight);for(index=0;codeindex!=0;index+)printf(%c,codeindex);printf(n);ptr=tree;index=0;if(ptr-lchild-mark=1&ptr-rchild-mark=1)ptr-mark=1;ptr=tree;index=0;printf(n);free(code);/*解码 */void decode(linktree tree,char code) int i=0,j=0;char *char0_1;linktree ptr=tree;char0_1=(char *)malloc(10*sizeof(char);/*此数组用于统计输入的0、1序列*/printf(霍夫曼编码-相应字符nn);for(j=0,ptr=tree;codei!=0&ptr-lchild&ptr-rchild;j=0,ptr=tree) for(j=0;codei!=0&ptr-lchild&ptr-rchild;j+,i+) if(codei=0) ptr=ptr-lchild;char0_1j=0; if(codei=1) ptr=ptr-rchild;char0_1j=1; if(!ptr-lchild&!ptr-rchild) char0_1j=0;for(j=0;char0_1j!=0;j+)printf(%c,char0_1j); printf(tt%cn,ptr-ch);if(codei=0&ptr-lchild&ptr-rchild) char0_1j=0;printf(没有与最后的几个0、1序列：%s相匹配的字符!n,char0_1);return;free(char0_1);/*文件*/inchange()FILE *fp;char ch;if(fp=fopen(e10_1.c,rt)=NULL)printf(Cannot open file strike any key exit!);getch();exit(1);ch=fgetc(fp);while (ch!=EOF)putchar(ch);ch=fgetc(fp);fclose(fp);/*释放霍夫曼树所占用的空间*/void deletenode(linktree tree) linktree ptr=tree;if(ptr) deletenode(ptr-lchild);deletenode(ptr-rchild);free(ptr);void Huffman() /*霍夫曼树建立*/ int n;char characterMAXLEN,codeMAXLEN;FILE *f1;linktree temp,ht,htree,ptr=NULL;printf(一、编码:n请输入要测试的字符串:nn);scanf(%s,character);printf(n);temp=tidycharacter(character);ht=taxisnode(temp);htree=createHftree(ht); Huffmancoding(htree); printf(二、解码:n请输入用于解码的0、1序列:nn);scanf(%s,code);printf(n);decode(htree,code); deletenode(htree);#include #include #include #include #include #include #include#define M 6 /* 6 个男子项目 */#define W 4 /* 4 个女子项目 */#define N 10typedef struct int man5+1; /* 排名，此数组中存放学校代码 */ int women3+1; char InameM+W+1; /* 项目名称 */Item; /* 项目代码，M的为女