《周《数据结构》课程设计任务书》由会员分享，可在线阅读，更多相关《周《数据结构》课程设计任务书（9页珍藏版）》请在金锄头文库上搜索。
1、沈 阳 工 程 学 院课程设计任务书课课程程设计题设计题目：目： 数据结构与算法课程设计 系系 别别 信息工程系信息工程系 班班级级 学生姓名学生姓名 学号学号 指指导导教教师师 职职称称 课课程程设计进设计进行地点：行地点： 任任 务务 下下 达达 时时 间间： ： 年年 月月 日日起止日期：起止日期： 年年 月月 日起日起至至 年年 月月 日止日止教教研研室室主主任任 年年 月月 日日批批准准一、课程设计的原始资料及依据一、课程设计的原始资料及依据数据结构与算法课程设计是在完成数据结构理论课程学习之后进行的一个综合性的实践教学环节，是对课程理论和课程实验的一个补充。通过课程设计，培养学生综
2、合运用已学过的理论和技能去分析和解决实际问题的能力，并使所学知识得到进一步巩固、深化和扩展。二、课程设计主要内容及要求二、课程设计主要内容及要求设计内容：设计内容： 1、 设有一元素为整数的线性表 L=(a1,a2,a3,an),存放在一维数组 AN中,设计 一个算法,以表中 an 作为参考元素,将该表分为左、右两部分,其中左半部分 每个元素小于等于 an,右半部分每个元素都大于 an, an 位于分界位置上(要求 结果仍存放在 AN中)。 2、 设线性表存于 A1.size的前 num 各分量中，且递增有序。请设计一个算法， 将 x 插入到线性表的适当位置上，以保持线性表的有序性。 3、 线
3、性表(a1,a2,a3,an)中元素递增有序且按顺序存储于计算机内。要求设计 一算法完成： 4、 用最少时间在表中查找数值为 x 的元素。 5、 若找到将其与后继元素位置相交换。 6、 若找不到将其插入表中并使表中元素仍递增有序。 7、 已知数组 A0:n-1的元素类型为 int，试设计算法将其调整为左右两个部分， 左边所有元素为奇数，右边所有元素为偶数。 8、 设计一个算法从顺序表 L 中删除所有值为 x 的元素 9、 设计一个算法从顺序表 L 中删除所有值为 x 到 y 之间（x(以其中之一为 0 标志结束),对于每条 这样的边,申请一个结点,并插入到的单链表中,如此反复,直到将图中所有边
4、处理完毕。提示：先产生邻接表的 n 个头结点（其结点数值域从 1 到 n） 。67、给出以十字链表作存储结构，建立图的算法，输入(i,j,v)其中 i,j 为 顶点号，v 为权值。 68、设有向 G 图有 n 个点(用 1,2,n 表示),e 条边,写一算法建立有向图 的逆邻接表。 69、设已给出图的邻接矩阵，要求将图的邻接矩阵转化为邻接表，试实现其 算法。 70、编写算法，将图的邻接矩阵存储改为邻接表的存储。 71、试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点 Vi到 顶点 Vj的路径（ij） 。 72、已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。 73、假设有向
5、图以邻接表存储，试编写算法删除弧的算法。 7474、假设有向图以十字链表存储，试编写算法，插入弧。 75、设有向图用邻接表表示,图有 n 个顶点,表示为 1 至 n,试写一个算法求 顶点 k 的入度(10)个人按顺时针方向围 坐一圈，每个人持有一个正整数密码。开始时任选一个正整数作为报数上限 m，从第一个人开始顺时针方向自 1 起顺序报数，报到 m 是停 止报数，报 m 的人出列，将他的密码作为新的 m 值，从他的下一个人 开始重新从 1 报数。如此下去，直到所有人全部出列为止。令 n 最大 值取 30。要求设计一个程序模拟此过程，求出出列编号序列。 90、表达式求值（） 问题描述：从键盘上输
6、入中缀算数表达式，计算出表达式的值。 基本要求： 1. 程序对所输入的表达式做简单的判断，如果表达式有错，能给出适 当的提示。 2. 能处理+、 这四种基本的算术运算符。 91、求图的中心点（） 问题描述：假设有一个公司在某个地区有 n 个产品销售点，现根据业 务需要打算在其中某个销售点上建立一个中心仓库负责向其他销售点 提供产品。由于运输路线不同，运输费用也不同。假定每天需要向每 个销售点运输一次产品，那么应将中心仓库建在哪个销售点上才能使 运输费用最低。 92、集合的交、并和差运算的实现（） 问题描述：用有序单链表表示集合，实现集合的交、并、差运算 基本要求： 空间复杂度为 O(1) 93
7、、单链表实现十进制大整数运算（） 问题描述：使用单链表实现不限大小的整数，每个结点存储一位数字， 要求实现加、减运算。即能从键盘上输入两个大整数，比如： 12345123451234512345 和-11111111111111111111，则加的结果应为： 01234012340123401234；减的结果应为：23456234562345623456。 基本要求： 从键盘上输入运算数和运算符，输出结果。 94、哈夫曼编码（） 问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短 信息传输时间，降低传输成本。这就要求在发送端通过一个编码系统 对待传数据预先编码,在接收端将传来的数据进
8、行译码。对于双工信道 (即可以双向传输信息的信道)，每端都需要一个完成的编译码系统。 试为这样的信息收发站写一个哈夫曼的编译码系统。 基本要求： 1. 初始化。从终端读入字符集大小 n，以及 n 个字符和 n 个权值， 建立哈夫曼树。 2. 编码。利用已建好的哈夫曼树,对正文进行编码。 3. 译码。对编码好的内容进行译码。 4. 打印编码。 95、稀疏矩阵运算器（） 问题描述：实现两个稀疏矩阵的加、减、乘运算。 基本要求：可用三元组顺序表存储稀疏矩阵，矩阵的运算结果以通常 的阵列形式输出。 96、校园导游程序（） 问题描述：用无向图表示你所在学校的景点平面图，图中顶点表示主 要景点，存放景点的
9、编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等消息。 基本要求： 1. 能查询各景点的相关信息 2. 为来访客人提供景点的问路查询，即已知一个景点，查询到 某景点之间的一条最短路径及长度。 97、八皇后问题（） 问题描述：八皇后问题，是一个古老而著名的问题，是回溯算法的典 型例题。该问题是十九世纪著名的数学家高斯 1850 年提出：在 88 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后 都不能处于同一行、同一列或同一斜线上。 基本要求：统计总共有多少种摆法，并以一定方式输出摆好的格局。 98、平衡二叉树操作演示（） 问题描述：利用平衡二叉树实现动态查找表。 基
10、本要求：设计平衡二叉树实现动态查找表的操作演示。 （1）实现动态查找表的三种基本功能：查找、插入、删除。 （2）合并两棵平衡二叉树。 （3）分解两棵平衡二叉树。 99、设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相 等的整数存在） ，试编写能实现下列功能的算法 ：（要求用最少的时间和 最小的空间） （） (1)确定在序列中比正整数 x 大的数有几个（相同的数只计算一次，如序列 20,20,17,16,15,15,11,10,8,7,7,5,4中比 10 大的数有 5 个） ； (2) 在单链表将比正整数 x 小的数按递减次序排列； (3) 将正整数比 x 大的偶数从单链表中删除
11、。设计要求：设计要求：(1)每名同学任选三题；标号的题为选做题，完成有加分；(2)学生应明确设计任务和要求，并拟定设计计划，按时完成；(3)设计分阶段进行，每一阶段的设计没有原则错误时才能允许进行下一阶段设计；(4)设计过程中，提倡独立思考、深入钻研，主动地、创造性地进行设计；(5)要求设计态度严肃认真、有错必改。三、对课程设计说明书撰写内容、格式、字数的要求三、对课程设计说明书撰写内容、格式、字数的要求1课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设 计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解 决方法、设计总结、参考文献等。一般不应少于 3000 字
12、。 2在适当位置配合相应的实验原理图、功能模块图、算法流程图等图表进 行说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。 3设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过 课程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。 4课程设计说明书手写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用 A4 纸，页边距均为 20mm，正文采用宋 体小四号字，行间距 18 磅。文中大标题采用黑体小三号字，一级节标题采用黑 体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。 5课程设计说明书装订顺序为：封面、任务书、成绩评定表、
13、目录、正文、 参考文献。四、设计完成后应提交成果的种类、数量、质量等方面的要求四、设计完成后应提交成果的种类、数量、质量等方面的要求1完成“任务书”中指定的功能，运行结果正确。 2课程设计报告。五、时间进度安排五、时间进度安排顺序阶段日期计 划 完 成 内 容备注1第 1 天阅读资料及系统分析设计2第 2-5 天程序编制3第 6-7 天程序调试4第 8-9 天成绩评定5第 10 天书写课程设计说明书六、主要参考资料（文献）六、主要参考资料（文献）1数据结构 ，清华大学出版社，2001，严蔚敏 吴伟民 2数据结构题集 ，清华大学出版社，1999，严蔚敏 吴伟民 3数据结构习题与解析 ，清华大学出版社，2006，李春葆4数据结构 ，高等教育出版社，2006，许卓群5数据结构习题解析 ，清华大学出版社，2011，殷人昆
