数据结构的基本概念ppt课件

1、第1章 绪论吴文国主要内容1.1 数据构造的根本概念1.2 数据构造的内容1.3 算法设计1.4 算法描画工具1.5 算法的性能评价1.6 数据构造与C言语表示1.1 数据构造的根本概念本节引见以下几个根本概念和术语1. 数据2. 数据元素和数据项3. 数据构造4. 数据类型5. 笼统数据类型1. 数据 数据是信息的载体，它是可以被计算机识别、存储和加工处置。信息计算机数据数据的主要特征 计算机可以识别、可以处置、可以存储的信息。 计算机化的信息。 数据的含义随着计算机的开展而变化。数据处置的实例 例1：要判别某一点能否在三角形之内 例2：判别下面这个人能否是某个电影明星 例3： 判别二条直线

2、能否相交 如何要计算机处置这些问题？如何把这些问题表示成计算机能处置的数据呢？数据例子 表示物体的位置，我们用两个整数表示。 表示物体飞行途径假设是直线的那么用两个点来描画。 假设描画物体运动过程，那么要坐标，时间来描画。 如何表示声音？结论 数据是表示客观事物的数值、文字可以被计算机识别的各种符号集合。阐明 数据随计算机的开展而变化。 最早的计算机：只能处置二进制的数据，需求打孔(punch)。后来可以是十进 制数据，再后来可以是英文字符，声音，图像。2. 数据元素 数据元素Data Element 数据元素是数据根本单位，在处置过程普通表示其整体性和完好性。数据元素又称为元素，顶点或结点。

3、又称记录(Record)。数据项 数据项：是具有独立含义的最小标识。又称为数据域。数据项与数据元素的关系 数据元素是由数据项组成的。举例 数据元素：一行就是一个数据元素，张三，男，78等是一个数据项。学号姓名性别语文数学物理总分名次201张三男788954202李四女987867203王五男899571数据对象 数据对象是性质一样的数据元素的集合，是数据的一个子集。如整数数据对象。 某个班级的45位同窗的数据姓名，性别，地址，联络，家长姓名，照片。3. 数据构造(Data Structure) 数据构造是指数据相互之间存在一种或多种特定关系的数据元素集合。4. 数据类型 所谓数据类型是一个值的

4、集合以及定义在这些值上的操作的总称。普通高级言语有根本的数据类型，也有根据用户需求创建的类型，即构造体。 数据构造课程 里经常用到构造体。数据类型 原子类型：不可分割，如整型int ,char,float ,double) 构造类型：其可以分割的，如数组，构造体等(struct ,union)。 通常数据类型可以看成是程序设计言语中已实现的数据构造。5. 笼统数据类型ADTADT包括定义和实现两个方面。定义独立于实现。定义仅给出一个ADT的逻辑特性，不用思索如何在计算机中实现。只从问题本身笼统出来。ADT定义的格式ADT 数据对象: 构造关系: 根本操作: ADT ADT阐明 数据对象定义是用

5、已定义的数据类型定义新的数据对象。 数据对象和构造关系采用数学符号和自然言语描画。 根本操作定义包括操作名，参数表、初始条件和操作结果四部分内容的定义和描画。其格式是 操作名参数表 操作前提：操作前提描画 操作结果：操作结果描画例1-2 给出简化线性表的ADT类型定义 ADT Linear_List 数据对象：一切属于同一类型的数据对象，i=1,2n,n=0 构造关系：一切数据元素ai，存在次序关系。a1无前趋，an无后继 根本操作： InitList(L):初始化空表续 ListLength(L):求线性表的长度 GetData(L,i)：取线性表的第i个元素 InsList(L,i,b):

6、 在L线性表中i位置插入元素b. DelList(L,i):删除L的第i个元素。 经过以上描画可以知道，由于它是ADT笼统，不限于某个特定类开，也不限于某特定的存储类型。用C言语实现ADT 在用C言语实现ADT时，要思索数据的存储类型。 譬如前面的例子里， a可以是一个整数，或一个浮点数，或一个学生信息的数据元素。 数据存储可以是数组，也可以是链表等，只需能反映它的逻辑构造关系就行。1.2数据构造的内容数据构造这个术语包含三方面的内容:1. 逻辑构造2. 存储构造3. 算法设计1. 逻辑构造 数据元素之间的逻辑关系，也称数据的逻辑构造Logical Structure； 数据的逻辑构造是从逻辑

7、关系上描画数据，与数据的存储无关，是独立于计算机的。数据的逻辑构造可以看作是从详细问题笼统出来的数学模型。四种逻辑构造 集合构造 线性构造 树形构造 图状构造 线性构造：线性表、栈，队、串，数组，广义表 非线性构造：树和图2. 存储构造 数据元素及其关系在计算机存储器内的表示，称为数据的存储构造Storage Structure； 数据的存储构造是逻辑构造用计算机言语的实现亦称为映象，它依赖于计算机言语。普通只在高级言语的层次上讨论存储构造。3. 数据的运算 数据的运算，即对数据施加的操作。数据的运算，即对数据施加的操作。数据的运算定义在数据的逻辑构造上，每种数据的运算定义在数据的逻辑构造上，

8、每种逻辑构造都有一个运算的集合。最常用的检逻辑构造都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实践上索、插入、删除、更新、排序等运算实践上只是在笼统的数据上所施加的一系列笼统的只是在笼统的数据上所施加的一系列笼统的操作。操作。实例1逻辑构造 有假设干个人组成一个小团体，它们之间有的是认识，有的不认识。所以它们的关系可以用下面的图来表示。连线表示二人之间是认识的。这个构造图反映对象之间的逻辑关系。FADBCE实例1存储构造 为了表示上述图里的各人之间的相互关系，我们用一个二维数来表示它们ABCDEFABCDEF实例1运算或操作 如今添加一个人G,G与A，C，D都认识， 如今删除

9、一个人如F。实例2某个班级成果计算机处置 一个班级有假设干个同窗，它们组成如下的表格。逻辑关系是指每个结点的前后关系。学号姓名性别语文数学物理总分名次201张三男788954202李四女987867203王五男899571实例2存储构造 存储构造是指如何在计算机里存储上述班级的人员。普通采用数组或链表等。a1a2a3a4a5a6a7a8a1a1a1a1实例2运算或操作 同窗的添加，删除，挪动，查找，修正等操作。结论用数据构造处理实践问题是，普通按下面顺序思索三个问题：1.首先对问题的逻辑构造分析清楚2.接着思索存储问题，普通采用构造体方式以数组或链表进展存储(这步相当于定义构造体3.确定好数据

10、存储构造后，就思索运算操作的实现这步相当于编写函数三者之间的构造关系 本书采用这种讨论方法逻辑关系存储构造操作运算算法程序员特点 逻辑关系不依赖于存储构造和运算操作 存储构造与逻辑关系有关与操作运算无关。 操作运算与逻辑关系和存储构造都有关系。1.3 算法设计 算法定义 算法的特性算法的定义 数据的操作步骤 是用算法来描画的。所以算法是数据构造中最重要的内容。 什么是算法？ 本质上说，可以清楚描画操作步骤的都可以称算法。 一个算法是将一系列输入转换为输出的计算步骤。 所以算法的方式并不独一，可以自然言语描画，也可以用类Pascal言语，本书采用类C言语算法的五个特性有穷性算法必须是经过有限的步

11、骤操作完成。确定性算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。有任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。可行性可行性一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。输入输入要有多个或零个输入输出输出至少有一个或多个输出（注意！千万不要把这里输出与C语言的printf联系起来）算法的正确性 假设一个算法对于每个输入实例均能终止并给出正确的结果，那么称该算法是正确的。正确的算法处理了给定的计算问题。 一个不正确的算法是指对某些输入实例不终止，或者虽然终止但给出的结果不是所盼望得到的答案，普通只思索正确的算法。

12、 不能终止，实践上就是死循环或死机。算法的评价算法的评价 选用的算法首先应该是“正确的。此外，主要思索如下三点：a. 执行算法所耗费的时间； b. 时间复杂度c.执行算法所耗费的存储空间，其中主要思索辅助存储空间；空间复杂度d. 可读性强壮性(鲁棒,Robust)时间复杂度 一个算法所耗费的时间是算法中每条语句的执行时间之和。而每条语句执行的时间是该语句的频度乘上该语句执行一次所需的时间。一条语句的执行时间与机器的指令性能，速度和编译器质量有关。但是为了简单化我们假设每条语句执行一次的时间为一个单位，那么算法的执行是该算法一切语句的频度之和。 所以在讨论算法的时间复杂度时，我们就简单计算语句的

13、频度。矩阵的相乘 二个矩阵的相乘nnnnnnnnnnnnnnnnnncccccccccbbbbbbbbbaaaaaaaaa212222111211212222111211212222111211nkkjikijbac1例1.求两个n阶方阵的乘积 C=AB # define n 100 / n 可根据需求定义,这里假定为100void MatrixMultiply(int Ann，int B nn，int Cnn) /右边列为各语句的频度int i ,j ,k; for(i=0; in;i+) /n for (j=0;jn;j+) /n2 Cij=0; /n2 for (k=0; kn; k+)

14、 /n3 Cij=Cij+Aik*Bkj; /n3 例1的时间复杂度 T(n)=2n3+3n2+2n+1 当n趋向无限大时那么上述式子与n3同阶的的，所以时间复杂度用下面来表示 T(n)=O(n3) 表示其时间复杂度是与输入规模n的三次方成正比。 我们称O(n3)为渐近时间复杂度。简称为时间复杂度。例2级下面算法，计算其时间复杂度 x=0; y=0; for(k=1;k=n;k+) x+; for(i=1;i=n;i+) for(j=1;j=n;j+) y+;例2 计算下面算法的时间复杂度x=1;for(i=1;i=n;i+) for(j=1;j=i;j+) fork=1;k=0&(Ai!=k

15、) i-; return i; 算法的时间复杂度要根据统计结果 例如，把某个数按顺序插入到一个有充列表中。35121821324556最坏 、最好和平均情况 假设运气好，第一次比较就相等，那么只需一次，运气不好比较n次，也找不到该值， 所以有时在讨论算法的时间复杂度时就采用最好情况，最坏情况和平均情况。空间复杂度 一个算法的空间复杂度(Space Complexity) S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也经常简称为空间复杂度。算法的时间复杂度和空间复杂度合称为算法的复杂度。 讨论前面的例子算法的空间复杂度 算法描画风格 一个算法用C言语的一个函数来表示。一个良好风格是指： 模块化算法表示方式函数前往值 函数名方式参数 内部数据类