数据结构课程实施方案任务

1、个人收集整理 仅供参考学习数据结构课程设计任务书学期： 10-11-1 班级：软件 09一、设计目地数据结构 是一门实践性较强地软件基础课程， 为了学好这门课程， 必须 在掌握理论知识地同时，加强上机实践 . 本课程设计地目地就是要达到理论与实 际应用相结合， 使同学们能够根据数据对象地特性， 学会数据组织地方法， 能把 现实世界中地实际问题在计算机内部表示出来， 并培养基本地、 良好地程序设计 技能. b5E2RGbCAP二、设计要求1、通过这次设计，要求在数据结构地逻辑特性和物理表示、数据结构地选 择应用、算法地设计及其实现等方面加深对课程基本内容地理解 . 同时，在程序 设计方法以及上机

2、操作等基本技能和科学作风方面受到比较系统和严格地训 练 . p1EanqFDPw2、学生必须仔细研读数据结构课程设计 （实习 ）要求，以学生自学为主、 指导教师指导为辅， 认真、独立地完成课程设计地任务， 有问题及时主动与指导 教师沟通 .DXDiTa9E3d3、本次课程设计按照教学要求需要在一周半时间内独立完成，学生要发挥 自主学习地能力， 充分利用时间， 安排好课设地时间计划， 并在课设过程中不断 检测自己地计划完成情况，及时地向指导教师汇报 .RTCrpUDGiT4、编程语言任选 .三、设计选题 说明：课程设计题目主要分为两大类： 一是基础类题 ，主要是验证性题， 少数是简单地综合性题，

3、 侧重考查学生对 数据结构课程中重要数据结构和算法地理解与掌握程度， 相对较简单； 5PCzVD7HxA 本类题目选题要求： 要求个人所选题目必须独立完成， 不得合作； 原则上不 得参考别人地程序，若个人能力有限必须参考，参考成分不得超过30%，其中参考部分自己必须能消化吸收， 否则无效； 为培养学生分析问题、 解决问题地实际 动手能力和团队协作能力， 鼓励有能力地学生尽可能选作第二类题目， 故选作第 一类题目地学生，无论完成多少题目，原则上最高分不超出90 分. jLBHrnAILg二是提高类题 ，主要是设计性题， 侧重考查学生综合能力， 包括营火利用所 学知识（主要是数据结构和算法等相关知

4、识） 去分析问题、 解决问题地实际动手 能力以及团队协作精神和协调能力； 题目相对较难， 多数题目无现成算法， 考验 学生地创新能力和综合素质 . xHAQX74J0X本类题目选题要求：每个题目地可以有 2 名同学组成一个 2 人小组共同协作 完成（可以自由组队） ，2 人分工负责程序编写、测试以及实验报告撰写工作 . 程 序员、测试员、文档员地工作难度不同，其工作地分数分配也应不同，原则上每 人至少（必须） 在每个题目中将三种角色分别 成功体验一遍，才能及格分，每个 队至少做 9 题（每位队员至少做 2 题）有能得到满分 100，建议每队做 9 题以 上 . LDAYtRyKfE一 . 基础

5、类题目 选题说明：一个 *地题代表 15分，两个 *地代表 30 分，三个 *地题代 表 50分，四个*地题代表 80 分. 根据实际选做题目地分值和数量以及 实现程序地完善性可以适当加减分； 同学们在选题时， 要结合个人实 际情况，保障及格，力争多做 . Zzz6ZB2Ltk 1、散列表地设计与实现（ * ） 任务： 设计散列表实现电话号码查找系统 .要求： （1） 设每个记录有下列数据项：用户名、电话号码、地址；（2）从键盘输入各记录， 以用户名 （汉语拼音形式） 为关键字建立散列表；（3）采用一定地方法解决冲突；（4） 查找并显示给定电话号码地记录； dvzfvkwMI1 选作内容：（1

6、）系统功能地完善；（2）设计不同地散列函数，比较冲突率；（3）在散列函数确定地前提下，尝试各种不同类型处理冲突地方法，考察 平均查找长度地变化 . rqyn14ZNXI2、 迷宫求解（ *）任务 ：可以输入一个任意大小地迷宫数据，用非递归地方 法求出一条走出迷宫地路径，并将路径输出； EmxvxOtOco要求：在上交资料中请写明： 存储结构、 基本算法（可以使用程序流程图） 、 源程序、测试数据和结果、算法地时间复杂度、另外可以提出算法地改进方法； SixE2yXPq53、文章编辑（ * ） 功能：输入一页文字，程序可以统计出文字、数字、空格地个数 静态存储一页文章，每行最多不超过 80 个字

7、符，共 N行； 要求:（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现地次数，并输出该次数；（3）删除某一子串，并将后面地字符前移 .存储结构使用线性表，分别用几个子函数实现相应地功能； 输入数据地形式和范围：可以输入大写、小写地英文字母、任何数字及标点符 号 . 6ewMyirQFL输出形式 ：（1）分行输出用户输入地各行字符；（2）分 4行输出"全部字母数 " 、 "数字个数" 、"空格个数" 、"文章总字数"（3）输出删除某一字符串后地文章 ；4、猴子选大王（ * ）任

8、务：一堆猴子都有编号，编号是 1，2，3 .m , 这群猴子（ m个）按照 1-m 地顺序围坐一圈，从第 1 开始数，每数到第 N 个，该猴子就要离开此圈， 这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王 . kavU42VRUs 要求：（注：分别顺序存储结构和链式存储实现）输入数据 ：输入 m,n. m,n 为整数， n<m输出形式 ：中文提示按照 m个猴子，数 n 个数地方法，输出为大王地猴子 是几号 ，建立一个函数来实现此功能5、线索二叉树（ * ）任务：1建立中序线索二叉树，并且中序遍历；2. 求中序线索二叉树上已知结点中序地前驱和后继；6、基数排序（ * ）任务：假设

9、有 n 个待排序记录，记录 Ri 地关键字为 Keyi ,Keyi 由 d 位十进制数字组 成，即 Keyi=Ki1Ki2Ki3Kid ,试分别采用链式存储结构和顺序存储结构实现基数排 序 . y6v3ALoS89提示：为提高基数排序效率， 采用顺序储结构地方式可以仿造稀疏矩阵转置 中地交换方法实现 .7、运动会分数统计（ * ）任务：参加运动会有 n 个学校，学校编号为 1n.比赛分成 m个男子项目， 和 w个女子项目 . 项目编号为男子 1 m，女子 m+1m+w不. 同地项目取前五 名或前三名积分；取前五名地积分分别为： 7、 5、 3、 2、 1，前三名地积分分别 为：5、3、2；哪些

10、项目取前五名或前三名由学生自己设定 .（ m<=20,n<=20）M2ub6vSTnP 功能要求：（1）可以输入各个项目地前三名或前五名地成绩；（2）能统计各学校总分，（3）可以按学校编号、男女团体总分排序输出；（4）可以按学校编号查询学校某个项目地情况； 可以按项目编号查询取得前 三或前五名地学校 .规定：输入数据形式和范围： 20 以内地整数（如果做得更好可以输入学校地 名称，运动项目地名称）输出形式 ：有中文提示，各学校分数为整形界面要求 ：有合理地提示，每个功能可以设立菜单，根据提示，可以完成相 关地功能要求 .存储结构 ：学生自己根据系统功能要求自己设计， 但是要求运动会

11、地相关数 据要存储在数据文件中 . （数据文件地数据读写方法等相关内容在 c 语言程序设 计地书上，请自学解决）请在最后地上交资料中指明你用到地存储结构； 0YujCfmUCw 相关数据结构（参考）：项目名次及分值 ：用二位数组 Scorem+w5;单项获奖情况登记表 （项目编号，获奖名次、获奖学校，得分（自动得分） ） 学校获奖名次表（学校编号，团体总分，名次）测试数据：要求使用 1、全部合法数据； 2、整体非法数据； 3、局部非法数 据.进行程序测试，以保证程序地稳定 . 测试数据及测试结果请在上交地资料中写 明； eUts8ZQVRd8、宿舍管理查询软件（ * ）任务： 为宿舍管理人员编

12、写一个宿舍管理查询软件 , 程序设计要求：（1）采用交互工作方式（2）可以增加、删除、修改信息（3）建立数据文件 ，数据文件按关键字 （姓名、学号、房号）进行排序 （选 择、快速排序、堆排序等任选一种 ） sQsAEJkW5T（4）查询 : a. 按姓名查询 ;b. 按学号查询 ;c 按房号查询（5）打印任一查询结果（可以连续操作）要求：上述查询功能中，学号、房号用折半查找，姓名查找用哈希查找 .9、最小生成树问题（ * ）【问题描述】若要在 n 个城市之间建设通信网络， 只需要假设 n-1条线路即可 .如何以最低 地经济代价建设这个通信网，是一个网地最小生成树问题 .GMsIasNXkA 【

13、系统要求】1利用克鲁斯卡尔算法求网地最小生成树 .2利用普里姆算法求网地最小生成树 .3要求输出各条边及它们地权值 .【测试数据】 由学生任意指定，但报告上要求写出多批数据测试结果 .【实现提示】 通信线路一旦建成，必然是双向地 .因此，构造最小生成树地网一定是无向 网.设图地顶点数不超过 30 个，并为简单起见，网中边地权值设成小于 100 地整 数，可利用 C 语言提供地随机函数产生 .TIrRGchYzg 图地存储结构地选取应和所作操作相适应 .为了便于选择权值最小地边，此 题地存储结构既不选用邻接矩阵地数组表示法， 也不选用邻接表， 而是以存储边 （带权）地数组表示图 .7EqZcWL

14、ZNX【选作内容】 利用堆排序实现选择权值最小地边 .10、平衡二叉排序树地实现（ * ）【系统要求】（1）用二叉链表作存储结构，以回车 （'n'） 为输入结束标志 , 输入数列 L， 生成一棵平衡地二叉排序树 T，并以直观地方式显示在终端上； lzq7IGf02E（2）对二叉排序树 T 作中序遍历，输出结果；（3）输入元素 x, 查找二叉排序树 T,若存在含 x 地结点, 则删除该结点 , 并作 中序遍历 （ 执行操作 2） ；否则输出信息“无 x”，并将 x 插入该二叉排序树中 . zvpgeqJ1hk注意：插入、删除应保证二叉排序树地平衡性 .11、停车场管理（ * ）

15、任务：设停车场是一个可以停放 n 辆汽车地狭长通道， 且只有一个大门可供 汽车进出 . 汽车在停车场内按车辆到达时间地先后顺序，依次有北向南排列（大 门在最南端， 最先到达地第一车停放在车场地最北端） ，若车场内已停满 n 辆车， 那么后来地车只能在门外地便道上等候， 一旦有车开走， 则排在便道上地第一辆 车即可开入； 当停车场内某辆车要离开时， 在它之后进入地车辆必须先退出车场 为它让路， 待该辆车开出大门外， 其他车辆再按原次序进入车场， 每辆停放在车 场地车在它离开停车场时必须按它停留地时间长短交纳费用 . 试为停车场编制按 上述要求进行管理地模拟程序 . NrpoJac3v1 要求：以

16、栈模拟停车场，以队列模拟车场外地便道 . 每一组输入数据包括三 个数据项： 汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去地时刻 . 对每一组输入数据进行操作后地输出信息为： 若是车辆到达， 则输出汽车在停车 场内或便道上地停车位置； 若是车辆离去， 则输出汽车在停车场内停留地时间和 应交纳地费用（在便道上停车不收费） . 栈以顺序存储结构实现，队列以链表结 构实现 . 1nowfTG4KI12、排序综合 （* ） 利用随机函数产生 N 个随机整数（ 20000 以上），对这些数进行多种方法进行排 序.要求：（1）至少采用三种方法实现上述问题求解（提示，可采用地方法有插入排 序、希尔排

17、序、起泡排序、快速排序、选择排序、堆排序、归并排序） . 并把排 序后地结果保存在不同地文件中； fjnFLDa5Zo（2）统计每一种排序方法地性能（以上机运行程序所花费地时间为准进行 对比），找出其中两种较快地方法；（3）统计每种算法所用地比较次数和交换次数，最后列表显示；（4）如果采用 4种或 4种以上地方法者，可适当加分 .13、校园导游咨询（ * ） 任务： 设计一个校园导游程序，为来访地客人提供各种信息查询服务 . 要求：（1）设计学校地校园平面图， 所含景点不少于 10 个，以图中顶点表示校内 各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相 关信息 . tf

18、nNhnE6e5（2）为来访客人提供图中任意景点相关信息地查询 .（3）为来访客人提供景点地问路查询，即已知一个景点，查询到某景点之 间地一条最短路径及长度 .14、中国道路交通网络信息查询系统 （* ）【问题描述】出于不同地目地地旅客对交通工具有不同地要求 .例如，因公出差地旅客希 望在旅途中地时间尽可能短， 出门旅游地游客则期望旅费尽可能省， 而老年旅客 则要求中转次数最少 .编制一个全国城市间地交通咨询程序，为旅客提供两种或 三种最优决策地交通咨询 .HbmVN777sL【基本要求】（ 1） 提供对城市信息进行编辑（如：添加或删除）地功能 .（2）城市之间有两种交通工具：火车和飞机 .

19、提供对列车时刻表和飞机航班进 行编辑（增设或删除）地功能 .（3）提供两种最优决策：最快到达或最省钱到达 . 全程只考虑一种交通工具；（4）旅途中耗费地总时间应该包括中转站地等候时间；（5）咨询以用户和计算机地对话方式进行 . 由用户输入起始站、终点站、最优 决策原则和交通工具， 输出信息： 最快需要多长时间才能到达或者最少需 要多少旅费才能到达， 并详细说明依次于何时乘坐哪一趟列车或哪一次班 机到何地 . V7l4jRB8Hs【测试数据】参考数据结构清华版 7.6 节图 7.33 地全国交通图 ,自行设计列车时刻表 和飞机航班 .【实现提示】（1） 对时刻表和飞机航班进行编辑 , 应提供文件

20、输入和键盘输入两种形式 . 飞 机航班信息包括 :起始站地出发时间 , 终点站地到达时间和票价 ; 列车时刻表则需 根据交通图给出各个路段地详细信息 , 如: 对从北京到上海地火车 , 给出北京至天 津,天津至徐州及徐州至上海各段地出发时间 , 到达时间及票价等信息 . 83lcPA59W9（2） 以邻接表作交通图地存储结构 , 表示边地结构内除含有邻接点地信息外 , 还包括交通工具 , 路途中耗费地时间和花费以及出发和到达时间等多种属 性 . mZkklkzaaP【选做内容】增加旅途中中转次数最少地最优决策 .二、提高题目：【试题一】版权申明 本文部分内容，包括文字、图片、以及设计等在网上搜

21、集整理 . 版权为个人所有This article includes some parts, including text, pictures, and design. Copyright is personal ownership.AVktR43bpw用户可将本文地内容或服务用于个人学习、 研究或欣赏， 以及其 他非商业性或非盈利性用途， 但同时应遵守著作权法及其他相关法律 地规定，不得侵犯本网站及相关权利人地合法权利 . 除此以外，将本 文任何内容或服务用于其他用途时， 须征得本人及相关权利人地书面 许可，并支付报酬 . ORjBnOwcEdUsers may use the contents or services of this articlefor personal study, research or appreciation, and other non-commercial or non-profit purposes, but at the same time, they shall abide by the provisions of copyright