实验数据结构与算法

实验数据结构与算法（精选8篇）

实验数据结构与算法篇1

学生实验报告册

课程名称：

学生学号：

所属院部：

（理工类）

算法与数据结构专业班级： 14计单（2）

1413201007 学生姓名：毛卓

计算机工程学院指导教师：章海鸥 16 ——20 17 学年第二学期

金陵科技学院教务处制

金陵科技学院实验报告

实验报告书写要求

实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用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归并成一个按元素值递减有序排列的顺序表（允许表中含有值相同的元素）。

程序清单：

（1）:/*编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。*/ #include typedef int datatype;#define maxsize 1024 typedef struct { datatype data[maxsize];int last;

金陵科技学院实验报告

}sequenlist;void main(){ sequenlist L;int i,n;printf(“请输入元素个数：”);scanf(“%d”,&n);printf(“n请输入元素：”);for(i=0;i

如果不存在，返回－1。*/ #include typedef int datatype;#define maxsize 1024 typedef struct { datatype data[maxsize];int last;}sequenlist;

int fun(sequenlist L,int x,int n){

金陵科技学院实验报告

} int i;for(i=0;i

} int i,n,y;int x;

printf(“请输入元素个数：”);scanf(“%d”,&n);printf(“n请输入元素：”);for(i=0;i

printf(“n请输入要查找的数据元素：”);scanf(“%d”,&x);y=fun(L,x,n);if(y==-1)else printf(“n数据元素 %d 所在的位置为 %d n”,x,y);printf(“n所要查找的数据元素不存在。n”);(3): /*在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。

解题思路：首先查找插入的位置，再移位，最后进行插入操作；

从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；

金陵科技学院实验报告

然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。*/ #define maxsize 100 typedef struct{

int data[maxsize];

int last;}sequenlist;main(){

int i,x,j;

sequenlist l={{1,3,5,6,7,9},5};

printf(“n插入元素前的数据为:”);

for(i=0;i<=l.last;i++)

printf(“%2d”,l.data[i]);

printf(“n请输入要插入的元素:”);

scanf(“%d”,&x);

for(i=1;i<=l.last;i++)

if(l.data[i-1]>x)break;

if(i>l.last)

{

l.data [l.last +1]=x;

}

else

{

for(j=l.last;j>=i-1;j--)l.data[j+1]=l.data[j];l.data[i-1]=x;

}

l.last++;

printf(“插入元素后的数据为:n”);

金陵科技学院实验报告

for(j=0;j<=l.last;j++)

printf(“%3d”,l.data[j]);

printf(“n”);}(4): /*删除顺序表中所有等于X的数据元素。*/ #define maxsize 100 typedef struct{

int data[maxsize];

int last;}sequenlist;main(){

int i,j,x=0,k=0;

sequenlist L={{1,3,5,7,2,4,6,8,2,9},9};

printf(“n原数据为:”);

for(i=0;i<=L.last;i++)printf(“%3d”,L.data[i]);

printf(“n请输入要删除的数据:”);

scanf(“%d”,&x);

for(i=1;i<=L.last+1;i++)

if(L.data[i-1]==x){

for(j=i;j<=L.last+1;j++)L.data[j-1]=L.data[j];

L.last--;

i--;

k=1;

}

if(k==1){

printf(“删除后的数据为:n”);

for(j=0;j<=L.last;j++)printf(“%3d”,L.data[j]);

}

else printf(“Not found!n”);

金陵科技学院实验报告

printf(“n”);}

四、实验结果与分析（程序运行结果及其分析）（1）结果：请输入元素个数：5

请输入元素：1 2 3 4 5

元素输出：1 2 3 4 5（2）结果：请输入元素个数：5

请输入元素：1 2 3 4 5

请输入要查找的数据元素：5

数据元素5所在的位置为 4（3）结果：插入数据前的元素为：1 3 5 6 7 9

请输入要插入的元素为：10

插入元素后的数据为:

5 6 7 9 10（4）结果：原数据为：1 3 5 7 2 4 6 8 2 9

请输入要删除的数据为：7

删除后的数据为： 3 5 2 4 6 8 2 9

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

金陵科技学院实验报告

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

金陵科技学院实验报告

实验2 单链表

一、实验目的和要求

1、实验目的

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

2、实验要求

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

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

二、实验仪器和设备

Visual C++6.0

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

1、必做题

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

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

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

2、选做题

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

金陵科技学院实验报告

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

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

金陵科技学院实验报告

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

金陵科技学院实验报告

实验3 堆栈和队列

一、实验目的和要求

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

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

二、实验仪器和设备

Visual C++6.0

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

1、必做题

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

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

2、选做题

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

金陵科技学院实验报告

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

金陵科技学院实验报告

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

金陵科技学院实验报告

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

金陵科技学院实验报告

实验4 串

一、实验目的和要求

掌握串的存储及应用。

二、实验仪器和设备

Visual C++6.0

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

1、必做题

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

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

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

2、选做题

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

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

金陵科技学院实验报告

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

金陵科技学院实验报告

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

金陵科技学院实验报告

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

金陵科技学院实验报告

实验5 二叉树

一、实验目的和要求

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

二、实验仪器和设备

Visual C++6.0

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

1、必做题

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

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

2、选做题

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

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

金陵科技学院实验报告

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

金陵科技学院实验报告

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

金陵科技学院实验报告

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

金陵科技学院实验报告

实验6 图

一、实验目的和要求

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

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

二、实验仪器和设备

Visual C++6.0

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

1、必做题

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

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

2、选做题

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

金陵科技学院实验报告

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

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

金陵科技学院实验报告

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

金陵科技学院实验报告

实验7 排序

一、实验目的和要求

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

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

二、实验仪器和设备

Visual C++6.0

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

1、必做题

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

2、选做题

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

金陵科技学院实验报告

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

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

金陵科技学院实验报告

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

金陵科技学院实验报告

实验8 查找

一、实验目的和要求

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

二、实验仪器和设备

Visual C++6.0

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

1、必做题

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

2、选做题

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

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

金陵科技学院实验报告

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

实验数据结构与算法篇2

关键词：数据结构与算法,实验教学,改革

数据结构与算法是计算机专业的核心基础课程之一, 通过本门课程的学习, 可以使学生透彻地理解各种数据对象的特点, 学会数据的组织方法和实现方法, 并进一步培养良好的程序设计能力, 而该课程的实验课是学生验证、掌握和应用数据结构理论的重要途径。

一、数据结构与算法上机实验课程的现状

数据结构与算法课程涉及大量数据类型及算法, 理论性很强, 抽象难懂, 对学生的学习造成了一定的难度。受传统的教学模式的影响, 课程的实验教学一直处于从属地位, 同时因学生基本程序设计能力有待提高等因素影响, 实验效果不甚理想。如何使学生理论学习和实践学习相结合, 提高学生的实践能力, 已成为高等院校培养应用型本科人才的一项重要课题。

目前在数据结构与算法实验教学过程中发现的问题主要有以下几点:

1.学生对于上机实验的重要性认识不够。对于学生来说, 由于部分院校的教学资源所限, 数据结构与算法课程长期以来都是课堂和实验分开进行, 授课教师对于上机实验过程几乎不参与, 这就导致了学生重视课堂理论的讲授, 而忽视上机实验课程的重要性。

2.课程实验缺乏层次性。上机实验教学内容大多为简单的验证性实验, 缺乏综合性、应用型、设计性实验项目。增加论述。

3.课程理论性强、难度大。数据结构与算法课程理论性极强, 抽象难懂, 很多学生在课堂听课过程中不能够完全理解, 无法建立起数据结构和相应算法的概念, 长此以往导致学生对于这门课程的畏惧和抵触情绪, 同时也严重打击了学生上机实验的积极性。

4.学生对掌握程序语言的程度不够。学生对程序设计语言掌握得不理想, 也是导致学生上机实验缺乏积极性的一个重要原因。数据结构与算法是学生在学过一门或几门语言课程之后开设的, 其算法大都由C或C++语言描述, 要求学生能够使用某种程序设计语言对算法进行程序设计, 并且上机调试通过。以我学院为例, 学生在学习数据结构时, 虽然已经学过C语言, 但仅是初学, 并不精通。因此对于抽象的数据类型、动态分配存储空间等概念, 在理解上还是有一定困难的。由于对程序设计语言掌握得不好, 大部分学生在编程的过程中陷入迷茫的状态, 阻碍了他们对各类数据结构和算法等知识点的理解和应用, 使教学目标难以实现。

二、实验教学的改革和探索

(一) 实验教学内容的改革

数据结构与算法课程主要使学生掌握程序数据的结构、组织和管理技术以及在此基础上的算法设计与分析技术, 不仅为后续课程操作系统、编译原理、数据库原理、软件工程、人工智能等课程提供必要的知识准备, 更重要的是可以提高学生软件分析、设计、编程和数据组织的能力。根据数据结构与算法整个课程体系的划分, 本课程的上机实验主要分为以下几种类型:

1. 验证性实验。

这一类型的实验主要在上机实验课中完成。以西安交通大学城市学院为例, 本门课程有8个学时的上机实验, 主要任务是将课堂上讲过的内容以实验的形式贯穿起来, 所涉及的实验以教材中提及到的基本算法和例题为主, 基本都是验证性的实验。以单链表为例, 要求学生通过定义线性表的抽象数据类型, 在链式存储结构下完成单链表的建立、插入、删除、查找、求前驱节点和求后继节点等操作, 通过实验教学, 在加深学生对数据结构课程内容理解的同时, 达到理论联系实际的目的。

学生通过完成此类实验, 一方面可以强化基础知识, 另一方面也可以通过编写算法掌握高级语言程序, 同时还可以训练学生良好的编程风格、基本实验技能和科学严谨的实验作风。

2. 综合性实验。

综合性实验部分实在课程设计阶段来完成。主要任务是考查学生运用所学基本数据结构解决实际问题的能力。所设计的实验项目可以是课程设计指导书中提供的参考题目, 也可以是工程中的实际课题, 选题要与所学阶段性知识紧密联系, 任务有一定的难度和综合性, 对学生的编程思路和方法有启发作用的项目。例如:学习了栈和队列知识后可以要求学生设计一个停车场管理系统, 以栈模拟停车场, 以队列模拟车场外的便道, 按照从终端读入的输入数据序列进行模拟管理。又如:学习了图的路径的相关算法后, 可利用学生熟悉的当地交通情况、旅游景点等设计问路系统。这些问题与课本理论知识联系密切, 而且具有一定的实用价值。

3. 研究性实验。

此类实验是针对于学有余力的学生, 可安排一些研究性实验, 针对计算机专业学生的特点, 可以以软件开发的形式进行, 让学生以创新者的角色去做实验。所设计的实验项目都是实际工程中的课题, 题目的解法要求符合工程实际情况, 具有可行性。学生可以自己提出实验题目和开发工具, 自己设计实验过程等, 有条件者还可以进入工程实践中进一步提升实践能力。

(二) 实验教学方法的改革

根据我院学生的特点和学院培养应用性本科人才教育宗旨, 我们在实验教学的方法上进行了改革。

1. 先简后难, 循序渐进。

在上机实验课中, 主要以验证性试验为主, 针对堂课讲授的知识安排配套的练习。练习的内容以编写的数据结构与算法实验指导书的形式发给学生, 每节课明确实验任务、实验方法和结果要求, 使学生在有限的课堂时间中完成相应训练目标, 掌握基础知识, 夯实基础;在课程完成之后的课程设计阶段, 加大难度, 主要以综合性的题目为主, 对于程度特别好的学生也可以完成研究性的项目。针对这一阶段的训练, 我们也编写了相应的课程设计指导书, 提供给学生适合的参考题目和编程提示。有助于学生更好的完成项目要求。通过一系列的训练, 培养学生算法设计能力以及创造性思维, 以达到提高学生应用知识解决复杂问题能力的目标。

2. 启发式教学和分组实验。

在教学方法上, 把传统教法中老师讲, 学生听的“灌输法”转化为“启发式”的教学方法, 引导学生自主思考, 常常提问“WWW”, 即“What, Hao, Why”:这个问题做什么的?需要用的哪方面的知识?怎么去解决问题?如何解决?教师教给学生提出问题、分析问题和解决问题的方法, 学生自行探究问题和解决问题, 激发学生探求知识的欲望和积极的学习兴趣。

在训练的形式上, 改变传统的“集体化”路线, 根据程度的不同将2~4名学生分成多个小组, 任命一名学习能力强、组织能力好的学生担任项目组长, 以软件开发小组的形式协同工作, 合理分工, 共同学习, 通过团队讨论解决问题。各小组成员不仅要完成自己的工作, 还要与其他成员合作, 共同完成整个项目。教师应多给予学生鼓励, 激发学生的思维, 促进他们合作的欲望和热情, 使课堂活泼积极, 并且适时的提供必要的启发式帮助, 只提供意见, 不具体替学生完成。让学生从解决问题和团队合作中获得成就感和自我认同感, 在轻松的氛围中达到激发学生兴趣, 提高学生综合实践能力的目标。

(三) 项目答辩和实验报告结合的考核方法。

1. 项目答辩。

在课程设计实验结束时, 专门抽出时间对个小组成员的工作进行考核, 要求每个小组选派2名学生进行答辩, 在规定时间内陈述小组工作情况, 遇到的问题及解决的办法, 最终达到的效果及心得体会等。根据答辩情况, 给予优、良、中、差和不及格五档评分。通过这种团队合作和答辩的方式大大提升了学生的实践能力、组织和口头表达能力及合作精神。

2. 实验报告的规范。

课程设计实验结束后要求学生写出实验报告, 以作为实验环节评分的书面依据之一和存档材料。实验报告以规定格式的电子文档书写、打印并装订, 排版及图、表要清楚、工整。每个小组每个题目提交一份实验报告, 实验报告除介绍本小组成员所做工作外还应包括以下内容:

(1) 需求分析。以规范的技术文档语言陈述说明项目设计的任务并明确规定: (1) 输入的形式和输入值的范围; (2) 输出的形式; (3) 程序所能达到的功能; (4) 测试数据:包括正确的输入及其输出结果和含有错误的输入及其输出结果。

(2) 概要设计。说明本程序中用到的所有抽象数据类型的定义、主控程序的流程以及各程序模块之间的层次关系。

(3) 详细设计。本阶段的主要任务是实现概要设计中定义的所有数据类型, 对各操作、主程序和其他模块均要求写出伪码算法, 同时可以使用流程图或者N———S图进行描述, 画出函数和过程的调用关系图。

(4) 调试分析。在程序的调试过程中出现的问题以及解决办法, 回顾和讨论设计与实现过程中的相关问题。

(5) 测试结果。列出完整和严格的测试数据, 包括输入和输出。

(6) 用户使用说明。说明程序的使用方法, 并列出每一步的具体操作步骤。

(7) 代码注释。算法必须给出完整、正确的文字注释。

三、改革的效果

通过数据结构与算法实验教学的改革, 学生的学习热情和积极性得到了明显的提高, 学生的主动思考和积极实践的热情得以激发。学生能够在实验期间主动积极的参与并解决问题, 提高了学生的实践能力和编程能力。通过分组合作的方式进行项目训练, 培养了学生的团队合作意识和严谨的工作作风。通过小组答辩, 教师了解了每组学生的学习情况, 把握学生的学习状态和程度, 有助于在日后的教学中给予适当的指导。教师在此过程中不断总结问题, 积累经验, 使教学质量得到显著提高。

四、结束语

数据结构与算法在计算机课程体系中占据重要地位, 其实验环节的教学质量直接关系到本门课程的学习效果。在实验教学过程中必须以培养学生的综合实践能力为宗旨, 不断改进教学方法, 加大实验教学力度, 做到夯实基础, 提高能力, 为学生后续专业课程的学习打下良好的基础。

参考文献

[1]耿国华.数据结构——C语言描述[M].北京:高等教育出版社, 2006.

[2]赵玉霞.《数据结构》课程上机实验改革初探[J].福建电脑, 2007, (4) :213-214.

[3]严蔚敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版社, 1997.

[4]宁正元, 王秀丽, 林大辉.与数据结构[M].北京:清华大学出版社, 2006.

实验数据结构与算法篇3

关键词:数据结构与算法;综合性实验;设计性实验

一、引言

在计算机科学与技术、软件工程等专业中,《数据结构与算法》课程具有较强的实践性,因此实验教学是该课程教学过程中的一个非常重要的环节。在以往的实验教学中,学生都是按照已经设计好的实验要求和步骤进行着验证性的实验,学生一般是被动地接受或机械式地编程,以完成实验讲义中的验证或孤立的单元实验。这种实验教学模式使得学生缺乏主动性和独立思考问题的能力,不利于他们综合素质的提高和自主创新能力的培养。为了克服这些不足,使学生真正能把理论知识灵活运用到实践当中,我们开设了《数据结构与算法》课程综合性、设计性实验项目并立项进行实践研究,通过两三年的实践,取得了一些经验和成果,学生的实践能力也有了较大提高。

二、综合性、设计性实验项目的实践环节

1.实验项目的选择。

通过《数据结构与算法》课程的学习和前期验证性实践环节,学生已初步具备了进行综合性、设计性实验的能力。为进一步提高学生的设计能力和编程能力,我们设计了4个综合性、设计性实验项目供学生选择:

①校园导游系统的设计(设计性);

②书管理系统的设计(综合性);

③哈夫曼编码/译码器(综合性);

④散列表的设计与实现(设计性)。

2.实验项目的内容。

校园导游系统的设计

问题描述:

设计一个校园导游程序,为来访的客人提供信息查询服务。

基本要求:

①设计你所在的学校的校园平面图,所含景点不少于15个,以图中顶点表示校内各景点,存放景点名称、代号、简介等信息,以边表示路径,存放路径长度等相关信息;

②为来访客人提供图中任意景点相关信息查询;

③为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短路径(静态或动态表示出来)。

图书管理系统的设计

问题描述:

设计一个图书管理系统完成图书管理基本业务。

基本要求:

①每种书的登记内容包括书号、书名、著作者和库存量;

②对书号建立索引表(线性表或树表)以提高查找效率;

③系统主要功能如下:

采编入库:新购一种书,确定书号后,登记到图书账目表中,如果表中已有,则只将库存量增加;

借阅:如果一种书的现存量大于0,则借出一本,登记借阅者的书证号和归还期限,改变现存量;

归还:注销对借阅者的登记,改变该书的现存量。

用户管理。

数据存储(要求用文件实现数据存储)。

哈夫曼编码/译码器

问题描述:

设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼编码,生成编码文件(压缩文件,后缀名.cod);反过来,可将一个压缩文件译码还原为一个文本文件(.txt)。

基本要求:

①随机抽取20个文本文件作为统计样本,统计这些文本文件中各字符的平均出现次数,作为权值,建立哈夫曼树及各个字符的哈夫曼编码;

②将用户输入或选择的待压缩文本文件利用①建立的编码表进行编码,生成压缩文件(后缀名.cod);

③输入一个待解压的压缩文件名称,并利用相应的编码表进行译码;

④显示指定的压缩文件和文本文件;

⑤(选作) 把哈夫曼编码用二进制位紧缩到一个变量中,利用位运算实现真正的数据压缩,并求压缩比。

散列表的设计与实现

问题描述:

设计散列表实现电话号码查找系统。

基本要求:

①随机生成1万个记录,每个记录有下列数据项:电话号码、用户名、地址,每个数据项的内容都是随机生成的;

②分别以电话号码和用户名为关键字建立散列表(自行选择或构造合适的散列函数);

③采用双散列法解决冲突;

④查找并显示给定电话号码的记录;

⑤查找并显示给定用户名的记录。

3.预期目标。

进一步巩固和加深对《数据结构与算法》课程中基本知识的理解,熟悉各种逻辑结构及存储结构;

了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力;

培养学生从事软件开发的编程及创新能力;

提高学生综合运用所学的理论知识解决问题的能力;

训练用系统的观点和软件进行软件开发,培养软件工作者所应具备的科学的工作方法和作风。

4.实验项目的组织与实施。

针对综合性设计性实验项目,安排学生自选项目并进行项目设计和开发,每个项目20学时,按照下面的项目开发设计步骤,最后完成课题的总体设计与实现。

项目分析

根据实验项目内容的要求,充分地分析和理解问题,明确问题要求做什么、解决什么问题、实现什么功能。

概要设计

对项目内容描述中涉及的操作对象,设计相应的数据结构,并按照以数据结构为中心的原则对模块进行划分,定义主程序模块和逻辑结构。逻辑设计的结果是每种数据结构的定义(包括数据结构的描述和每个基本操作的功能说明)。

详细设计

为各个数据结构设计相应的存储结构并写出各模块的算法。设计是编程中重要的一环,在“详细设计”过程中,引导学生结合总体设计制订合理的程序结构和算法,理顺各个模块之间的相互关系,将详细设计的结果用结构图及流程图清晰地描述出来,在本过程中,教师要尽可能帮助学生养成自己解决问题的习惯。

编程

将详细设计的结果进一步求精为程序设计语言程序。在该环节中,教师应指导学生按照规范的程序编写方法去编程,并指导学生按照大型软件中常用的调试方法对程序进行跟踪及改进。

结果分析

在编程过程中及结束后,形成学生、课题小组组长、指导教师三位一体的项目质量监控体系,做到对各个阶段的结果都能进行实时的检测,如有不足之处,小组内成员和学生自行研讨出合理的整改方案并对课题实施进行改进,直至达到功能要求。

5.项目总结。

主要包括学生实验项目总结心得、实验报告撰写,学生成绩的评定。

实验项目总结心得

在实验临将近结束时让学生共同讨论实验结果的正确性,讨论实验设计步骤的合理性,总结经验,进一步改善项目实施的方案及步骤。笔者认为,实验后的总结非常重要,是从理论到实践,再由实践到理论认识的进一步升华,也是使学生提高实验兴趣、锻炼并增解决实际问题的重要过程和手段。

实验报告撰写

学生实验报告一般应包含的内容是:实验题目、实验环境、实验目的、实验任务、数据结构描述、算法流程图表示、实验总结。

学生成绩的评定

教师根据学生的实验设计报告、学生的实际操作能力(程序检查)及学生的创新能力等几个方面综合评定,给出综合成绩。

三、实践的成果

1.对学生的影响。

经过近两年的实验教学实践,有超过70%的学生认为此次实验收获很大,大约80%的学生对这类实验取得的成果表示满意。从总体效果来看,学生通过综合性、设计性实验,提高了设计及编程能力。大部分学生认为《数据结构与算法》综合性、设计性实验项目的开展改变了以往传统的实践教学模式,内容新颖,提高了他们的编程兴趣和热情,对他们帮助很大。

2.对教师的促进。

《数据结构与算法》综合性、设计性实验的指导教师由计算机科学技术学院《数据结构与算法》课程的主讲教师和专业实验室的教师共同承担,我们认为,开展综合性设计性实验项目整合了多个知识环节,既能够帮助学生掌握知识的系统性和衔接性,理清程序设计的思路,促进知识的融会贯通;同时也给主讲教师带来新的挑战,能使教师总结在理论教学中的不足,进一步加强教学方法和内容的改革。

参考文献:

[1]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2006.

[2]唐册善.数据结构—C语言描述[M].北京:高等教育出版社,2003.

数据结构算法设计与分析篇4

网页制作、程序设计Java、JSP程序设计、Oracle、XML程序设计、计算机网络、SSH（Struts+Spring+Hibernate）框架、Java EE程序设计、Ajax程序设计、Linux+PHP+MySQL程序设计、Android手机开发、UML系统分析与设计、性能测试、自动化软件测试、软件质量保证、毕业设计及项目综合实训等。

数据结构、计算机网络、计算机组成原理、操作系统原理、编译原理、数据库原理及应用、金融学概论、西方经济学等基础理论课程；

网页制作、程序设计Java、JSP程序设计、J2EE程序设计、SQL Server数据库、Oracle数据库、Linux操作系统、UML系统分析与设计、软件工程、XML程序设计、SSH框架、金融市场学、ERP财务管理、管理信息系统、投资银行学、商业银行学、国际金融管理、毕业设计及项目综合实训等专业课程。

数据结构、计算机网络、计算机组成原理、操作系统原理、数据库原理及应用、软件工程、软件测试等计算机基础理论课程；

数据结构与算法课程设计题目篇5

1．成绩管理

问题描述：给出n个学生的考试成绩表，成绩表包括学生的学号、姓名、考试成绩（高等数

学、英语、物理），设计一个简单的成绩管理程序。

基本要求：

（1）建立成绩表，能够插入、删除、修改学生的成绩记录；（2）按任一单科成绩排序；(3)计算每名学生的平均成绩；

(4)统计任一单科成绩不及格的学生人数, 输出不及格人数及不及格的学生名单(5)根据平均成绩将成绩表按由高到低的次序排列，统计每名学生在考试中获得的名次，分数相同的为同一名次，按名次输出成绩表。

(6)成绩表保存在文件中, 可以从文件读取数据。

测试数据：学生可以根据自己班级的考试成绩单，任意截取一部分做为测试数据 2．一元多项式简单计算

问题描述：设计一个简单一元多项式计算器。基本要求：(1)输入并建立多项式；(2)输出多项式；

(3)两个多项式相加，输出结果多项式；(4)两个多项式相减，输出结果多项式。

提高要求：可以根据输入变量的值，计算出多项式的结果，且算法的效率高。测试数据：可任意选取两个一元多项式，可以是一般的多项式，也可以是稀疏多项式。3．舞伴问题

问题描述：一班有m个女生、n个男生(m不等于n), 举办一场舞会.男女生分别编号坐在舞池两边的椅子上，每曲开始时, 依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴，设计一个程序模拟舞伴配对过程。

基本要求：输入男、女学生的姓名、性别，由程序自动为男女生编号，可以顺序编号，也可以随机编号，输出每曲配对情况（包括男、女生的姓名、性别和编号）。原始数据和结果数据要保存到文件中。

测试数据：分别选择男生多于女生、女生多于男生、男女生相等的三组测试数据提高要求：计算出任意一位男生(编号为X)和任意一位女生(编号为Y), 在第K曲配对跳舞的情况。

4．文学研究助手（*）

问题描述：文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。基本要求：英文小说存于一个文本文件中，待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计, 结果保存到文件中。

提高要求：模式匹配选取KMP算法

测试数据：以你的C/C++/JAVA源程序模拟英文小说，相应语言的保留字集作为待统计的词汇集。

5．哈希表的设计与实现（*）

问题描述：针对某个单位电话号码簿，设计一个哈希表，并完成相应的建表和查表程序。基本要求：设每个记录有下列数据项：电话号码、用户名、住址。从键盘输入各记录，以用户名为关键字建立哈希表，哈希函数用除留取余数法构造，采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录，并计算查找长度, 哈希表保存到文件中。

测试数据：取某个单位电话号码簿中的30个记录。

提高要求：将电话号码薄以文件形式保存到盘上，能够按用户名和电话号码两种形式建立哈希表并实现插入、查找、删除表中元素的功能。

6．管道铺设施工的最佳方案（*）

问题描述:需要在某个城市的n个小区铺设管道，则在这n个小区之间铺设n-1条管道即可，假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同，选择最优的施工方案使总投资尽可能的少。

基本要求：输入表示小区间关系的图及每条管道的权值，选择出n-1条管道, 使总投资最小。图的信息输入一次后, 保存到文件中, 选择的n-1条管道输出到显示器的同时, 也保存于文件中。

测试用例：任意选择一个图，模拟小区间可能铺设的管道及费用。提高要求：显示原始图及选择n-1条管道后的图。

7．安排教学计划（**）

问题描述：大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两个学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排上必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课程恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

基本要求：输入参数包括学期总数，一学期的学分上限，每门课程的课程号、学分和直接先修课的课程号；允许两种策略，一是使学生在各学期的学习负担尽量均匀，二是使课程尽量集中在前几个学期；若根据给定的条件问题无解，则报告适当的信息，否则将教学计划输出到用户指定的文件中。教学计划的表格格式自行设定, 可以从键盘读取数据也可以从文件读取数据, 结果保存到文件中。

测试数据：学期总数为6，学分上限为10，该专业共开设12门。以08级某专业必修课与选修课为例，选择12门课程及相应学分，制定一个表明各门课程先后约束关系的有向图。

提高要求：产生多种不同的方案，并使方案之间的差异尽可能地大。8．停车场管理程序(**)问题描述：设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。

基本要求：每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费，单位时间的停车费用由用户从键盘输入）。

测试数据：设输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。

提高要求：设停车场有南、北两个门，每个门都可以进、出车辆。9．计算表达式的值(**)问题描述：对于给定的一个表达式，表达式中可以包括常数、算术运行符（“+”、“-”、“*”、“/”）和括号，编写程序计算表达式的值。

基本要求：从键盘输入一个正确的中缀表达式，将中缀表达式转换为对应的后缀表达式，计算后缀表达式的值。

测试数据：任意选取一个符合题目要求的表达式。提高要求：（1）对于表达式中的简单错误，能够给出提示；

（2）表达式中可以包括单个字母表示的变量。

10．设计Huffman 编码器与解码器（***）

问题描述：利用哈夫曼编码进行信息通讯可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码；在接受端将传来的数据进行译码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个哈夫曼码的编/译码系统。

基本要求：根据某字符文件统计字符出现频度，构造Huffman 树，编制Huffman编码，并将给定字符文件编码，生成编码文件；再将给定编码文件解码，生成字符文件。（要求按二进制位表示编码）测试数据：英文文件。

提高要求：用二进制表示编码，生成二进制的编码文件。11．银行业务模拟（***）

问题描述：设银行有四个服务窗口，一个等待队列, 每个窗口均可以办理存款、取款、挂失、还贷业务，每种业务所需的服务时间不同，客户到达银行后，先到打号机上打号，号票上包括到达时间、编号和需要办理的业务，然后在银行内等候, 当任一服务窗口空闲时,处理等候客户中排在最前面的客户的业务。写一个上述银行业务的模拟系统,通过模拟方法求出客户在银行内逗留的平均时间和每个窗口办理的客户数及办理的每种业务数。

基本要求：每个客户到达银行的时间和需要办理的业务随机产生，输出一天客户在银行的平均逗留时间和每个窗口每天办理的客户数和每种业务数。

测试数据：营业时间为8小时，其他模拟量自行设定。12．程序源代码的相似性（***）

问题描述：对于两个C++语言的源程序代码，用哈希表的方法分别统计两个程序中使用C++语言关键字的情况，并最终按定量的计算结果，得出两份程序的相似性。

基本要求：建立C++语言关键字的哈希表，统计在每个源程序中C++关键字出现的频度, 得到两个向量X1和X2，通过计算向量X1和X2的相对距离来判断两个源程序的相似性。

例如: 关键字 Void Int For Char if else while do break class 程序1关键字频度 4 3 0 4 3 0 7 0 0 2 程序2关键字频度 4 2 0 5 4 0 5 2 0 1 X1=[4,3,0,4,3,0,7,0,0,2] X2=[4,2,0,5,4,0,5,2,0,1] 设s是向量X1和X2的相对距离，s=sqrt(∑(xi1-xi2)2)，当X1=X2时，s=0, 反映出可能是同一个程序；s值越大，则两个程序的差别可能也越大。

测试数据: 选择若干组编译和运行都无误的C++程序，程序之间有相近的和差别大的，用上述方法求s, 对比两个程序的相似性。

提高要求：建立源代码用户标识符表，比较两个源代码用户标识符出现的频度，综合关键字频度和用户标识符频度判断两个程序的相似性。

13．小型文本编辑器

问题描述：设计一个行编辑程序，使其具有通常行编辑器(如Vi、Edlin)应具备的基本功能。

基本要求：编辑器应具备对文本文件的查找、插人、删除、修改、字符串替换、统计字数，统计行数等功能，对于超过一屏的长文件，应能够分页显示，查找功能用字符串匹配算法实现。设计用户接口命令，实现对文本的编辑。具体的编辑命令，可参考数据结构算法网络教学平台上提供的edlin、Vi的命令集。

测试数据：任一文本文件。

提高要求：１.可以支持“* ”、“? ”等通配符；

２.支持复制、粘贴等功能

3.支持多文档同时编辑；

提示：可以考虑用双向链表实现，每一结点表示一行字符，注意每行字符不能超过255。14．小型英汉词典

问题描述：设计一个英汉词典，支持Member(查找)、Insert(插入)、Delete(删除)操作。

基本要求：实现字典的常用方法有：有序线性表（Memeber用二分检索实现）、AVL树（二叉搜索树）、Patricia Trie、散列表等，任选一种方法实现字典的操作，查找单词、插入单词（插入时，先查找，找不到插入，找到提示用户）、删除单词（删除时，先查找，找到删除，找不到提示用户）。

测试数据：任一英文单词。提高要求：选用两种以上的方法实现字典的操作，并比较不同实现算法的时间复杂度和空间复杂度。

提示：字典可以自己建立，但必须按字母a~z建立26个文件，建议从网上下载，文件类型为txt。

备注：

1.每道题目后面的*号，表示题目的难度系数；对应的评定成绩等级为及格（无*号）、中等（*号）、良好（**号）、优秀（***号），学生完成题目的基本要求，即可得到程序设计部分的相应等级成绩，完成题目提高要求，成绩可以向上浮动，如果没有完成基本要求，成绩向下浮动，直至不及格。

实验数据结构与算法篇6

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

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

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

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

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

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

实验数据结构与算法篇7

关键词：算法与数据结构,教学研究,教学改革

近年来, 信息技术已经改变人类社会生活的模式, 计算机技术的教育与应用得到了极大发展。数据结构作为计算机专业的七大核心课程之一, 被列为计算机科学与技术、软件工程、网络工程等信息类专业的全国统考研究生考试课程之一, 也是编译原理、操作系统、数据库原理、计算机网络等专业课程的先导课程, 在计算机专业课程体系中发挥着承上启下的核心作用。

一、数据结构与算法教学现状的分析

(一) 学生的课程学习现状

在传授学生学习算法和数据结构时, 学生的计算机编程的理论基础和应用经验往往是不同的, 因此很容易引起学生理解和掌握能力的偏差。

在实际授课中, 教学时间是有限的, 而且有的学生经常在听课的过程中聊天或玩游戏, 不按照训练复习。还有一些学生是为了应付期末考试和学习, 学习的方法和策略都没有用, 而且很难获得对知识的全面理解, 学习质量不高。

(二) 教学环节缺乏创新

以往的教学模式单一, 都是以教师为中心进行教学, 注重教学过程, 忽视学生的学习过程。学生只是被动接受学习, 根本无法提高学生的学习兴趣。

教师对计算机知识型内容的教学方法是比较熟悉的, 能够强调重点知识、讲解难点知识, 使学生能够有重点、有目标地进行学习, 但针对操作型内容教学则显得经验不足, 教学方法不当。

(三) 考核环节的缺陷

传统的考核模式是“以教师评价为主”, 强调最终评价结果, 当面临应用性评测时, 则暴露了它的缺点。学生本来就很难对一些知识进行运用, 而为了通过测试, 就抄袭、拷贝其他同学的程序, 所以经常出现全班的程序都是一个模版的情况。这样的考试不能考核出学生的真实水平。

二、教学研究中需要探索的内容

(一) 教学大纲的更新

教学大纲在教学中起着指导性的作用, 因此教学研究中务必跟踪新技术发展与数据结构的新算法, 不断更新教学内容, 完善教学大纲的编制。以算法与程序设计能力培养为主线, 提升学生应用基本结构分析问题、算法设计与编程的能力。结合《数据结构课程设计》等实践环节, 夯实学生的应用技能。

在教材方面, 可以选用张乃孝等人编著的高等教育出版社出版的最新版《算法与数据结构———C语言描述》作为主教材, 同时选用唐策善等人编著的高等教育出版社出版的《数据结构———用C语言描述》作为参考教材, 实现教材内容的高低配合, 理论算法与算法的相互补充。

(二) 教学模式的变革

在数据结构的教学改革中, 应摒弃传统的陈旧的教学模式。由浅入深、由线性到非线性、横向与纵向比对教学模式, 找出每种数据结构教学的优缺点。

(三) 强化实验和考核

数据结构实践教学要突出“理论与实践”的原则, 通过对问题的抽象, 选择合适的数据结构来解决实际问题, 提高应用能力。

考核评价设计紧密结合数据结构与算法课程, 注重过程考核、算法设计评价考核、实际解决问题能力的考核。加大实践环节考核的比例, 以阶段性课外作业的形式加强阶段性考核, 体现考核形式的多样化、考核标准的合理化以及考核的不间断性。

三、基于CDIO的多元教育模式教学改革

通过对当前数据结构教学的研究和分析, 笔者尝试将一种全能的工程理念———CDIO工程教育模式应用在指导数据结构教学的过程中。CDIO, 即构思 (conceive) 、设计 (design) 、实现 (implement) 和运作 (operate) , 它以产品研发到产品运行的生命周期为载体, 让学生以主动、实践、课程之间有机联系的方式学习工程。CDIO模式作为先进的多元教育模式可以很好地培养新型的优秀的工程人才。

(一) 教学指导思想的定位

CDIO模式突出了工程基础知识、个人能力、人际团队协调能力和工程系统能力。在完善数据结构课程教学指导思想时应当充分考虑以下几个方面。

1. 制定一体化教学计划。

新计划要大幅减少基础理论的权重, 可将涉及工程的一系列课程进行整合, 增加知识的综合运用能力。比如, 数据结构课程可以和C语言进行整合安排。

2. 以CDIO模式为基本环境。

应当以“基于项目的教育学习”为宗旨, 着力培养四种能力, 并围绕上述目标进行详细规划, 制定目标和标准。

3. 职业训练计划。

纳入CDIO模式后, 必须将学科学习与职业训练相结合, 要在大学期间融入优秀工程师的职业训练, 实际上也是四种能力培养的又一次强化。

(二) 精选实际问题用于设计性实验, 提高学生实际算法设计能力

由于数据结构课程与实际工程问题的融合, 在设计实验时, 要摒弃传统验证性的实验, 通过设计性实验来引导学生运用数据结构基础知识, 指导学生如何分析选择合适的数据结构, 传授正确的算法设计理念。通过设计一些实际的小型应用课题, 让学生自主探索实际运用算法的能力, 使学生有更多的创造空间。

(三) 以工程任务为牵引, 提高学生的算法设计创新能力

探索以实际的工程任务为牵引, 引导学生主动学习的新教学模式。改变传统教学中的先给学生布置作业, 然后再进行课堂教学的缺乏主动创新动力的模式。选取的工程任务力求既结合实际, 又能涵盖课程教学的要求。教师重点关注学生自学、开发和研究的进度。以工程任务为牵引的教学模式, 打破了算法设计类课程一贯采用的“填鸭式”教学模式, 变“要我学”为“我要学”。以任务为主线展开, 重在分析实际任务所涉及的数据结构、算法思路, 培养学生算法设计的创新能力。

(四) 考核评定的新标准

制定考核评定的标准应基于两个方面的考虑:一方面, 通过考核使教师和学生自觉以CDIO模式为前提开展数据结构课程的教与学, 避免推行CDIO模式流于形式化。另一方面, 考核标准要纳入CDIO模式原则和相关标准, 要实现从基础理论考核为主转变为“实践中学习”, 自主学习的实际动手能力考核。新标准要确立两个主体、三个客体:两个主体就是学生和教师。不仅考核学生的基础知识、自主学习能力、团队合作能力和工程软件项目能力, 而且要考核教师的CDIO模式运用能力、教师专业素质能力和调动学生兴趣的能力。三个客体是指考核的测评方:一是学校教学部门。主要考核教师的CDIO教学能力和学生最终的学习实践能力, 通过考核促进CDIO模式的推广和学生全方位适应用人单位的要求。二是合作项目单位。合作项目单位通过项目完成情况, 对学校、教师、学生的实际能力给予评价。三是授课教师。授课教师通过全过程的授课情况、学生完成项目情况、在项目合作中的表现和全课程中的自我学习情况, 结合基础知识考核给出学生综合分。

四、结语

CDIO模式是解决当前软件人才培养中学用脱节、不适应职业特征要素的有效举措。本文结合数据结构课程的教学改革与实践经验, 重点培养学生对基本数据结构的理解能力和应用能力, 提高算法设计和解决实际问题的综合能力, 为后续课程的学习与学生综合素质的提高打下坚实基础。

参考文献

[1]胡文龙.基于CDIO的工科探究式教学改革研究[J].高等工程教育研究, 2014 (1) .

[2]张伟, 王丽云.CDIO教学改革中的教学质量评估系统[J].辽宁大学学报, 2013 (3) .

[3]张国斌, 张树军, 刘春城, 等.基于CDIO模式的学生实践能力的培养[J].实验室科学, 2014 (1) .

[4]范会联, 仲元昌.基于CDIO理念的软件人才培养模式探索[J].实验室研究与探索, 2012 (1) .

[5]张婧, 韩雁, 梁志星.基于CDIO项目式教学的教师能力培养[J].重庆理工大学学报, 2013 (11) .

实验数据结构与算法篇8

【关键词】实时数据库；数据压缩；算法

应用于工业实时数据库的数据压缩算法要求达到两个方面的要求，一是较高的压缩比率，以满足海量数据存储的要求，二是较快的数据压缩和解压处理速度，以满足实时性的要求。目前在实时数据库的数据压缩算法中使用得较多的是基于有损压缩的算法，也就是通过减少采集数据点达到压缩的目的，人为导致数据的缺失，而且精度较低，压缩效果也有限，当数据变化较大时，则要在压缩之前对数据进行滤波处理，所以无法应用于对精度要求较高的工业生产领域。为了解决有损压缩方式存在的问题，可以采用无损数据压缩的算法对历史实时数据进行处理，并且根据不同实时数据的特征选择最为适合的压缩算法。

一、整体数据压缩方案设计

目前有很多实时数据库数据压缩的实施方案，一般情况下采用的是有损的旋转门算法，以及死区限值数据压缩算法，其特点是对实时数据进行处理的速度快，效率高，而且压缩的精度也在可接受范围内。但是对于高精度的工业控制领域，这类算法就不是很适用。造成目前工业实时数据压缩处理效果不尽如人意的原因还包括普通的方案并没有对工业数据库中的数据进行分类分析，而是采用同一种压缩算法对所有类型的数据进行处理。而不同压缩算法在对不同数据处理时表现出的性能是不同的。在实际的生产过程中，实时数据是将采样时间点上，每一个数据采集源上的时间数据、代码数据、数值型数据都发送到处理终端，等文件在缓存中积累到一定的大小后，由压缩模块负责对数据进行压缩和存档。由于上述三类数据的特点不同，不同类别的压缩算法对不同数据的处理效率也不同，所以，在工业实时数据压缩方案的设计中，必须要对数据的特点进行充分研究，选择适合的数据压缩算法，并且对算法进行一定的改进，使之能够具备更好的处理性能。同时，在方案设计时还需要考虑到数据解压的效率问题，在压缩时追求更高的压缩率，但是在对数据进行查询、统计、搜索等操作时，则需要对压缩数据进行解压处理后才能够实施，要提高查询的效率，就需要具有較高的压缩包解压效率。压缩和解压是一对矛盾的关系，所以必须要找到两者的平衡点。一般而言，数据越类似，其压缩的效率越高，而工业实时数据中的不同类别又有其自身的特点，所以在设计历史实时数据压缩方案时，首先对数据进行分类，然后分别采用不同的压缩方法进行处理。为了保证实时数据的精度，采用无损的通用压缩算法为基础，根据数据的特征进行选择和改进。针对于实时数据中的时间型数据和代码型数据，基于其一段时间内的重复率较高，所以采用RLE算法进行处理；对于浮点型数据利用改进的LZW算法进行处理，目的是提高其压缩率；对于布尔量数据，由于其自身占用的字节较少，只需要转换为比特位就可以实现压缩的目标；对于百分量型数据，主要是将LZ78算法与LZW算法相结合进行处理。

二、时间型数据的压缩算法设计

由于工业实时数据的采集是按周期完成的，所以时间型数据的特征是呈现出等差序列的排列方式，但这是理想情况，在实际的采集过程中，由于采集设备、通信线路等各方面因素的影响，有可能会出现1-2个毫秒的偏差，这对于以秒级作为周期的应用环境不会造成影响，即使是以毫秒级作为采集周期的应用，其影响也有限，所以在对时间型数据压缩处理中不考虑这一情况。另一种情况是出现漏点，这也是在实际的生产过程中不可避免的，对于这一情况的处理，一种可行的解决方案是人为地补充该点，并将该点的代码型数据或者浮点型数据设置为异常状态，仍然压缩到实时数据库中，在使用数据时不显示该点。但这一处理方式需要消耗一定的时间，而且也没有实际的意义，所以在本方案的设计中不考虑对这一情况的处理，实际上，漏点情况发生的概率很低。如果将时间型数据看成是等差序列，则只需要记录第一个点的时间值，后继的时间点都可以通过第一个点加上相应的时间周期得到，所以压缩处理过程中，将后一个时间数据减去前一个时间数据，得到一系列的差值，再进行压缩，由于是等差序列，所以差值相同，可采用对这一情况压缩性能最佳的RLE算法进行处理。在理想情况下，如果一个数据包单位内没有出现漏点的情况，则其压缩后只需要两个数据表示，而如果出现漏点的情况，则需要再增加两个数据，由于漏点情况极少出现，所以利用RLE算法对时间型数据处理可以达到极高的压缩效率。

三、代码型数据的压缩算法设计

代码型数据的特点是在一定的时间内不会发生改变，所以对它的压缩也采用RLE算法，而且相对于时间型数据，代码型数据不会出现偏差情况，也不需要进行预处理。在实际的工业实时数据采集环境中测试，采用RLE算法对代码型数据进行压缩，其压缩率可高达96%以上。

四、数值型数据的压缩算法设计

数值型数据是工业实时数据采集中的主要组成部分，也是数据压缩的难点，该类数据又可以分为布尔型数据、浮点型数据、百分量型数据三种，分别设计如下。

1、布尔型数据

该类型的数据只有两个值，非0即1，而在非经压缩的情况下，它需要占用一个字节，由于每一个比特位就可以有两种状态，所以不需要利用通用的无损压缩算法进行处理，只需要将布尔型数据按位设置，由于原本要用8个比特位表示的布尔值，现在只用1个比特位表示，所以这一处理方式可以使压缩率达到7/8。

2、百分量型数据

该类型的数据的特点是变化的幅度较小，用12位比特表示的百分型数据，相邻两个数据点之间的差值一般小于256，所以考虑对其相邻数据点的差值进行计算和压缩。所以选用LZW数据压缩算法，该算法压缩和解压的速度较快，满足实时数据库的应用需求；又考虑到百分量型数据主要是在数值上有差异，所以对传统的LZW算法进行改进，每一次读入的不是字节，而是数值，直接对差值进行压缩处理；又考虑到有可能出现的差值大于256的情况，所以结合LZ78数据压缩算法处理这种情况，将数值加入到字典中，并输出二元组。这一处理方式的优点在于：充分利用了LZW数据压缩算法运算时间短的优点，结合采用值压缩的处理方式，进一步提高了压缩效率；同时，通过引入LZ78算法，确保了一些意外数据值也可以得到处理，保证了实时数据的精度。

3、浮点型数据

工业实时数据中的浮点型数据一般用低精度浮点表示，其占用的字节数为2-4个。浮点数值的特点是在较小的时间间隔内变化不大，所以考虑用压缩相邻两点之间差值的方式实现数据压缩。由于浮点数的特殊性，即使在数值上相差较少，在二进制表达时也完全不同，所以直接选用任何一种通用数据压缩算法都无法取得较好的结果。为了保证处理的实时性，仍然以LZW算法为基础，对其进行改进处理。一是针对于该算法的字典容量存在限制，以及对于字符的匹配效率较低的问题，设计了新的字典生成算法，根据待处理实时数据的形态确定字典的容量，并引入了基于散列函数的数据搜索方法，用于对字符串进行匹配，有效地提高了处理的速度；二是基于LZW算法压缩率不高的问题，对浮点数进行预处理，使其满足LZW算法具有高压缩率时的数据特征，主要的做法是将不规律的浮点型数据差值转换为相应的百分量型数据，再应用LZW算法进行压缩处理。

五、结束语

本文针对传统有损数据压缩算法无法应用于高精度实时数据库的问题，提出了基于不同类型数据采用不同数据压缩算法的解决方案，实现了高精度的数据压缩，解决了数据精度和数据库存储容量之间的矛盾，在实际的应用过程中取得了良好的效果。

参考文献

[1]刘云生等.实时数据库系统（RTDBS）及其特征.华中理工大学学报，2010，06：66-70

[2]杨永军，徐江，许帅，舒逸.实时数据库有损压缩算法的研究.计算机技术与发展，2012（09）：59-62

[3]王君.基于实时数据库的有损线性压缩算法研究与改进.微计算机应用，2013（07）：99-101

[4]MarkNelson著，贾起东译.数据压缩技术原理与范例.北京：科学出版社，2010，04：312-315

[5]于翔.数据压缩技术分析.青海大学学报（自然科学版），2012，20（5）：52-54

[6]刘红霞，牛富丽.实时数据库数据压缩算法探讨与改进.化工自动化及仪表，2013（06）：38-40

【实验数据结构与算法】推荐阅读：

《数据结构》实验报告——排序05-30

数据结构实验3报告doc09-06