数据结构第1章(耿国华)

《数据结构第1章(耿国华)》由会员分享，可在线阅读，更多相关《数据结构第1章(耿国华)（61页珍藏版）》请在金锄头文库上搜索。

1、*1第1章 绪 论1.7 关于学习数据结构 l1.1 数据结构的基本概念(定义)l1.2 数据结构的内容（研究范围）l1.3 算法设计l1.4 算法描述工具 l1.5 对算法作性能评价l1.6 数据结构与C语言表示Date21.1 数据结构的基本概念（定义）数据结构的相关名词：l数据（Data）l数据元素（Data Element） l数据对象（Data Object） l数据结构（Data Structure） l数据类型(Data Type) l数据抽象与抽象数据类型Date3数据（Data）l定义：数据是描述客观观事物的数值值、字符以及能输输入机器且 能被处处理的各种符号集合。数据包含整

2、型、实型、布尔型、图象、字符、声音等一切可 以输入到计算机中的符号集合。C编译程序 源程序（.c）目标程序（.obj）可执行程序（.exe）C链接程序例如对C源程序Date4数据元素（Data Element）l定义：数据元素是组成数据的基本单位 ，是数据 集合的个体，在计算机中通常作为一个整体进行考虑和处 理。例如：. . . . . . 北京1983.11河北女 赵虹玲101 住 址 出生年月 籍 贯性 别 姓 名 学 号 数据元素数据项Date5数据对象（Data Object） l定义：数据对象是性质相同的数据元素的集合，是 数据的一个子集。整数集合：N=0，1，2， 无限集 字符集合

3、：C=A，B，Z 有限集例如：Date6数据结构（Data Structure） l定义：数据结构是指相互之间存在一种或多种特定 关系的数据元素集合，是带有结构的数据元素的集合，它 指的是数据元素之间的相互关系，即数据的组织形式。 例 如表结构：. . . . . . 北京1983.11河北女 赵虹玲101 住 址 出生年月 籍 贯性 别 姓 名 学 号 Date7数据结构（Data Structure）树型结构图结构12543Date8数据类型(Data Type) l定义：数据类型是一组性质相同的值集合以及定 义在这个值集合上的一组操作的总称。如在高级语言中，整型类型的取值范围为：-327

4、68+32767，运算符集合为加、减、乘、除、 取模，即+、-、*、/、%。Date9数据类型(Data Type)l高级语言中的数据类型分为两大类： 1.原子类型，其值不可分解。如C语言中的标准类 型（整型、实型、字符型、）。2.结构类型，其值是由若干成分按某种结构组成的 ，因此是可以分解的，并且它的成分可以是非结构 的，也可以是结构的。指针类型属于哪种类型？Date10数据抽象与抽象数据类型 l数据的抽象l抽象数据类型(Abstract Data Type) l抽象数据类型实现 lADT的表示与实现l面向对象的概念l结构化的开发方法与面向对象开发方法不同点 Date111.2 数据结构的内

5、容 l逻辑结构 l存储结构 l运算集合 Date12逻辑结构l定义：数据的逻辑结构是指数据元素之间逻辑关系描述。l形式化描述： Data_Structure=（D,R）其中D是数据元素的 有限集，R是D上关系的有限集。l四类基本的结构集合结构、线性结构、树型结构、图状结构 。 Date13集合结构l定义：结构中的数据元素之间除了同属于 一个集合的关系外，无任何其它关系。 集合例如：Date14线性结构l定义：结构中的数据元素之间存在着一对 一的线性关系。 例如：线性表Date15树型结构l定义：结构中的数据元素之间存在着一对 多的层次关系。 例如：树Date16图状结构或网状结构 l定义：结构

6、中的数据元素之间存在着多对 多的任意关系。例如：图Date17综上所述，数据的逻辑结构可概括为：线性结构线性表、栈、队、字符串 、 数组、广义表 逻辑结构非线性结构树、图逻辑结构Date18存储结构 l定义：存储结构（又称物理结构）是逻辑结构在计 算机中存储映象，是逻辑结构在计算机中的实现，它包括 数据元素的表示和关系的表示。 l形式化描述：D要存入机器中，建立一从D的数据元素到存储 空间M单元映象S ，DM，即对于每一个d， dD, 都有唯一的zM使S（D）=Z, 同时这个映象必须明 显或隐含地体现关系R。Date19逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身映象，是数

7、据结构的实现；逻辑结构是数据结构的抽象。 数据元素之间关系在计算机中的表示方法：顺序映象 （顺序存储结构） 非顺序映象（非顺序存储结构）存储结构 Date20运算集合例如工资表：编编 号姓 名性别别基本工资资工龄龄工资资应应扣工资资实发实发 工资资100001张爱张爱 芬女3456714545300045112100002李 林 男 4459018560450058650100003刘晓晓峰 男 3450013000250045000100004赵赵 俊 女 5609022590650072180100005孙孙 涛 男 4506019080500059180 100121张兴张兴 强 男 1

8、0259836553100001291.51Date21数据结构的内容 综上所述，数据结构的内容可归纳为三个部分，逻辑结构、存储结构和运算集合：按某种逻辑关系组织起来的一批数据，按一定的映 象方式把它存放在计算机存贮器中，并在这些数据 上定义了一个运算的集合，就叫做数据结构。Date221.3 算法 l算法（Algorithm）定义 l算法的特性 l算法设计的要求 Date23算法（Algorithm）定义l定义：Algorithm is a finite set of rules which gives a sequence of operation for solving a specif

9、ic type of problem.算法是规则的有限集合，是为解决 特定问题而规定的一系列操作。 Date24算法的特性1. 有限性：有限步骤之内正常结束，不能形成无穷循环2. 确定性：算法中的每一个步骤必须有确定含义，无二义性得以实现。 3. 输 入： 有多个或0个输入 4. 输 出： 至少有一个或多个输出。5. 可行性：原则上能精确进行，操作可通过已实现基本运算执行有限次而完成。 Date25算法设计的要求 l算法的正确性 算法特征：l 可读性 l 健壮性 l 高效率和低存储量例如要求n个数的最大值问题给出算法如下：max:=0;for（i=1 ；imax) max=x;Date261.

10、4 算法描述的工具 l概述： 算法+数据结构=程序 l算法、语言、程序的关系 l设计实现算法过程步骤l类描述算法的语言选择Date27算法、语言、程序的关系1. 算法：描述了数据对象的元素之间的关系（包 括数据逻辑关系、存贮关系描述）。2. 描述算法的工具：算法可用自然语言、框图或 高级程序设计语言进行描述。3.程序是算法在计算机中的实现。Date28设计实现算法过程步骤1. 找出与求解有关的数据元素之间的关系2. 确定在某一数据对象上所施加运算3. 考虑数据元素的存储表示4. 选择描述算法的语言5.设计实现求解的算法，并用程序语言加以描述 。Date29类描述算法的语言选择l类语言：类语言是

11、接近于高级语言而又不是严格的高级语言 ，具有高级语言的一般语句设施，撇掉语言中的细 节，以便把注意力主要集中在算法处理步骤本身的 描述上。Date303.赋值语句对C语言作以下描述：（1）简单赋值1）变量名=表达式 2） 变量+， 3） 变量- -，（2）串联赋值变量1=变量2=变量3=变量k=表达式 Date31对C语言作以下描述：（4）条件赋值变量名=条件表达式？表达式1:表达式2 （3）成组赋值(,)数组名1下标1下标2=数组名2下标1下标2 Date324.条件选择语句对C语言作以下描述：if () 语句;if () 语句1;else 语句2;Date33情况语句switch (）ca

12、se 判断值1:语句组 1；break;case 判断值2:语句组 2；break; case 判断值n:语句组n;break;default: 语句组；break; 对C语言作以下描述：Date34对C语言作以下描述：5.循环语句for 语句for (；）循环体语句；Date35while 语句while (）循环体语句；对C语言作以下描述：do while 语句do 循环体语句while ( ） Date361.5 对算法作性能评价 l评价算法的标准：评价一个算法主要看这个算法所占 用机器资源的多少，而这些资源中时间代价与空 间代价是两个主要的方面，通常是以算法执行所 需的机器时间和所占用

13、的存储空间来判断一个算 法的优劣。 l性能评价 l有关数量关系计算 Date37性能评价l定义：对问题规模与该算法在运行时所占的空间S与所耗费 的时间T给出一个数量关系的评价。问题规模N对不同的问题其含义不同：对矩阵是阶数；对多项式运算是多项式项数；对图是顶点个数；对集合运算是集合中元素个数。Date38有关数量关系计算 数量关系评价体现在时间算法在机器中所耗费时间 。 数量关系评价体现在空间算法在机器中所占存储量 。l关于算法执执行时间时间l语句频度 l算法的时间复杂度l数据结结构中常用的时间时间 复杂杂度频频率计计数 l最坏时间时间 复杂杂度 l算法的空间复杂度 Date39关于算法执执行

14、时间时间l定义：一个算法的执行时间大致上等于其所有语句执行 时间的总和，对于语句的执行时间是指该条语句的执行 次数和执行一次所需时间的乘积。l分析：不是针对实际执行时间的精确地算出算法执行 具体时间，而是针对算法中语句的执行次数做出估 计，从中得到算法执行时间的信息。Date40语句频度 l定义： 语句频度是指该语句在一个算法中重复执行的次 数。例如 ：两个 矩阵 相乘算法语句 对应的语句频度 1for（i=0；iaj+1) temp= aj;aj=aj+1;aj+1=temp;change=true;i=i+1 ;while(i，ai无前趋，an无后继； 操作 设L为Linear_list

15、Initial(L)初始化空线性表； Length(L)求线性表的表长； Get(L,i)取线性表的第i个元素； Insert(L,i,b)在线性表的第i个位置插入元素b； Delete(L,i)删删除线线性表的第i个元素； Date50ADT的表示与实现 lADT的定义：ADT 数据对象:结构关系:基本操作:ADT 基本操作的定义格式为 ：(参数表) 操作前提: 操作结果:Date51用标准C语言表示和实现ADT描述时，主要有两个方面：二、用C语言函数实现各操作。一、通过结构体将int、float等固有类型组合到一起,构成一 个结构类型,再用typedef为该类型或该类型指针重新起一个 名字。ADT的表示与实现 Date52#definemaxsize=线性表可能达到的最大长度； typedef struct ElemType elemmaxsize； /* 线性表占用的数组空间 */int last； /*记录线性表中最后一个元素在数组elem