数据结构与算法实验教程.doc

数据结构与 算法实验  内容简介 《数据结构与算法实验教程》是为了使学生能够尽快地掌握数据结构中的各种算法而编写的。本教材所写算法结构清晰、可读性强、易于调试、符合软件工程的规范要求等特点。所有实验项目都给出了完整的C语言程序，对关键的算法及语句都给出了详细的注释。所有程序都在Visual C++环境下调试运行通过。本书结合c++面向对象程序设计的特点，讨论了数据结构与算法基础知识，并构建了实验与课程设计。 全书共分5章。主要内容包括绪论、线性表的基本操作及多项式的算术运算、二叉树的基本操作、图的基本运算、各种内排序算法的实现及性能比较。 通过《数据结构与算法实验教程》的学习，不但能迅速提高数据结构与算法的水平，同时还能提高c++程序设计的能力。通过对本书的学习，可掌握面向过程的程序设计方法，分析问题空间中的需求、进行功能划分，明确每个功能函数以及它们之间的关系。可以进一步比较学习面向对象的程序设计方法，分析问题空间中的类及类之间的关系。此外，可学会确定系统中每个函数的合理组织方法，明确定义函数的主要数据结构和外部接口。同时，可利用数据结构所学知识设计结构清晰的算法和程序，分析所设计的算法的时间和空间复杂度等。 本书可作为数据结构与算法分析、数据结构、数据结构与算法设计、数据结构与算法等课程实验与课程设计的教材，也可供其他从事软件开发工作的读者学习参考使用。  目 录 _Toc455834628 第1章 绪论 1 1.1 知识点概述 1 1.1.1 基本概念及有关术语 1 1.1.2 重点难点 2 1.2 算法的衡量 2 1.2.1 算法的定义 2 1.2.2 算法复杂度的渐近表示法 3 第2章 线性表的基本操作及多项式的算术 5 2.1 知识点概述 5 2.2 线性表的顺序存储实验 6 2.2.1 实验目的 6 2.2.3 实验内容 6 2.2.3 实验步骤 6 2.3 线性表的链式存储实验 10 2.3.1 实验目的 10 2.3.2 实验内容 10 2.3.3 实验步骤 10 2.4 线性表的应用—多项式的算术运算 16 2.4.1 实验目的 16 2.4.2 实验内容 16 2.4.3 实验步骤 16 2.5 思考题 20 2.6 小结 20 第3章 栈与队列 21 3.1 知识点概述 21 3.2 栈与队列实验 22 3.2.1 实验目的 22 3.2.2 实验内容 22 3.2.3 实验步骤 22 3.3 思考题 40 3.4 小结 41 第4章 二叉树的基本操作 42 4.1 知识点概述 42 4.1.1 树及二叉树 42 4.1.2 术语 45 4.1.3 二叉树的遍历 45 4.2 二叉树实验 46 4.2.1 实验目的 46 4.2.2 实验内容 46 4.2.3 实验步骤 46 4.3 思考题 52 4.4 小结 52 第5章 图的基本运算 53 5.1 知识点概述 53 5.2 图的实验 55 5.2.1 实验目的 55 5.2.2 实验内容 55 5.2.3 实验步骤 55 5.3 思考题 59 5.4 小结 59 第6章 各种内排序算法的实现及性能比较 60 6.1 知识点概述 60 6.2 排序实验 62 6.2.1 实验目的 62 6.2.2 实验内容 62 6.2.3 实验步骤 62 6.3 思考题 76 6.4 小结 76 参考文献 77 绪论 1.1.1 基本概念及有关术语 10．算法设计的5个基本要： (1) 正确性。算法应满足具体问题的需求，这是算法设计的基本目标。 (2) 可读性。算法的可读性有助于人对算法的理解，便于系统设计人员之间的合作与交流也便于对算法相应的程序进行调试和查错。 (3) 健壮性。当输入非法数据时，算法要能作出适当处理，而不至于产生莫名其妙的输出结果。 (4) 高时间效宰。算法的时间效宰指的是算法的执行时间效卒。对解决统一问题而言，执 行时间越短的算法，其时间效率越高。 (5) 高空间效率。算法在执行时一般要求额外的存储空间。对于同一问题而言，如果多个算法可供选择，则存储空间要求较低的算法具有较高的空间效率。 1.1.2 重点难点 重点：数据结构、逻辑结构、存储结构(物理结构)、算法及算法分析。 难点：算法及算法分析。 解决一个具体的问题，不同的人有不同的解决方法，那到底谁的算法要好些呢?一般的想法是，看看谁的算法运行的时间较短，运行时间越短的算法我们认为要好些，这种比较算法好与坏的方法称为事后统计法