19610325j-数据结构与算法试验-教学大纲-丁宝峰

数据结构与算法(DataStructureandAlgorithm)课程代号：19600325j(实验19610325j)适用专业：计算机应用、软件、电子信息工程课程总学时数：64其中讲课：48学时实验：16学时学分：3.0+0.5数据结构与算法实验DataStructureandAlgorithmExperiments1.理论课程（或实验课程）课号：19610325j适用专业：计算机应用、软件、电子信息工程理论课程总学时：48实验总学时（周学时）：16学分：0.5开出实验个数：（验证实验0个；综合实验8个；综合设计实验0个）应开实验学期：2.实验课程简介：现在数据结构与算法在计算机专业知识的教学中地位极其重要。本门课程的实验课是本门课程学习的重要手段，学生应通过实验自己动手进行程序设计，以验证和设计相关的算法。实验课程通过8个实验，把数据结构与算法的主要内容的进行了验证与应用。.实验教学目标及基本要求：实验教学目标是要掌握数据结构与算法的基本实验套路，并在此基础上能够独立完成一般算法的分析和设计。.教材及主要参考书：教材 数据结构（C语言版），严蔚敏等，清华大学出版社，1997（2014印次）.主要参考书数据结构一用C语言描述，耿国华著，高等教育出版社，2012.算法与数据结构一C语言描述（第2版），张乃孝著，高等教育出版社，2006..考核办法对于程序调试的准确性来判断学生对程序语言的掌握程度。实验大纲主撰人：丁宝峰（电信学院电子信息教研室）实验项目1：熟悉数据结构上机环境.实验特点实验类型：综合实验类别：专业基础计划学时：2 每组人数：1首开日期：10周说明：实验类别指基础、专业基础、专业实验类型指验证、综合、设计。每组人数指教学实验项目中在每套仪器设备上完成本实验项目的人数。.实验目的与要求回顾如何使用实验环境Vc6.0；学习数据结构与算法上机实验过程；编辑运行实现顺序表抽象数据类型及其基本操作；.主要仪器设备序号主要仪器设备名称型号规格数量计算机100.实验内容提要回顾实验环境Vc6.0的使用。学习数据结构与算法上机实验过程。第一步：包含必要的标准头文件，如标准的输入输出头文件“stdio.h”,同时给出必要的符号常量宏定义；第二步：将某一数据结构所对应的类型定义存放在一个头文件当中，将某一数据结构所对应的基本操作算法存放在一个分类的.c文件当中.如：可以将单链表的有关类型定义存放在linklist.h中,将单链表的基本操作算法存放在 linklist.c中，之后通过文件包含#include"linklist.h"和#^^0"linklist.c",以实现对有关数据类型的引用及有关操作函数的调用；第三步：编写基于某种数据结构的具体问题的算法；第四步：编写主函数，其中进行合理的函数调用，形成一个可执行程序。编辑实现顺序表抽象数据类型的头文件。详细内容参考教材Page22：线性表的动态分配顺序存储结构。编辑实现顺序表抽象数据类型的基本操作：InitList_Sq()；并进行编译和运行。详细内容参考教材Page23：算法2.3。编辑实现顺序表抽象数据类型的操作：AssignList_Sq()；并进行编译和运行。概要：#include“stdlib.h”for(i=0;i<10;i++){p->elem[i]=rand()%100;p->length++;}//assign编辑实现顺序表抽象数据类型的操作：OutputList_Sq()；并进行编译和运行。for(i=0;i<10;i++){“Theelementare:%d\n”，p->elem[i];}//output.实验操作要点首先，应注重了解实验环境的操作；其次，所有抽象数据类型中的抽象描述都要给出符合C语言的明确说明/定义，可以统一放在头文件中，以便重复使用；最后，注意所有的操作都应在main()中调用执行。.注意事项注意既要包含必要的标准头文件，还要包含自己编写的头文件；在调试正确后，几个操作的代码要放入头文件，以便后续实验重复使用；调试时的错误与警告信息的提示。实验项目2：顺序表的实现.实验特点实验类型：综合实验类别：专业基础计划学时：2 每组人数：1首开日期：10周说明：实验类别指基础、专业基础、专业实验类型指验证、综合、设计。每组人数指教学实验项目中在每套仪器设备上完成本实验项目的人数。.实验目的与要求掌握线性表的顺序存储实现；掌握在顺序表存储实现下，利用基本操作实现较复杂的操作;.主要仪器设备序号主要仪器设备名称型号规格数量1计算机100实验内容提要掌握线性表的顺序存储实现；详细内容参考实验一(3)：线性表的动态分配顺序存储结构。利用基本操作实现较复杂的操作ListInsert_sq()；概要：#include”实验一的头文件”〃顺序表类型定义，调用其中的相关操作InitList_Sq()；AssignList_Sq()；OutputList_Sq()；〃改变前的ListInsert_sq(); 〃参考教材Page24：算法2.4OutputList_Sq()；〃改变后的利用基本操作实现较复杂的操作ListDelete_sq()；概要：#include”实验一的头文件”〃顺序表类型定义，调用其中的相关操作InitList_Sq()；AssignList_Sq()；OutputList_Sq()；〃改变前的ListDelete_sq(); 〃参考教材25：算法2.5OutputList_Sq()；〃改变后的.实验操作要点一是，实验一的头文件中的类型定义等的名称应与本次实验保持一致；二是，调用各种操作时传递实参要匹配；三是，反复调用Output()是为了看到改变的前后区别。.注意事项注意既要包含必要的标准头文件，还要包含自己编写的实验一的头文件;注意工作区的使用:一是头文件与主函数文件应该在一个工作区内，二是实验内容(2)与实验内容(3)应该分开在两个工作区内，因为有两个main()；注意调试时的错误与警告信息的提示。实验项目3：单链表的实现.实验特点实验类型：综合实验类别：专业基础计划学时：2每组人数：1首开日期：11周说明：实验类别指基础、专业基础、专业实验类型指验证、综合、设计。每组人数指教学实验项目中在每套仪器设备上完成本实验项目的人数。.实验目的与要求掌握线性表的链式存储表示；掌握线性表的链式存储的基本操作；掌握在线性表的链式存储实现下，利用基本操作实现较复杂的操作；.主要仪器设备序号主要仪器设备名称型号规格数量1计算机100.实验内容提要线性表的链式存储实现；详细内容参考教材Page37：带头结点的线性链表的类型定义。编辑运行实现线性链表的基本操作：InitList()；InitList()详细内容参考教材Page30：算法2.11—CreateList_L()编辑运行实现线性链表的基本操作：ListTraverse()；详细内容参考教材Page29：算法2.8；添加output()部分。利用基本操作实现较复杂的操作：InsBefore()；详细内容参考教材Page38—39：算法2.20。.实验操作要点存储采用带头结点的单链表，那么各种操作要与存储实现形式保持一致。.注意事项处理时注意有头结点；另外，单链表的处理注意保存当前节点和前一个节点，以免回溯。实验项目4：顺序栈的实现.实验特点实验类型：综合实验类别：专业基础计划学时：2 每组人数：1首开日期：11周说明：实验类别指基础、专业基础、专业实验类型指验证、综合、设计。每组人数指教学实验项目中在每套仪器设备上完成本实验项目的人数。.实验目的与要求掌握栈的顺序存储表示；掌握栈的顺序存储的基本操作；掌握在栈的顺序存储实现下，栈的应用；.主要仪器设备序号主要仪器设备名称型号规格数量1计算机100.实验内容提要栈的顺序存储详细内容参考教材Page46：栈的顺序存储表示；栈的顺序存储的基本操作详细内容参考教材47：栈的顺序存储表示；数制转换详细内容参考教材Page48：算法3.1；表达式求值；详细内容参考教材54：算法3.4；.实验操作要点栈的存储采用顺序存储，因此注意实现时的具体情况。.注意事项注意栈空与栈满这两种溢出情况的判断与处理。实验项目5：队列的实现.实验特点实验类型：综合实验类别：专业基础计划学时：2 每组人数：1首开日期：12周说明：实验类别指基础、专业基础、专业实验类型指验证、综合、设计。每组人数指教学实验项目中在每套仪器设备上完成本实验项目的人数。.实验目的与要求掌握队列的链式存储表示；掌握队列的链式存储的基本操作；掌握循环队列的顺序存储表示；掌握循环队列的顺序存储的基本操作；.主要仪器设备序号主要仪器设备名称型号规格数量1计算机100.实验内容提要编辑运行队列的链式存储表示；详细内容参考教材Page61：队列的链式存储结构；编辑运行队列的链式存储的基本操作；详细内容参考教材Page62：队列的链式存储的基本操作：InitQueue、EnQueue、DeQueue、QueueTraverse、OutputQueue等；编辑运行循环队列的顺序存储表示；详细内容参考教材Page64：循环队列的顺序存储结构；编辑运行循环队列的顺序存储的基本操作；详细内容参考教材65：循环队列的顺序存储的基本操作：InitQueue、EnQueue、DeQueue、QueueTraversaOutputQueue等；.实验操作要点链式存储实现时注意指针的使用；循环队列要注意队头、队尾指针。.注意事项注意队列溢出、假溢出时指针的判断。实验项目6：稀疏矩阵转置算法的实现.实验特点实验类型：综合实验类别：专业基础计划学时：2每组人数：1首开日期：12周说明：实验类别指基础、专业基础、专业实验类型指验证、综合、设计。每组人数指教学实验项目中在每套仪器设备上完成本实验项目的人数。.实验目的与要求掌握稀疏矩阵的顺序存储表示：三元组顺序表；掌握稀疏矩阵的顺序存储表示下的基本操作；掌握稀疏矩阵转置算法的实现；.主要仪器设备序号主要仪器设备名称型号规格数量1计算机100.实验内容提要稀疏矩阵的顺序存储表示：三元组顺序表；详细内容参考教材Page98：稀疏矩阵的三元组顺序表存储结构；稀疏矩阵的顺序存储表示下的基本操作；详细内容参考教材95：数组的顺序存储的基本操作：InitArray,InputArray、OutputArray等；稀疏矩阵转置算法的实现；详细内容参考教材Page99：算法5.1；稀疏矩阵转置改进算法的实现；详细内容参考教材Page100：算法5.2；.实验操作要点采用顺序存储，注意C中数组下标的使用；在改进算法中，注意辅助向量的使用；.注意事项注意数组下标的使用。实验项目7：二叉树.实验特点实验类型：设计实验类别：专业基础计划学时：2 每组人数：1首开日期：13周说明：实验类别指基础、专业基础、专业实验类型指验证、综合、设计。每组人数指教学实验项目中在每套仪器设备上完成本实验项目的人数。.实验目的与要求掌握二叉树的线索化；掌握哈夫曼树及哈夫曼编码的使用；.主要仪器设备序号主要仪器设备名称型号规格数量1计算机100.实验内容提要二叉树的线索化；详细内容参考教材135：二叉树的二叉线索存储表示；算法6.6或算法6.7；哈夫曼编码；详细内容参考教材148：哈夫曼树和哈夫曼编码的存储表示;求哈夫曼编码的算法：算法6.12或算法6.13；.实验操作要点二叉树的线索化时，得先建立一棵二叉树，并输入模拟数据，才能对其进行线索化；求哈夫曼编码时却不需要，因为算法要先构建哈夫曼树，并输入模拟数据，才能求得哈夫曼编码。.注意事项使用动态分配存储空间的使用；注意递归算法与非递归算法的区别。实验项目8：图.实验特点实验类型：综合实验类别：专业基础计划学时：2 每组人数：1 首开日期：13周说明：实验类别指基础、专业基础、专业实验类型指验证、综合、设计。每组人数指教学实验项目中在每套仪器设备上完成本实验项目的人数。.实验目的与要求掌握图的数组表示法存储；掌握图的邻接表存储；掌握无向网的最小生成树算法;掌握有向网的关键路径算法。.主要仪器设备序号主要仪器设备名称型号规格数量1计算机100.实验内容提要图的数组表示法存储；详细内容参考教材Page161：图的数组（邻接矩阵）存储表示；无向网的最小生成树算法；详细内容参考教材Page175：算法7.9（Prim算法）；图的邻接表存储；详细内容参考教材Page163：图的邻接表存储表示；有向网的关键路径算法；详细内容参考教材Page185：算法7.13（求最早发生时间）、算法7.14