数据结构_第1次课第一章基本概念(更改的).ppt

第一章 绪论;为什么要学习数据结构？;用计算机解决问题的过程;数据结构课程的形成和发展;介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 ;学习提要;教学重点;;1.1 什么是数据结构 众所周知，计算机的程序是对信息进行处理。在大多数情况下，这些信息并不是没有组织的，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。;1.1 什么是数据结构; 一元二次方程求解 ;例一：电话号码查询系统;;例三：铺设城市的煤气管道;概括地说，;1.2 基本概念和术语;一、数据与数据结构; 是数据（集合）中的一个“个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的基本单位。; 其中每个款项称为一个“数据项”;数据结构：;例如，当用三个 4 位的十进制数表示一个含 12 位数的十进制数时，;又例，在 2 行 3 列的二维数组中六个元素 {a1, a2, a3, a4, a5, a6} 之间存在两个关系:; 若在 6 个数据元素{a1, a2, a3, a4, a5, a6} 之间存在如下的次序关系:;从关系或结构分，数据结构可归结为以下四类:;数据结构包括“逻辑结构” 和“物理结构”两个方面(层次):;数据结构的形式定义描述为:;数据的存储结构 ;数据元素的映象方法：;关系的映象方法：;链式映象;在不同的编程环境中 存储结构可有不同的描述方法。;二、数据类型;整型数据类型：值的集合N＝｛…－2,－1,0,1,2…} 　　　　　　　一组操作：＋、－、x、/、%等 数据类型：基本类型和构造类型 基本类型：整型、浮点型、字符型 构造类型：数组、结构、联合、指针、枚举型、自定义; 数据类型 是一个值的集合和定义在此集合上的一组操作的总称。;数据类型的抽象性：各种高级程序设计语言中都拥有“整数”类型，尽管它们在不同处理器上实现的方法不同，但对程序员而言是“相同的”，因为它们的数学特性相同。;三、抽象数据类型 (Abstract Data Type 简称ADT);ADT（抽象数据类型的两个重要特征）;例如，定义抽象数据类型“复数”;基本操作：; GetImag( Z, ImagPart ) 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。;抽象数据类型的描述方法;ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名;赋值参数 指为操作提供输入值； 引用参数 以打头，除可提供输入值外， 还将返回操作结果。;抽象数据类型的表示和实现;1.4 算法和算法分析 算法：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。 算法具有以下五个特性： （1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 （2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。 （3）可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 （4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 （5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。;1.4.2 算法设计的要求 评价一个好的算法有以下几个标准: (1)正确性:算法应满足具体问题的需求。 (2)可读性:算法应该好读。以有利于阅读者对程序的理解。 (3)健状性:算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 (4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。执行时间少，存储空间小。;1.4.3 算法效率的度量 对一个算法要作出全面的分析可分成两种方法： 事先分析 求出该算法的一个时间界限函数 事后统计 收集此算法的执行时间和实际占用空间的统计资料。缺陷：一是必须先运行依据算法编制的程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。　;和算法执行时间相关的因素：; 一个特定算法的“运行工作量” 的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。;例１、for(i=1;i=n;++i) for(j=1;j=n;++j) { c[i][j]=0; for(k=1;k=n;++k)