DS课程设计大纲

数据结构课程设计大纲数据结构课程设计大纲课程设计名称：数据结构实验室名称：计算机与信息技术实验室适用专业：计算机科学与技术、信息管理与信息系统实验对象：本科生实验要求：必修一、课程设计的目的课程设计是数据结构课程教学必不可缺的一个重要环节，它可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。通过课程设计，能够提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力，因而必须给予足够的重视。二、课程设计的要求1明确课程任务，复习与查阅有关资料。2按要求完成课程设计内容，课程设计报告要求文字和图工整、思路清楚、正确。3一至四名同学分为一组，完成一个应用问题的程序的编写工作。4应用程序应具有一定的可用性：（1）等候用户输入时，给出足够的提示信息，如“Please Select（13）：”提示用户选择。（2）格式明显易懂，配上适当的颜色、声音等辅助效果，能方便地改正输入时的错误，使用户感到方便、好用。（3）有联机求助功能。用户能直接从系统得到必要的提示，不查手册也能解决一些疑难。5程序具有一定的健壮性，不会因为用户的输入错误引起程序运行错误而中断执行：（1）对输入值的类型、大小范围、字符串的长度等，进行正确性检查，对不合法的输入值给出出错信息，指出错误类型，等待重新输入。（2）当可能的回答有多种时，应允许输入任何一种回答。（3）对删除数据应给出警告。三、课程设计的内容 课程设计的题目可由教师指定，如可在下列选题中选择，或由教师另外选择，也可由学生自行选择。但选题内容、难度要适当，要有一定的实际意义，并能达到进一步巩固和强化本课程所学知识的效果。选题1一元稀疏多项式简单计算器问题描述：设计一个一元多项式简单的计算器。基本要求：一元多项式简单计算器的基本功能为：（1）输入并建立多项式；（2）输出多项式；输出形式为整数序列：n，c1，e1，c2，e2cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列。（3）两个多项式相加减、相乘，建立并输出多项式。实现提示：可选择带头结点的单向循环链表或单链表存储多项式，头结点可存放多项式的参数（如项数等）。选题2停车场管理问题问题描述：设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排以便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场时，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。基本要求：要求程序输出每辆车到达后的停车位置（停车场或便道上），以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。实现提示：汽车的模拟输入信息格式可以是：（到达/离去，汽车牌照号码，到达/离去的时刻）。例如，（A，1，5）表示1号牌照车在5这个时刻到达，而（D，5，20）表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为（E，0，0）时结束。本题可用栈和队列来实现。选题3迷宫问题问题描述：迷宫实验是取自心理学的一个古典的实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻拦。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走通迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。基本要求：要求程序输出： （1）一条通路的二元组（i，j）数据序列，（i，j）表示通路上某一点的坐标。 （2）用一种标志（如数字8）在二维数组中标出该条通路，并在屏幕上输出二维数组。实现提示：可以利用一个二维数组mazeij表示迷宫，其中1im，1jn。数组元素值为1表示该位置是墙壁，不能通行；元素值为0表示该位置是通路。假定从maze11出发，出口位于mazemn，移动方向可以是8个方向（东、东南、南、西南、西、西北、北和东北）。选题4哈夫曼编/译码器问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，请设计这样的一个简单编/译码系统。基本要求：（1）接收原始数据： 从终端读入字符集大小n，n个字符和n个权值，建立哈夫曼树，存于文件hfmtree.dat中。（2）编码： 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入）对文件中的正文进行编码，然后将结果存入文件codefile.dat中。（3）译码： 利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入文件textfile.dat 中。（4）打印编码规则：即字符与编码的一一对应关系。（5）打印哈夫曼树：将已在内存中的哈夫曼树以直观的方式显示在终端上。实现提示构造哈夫曼树时使用静态链表作为哈夫曼树的存储。求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值。由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0，1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。选题5. 校园导游咨询问题描述：设计一个校园导游程序，为来访的客人提供各种信息查询服务。基本要求：（1）设计你所在学校的校园平面图，所含景点不少于10个，以图中顶点表示校内各景点，存放景点名称，代号，简介等信息；以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。实现提示：一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。选题6. 地图着色 问题描述：1976年，美国科学家Appel和Haken利用计算机证明了：对一张地图，可以用不超过4种颜色对其填色，使得相邻的区域填上不同的颜色。基本要求：请模拟这一填色过程，输入一张行政区地图，用4种颜色对其填色，要求相邻的行政区域内没有相同的颜色，给出所有的填色方案，并统计方案的个数。实现提示：首先考虑如何存储行政区地图，由于邻接矩阵能更好地描述各行政区之间的关系，所以采用邻接矩阵G来存储地图。 1 i，j 两个行政区相邻 Gi ,j= 0 否则邻接矩阵G可以用二维数组表示；另设一维数组colori记录第i（i=0n-1）个行政区所填的颜色，分别取值为：1红，2黄，3蓝，4绿；数据描述如下：int Gnnint colorn+1选题7. 均分溶剂问题 问题描述：设有两个小杯子B和C，容量分别为x ml和y ml，在一个大杯子A里装了（x+y）ml的化学溶剂，实验中需要精确地将大杯子中的溶剂分为两等份，在没有其它量具的情况下，只能利用这两个小杯子。基本要求：设计一个算法，并编程找到最快的均分方法；如若用此方法不能得到两份相同的溶剂，请给出“No Way！”的信息。实现提示: 这是一个典型的产生式系统，用图的广度搜索可以求得最佳解。将三个杯子中溶剂的数量状态作为一个结点，从一个杯子往另一个杯子倒溶剂时，状态发生了变化，从前一状态结点到后一状态结点用箭头连接，就得到了状态图，这个图就是数据结构中的图；当x=50,y=30时，得到下面的状态图。 只要搜索到目标状态（40，40，0）时就结束。搜索的过程就是一个产生新结点的过程，需要特别注意的是：产生的新结点一定不能重复，这样就可以构成一棵生成树，避免重复搜索。选题8. 设置棋子布局问题描述：在一个3*3的棋盘上，摆了8个棋子，每个棋子上分别标有1-8的数字，棋盘中留有一个空格，空格周围的棋子可以移到空格中。基本要求：给出一种初始布局和目标布局，找到一种最少的移动方法，实现从初试布局到目标布局的移动。例如：初始布局 目标布局 2 8 3 1 2 3 8 6 4 9 0 4 7 0 5 7 6 5这里0代表空格。实现提示：本题的解法同上题是一样的，每个棋子可以上，下，左，右移动，分别形成不同的状态，构成状态搜索图（树），用队列来记录搜索和产生的过程，从而找到最优解。选题9. 农夫过河问题 问题描述：一个农夫带着一只狼，一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。基本要求：求出农夫将所有的东西运过河的方案。实现提示： 求解这个问题的简单方法是一步一步进行试探，每一步搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。要模拟农夫过河问题，首先需要对问题中每个角色的位置进行描述。一个很方便的方法是用4位二进制数顺序分别表示农夫，狼，白菜和羊的位置。用0表示农夫或者某东西在河的南岸，1表示在河的北岸。例如整数5（其二进制表示为0101）表示农夫和白菜在河的南岸，而狼和羊在北岸。现在问题变成：从初始状态二进制0000（全部在河的南岸）出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111（全部到达河的北岸）为最终目标，并且在序列中的每一个状态都可以从前一状态到达。为避免浪费功夫，要求在序列中不出现重复的状态。实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先搜索，另一种是深度优先搜索。选题 10. 个人书籍管理系统的设计与实现问题描述：学生在自己的学习和生活中会有很多书籍，对所购买的书籍进行分类和统计是一种良好的习惯。可以便于对这些知识资料的整理和查找使用。如果用文件来存储相关书籍的各种信息，包括分类，购买日期，价格，简介等等。辅之以程序来使用这些文件对里面的书籍信息进行统计和查询的工作将使得这种书籍管理工作变得轻松而有趣。简单个人书籍管理系统的开发就是为了解决这个实际问题的。基本要求：这个系统具备如下功能：（1）存储书籍各种相关信息；（2）提供查找功能，按照多种关键码查找所需书籍，查找成功后可以修改记录的相关项。（3）提供排序功能，按照多种关键码对所有书籍排序，例如按照购买日期进行排序。（4） 其他辅助的维护工作。实现提示： 由于书籍的册数较多，而且要在程序不再运行的时候仍然要保持里面的数据，所以采用文件的形式放到外存储器中。需要操作时，从文件中调入内存来进行查找和排序的工作。选题11. 开关盒布线 问题描述：给定一个矩形布线区域，其外围有若干针脚。两个针脚之间通过布设一条金属线路而实现互连。这条线路被称为电线，被限制在矩形区域内。如果两条电线发生交叉，则会发生电流短路。所以，不允许电线间的交叉。每对互连的针脚被称为网组。目标是要确定对于给定的网组，能否合理地布设电线以使其不发生交叉。例：下图（a）有一个布线的例子，其中有8个针脚和4个网组。4个网组分别是（1，4）（2，3）（5，6）（7，8）。如图b给出的布线方案有交叉现象发生（(1,4)和(2,3)交叉），图c则没有交叉现象发生。由于4个网组可以通过合理安排而不发生交叉，因此可称其为可布线开关盒。（在具体实现时，还需要在两个相邻的电线间留出一定的间隔，为使问题简化，本应用中忽略这个额外的要求。） c基本要求：要求给定一个开关盒布线实例，确定它是不是一个可布线的。实现提示：当两个针脚互连时，其电线把布线区分成两个分区。例，当（1，4）互连时，就得到了两个分区，一个分区包含针脚2和3，另一个分区包含针脚58，现在如果有一个网组，其两个针脚分别位于这两个不同的分区，那么这个网组是不可以布线的，因而整个电路也是不可布线的。如果没有这样的网组，则可以继续判断每个独立的分区是不是可布线的。为此，可以从一个分区中取出一个网组，利用该网组把这个分区又分成两个子分区，如果任一个网组的两个针脚都分布在同一个分区之中（即不会出现两个针脚分别位于两个子分区的情形），那么这个分区就是可布线的。选题12. 八皇后问题 问题描述：在一个8*8的棋盘里放置8个皇后，要求每个皇后两两之间不相“冲”（在每一横列竖列斜列只有一个皇后）。基本要求： 输出棋盘布局。实现提示：可以用递归循环来做，分别一一测试每一种摆法，直到得出正确答案。主要解决冲突（包括行，列，两条对角线）问题。（1） 列：规定每一列放一个皇后，不会造成列上的冲突。（2） 行：当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态。（3） 对角线：对角线有两个方向。在同一对角线上的所有点（设下标为（i,j），要么（i+j）是常数，要么(i-j)是常数。因此，当第i个皇后占领了第j列后，要同时把以（i+j）和（i-j）为下标的标记置为被占领状态。五，成绩评定验收成绩：根据实验方案的设计，程序编制，调试结果，实验报告、学习态度等标准打分确定成绩。其中，程序正确性是第一位的，占70%。课程设计报告占15%，其余占15%。采用百分制评分标准。六，参考文献数据结构题集（C语言版） 严蔚敏 吴伟民 清华大学出版社。1999年2月第1版。数据结构经典算法实现与习题解答 汪杰 人民邮电出版社。2004年1月第1版数据结构习题解答与实验指导 罗文劼，王苗，石强，中国铁道出版社，2004年12月第1版。数据结构实验教程王玲，四川大学出版社，2002年10月第1版。附录一、课程设计报告格式附录二、课程设计报告范例一、课程题目二、需求分析简单说明程序要解决什么问题。 三、概要设计确定模块结构，划分功能模块，将软件功能需求分配给所划分的最小单元模块。确定模块间的联系，确定数据结构。四、详细设计 确定每一个模块的算法，内部的数据组织，选定工具清晰正确表达算法。说明本程序中实现的每项功能及其具体要求 五，测试数据及运行结果六，源程序 一、设计题目约瑟夫环问题二、需求分析设编号为1,2,n(n0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限值m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，抱m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数；如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。要求：（1）初始报数上限值m和测试数据在程序中确定；（2）用带头结点的单循环链表作数据元素的存储结构；（3）把带头结点的单循环链表作为抽象数据类型设计。三、概要设计带头结点的单循环链表抽象数据类型SCLinList，其中包括基本操作的函数有：初始化操作函数、插入一个结点操作函数、删除一个结点操作函数、取一个结点数据操作函数和判表是否非空操作函数。该抽象数据类型文件名为SCLinList.h。JesephRing()函数是实现问题要求的主要函数。void SCLLDeleteAfter(SCLNode *p)，其功能是删除带头结点的单循环链表中指针p所指结点的下一个结点。void JesephRing(SCLNode *head, int m)，其功能是对带头结点的单循环链表head,以m为初始报数上限值实现问题要求。void main(void)，主函数，功能是给出测试数据值，建立测试数据值的带头结点单循环链表，调用JesephRing()函数实现问题要求。四、详细设计JesephRing()函数作为主要函数，其算法思想是：从1至m对带头结点的单循环链表循环计数，到m时，输出该结点的编号值，将该结点的密码作为新的m值，再从该结点的下一个结点起重新自1起循环计数；如此下去，直到单循环链表空时循环过程结束。（1）数据类型DataType定义如下：typedef structint number;int cipher; DataType; （2）带头结点单循环链表抽象数据类型SCLinList。（3）带头结点单循环链表抽象数据类型的结点结构定义如下： typedef struct nodeDataType data;struct node *next; SCLNode; 五、测试数据及运行结果测试数据n = 7，七个人的密码依次为3,1,7,2,4,8,4初始报数上限值m = 20 运行结果程序输出为：6 1 4 7 2 3 5六、源程序源程序存放在两个文件中，文件SCLinList.h是带头结点单循环链表抽象数据类型，文件Exam3-9.c是主程序。文件SCLinList.h：typedef struct nodeDataType data;struct node *next; SCLNode; /*结点结构定义*/void SCLLInitiate(SCLNode *head) /*初始化*/if(*head = (SCLNode *)malloc(sizeof(SCLNode) = NULL) exit(1);(*head)-next = *head;int SCLLInsert(SCLNode *head, int i, DataType x) /*插入一个结点*/SCLNode *p, *q;int j;p = head-next; j = 1;while(p != head & j next; j+;if(j != i - 1 & i != 1)printf(插入位置参数错！);return 0;if(q = (SCLNode *)malloc(sizeof(SCLNode) = NULL) exit(1);q-data = x;q-next = p-next;p-next = q;return 1;int SCLLDelete(SCLNode *head, int i, DataType *x) /*删除一个结点*/SCLNode *p, *q;int j;p = head; j = 0;while(p-next != head & j next; j+;if(j != i - 1)printf(删除位置参数错！);return 0;q = p-next;p-next = p-next-next;*x = q-data;free(q);return 1;int SCLLGet(SCLNode *head, int i, DataType *x) /*取一个结点数据元素值*/SCLNode *p;int j;p = head; j = 0;while(p-next != head & j next; j+;if(j != i)printf(取元素位置参数错！);return 0;*x = p-data;return 1;int