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

数据结构课程设计报告

第一篇：数据结构课程设计报告数据结构课程设计散列表的应用:插队买票专业计算机科学与技术（网络技术）金玲计算机1311310704114张静林2015年1月23日学生姓名班学级号指导教师完成日期目录概述……………………………………………………………………………………11.1课程设计目的……………………………………………………………………….11.2课程设计内容……………………………………………………………………….12系统需求分析……………………………………………………………………….12.1主体功能…………………………………………………………………………....23系统概要设计…………………………………………………………………………23.1系统流程图………………………………………………………………………….24系统详细设计…………………………………………………………………………35测试……………………………………………………………………………………55.1测试方案…………………………………………………………………………….55.2测试结果…………………………………………………………………………….56小结……………………………………………………………………………………5参考文献…………………………………………………………………………………5附录………………………………………………………………………………………7附录1源程序清单……………………………………………………………………...7概述1.1课程设计目的数据结构课程设计是为数据结构课程独立开设的实践性教学环节。数据结构课程设计对于巩固数据结构知识，加强学生的实际动手能力和提高学生综合素质是十分必要的。课程设计的目的：1．要求学生达到熟练掌握C语言的基本知识和技能。2．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。3．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。4．培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。5．初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。1.2课程设计内容本课程设计的任务是写一个程序模拟这种情况。每个队伍都允许插队。如果你在排队，有一个以上的朋友要求插队，则你可以安排他们的次序。每次一个人入队，并且如果这个入队的人发现队伍中有自己的朋友，则可以插入到这个朋友的后面；当队伍中的朋友不止一个的时候，这个人会排在最后一个朋友的后面；如果队伍中没有朋友，则他只能够排在这个队伍的最后面。每一个入队的人都先进行上述的判断。当队伍前面的人买到车票之后，依次出队。系统需求分析2.1主体功能程序从“input.txt”文件读入测试用例，一个文件可包含多个测试用例。每个用例的第一行是朋友组的数目n（1下面是一些具体命令：.ENQUEUE——X入队;.DEQUEUE——排队头的人买票，离开队伍，即出队；.STOP——一个测试用例结束。测试结果输出到“output.txt”文件中。每个测试用例第一行输出“Scenario#k”，k是测试用例的序号（从1开始）。对每一个出队命令，输出刚买票离开队伍的人名。两个测试试用例之间隔一空行，最后一个用例结束不输出空行。系统概要设计3.1系统流程图系统详细设计本题目主要解决两个问题：一是怎么存放和查找大量数据（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。用散列表来存放和查找数据。由于最多有1000个朋友组，每组最多有1000人，使用平方探测法解决冲突，则表的大小是2*（1000*1000），所以选择TableSize=2000003（2000003是大于2000000的最小素数）。同一个组内的都是朋友，所以每个人除了记录他的名字name，还要记录他属于哪个组group，另外用info来表示该单元是否被占用，数据结构如图4.1所示。散列函数是根据Honer法则计算一个以64为阶的多项式，如图4.2所示。冲突解决方法采用平方探测法，如图4.3所示。#defineTabSize2000003typedefstructhashtab*PtrToHash;structhashtab/*散列表数据结构*/{charname[5];/*名字*/intgroup;/*属于哪个朋友组*/charinfo;/*标志位，该单元是否被占用*/};图4.1数据结构：散列表IntHash(char*key,intTableSize){IntHashVal=0;While(key!=NULL)HashVal=(HashValReturnHashVal%T