学习数据结构应从最基础的概念开始.

1、 数据结构和算法简介数据结构和算法简介数据结构数据结构(C#描述描述) 目标目标 在本章中，你将达到如下目标： 了解问题求解的基本步骤 认识数据结构,熟悉其基本概念 熟悉算法的定义及特征 了解算法分析与度量的方法 初步了解本教材进行问题求解的基本思路 数据结构和算法简介数据结构和算法简介数据结构数据结构(C#描述描述) 问题描述问题描述 某电信部门想开发一个查询知名电子企业服务电话号 码的程序。要求对于任意给出的一个企业名称，若该 企业已注册其服务电话号码，则迅速找到其电话号码； 否则指出没有该企业的服务电话号码。 问题引入问题引入查找电话号码问题查找电话号码问题 数据结构和算法简介数据结构和

2、算法简介数据结构数据结构(C#描述描述) 问题引入问题引入查找电话号码问题查找电话号码问题 首先构造一张电话号码信息表。 接着将电话号码登记表存储到计算机中 。 然后确定解决问题的算法。 最后编程实现算法，写出C#的实现代码. 解决问题的步骤解决问题的步骤 数据结构和算法简介数据结构和算法简介数据结构数据结构(C#描述描述) 问题引入问题引入问题求解的基本步骤问题求解的基本步骤 根据实际问题，确定数据及数据之间的关系，即对数据的结构进行设 计 分析对数据结构可能进行的操作，设计算法； 用一种存储结构在计算机内部表示数据及数据之间的关系； 根据存储结构的存储方式及设计的算法实现算法的计算机表示；

3、 使用己实现的存储结构及算法解决实际问题。 数据结构和算法简介数据结构和算法简介数据结构数据结构(C#描述描述) 认识数据结构认识数据结构数据的概念数据的概念 数据是对客观事物的符号表示，在计算机科学中是 指所有能输入到计算机中并被计算机程序处理的符 号的总称 数据结构和算法简介数据结构和算法简介数据结构数据结构(C#描述描述) 认识数据结构认识数据结构数据元素和数据项数据元素和数据项 数据元素是数据的基本单位，是计算机进行输入输出操作的最 小单位。 数据元素可以由不可分割的数据项组成 。 数据结构和算法简介数据结构和算法简介数据结构数据结构(C#描述描述) 认识数据结构认识数据结构数据结构的

4、概念数据结构的概念 数据结构是相互之间存在一种或多种特定关系的数据元素的集 合 。 数据结构=数据元素+关系（结构） 在任何问题中，数据元素都不是孤立存在的，而是在它们之间 存在着某种关系，这种数据元素相互之间的关系称为结构 根据数据元素之间关系的不同特性，通常有四类基本结构 :集 合、线性结构、树形结构、图状结构 四种关系是数据元素之间的逻辑关系，又称为逻辑结构 数据结构和算法简介数据结构和算法简介数据结构数据结构(C#描述描述) 认识数据结构认识数据结构数据结构的存储数据结构的存储 数据元素在计算机中的表示称为数据的存储结构。它包括数据 元素的表示和关系的表示。 在计算机中数据元素是用一个

5、由若干位组合起来形成的一个位 串来表示 数据元素之间关系在计算机中有两种不同的表示方法：顺序存 储和链式存储，并由此得到两种不同的存储结构：顺序存储结 构和链式存储结构。 顺序存储结构借助元素在存储器中的相对位置来表示数据元素 之间逻辑关系，数据元素存放在一片连续的存储空间里，通常 用数组来实现 链式存储结构则借助于引用或指针来表示数据元素之间的逻辑 关系，被存放的元素被随机的存放在内存中再用指针将它们链 接在一起。 数据结构和算法简介数据结构和算法简介数据结构数据结构(C#描述描述) 认识算法认识算法算法的定义及特征算法的定义及特征 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，

6、其中每一条指令表示一个或多个操作。 算法具用5个重要的特征： 有限性：算法必须在有限的步骤之后结束 确定性：算法的每一步都是确定的定义，无二义性。即在任何条件下，算法只 有唯一的一条执行路径，即对于相同的输入只能得出相同的输出 输入：一个算法可接受零个或多个输入 输出：一个算法有至少一个或多个输出 有效性：算法由可实现的基本指令组成。 数据结构和算法简介数据结构和算法简介数据结构数据结构(C#描述描述) 认识算法认识算法算法的性能分析与度量算法的性能分析与度量 一个算法的评价可以从算法执行的时间与算法的所占用的内存 空间两个方面来进行 算法的执行时间需通过依据该算法编制的程序在计算机上运行 时

7、所消耗的时间来度量。而这种机器的消耗时间与下列因素有 关： (1) 书写算法的程序设计语言； (2) 编译产生的机器语言代码的质量； (3) 机器执行指令的速度； (4) 问题的规模。 算法的效率只与问题的规模有关，或者说，算法的效率是问题 规模的函数 一个算法的时间复杂度反映了程序运行从开始到结束所需要的 时间。通常使用大O符号表示：T（n）=O(f(n) 数据结构和算法简介数据结构和算法简介数据结构数据结构(C#描述描述) 寻求问题求解的实现方法寻求问题求解的实现方法 抽象数据类型：一个抽象数据类型（ADT, abstract data type） 是一个数据结构和可能在这个数据结构上进行

8、的操作定义的。 开发者们通过抽象数据类型的操作方法来访问抽象数据类型中 的数据结构，而不管这个数据结构内部各种操作是如何实现的。 为了用C#实现抽象数据类型，本书遵循下面的解题步骤： (1) 用数据类型（包括值类型和引用类型）表示数据结构中的数据元素（后 面也称结点）； (2) 用顺序存储结构或链式存储结构表示数据元素之间的关系； (3) 用接口定义在数据结构上的基本操作； (4) 将数据结构的表示代码及对接口所定义操作的实现代码封装在类中，用 类表示某种数据结构所对应的抽象数据类型； （5）通过使用实现抽象数据类型的C#类解决实际应用的问题。 数据结构和算法简介数据结构和算法简介数据结构数据结构(C#描述描述) 小结小结 数据是对客观事物的符号表示，数据元素是数据的基本单位，是计算机 进行输入输出操作的最小单位； 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。可用 公式表示为：数据结构=数据元素+关系（结构）； 通常有4类基本数据结构： 集合、线性结构、树形结构、图形结构 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每 一条指令表示一个或多个操作，算法具用5个重要的