《数据结构课程设计报告-模板.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告-模板.docx（25页珍藏版）》请在课桌文档上搜索。
1、电3科技比W信息与软件工程学院课程设计报告课程名称：数据结构课程设计学院专业：信息与软件学院XX专业学生姓名：赵大钱二孙三李四周五吴六学号：20112210XXXXX2011221011XXX20112210XX11X20112210XXXXX20112210XX11X20112210XXXXX指导教师：周益民日期：2012年06月08日目录第一章绪论11.1. 数据结构课程设计概要11.2. 训练要求11.3. 课程设计的根本内容2第二章约瑟夫生死者游戏32.1. 游戏描述32.2. 需求分析32.3. 概要设计42.3.1. 循环链表42.3.2. 顺序表42.4. 详细设计42.4.1.
2、 循环链表解决方案42.4.2. 顺序表解决方案62.5. 低复杂度求解进阶方案72.6. 测试分析82.7. 小结10第三章哈夫曼压缩编码H3.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小时。第二章约瑟夫生死者游戏在这一次的课程中，将利用线性链表，特别是循环链表来实现约瑟夫生死问题。2.1. 游戏描述【其一】据说著名犹太
8、历史学家JoSePhUS有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与JoSePhUS及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而JOSePhUS和他的朋友并不想遵从，JOSePhUS要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。【其二】17世纪的法国数学家加斯帕在数目的游戏问题中讲了这样一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免
9、于难，于是想了一个方法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。【其三】N个人，编号0.N-1,从0开始报效，报到M-I的退出，通常取Mnext;while(q-next!=p)(q=q-next;while(P!=p-next)(for(inti=l;knext;q-next=p-next;free(p);p=q-next;returnp-number;J采用线性链表来解决约瑟夫问题必然使用到N个节点，节点中既要存储数据信息也需要存储位置信息(即循环链表的指针)。存储空间使用较多，
10、为O(N)O构造线性循环链表Jonse*Create(intn)(Jonse*hz*p;inti;h=(Jonse*)malloc(sizeof(Jonse);=h;for(i=l;icode=i;if(inext=(Jonse*)malloc(sizeof(Jonse);p=p-next;)-next=h;returnh;榆出遍历链表voidShowList(Jonse*h)(JonSe*p;=h;do(printfzp-code);p=p-next;while(!=h);执行算法voidOut(Jonse*hzintizintdzintnum,intflag)Jonse*pz*q;intk
11、;p=h;for(q=hq-next!=h;q=q-next);for(k=l;knext;)while(p!=p-next)(for(k=l;knext;)printf(%dt,p-code);q-next=p-next;free(p);p=NULL;p=q-next;flag+;if(num-flag=2)break;)printf(%dnrp-code);free(P);p=NULL;J2.4.2. ,顺序表解决方案intJonesArray(intN,intM)int*jones;intwinner;jones=newint(N);intizjzt;for(i=0;i=l;i-)t=(
12、t+M-l)%i;coutjonest;for(j=t+l;j=i-l;j+)jonesj-l=jonesj;)winner=jones0;coutwinneriswinnerl奎茎封祥亮线曳汨N-1个人报数的子问题，假设我们知道这个子问题的解:例如X是最终的胜利者，那么根据上面这个表把这个X变回去不刚好就是N个人情况的解吗？变回去的公式很简单，相信大家都可以推出来：x=(x+2)modN如何知道N-I个人报数的问题的解？对，只要知道N-2个人的解就行了。N-2个人的解呢？当然是先求N-3的情况这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：令/表示i个人玩游戏报M退出最后胜利者的编
13、号，最后的结果自然是/()fn。递推公式/(D=O=(+M)modzl有了这个公式，我们要做的就是从1.N-1顺序算出/的数值，最后结果是/(N)。因为实际生活中编号总是从1开始，我们输出f(N)+l0由于是逐级递推，不需要保存每个了,程序也是异常简单。intJonesWinner(intN,intM)(intwinner=O;for(inti=2;i=N;i+)winner=(winner+M)%i;winner+=l;coutwinneriswinner winner is 334数学方法耗时：3 msplease input the N:10000Please input the M：5
14、00JonesArrayO v/inner is 368飒序表方案耗时：108 msJonesListO winner is 368链表方法耗时：87msJonesWinnerO winner is 368留学方法耗时：1msPlease input the N:10000Please input the M：9999JonesArrayO winner is 3377顺序表方莱耗时：II6 msJonesListO winner is 3377链表方法耗时：998 nsJonesWinnerO winner is 3377数学方法耗时：3 ms上面只是进行了简单的测试，从上面的测试我们可以看
15、出至少这三种方案都正确的进行了模拟，得出了我们想要的结果。关于效率问题，前面有提到过顺序表和链表的实现的时间复杂度都是O(MM,但是在实际的程序运行还是存在差异。顺序表每次淘汰一个数后还需要消耗时间将后续的数向前搬移1个单元；链表每次淘汰一个节点后需要消耗时间释放该节点的内存空间。数学的模拟方法确实就比拟高而稳定了，时间复杂度为O(N)o其实本人还进行了很多的测试，想要总结一下它们之间的效率比照问题。但是最后发现测试结果不规律，主要是链表方法的结果不规律。由于未能分析得出非常确切的答案，所以下面只进行大致的描述，提出猜测，待以后进行验证。顺序表实现和数学实现还是比拟规律的，比拟可以分析理解。关
16、于链表实现不规律的问题，我直接举一个例子就能看到了，如右图。都是N=IoOO0,M=I的结果是M=2的结果的9倍左右，差距非常的大。再进行其他的一些测试，测试结果也是存在波动的。下面是本人关于这个问题的一些猜测。当M=I时，链表的处理比拟特殊，链表不会往后移动，会直接淘汰当前的节点，释放free单元。从理论上来说，不管M为何值，最终N个节点都会释放的，也就是要free()N次，一般我们认为这N次释放的时间花销应该是一样的，那么当M=I时，时间花销应该是最小的，因为它节约了向后移动的时间花销。但是我们实际结果，不仅不是最小的，反而效率非常低下，当M=2时，每次向后移动一个节点，效率马上又不那么低
17、下了。从此，我们可以推断：释放内存操作不能够连续高效地进行，操作之间存在一些间隔反而能更加高效。这里面就应该设计到内存池的实现机制的问题了。在此，我们可以猜测：链表实现方法的效率的不规律受内存池的机制内存分配与释放等影响较大。比方：free。之后内存可能不会立即归还系统，下次malloc时也许会重用，那么这个时间间隙是多久呢？在时间间隙中有要释放内存单元呢？该问题需进一步研究后得出结论，在此就简单描述了。2.7. 小结通过上面的实验，验证了用3种方法实现约瑟夫的模拟。另外，有趣的是在分析实验数据的时候发现了链表实现的不规律问题，猜测原因是与内存池机制有关，留待后续处理。通过遇到的问题，真正让我
18、感受到，很多时候实践确实是很有价值的，能发现问题，也只有通过实践后才能去肯定我们的理论技术。当我们只有真正去动手做时，就会发现该游戏程序中很多问题，在发现问题的过程中，也伴随着大家培养解决问题的能力，促进这个团队的工作力与协作性，在诸多问题的一个个解决过程中，每一位队员都学习了良好的经验与纠错能力。总之，一句话，我们正在成长。第三章哈夫曼压缩编码3.1. 哈夫曼树和哈夫曼编码3.1.1. 哈夫曼树哈夫曼树。给定n个权值作为n个叶子结点，构造一棵二叉树，假设带权路径长度到达最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(HUffmantree)。哈夫曼树相关的根本术语：(1)路径和路径长度在一
19、棵树中，从一个结点往下可以到达的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。假设规定根结点的层数为1,那么从根结点到第L层结点的路径长度为L7;(2)结点的权及带权路径长度假设将树中结点赋给一个有着某种含义的数值，那么这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积；(3)树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPLo哈夫曼树的构造：假设有n个权值，那么构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1、W2、wn,那么哈夫曼树的构造规那么为：(1)将w1、w2、，Wn看成是有n棵树的森林
20、(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树参加森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。3.1.2. 哈夫曼编码霍夫曼编码(HUffnlanCOding)是一种编码方式，是一种用于无损数据压缩的场编码权编码算法。1952年，DavidA.HUffman在麻省理工攻读博士时所制造的，并发表于一种构建极小多余编码的方法AMethodfortheConstructionofMinimum-RedundancyCod
21、es一文。在数据通信中，需要将传送的文字转换成二进制的字符串，用0,1码的不同排列来表示字符。例如，需传送的报文为“AFTERDATAEARAREARTAREA”，这里用到的字符集为“A,E,R,T,F,D”，各字母出现的次数为8,4,5,3,1,1）现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、IO0、101对“A,E,R,T,F,D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。假设报文中可能出现26个不同字符，那么固定编码长度为5。然而，传送报文时总是
22、希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z,自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。为使不等长编码为前缀编码（即要求一个字符的编码不能是另一个字符编码的前缀），可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于求出了传送报文的最短长度。因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼
23、树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。3.2. 需求分析利用哈夫曼编码算法压缩文件是一种无损压缩算法，它适用于文本压缩或者能够统计字符的文件，因为哈夫曼算法是一种基于字符统计的压缩方法。它的本质就是对文本文件中的字符进行重新编码,对于使用频率越高的字符,其编码也越短。但要求编码属于前缀码,即任何2个字符的编码,不能出现向前包含的关系,也就是说字符A的编码的前段,不能为任意一个字符B的编码。产生哈夫曼编码压缩需要对原始数据扫描两遍：第一遍是为了建立哈弗曼码表，扫描要精确地统计出原始数据中的每个字符出现的频率,然后用频率作为权重值建立哈哈弗曼树，在根据建立好的哈夫
24、曼树进行哈夫曼编码，生成哈弗曼码表；第二遍就利用生成的码表将文本中的字符转换成码表中对应的编码,即进行压缩操作。压缩生成的文件主要包含2个局部：原始文本的字符统计和原始文本压缩转换后的内容。解压缩的时候，先把原始文本的字符统计取出,然后根据统计值为权重建立新的哈夫曼树，生成哈弗曼码表，然后使用这一码表对压缩内容局部各个字符进行逐一解码,复原为原始文件。哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最正确的。该算法不对重复子串统计编码，而且符号的出现频率不能预知,所以效率也是不能预知的。而且需要统计和编码两次处理，所以速度较慢，但简单有效，因而得到广泛的应用。概要设计思路：统计ASCI
25、l编码各编码出现的字数，对个编码的权重赋值。因此需要翻开目标文件，对目标文件进行遍历。此功能通过以下函数实现。voidcharacter_count();3.3.2对每个字符的权值赋值后，接着创立哈夫曼树，哈夫曼树的创立是从底向上的，取出权值最小的两个节点，作为新节点的左右孩子，新节点的权值赋值为左右孩子权值之和。删除原来的两个节点，并把新节点放入原节点的集合。1.1.5 重复1、2步直至剩下一个节点(即哈夫曼树的根节点)此功能需要通过下面三个函数实现创立哈夫曼树，返回根的地址phuffhuffman_tree_creat();找出权值最小的两个节点voidfind_min();进行节点的合并
26、、删除替换voidcombine_replace();1.1.6 创立了哈夫曼树，需要建立256ASCII编码的哈夫曼编码码表,方便对下一步对字符压缩进行位运算操作。编码码表的建立通过遍历哈夫曼树确定，并将每个字符的编码储存与字符串指针数组中。此功能通过以下函数实现voidhuffman_code_hashO;建立码表之后就可以对文本进行压缩。这里有三个问题需要注意，还有一点改良建议。每个ASell编码对应的哈夫曼编码由0、1的有序序列组成,但使用CHAR类型进行存储达不到压缩的文本的目的（一个字符的编码变成了多个0、1组成的字符串）。需要以位为单位记录编码信息。但是C语言允许的最小操作对象是
27、一个字节，故存储的时候必须对每个字节进行位运算，使用Char类型比拟适宜。不建议把文件的哈夫曼编码写文本文件。文本文档以；结尾，负数在计算机内存中以补码的形式存在，即；是存储为IIIIII11,在实际压缩字符是我们可能会连续写入多个1,这样的话可能造成在编码的存储文件中间参加文本结束符，后面的编码无法读取，信息丧失，而这是不允许的。解决方案有两个。一可以继续选择存储为文本模式，但是每个字节必须空出最高位，即最高位置0,防止在文本的中间写入IIIIII11,使得后面的编码序列无法读取。但是这种方式首先造成了大量的浪费，每个字节8位，空出了1位，当压缩的文本巨大时造成存储空间的大量浪费，而这一点跟
28、哈夫曼编码的压缩功能是相违背。再者，每个字节空出一位，那么对每个字节进行位运算是需要做特殊处理，虽然不是很麻烦，但是多余的而且必须的操作造成了时间上面的浪费。第二种解决方案比拟简单，将哈夫曼编码存储位二进制文件，使用函数feof()判断文件时候读取到最后。1.1.7 对存储哈夫曼编码的最后一个字节必须做特殊处理，如果还有剩余K位没有操作，那么必须填充哈夫曼树中深度最的的编码的前面K位。原因有两点，一是为了保证前面8*位位于字符的高位，方便解码函数的编写，第二是为了保证不输出多余信息，实现文本的无损压缩(当指针到达不了叶子，那么就没有字符输出)。1.1.8 这一点是改良建议，在编写的程序中是每操
29、作一个字符都对文件进行一次读写，这样在哈夫曼进程与系统进程的频繁切换造成了大量的时间浪费，降低了效率，为了提高程序的效率，可以采用缓冲技术，每次从源文件读取一定长度的数据，存储在源文件缓冲区，对源文件缓冲区的字符进行操作，并将存储了哈夫曼编码的char类型的数据存储在一个缓冲区。当源文件缓冲区或哈夫曼编码缓冲区满的时候对硬盘进行一次读取写入操作，减少哈夫曼进程与系统进程的切换次数，减少不必要的时间损耗。记录ASCll编码的权值，以便重新翻开。3.3. 详细设计includettinclude#include#includeincludeItincludedefineBUFFSIZE512typ
30、edefstructHUFFMAN,TREE(unsignedchardate;structHUFFMANTREE*left;structHUFFMANTREE*right;huff,phuf;IypedefstructCHARACTERCOUNT(unsignedchardate;unsignedintnum;cher;voidmain(intac,char*av)(FILE*fp=NULL:chercharacter256;intChajhaSh256=0;voidcharactercount(),character_sort();voidcharacterhash(),character
31、encode(),characterdecode();phuffHuffmanIree一Creat();/nofiletoprocess,exitif(ac=l)printf(*nofileinputn*);return;)/dealonefileeachtimewhile(-ac)(fp=fopen(*+av,r);if(fP=NULL)exit(1);charactercount(fp,character);charactersort(character,0,255);characterhash(charhash,character);characterencode(*av,fp,char
32、hash);characterdecode(*av,character);huffmantreecreat(character);)/asyoucansee,itcountthefrequencyofeachcharacter,/andsaveitinastructarryvoidcharactercount(FILE*fp,chercharacter256)inti;charbuffBUFFSIZE+l=,0,：for(i=0;iright)return;for(std=left,i=std+l;i=characteri.num)continue：elseunsignedintnumtemp
33、=0;unsignedchardatetemp=,0,;numtemp=characterstd.num;datetemp=characterstd.date;charactersId.num=characteri.num;characterstd.date=characteri.date;characteri.num=characterstd+l.num;characteri.date=characterstd+l.date;+std;characterstd.num=numtemp;characterstd.date=datetemp;)charactersort(character,le
34、ft,std-l)：character,sort(character,std+l,right);return：)/setupahashfunction,soitwillbemucheasiertoknowwhathuffma11-codeofthepresentcharacterisvoidcharacterhash(intcharhash,chercharacter256)inti;for(i=0;i0,;unsignedcharnamedes32=,0,;unsignedintor_value();FILE*fpdes;char*desname=(char*)malloc(strlen(f
35、iIe.name)+10)*sizeof(char);strcpy(desname,filename);StrCat(des一name,code.lxl);desname(strIen(fiIename)+9)=,0,：fpdes=fopen(desname,w);rewind(fpsou);c=fgetc(fp一SOU);for(k=8;!feof(fpsou);)(hash=charhashc;if(khash)(buffcode=hash;buffcode=orvalue(hash);buffcode=l;k-=hash+l;)elsewhile(k=hash)(buffcode0;ha
36、sh-=k;k=8;)buffcode=hash;buffcodeI=or_value(hash);buff_code=l;k-=hash+l：)c=fgetc(fp一SoU);)if(k!=O)buff_code=k;buffcodeI=or_value(k)：putc(buffcode,fpdes);)fclose(fpdes);return;)/decodethecodefile,otherwiseiIwillbeveryhardforyoutoreaditvoidcharacterdecode(char*ilename,chercharacter256)FILE*fp_code：unsignedcharbuff;
