数据结构与算法实验指导书

《数据结构与算法实验指导书》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构与算法》实验指导书实验课程编号：07ZB101109实验室名称：多媒体技术实验室系（院）：数计学院实验室地点：N5-402实验课学时：36实验类别：专业课适用专业：计算机科学与技术是否独立设课：是执笔人：李文新审批人：一、实验课程教学目的和要求《数据结构与算法》是一门实践性很强的课程，光靠读书和做习题是不能提高实践能力的。《数据结构与算法》的实验与程序设计语言课程中的实验不同，后者更多的强调语言方面的功能实现，而前者更接近实际，需要同学们自己分析问题，设计模型和算法，再上机调试完成。《数据结构与算法》的实验的目的主要有两个：

2、1）深化理解书本上的理论知识，将书本的知识变“活”（为已掌握，为已活用）；2）理论和实践相结合，学会将相关的数据结构和算法应用于解决实际问题，培养数据结构的应用能力和软件工程所需要的实践能力。《数据结构与算法》的实验类型1）验证性实验—主要是验证教材中已有的数据结构和算法。2）设计性实验—针对具体问题，应用某一个知识点，自己设计数据结构和算法，培养对数据结构的简单运用能力。3）综合性实验—针对具体问题，应用某几个知识点，自己设计数据结构和算法，培养对数据结构的综合运用能力。《数据结构与算法》的实验安排项目实验题目学时说明一顺序表的保序

3、插入操作2验证二单链表的操作2验证三循环单链表的插入和删除2设计四栈与队的操作2验证五栈与队的的应用2设计六栈与队的的应用2设计七对称矩阵的压缩存储2验证八压缩矩阵的应用2设计九二叉树的操作2验证十二叉树的应用2设计十一二叉树的应用2设计十二图的操作2验证十三图的应用2设计十四图的应用2设计十五查找操作2验证十六查找应用2设计十七排序操作2验证十八排序应用2设计《数据结构与算法》实验的一般步骤1）需求分析：要对简单的问题描述进行详细的分析，充分理解问题，明确问题要求做什么，有什么数据，边界条件……。2）概要设计：针对问题描述中涉及到数

4、据定义抽象数据类型，设计数据结构和算法模型。本部分不必考虑实现的细节。3）详细设计：设计具体的存储结构（用C++实现抽象数据类型对应的类）。此外，还要设计对象间的调用关系及输入输出。4）上机调试（运行代码，修正语法及逻辑错误）5）结果与总结《数据结构与算法》的实验要求：1）完成实验预习；2）完成并上交实验报告；3）完成电子设计文档预习/实验报告的格式要求：1）实验名称2）实验目的3）实验内容及要求4）概要设计：ADT5）详细设计：C++类或C函数6）调试分析：7）结果与总结实验一:顺序表的保序插入操作一、实验目的：1）掌握线性表的顺序

5、存储结构与算法实现；2）掌握顺序表及其基本操作的实现。二、实验内容及要求：1）建立含有若干个元素并递增有序的顺序表；2）对已建立的顺序表实现保序插入、删除、查找、输出等基本操作。实验二:单链表的操作一、实验目的：1）掌握线性表的链接存储结构；2）掌握链表及其基本操作的实现。二、实验内容及要求：1）用头插法（或尾插法）建立带头结点的单链表；2）对已建立的单链表实现插入、删除、查找、输出等基本操作。实验三:循环单链表的插入和删除一、实验目的：1）进一步掌握线性表的链接存储结构；2）掌握循环单链表及其基本操作的实现。二、实验内容及要求：1）

6、用头插法（或尾插法）建立带头结点的循环单链表；2）在采用尾指针（rear）表示的循环单链表中，查找元素为x的结点，如果有则删除该结点；如果没有则插入到循环单链表的尾部。操作接口：TLinkListLDI(Tx)实验四:栈与队的操作一、实验目的：1）掌握栈和队的顺序与链接存储结构；2）掌握栈和队的操作特性；3)掌握顺序栈和链队列的基本操作的实现方法。二、实验内容及要求：1）分别建立一个空的顺序栈和空的链队列；2）对已建立的顺序栈和链队列实现插入、删除、取栈顶元素、取队头元素及输出等基本操作。实验五：栈与队的的应用（括号匹配问题）一、实验

7、目的：1）掌握栈和队列的存储结构；2）掌握栈和队列的操作特性；3）掌握栈和队列基本操作的实现。二、实验内容及要求：括号匹配问题在算述表达式中，可能出现嵌套的大、中、小括号，设计一个算法，可以判断给定的表达式串中的括号是否是匹配的。要求：首先，分别先定义一个栈和一个队；其次，将表达式串中的各种括号字符依次入队（其它字符不予考虑）；最后利用栈来判断队中的括号是否是匹配的。无论是什么括号，最后出现的左括号，必须与其后最先出现的右括号匹配，这符合栈的后进先出的特点，故我们可以用栈和进行匹配性判断。根据要求，串(括号)à队à栈操作接口：bool

8、match(char*s)主要操作：队，栈初始化括号字符入队出队为左括号：进栈出队为右括号：弹栈匹配？实验六：栈与队的的应用（表达式求值）一、问题描述：1）对一个合法的中缀表达式求值；2）假设表达式只包含+、－、×、÷4