数据结构与算法课程设计数据结构与算法课程设计一、课程设计的目的、要求和任务本课程设计是为了配合《数据结构与算法》课程的开设，通过设计完整的程序，使学生掌握数据结构的应用、算法的编写等基本方法。

1.课程的目的（1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。

（2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。

（3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力；2.课程的基本要求与任务（1）巩固和加深对数据结构基本知识的理解，提高综合运用课程知识的能力。

（2）培养学生自学参考书籍，查阅手册、图表和文献资料的能力。

（3）通过实际课程设计，初步掌握简单软件的分析方法和设计方法。

（4）了解与课程有关的工程技术规范，能正确解释和分析实验结果。

（5）题目具有足够的工作量。

二、课程设计的一般步骤（1）划分课程设计小组：由不超过3名同学组成一个课程设计小组，自愿组队。

（2）选题与搜集资料：每个课程设计小组在参考选题中选择课题，并保证每人一题。

（3）分析与概要设计：根据搜集的资料，进行程序功能与数据结构分析，并选择合适的数据结构、并在此基础上进行实现程序功能的算法设计。

（3）程序设计：运用掌握C/C++语言编写程序，实现所有程序的各个模块功能。

（4）调试与测试：调试程序，并记录测试情况。

（5）完成课程设计报告。

（6）验收与评分：指导教师对每个同学的开发的系统进行综合验收。

三、任务完成形式1．完整的软件系统最终必须向指导老师提交完整的程序源代码(.c和.cpp以及.h为后缀的文件)、数据文件以及使用说明文件等。

源代码文件要特别注意编程规范、代码风格，关键代码需有合理的注释，不含任何无用代码；数据文件内要求有一定数量的“真实”数据（如对于记录文件，需要有5条以上记录）；使用说明文件的第一行，需要给出设计者的学号、姓名，后面为其它说明。

2．课程设计报告报告总体上主要包括以下几个部分，封面、目录、课程设计报告正文、使用说明、参考文献。

其中课程设计报告正文(12-20页之间，8000字以上)，书写规范，应包括如下8个部分：（1）问题描述：描述要求编程解决的问题。

（2）功能要求：给出程序要达到的具体的要求。

（3）算法思想：描述解决相应问题算法的设计思想。

（4）模块划分：描述所设计程序的各个模块（即函数）功能。

（5）数据结构：给出所使用的基本抽象数据类型,所定义的具体问题的数据类型,以及新定义的抽象数据类型。

（6）核心源程序：给出核心算法源代码，要求有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。

（7）测试数据：设计测试数据，或具体给出测试数据。

要求测试数据能全面地测试所设计程序的功能。

（8）测试情况与结果分析：给出程序的测试情况，并分析运行结果。

四、成绩评定标准学生成绩以优、良、中、及格和不及格5个等级评定。

其中：（1）学生编写的实际软件和运行结果，占总成绩45%；（2）设计报告，占总成绩45%。

（3）小组合作情况，占总成绩的10%。

该部分由指导教师进行现场口试，依据表现给分。

只有程序验收通过后，才能按以下方法核定本次课程设计的总成绩。

以下几点是决定总成绩的关键因素：（1）考勤、纪律、实验室卫生（2）工作量（代码量、功能多少、难度）（3）所用到的关键技术（4）实用性、创新（5）代码书写规范性（6）程序界面美观、新技术运用得当（7）个人答辩及小组合作情况以下几种情形认定为成绩不合格：（1）未能独立完成设计或概念不清；（2）有效代码总量不足1000行(不含自动生成代码)；（3）“管理系统”类课题中使用现有数据库系统如access，SQL Server等；（4）课程设计报告或源代码有抄袭行为；（5）3次(含)以上点名未到；（6）不遵守实验室规章制度，或不按要求完成实验室卫生工作。

五、附课程设计题目1）可另选题目，经指导老师认可后正式作为课程设计题目。

2）数据结构课程设计参考题目1.文件查重系统[问题描述]抄袭检查越来越成为一种重要的需求。

本问题要求，从文件中读入两个文件，比较其雷同字句的数目。

并给出详细对照。

当两字符串中连续相同字符的个数达到一定数目（例如20字)可视为雷同。

也可按照相同字符占句子长度的比例来检测雷同。

[基本功能]统计不同文件的雷同字段数，字段总长度，雷同字段比例。

[测试数据]可自己定义。

[实现提示]程序运行后首先要求用户给出制定的两个文件。

[高级要求]建立文件库，对新的文件检测该文件与库中哪些文件雷同，并给出相应的比例。

2.课程设计案例管理系统收集各本课程的题目案例，每个案例包括问题描述、基本功能要求、测试数据集、高级或扩展要求、课题实现源代码包、课程设计报告、评语等各部分。

[基本功能](1).案例导入或录入 (2).展示问题 (3)展示案例结果 (4)案例查询 (5)单问题多解决方案入库的处理3.约瑟夫环[问题描述]约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

试设计一个程序求出出列顺序。

[基本要求]利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

[测试数据]m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。

[实现提示]程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。

设n≤30。

*4.长整数运算[问题描述]设计一个程序实现两个任意长的整数求和运算。

[基本要求]利用双项循环链表实现长整数的存储，每个结点含一个整型变量。

任何整型变量的范围是-（215-1）~（215-1）。

输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。

[测试数据]（1）0；0；应输出“0”。

（2）-2345,6789；-7654,3211；应输出“-1,0000,0000”。

（3）-9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。

（4）1,0001,000；-1,0001,0001；应输出“0”。

（5）1,0001,0001；-1,0001,0000；应输出“1”。

[实现提示]（1）每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。

但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。

故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。

（2）可以利用头结点数据域的符号代表长整数的符号。

用其绝对值表示元素结点数目。

相加过程中不要破坏两个操作数链表。

两操作数的头指针存于指针数组中是简化程序结构的一种方法。

不能给长整数位数规定上限。

[选作内容]修改上述程序，使它在整型量范围是-（2n-1）~（2n-1）的计算机上都能有效地运行。

其中，n 是由程序读入的参量。

输入数据的分组方法可以另行规定。

5.多项式链式存储结构及其代数运算[问题描述]设计并建立一个链式存储分配系统来表示和操作多项式。

为了避免对零和非零多项式进行不同的处理，使用带头结点的循环链表。

为了充分利用多项式中不再使用的结点，维护一个可用空间表avail,把不再使用的多项式的结点链入其中。

当需要一个新结点时，就查看这个单链表avail。

如果表非空，那么可以使用它的一个结点。

只有当该表为空时，才使用动态存储分配来创建新结点。

[基本要求]设计多项式的存储结构，编写并测试下列函数：a) get_node和ret_node，从/向可用空间表申请和插入一个多项式结点。

b) pread，读取一个多项式，并将其转换成循环存储表示。

返回指向该多项式的头结点的指针。

c) pwrite，输出多项式，采用能够清楚显示的形式。

d) padd，计算d = a+b。

不改变a 和b。

e) psub，计算d = a-b。

不改变a 和b。

f) pmult，计算d = a*b。

不改变a和b。

g) eval，计算多项式在某点a的值，其中a是一个浮点型常量。

返回结果为浮点数。

h) perase，把存储表示为循环链表的多项式返还给可用空间表。

[实现提示]为了进一步简化加法算法，把多项式的头结点的指数域设为-1。

*6.稀疏矩阵的完全链表表示及其运算[问题描述]稀疏矩阵的每个结点包含down，right，row，col和value五个域。

用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。

使得第一个表即行表，把所有结点按照行序（同一行内按列序）用right域链接起来。

使得第二个表即列表，把所有结点按照列序（同一列内按行序）用down链接起来。

这两个表共用一个头结点。

另外，增加一个包含矩阵维数的结点。

稀疏矩阵的这种存储表示称为完全链表表式。

实现一个完全链表系统进行稀疏矩阵运算，并分析下列操作函数的计算时间和额外存储空间的开销。

（2）设计目的认识和掌握稀疏矩阵的完全链表表示；能够建立并运用这种存储结构(3) 基本要求建立一个用户友好、菜单式系统进行下列操作，并使用合当的测试数据测试该系统。

读取一个稀疏矩阵建立其完全链表表示输出一个稀疏矩阵的内容删除一个稀疏矩阵两个稀疏矩阵相加两个稀疏矩阵相减两个稀疏矩阵相乘稀疏矩阵的转置（4）实现提示链表上的操作。

*7.实现简单数字图像处理[问题描述]一幅图像就是一个从位置集到颜色集的变换。

考虑二维图像，位置集实际上就是一个矩阵，此时一幅图像实际上就是一个内容为颜色矩阵。

如果颜色为0-255间的整数，表示该位置的灰度等级，0为黑色，255为白色，此时的图像称为灰度图。

而图像的处理就是在该矩阵进行相关计算。

一种常见的计算就是通过一点和周围8个点的信息共同决定该点的新值：如一点的新值为该点和周围8点颜色值之和的均值，这一操作可用下图表示。

显然这样处理后，图像会变得平滑，因此称为平滑操作。

显然将上述操作变为下图时，就成为锐化操作。

要求实现若干基本的图像处理操作。

[基本要求]①熟悉Windows下BMP文件的格式，能够实现其读写(只考虑灰度图像)。

②实现图像的平滑和锐化操作，其它处理操作选做。

③需用VC++作为语言。

*8.回文判断[问题描述]试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1&序列2’模式的字符序列。

其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。