数据结构课程序设计指导书

《数据构造》〔章翔编沈阳大学信息学院课程编码： 适用层次：本科 适用专业：计算机科学与技术 适用学期:第4学期撰写人： 章翔 审核人： 刘天惠 教学院长：范立南全部打印在A4纸〔见附件〕，各级标题四号宋体加粗，正文文字小四号宋timesnewroman3000字以上。严禁抄袭，如有雷同者，均按不及格论处。一、课程设计的目的数据构造的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的根本方法。二、课程设计的根本要求1、要充分生疏课程设计对自己的重要性，认真做好设计前的各项预备工作。2、既要虚心承受教师的指导，又要充分发挥主观能动性。结合课题，独立思考，努力钻研，勤于实践，勇于创。3、独立按时完成规定的工作任务，不得弄虚作假，不准抄袭他人内容，否则成绩以不及格计。4、严格遵守学校的学习和劳动纪律、规章制度，学生有事离校必需请假。课程设计期间，无故缺席按旷课处理；缺席时间达三分之一以上者，其成绩按不及格处理。5、在设计过程中，要严格要求自己，树立严峻、严密、严谨的科学态度，必需按时、按质、按量完成课程设计。6、小组成员之间，分工明确，但要保持联系畅通，亲热合作，培育良好的相互帮助和团队协作精神。三、课程设计的主要内容题目可由下面供给的选题中选择或学生自选经教师审核前方可告必需独立完成。1、猴子选大王任务：一堆猴子都有编号，编号是1，2，3...m,这群猴子〔m个〕依据1-m的挨次围坐一圈，从第1开头数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最终一只猴子，则该猴子为大王。要求：输入数据：输入m,nm,n为整数，n<m输出形式：中文提示依据m个猴子，数n个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能2、joseph环任务：编号是1，2，……,n的n〔正整数。一开头任选一个正整数作为报数上限值m,从第一个仍开头顺时针方向自1开头挨次报数，报到m时停顿报数。报m的人出列，将他的密码作为的m值，从他在顺时针方向的下一个人开头重从1报数，如此下去，直到全部人全部出列为止。设计一个程序来求出出列挨次。要求：利用单向循环链表存储构造模拟此过程，依据出列的挨次输出各个人的编号。测试数据：m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？m的初值，n，输入每个人的密码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列3、一元多项式计算任务：能够依据指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入。4、文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求〔1〕分别统计出其中英文字母数和空格数及整篇文章总字数23〕删除某一子串，并将后面的字符前移。存储构造使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。〔1〕分行输出用户输入的各行字符〕数“、“空格个数“、“文章总字数“〔3〕输出删除某一字符串后的文章。5、稀疏矩阵的操作要求：A和B的相加矩阵C，并输出C。求出A的转置矩阵D，输出D。6、赫夫曼树的建立任务：建立建立最优二叉树函数要求：可以建立函数输入二叉树，并输出其赫夫曼树在上交资料中请写明：存储构造、根本算法〔可以使用程序流程图〕、输入输出、源程序、测试数据和结果、算法的时间简单度、另外可以提出算法的改进方法；7、纸牌玩耍任务：编号为1-52张牌，正面对上，从第2张开头，以2为基数，是2的倍数的牌翻一次，直到最终一张牌；然后，从第3张开头，以3为基数，是3的倍数的牌翻一次，直到最终一张牌；然后…从第4张开头，以4为基数，是4的倍数的牌翻一次，直到最终一张牌；...再依次5的倍数的牌翻一次，6的，7的直到以52为基数的翻过，输出：这时正面对上的牌有哪些？四、主要技术关键的分析、解决、方案比较问题分析和任务定义：依据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？〔而不是怎么做？〕限制条件是什么？规律设计：对问题描述中涉及的操作对象定义相应的数据类型，并依据以数据构造为中画出模块之间的调用关系图；具体设计：定义相应的存储构造并写出各函数的伪码算法。在这个过程中，要综合考虑据封装，根本操作的规格说明储构造的类型定义，写出函数形式的算法框架；程序编码：把具体设计的结果进一步求精为程序设计语言程序。同时参加一些注解和断言，使程序中规律概念清楚；程序调试与测试：承受自底向上，分模块进展，即先调试低层函数。能够娴熟把握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证明它或绕过它。调试正确后，认真整理源程序及其注释，形成格式