第2章算法分析与数据结构.docx

版本控制页

版本控制表
序号版本号版本性质创建时间建议人修订人修改日期修改内容简述备注V0.00初稿11.5.2007王文丛一校孔祥萍二校2008.11.11赵元
算法分析与数据结构
本章主要内容：
算法
数据抽象
算法复杂度的计算
数组
栈
队列
链表
树
哈希表
图
本章重点：
数据抽象
算法复杂度的计算
栈的定义及基本运算
队列的定义及基本运算
哈希表
本章难点：
算法复杂度的计算
链表实现
哈希表的实现
学完本章您将能够：
了解数据抽象概念
掌握基本复杂度的计算方法
了解常用数据结构的概念及实现
引言
使用计算机解决实际问题的过程，就是分析问题涉及的数据、合理组织数据以及规划解决问题的算法的过程。在计算机科学的发展过程中，分析、组织数据和规划算法被单独成一个学科，这就是数据结构。数据结构在计算机科学技术中，尤其是在网络游戏程序设计中起到了举足轻重的作用。数据结构是网络游戏开发的核心知识之一，是许多后续内容的重要基础。从这里开始，将带领大家开始数据结构知识的学习。本章首先来学习数据结构的基本概念。
算法描述
算法是解题的步骤，可以把算法定义成解决某类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，代表用计算机解一类问题的精确、有效的方法。“算法+数据结构=程序”，求解一个给定的可计算或可解的问题，不同的人可以编写出不同的程序，来解决同一个问题。算法和程序之间存在密切的关系。
算法是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算，是对解题方案的准确与完整的描述。制定一个算法，一般要经过设计、确认、分析、编码、测试、调试、计时等阶段。
一个算法可以用自然语言、计算机程序语言或其他语言来说明，惟一的要求是该说明必须精确地描述计算过程。
算法的描述方法可以归纳为以下4种：
1）自然语言；
2）图形，如NS图、流程图，图的描述与算法语言的描述对应；
3）算法语言，即计算机语言、程序设计语言、伪代码；
4）形式语言，用数学的方法，可以避免自然语言的二义性。
人们的生产活动和日常生活离不开算法，都在自觉不自觉地使用算法。例如，人们到商店购买物品，会首先确定购买哪些物品，准备好所需的钱，然后确定到哪些商场选购、怎样去商场、行走的路线是什么，若物品的质量好如何处理，对物品不满意又怎样处理，购买物品后做什么等。以上购物的算法是用自然语言描述的，也可以用其他描述方法描述该算法。
数据抽象
数据抽象是程序设计的中心内容。这种抽象被称为数据抽象类型，它定义了数据取值范围和表示结构，以及对数据的操作集。也就是说，数据抽象类型给出了一种用户定义的数据类型，其运算符指明了用户如何操作数据，数据抽象类型与具体应用无关，这可使程序员把注意力集中在数据及其操作的理想模型上。例如：
圆是平面上圆心等距的所有点的集合。从图形显示角度看，圆的抽象数据类型包括圆心和半径，从计算的角度看，其抽象数据类型只需要半径。
ATDCirleis//抽象数据类型名称
Data//抽象数据类型的数据描述结构
//非负实数，给出圆的半径
Operations
Constructor//构造函数
Initialvalues: 圆的半径//初始化对象
Process: 给圆的半径赋初值
Area//操作说明，本例为计算
//圆面积
Input: 无//用户输入
Preconditions: 无//系统执行本操作前数据所必须的状态
Process: 计算圆的面积//对数据进行的操作
Output: 返回圆的面积//返回给用的数据
Postconditions:无//系统执行操作后的数据状态
Circumference//操作说明，本例为计算圆
Input: 无
Preconditions: 无
Process: 计算圆的周长
Output: 返回圆的周长
Postconditions:无
endADTCircle
可以把上述抽象数据类型转换成c++代码。
classCirle
{
public:
Cirle(floatr){m_Radii=r;}
floatArea();//计算圆面积
floatCirumference();//计算圆周长
private:
floatm_Radii;
};
算法复杂度的计算
空间复杂度
程序所需要的空间主要由指令空间、数据空间、环境栈空间构成。
指令空间
指令空间是指用来存储经过编译之后的程序指令所需的空间。
程序所需要的指令空间的数量取决于如下因素：
1）把程序编译成机器代码的编译器；
2）编译时实际采用的编译器选项；
3）目标计算机。
数据空间
数据空间是指用来存储所有常量和所有变量值所需的空间。数据空