最新数据结构与算法(通用13篇)

短篇小说是一种以叙述事件为主线，通过情节的展开和冲突的发展，表现人物形象和情感的一种文学作品。写一篇较为完美的总结，需要注重客观评价和自我反思。请大家参考这些范文，不要照搬照抄，要结合自己的情况进行修改和完善。

数据结构与算法篇一

为了顺利完成实验教学任务，确保人身、设备的安全，培养严谨、踏实、实事求是的科学作风和爱护国家财产的优良品质，特制定以下实验规则：

1、实验前必须充分预习，完成指定的预习任务。预习要求如下：

（1）认真阅读指导书，进行必要的设计与计算。（2）熟悉实验内容。

（3）预先复习，并按要求编写程序。（4）未完成预习任务者不得进入实验室。

2、遵守以下纪律：

（1）在实验室不得做和实验无关的事情。

（2）进行任课老师指定内容以外的实验，必须经指导教师同意。（3）遵守纪律，不迟到。

（4）保持实验室内安静、整洁，爱护公物，不许乱写乱画。

实验环境。

本实验在386以上的微机上进行，运行环境为vc6.0。

实验报告要求。

1、实验题目2．实验目的3．实验环境。

4．实验内容与完成情况（可以附上自主设计的源程序）5．出现的问题及对问题的解决方案6．实验思考：（学生对本次实验的收获的总结）。

实验一单链表。

（一）一、实验目的。

掌握线性表的链式存储结构及其基本操作。

二、预习要求。

1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。

2、根据要求，编写程序准备上机调试。

三、实验内容。

实现一个简单的学生信息管理系统，该系统的功能有：

1、利用单链表建立学生基本信息表。

2、浏览每个学生的信息。

3、根据学号查询某个学生的基本信息。

4、添加学生信息到单链表中。

5、删除一个学生的信息。

四、实现提示。

设计结点的结构体类型，包括学生的学号、姓名、年龄、性别；要求设计一个简单的菜单界面，根据需要选择所要进行的操作；构造函数，每一个函数实现上述的一个功能。

实验二单链表。

（二）一、实验目的。

掌握线性表的链式存储结构及其基本操作。

二、预习要求。

1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。

2、根据要求，编写程序准备上机调试。

三、实验内容。

1、实现单链表的就地逆置。

2、建立两个非递减有序单链表，然后合并成一个非递减链表。

3、建立两个非递减有序单链表，然后合并成一个非递增链表。

4、编写一个主函数,调试上述算法。

四、选做题、思考题。

1、如何用带表头结点的单链表作为多项式的存储表示，实现两个多项式的相加。

2、约毖夫环的实现。

3、如何利用文件实现学生信息的存取。

实验三栈。

一、实验目的。

深入了解并掌握栈的特性及其在实际中的应用；熟练掌握栈的算法实现；运用栈操作求解实际问题。

二、预习要求。

1、看懂书上的算法，深入理解栈的特性和存储结构，以便在实际问题背景下灵活运用。

2、根据要求，编写程序准备上机调试。

三、实验内容。

利用栈实现数据的分类，要求当输入为偶数时进栈1，当输入为奇数时进栈2，最后分别从栈1和栈2输出偶数和奇数序列。

四、实现提示。

1、开辟一个连续的存储空间，实现两个栈顺序存储空间的共享；分别在两端设置栈顶指针，并按要求实现栈操作。

2、采用顺序存储实现栈的初始化、入栈、出栈操作。

五、选做题、思考题。

1、两栈空间共享时，栈满的条件是什么？

2、为停车场编制进行管理的模拟程序（习题集p96，2.1）。

3、编写程序，利用栈实现表达式求值。

实验四二叉树。

一、实验目的。

通过实践掌握二叉树的存储结构和遍历思想；掌握二叉树的常见算法的程序实现。

二、预习要求。

二叉树的三种遍历方法。

三、实验内容。

1、输入字符序列，建立二叉链表。

2、利用栈，编写非递归算法，编程实现二叉树的中序遍历。

3、求二叉树的叶子结点个数。

4、在主函数中设计一个简单的菜单，分别调试上述算法。

四、选做题、思考题。

1、如何实现二叉树的后序遍历（非递归）。

2、如何求二叉树的高度。

实验五最短路径（旅游景点导游咨询模拟）。

一、实验目的。

利用图的最短路径原理为用户提供路径咨询，掌握求最短路径的算法并编程实现。

二、预习要求。

学习了解图的存储结构，掌握求最短路径的两种算法。

三、实验内容。

设计一个旅游景点导游模拟程序，为来访的客人提供景点最短路径的信息查询服务，任意选取n城市，构成一个有向带权图，图中顶点表示城市，边上的权值表示两点间的距离，根据用户指定的始点和终点输出相应的最短路径。

四、实现提示。

咨询以用户和计算机的对话方式进行，由用户输入起始点和终点，输出信息：最短路径是多少？并指出所经过的城市。存储结构可选用邻接矩阵。

五、选做题、思考题。

1．如何实现对城市信息进行编辑（如：添加或删除）的功能。

2．用邻接表作存储结构，求一指定景点出发，到其余各景点的最短路径。

实验六内部排序。

一、实验目的。

直观感受算法的关键字比较次数和关键字移动次数。

二、预习要求。

1、常见的排序算法(插入排序、交换排序、选择排序、归并排序、基数排序等)的思想、特点及其适用条件。

2、根据要求，编写程序准备上机调试。

三、实验内容。

1、对直接插入排序和简单选择排序算法进行关键字比较次数和关键字移动次数的比较。

2、利用链式存储结构，编写程序，实现直接插入排序和冒泡排序。

四、实现提示。

测试数据可以为几组典型的数据：正序、逆序、乱序。

五、选做题、思考题。

1、快速排序算法的非递归实现。

2、结合实验，理解针对不同待排元素的特点而选择不同排序方法的重要性。

3、如何对本实验进行时间、空间的复杂度分析。

数据结构与算法篇二

完成了这次的二元多项式加减运算问题的课程设计后，我的心得体会很多,细细梳理一下，有以下几点：

1、程序的编写中的语法错误及修改。

因为我在解决二元多项式问题中，使用了链表的方式建立的二元多项式，所以程序的空间是动态的生成的，而且链表可以灵活地添加或删除结点，所以使得程序得到简化。但是出现的语法问题主要在于子函数和变量的定义，降序排序，关键字和函数名称的书写，以及一些库函数的规范使用，这些问题均可以根据编译器的警告提示，对应的将其解决。

2、程序的设计中的逻辑问题及其调整。

我在设计程序的过程中遇到许多问题，首先在选择数据结构的时候选择了链表，但是链表的排序比较困难，特别是在多关键字的情况下，在一种关键字确定了顺序以后，在第一关键字相同的时候，按某种顺序对第二关键字进行排序。在此程序中共涉及到3个量数，即：系数，x的指数和y的指数，而关键字排是按x的指数和y的指数来看，由于要求是降幂排序且含有2个关键字，所以我先选择x的指数作为第一关键字，先按x的降序来排序，当x的指数相同时，再以y为关键字，按照y的指数大小来进行降序排列。

另外，我在加法函数的编写过程中也遇到了大量的问题，由于要同时比较多个关键字，而且设计中涉及了数组和链表的综合运用，导致反复修改了很长的时间才完成了一个加法的设计。但是，现在仍然有一个问题存在：若以0为系数的项是首项则显示含有此项，但是运算后则自动消除此项，这样是正确的。但是当其不是首项的时候，加法函数在显示的时候有0为系数的项时，0前边不显示符号，当然，这样也可以理解成当系数为0时，忽略这一项。这也是本程序中一个不完美的地方。

我在设计减法函数的时候由于考虑不够充分就直接编写程序，走了很多弯路，不得不停下来仔细研究算法，后来发现由于前边的加法函数完全适用于减法，只不过是将二元多项式b的所有项取负再用加法函数即可，可见算法的重要性不低于程序本身。

3、程序的调试中的经验及体会。

我在调试过程中，发生了许多小细节上的问题，它们提醒了自己在以后编程的时候要注意细节，即使是一个括号的遗漏或者一个字符的误写都会造成大量的错误，浪费许多时间去寻找并修改，总结的教训就是写程序的时候，一定要仔细、认真、专注。

我还有一个很深的体会就是格式和注释，由于平时不注意格式和注释这方面的要求，导致有的时候在检查和调试的时候很不方便。有的时候甚至刚刚完成一部分的编辑，结果一不注意，就忘记了这一部分程序的功能。修改的时候也有不小心误删的情况出现。如果注意格式风格，并且养成随手加注释的习惯，就能减少这些不必要的反复和波折。还有一点，就是在修改的时候，要注意修改前后的不同点在哪里，改后调试结果要在原有的基础上更加精确。

数据结构与算法篇三

课程名称：

学生学号：

所属院部：

（理工类）。

学生姓名：

指导教师：——20学年第学期。

金陵科技学院教务处制。

实验报告书写要求。

实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用a4的纸张。

实验报告书写说明。

实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。

填写注意事项。

（1）细致观察，及时、准确、如实记录。（2）准确说明，层次清晰。

（3）尽量采用专用术语来说明事物。

（4）外文、符号、公式要准确，应使用统一规定的名词和符号。（5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。

实验报告批改说明。

实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。

实验报告装订要求。

实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。

实验项目名称：顺序表实验学时：2同组学生姓名：实验地点：实验日期：实验成绩：批改教师：批改时间：

实验1顺序表。

一、实验目的和要求。

掌握顺序表的定位、插入、删除等操作。

二、实验仪器和设备。

vc6.0。

三、实验内容与过程（含程序清单及流程图）。

1、必做题。

（1）编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。

（2）编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回－1。编写主函数测试结果。（3）在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。

解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。

（4）删除顺序表中所有等于x的数据元素。

2、选做题。

（5）已知两个顺序表a和b按元素值递增有序排列，要求写一算法实现将a和b归并成一个按元素值递减有序排列的顺序表（允许表中含有值相同的元素）。

程序清单：

四、实验结果与分析（程序运行结果及其分析）。

五、实验体会（遇到问题及解决办法，编程后的心得体会）。

实验项目名称：单链表实验学时：2同组学生姓名：实验地点：实验日期：实验成绩：批改教师：批改时间：

实验2单链表。

一、实验目的和要求。

1、实验目的。

掌握单链表的定位、插入、删除等操作。

2、实验要求。

（1）注意链表的空间是动态分配的，某结点不用之后要及时进行物理删除，以便释放其内存空间。

（2）链表不能实现直接定位，一定注意指针的保存，防止丢失。

二、实验仪器和设备。

visualc++6.0。

三、实验内容与过程（含程序清单及流程图）。

1、必做题。

（1）编写程序建立一个单链表，并逐个输出单链表中所有数据元素。（2）在递增有序的单链表中插入一个新结点x，保持单链表的有序性。

解题思路：首先查找插入的位置然后进行插入操作；从第一个结点开始找到第一个大于该新结点值的结点即为插入位置；然后在找到的此结点之前插入新结点；注意保留插入位置之前结点的指针才能完成插入操作。

（3）编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。

2、选做题。

已知指针la和lb分别指向两个无头结点单链表的首元结点。要求编一算法实现，从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第j个元素之前。程序清单：

四、实验结果与分析（程序运行结果及其分析）。

五、实验体会（遇到问题及解决办法，编程后的心得体会）。

实验项目名称：堆栈和队列实验学时：2同组学生姓名：实验地点：实验日期：实验成绩：批改教师：批改时间：

实验3堆栈和队列。

一、实验目的和要求。

（1）掌握应用栈解决问题的方法。（2）掌握利用栈进行表达式求和的算法。

（3）掌握队列的存储结构及基本操作实现，并能在相应的应用问题中正确选用它们。

二、实验仪器和设备。

visualc++6.0。

三、实验内容与过程（含程序清单及流程图）。

1、必做题。

（1）判断一个算术表达式中开括号和闭括号是否配对。（2）测试“汉诺塔”问题。

（3）假设称正读和反读都相同的字符序列为”回文”，试写一个算法判别读入的一个以’@’为结束符的字符序列是否是“回文”。

2、选做题。

在顺序存储结构上实现输出受限的双端循环队列的入列和出列算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。程序清单：

四、实验结果与分析（程序运行结果及其分析）。

五、实验体会（遇到问题及解决办法，编程后的心得体会）。

实验项目名称：串实验学时：2同组学生姓名：实验地点：实验日期：实验成绩：批改教师：批改时间：

实验4串。

一、实验目的和要求。

掌握串的存储及应用。

二、实验仪器和设备。

visualc++6.0。

三、实验内容与过程（含程序清单及流程图）。

1、必做题。

（1）编写输出字符串s中值等于字符ch的第一个字符的函数，并用主函数测试结果。

（2）编写输出字符串s中值等于字符ch的所有字符的函数，并用主函数测试结果。

解题思路：可以将第一题程序改进成一个子函数，在本题中循环调用。（3）设字符串采用单字符的链式存储结构，编程删除串s从位置i开始长度为k的子串。

2、选做题。

假设以链结构表示串，编写算法实现将串s插入到串t中某个字符之后，若串t中不存在这个字符，则将串s联接在串t的末尾。

提示：为提高程序的通用性，插入位置字符应设计为从键盘输入。程序清单：

四、实验结果与分析（程序运行结果及其分析）。

五、实验体会（遇到问题及解决办法，编程后的心得体会）。

实验项目名称：二叉树实验学时：2同组学生姓名：实验地点：实验日期：实验成绩：批改教师：批改时间：

实验5二叉树。

一、实验目的和要求。

（1）掌握二叉树的生成，以及前、中、后序遍历算法。（2）掌握应用二叉树递归遍历思想解决问题的方法。

二、实验仪器和设备。

visualc++6.0。

三、实验内容与过程（含程序清单及流程图）。

1、必做题。

（1）建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。

（2）在第一题基础上，求二叉树中叶结点的个数。（3）在第一题基础上，求二叉树中结点总数。（4）在第一题基础上，求二叉树的深度。

2、选做题。

已知一棵完全二叉树存于顺序表sa中，[1…]存储结点的值。试编写算法由此顺序存储结构建立该二叉树的二叉链表。

解题思路：根据完全二叉树顺序存储的性质来确定二叉树的父子关系即“还原”了二叉树，之后再按照二叉树二叉链表的构造方法进行建立。完全二叉树顺序存储的一个重要性质为，第i个结点的左孩子是编号为2i的结点，第i个结点的右孩子是编号为2i+1的结点。程序清单：

四、实验结果与分析（程序运行结果及其分析）。

五、实验体会（遇到问题及解决办法，编程后的心得体会）。

实验项目名称：图实验学时：2同组学生姓名：实验地点：实验日期：实验成绩：批改教师：批改时间：

实验6图。

一、实验目的和要求。

（1）熟练掌握图的基本概念、构造及其存储结构。

（2）熟练掌握对图的深度优先搜索遍历和广度优先搜索遍历的算法。

二、实验仪器和设备。

visualc++6.0。

三、实验内容与过程（含程序清单及流程图）。

1、必做题。

（1）构造一个无向图（用邻接矩阵表示存储结构）。

（2）对上面所构造的无向图，进行深度优先遍历和广度优先遍历，输出遍历序列。

2、选做题。

采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。简单路径是指其顶点序列中不含有重复顶点的路径。提示：两个顶点及k值均作为参数给出。程序清单：

四、实验结果与分析（程序运行结果及其分析）。

五、实验体会（遇到问题及解决办法，编程后的心得体会）。

实验项目名称：排序实验学时：2同组学生姓名：实验地点：实验日期：实验成绩：批改教师：批改时间：

实验7排序。

一、实验目的和要求。

（1）熟练掌握希尔排序、堆排序、直接插入排序、起泡排序、快速排序、直接选择排序、归并排序和基数排序的基本概念。

（2）掌握以上各种排序的算法。区分以上不同排序的优、缺点。

二、实验仪器和设备。

visualc++6.0。

三、实验内容与过程（含程序清单及流程图）。

1、必做题。

用随机数产生100000个待排序数据元素的关键字值。测试下列各排序函数的机器实际执行时间（至少测试两个）：直接插入排序、希尔排序（增量为4，2，1）、冒泡排序、快速排序、直接选择排序、二路归并排序、堆排序和基于链式队列的基数排序。

2、选做题。

假设含n个记录的序列中，其所有关键字为值介于v和w之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v…w]，令number[i]统计关键字为整数i的纪录个数，然后按number重排序列以达到有序。试编写算法实现上述排序方法，并讨论此种方法的优缺点。程序清单：

四、实验结果与分析（程序运行结果及其分析）。

五、实验体会（遇到问题及解决办法，编程后的心得体会）。

实验项目名称：查找实验学时：2同组学生姓名：实验地点：实验日期：实验成绩：批改教师：批改时间：

实验8查找。

一、实验目的和要求。

（1）掌握顺序表查找、有序表查找、索引顺序表查找的各种算法。（2）掌握哈希表设计。

二、实验仪器和设备。

visualc++6.0。

三、实验内容与过程（含程序清单及流程图）。

1、必做题。

（1）在一个递增有序的线性表中利用二分查找法查找数据元素x。

2、选做题。

（2）构造一个哈希表，哈希函数采用除留余数法，哈希冲突解决方法采用链地址法。设计一个测试程序进行测试。

提示：构造哈希表只是完成查找的第一步，大家应该掌握在哈希表上进行查找的过程，可以试着编程序实现。程序清单：

四、实验结果与分析（程序运行结果及其分析）。

五、实验体会（遇到问题及解决办法，编程后的心得体会）。

数据结构与算法篇四

1004012033陈孝婕10计本3“数据结构与算法”这门课程对于计算机科学与技术系的学生来说是非常重要的课程。这门课程主要包括十个章节。

一．每章主要知识点总结和个人掌握情况。

第一章主要要求学生掌握数据、数据类型、数据结构、算法及算法分析等基本概念和基础知识。另外，第一章结合课程学习要求，复习和掌握算法描述工具--c语言中的指针类型与指针变量、结构类型与结构变量、函数与参数、递归定义和递归函数、动态存储分配、文件操作、程序测试和测试集、测试数据的设计和程序调试等问题。

从这一章中我不仅学到了数据结构的基本概念和基础知识，了解到什么是数据结构，我们为什么要学习数据结构这门课程。而且复习了大一下学期所学的c语言程序课程设计中的算基本法语句。有利于数据结构与算法后面课程的学习。

第二章主要学习顺序表（包括顺序串）数据类型、数据结构、基本算法及相关应用。知识点包括顺序表的概念、数据结构定义、数据类型描述、基本算法的实现及其性能的分析等知识；还有“查找”和“排序”的概念，“查找”包括3种查找方式：简单顺序查找、二分查找、分块查找；“排序”包括直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序和归并排序（重点为二路归并排序）6种排序方式；掌握应用顺序表来进行查找和排序的各类算法以及不同的查找和排序算法间的性能差异。在此基础上，理解顺序串的相关应用。

从这一章中我学习到各种不同的查找方法和排序方式，其中二分查找作为重点查找方法我进行了重点学习，熟悉并熟练地运用二分查找并且了解到各种排序方法适合于不同的顺序表。对于顺序串的学习，我主要掌握了字符串的基本运算，包括：求串长strlen(s)、连接stract(st1,st2)、求子串substr(s,i,j)、比较串的大小strcmp(s,t)、插入insert(s1,i,s2)、删除delete(s,i,j)、子串定位index(s1,s2)、置换(replace(s1,i,j,s2)、replace(s,t,v)两种)。

第三章主要学习链表（单聊表、循环链表）的概念、数据结构、数据类型描述、基本算法以及链表相关应用。需要掌握各种链表的概念、数据结构定义、基本算法实现以及算法的性能分析等知识，掌握链表的相关应用方法，在此基础上掌握链串的相关知识。

通过这一章我学习了另一种数据结构——链表，在逻辑结构上，链表与顺序表一样，也是线性逻辑结构；单链表借助“地址”的概念，使用了链式存储结构，产生了一种新的数据结构——链表，链表的基本操作是地址运算，在此基础上构成的链表基本算法的特点也就不同，从链表算法的功能看，链表的基本运算与顺序表基本相同，但实现方法和过程与顺序表是不同的，链表可分为静态链表和动态链表两种。这一章我学习到的实际应用是链表的创建、插入和删除等基本操作。循环链表的建立和查询方法。

第四章主要知识点是在两种不同的存储结构下设计的堆栈，即顺序栈和链栈。主要内容是顺序栈和链栈的概念、数据类型、数据结构定义和基本运算算法及其性能分析。通过对本章的学习，要求掌握顺序栈及链栈的数据类型描述、数据结构、基本算法及其性能分析等知识。在此基础上，了解堆栈的相关应用，掌握应用堆栈解决实际问题的思想及方法。

通过对这一章的学习，我了解了堆栈的概念，堆栈的原理、创建方法以及使用方式。“后进先出”是其基本原则。利用堆栈可以轻松方便的解决对称问题以及括号匹配等问题。堆栈与顺序表、链表不同的是，堆栈只能对一端的数据元素进行操作，即只在栈顶进行元素的插入和删除。掌握顺序栈和链表的存储结构是学习堆栈的要素之一。堆栈是一类常用的数据结构，被广泛应用于各种程序设计中。

第五章的重点知识是在顺序存储和链接存储下的两种队列——顺序（循环）队列和链队。

列的数据结构、基本运算及其性能分析以及应用。通过本章的学习，要求掌握顺序队列（重点是循环队列）及链队列的概念、数据类型描述、数据结构、基本算法及其性能分析等知识。在此基础上，了解队列的相关应用，掌握应用队列来解决实际问题的思想及方法。

通过这一章的学习，我掌握了队列的定义，概念，创建以及“对头删除”，“队尾插入”的原则。重点了解了判断循环队列空和满的判断条件。同堆栈一样，队列也是一种具有线性逻辑结构、运算受限制的数据结构。与堆栈只在一端（栈顶）进行元素的插入和删除运算不同的是，队列是在对头进行插入，而在队尾完成数据元素的删除，所以队列的算法和适用的应用问题与堆栈有很大的区别。队列作为一类常用的数据结构，被广泛应用于各种程序设计中。

第六章主要学习数组、系数矩阵和广义表的基本概念、集中特殊矩阵的存储结构及基本运算，在此基础上学习特殊矩阵的计算算法与广义表应用等相关问题。通过本章的学习，要求掌握特殊矩阵的压缩存储结构，在该存储结构下元素的定位方法，理解稀疏矩阵的计算和广义表的存储结构及其基本运算。了解矩阵与广义表的相关应用。

通过这章的学习和前几章的比较，我了解到前几章的线性结构中的数据元素都是非结构的原子类型，即每一个元素都是不可再分解的。本章讨论的数组和广义表等数据结构可以看成是在前几章线性结构基础上的一个扩展：组成该数据结构的数据元素本身也是一个数据结构。矩阵计算应该数值计算方面的问题，由于矩阵和数组的关系以及特殊矩阵存储结构的复杂性，进而使得特殊矩阵的存储结构和算法也表现出其特殊性，所以数据机构课程应该解决其计算问题。

第七章的学习重点是二叉树的概念、数据类型、数据结构定义和各种基本算法，在此基础上介绍二叉树的一些应用问题。通过本章的学习，我掌握了二叉树概念及其性质、二叉树的逻辑结构和存储结构等知识，掌握二叉树的建立、遍历、线索化等基本概念和算法及性能分析，能熟练应用二叉树这章结构来解决一些实际问题，如哈夫曼树及哈夫曼编码、查找与排序（二叉树排序）等问题。了解堆栈排序及其算法等知识。二叉树是非线性数据结构，是树形结构的一种特殊形式。在现实生活有许多数据关系可抽象为树或二叉树的形式。本章中的二叉树的概念及其性质、二叉排序树、存储结构、遍线索（化）、基本算法为重点内容，二叉排序树的应用为难点内容。

第八章的学习重点是树和森林的数据结构、基本算法及其性能分析，树和森林与二叉树间的转化算法等，在此基础上介绍树的应用——b-树。通过本章的学习，我掌握了树和森林的概念和性质、数据结构、树的基本算法及性能分析、树与二叉树间的转换及其算法，并能应用b-树来实现数据元素的动态查找。舒适一种非线性结构，它在二叉树的基础上做了更为一般化的扩展，而森林是树的集合。在树结构中，每一个元素最多只有一个前驱，但可能有多个后继。现实生活中的家族关系、单位的组成结构等，均可抽象为树的形式。

第九章学习重点是散列结构的相关知识，学习常用的散列函数和冲突处理方法，散列表的常用算法及其性能分析，通过本章的学习，我掌握了散列结构和散列函数的相关概念，掌握散列结构的存储（散列表）的相关概念，要求掌握散列冲突处理方法（散列法）的相关知识，并能灵活运用散列法解决应用问题。

散列结构是使用散列函数建立数据结点关键字与存储地址之间的对应关系并提供多种当数据节点存储地址发生“冲突”时的处理方法而建立的一种数据结构。散列结构的查找等运算效率是很高的，本章中的散列函数、散列结构、散列表、散列法的基本概念和基本算法是重点，线性探测散列算法、链地址法散列算法和散列法的应用是难点。

第十章的学习重点是图的定义及性质，图的四种存储结构，图的两种遍历算法以及图的典型应用，包括最小生成树、最短路径、拓扑排序和关键路径等。通过本章学习，我掌握了图的概念和基本性质，图的存储结构（邻接矩阵和邻接表）及其基本算法、图的遍历及算法、图的最小生成树普利姆算法或者克鲁斯卡尔算法、图的最短路径迪杰斯特拉算法和弗洛伊德算法、有向无环图拓扑排序算法。了解了图的逆邻接表、十字链表、邻接多重表存储结构及其基本算法、关键路径求解算法，并能灵活运用图的不同的数据结构和遍历算法解决复杂的应用问题。

二．课程学习体会。

在学习开始的时候，老师就明确提出它不是一种计算机语言，不会介绍c语言的变成语言，而是通过学习可以设计出良好的算法，高效地组织数据。一个程序无论采用何种语言，其基本算法思想不会改变。联系到在大一和大二上学期学习的c和c++语言，我深刻认识到了这一点。“软件开发好比写作文，计算机语言提供了许多华丽的辞藻，而数据结构则考虑如何将这些辞藻组织成一篇优秀的文章来。”在学习这门课中，要熟悉对算法思想的一些描述手段，包括文字描述、图形描述和计算机语言描述等。因此，计算机语言基础是必须的，因为它提供了一种重要的算法思想描述手段——机器可识别的描述。

这门课结束之后，我总结了学习中遇到的一些问题，最为突出的，书本上的知识与老师的讲解都比较容易理解，但是当自己采用刚学的知识点编写程序时却感到十分棘手，有时表现在想不到适合题意的算法，有时表现在算法想出来后，只能将书本上原有的程序段誊写到自己的程序中再加以必要的连接以完成程序的编写。针对这一情况，我会严格要求自己，熟练掌握算法思想，尽量独立完成程序的编写与修改工作，只有这样，才能够提高运用知识，解决问题的能力。

1、建议在上课过程中加大随堂练习的分量，以便学生能当堂消化课堂上学习的知识，也便于及时了解学生对知识点的掌握情况，同时有助于学生上课积极思考，不会开小差。

2、建议在课时允许的情况下，增加习题课的分量，通过课堂的习题讲解，加深对知识点的掌握，同时对各知识点的运用有一个更为直观和具体的认识。

以上便是我对《数据结构与算法》这门课的学习总结，我会抓紧时间将没有吃透的知识点补齐。今后我仍然会继续学习，克服学习中遇到的难关，在打牢基础的前提下向更深入的层面迈进！

数据结构与算法篇五

课程设计是《数据结构》课程的一个重要的实践环节，它可加深学生对该课程所学内容的进一步的理解与巩固，达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，培养基本的对基本数据结构的理解和运用，良好的程序设计方法、提高编码及调试程序技能的能力，为整个专业的学习以及软件设计水平的提高打下良好的基础。

二、设计内容。

每位学生可以从《数据结构课程设计备选题目》中选择一个题目自行完成。要求每班中题目不能重复。

三、设计要求。

1.学生必须仔细阅读《数据结构课程设计任务书》，认真主动完成课设的要求。有问题及时主动通过各种方式与指导教师联系沟通。

2.学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时向教师汇报。

3.课程设计按照教学要求需要两周时间完成，学院安排设计时。

间学生不得缺席。

4、每位学生必须认真、独立完成设计任务，发现抄袭者或雷同者，一律按零分处理。

5、程序设计语言可选择c或c++。

6、程序要正确且具有一定的健壮性，不会因为用户的输入错误引起程序运行错误而中断执行，对输入值的类型、大小范围、字符串的长度等，进行正确性检查，对不合法的输入值给出出错信息，指出错误类型，等待重新输入。

四、上交相关内容要求。

上交的成果的内容必须由以下三个部分组成，缺一不可。

3．课程设计报告：（保存在word文档中，文件名要求按照“学号_姓名_课程设计报告题目”起名，如文件名为“001_张三_二叉树动态演示”.doc）。报告要求文字工整通顺、图表规范、思路清楚、内容正确。设计报告必须按照规定格式规范，a4纸双面打印、装订。

将以上三个部分放在一个文件夹里，文件夹名要求按照"学号_姓名_课程设计报告题目”.zip命名。每个班将所有学生的文件夹收集起来刻成光盘上交。

五、时间安排。

设计时间为两周（7.07—7.18），7月16日—7月18日答辩。考核方式。

成绩按五分制，包括课程设计过程、课程设计结果、课程设计报告三部分。其中：

课程设计过程：20%。

包括设计态度（10分）、出勤（10分）。

课程设计结果：40%。

其中：程序正确性：30分，运行效果：10分，答辩：10分。课程设计报告：40%。

其中：正确性：20分，完整性：10分，规范性：10分。

六、设计报告格式。

数据结构与算法篇六

数据结构与算法是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且也已经成为其他理工专业的热门选修课。随着高级语言的发展，数据结构在计算机的研究和应用中已展现出强大的生命力，它兼顾了诸多高级语言的特点，是一种典型的结构化程序设计语言，它处理能力强，使用灵活方便，应用面广，具有良好的可移植性。通过学习，先报告如下：

第一章的内容主要包括有关数据、数据类型、数据结构、算法、算法实现、c语言使用中相关问题和算法分析等基本概念和相关知识。其中重点式数据、数据类型、数据结构、算法等概念；c语言中则介绍了指针、结构变量、函数、递归、动态存储分配、文件操作、程序测试与调试问题等内容。

第二章主要介绍的是线性逻辑结构的数据在顺序存储方法下的数据结构顺序表（包括顺序串）的概念、数据类型、数据结构、基本运算及其相关应用。其中重点一是顺序表的定义、数据类型、数据结构、基本运算和性能分析等概念和相关知识。二是顺序表的应用、包括查找问题（简单顺序查找、二分查找、分块查找）、排序问题（直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、归并排序）、字符处理问题（模式匹配）等内容。本章重点和难点在查找和排序问题的算法思想上，6种排序方法的性能比较。

第三章主要介绍的是线性逻辑结构的数据在链接存储方法下数据结构链表的相关知识。主要是单链表、循环链表的数据类型结构、数据结构、基本运算及其实现以及链表的相关应用问题，在此基础上介绍了链串的相关知识。在应用方面有多项式的相加问题、归并问题、箱子排序问题和链表在字符处理方面的应用问题等。本章未完全掌握的是循环链表的算法问题和c的描述。

第四章介绍在两种不同的存储结构下设计的堆栈，即顺序栈和链栈的相关知识，了解堆栈的相关应用，掌握应用堆栈来解决实际问题的思想及方法。本章主要内容是顺序栈和链栈的概念、数据类型、数据结构定义和基本运算算法及其性能分析。本章堆栈算法思想较为简单，所以能较好掌握。

第五章主要介绍顺序存储和链接存储方法下的两种队列、顺序（循环）队列和链队列的数据结构、基本运算及其性能分析以及应用。顺序队列(重点是循环队列）和链队列的概念、数据类型描述、数据结构和基本运算算法及其性能分析等。本章同堆栈有点类似，算法思想较为简单，所以能较好掌握；但难点重在循环队列队空、队满的判断条件问题。第六章“特殊矩阵、广义表及其应用”将学习数组、稀疏矩阵和广义表的基本概念，几种特殊矩阵的存储结构及其基本运算，在此基础上学习特殊矩阵的计算算法与广义表应用等相关问题。本章的重点是相关数据结构的存储结构及其基本运算算法。掌握了特殊矩阵的压缩存储结构，在该存储结构下元素的定位方法，理解了稀疏矩阵的计算和广义表的存储结构。

第七章“二叉树及其应用”的知识结构主要是：非线性结构数据二叉树的定义、性质、逻辑结构、存储结构及其各种基本运算算法，包括二叉树的建立、遍历、线索化等算法。在此基础上，介绍二叉树的一些应用问题，包括哈夫曼编码问题、（平衡）二叉排序树问题和堆排序问题等。

第八章“树和森林及其应用”介绍树和森林的数据结构、基本算法及其性能分析，树和森林与二叉树之间的转换算法等，在此基础上介绍树的应用---b-树，应用b-树来实现数据元素的动态查找。本章基本掌握树和森林的概念和性质、数据结构、树的基本算法及性能分析，树和二叉树间的转换及其算法，并用应用b-树来实现数据元素的动态查找未能掌握好。

第九章“散列结构及其应用”是逻辑结构“集合型”的数据元素在散列存储方法下的数据结构及其应用知识内容。主要介绍散列函数的概念、散列结构的概念、散列存储结构的概念---散列表、散列函数和散列表中解决冲突的处理方法---开放定址法、链地址法以及散列表的基本算法及其性能分析。本章概念较为多，所以掌握不太好。

第十章“图及其应用”是逻辑结构为“图形”的数据结构及其应用知识内容，主要介绍图的定义和基础知识，图的2种存储结构。图的基本算法以及图的典型应用问题（最小生成树、最短路径、拓扑排序和关键路径等）。

二、对各知识点的掌握情况。

我对各知识点的掌握情况总结如下：

第一章不太难，能基本掌握。但关系全书的时间性能分析有些未能全部掌握。第二章本章重点和难点在查找和排序问题的算法思想上，6种排序方法的性能比较。本章未掌握的为希尔排序、快速排序、归并排序的时间复杂度分析。第三章，对链表掌握还好，对其数据结构进行了分析，有循环链表，掌握的不是很好，对其中一些用法不熟练。第四章堆栈，本章堆栈算法思想较为简单，所以能较好掌握，但表达式计算问题未掌握好的。第五章的循环队列队空、队满的判断条件问题掌握的不是很好。第六章的重点是相关数据结构的存储结构及其基本运算算法。掌握了特殊矩阵的压缩存储结构，在该存储结构下元素的定位方法，理解了稀疏矩阵的计算和广义表的存储结构。第七章对二叉树掌握较好，其概念，存储，遍历有很好的掌握。就是对二叉排序树有点生疏，它的生成算法不是很会。第八章树树与二叉树之间的转换，森林与二叉树的转换算法思想基本掌握。第九章散列的一些知识，没有深入学习，大概了解了散列存储结构散列表，散列函数，冲突的处理方法。第十章了解了图的逆邻接表的存储结构，关键路径求解算法未能掌握好，不能灵活运用图的不同数据结构和遍历算法解决复杂的应用问题。

三、学习体会。

通过学习数据结构与算法，让我对程序有了新的认识，也有了更深的理解。同时，也让我认识到，不管学习什么，概念是基础，所有的知识框架都是建立在基础概念之上的，所以，第一遍看课本要将概念熟记于心，然后构建知识框架。并且，对算法的学习是学习数据结构的关键。在第二遍看课本的过程中，要注重对算法的掌握。对于一个算法，读一遍可能能读懂，但不可能完全领会其中的思想。掌握一个算法，并不是说将算法背过，而是掌握算法的思想。我们需要的是耐心。每看一遍就会有这一遍的收获。读懂算法之后，自己再默写算法，写到不会的地方，看看课本想想自己为什么没有想到。对算法的应用上，学习算法的目的是利用算法解决实际问题。会写课本上已有的算法之后，可以借其思想进行扩展，逐步提高编程能力。

四、对课程教学的建议。

1、感觉上课时的气氛不是很好，虽然大部分人都在听，可是效果不是很好。所以希望老师能在授课中间能穿插一些活跃课堂氛围的话题，可以是大家都非常关心的一些内容，这样既让大家能在思考之余有一个放松，也能够提高学生的学习积极性和学习效率。

2、学习的积极性很重要，有时候我们花了很长时间去写实验报告，也很认真的去理解去掌握，可是最后实验报告可能就只得了一个c，抄的人反而得a，这样的话很容易打击学生的积极性，在后面的实验报告中没动力再去认真写。所以希望老师能在这方面有所调整。

3、虽然讲课的时间很紧，但是还是希望老师能在讲述知识点的时候能运用实际的调试程序来给我们讲解，这样的话能让我们对这些内容有更深刻的印象和理解。

数据结构与算法篇七

计算机技术已成为现代化发展的重要支柱和标志，并逐步渗透到人类生活的各个领域。随着计算机硬件的发展，对计算机软件的发展也提出了越来越高的要求。由于软件的核心是算法，而算法实际上是对加工数据过程的描述，所以研究数据结构对提高编程能力和设计高性能的算法是至关重要的。

非数值计算问题的数学模型不再是传统的数学方程问题，而是诸如表、树、图之类的数据结构。因此，简单地说，数据结构是一门研究非数值计算的程序设计问题的学科，主要研究数据的逻辑结构、存储结构和算法。

一、教学目的与要求---了解数据的逻辑结构和物理结构；

教学要求在每章教学内容给出，大体上为三个层次：了解、掌握和熟练掌握。他们的含义大致为：了解是正确理解概念，掌握是学会所学知识，熟练掌握就是运用所学知识解决实际问题。

教学目的为：了解算法对于程序设计的重要性；学习掌握基本数据结构的描述与实现方法，熟练掌握典型数据结构及其应用算法的设计。了解算法分析方法。

二、教学重点与难点--数据结构中基本概念和术语，算法描述和分析方法。

1、链表插入、删除运算的算法。算法时间复杂度。

2、后缀表达式的算法，数制的换算。

利用本章的基本知识设计相关的应用问题。

3、循环队列的特点及判断溢出的条件。

利用队列的特点设计相关的应用问题。

4、串的模式匹配运算算法。

5、二叉树遍历算法的设计。

利用二叉树遍历算法，解决简单应用问题哈夫曼树的算法。

6、图的遍历。

最小生成树。

最短路径。

7、二叉排序树查找。

平衡树二叉树。

8、堆排序。

快速排序归并排序。

四、教学内容、目标与学时分配。

教学内容教学目标课时分配。

1、绪论。

逻辑结构与存储结构。

算法和算法分析。

2、线性表。

线性表的定义与运算。

线性表的顺序存储。

线性表的链式存储。

3、栈。

栈的定义与运算。

栈存储和实现。

栈的应用举例。

4、队列。

队列的定义与基本运算。

队列的存储与实现。

队列的应用举例。

5、串。

串的定义与基本运算。

串的表示与实现。

串的基本运算。

6、树和二叉树。

树的定义和术语。

二叉树树的基本概念和术语遍历二叉数和线索二叉树。

二叉树的转换。

二叉树的应用。

哈夫曼树及其应用。

7、图。

图的定义和术语。

图的存储结构。

图的遍历算法。

图的连通性。

8、查找。

查找的基本概念与静态查找动态查找。

哈希表。

了解。

了解。

掌握。

熟练掌握顺序表存储地址的计算。

掌握单链表的结构特点和基本运算。

掌握双链表的结构特点和基本运算。

掌握栈的定义与运算。

掌握栈的存储与实现。

熟练掌握栈的各种实际应用。

掌握队列的定义与基本运算。

熟练掌握队列的存储与实现。

掌握循环队列的特征和基本运算。

了解串的逻辑结构。

掌握串的存储结构。

熟练掌握串的基本运算。

了解。

了解二叉树。

熟练掌握二叉树定义和存储结构。

了解二叉树的遍历算法。

掌握。

掌握哈夫曼的建立及编码。

了解。

了解。

熟练掌握。

熟练掌握。

了解。

熟练掌握。

了解哈希表与哈希方法。

4学时。

1学时。

1学时。

2学时。

8学时。

2学时。

2学时。

4学时。

8学时。

2学时。

2学时。

4学时。

6学时。

2学时。

2学时。

2学时。

6学时。

2学时。

2学时。

2学时。

12学时。

2学时。

2学时。

2学时。

2学时。

2学时。

2学时。

8学时。

2学时。

2学时。

2学时。

2学时。

8学时。

4学时。

2学时。

2学时。

9、排序。

12学时插入排序。

熟练掌握基本思想。

3学时快速排序。

了解各种内部排序方法和特点。

3学时选择排序。

掌握。

2学时各种排序方法比较。

掌握。

2学时。

实验内容实验目标课时分配算法编程实验：

1、用指针方式编写程序复习c（c++）语言指针、结构体等的用法。

2、对单链表进行遍历。

链表的描述与操作实现。

3、栈及其操作。

描述方法及操作。

4、编写串子系统1串的特点及顺序定长存储、操作、查找。

5、编写串子系统2串的特点及顺序定长存储、操作、查找。

6、编写树子系统1二叉树的特点及存储方式、创建、显示、遍历等。

7、编写树子系统2二叉树的特点及存储方式、创建、显示、遍历等。

8、图子系统。

图的邻接矩阵的存储、遍历、广度/深度优先搜索。

9、查找子系统。

理解查找基本算法、平均查找长度、静态、动态查找等。

五、考试范围与题型。

1、考试范围与分数比例。

1)绪论。

12%2)线性表。

17%3)栈。

7%4)队列。

6%5)串。

4%6)树和二叉树。

14%7)图。

15%8)查找。

4%9)排序。

21%。

2、考试题型与分数比例。

1)名词解释。

18%2)判断对错。

16%3)填空。

16%4)单项选择。

18%5)应用。

32%。

六、教材与参考资料。

1、教材：实用数据结构基础（谭浩强）中国铁道出版社。

2、参考资料：数据结构（严蔚敏）清华大学出版社。

（撰写人：

审核人：2学时2学时2学时2学时2学时2学时2学时2学时2学时）。

数据结构与算法篇八

谈到计算机方面的专业课程，我觉得数据结构算是一门必不可少的课了，它是计算机从业和研究人员了解、开发及最大程度的利用计算机硬件的一种工具。数据结构与算法分析是两门紧密联系的课程,算法要靠好的数据结构来实现,二者的关系是密不可分的,谈到算法不得不讲数据结构,谈数据结构也不可避免的要了解算法,好的算法一定有一个好的数据结构，很多算法实际上是对某种数据结构实行的一种变换,研究算法也就是研究在实行变换过程中数据的动态性质。这两门课程分别是我在大二和研一的时候学的，因为它们密切的联系，这里将其放在一起总结如下。

什么是数据结构呢？研究数据的逻辑结构和存储结构（物理结构）以及它们之间的关系，且为该结构定义相应的运算设计相应的算法。这里的数据是指可输入到计算机能被程序处理的符号的集合。其中，数据的逻辑结构是指数据之间逻辑关系的描述，逻辑结构的分类有线性结构、树形结构和图结构。数据的存储结构是指数据在计算机中存储结构，也称为物理结构，它有4类基本的存储映射方法：1.顺序的方法；2.链接的方法；3.索引的方法；4.散列的方法。在程序设计语言中，数据结构直接反映在数据类型上，比如一个整型变量就是一个节点，根据类型给他分配内存单元。抽象数据类型：一组值以及在这些值上定义的操作集合，它是描述数据结构的一种理论工具，其特点是把数据结构作为独立于应用程序的一种抽象代数结构。

线性表结构：由一系列元素组成的有序的序列，除了第一个元素和最后一个元素外，每个元素都只有一个直接前趋和直接后继，元素的个数称为线性表的长度。它的存储方式有顺序存储和链式存储。顺序存储方式它的优点是存储单元是连续的，适合快速访问元素内容，链表的特点是动态申请内存空间，并通过指针来链接结点，按照线性表的前驱关系把一个个结点链接起来，这样可以动态地根据需要分配内存空间，经常用于插入新结点或删除节点的需要，链表还可以根据结点中指针个数分为单链表、双链表、循环链表等。在线性表结构中有两类特别的线性表：栈和队列。栈是一种限制访问端口的线性表，常称为后进先出表。正是这种特殊的性质使得栈的用途非常广泛，比如在计算表达式的值时处理运算符的先后次序，另外一个大的用处就是递归了，hanoi塔就是最典型的用了递归的思想，在算法中，也有很多运用递归思想的例子。队列也属于限制访问点的线性表，它的特点就是加入和删除元素都只能在队列的一端进行，即队列首出，队列尾进，最大的特点是先来先服务，先进先出。因为这个特点，队列常被用作消息缓冲器。

在算法设计中，顺序表主要用于检索，而利用栈中的递归思想在算法中则应用非常广泛，如递归排序，分治算法等。

树结构：是一种非常重要的非线性数据结构，它是由一个根结点和若干叶结点组成的树状结构，除了根结点每个结点只能有一个父节点，可以有若干子结点，若干个树结构还可以构成森林，树的存储结构也分为顺序存储和链式存储，最典型的是左孩子右兄弟法。在树结构中比较重要的算法就是周游（遍历）树，有先根次序、后根次序以及中根次序。树结构中有几类非常重要的特殊树结构，如二叉树，b树，b+树等，其中，二叉树应用最为广泛。

二叉树：是指每个结点最多有两个子结点的树结构，具体细分，根据叶子结点的特性可分为满二叉树、完全二叉树等。二叉树的遍历也分为深度优先和广度优先。另外，二叉树有几条非常重要的性质，这也使得它的应用非常广泛。

在算法设计中，典型的利用树的深度优先遍历的算法是回溯法，而典型的广度优先搜索算法是分枝定界法。

图：是一种较线性表和树更为复杂的数据结构。一般来讲，数据的逻辑结构可表示为结点的有穷集合k和k上的一个关系r,如果对k中结点相对于r的前驱、后继个数加以限制，则可以分别定义线性结构、树形结构和图结构，即：

图结构：不限制前驱的个数，亦不限制后继的个数，反映一种网状关系。

通常用g=(v,e)代表一个图，其中v是顶点集，e是边集。图分为有向图和无向图，图的存储方式有邻接表和邻接矩阵法。和树类似的，图中也需要周游，同样有深度优先搜索和广度优先搜索，而比树的周游要更复杂，也更重要。在这一块中，有两种比较典型的求最短路径和最小支撑树的算法需要注意，它们分别是dijkstra算法和prim算法。另外需要注意的是图的连通性。

在算法设计中，典型的用到图论的算法有贪心算法和动态规划算法。

（1）输入：有零个或多个由外部提供的量作为算法的输入。（2）输出：算法产生至少一个量作为输出。

（3）确定性：组成算法的每条指令是清晰的，无歧义的。（4）有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。

我们研究一个算法或者评价一个算法主要是通过估计该算法的复杂性，包括时间复杂性和空间复杂性。空间复杂性是指使用该算法的程序在运行时需要占用多少内存空间，具体包括指令空间、数据空间和环境栈空间。时间复杂性是指执行该程序所需要的时间量级，通常是估算的时间，包括编译时间和运行时间。同时评价一个算法的好坏还要看其时间复杂性和空间复杂性随着输入规模的增长趋势，一般能接受的最好是线性增长。在算法设计这本书中，每介绍一个算法都会分析其算法复杂度，由此可看出它的重要性。

首先，从递归的分治算法开始。分治算法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归的解这些子问题，然后将各个子问题的解合并得到原问题的解。该算法的主要应用有大整数乘法，矩阵乘法、合并排序等。可以大大降低算法的时间复杂度，但使用递归栈可能增加程序的空间规模。

动态规划算法和贪心算法：与分治算法类似，动态规划的基本思想也是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治算法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。动态规划算法适用于解最优化问题。通常可按以下4个步骤：

（1）找出最优解的性质，并刻画其结构特征。（2）递归的定义最优值。

（3）以自底向上的方式计算出最优值。

（4）根据计算最优值时得到的信息，构造最优解。

动态规划算法的基本要素是最优子结构性质和子问题重叠性质。

最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

子问题重叠性质。子问题重叠性质是指在用递归演算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

另外一点要素是备忘录方法，它作为动态规划算法的变形，用表格保存已解决问题的答案，在下次需要解此子问题时，只要简单查看子问题的解答，而不必重新计算。与动态规划不同的是备忘录方法的递归是自顶向下的，而动态规划则是自底向上的。

动态规划算法设计策略典型的应用案例有：矩阵连乘、最大字段和、流水作业调度等。有时满足动态规划条件的问题可以有更好的算法，比如贪心算法。贪心算法即总是做出在当前看来是最好的选择。也就是说贪心算法并不从整体最优上加以考虑，它所做的总是做出的选择只是在某种意义上的局部最优。这种启发式的策略并不能总是奏效，然而对某些特定的问题确能达到预期目的。比如活动安排的例子。

贪心算法的基本要素主要有贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法与动态规划的主要区别，它们的共同点是都要求问题具有最优子结构性质。

贪心算法的典型案列是：活动安排、最优装载问题、最短路径和最优生成树问题。回溯法和分枝定界法：回溯法有“通用的解题法”之称。用它可以系统的搜索一个问题的所有解或任一解。它在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。其算法框架包含递归回溯和迭代回溯，两个特别的解空间树为子集树和排列树。典型的回溯法的案例有：批处理作业调度、图的m着色、旅行售货员问题、0-1背包问题等。

分枝定界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分治定界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有的解，而分枝定界法的求解目标则是找出满足约束条件的一个解，或是满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。由于求解目标不同，导致分支定界法与回溯法对解空间的搜索方式也不相同。回溯法以深度优先的方式搜索解空间，而分枝定界法则以广度优先或以最小耗费优先的方式搜索解空间。

另外，在算法分析中一定要提的是np问题。首先需要介绍p(polynomial,多项式)问题.p问题是可以在多项式时间内被确定机(通常意义的计算机)解决的问题。np(non-deterministicpolynomial,非确定多项式)问题,是指可以在多项式时间内被非确定机(他可以猜,他总是能猜到最能满足你需要的那种选择,如果你让他解决n皇后问题,他只要猜n次就能完成----每次都是那么幸运)解决的问题.这里有一个著名的问题----千禧难题之首,是说p问题是否等于np问题,也即是否所有在非确定机上多项式可解的问题都能在确定机上用多项式时间求解。

np完全(npcomplete,npc)问题是指这样一类np问题,所有的np问题都可以用多项式时间划归到他们中的一个。所以显然np完全的问题具有如下性质:它可以在多项式时间内求解，当且仅当所有的其他的np－完全问题也可以在多项式时间内求解。这样一来,只要我们找到一个npc问题的多项式解,所有的np问题都可以多项式时间内划归成这个npc问题,再用多项式时间解决,这样np就等于p了。

小结一下，在算法设计这么课中学了这么几大类典型的算法，里面也涉及到具体的应用案例，但我觉得学算法的目的远不是学会这几种固定的特殊问题的解法而已，事实上领会这些巧妙算法背后的思想然后学会迁移到其他新的问题中去才是领会了算法设计的精髓。

数据结构与算法篇九

（一）课程性质。

《数据结构》是一门专业基础课，在计算机软件的各个领域中均会使用到数据结构的有关知识。本课程的先修课程为c程序设计或c++程序设计。

（二）教学目的。

学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法，并初步掌握时间和空间分析技术。另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，要求学生会书写符合软件工程规范的文件，编写的程序代码应结构清晰、正确易读，能上机调试并排除错误。

（三）教学时数。

课堂讲授每周4学时，18周，共72学时。

（四）教学方法。

本课程将采用课堂讲授及课堂讨论相结合的交互式教学法，同时辅以必要的上机操作实践。

（五）面向专业。

计算机科学与技术专业。

二、教学内容。

第一章绪论。

（一）教学目的要求。

介绍数据结构的一些基本概念，算法的时间复杂度和空间复杂度的分析方法，抽象数据类型的定义和使用以及算法的描述方法。掌握数据结构的一些基本概念，掌握算法的时间复杂度和空间复杂度的分析方法，了解抽象数据类型的定义和使用，了解算法的描述方法。

（二）教学内容。

主要内容：数据结构的一些基本概念：数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法等。抽象数据类型。算法时间复杂度和空间复杂度的分析。

教学重点：有关数据结构的各个名词和术语的含义，以及语句频度和时间复杂度、空间复杂度的估算。

教学难点：算法时间复杂度和空间复杂度的分析。

第一节。

一、非数值计算。

第二节。

一、数据。

三、数据类型。

四、抽象数据类型。

五、多型数据类型。

第三节。

一、固有数据类型。

基本概念和术语什么是数据结构。

二、数据抽象。

三、抽象数据类型的描述语言。

第四节。

一、算法。

二、算法设计的要求。

三、算法效率的度量。

四、算法的存储空间需求。

（三）教学方法与形式。

课堂讲授、多媒体课件。

（四）教学时数。

4学时。

第二章线性表。

（一）教学目的与要求。

介绍线性表的基本概念和类型定义，对顺序表和单链表的常用操作方法及其程序实现，循环链表和双向链表的定义和它的插入、删除等操作方法。掌握线性表的基本概念和类型定义；熟练掌握对顺序表和单链表的常用操作方法及其程序实现；掌握循环链表和双向链表的定义和它的插入、删除等操作方法。

（二）教学内容。

主要内容：线性表的基本概念和类型定义，线性表的顺序存储结构，线性表的链接存储结构：（1）单链表的查找、插入和删除；（2）循环链表；（3）双向链表。

教学重点：在顺序表和链表上各种基本算法的实现及相关的时间性能分析。

教学难点：用所学的基本知识设计有效算法解决与线性表相关的应用问题。链表要分清链表中指针p和结点*p之间的对应关系，区分链表中的头结点、头指针以及循环链表、双向链表的特点等。

第一节。

一、线性表的定义。

二、线性表的基本操作。

第二节。

一、顺序表。

二、顺序表上基本运算的实现。

三、顺序表应用举例。

第三节。

一、线性链表。

二、循环链表。

三、双向链表。

四、静态链表。

第四节一、一元多项式的数学表示二、一元多项式的计算机表示。

三、抽象数据类型：一元多项式的定义。

四、抽象数据类型：一元多项式的存储结构。

五、抽象数据类型：一元多项式的基本操作算法实现。

（三）教学方法与形式。

一元多项式的表示及相加线性表的链式存储表示和实现线性表的顺序存储表示和实现。

线性表的类型定义算法和算法分析课堂讲授、多媒体课件。

（四）教学时数。

8学时。

第三章栈和队列。

（一）教学目的与要求。

介绍栈和队列的定义，顺序和链接存储的栈和队列的各种运算的方法及其程序实现。掌握栈和队列的定义，熟练掌握顺序和链接存储的栈和队列的各种运算的方法及其程序实现。

（二）教学内容。

主要内容：栈的类型定义，栈的顺序存储和链接存储的表示，在栈的顺序存储和链接存储上进行各种栈操作的算法，栈的应用举例，队列的类型定义，队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。

教学重点：栈和队列在两种存储结构上实现的基本运算。教学难点：递归的实现、循环队列中对边界条件的处理。

第一节。

一、抽象数据类型栈的定义。

二、栈的表示和实现。

第二节。

一、数制转换。

二、括号匹配的检验。

三、表达式求值。

第三节。

一、函数调用与栈。

二、递归调用栈的变化。

第四节。

一、抽象数据类型队列的定义。

二、链队列--队列的链式表示和实现。

三、循环队列--队列的顺序表示和实现。

第五节。

一、优先级队列的概念。

二、优先级队列的存储表示和实现。

（三）教学方法与形式。

课堂讲授、多媒体课件。

（四）教学时数。

4学时。

第四章串。

（一）教学目的与要求。

介绍串的基本概念和操作，串的存储结构以及基本操作的算法实现。掌握串的基本概念和操作，掌握串的存储结构以及基本操作的算法实现。

（二）教学内容。

主要内容：串的类型定义，串的表示和实现，正文模式匹配，正文编辑——串操作应用举例串的类型定义。

教学重点：串类型定义中各基本操作的定义以及串的实现方法。教学难点：利用串的基本操作来实现串的其它操作。

优先级队列队列栈与递归的实现栈的应用举例。

栈

第一节。

一、串的定义。

二、串的基本操作。

第二节。

一、定长顺序存储表示。

二、堆分配存储表示。

三、串的块链存储表示。

四、字符串操作的实现。

第三节。

二、模式匹配的一种改进算法。

（三）教学方法与形式。

课堂讲授、多媒体课件。

（四）教学时数。

4学时。

串的类型定义。

串的表示和实现。

字符串的模式匹配。

一、求子串位置的定位函数index（s，t，pos）。

第五章数组和广义表。

（一）教学目的。

介绍数组的基本概念和基本操作的算法实现；稀疏矩阵的定义和各种存储结构，稀疏矩阵的转置和相加的方法并了解其算法；广义表的定义、存储结构和求广义表的长度及深度的算法，建立广义表和输出广义表的方法并了解其算法。掌握数组的基本概念和基本操作的算法实现；掌握稀疏矩阵的定义和各种存储结构，掌握稀疏矩阵的转置和相加的方法并了解其算法；掌握广义表的定义、存储结构和求广义表的长度及深度的算法，掌握建立广义表和输出广义表的方法并了解其算法。

（二）教学内容。

主要内容：稀疏矩阵的定义、存储和运算，广义表的定义、存储和运算串的类型定义。教学重点：特殊矩阵的压缩存储，以及稀疏矩阵的三元组顺序表示。教学难点：特殊矩阵的压缩存储，以及稀疏矩阵的三元组顺序表示。

第一节第二节。

一、数组的存储方式。

二、数组元素存储位置的计算。

三、基本操作的实现。

第三节。

一、特殊矩阵。

二、稀疏矩阵。

第四节。

一、广义表的基本概念。

二、广义表的三个重要结论。

第五节。

一、头尾链表存储表示。

二、扩展线性链表存储表示。

第六节。

一、求广义表的深度。

二、复制广义表。

三、建立广义表的存储结构。

（三）教学方法与形式。

课堂讲授、多媒体课件。

（四）教学时数。

6学时。

第六章树和二叉树。

（一）教学目的与要求。

介绍树的定义、性质、存储结构及遍历算法，握二叉树的各种遍历方法及其实现，二叉树的其他操作方法及实现，树、森林和二叉树的转换方法，哈夫曼树的定义和构造哈夫曼树的方法，哈夫曼树编码的方法。掌握树的定义、性质、存储结构及遍历算法，熟练掌握二叉树的各种遍历方法及其实现，掌握二叉树的其他操作方法及实现，掌握树、森林和二叉树的转换方法，掌握哈夫曼树的定义和构造哈夫曼树的方法，了解哈夫曼树编码的方法。

（二）教学内容。

主要内容：树的定义、性质和表示方法，二叉树的定义、性质和存储结构，二叉树的各种遍历方法及实现，建立二叉树、输出二叉树、求二叉树深度等的操作方法及实现，树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现，进行树与二叉树的转换方法，哈夫曼树的定义、构造哈夫曼树的方法及哈夫曼编码的方法。

教学重点：二叉树和树的遍历及其应用。

教学难点：实现二叉树和树的各种操作的递归算法。

第一节。

一、树的定义。

二、森林的定义。

三、树的抽象数据类型定义。

第二节一、二叉树的定义二、二叉树的性质三、二叉树的存储结构。

第三节。

一、遍历二叉树。

二、线索二叉树。

第四节。

一、树的存储结构。

二、森林与二叉树的转换。

三、树和森林的遍历。

第五节。

一、最优二叉树（赫夫曼树）。

二、赫夫曼编码。

（三）教学方法与形式。

课堂讲授、多媒体课件。

（四）教学时数。

10学时。

最优树和赫夫曼编码。

树和森林。

遍历二叉树和线索二叉树。

二叉树。

树的定义和基本术语。

第七章图。

（一）教学目的与要求。

介绍图的定义和术语；图的存储结构及深度和广度优先搜索方法及其实现；图的生成树的概念，求图的最小生成树的普里姆算法和克鲁斯卡尔算法并了解其实现算法；拓扑排序的方法并了解其实现算法；计算关键路径的方法及其实现算法。掌握图的定义和术语；熟练掌握图的存储结构及深度和广度优先搜索方法及其实现；掌握图的生成树的概念，掌握求图的最小生成树的普里姆算法和克鲁斯卡尔算法并了解其实现算法；掌握拓扑排序的方法并了解其实现算法；了解计算关键路径的方法并了解其实现算法。

（二）教学内容。

主要内容：图的定义和术语，图的邻接矩阵、邻接表和边集数组表示，图的深度和广度优先搜索遍历，图的生成树和最小生成树，拓扑排序。

教学重点：图在邻接矩阵与邻接表上实现的遍历算法(dfs和bfs)。教学难点：基于遍历算法的应用。

第一节。

一、图的定义。

二、无向图。

三、有向图。

四、连通图。

五、生成树。

第二节。

一、数组表示法。

二、邻接表三、十字链表。

四、邻接多重表。

第三节。

一、深度优先搜索。

二、广度优先搜索。

三、连通分量。

第四节。

一、kruskal算法。

二、prim算法。

第五节。

一、拓扑排序。

二、关键路径。

第六节。

一、从某个源点到其余各项点的最短路径。

二、每一对顶点之间的最短路径。

（三）教学方法与形式。

课堂讲授、多媒体课件。

（四）教学时数。

12学时。

最短路径有向无环图及其应用。

最小生成树图的遍历图的存储表示图的定义和术语。

第八章查找表。

（一）教学目的与要求。

介绍顺序表查找和有序表查找的方法及实现；二叉排序树和平衡二叉树的定义、对二叉排序树和平衡二叉树进行插入、删除和查找的方法和实现。哈希表的定义，构造哈希函数的多种方法，以及处理冲突的方法；b树的定义，查找、插入和删除元素的方法。熟练掌握顺序表查找和有序表查找的方法及实现；掌握二叉排序树和平衡二叉树的定义、熟练掌握对二叉排序树和平衡二叉树进行插入、删除和查找的方法和实现。掌握哈希表的定义，构造哈希函数的多种方法，以及处理冲突的方法；了解b树的定义，查找、插入和删除元素的方法。

（二）教学内容。

主要内容：顺序查找和二分查找，索引查找和分块查找，散列查找，动态查找树表。教学重点：顺序查找、二分查找、二叉排序树上查找以及散列表上查找的基本思想和算法实现。

教学难点：二叉排序树的删除算法。

第一节。

一、顺序表的查找。

二、有序表的查找。

三、静态树表的查找。

四、索引顺序表的查找。

第二节一、二叉排序树。

二、平衡二叉树。

三、动态的m路搜索树。

四、b树和b+树基本概念。

第三节。

一、什么是哈希表。

二、哈希函数的构造方法。

三、处理冲突的方法。

四、哈希表的查找及其分析。

（三）教学方法与形式。

课堂讲授、多媒体课件。

（四）教学时数。

10学时。

第九章内部排序。

（一）教学目的与要求。

介绍插入排序、交换排序、选择排序、快速排序、归并排序、基数排序的方法及其实现，快速排序、堆排序、二路归并排序的方法及其实现，各种排序方法的稳定性、时间复杂度和空间复杂度。掌握插入排序、交换排序、选择排序、快速排序、归并排序、基数排序的方法及其实现，熟练掌握快速排序、堆排序、二路归并排序的方法及其实现，掌握各种排序方法的稳定性、时间复杂度和空间复杂度。

（二）教学内容。

主要内容：排序的概念，直接插入排序，冒泡排序和快排序，直接选择排序和堆排序，归并排序。

哈希表动态查找表静态查找表教学重点：插入排序(直接插入、折半插入)、交换排序（冒泡、快速排序）、选择排序（直接选择、堆）、2-路归并排序。

教学难点：快速排序partition算法的应用和堆的调整。

第一节。

一、稳定的排序方法。

二、内部/外部排序。

三、内部排序种类。

四、排序中的基本操作。

五、排序数据的存储方式。

第二节。

一、直接插入排序。

二、其他插入排序。

三、希尔排序。

第三节。

一、起泡排序算法。

二、快速排序算法。

第四节。

一、简单选择排序。

二、树形选择排序。

三、堆排序。

第五节第六节。

一、多关键字的排序。

二、链式基数排序。

第七节。

（三）教学方法与形式。

课堂讲授、多媒体课件。

（四）教学时数。

10学时。

第十章文件。

（一）教学目的与要求。

介绍文件和记录的基本概念以及基本操作。掌握文件和记录的基本概念以及基本操作。

（二）教学内容。

主要内容：基本概念，顺序文件，索引文件，索引顺序文件，散列文件，多关键码文件。教学重点：各种文件的结构特点及其适用场合。教学难点：各种文件的结构特点及其适用场合。

第一节。

一、文件及其类别。

二、记录的逻辑结构和物理结构。

三、文件的操作。

四、文件的物理结构。

第二节。

一、顺序文件的定义。

顺序文件基本概念。

各种排序方法的综合比较。

归并排序法基数排序选择排序法交换排序法插入排序排序的定义和方法。

二、顺序文件的优缺点。

第三节。

一、索引文件的定义。

二、索引文件的特点。

第四节。

一、isam文件。

二、vsam文件。

第五节。

一、散列文件的定义。

二、散列文件的特点。

第六节。

一、多重表文件。

二、倒排文件。

（三）教学方法与形式。

课堂讲授、多媒体课件。

（四）教学时数。

4学时。

三、考核方式。

本课程的考核采用闭卷考试的方式，课程的总评成绩由平时成绩、实验成绩和期末考试成绩三部分组成，其中平时成绩占总评成绩的10%，实验成绩占总评成绩的30%，期末考试成绩占总评成绩的60%。

四、教材选用。

1、殷人昆，陶永雷，谢若阳等：《数据结构（用面向对象方法与c++语言描述）》，清华大学出版社，2007.6年第二版。

2、严蔚敏，吴伟民：《数据结构（c语言版）》及《数据结构题集（c语言版）》，清华大学出版社，2003年第一版。

多关键码文件散列文件isam文件和vsam文件。

索引文件。

数据结构与算法篇十

一、基本信息。

课程编号：e1132107课程类别：学科基础课必修课适用层次：本科。

二、教学目的。

数据结构与算法课程设计不仅是数据结构与算法课程的实践教学环节，而且是一门综合性实验项目。通过这个实验，培养学生综合运用数据结构基本知识和程序设计基本知识，解决实际问题，提高程序设计的能力和团队协作精神。

本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。

1．学生通过实践掌握线性表、树、图等数据结构的存储结构及算法实现；2．培养学生利用数据结构知识解决实际问题的能力;3．使学生初步具备查阅资料、分析设计、上机实现和书写科技报告的能力。

三、基本要求。

1.指导教师要在选题、设计、上机实现等诸环节上投入精力，加强指导、讨论和答疑的力度。尤其在选题上，要充分考虑学生目前所具有的知识水平、掌握的开发工具、以及综合设计能力的现状，使题目取材合理、大小适中、难易适度，使学生在完成设计工作后，能有所收获。2.参加课程设计的学生要珍惜机会、勤奋工作、勇于创新、勇于探索、勇于实践，虚心向指导教师请教，向同学学习，独立完成设计任务。

3.学生需保质、保量、保时间进度地提交规范的课程设计报告，审查由指导教师负责。

四、教学内容。

1.主要内容：应用所掌握的线性表、树、图等数据结构知识解决实际问题。2.软件开发工具：c/c++、java。

3.课程设计题目：指导教师拟定（参考题目见附录1）。

4.具体步骤：指导教师拟定设计题目，学生研究具体问题、进行需求分析、选择合适的数据结构、设计算法、编写并调试代码、书写文档材料、提交设计报告，最后，由指导教师验收并评定成绩。

5.设计内容及时间安排：第1-3天，选定题目，明确题目要求、确定数据结构、设计算法，并分析算法复杂度；第4-8天，编写程序、调试程序、测试程序；第9-10天，撰写设计报告，准备答辩（上机演示，回答教师提问）。6.设计报告书写要求：按照软件开发规范的要求书写设计报告（参见附录三报告书写格式）；要求报告层次结构清晰、图表完整、语言通顺、字迹工整。7.验收要求：1）运行所设计的程序；2）回答有关问题；3）提交课程设计报告（打印或手写在实习报告册上）；4）提交软盘（源程序）。（鼓励学生创新。对内容有创新者，成绩评定将适当提高）。

五、考核方法。

学习成绩的评定方式：考查。

课程设计成绩评定=平时出勤（20%）+设计报告（40%）+答辩（40%）通过设计答辩方式，并结合学生的动手能力，独立分析解决问题的能力和创新精神，总结报告和答辩水平以及学习态度综合考评。成绩分为优、良、中、及格和不及格五等。

六、教材与参考资料1.建议教材：

2.建议参考书目：

附录一。

参考题目（可分若干组，每个学生选择其中一个题目）。

1．商厦家电库存管理2.排序算法的时间比较。

16．文字统计系统—文字研究助手17．修道士野人问题18．考试问题。

19．计算机辅助考核系统20．学籍管理系统。

注：学生可以自选题目或选择指导老师拟定的题目。

附录二。

开发步骤。

1.分析题目的要求、目的；2.选择适当的数据结构；

3.抽象数据类型的设计；4.抽象数据类型的实现；5.编写代码、上机调试；6.总结验收、评价。

附录三报告书写格式。

1．问题描述。

题目内容、基本要求2．需求分析。

软件的基本功能、输入/输出形式、测试数据要求3．概要设计。

所需的adt及作用、主程序流程及模块调用关系4．详细设计。

编码与调试过程中遇到的问题及解决的办法，还存在哪些没有解决的问题？6．使用说明。

简要说明程序运行操作步骤7．测试结果。

8．课程设计心得体会。

数据结构与算法篇十一

考试形式：半开卷考试讲课对象：计算机本科。

建议教材：《数据结构》(c语言版)陈明编著清华大学出版社。

课程简介：数据结构课程介绍如何组织各种数据在计算机中的存储、传递和转换。内容包括：数组、链接表、栈和队列、串、树与森林、图、排序、查找、索引与散列结构等。课程以结构化程序设计语言c语言作为算法的描述工具，强化数据结构基本知识和结构化程序设计基本能力的双基训练。为后续计算机专业课程的学习打下坚实的基础。

二、课程的教学目标。

“数据结构”是计算机相关专业的一门重要专业基础课，是计算机学科的公认主干课。课程内容由数据结构和算法分析初步两部分组成。

数据结构是针对处理大量非数值性程序问题而形成的一门学科，内涵丰富、应用范围广。它既有完整的学科体系和学科深度，又有较强的实践性。通过课程的学习，应使学生理解和掌握各种数据结构(物理结构和逻辑结构)的概念及其有关的算法；熟悉并了解目前常用数据结构在计算机诸多领域中的基本应用。

算法分析强调最基本的算法设计技术和分析方法。要求学生从算法和数据结构的相互依存关系中把握应用算法设计的艺术和技能。

经过上机实习和课程设计的训练，使学生能够编制、调试具有一定难度的中型程序；以培养良好的软件工程习惯和面向对象的软件思维方法。

“数据结构”的前序课是《离散数学》、《c语言程序设计与算法初步》。

三、理论教学内容的基本要求及学时分配。

1、序论(2学时)学习目标：熟悉各类文件的特点，构造方法以及如何实现检索，插入和删除等操作。

重点与难点：本章无。

知识点：数据、数据元素、数据结构、数据类型、抽象数据类型、算法及其设计原则、时间复杂度、空间复杂度。

2、线性表(4学时)。

学习目标：

(4)结合线性表类型的定义增强对抽象数据类型的理解。

重点与难点：链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针p和结点*p之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。

知识点：线性表、顺序表、链表、有序表。

3、栈和队列(4学时)。

学习目标：

(1)掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们；

(2)熟练掌握栈类型的两种实现方法；

(3)熟练掌握循环队列和链队列的基本操作实现算法；(4)理解递归算法执行过程中栈的状态变化过程。

重点与难点：栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。

知识点：顺序栈、链栈、循环队列、链队列。

4、串(2学时)。

(2)理解串类型的各种存储表示方法；(3)理解串匹配的各种算法。

重点和难点：相对于其它各个知识点而言，本章非整个课程的重点，鉴于串已是多数高级语言中已经实现的数据类型，因此本章重点仅在于了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作。本章的难点是理解实现串匹配的kmp算法的思想。

知识点：串的类型定义、串的存储表示、串匹配、kmp算法。

5、数组和广义表(4学时)。

学习目标：

(2)掌握特殊矩阵的存储压缩表示方法；

(3)理解稀疏矩阵的两类存储压缩方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。

重点和难点：本章重点是学习数组类型的定义及其存储表示。

知识点：数组的类型定义、数组的存储表示、特殊矩阵的压缩存储表示方法、随机稀疏矩阵的压缩存储表示方法。

6、树和二叉树(8学时)。

学习目标：

(3)熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作；

(4)理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法；

(7)了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。

重点和难点：二叉树和树的遍历及其应用是本章的学习重点，而编写实现二叉树和树的各种操作的递归算法也恰是本章的难点所在。

知识点：树的类型定义、二叉树的类型定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、线索二叉树、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码。

7、图(8学时)。

学习目标：

(1)领会图的类型定义；

(2)熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则；

(3)熟练掌握图的两种遍历算法；(4)理解各种图的应用问题的算法。

重点和难点：图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。

知识点：图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径。

8、查找(6学时)。

学习目标：

(3)熟悉静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系；

(4)熟练掌握二叉查找树的构造和查找方法；(5)理解二叉平衡树的构造过程；

(6)熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；

(7)掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。

重点和难点：本章重点在于理解查找表的结构特点及其各种表示方法的特点和适用场合。

知识点：顺序表、有序表、索引顺序表、静态查找树、二叉查找树、二叉平衡树、哈希表。

9、内部排序(6学时)。

学习目标：

(3)理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。

重点和难点：希尔排序、快速排序、堆排序和归并排序等高效方法是本章的学习重点和难点。

知识点：排序、直接插入排序、折半插入排序、表插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序、基数排序、排序方法的综合比较。

10、文件(4学时)。

学习目标：熟悉各类文件的特点，构造方法以及如何实现检索，插入和删除等操作。

重点和难点：本章重点在于了解各种文件的结构特点及其适用场合。知识点：顺序文件、索引文件、b-树、b+树、索引顺序文件、vsam文件、散列文件、多关键字文件。

四、实验教学内容的基本要求及学时分配。

1、线性表(1学时)实验一顺序表的应用实验二链表的应用。

要求：理解线性表的定义及其运算；理解顺序表和链表的定义，组织形式，结构特征和类型说明；掌握在这两种表上实现的插入，删除和按值查找的算法；了解循环链表，双(循环)链表的结构特点和在其上施加的插入，删除等操作。

2、栈(0.5学时)实验三栈的应用。

要求：理解栈的定义，特征及在其上所定义的基本运算；掌握在两种存储结构上对栈所施加的基本运算的实现。

3、队列(0.5学时)实验四队列的应用。

要求：理解队列的定义，特征及在其上所定义的基本运算；掌握在两种存储结构上对队列所施加的基本运算的实现。

4、串(0.5学时)实验五串的应用。

要求：了解串的定义；理解和领会串的存储方式；掌握常用的串运算。

5、数组和广义表(0.5学时)实验六稀疏矩阵的应用。

要求：理解多维数组的结构特点和在内存中的两种顺序存储方式；理解并掌握矩阵和特殊矩阵元素在存储区中地址的计算；领会稀疏矩阵的压缩方式和简单运算；了解广义表的定义和基本运算。

6、树与二叉树(4学时)实验七树与二叉树的应用。

要求：理解树的定义，术语；领会并掌握树的各种存储结构；熟练掌握森林与二叉树间的相互转换；领会树和森林的遍历；了解树的简单应用。深刻理解二叉树的定义，性质及其存储方法；熟练掌握二叉树的二叉链表存储方式，结点结构和类型定义；理解并掌握二叉树的三种遍历算法；掌握二叉树的线索化方法；灵活运用二叉树的遍历方法解决相关的应用问题。

7、图(3学时)实验八图的应用。

要求：理解图的基本概念及术语；掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法；熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想，步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；理解最小生成树的概念，能按prim算法构造最小生成树；领会并掌握拓扑排序，关键路径，最短路径的算法思想。

8、查找(3学时)实验九顺序查找实验十折半查找实验十一哈希表的应用实验十二二叉排序树的综合练习要求：了解查找的基本思想及查找成功和不成功的概念；掌握在顺序表，有序表，索引表，散列表等上的查找方法和算法，并能求出相应的平均查找长度；理解并掌握二叉排序树，平衡二叉树b-树的各种算法。

9、排序(3学时)实验十三插入排序实验十四选择排序实验十五排序综合练习。

要求：领会排序的基本思想和基本概念；理解并掌握插入排序，冒泡排序，快速排序，直接选择排序，堆排序，归并排序和基数排序的基本思想，步骤，算法及时空效率分析；了解外排序的定义和基本方法。

五、大纲说明。

1、课堂讲述的论题只是核心或有特色的知识内容，还有相当数量的篇章内容留给学生自学，所确定的自学部分内容亦属考查范围。

2、“数据结构”课注重上机训练，所有作业都必须配有规范的文档。上机训练由平时的上机训练和小学期的实训课程设计两部分组成。

3、课内学时安排说明：前8周每周4学时全为理论课，从第9周开始理论和上机为1：1，也即2学时理论，2学时上机训练。

4、本课强调能力的培养，期末采用半开卷考试(允许同学携带一页a4纸的总结资料)。本课成绩由平时作业、上机成绩(30%)和期末考试(70%)合成得到，有独到见解的作业予以适当加分。

5、主要参考书：

[2]《数据结构(c语言版)》(含cd)严蔚敏吴为民编著清华大学出版社。

[3]《数据结构习题集(c语言版)》严蔚敏编著清华大学出版社。

[4]《数据结构习题解析与实训》张世和编著清华大学出版社。

数据结构与算法篇十二

在两周的学习和实践过程中，通过解决学生搭配问题这一实际问题，让我对循环队列有了更深的了解，对数据结构也产生了更加浓厚的兴趣，同时也是对我解决实际问题能力的一次提升。

记得王教授给我们上课时就要不断的通过走算法的方式，掌握所学习的数据结构、算法等，而上机则能进一步巩固自己所学的知识、提高自己的学习能力。在上机的同时也改正了自己对某些算法的错误使用，使自己能在通过程序解决问题时抓住关键算法，能够很好的够造出解决问题的数据结构、算法的设计思想和流程图，并用c语言描绘出关键算法。

首先对于这次的课程设计题目而言，主要是对队列这一知识点的运用。首先是对问题的分析，明白题目的具体要求，即将现实生活中的舞会搭配问题，用链队列这一数据结构描绘出来。用两个链队列boy和girl分别代表男生和女生，当播放每一首歌曲时，便可使两队各有一元素出队列，这样就可以模拟出搭配情况。同时，由于题目要求系统能模拟动态地显示出上述过程，所以就考虑调用一个延迟函数sleep()，使歌曲之间有一段时间间隔，即模拟了显示中的那一动态过程。其次便是在实现过程中遇到的具体细节问题，比如一开始设计了两个出对函数dequeue()，让首元素结点出队，然后调用入队函数add()，使其入队到队尾，但在测试时发现，如果输入的人数为2，那么在到第三首歌曲时程序便会终止；经过分析发现是这两个函数的调用，使数据出错，所以就将这两个出对函数用一个函数change()代替，这个函数能实现将首元素结点移到队尾的功能。这样不仅没有了之前的问题，而且使程序更加易懂。在这些细节方面的具体设计，是对个人分析问题、解决问题能力的一个很好的锻炼。通过这个过程的锻炼，不仅能对所学的知识点有很好的掌握，而且还是对个人能力的很好的训练。

其次，以前我对数据结构（c语言描述）的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对c语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。让自己有一定的能力去改正一些常见的错误语法，很高兴这两周的学习让我对数据结构（c语言描述）有了新的认识，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。在这次课程设计的实验中，我收获了许多知识，通过查找大量资料，请教老师，以及不懈的努力，也培养了独立思考、动手操作的能力。我也学会了许多学习和解决实际问题的方法，让我受益匪浅。课程设计对我来说，趣味性强，不仅锻炼能力，而且可以学到很多东西，在与老师和同学的交流过程中，互动学习，将知识融会贯通，也增强了我和同学之间的团队合作的能力。让我们知道只要努力，集中精力解决问题，一定会有收获的，过程也是很重要的。

在这次课程设计中我们要学会利用时间，在规定的时间内完成我们的任务，要逐渐养成用c语言编写程序的良好习惯。这些对我来说都是一种锻炼，一个知识积累的过程，一种能力的提高。要打好基础，才能用更好的办法，更简洁明了的程序解决实际问题，只有这样才能进一步的取得更好的成绩。我们会更加努力，努力的去弥补自己的缺点，发展自己的优点，去充实自己，只有在了解了自己的长短之后，我们会更加珍惜拥有的，更加努力的去完善它，增进它。

当然我现在的水平还是很有限，但我还会继续努力的，在解决实际问题时如果遇到了难题，我们要学会去查找大量的有关这方面的资料，还要借助于网络不断扩大自己的知识面和阅读量。这样也可以锻炼我们的自主学习能力和解决问题的能力，学到了许多以前没学到的东西。

在课程设计中的程序都比较复杂，所以需要我们要更加地细心，认真的完成每一步的操作，修改语法，按照老师的指导思想来完成。还记得一开始拿到题目时我们的一脸茫然，而现在是收获满满的自信，每个人都或多或少有所收获，也让我们对程序设计和算法有了进一步理解、认识。

数据结构与算法篇十三

算法与数据结构这一门课程，就是描述了数据的逻辑结构，数据的存储结构，以及数据的运算集合在计算机中的运用和体现。数据的逻辑结构就是数据与数据之间的逻辑结构；数据的存储结构就包含了顺序存储、链式存储、索引存储和散列存储。在这学期当中，老师给我们主要讲了顺序存储和链式存储。最后数据的运算集合就是对于一批数据，数据的运算是定义在数据的逻辑结构之上的，而运算的具体实现依赖于数据的存储结构。

通过这学期的学习，让我在去年c语言的基础上对数据与数据之间的逻辑关系有了更深的理解和认识。以前在学matlab这一课程的时候，我们如果要实现两个数的加减乘除，或者一系列复杂的数据运算，就直接的调用函数就行，套用规则符号和运算格式，就能立马知道结果。在学习c语言这一课程时，我们逐渐开始了解函数的调用的原理，利用子函数中包含的运算规则，从而实现函数的功能。现今学习了算法，让我更深层次的知道了通过顺序表、指针、递归，能让数据算法的实现更加的简洁，明了，更易于理解。摒弃了数据的冗杂性。

在本书第二章中，主要介绍了顺序表的实现以及运用。顺序表中我认为最重要的是一个实型数组，和顺序表的表长，不论是在一个数据的倒置、插入、删除以及数据的排序过程中，都能将数据依次存入数组当中，利用数组下标之间的关系，就能实现数据的一系列操作了。在存储栈中，给我留下最深刻的映像就是“先进后出”，由于它特殊的存储特性，所以在括号的匹配，算术表达式中被大量应用。在存储队列之中，数据的删除和存储分别在表的两端进行操作，所以存储数据很方便。为节省队列浪费闲置空间的这一大缺点，所以引入了循环队列这一概念，很好用。

在第三章中，主要讲的是链式存储特性。它最突出的优点就是可以选择连续或者不连续的存储空间都行。所以，不管是数据在插入或者删除一个数据时，会很方便，不会像顺序表那样，要移动数组中的诸多元素。所以链表利用指针能很方便的进行删除或者插入操作。而链式在栈和队列的基础上，也有了多方面的应用，所以在这些方面有了更多的应用。

第四章字符串中，基本的数组内部元素的排序和字符串的匹配大部分代码自己还是能够理解，能够看懂，如果真的要将所学的大量运用于实践的话，那就要多花些功夫和时间了。在对称矩阵的压缩，三角矩阵的压缩，稀疏矩阵在存储中能够合理的进行，能大大提高空间的开支。

在第五章递归当中，就是在函数的定义之中出现了自己本身的调用，称之为递归。而递归设计出来的程序，具有结构清晰，可读性强，便于理解等优点。但是由于递归在执行的过程中，伴随着函数自身的多次调用，因而执行效率较低。如果要在追求执行效率的情况下，往往采用非递归方式实现问题的算法程序。

在第六章数型结构当中，这是区别于线性结构的另一大类数据结构，它具有分支性和层次性。它是数据表示，信息组织和程序设计的基础和工具。在本章中，映像深刻的是树的存储结构。有双亲表示法，孩子表示法，以及孩子兄弟表示法。在表示怎样存储数据之后，接着要从数型结构中将数据读取出来，于是，有了树的遍历，在遍历当中，又分为前序、中序和后序遍历，这三种遍历各有各的特点。

在第七章中，说到了树的扩展---二叉树。二叉树不同一般的树型结构的另一种重要的非线性结构，它是处理两种不同的数据结构，许多涉及树的算法采用二叉树表示和处理更加便捷和方便。其他的也是和一般的二叉树差不多。还多了一个树、森林和二叉树之间的转换。

第八章的围绕着图来展开，它是一种复杂的非线性结构，在人工智能、网络工程、数学、并行计算和工业设计有着广泛的应用。图最重要的由一个非空的顶点集合和一个描述顶点之间的多对多关系的边集合组成的一种数据结构。图的存储室通过邻接矩阵老存储图的信息。而图的读取是通过深度优先遍历和广度优先遍历实现。生成最小生成树有prim算法和kruskal算法，相对于这两种算法，后一种算法要更加易于理解。

在考试的时候，我以为老师只会出题作业部分。然后书中有一小部分就没看，但是题中出现了一个二叉树转换为森林的时候，我有印象，但就是没思路想法了，就没做。从中我真的理解了老师说的，考试不代表学习的结束。或者你现在看的内容在生活中学习中暂时没有太大的作用，但是到了某一特定的环境条件下，总会有作用。所以，学习是一个积累的过程，不懈怠，踏实的走下去，你才会有所收获。