数据结构与算法课程设计题目.docx

《数据结构与算法课程设计题目.docx》由会员分享，可在线阅读，更多相关《数据结构与算法课程设计题目.docx（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构与算法课程设计题目 数据结构与算法课程设计 一、课程设计的目的、要求和任务 本课程设计是为了配合数据结构与算法课程的开设，通过设计完整的程序，使学生掌握数据结构的应用、算法的编写等基本方法。 1.课程的目的是： （1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。 （2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。 （3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力； 2.课程的基本要求与任务是： （1）巩固和加深对数据结构基本知识的理解，提高综合运用课程

2、知识的能力。 （2）培养学生自学参考书籍，查阅手册、图表和文献资料的能力。 （3）通过实际课程设计，初步掌握简单软件的分析方法和设计方法。 （4）了解与课程有关的工程技术规范，能正确解释和分析实验结果。 （5）题目具有足够的工作量。 二、课程设计的一般步骤： （1）划分课程设计小组：由不超过5名同学自由组成一个课程设计小组，设组长一名。 （2）选题与搜集资料：每个课程设计小组在参考选题中至少选择3道课题，并保证线性表、栈、队列与递归算法设计和树、图及其应用均有一道； （3）分析与概要设计：根据搜集的资料，进行程序功能与数据结构分析，并选择合适的数据结构、并在此基础上进行实现程序功能的算法设计。

3、 （3）程序设计：运用掌握C+/Java/C#语言编写程序，实现所程序的各个模块功能。 （4）调试与测试：调试程序，并记录测试情况。 （5）完成课程设计报告。 （6）验收与评分：指导教师对每个同学的开发的系统进行综合验收。 三、课程设计报告的规范 课程设计报告（3000字以上，每个题目1000字以上）要求规范书写，应当包括如下8个部分： （1）问题描述：描述要求编程解决的问题。 （2）基本要求：给出程序要达到的具体的要求。 （3）算法思想：描述解决相应问题算法的设计思想。 （4）模块划分：描述所设计程序的各个模块（即函数）功能。 （5）数据结构：给出所使用的基本抽象数据类型,所定义的具体问题的

4、数据类型,以及新定义的抽象数据类型。 （6）源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。 （7）测试数据：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。 （8）测试情况：给出程序的测试情况，并分析运行结果 四、成绩评定标准 学生成绩以优、良、中、及格和不及格5个等级评定。 （1）学生编写的实际软件和运行结果，占总成绩50%； （2）设计报告，占总成绩50%。 五、附课程设计题目 各小组可另选题目，经指导老师认可后正式作为课程设计题目。 Programming Projects 3.5 P1 模拟飞机场 Pr

5、ogramming Projects 4.5 P1 多项式计算器 Programming Projects 5.3 P1 八皇后问题 Programming Projects 7.2 P1 查找算法测试程序 Programming Projects 8.2 P1 排序算法测试程序 Programming Projects 10.2 P2 二叉树演示程序 Programming Projects 10.4 P2 A VL树演示程序 Programming Projects 11.3 P1 B-树演示程序 数据结构课程设计参考题目 类型一线性表、栈、队列与递归算法设计 1约瑟夫环 问题描述 约瑟夫

6、（Joeph）问题的一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 基本要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 测试数据 m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。 实现提示 程序运行后首先要求用户指定初始报数上限值，然后读取各

7、人的密码。设n30。 2、长整数运算 问题描述 设计一个程序实现两个任意长的整数求和运算。 基本要求 利用双项循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是-（215-1）（215-1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。 测试数据 （1）0；0；应输出“0”。 （2）-2345,6789；-7654,3211；应输出“-1,0000,0000”。 （3）-9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。 （4）1,0001,000；-1,0001,0001；应输出“0”。 （5）1,0

8、001,0001；-1,0001,0000；应输出“1”。 实现提示 （1）每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为 万进制数。 （2）可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。 选作内容 修改上述程序，使它在整型量范围是-（2n-1）（2n-

9、1）的计算机上都能有效地运行。其中，n是由程序读入的参量。输入数据的分组方法可以另行规定。 3、多项式链式存储结构及其代数运算 问题描述 设计并建立一个链式存储分配系统来表示和操作多项式。为了避免对零和非零多项式进行不同的处理，使用带头结点的循环链表。为了充分利用多项式中不再使用的结点，维护一个可用空间表avail,把不再使用的多项式的结点链入其中。当需要一个新结点时，就查看这个单链表avail。如果表非空，那么可以使用它的一个结点。只有当该表为空时，才使用动态存储分配来创建新结点。 基本要求 设计多项式的存储结构，编写并测试下列函数： a) get_node和ret_node，从/向可用空间

10、表申请和插入一个多项式结点。 b) pread，读取一个多项式，并将其转换成循环存储表示。返回指向该多项式的头结点的指针。 c) pwrite，输出多项式，采用能够清楚显示的形式。 d) padd，计算d = a+b。不改变a和b。 e) psub，计算d = a-b。不改变a和b。 f) pmult，计算d = a*b。不改变a和b。 g) eval，计算多项式在某点a的值，其中a是一个浮点型常量。返回结果为浮点数。 h) perase，把存储表示为循环链表的多项式返还给可用空间表。 实现提示 为了进一步简化加法算法，把多项式的头结点的指数域设为-1。 4、稀疏矩阵的完全链表表示及其运算 问

11、题描述 稀疏矩阵的每个结点包含down，right，row，col和value五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行内按列序）用right域链接起来。使得第二个表即列表，把所有结点按照列序（同一列内按行序）用down链接起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。 实现一个完全链表系统进行稀疏矩阵运算，并分析下列操作函数的计算时间和额外存储空间的开销。 （2）设计目的 认识和掌握稀疏矩阵的完全链表表示；能够建立并运用这种存储结构 (3) 基本要求

12、建立一个用户友好、菜单式系统进行下列操作，并使用合当的测试数据测试该系统。 读取一个稀疏矩阵建立其完全链表表示 输出一个稀疏矩阵的内容 删除一个稀疏矩阵 两个稀疏矩阵相加 两个稀疏矩阵相减 两个稀疏矩阵相乘 稀疏矩阵的转置 （4）实现提示 链表上的操作。 5、实现简单数字图像处理 问题描述 一幅图像就是一个从位置集到颜色集的变换。考虑二维图像，位置集实际上就是一个矩阵，此时一幅图像实际上就是一个内容为颜色矩阵。如果颜色为0-255间的整数，表示该位置的灰度等级，0为黑色，255为白色，此时的图像称为灰度图。 而图像的处理就是在该矩阵进行相关计算。一种常见的计算就是通过一点和周围8个点的信息共同

13、决定该点的新值：如一点的新值为该点和周围8点颜色值之和的均值，这一操作可用下图表示。 图像平滑模板 显然这样处理后，图像会变得平滑，因此称为平滑操作。显然将上述操作变为下图时，就成为锐化操作。 要求实现若干基本的图像处理操作。 基本要求 熟悉Windows下BMP文件的格式，能够实现其读写(只考虑灰度图像)。 实现图像的平滑和锐化操作，其它处理操作选做。 需用VC+作为语言。 6、回文判断 问题描述 试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，

14、而+&则不是。 实现提示 首先，序列1进栈，然后序列1出栈并与序列2比较。 测试数据 由学生依据软件工程的测试技术自己确定。注意测试边界数据，如序列1和序列2均为空串。 7、商品货架管理 问题描述 商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。 基本要求 针对一种特定商品，实现上述管理过程。 实现提示 用栈模拟货架和周转空间。 测试数据 由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空栈。 8、停车场管理 问题描述 设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场

15、内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 测试数据 设n=2,输入数据为：（A，1，5），（A，2，10），（D，1，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，

16、40），（E，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，A表示到达；D表示离去，E表示输入结束。 基本要求 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。 实现提示 需另设一个栈，临时停放为给要离

17、去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数 据项：汽车的牌照号码和进入停车场的时刻。 9、电梯运行仿真程序 问题描述 办公大楼有若干层（例如，十层），每层有电梯，同时有步行楼梯； 全楼有若干部（例如，不多于10部）电梯同时供使用，电梯容量为24人，速度每上下一层需5秒，在某一层停下至少15秒。其运行状态可分：向上、向下、停止，当前乘客数，当前所在层数。它设有一个“按钮数组”，例如第五层的按钮按下，意味着有乘客在第5层到达目标层，等等。 在楼的每一层，有电梯数，有按钮表示有人等待向上或向下，由若干人在等待，有若干

18、电梯在本层停下，等等。 在大楼中（包括进出）的总人数不超过500 人，每个人站在电梯前有个目标层，他有一个最大的忍受等待时间，因为他可以选择电梯或是步行走楼梯，等等。 还有下面若干假设：在每个时间段要进大楼的人数在0199 之间随机取值； 用电梯的每个人的目标层在110 之间取值；一个人在进电梯或改走楼梯之前的等待时间在180360 秒范围内随机发生；一个人到达目标层后第二次再乘电梯中间的工作时间在4006600 秒间随机取值。 基本要求 编写一个程序，模拟办公大楼中全部电梯的工作过程。这个仿真程序可以用来监测系统运行情况，改善大楼管理，它也可以看成是一种游戏程序。 屏幕显示的布局设计 类型二

19、串及其应用 1、文学研究助手 问题描述 文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。 基本要求 英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。 测试数据 以你的源程序模拟英文小说，程序语言保留字集作为待统计的词汇集。 实现提示 设小说中的词汇一律不跨行。这样，每读入一行，就统计每个词在这行中的出现次数。出现位置所在行的行号可以用链表存储。若某行中出现了不止一次，不必存多个相同的行号。 类型三

20、树、图及其应用 1、二叉树的建立与遍历 问题描述 建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。 基本要求 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。 测试数据 ABCDEGF（其中表示空格字符） 则输出结果为： 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA 选作内容 采用非递归算法实现二叉树遍历。 2、打印二叉树结构 问题描述 按凹入表形式横向打印二叉树结构，即二叉树的根在屏幕的最左边，二叉树的左子树在屏幕的下边，二叉树的右子树在屏幕的上边。 测试

21、数据 由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空二叉树。 3、打印树结构 问题描述 按凹入表形式打印树形结构。 测试数据 由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空树。 实现提示 （1）利用树的先根遍历方法； （2）利用结点的深度控制横向位置。 4、图遍历的演示 问题描述 很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示无向图的遍历操作。 基本要求 以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 测试数据 由学生依据软件工程的测试技术自己确定。注意测

22、试边界数据，如单个结点。 实现提示 设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。 5、学生选课系统 问题描述 大学里实行学分制。每门课都有一定的学分。每个学生均需要修满规定数量的课程才能毕业。其中有些课程可以直接修读，有些课程需要一定的基础知识，必须在选了其他一些课程的基础上才能修读。例如，数据结构必须在选修了程序设计基础之后才能选修。我们称程序设计基础是数据结构的“先修课”。假定每门课的直接先修课至多只有一门，两

23、门课可能存在相同的先修课。例如： 课程号先修课号学分 1 0 1 2 1 1 3 2 3 4 0 3 5 2 4 上例中，1是2的先修课，即如果要选修2，则1必定被选。 基本要求 学生不可能学完大学里开设的所有课程，因此每个学生必须在入学时选定自己要学的课程。每个学生所修的学分数的下限是给定的。现在编写一个“学生选课系统”，任意给定一种课程体系（总课程数，课程之间的修读先后制约关系，学生毕业要求修的课程学分数），该系统能帮助学生找出一种选课方案，使得他所选课程数目最少，并获得毕业所需学分，并且必须满足先修课程优先的原则。 具体功能如下： 1.将课程体系存放为课程体系文件CourseHierar

24、chy.txt ； 2.将课程体系文件CourseHierarchy.txt 转换左孩子右兄弟二叉树表示； 3.在此基础上对二叉树进行先序、中序、后序遍历。 4. 给出选课方案。 6、设计一个哈夫曼码的编/译码系统 基本要求 该系统应具有以下功能： （1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 （2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree 中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile 中。 （3）D：译码（D

25、ecoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 （4）P：打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 （5）T：打印哈夫曼树（Tree printing）。将已在中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。实现提示 （1）编码结果以文本方式存储在文件CodeFile中。 （2）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请

26、用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至 某次用户选择了“Q”为止。 （3）在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能 早已建好。 测试数据 （1）利用下面这道题中的数据调试程序。 某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。 （2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FA VORITE”。 7、校园导游咨询系统 问题描述 设计一个校园导游程序，为来访的客人提供信息查询服务。 基本要求 （1）设计学校的校园平面图，所含景点不少于10个，以图中顶点表示校内各景点，存放景点名称、代号、简介等信息，以边表示路径，存放路径长度等相关信息。 （2）为来访客人提供图中任意景点相关信息的查询； （3）为来访客人提供从校门口到图中任意景点的问路查询；