数据结构与算法实验指导书(计科1021).doc

《数据结构与算法》实验指导书 实验课程编号：07ZB101109 实验室名称：多媒体技术实验室 系（院）：数计学院 实验室地点：N5-402 实验课学时：36 实验类别：专业课 适用专业：计算机科学与技术 是否独立设课：是 执笔人：李文新 审批人： 一、实验课程教学目的和要求 《数据结构与算法》是一门实践性很强的课程，光靠读书和做习题是不能提高实践能力的。 《数据结构与算法》的实验与程序设计语言课程中的实验不同，后者更多的强调语言方面的功能实现，而前者更接近实际，需要同学们自己分析问题，设计模型和算法，再上机调试完成。 《数据结构与算法》的实验的目的主要有两个： 1）深化理解书本上的理论知识，将书本的知识变“活”（为已掌握，为已活用）； 2）理论和实践相结合，学会将相关的数据结构和算法应用于解决实际问题，培养数据结构的应用能力和软件工程所需要的实践能力。 《数据结构与算法》的实验类型 1）验证性实验—主要是验证教材中已有的数据结构和算法。 2）设计性实验—针对具体问题，应用某一个知识点，自己设计数据结构和算法，培养对数据结构的简单运用能力。 3）综合性实验—针对具体问题，应用某几个知识点，自己设计数据结构和算法，培养对数据结构的综合运用能力。 《数据结构与算法》的实验安排 项目 实验题目 学时 说明 一 二 结构体的运用 结构体与指针的运用 顺序表的保序插入操作 2 2 2 设计 设计 设计 三 链表的保序插入操作 2 设计 四 循环单链表的插入和删除 2 设计 五 栈与队的操作 2 验证 六 栈与队的的应用 2 设计 七 对称矩阵的压缩存储 2 验证 八 压缩矩阵的应用 2 设计 九 二叉树的操作 2 验证 十 二叉树的应用 2 设计 十一 二叉树的应用 2 设计 十二 图的操作 2 验证 十三 图的应用 2 设计 十四 图的应用 2 设计 十五 查找操作 2 验证 十六 查找应用 2 设计 十七 排序操作 2 验证 十八 排序应用 2 设计 《数据结构与算法》实验的一般步骤 1）需求分析：要对简单的问题描述进行详细的分析，充分理解问题，明确问题要求做什么，有什么数据，边界条件……。 2）概要设计：针对问题描述中涉及到数据定义抽象数据类型，设计数据结构和算法模型。本部分不必考虑实现的细节。 3）详细设计：设计具体的存储结构（用C++实现抽象数据类型对应的类）。此外，还要设计对象间的调用关系及输入输出。 4）上机调试（运行代码，修正语法及逻辑错误） 5）结果与总结 《数据结构与算法》的实验要求： 1）完成实验预习； 2）完成并上交实验报告； 3）完成电子设计文档 预习/实验报告的格式要求： 1）实验名称 2）实验目的 3）实验内容及要求 4）概要设计：ADT 5）详细设计：C++类或C函数 6）调试分析： 7）结果与总结 实验一: 结构体的运用 一、实验目的： 1）结合C++的输入输出流复习C语言的知识； 3）掌握结构体的运用方法。 二、实验内容及要求： 一个班有n个学生，每个学生有学号（no）、姓名（name）、年龄（age）、成绩（score）。定义结构体来描述学生信息。并定义n个学生的结构体数组。 要求： 设计一个函数，输入n个学生的数据；提示性输入。 设计一个函数，输出n个学生的数据；输出整齐，控制域宽。 设计主函数，调用输入输出函数。 分别定义结构体数组为全局变量和局部变量两种情形进行调试和运行程序。 结构体与指针的运用 一、实验目的： 1）结合C++的输入输出流及动态分配/撤消运算符复习C语言的知识； 3）掌握结构体与指针的运用。 二、实验内容及要求： 建立一个动态链表，链表的结点结构： data next 其中：data为整数类型，next为指针类型 链表示例： 其中：head为指向该链表的头指针。 要求： 定义一个结构体：描述结点信息； 设计一个函数，动态建立该链表； 设计一个函数，输出该链表的数据； 设计主函数，调用建立链表和输出链表数据的函数。 分别定义head为全局变量和局部变量两种情形进行调试和运行程序。当head为局部变量时应将建立链表函数的参数设为引用参数。 实验二: 顺序表的保序插入操作 一、实验目的： 1）掌握线性表的顺序存储结构与算法实现； 3）掌握顺序表的逻辑插入方法。 二、实验内容及要求： 设计：主函数、构建n个整数的顺序表函数、保序插入函数、输出函数。 提示：主函数中调用构建n个整数的顺序表函数并调用输出函数； 调用保序插入函数实现插入操作并调用输出函数输出。 实验三: 单链表的保序插入操作 一、实验目的： 1）掌握线性表的链接存储结构与算法