数据结构讲义第1章绪论ppt课件

《数据结构讲义第1章绪论ppt课件》由会员分享，可在线阅读，更多相关《数据结构讲义第1章绪论ppt课件（47页珍藏版）》请在金锄头文库上搜索。

1、数据结构 DATA STRUCTURE, 教材,2 数据结构（ C语言篇）习题与解析李春葆 清华大学出版社, 参考教材 1 数据结构题集 （ C语言版）严蔚敏 吴伟民 清华大学出版社,数据结构（ C语言版）严蔚敏 吴伟民 清华大学出版社 2002,课程学时课程总学时数：72（讲课：56，实验：16）课程设计（1周）,目录,第一章 绪论,第二章 线性表,第三章 栈与队列,第五章 数组和广义表,第七章 图,第八章 查找,第九章 排序,第六章 树与二叉树,C语言相关知识回顾,数据处理 输入、输出、加工、存储 模块化 函数声明与调用 参数传递 其它 typedef使用 指针操作：malloc，free

2、,第一章 绪论,1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示和实现 1.4 算法和算法分析,1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求,非数值问题,1.1 什么是数据结构,例1 学生信息检索系统,1.1 什么是数据结构,1968年美国唐欧克努特（Donald E. Knuth ）教授开创了数据结构的最初体系：它所著的计算机程序设计技巧（The Art of Computer Programming）第一卷基本算法是第一本系统阐述数据的逻辑结构和存储结构及其操作的著作。,数据结构课程主要是研究非数值计算

3、的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。,1.2 基本概念和术语,数据(Data):是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数值数据、非数值数据（文字、图像、声音等） 数据元素(Data Element)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。,1.2 基本概念和术语,数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。 在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属

4、于同一数据对象。数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。数据的逻辑结构,1.2 基本概念和术语,数据结构的分类： 一、线性结构：结构中的数据元素之间存在一对一的关系。 二、树型结构：结构中的数据元素之间存在一对多的关系。 三、图状结构或网状结构：结构中的数据元素之间存在多对多的关系。,三类基本结构的示意图,1.2 基本概念和术语,例：,某班学生基本情况登记表，,学号 姓名 专业 政治面藐 001 王洪 计算机 党员 002 孙文 计算机 团员 003 谢军 计算机 团员 004 李辉 计算机 团员 005 沈祥福 计算机 党员006 余斌 计

5、算机 团员 007 巩力 计算机 团员 008 孔令辉 计算机 团员,学生间学号顺序关系 是一种线性结构关系,1.2 基本概念和术语,例：,家族的族谱 假设某家族有10个成员A， B， C， D， E， F， G， H，I， J，他们之间的血缘关系可以用如下图表示。,1.2 基本概念和术语,对每种数据结构，主要讨论如下两方面的问题：1） 数据的逻辑结构，数据结构的基本操作； 2） 数据的存储结构，数据结构基本操作的实现。,1.2 基本概念和术语,一、数据（逻辑）结构的表示 图示表示,学生基本情况表的图示表示,家族树的图示表示,1.2 基本概念和术语,一、数据（逻辑）结构的表示 二元组表示 Da

6、ta_Structrue=（D，S）其中: D 是数据元素集合，S 是 D 上关系的集合。,D = 001，002，003，004，005，006，007，008 S = R R= , ,1.2 基本概念和术语,一、数据（逻辑）结构的表示数据的逻辑结构 可以看作是从具体问题抽象出来的数学模型，它与数据的存储无关,1.2 基本概念和术语,二、数据的存储结构1 定义数据结构在计算机中的表示或实现称为数据的物理结构，又称为存储结构。包括数据元素的表示及元素间关系的表示。,1.2 基本概念和术语,二、数据的存储结构2 表示 i)数据元素的表示在计算机中，可用二进制位串表示一个数据元素，称这个位串为元素

7、（Element）或 结点（Node）。 ii)元素间关系的表示,1.2 基本概念和术语,二、数据的存储结构3 分类根据数据元素之间的关系在计算机中的不同表示方法，数据的存储结构分为： 顺序存储结构 链式存储结构,1.2 基本概念和术语,二、数据的存储结构3 分类 顺序存储结构 用元素在存储器中的相对位置表示数据元素之间的逻辑关系,200 201 202 203,M,1.2 基本概念和术语,二、数据的存储结构3 分类链式存储方法用指针表示数据元素之间的逻辑关系,k1,k2,k3,200,300,400,M,null,1.2 基本概念和术语,二、数据的存储结构3 分类其它存储方式： 1）索引存储

8、,张三 数据结构,李四 离散数学,张三 200,李四 300,100,101,200,300,结点表,索引表,.,1.2 基本概念和术语,二、数据的存储结构3 分类其它存储方式： 2）散列存储,f(key)=key % 12 +200,012,001,004,007,207,200,201,204,056,208,1.2 基本概念和术语,二、数据的存储结构4 描述本书采用在高级语言中的数据类型（Data type）来描述存储结构。 如： 对数据元素，可用基本类型（整型、字符型等）或结构类型来描述 对关系：可用一维数组描述顺序存储结构用“指针”描述链式存储结构,1.2 基本概念和术语,数据类型（

9、Data Type） 是一个值的集合和定义在该值集上的一组操作的总称。 抽象数据类型（Abstruct Data Type，简称ADT） 是指一个数学模型以及定义在该模型上的一组操作。 （D，S，P） 其中，D表示数据对象，S表示关系集，P表示基本操作集。 本书实际用ADT来描述数据的逻辑结构及运算。,1.2 基本概念和术语,三、数据的运算数据的运算是在数据的逻辑结构上定义的操作算法。如检索、插入、删除等。 数据的运算是在逻辑结构上定义，在具体的存储结构上实现。,小结,数据的逻辑结构、存储结构、运算间关系 运算在逻辑结构上定义，在存储结构上实现 存储结构是逻辑结构在计算机内部的映象,数据结构课

10、程的内容：,1.3 抽象数据类型的表示与实现,抽象数据类型的定义 抽象数据类型定义格式： ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名。 其中，数据对象和数据关系的定义用伪码描述。 数据基本操作的定义格式：基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述,例： ADT Triplet 数据对象：D=e1，e2,e3 |e1,e2,e3Elemset(定义了关系运算的某个集合) 数据关系：R1=e1,e2, 基本操作：InitTriplet(&T,v1,v2,v3)DestroyTriplet（&T）

11、Get（T,i,&e）Put(&T,i,e)ADT Triplet,1.3 抽象数据类型的表示与实现,数据元素的表示 数据类型 typedef 定义新类型 算法的描述 类C语言 函数,1.3 抽象数据类型的表示与实现,1.3 抽象数据类型的表示与实现,几点说明： 1 typedef 2 数据元素的定义 例：,1.3 抽象数据类型的表示与实现,几点说明： 3 算法的书写 采用类C语言、函数描述算法的输入、输出新的参数传递方式：引用参数传递,1.3 抽象数据类型的表示与实现,例：已知学生信息表，写出它的顺序存储表示以及根据学号查找学生所在专业的算法声明。,1.4 算法和算法分析,1.4.1算法 算

12、法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列。 算法的五个特性： （1）有穷性 （2）确定性 （3）可行性 （4）输入 （5）输出,1.4.2 算法设计的要求 要设计一个好的算法通常要考虑以下的要求。 正确性(Correctness )算法应满足具体问题的需求。 可读性(Readability)算法应该好读。以有利于阅读者对程序的理解。 健壮性(Robustness)算法应具有容错处理。 效率与低存储量要求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。,1.4.3 算法效率的度量 算法执行时间分析方法的分

13、类： 事后统计 事前分析 度量方法 采用时间复杂度来估计算法的算法的执行时间T(n)=O(f(n)即：如果存在两个正常数c和n0，对于所有的nn0，有T(n) cf(n) 它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作渐近时间复杂度（Asymptotic Time Complexity），简称时间复杂度。,时间复杂度的求法： 基本操作（原操作） 语句的频度：语句执行的次数 定理：若A(n)=amn m +am-1nm-1+a1n+a0是一个m次多项式，则A(n)=O(nm) 方法：确定基本操作，求各语句的频度之和，根据定理求出最后结果。,1.4.3 时间复杂度的求法

14、,示例:,(a)+x;s=0;,基本操作,语句频度,基本操作,1,1,2,语句频度之和：,根据定理：若A(n)=amn m +am-1nm-1+a1n+a0是一个m次多项式，则A(n)=O(nm)（ O(nm) 表示A(n)与nm成正比, 即O(nm) 与nm 同一数量级；） 得：T(n) = 2 = O(1)时间复杂度为O(1),1.4.3 时间复杂度的求法,示例:(b) for (i=1;i=n;+i) +x;s+=x;(c) for (j=1;j=n;+j)for (k=1;k=n;k+)+x;s+=x;,(d) for (j=2;j=n;+j)for (k=2;k=j-1;k+)+x;

15、 s+=x;(e) i=1while(i=n)i=i*2,1.4.3 时间复杂度的求法,常用的时间复杂度关系：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3) O(2n)O(n!)O(nn)若算法中基本操作重复执行的次数随问题输入数据集不同而不同，这时可计算最坏情况下的时间复杂度或平均时间复杂度。,1.4.3 时间复杂度,1.4.3 时间复杂度,1.4.3 时间复杂度,1.4.4算法的存储空间需求空间复杂度:算法所需存储空间的度量，记作:S(n)=O(f(n) 其中n为问题的规模(或大小) 一般只考查算法所需的辅助空间的大小作为算法所需空间的度量。,14 空间复杂度,例,计算 解法1 先计算x 的幂, 存于power 中,再分别乘以相应的系数# define N 100float evaluate (float coef , float x , int n ) float powerN, f; int i;for (power 0=1, i = 1; i=n; i+ ) poweri=x*poweri-1; for (f = 0, i=0; i=N; i +) f=f+coefi*poweri; return(f);,