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

数据结构和算法简介 数据结构(C#语言版) * 数据结构和算法简介 数据结构(C#描述) * * 数据结构和算法简介 数据结构(C#描述) * 目标 在本章中，你将达到如下目标： 了解问题求解的基本步骤 认识数据结构,熟悉其基本概念 熟悉算法的定义及特征 了解算法分析与度量的方法 初步了解本教材进行问题求解的基本思路 [问题描述] 某电信部门想开发一个查询知名电子企业服务电话号码的程序。要求对于任意给出的一个企业名称，若该企业已注册其服务电话号码，则迅速找到其电话号码；否则指出没有该企业的服务电话号码。 问题引入——查找电话号码问题 问题引入——查找电话号码问题 首先构造一张电话号码信息表。 接着将电话号码登记表存储到计算机中 。 然后确定解决问题的算法。 最后编程实现算法，写出C#的实现代码. 解决问题的步骤 问题引入——问题求解的基本步骤 根据实际问题，确定数据及数据之间的关系，即对数据的结构进行设计 分析对数据结构可能进行的操作，设计算法； 用一种存储结构在计算机内部表示数据及数据之间的关系； 根据存储结构的存储方式及设计的算法实现算法的计算机表示； 使用己实现的存储结构及算法解决实际问题。 认识数据结构——数据的概念 数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 认识数据结构——数据元素和数据项 数据元素是数据的基本单位，是计算机进行输入输出操作的最小单位。 数据元素可以由不可分割的数据项组成 。 认识数据结构——数据结构的概念 数据结构是相互之间存在一种或多种特定关系的数据元素的集合 。 数据结构=数据元素+关系（结构） 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构 根据数据元素之间关系的不同特性，通常有四类基本结构 :集合、线性结构、树形结构、图状结构 四种关系是数据元素之间的逻辑关系，又称为逻辑结构 认识数据结构——数据结构的存储 数据元素在计算机中的表示称为数据的存储结构。它包括数据元素的表示和关系的表示。 在计算机中数据元素是用一个由若干位组合起来形成的一个位串来表示 数据元素之间关系在计算机中有两种不同的表示方法：顺序存储和链式存储，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。 顺序存储结构借助元素在存储器中的相对位置来表示数据元素之间逻辑关系，数据元素存放在一片连续的存储空间里，通常用数组来实现 链式存储结构则借助于引用或指针来表示数据元素之间的逻辑关系，被存放的元素被随机的存放在内存中再用指针将它们链接在一起。 认识算法——算法的定义及特征 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 算法具用5个重要的特征： 有限性：算法必须在有限的步骤之后结束 确定性：算法的每一步都是确定的定义，无二义性。即在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出 输入：一个算法可接受零个或多个输入 输出：一个算法有至少一个或多个输出 有效性：算法由可实现的基本指令组成。 认识算法——算法的性能分析与度量 一个算法的评价可以从算法执行的时间与算法的所占用的内存空间两个方面来进行 算法的执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而这种机器的消耗时间与下列因素有关： (1) 书写算法的程序设计语言； (2) 编译产生的机器语言代码的质量； (3) 机器执行指令的速度； (4) 问题的规模。 算法的效率只与问题的规模有关，或者说，算法的效率是问题规模的函数 一个算法的时间复杂度反映了程序运行从开始到结束所需要的时间。通常使用大O符号表示：T（n）=O(f(n)) 寻求问题求解的实现方法 抽象数据类型：一个抽象数据类型（ADT, abstract data type）是一个数据结构和可能在这个数据结构上进行的操作定义的。开发者们通过抽象数据类型的操作方法来访问抽象数据类型中的数据结构，而不管这个数据结构内部各种操作是如何实现的。 为了用C#实现抽象数据类型，本书遵循下面的解题步骤： (1) 用数据类型（包括值类型和引用类型）表示数据结构中的数据元素（后面也称结点）； (2) 用顺序存储结构或链式存储结构表示数据元素之间的关系； (3) 用接口定义在数据结构上的基本操作； (4) 将数据结构的表示代码及对接口所定义操作的实现代码封装在类中，用类