《2022年数据结构课程方案大纲.docx》由会员分享，可在线阅读，更多相关《2022年数据结构课程方案大纲.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用数据结构课程设计教案大纲课程代码： 0806522088 课程名称：数据结构设计周数： 1 周 设计学分： 0.5 一、课程设计的目的与任务课程设计是同学对课程所学学问的综合运用,它与课堂听讲、上机试验、课外练习、自学讨论相辅相成,构成一个完整的课程教案体系；数据结构是一门实践性强的课 程,其中对算法设计和程序编写的把握尤为重要；同学虽然可以通过与课堂教案同步的上 机试验完成相关内容的练习,但却往往局限于一些功能简洁、彼此之间关系独立的算法和 程序；课程设计是一种综合训练,致力于培育同学全面、敏捷的算法设计思想和较高的
2、编 程才能,为今后从事运算机开发与应用打下基础；新世纪需要具有丰富科学学问、独立解 决实际问题、有制造才能的新型人才,这也是该课程设计的最终目的；二、本课程设计的基本理论数据结构课程设计中牵涉到本课程中的六个主要章节的基本理论,包括基本数据 结构 线性结构 线性表、栈、队列）、图、树）的特点、储备方式、运算原理和方法、典 型应用和两种重要操作查找、排序的基本原理与方法；三、课程设计的方式与基本要求方式： 整个课程设计要求分为四个阶段来完成；第一阶段为分组及预备阶段,此阶段 要求将同学分成如干小组,每小组挑选好设计模块,然后由同学自主进行问题分析和相关 资料查询,并对课程设计内容作初步设计；其次
3、阶段为编程及程序调试阶段,此阶段会安 排肯定数量的集中上机时间,有指定的指导老师负责指导同学解决凝难问题；第三阶段为 程序测试及检查阶段,此阶段由指导老师对每位同学的设计结果作测试和检查,并依据测试及检查结果评定同学成果,此成果占课程设计总成果的70%；第四阶段为同学编写课程设计试验报告阶段,每位同学依据课程设计试验报告的内容和要求编写具体的课程设计实 验报告并打印上交给指导老师,由指导老师依据每位同学的完成情形评定成果,此成果占 课程设计总成果的 30%；基本要求：通过这次设计,要求在分析运算机处理对象的规律特性和物理表示、数据 结构的挑选和应用、算法的设计及其实现等方面加深对课程基本内容的
4、懂得；要求每个学生在规定的时间内完成一组中2 个应用问题,并依据所选问题分析设计思路、挑选数据结构描述、确立算法过程、用一种运算机语言 例如 Turbo C 、Java ）编写出具体的实现程序,然后通过上机反复调试与修改,直到获得中意的结果为止；对于要解决的同一问题,由于所采纳的数据结构可能不同、所挑选的算法可能不同、编写的程序也不仅相同,但只要结果正确且有效 具有较好的时间复杂度和空间复杂度）即可,即不要求编写的算法和程序完全一样,但力求编写的算法和程序更优秀、综合指标更好；名师归纳总结 - - - - - - -第 1 页,共 7 页精选学习资料 - - - - - - - - - 个人资
5、料整理 仅限学习使用四、课程设计的内容将以下所示的12 道题分成六组,分别是1、10）, 4、8）, 3、11）, 5,7）,2、 12）, 6,9）,同学也分成六组,每组同学挑选一组题目完成；1.约瑟夫环问题求解【问题描述】编号为 1,2 n 的 n 个人按顺时针方向围坐一圈,每人持有一个密码 利用单循环链表作为储备结构模拟此过程；2键盘输入总人数、初始报数上限值 m 及各人密码；3依据出列次序输出各人的编号；【选做内容】1添加在次序结构上实现的部分；2界面设计的优化；2. 猴子选王问题求解【问题描述】一堆猴子都有编号,编号是 1,2,3 .m ,这群猴子 利用单循环链表作为储备结构模拟此过
6、程；2输入数据：输入 m,n, m,n 为整数, n输出形式：中文提示依据 m 个猴子,数 n 个数的方法,输出为大王的猴子是几号 ,建立一个函数来实现此功能；【选做内容】1添加在次序结构上实现的部分；2界面设计的优化；3. 一元稀疏多项式运算器【问题描述】设计一个一元多项式加法器；【基本要求】1输入并建立多项式,用带表头结点的单链表储备多项式,多项式的项数存放在头结点中；2两个多项式相加；3输出多项式： n, c1, e1, c2, e2, cn , en, 其中, n 是多项式项数,ci 和 ei 分别是第 i 项的系数和指数,序列按指数降序排列；【选做内容】1运算多项式在 x 处的值；2
7、多项式的输出形式改进；名师归纳总结 - - - - - - -第 2 页,共 7 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用3求多项式的导函数；4运算器的仿真界面；4. 迷宫求解【问题描述】以一个 m n 长方阵表示迷宫,0 和 1 分别表示迷宫中的通路和障碍,设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论；【基本要求】1以二维数组储备迷宫数据；2求得的通路以二元组 i , j 的形式输出,其中以方阵形式输出迷宫及其通路； 2显示整个查找通路的动态过程；5. 哈夫曼编码 /译码器【问题描述】设计一个利用哈夫曼算法的编码和译码
8、系统,重复地显示并处理以下工程,直到挑选退出 为止；【基本要求】1初始化：键盘输入字符集大小n、n 个字符和 n 个权值,建立哈夫曼树；2编码：利用建好的哈夫曼树生成哈夫曼编码；3输出编码；4设字符集及频度如下表：字符： A B C D E F 频度： 4 9 23 2 17 15 字符： G H I J K 频度： 1 2 3 3 4 【选做内容】1显示哈夫曼树；2界面设计的优化；6. 图书治理系统【问题描述】设计一个运算机治理系统完成图书治理基本业务；【基本要求】1每种书的登记内容包括书号、书名、著作者、现存量和库存量；2对书号建立索引表 系统主要功能如下：*采编入库：新购一种书,确定书号
9、后,登记到图书帐目表中,假如表中已有,就只将库存 量增加；*借阅：假如一种书的现存量大于 现存量；0,就借出一本,登记借阅者的书证号和归仍期限,转变*归仍：注销对借阅者的登记,转变该书的现存量；【选做内容】1系统功能的进一步完善；2索引表采纳树表；7内部排序算法的性能分析名师归纳总结 - - - - - - -第 3 页,共 7 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用【问题描述】设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受；【基本要求】1对起泡排序、直接插入排序、简洁挑选排序、快速排序、希尔排序进行比较；2待排序表的表长不
10、小于 100,表中数据随机产生,至少用 5 组不同数据作比较,比较指 标有：关键字参与比较次数和关键字的移动次数 输出比较结果；【选做内容】1对不同表进步行比较；2验证各算法的稳固性；3输出界面的优化；8哈希表 设每个记录有以下数据项：电话号码、用户名、地址；2 从键盘输入各记录,分别以电话号码为关键字建立散列表；3采纳拉链法解决冲突；4查找并显示给定电话号码的记录；5 查找并显示给定用户名的记录；【选做内容】1系统功能的完善；2设计不同的散列函数,比较冲突率；3在散列函数确定的前提下,尝试各种不同类型处理冲突的方法,考察平均查找长度的变 化；9. 背包问题求解【问题描述】设有不同价值 ,不同
11、重的物品n 件,求从这n 件物品中选取一部分物品的方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和为最大.【基本要求】1 分别输入 n 件物品的重量和价值 2 采纳递归查找物品的挑选方案 . 3 输出正确的装填方案 : 包括选中的是哪几种物品 ,总价值为多少 . 10. 八皇后问题求解【问题描述】在一个 的棋盘里放置个皇后,要求每个皇后两两之间不相 冲 在每一横列 竖列斜列只有一个皇后）；【问题分析】数组 a、b、c 分别用来标记冲突,a 数组代表列冲突,从 a0a7 代表第 0 列 1,否就为 0；到第 7 列,假如某列上已经有皇后,就为数组 b 代表主对角线冲突,为有皇后
12、,就为 1,否就为 0；数组 c 代表从对角线冲突,为皇后,就为 1,否就为 0；【基本要求】bi-j+7 ,即从 b0b14 ,假如某条主对角线上已经 ci+j ,即从 c0c14 ,假如某条从对角线上已经有名师归纳总结 - - - - - - -第 4 页,共 7 页精选学习资料 - - - - - - - - - （1）用递归算法实现个人资料整理仅限学习使用（2）输出全部棋盘状态,其中空的地方为“*” ,放置皇后的地方为“”11最小生成树求解【问题描述】在 n 个城市之间建设网络,只需保证连通即可,求最经济的架设方法；【基本要求】1）假设已知 n 个城市之间的网络是一个带权连通无向图；2
13、）用邻接矩阵 COST 表示给定的带权连通无向图；知阵元素定义为 wij Cost= 0 3）利用普里姆或克鲁斯卡尔算法求图的最小生成树；12二叉树的建立【问题描述】已知二叉树 T 中结点的中序和后序遍历序列,编写算法实现构造满意上述条件的二叉树；【基本要求】（1）假设二叉树 T 的结点值是字符；（2）建立的二叉树以二叉链表的储备结构进行储备；（3）输出二叉树的先序遍历序列；五、考核方式与评分方法1. 考核方式：随堂抽查同学的试验过程和运行结果及检查同学编写的课程设计试验报告；2. 评分方法：本试验课程成果由两部分构成,一部分是为试验过程成果 . 北京：清华高校出版社,1999 4张铭 . 数
14、据结构与算法学习指导与习题解读 . 北京：高教出版社 .2022 5耿国华等 . 数据结构 -C 语言描述 . 北京：高教出版社 .2005.7 6刘怀亮 . 数据结构 C 语言描述 习题与试验指导导 .北京：冶金出版社 .2005.2 7徐孝凯 . 数据结构课程试验 . 北京：清华高校出版社 2002 8孟佳娜 , 胡潇琨 . 算法与数据结构试验与习题 . 北京：机械工业出版社,2004. 七、课程设计实习报告内容与要求数据结构课程设计试验报告要求完成的内容包括：1问题描述名师归纳总结 - - - - - - -第 5 页,共 7 页精选学习资料 - - - - - - - - - 个人资料
15、整理 仅限学习使用依据你所选做题目,写出其问题的文字描述；2问题分析 依据自身对课程的把握程度,充分分析和懂得问题的设计要求,给出较为明确、简洁 的设计思路和解决方法；3数据结构描述 依据要解决的问题,考虑各种可能的数据结构类型,从中挑选一种较为有效的数据结 构,确定其储备形式并写出储备结构的描述；4算法设计 依据问题分析的结果,及储备结构的描述,写出合理的算法设计过程,特殊要留意所使用函数间的调用与被调用关系,可以用程序总模块图及程序流程图表示；5具体程序清单依据算法的内容,用运算机语言如 Java 或 C）编写完整的程序,并将程序在机器上反复调试,直到结果正确为止,最终将程序清单打印出来,
16、要求附上具体注解；特殊要注意算法与程序的区分以及上下层模块间的接口处理即参数的设置）；同时要求只写一个主程序,每个问题的处理通过主程序对函数的调用来实现,而且要求在主程序中要求设计 一个界面,用户在运行程序时可通过界面的提示挑选执行相应的功能模块；6程序运行结果 利用典型的测试用例,将数据输入到程序执行过程中去,登记执行过程中屏幕显示情 况与相应结果；7写出访用说明,实习体会心得等；最终将以上文字材料装订成册,并做好封面,封面格式见最终的附件名师归纳总结 - - - - - - -第 6 页,共 7 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用附件 :数据结构课程设计 试验报告题 目 学 院 专 业 班 级 学 号 同学姓名 同组成员 指导老师 编写日期名师归纳总结 - - - - - - -第 7 页,共 7 页