数据结构与算法专业课程设计专题计划书.doc

计算机科学和工程学院集中性实践教学计划书( - 年第二学期课程名称:数据结构和算法课程设计专业:计算机科学和技术软件工程、网络工程班级:计算机科学和技术101-6软件工程101-4网络工程101-4课程责任人:李锡祚、王玲芬、李威指导老师分配情况:专业指导老师计算机科学和技术李威、李笑牛、张恒博、云健、刘爽、包书哲软件工程王玲芬、王鹏杰、王存睿、孙世昶、网络工程李锡祚、姜楠、王晓强、王波教学起止周:第1 至3 教学周一、教学目标和要求:数据结构和算法课程设计目标是使同学们能够依据数据对象特征,合理组织数据并能综合利用数据结构和算法基础知识和程序设计基础知识处理实际问题,培养基础、良好程序设计技能。二、关键阶段、内容、时间及地点安排(以天为单位计:阶段和内容第1阶段:指导老师部署设计任务并解析相关题目标设计指标和任务具体内容,学生选择题目,明确问题描述和要求,查阅资料。(1天;各班长或学习委员将本班选题表交给教导老师,一人一题,每道题选择人数标准上不能超出3人,第一天课程设计结束后,每名学生全部要确定题目。第2阶段:明确题目要求、确定数据结构、设计算法,编写程序、调试程序、测试程序(11天;第一周,学生应明确题目要求、确定数据逻辑结构和存放结构、实现基础操作编码和调试、实现主菜单。第二周,完成关键算法设计、编码和调试。第三周,完成剩下任务编码和调试,准备足够测试数据,对软件进行测试和调试。第3阶段:完成设计任务,准备验收、答辩(1天;第4阶段:答辩(上机演示,回复老师提问(1天;第5阶段:撰写课程设计汇报(2天。地点和时间地点:金石滩校区图书馆时间:计算机科学和技术:课程设计上机时间表周一周二周三周四面五第一周早晨、下午早晨第2大节、下午第二周早晨、下午早晨第2大节、下午第三周早晨、下午早晨第2大节、下午(验收软件工程:课程设计上机时间表周一周二周三周四面五第一周早晨、下午早晨、下午下午第二周早晨、下午早晨、下午下午第三周早晨、下午早晨、下午下午(验收网络工程:课程设计上机时间表周一周二周三周四面五第一周早晨、下午早晨下午早晨第二周早晨、下午早晨下午早晨第三周早晨、下午早晨下午早晨(验收注:早晨8:3011:10下午1:404:20三、课程设计题目及具体要求:1.成绩管理问题描述:给出n个学生考试成绩表,成绩表包含学生学号、姓名、考试成绩(高等数学、英语、物理,设计一个简单成绩管理程序。基础要求:(1建立成绩表,能够插入、删除、修改学生成绩统计;(2按任一单科成绩排序;(3 计算每名学生平均成绩;(4 统计任一单科成绩不及格学生人数, 输出不及格人数及不及格学生名单(5 依据平均成绩将成绩表按由高到低次序排列,统计每名学生在考试中取得名次,分数相同为同一名次,按名次输出成绩表。(6 成绩表保留在文件中, 能够从文件读取数据。测试数据:学生能够依据自己班级考试成绩单,任意截取一部分做为测试数据提升要求:成绩表用链式结构表示,实现上述全部要求。考评要求:(1用次序结构表示成绩单,完成任务(1(6,成绩为及格;(2用链表表示成绩单,完成任务(1(6,且软件容错能力强,成绩为中等2.一元多项式简单计算问题描述:设计一个简单一元多项式计算器。基础要求:(1输入并建立多项式;(2输出多项式;(3两个多项式相加,输出结果多项式;(4两个多项式相减,输出结果多项式。测试数据:可任意选择两个一元多项式,能够是通常多项式,也能够是稀疏多项式。提升要求:能够依据输入变量值,计算出多项式结果,且算法效率高。考评要求:(1用链表表示多项式,完成任务(1(4,成绩为及格(2满足考评(1要求,同时能够输入变量值,计算出多项式结果,成绩中等,尤其注意不能用XN计算,不然等同于没有完成提升要求。3.舞伴问题问题描述:一班有m个女生、n个男生(m不等于n, 举行一场舞会. 男女生分别编号坐在舞池两边椅子上,每曲开始时, 依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等候下一曲找舞伴,设计一个程序模拟舞伴配对过程。基础要求:输入男、女学生姓名、性别,由程序自动为男女生编号,能够次序编号,也能够随机编号,输出每曲配对情况(包含男、女生姓名、性别和编号。原始数据和结果数据要保留到文件中。测试数据:分别选择男生多于女生、女生多于男生、男女生相等三组测试数据提升要求:计算出任意一位男生(编号为X和任意一位女生(编号为Y, 在第K曲配对跳舞情况。考评要求:(1用队列表示男、女学生,能够从文件中读取数据,文件中最少包含三组测试数据,分别为男生多于女生、女生多于男生、男女生人数相等。次序输入舞曲编号,对于每支舞曲,输入配对跳舞男、女学生信息。并把本支舞曲配对情况保留到文件中。完成上述任务,成绩为及格。(2在完成考评要求(1基础上,直接输出第K支舞曲配对情况,能够处理异常,如文件空、只有男生或只有女生等。成绩为中等。4.文学研究助手(*问题描述:文学研究人员需要统计某篇英文小说中一些形容词出现次数和位置。试写一个实现这一目标文字统计系统,称为“文学研究助手”。基础要求:英文小说存于一个文本文件中,待统计词聚集合要一次输入完成,即统计工作必需在程序一次运行以后就全部完成。文本文件名和待统计词汇从键盘输入,程序输出结果是每个词出现次数和出现位置所在行行号,格式自行设计, 结果保留到文件中。提升要求:包含是否区分大、小写两种匹配模式,且让用户选择。测试数据:以你C/C+/JAVA源程序模拟英文小说,对应语言保留字集作为待统计词聚集。考评要求:(1用线性结构表示文本文件和待统计单词,动态分配内存,完成基础要求功效,成绩为中等。(2在完成基础要求基础上,完成提升要求,且用户界面友好,能够处理异常,成绩为良好。5.哈希表设计和实现(*问题描述:针对某个单位电话号码簿,设计一个哈希表,并完成对应建表和查表程序。基础要求:设每个统计有下列数据项:电话号码、用户名、住址。从键盘输入各统计,以用户名为关键字建立哈希表,哈希函数用除留取余数法结构,采取线性探测法处理冲突。能够插入、查找、删除并显示给定用户名统计,并计算查找长度, 哈希表保留到文件中,并能从文件中读取数据。测试数据:取某个单位电话号码簿中30个统计。提升要求:(1将电话号码薄以文件形式保留到盘上,能够按用户名和电话号码两种形式建立哈希表并实现插入、查找、删除表中元素功效。(2对于相同哈希函数,采取两种或两种以上处理冲突方法,如线性探测法和拉链法,比较不一样处理冲突方法平均查找长度改变。测试时,采取同一组测试数据,分别用不一样方法处理冲突,统计并输出各自平均查找长度。(3设计图形用户界面考评要求:(1能够从键盘和文件输入原始数据,能够把改变哈希表重新写回到文件中,同时完成其它基础要求,成绩为中等。(2达成提升要求中(1或(2,或同时达成(1和(2,成绩为良好。(3用C+或MFC实现图形用户界面,成绩为良好6.管道铺设施工最好方案(*问题描述:需要在某个城市n个小区铺设管道,则在这n个小区之间铺设n-1条管道即可,假设任意两个居民区之间全部能够架设管道,但因为地理环境不一样,所需经费不一样,选择最优施工方案使总投资尽可能少。基础要求:输入表示小区间关系图及每条管道权值,选择出n-1条管道, 使总投资最小。图信息输入一次后, 保留到文件中, 选择n-1条管道输出到显示器同时, 也保留于文件中。测试用例:任意选择一个图,模拟小区间可能铺设管道及费用。提升要求:(1显示原始图及选择n-1条管道后图。(2用两种以上算法找到最小生成树。(3设计图形用户界面考评要求:(1注意,本题要求能够从键盘和文件中读取原始图数据,且选择出最好方案也要保留到文件中,假如不能达成这个要求,成绩为不及格。完成基础要求,成绩为中等。(2达成提升要求中(1或(2,或同时达成(1和(2,成绩为良好。(3 用C+或MFC实现图形用户界面,实现友好图形用户界面,成绩为良好7.安排教学计划(*问题描述:大学每个专业全部要制订教学计划。假设任何专业全部有固定学习年限,每年含两个学期,每学期时间长度和学分上限值均相等。每个专业开设课程全部是确定,而且课程在开设时间安排上必需满足先修关系。每门课程有哪些先修课程是确定,能够有任意多门,也能够没有。每门课程恰好占一个学期。试在这么前提下设计一个教学计划编制程序。基础要求:输入参数包含学期总数,一学期学分上限,每门课程课程号、学分和直接先修课课程号;许可两种策略,一是使学生在各学期学习负担尽可能均匀,二是使课程尽可能集中在前多个学期;若依据给定条件问题无解,则汇报合适信息,不然输出教学计划表(如每个学期所开设课程课程号及学分,同时将教学计划输出到用户指定文件中。教学计划表格格式自行设定, 能够从键盘读取数据也能够从文件读取数据, 结果保留到文件中。测试数据:学期总数为6,学分上限为10,该专业共开设12门。以10级某专业必修课和选修课为例,选择12门课程及对应学分,制订一个表明各门课程前后约束关系有向图。提升要求:产生多个不一样方案,并使方案之间差异尽可能地大。考评要求:(1达成基础要求,成绩为良好,假如不能把结果保留到文件中,成绩为不及格。(2在达成基础要求基础上,产生3种以上处理方案,且用户界面友好,成绩为优异。8.计算表示式值(*问题描述:对于给定一个表示式,表示式中能够包含常数、算术运行符(“+”、“-”、“*”、“/”和括号,编写程序计算表示式值。基础要求:从键盘输入一个正确中缀表示式,将中缀表示式转换为对应后缀表示式,计算后缀表示式值。测试数据:任意选择一个符合题目要求表示式。提升要求:(1对于表示式中简单错误,能够给出提醒;(2不仅提醒错误,也能给犯错误信息(3表示式中能够包含单个字母表示变量(4能够处理多个操作符(5实现包含简单运算计算器(6实现一个包含简单运算和函数运算计算器考评要求:(1表示式中数据能够是整数或小数,达成基础要求,成绩为良好。假如仅能处理个位数,成绩为及格,假如仅能处理整数,成绩为中等。(2在达成基础要求基础之上,假如达成提升要求2项或以上,成绩能够为优异。激励设计图形用户界面。9.设计Huffman 编码器和解码器(*问题描述:利用哈夫曼编码进行信息通讯能够大大提升信道利用率,缩短信息传输时间,降低传输成本。不过,这要求在发送端经过一个编码系统对待传输数据预先编码;在接收端将传来数据进行译码。对于双工信道(即能够双向传输信息信道,每端全部需要一个完整编/译码系统。试为这么信息收发站编写一个哈夫曼码编/译码系统。基础要求:依据某字符文件统计字符出现频度,结构Huffman 树,编制Huffman编码,并将给定字符文件编码,生成编码文件;再将给定编码文件解码,生成字符文件。(要求按二进制位表示编码提升要求:改善Huffman编码,产生两种以上编码方案,对同一组测试数据,用不一样编码方案编码,从文件长度、算法复杂度等方面进行比较。测试数据:英文文档文件或汉字文档文件。考评要求:(1对原文件编码后,保留到新建文件中,将原文件和新文件比较,假如新文件长度大于原文件,则编码失败,成绩不及格。假如达成题目标基础要求,成绩为良好。(2达成提升要求,成绩能够为优异。10.银行业务模拟(*问题描述:设银行有四个服务窗口,一个等候队列, 每个窗口均能够办理存款、取款、挂失、还贷业务,每种业务所需服务时间不一样,用户抵达银行后,先到打号机上打号,号票上包含抵达时间、编号和需要办理业务,然后在银行内等候, 当任一服务窗口空闲时,处理等候用户中排在最前面用户业务。写一个上述银行业务模拟系统,经过模拟方法求出用户在银行内逗留平均时间和每个窗口办理用户数及办理每种业务数。基础要求:每个用户抵达银行时间和需要办理业务随机产生,输出一天用户在银行平均逗留时间和每个窗口天天办理用户数和每种业务数。提升要求:设计图形用户界面,模拟中国银行真实打号机操作界面,当用户选择一个业务后,要提醒用户排在前面人数。测试数据:营业时间为8小时,其它模拟量自行设定。考评要求:(1数据结构选择合理,达成题目标基础要求,成绩为良好。(2达成提升要求,用户界面友好,能够处理异常,成绩能够为优异11.程序源代码相同性(*问题描述:对于两个C+语言源程序代码,用哈希表方法分别统计两个程序中使用C+语言关键字情况,并最终按定量计算结果,得出两份程序相同性。基础要求:建立C+语言关键字哈希表,统计在每个源程序中C+关键字出现频度, 得到两个向量X1和X2,经过计算向量X1和X2相对距离来判定两个源程序相同性。比如:关键字 Void Int For Char if else while do break class程序1关键字频度 4 3 0 4 3 0 7 0 0 2程序2关键字频度 4 2 0 5 4 0 5 2 0 1X1=4,3,0,4,3,0,7,0,0,2X2=4,2,0,5,4,0,5,2,0,1设s是向量X1和X2相对距离,s=sqrt( (x i1-x i2 2 ,当X1=X2时,s=0, 反应出可能是同一个程序;s值越大,则两个程序差异可能也越大,分析计算结果,给出相同度结论。测试数据: 选择若干组编译和运行全部无误C+程序,程序之间有相近和差异大,用上述方法求s, 对比两个程序相同性。提升要求:建立源代码用户标识符表,比较两个源代码用户标识符出现频度,综合关键字频度和用户标识符频度判定两个程序相同性。考评要求:从源代码中分解单词,判定是否为关键字要采取效率高方法,设计哈希函数尽可能产生较少冲突,任选处理冲突方法,选择测试数据要尽可能包含多个情况,能够处理异常,达成这些要求成绩为优异,不然成绩向下浮动。激励按关键字和用户标识符判定相同性,激励设计图形用户界面。12.小型文本编辑器(*问题描述:设计一个行编辑程序,使其含有通常行编辑器(如Vi、Edlin应含有基础功效。基础要求:编辑器应含有对文本文件查找、插人、删除、修改、字符串替换、统计字数,统计行数等功效,对于超出一屏长文件,应能够分页显示,查找功效用字符串匹配算法实现。设计用户接口命令,实现对文本编辑。具体编辑命令,可参考数据结构算法网络教学平台上提供edlin、Vi命令集。测试数据:任一文本文件。提升要求:1.能够支持“* ”、“? ”等通配符;2.支持复制、粘贴等功效3. 支持多文档同时编辑;考评要求:(1界面能够是菜单形式,完成基础要求,成绩可为优异,假如只实现了基础要求部分功效,成绩向下浮动。(2能够用MFC设计界面,但其中功效实现不能用类库中类。提醒:能够考虑用双向链表实现,每一结点表示一行字符,注意每行字符不能超出255。13.小型英汉词典(*问题描述:设计一个英汉词典,支持Member查找、插入、删除操作。基础要求:实现字典常见方法有:有序线性表(用二分检索实现、A VL树(二叉搜索树、Patricia Tree、散列表等,任选一个方法实现字典操作,查找单词、插入单词(插入时,先查找,找不到插入,找到提醒用户、删除单词(删除时,先查找,找到删除,找不到提醒用户。字典是按字母次序排列,不能用次序查找,插入或删除单词后,要保持字典有序性。测试数据:任一英文单词。提升要求:选择两种以上方法实现字典操作,要比较不一样实现算法时间复杂度和空间复杂度。考评要求:(1假如采取线性结构且无序,成绩为不及格。(2选择适宜数据结构,达成了基础要求,成绩为优异。(3激励设计图形用户界面。提醒:字典能够自己建立,但必需按字母az建立26个文件,提议从网上下载,文件类型为txt。14.地图着色(*问题描述:对中国地图进行着色,两个共同边界省份染不一样颜色,当能够选择7、6、5、4种不一样颜色情况下,由程序自动进行处理,给出具体染色方案。基础要求:(1建立以省为节点,以是否相邻为边一个无向图;(2从颜色模板中选择一个颜色赋值给每个节点;(3 相邻节点颜色不能相同;测试数据:学生能够自己选择颜色模板做为测试数据;分别需要测试7、6、5、4种不一样颜色。提升要求:当用4种颜色染色时,给出不一样染色方案,计算染色效率。考评要求:(1能够不实际画图,用数字或文字表示颜色,给出着色方案,达成基础要求,成绩可为优异。(2激励画出彩色图。15.漫游中国(*问题描述:从任一省会出发,走遍全部省会,给出某种评价指标,然后依据该指标由计算机选择最优漫游路线。基础要求:(1建立以省会为节点,以是否相邻为边一个无向赋权图;(2只能选择陆路和水路交通;(3 每条边权重为两地之间距离,以公里为单位;测试数据:学生能够自己选择评价指标,如费用最少、时间最短等等。提升要求:不一样出发点结果是否一致,并讨论多目标模型。考评要求:(1不要求画图,用数字或文字表示省会,给出漫游路线,达成基础要求,成绩可为优异。(2激励画图,用不一样颜色线画出漫游路线。2123为附加题,有能力完成学生能够选择。Ply格式解析这里以big_porsche.ply为例解析其格式:1、文件头部:参看图1,文件头两行组成文件头部,其中第一行说明文件有多少个顶点(比如big_porsche.ply共有“element vertex 5247”表示有5247个顶点;第二行表示文件有多少个面(比如比如big_porsche.ply共有“element face 10474”表示有10474个面。图1 红色方框内就是文件头部2、文件体:2.1 点表部分文件头部紧接下面就是文件顶点部分,根据头部说明,应该有5247行顶点数据,图2中只是显示了10行。每个顶点有x、y、z三个浮点数代表三维坐标。图 2 红色方框内是 10 行顶点数据 2.2 面表部分 紧接这顶点数据是 10474 行面表。每个行表示一个面，假如这个行第一个值是 3，表示 此面为三角形，后面三个数顺次是三角形三个顶点索引。图 3 所表示，面表第一行是个三 角形，第一个顶点为 0 号顶点（即 2.1 中点表第一个顶点） 、第二个顶点为 1 号顶点（即 2.1 中点表第二个顶点） 、第三个顶点为 2 号顶点（即 2.1 点表中第三个顶点） 。 图 3 红色方框内是 9 行面表数据 3、绘制结果 由这么一个文件就能绘制出一个三维车模型，以下图所表示： 10 和这个文件相关三个题目 21、表排序并维护面表索引一致性（*） 过程以下： 1）首先对整个点表数据根据 X 坐标从小到大排序。 2）定义一个值 lengthX，从上到下切分 X 值段，每段长度为 lengthX。 3）在每个 lengthX 行数据内，按 Y 值进行排序。 4）在每个 lengthX 内再切分出 lengthY。 5）在 lengthY 内按 Z 值排序。 两点需要注意： 整个排序过程中每个点（即点表一行数据）是一个整体。 点编号改变，请同时维护面表一致性（即维护面表和点表初始时对应关系） 。 22、对大点表序列排序，请设计基于外存排序算法（即即使对大文件排序，占用内存也 很小，比如对 1G 文件整体排序，整个运行过程只需要占用 2M 内存）(* 23、完成对 ply 文件压缩(* 定 义 点 表 中 两 个 顶 点 （ x1, y1, z1 ） 和 (x2, y2, z2 之 间 距 离 定 义 为 ： dis = ( x1 x22 + ( y1 y 22 + ( z1 z 22 。 对 ply 文件压缩过程以下： 1）请以以上距离作为两点之间权值，构建一个最小生成树。 2）请存放两种必需信息到两个文件中： 最小生成树树形结构； 沿最小生成树存放父子节点差值。 3）对 2）中数据用 Huffman 编码进行编码压缩。 解压缩过程为以上过程逆过程。需要注意是在整个处理过程中需维护面表索引和点表 一致性。 备注： 1. 每道题目后面*号，表示题目标难度系数；对应评定成绩等级为及格（无*号） 、中等 （*号） 、良好（*号） 、优异（*号） ，学生完成题目标基础要求，即可得到程序设计部分相 应等级成绩，完成题目提升要求，成绩能够向上浮动，假如没有完成基础要求，成绩向下浮动， 直至不及格。 2. 全部题目标准上需用 C+完成，不能用 C，也不能用类库中类完成题目，如用 MFC，则 只能用 MFC 实现界面部分。 3. 选择附加题目标学生，对题目有疑问，找老师咨询。 4. 尤其注意：每道题选择人数不能超出 3 人，开学第一天，各班长将选题情况表报给各 班负责老师。 11 四、应阅读基础文件： 1王红梅，胡明，王涛编著.数据结构（C+版）. 北京：清华大学出版社，.7. 2谭浩强编著.C+面向对象程序设计.北京：清华大学出版社，.1. 面向对象程序设计、数据结构、算法分析和设计相关其它书籍和资料 五、考评方法（包含总成绩组成及分配百分比） ： 课程设计总成绩 = 平时出勤（20%）+设计汇报（40%）+上机验收及答辩（40%） 题目中给出考评要求，对应成绩仅仅是上机验收部分，课程设计总成绩要结合学生实 践能力、独立分析处理问题能力和创新精神，总结汇报和答辩水平和学习态度综合考评。成 绩分为优、良、中、及格和不及格五个档次。 六、其它相关问题说明： 无 年 课程责任人（签字） ： 月 日 年 专业教研室主任（签字） ： 月 日 年 主管院长（签字） ： 月 日 年 月 日 12