《数据结构》课程设计指导书齐晓轩编沈阳大学信息工程学院课程编码：1243331 适用层次：本科周数：1 适用专业：计算机科学与技术适用学期:第3学期撰写人：齐晓轩审核人：刘天惠教学院长：王晖一、课程设计的目的本课程设计是为了配合《数据结构》课程的开设，通过设计一完整的程序，使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法。

二、课程设计的基本要求1、要充分认识课程设计对自己的重要性，认真做好设计前的各项准备工作。

2、既要虚心接受老师的指导，又要充分发挥主观能动性。

结合课题，独立思考，努力钻研，勤于实践，勇于创新。

3、独立按时完成规定的工作任务，不得弄虚作假，不准抄袭他人内容，否则成绩以不及格计。

4、在设计过程中，要严格要求自己，树立严肃、严密、严谨的科学态度，必须按时、按质、按量完成课程设计。

5、小组成员之间，分工明确，但要保持联系畅通，密切合作，培养良好的互相帮助和团队协作精神。

6、课程设计报告要求规范书写。

应当包括如下几个部分：1．课程设计的目的2．设计方案论证包括设计思路、设计方法、有关计算、图表或程序等。

3．设计结果与分析4．设计体会5．参考文献参考文献要列出3篇以上，格式见附录三、课程设计的主要内容1. 分析题目，查阅相关资料；2. 算法设计、数据结构设计；3. 编写代码并调试；4. 完成课程设计报告。

可以小组为单位，每组1名学生，在教师的指导下，每组完成一个题目。

题目可由下面提供的选题中选择或学生自选经教师审核后方可（自选题目中必须用到所学过的几种数据结构之一）。

1、猴子选大王任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

要求：输入数据：输入m,n ；m,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、两个链表的合并要求：（1）建立两个链表A和B，链表元素个数分别为m和n个。

（2）假设元素分别为(x1,x2,...xm)，和(y1,y2, ...yn)。

把它们合并成一个线形表C，使得：当m>=n时，C=x1,y1,x2,y2,...xn,yn, (x)当n>m时，C=y1,x1,y2,x2,…ym,xm,…,yn输出线形表C（3）用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。

（4）测试数据：①A表（30，41，15，12，56，80）B表（23，56，78，23，12，33，79，90，55）②A表（30，41，15，12，56，80，23，12，34）B表（23，56，78，23，12）4、一元多项式的计算任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入。

5、文章编辑器任务：输入一页文字，程序可以统计出文字、数字、空格的个数。

静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。

存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。

输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"（3）输出删除某一字符串后的文章。

6、数组的应用任务：按照行优先顺序将输入的数据建成2维数组，再按照列优先顺序输出结果，给出任意处的元素值，并给出对应的一维数组中的序号。

7、稀疏矩阵的操作要求：（1）稀疏矩阵采用三元组表示，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C。

（2）求出A的转置矩阵D，输出D。

8、矩阵乘法：A B－1（1）任务：设计一个矩阵相乘的程序，首先从键盘输入两个矩阵a，b的内容，并输出两个矩阵，输出ab－1结果。

（2）有兴趣的同学可以自己扩充系统功能。

9、赫夫曼树的建立任务：建立最优二叉树函数要求：可以建立函数输入二叉树，并输出其哈夫曼树在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；10、图的深度遍历任务：对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用堆栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现图的深度优先搜索遍历。

11、图的广度遍历任务：图的广度遍历：对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索遍历。

12、排序算法比较利用随机函数产生5000个随机整数，利用插入排序、起泡排序、选择排序、快速排序等排序方法进行排序，并统计每一种排序上机所花费的时间。

13、纸牌游戏任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后，第4张开始，以4为基数，是4的倍数的牌翻一次，直到最后一张牌；再依次5的倍数的牌翻一次，6的，7的直到以52为基数的翻过，输出：这时正面向上的牌有哪些？四、主要技术关键的分析、解决、方案比较以下是可以参考的课程设计可能包含的相关知识：1、编写良好算法的基本思想及算法性能的分析2、线性结构、树型结构、图型形结构的特点及应用3、查找与排序的常见算法及其改进五、课程设计考核方式与标准课程设计结束后，学生写出课程设计论文，并在最后附源程序，指导教师依课程设计论文情况及整个课程设计中学生的表现，综合给出成绩。

成绩分为优、良、中、及格、不及格五级。

六、主要参考资料1、《数据结构》，严蔚敏等，清华大学出版社2、《数据结构题集》，严蔚敏等，清华大学出版社3、《程序设计与问题求解》，朱国进等，东华大学出版社七、课程设计说明书应体现如下内容：设计题目1．课程设计的目的2．设计方案论证包括设计思路、设计方法、有关计算、图表或程序等3．设计结果与分析此处必须有程序的运行截图（即图中显示运行结果）4．设计体会5．参考文献参考文献要列出3篇以上，格式如下：[1] 谢宋和, 甘勇. 单片机模糊控制系统设计与应用实例[M]. 北京: 电子工业出版社, 1999.5：20-25（参考书或专著格式为:著者. 书名[M]. 版本(第1版不注). 出版地:出版者, 出版年月：引文所在页码）[2] 潘新民, 王燕芳. 微型计算机控制技术[M], 第2版. 北京: 电子工业出版社, 2003.4：305-350（1本书只能作为1篇参考文献，不能将1本书列为多个参考文献）[3] 范立南, 谢子殿. 单片机原理及应用教程[M]. 北京: 北京大学出版社, 20 06.1：123-130[4] Newman W M, Sbroull R F. Principles of Interactive Computer Graph ics[M]. New York: McGraw Hill, 1979.10：10-25[5]卜小明, 龙全求. 一种薄板弯曲问题的四边形位移单元[J]. 力学学报, 199 1,23(1):53-60（参考期刊杂志格式为:作者. 论文题目[J]. 期刊名, 出版年, 卷号(期号): 页码）（期刊名前不写出版地）[6] Mastri A R. Neuropathy of diabetic neurogenic bladder[J]. Ann Int ern Med, 1980, 92(2):316-318[7] 范立南, 韩晓微, 王忠石等. 基于多结构元的噪声污染灰度图像边缘检测研究[J]. 武汉大学学报(工学版), 2003，49(3):45-49[8] index.asp（一般情况下不要用网址作为参考文献，如果用，最多1个）注：[M]表示参考的是书籍；[J]表示参考的是学术期刊的论文；如果参考会议论文集中的论文用[C]。

八、课程设计说明书的要求：全部打印在A4纸（课程设计专用纸），各级标题四号宋体加粗，正文文字小四号宋体，程序五号times new roman，字数3000字以上。

严禁抄袭，如有雷同者，均按不及格论处。

九、课程设计说明书的注意问题：1．所有的图要有标注（标注位于图下），标注中的序号从1、2、3…等开始编号，并居中排版，例如：图1 程序流程图图2 ***图2．所有的表要有表注（表注位于表上），表注中的序号从1、2、3…等开始编号，并居中排版，例如：3．说明书中的内容序号分别为：一级标题 1 2 3二级标题 1.1 1.2 1.3三级标题 1.1.1 1.1.2 1.1.3接下来用（1）（2）（3）再接下来用①②③4. 说明书中必须有程序运行的截图（即图中显示运行结果）在详细设计或功能说明中，要对每一功能模块做以介绍，要有文字说明及相应的图或表，也可加上关键代码（关键代码不是必须的）。

5．效果及存在的问题中要有针对性的对本系统进行总结和说明。

6．附录另起一页。