数据结构课程设计

1、数据结构课程设计一、 课程设计的目的：通过数据结构课程设计使能够运用数据结构提供的方法与技巧更好地进行算法设计和程序设计，即能最好地实现与课程同步练习，又能培养同学们程序设计及上机调试的能力。希望这次机会提高自己。二、课程设计的要求：要仔细阅读题目内容，认都能积极的参与课程设计，充分利用动完成课程设计的要求题目的设计、程序的调试及书写课程设计。在课程设计中要发挥学习的能力，充分利用时间，安排好课设的时间计划，并在课程设计过程中不断检测自己的计划完成情况，有问题及时主动与老师联系沟通。课程设计的时间安排：（1）11 月 20 日前交各组的开题。开题内容包含每个项目的设计思想及数据的结构（相应的数

2、据类型），课程设计的具体进度安排。（见表）数据结构课程设计开题表（2）11 月 20 日前中期检查，完成程序框图及各模块的功能说明（包括数和出口参数），并汇报设计进度。参（3）12 月 25 日前完成设计和调试，交课程设计。课题名称小组题目的设计及数据的结构：进度安排：二、 课程设计要求：（保存在 word 文档中，文件名要求 按照内容包括:-学号-课程设计起名 ）（1）（2）求分析：在该部分中叙述，每个模块的功能要求。概要设计：在此说明每个部分的算法设计说明（可以是描述算法的流），每个程序中使用的结构设计说明（如果指定结构请写出该结构的定义。（3）详细设计：各个算法实现的源程序，对每个题目要

3、有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。调试分析：测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。课设总结：课程设计 过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对数据结构课程的认识等内容（4）（5）1、 设计集合的运算器*基本功能要求：（1） 输入两个集合，按值递增有序在单链表中并输出。（2） 利用归并法分别求出两个集合的并集、交集

4、和差集，且按值递减有序，并输出结果。2、 设计线性表的运算器*基本功能要求：线性表以静态链表方式。实现以下基本运算，（1）（2）（3）（4）（5）初始化：ListInIt(&L)定位：LocateElem(L,e)：ListInsert(&L,i,&e) 删除：ListDelete(&L,i,&e)替换：ListReplace(&L,len,L1)3、 设计两个任意长的整数加减法的运算器*基本功能要求：（1）（2）（3）输入两个长整数。利向循环链表长整数，每个结点四位数。计算结果于双向循环链表。输出运算式子及结果。4、*说明：先将一个花色的 13排列好。朝上开始表演，每次向下翻过 n 张牌后出

5、上面一张，依次操作直到出完所有牌，出牌的结果为 A 2 3 。j Q K。例如：n=2 排列好的牌为J 5 A 8 10 2 6 Q 3 9 7 4 K基本功能要求：（1） 建立单向循环链表排列好的牌型。（根据输入的n=0,1,2,3.,n=0 为要出几就翻几）（2） 模拟此过程，显示每次出牌有的牌型。5、 停车场管理*说明：停车场是一个能放 n 辆车的狭长通道，只有一个大门，汽车按到达的先后次序停放。若车场满了，车要停在门外的便道上等候，一旦有车走，则便道上第一辆车进入。当停车场中的车离开时，由于通道窄，在它后面的车要先退出，待它走后在依次进入。汽车离开时按停放时间基本功能要求：。建立三个数

6、据结构分别是：停放、让路、等候。输入数据模拟管理过程，数据的三元组（入或出，车号，时间）。6、多个栈共享空间*说明：设 STACKMAXSIZE为 n（n2）个栈共享。设各栈栈顶指针为 topn，分别指向栈顶元素的位置；设各栈栈底指针为 botn，分别指向栈底元素的前一个位置，这里 topi和 boti确定了栈 i 的空间。初始时 STACKMAXSIZE空间平分给n 个栈。基本功能要求：设计算法对第 i 栈入栈操作：Push(&S,i,e) 仅当 MAXSIZE 个空间全部占用时才产生溢出。 (即当第i 栈满时需要调整前后栈空间)7、单词的词频统计*基本功能要求：（1） 从文件中读出一篇英文

7、文章，将不同的单词存入堆中，建立相应的索引表确定各单词在堆中的位置及出现的次数。（2） 按出现的频率递减的次序输出。8、稀疏矩阵的操作*基本功能要求：（1）（2）（3）（4）采用三元组表两个稀疏矩阵A 和B。求出 C=A*B，输出 C。采用链表两个稀疏矩阵A 和B。求出 C=A+B，输出 C。9、多元多项式的计算*基本功能要求：输入一个三元多项式 P(x,y,z)以广义表的方式实现求 P(x0,y0,z0)的值。10、二叉树的操作*基本功能要求：（1）（2）（3）（4）建立二叉链表。求出二叉树中指定结点的子孙。删除其所有子孙结点。求出二叉树中指定结点的祖先。11、树与码基本功能要求（1）输入一

8、个文本，统计各字符出现的频度，输出结果使用字符出现的频度构造确定和输出各字符的树码（4）输入一个由 0 和 1 组成的代码序列，翻译并输出与之对应的文体，若最后的代码子序列不能译为文本，则输出相关信息12、有向图基本功能要求：链表的操作*（1）（2）（3）有向图以链表方式。出指定结点的度（出度和入度）。操作：一边（u,v），删除一边(u,v)。13、无向图邻接多重表的操作*（1）（2）（3）图的建立，采用邻接多重表作为求出指定结点的度。结构。操作：一边（u,v），删除一边(u,v)。14、二叉排序树的操作*基本功能要求：（1）（2）（3）输入一组单词建立一个二叉排序树。有序显示这组单词，计算平

9、均查找长度。功能：检索、删除。15、哈希表的操作*基本功能要求：（1）（2）输入一组单词。建立用开放定址法处理数）。功能：检索、删除。建立哈希表（以第1 字母的序号作为哈希函（3）16、哈希表的操作*基本功能要求：（4）（5）（6）输入一组单词。建立用链地址法处理建立哈希表。（以第 1 字母的序号作为哈希函数）功能：检索、删除。17、链表排序*基本功能要求：（1）（2）（3）生成一组随机数以单链表方式，并输出。利用起泡排序法排序，并显示结果。利用选择排序法排序，并显示结果。（建立两个单链表分别排序）18、基数排序的应用*基本功能要求：（参考书 P293）（1）（2）（3）输入一组单词并显示。利

10、用基数排序方法对单词排序。按字母次序输出排序结果。19、家谱*基本要求：从文件中读入家庭成员建立家谱，以孩子兄弟表示法基本功能：家谱管理，文件输入样本：（也可以是英文名字）。（、吴本质、吴本身）（、）（、）（）吴本质（）（、）吴本身（、）（、）20、设计程序模拟排队买票的过程*问题描述：排队买票每个队伍允许插队。每次一个人入队列，如果这个入队的人发现队伍中有自己的朋友，则可以到这个朋友的后面；当队伍中朋友不止一个的时候，这个人要排在最后一个朋友的后面；如果队伍中没有朋友，则他只能排在这个队伍的最后面。当队伍前面的人买到车票之后，依次出队。输入要求：从文件“input.txt”中读入测试用例，一个文件可包含多个测试用例。每个用例第一行是朋友组的数目n。对于一个朋友组的数目m 开始，由朋友的个数以及他们的名字组成，以空格分隔，每个人的名字都不同，每个人只能属于一个朋友组。n=0 时测试结束。操作命令：ENQUEUEXX 入队；DEQUEUE对头卖完票出队；STOP一个测试用例结束。输出要求：输出到文件“output.txt”中，并显示在屏幕上。每个测试用例第一行输出“Scenario #k”，k 为测试用例序号（从 1 开始）。对于每个 DEQU