数据结构课程设计报告-模板.docx

《数据结构课程设计报告-模板.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告-模板.docx（26页珍藏版）》请在第一文库网上搜索。

1、电3府放4W信息与软件工程学院课程设计报告课程名称：数据结构课程设计学院专业：信息与软件学院XX专业学生姓名：赵大钱二孙三李四周五吴六学 号：20112210XXXXX 20112210XXXXX20112210XXXXX 20112210XXXXX20112210XXXXX 20112210XXXXX指导教师：周益民日 期：2012年06月08 0目录第一章绪论11.1. 数据结构课程设计概要11.2. 训练要求11.3. 课程设计的根本内容2第二章约瑟夫生死者游戏32.1. 游戏描述32.2. 需求分析32.3. 概要设计42.3.1. 循环链表42.3.2. 顺序表42.4. 详细设计4

2、2.4.1. 循环链表解决方案42.4.2. 顺序表解决方案625低复杂度求解进阶方案72.6. 测试分析82.7. 小结10第三章哈夫曼压缩编码113.1. 哈夫曼树和哈夫曼编码113.1.1. 哈夫曼树113.1.2. 哈夫曼编码113.2. 需求分析123.3. 概要设计133.4. 详细设计153.5. 测试分析213.6. 小结22第四章报告总结23第五章参考文献25第一章绪论计算机科学与技术专业强调四个方面的专业能力：计算思维能力、算法设计与分析 能力、程序设计与实现能力和计算机系统的认知、分析、设计和运用能力。1.1. 数据结构课程设计概要数据结构课程设计是数据结构课程的深入与实

3、践，是计算机科学与技术学 科的核心课程。通过数据结构课程设计的学习.目的在于使学生：1、使学生进一步理解和掌握课堂上所学各种根本抽象数据类型的逻辑结构、存储结构和操作 实现算法，以及它们在程序中的使用方法。2、使学生掌握软件设计的根本内容和设计方法，并培养学生进行标准化软件设计的能力。3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的根本能力。4.使学生学会自主学习，也学会以团队的形式思考问题，解决问题，培养学生的团队合作能力。5.使学生在团队工作中培养良好的人际交流的能力，以及沟通能力随着计算机的普遍应用与日益开展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、

4、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为 以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术根底。算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储 结构，从而使建立在其上的解决问题的算法到达最优。数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构 成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结 构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结 构反映成分数据在计算机内部的存储安排。

5、数据结构是数据存在的形式。数据结构主要介绍一些最常用的数据结构，说明各种数据结构内在的逻辑关系，讨论其在计算 机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。 数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程 序设计、数据库、操作系统、编译原理及人工智能等的重要根底，广泛的应用于信息学、系统工程 等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。1.2. 训练要求数据结构课程设计独立于具体的数据结构教科

6、书，重点放在数据的存储及在存储结 构上实现的相关典型算法上。以较多的应用实例来涵盖数据结构这门课程所要求的各类 重要根底知识。结合实际应用的要求，使课程设计既覆盖教学所要求的知识点，又接近工程的实际 需要。训练了实际分析问题、解决问题及编程能力的整体提高。通过详细的实例分析、循序渐进的描述，启发同学们顺利完成设计。课程设计将设 计要求、需求分析、算法设计、编程和测试运行分开，为同学们创造分析问题、独立思 考的条件。在充分理解要求和算法的前提下，完全可以不按教材中提供的参考程序，设 计出具有特色的应用程序。课程设计的内容根本上按照课程教学的顺序设计，可以让学生循序渐进地学习，以 加深同学们对数据

7、结构知识的理解。课程设计的最后提出了几个比拟大的综合课程设计题目，以进一步锻炼同学们的动 手能力。1.3. 课程设计的根本内容主要内容包含有：1 .链表的应用：约瑟夫生死者游戏。2 .树结构的应用：赫夫曼编码的应用。学生必须仔细阅读数据结构课程设计方案，认真主动完成课设的要求。有问题及时 主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间，安排好课设的时间方案，并在课设过 程中不断检测自己的方案完成情况，及时向教师汇报。课程设计按照教学要求需要16 课时的时间完成，上机调试程序时间总共不少于16小时。第二章 约瑟夫生死者游戏在这一次的课程中，将利用线性链表，特别是循环链表来

8、实现约瑟夫生死问题。2.1. 游戏描述【其一】据说著名犹太历史学家JoSePhUS有过以下的故事：在罗马人占领乔塔帕特 后，39个犹太人与JoSePhUS及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要 被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数， 每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为 止。然而JoSePhUS和他的朋友并不想遵从，JoSePhUS要他的朋友先假装遵从，他将朋友 与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。【其二】17世纪的法国数学家加斯帕在数目的游戏问题中讲了这样一个故事： 15个教

9、徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免 于难，于是想了一个方法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九 个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次 投入大海的都是非教徒。【其三】N个人，编号0.N-1,从。开始报数，报到1的退出，通常取 剩下的人继续从。开始报数，报到V-1的退出，如此往复。求最终胜利者的编号。2.2. 需求分析构建线性表，通过线性表循环地向后移动来模拟“约瑟夫生死问题”的进行,最后给 出模拟结果。分别用数组和链表来实现此次模拟。并思考是否有其他更优解决方案。程序提示使用者输入人数N,和每次报数个

10、数M,输出淘汰序列和最后赢家。2.3. 概要设计2.3.1. 循环链表议定30个人围成一圈，由第1个人数起，依次报数，数到第9人，便把他投入大 海中，然后再从他的下一个人数起，数至第9人，再将他扔到大海中，如此循环地进行， 直到剩下最后一个乘客为止。约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实 现方法。题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结 构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环 形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未 扔下海的人进行计数，每数到9时，将结构中的

11、标记改为0,表示该人已被扔下海了。 这样循环计数直到有最后一个人为止。232.顺序表为了节省空间复杂度，我们提出了这样一种问题：能否采用线性表来实现？答案是肯定的。那么怎样实现呢？以动态数组元素代替循环链表节点的算法实现。考虑：动态数组的申请、使用、回收三原那么。用30个元素数组来存放结果，初始化全为1,如果这个人被丢到海里了，就把对应 位置的元素置为0;用一个变量依次对数组里不为0的元素计数，数到9那么把对应位 置的数组元素置0；循环控制可以用乘客数量来控制；初始为30,每有一个元素被置0, 那么乘客数量减1,直到1。2.4. 详细设计2.4.1. 循环链表解决方案伪代码：1 .首先定义链表

12、节点。数据域用整数表示人员编号。2 .然后将节点组成为30个节点的单循环链表。删除计数器置0。3 .从指定位置开始计数，移动计数器置1,移动指针到下一个节点，移动计数器加Io 计数器置8时，将下一节点删除。删除计数器加1。4是否只剩下最后一人？否那么从删除节点的下一个节点开始作为起始位置，跳至3o是那么结束循环。int JonSLiSt(JonS * Had, int N, int M) JonS *p,*q;P=Had;q=p_nxt;WhiI(q-nXt!=P)q=q_nxt;)WhiI(P!=p-nXt)for (int i=l;krxt=p-rxt;fr(P);p=q_nxt;)ret

13、urn p-numbr;采用线性链表来解决约瑟夫问题必然使用到N个节点，节点中既要存储数据信息也 需要存储位置信息(即循环链表的指针)。存储空间使用较多，为O(N)。构造线性循环链表JcmS * Cr(int n)JOnS *h,*p;int i;h=(Jons *)malloc(siz of (JonM);p=h;for (i=l;icod=i;if (inXt=(Jonse *)malloc(sizof (Jonsa);P=P_nxt;)p-r xt=h;return h;输出遍历链表void ShOWLiSt(JC)ns *h) JC)ns *p;Pdprintf(dt，p-cod);P

14、=P_nxt; WhiI(p!=h);执行算法void OUt(JOnS *h,int irint d,int num, int flag) JcmS *p, *q;int k;p=h;f。工(q=h; q-rxt! =h; q=q-nXt);for(k=l;knXt)for (k=l;kcod);q-rxt=p-rxt;f工(P);P=NULL;p=q_nxt;flag+;if(num-flag=2)brak;printf(dn，p-Cod);fr(P);p=NULL;242.顺序表解决方案int JOrIsArray (int N, int M) int *jcms;int winner;jons=nW int(N);int i,j,t;for(i=0;i=l;i-)t=(t+M-1)%i;coutj onSt ;for (j=t+l;j=i-l;j +)jonSj-1=jonS j;)Wirm