文档介绍：数据结构和算法分析基础
实验］

（实验估计时间：90分钟）

除了进行科学计算之外，计算机已经被广泛地应用在控制、管理和数据处理等非数值计算的领域中。与此相应，处理对象也由早先纯序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。
一个算法应该具有以下5个重要的特征。
1）有穷性：一个算法必须保证执行有限步骤之后结束。
2）确切性：算法的每一步骤必须有确切的定义。
3）可行性：算法中的每一步骤必须充分可及，即算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
4）输入：一个算法有0个或多个输入，以刻画运算对象的初始情况。所谓0个输入是指算法本身定义了初始条件。
5）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。

要用计算机解决一个稍为复杂的实际问题，大体都要经历如下步骤（示）O
实际问题
抽象

数学模型
非形式算法
设计
\
-v
数据结构
算法
编码
K

数据类型
程序

1）将实际问题数学化。即把实际问题抽象为一个带有一般性的数学问题。这一步要引入一些数学概念，精确地阐述数学问题，弄清问题的已知条件、所要求的结果，以及在已知条件和所要求的结果之间存在着的隐式或显式的联系等。
2）对于确定的数学问题，设计其求解的方法。即所谓的算法设计。这一步要建立问题的求解模型，即确定问题的数据模型并在此模型上定义一组运算。然后，借助于对这组运算的调用和控制，从已知数据出发导向所要求的结果，形成算法并用自然语言来表述。这种语言还不是程序设计语言，不能被计算机所接受。
3）用计算机的某种程序设计语言来表达己设计好的算法。换句话说，将非形式自然语言表达的算法转变为一种程序设计语言表达的算法。这一步叫程序设计。
4）在计算机上编辑、调试和测试编制好的程序，直到输出预期的结果。
在这里，我们只关心第3步，而且把注意力集中在算法程序表达的抽象机制上，目的是引入一个重要的概念一一抽象数据类型，同时为大型程序设计提供一种相应的自顶向下逐步求精、模块化的具体方法，即运用抽象数据类型来描述程序的方法。
抽象数据类型（abstract data types,简称ADT）是算法设计和程序设计中的重要概念。严格地说，它是算法的一个数据模型连同定义在该模型上、作为该算法构件的一组运算。这个概念明确地把数据模型与作用在该模型上的运算紧密地联系起来。
事实正是如此。一方面，数据模型的运算依赖于数据模型的具体表示，因为数据模型运算以数据模型中的数据变量作为运算对象，或作为运算结果，或二者兼而为之; 另一方面，有了数据模型的具体表示以及数据模型运算的具体实现，运算的效率随之确定。
于是，就有这样的一个问题：如何选择数据模型的具体表示使该模型上的各种运算的效率都尽可能地高？很明显，对于不同的运算组，为使组中所有运算的效率都尽可能地高，其相应的数据模型所具体表示的选择将是不同的。在这个意义下，数据模型的具体表示又反过来依赖于数据模型上定义的那些运算。特别是，当不同运算的效率互相制约时，还必须事先将所有运算的相应使用频度排序，让所选择的数据模型的具体表示优先保证使用频度较高的运算有较高的效率。数据模型与定义在该模型上的运算之间存在着的这种密不可分的联系，是抽象数据类型的概念产生的背景和依据。
一些基本抽象数据类型，包括表、栈、队列、串、树、二叉树和图等，是最基本
和最简单的，并且是实现其他抽象数据类型的基础。
高级抽象数据类型主要包括集合、字典、散列表、有序字典、并查集、优先队列、
优先级树和堆、检索树、搜索树、分离集合等。

1）理解数据结构和算法的基本概念。
2）通过因特网搜索与浏览，了解数据结构和算法的计算环境，了解因特网环境中主流的数据结构和算法技术网站。
3）掌握通过专业网站不断丰富数据结构和算法最新知识的学习方法，尝试通过专业网站的辅助和支持来开展数据结构和算法的应用实践。

在开始本实验之前，请回顾教科书的相关内容。
需要准备一台带有浏览器，能够访问因特网的计算机。

1）请查阅有关资料，简单叙述下列概念：
数据结构：
算法：
ADT：
2）请简述数据结构与算法对计算机学科的意义。
3）请教你的老师或者查阅有关的专业教学计划，并简述：
①在你主修的专业中，数据结构课程与哪些后续课程有什么关联?
②就你主修的专业而言