《第一章数据结构绪论.ppt》由会员分享,可在线阅读,更多相关《第一章数据结构绪论.ppt(27页珍藏版)》请在三一文库上搜索。
1、数 据 结 构,主讲教师:邓奉先,1.1数据结构简介 数据结构这门学科形成的背景,第一章 绪 论,第一章 绪 论,什么是数据结构? 数据结构是主要研究非数值应用问题中数据之间的逻辑关系和对数据的操作,同时还研究如何将具有逻辑关系的数据按一定的存储方式存放在计算机内。,第一章 绪 论,学生基本信息的管理,第一章 绪 论,线性关系: 列车中各车箱之间的关系就是线性的。 排队买车票人之间的关系是线性的。 叠盘子中各盘子之间的关系是线性的。,第一章 绪 论,层次关系: 在军队的编制中,军下面是师,师下面是团,军、师、团之间是层次关系。 人的辈分关系中,祖辈下是父辈,父辈下是子辈,这些是层次关系。 学校
2、的编制中,学校分成若干个学院、学院下又分成若干个系、系下又分成若干个教研室,这些也都是层次关系。,第一章 绪 论,网状关系: 在城市铁路交通图中,各城市之间的关系是网状关系。 电话网中,各电话之间是网状关系。 计算机网络中,各计算机之间是网状关系。,第一章 绪 论,通过以上几例可以直接地认为:数据结构 就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的操作,而且确保经过这些操作后所得到的新结构仍然是原来的结构类型。,第一章 绪 论,1.2 基本概念和术语 数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。它
3、是计算机程序加工的“原料”。,第一章 绪 论,数据元素(Data Element):是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据由若干个数据元素组成,一个数据元素可由一个或若干个数据项组成。数据项是数据的不可分割的最小单位。,第一章 绪 论,数据对象(Data Object):是性质相同的数据元素的集合。是数据的一个子集。某种数据类型元素的集合。 例 整数的数据对象是-3,-2,-1,0,1,2,3, 英文字符类型的数据对象是A,B,C,D,E,F,,第一章 绪 论,数据结构:是相互之间存在一种或多种关系的数据元素的集合。 数据结构的形式定义: Data_Struct
4、ure=(D,S) D是数据元素的有限集 S是D上关系的有限集,S是指数据元素之间的逻辑关系,即数据的逻辑结构,第一章 绪 论,数据元素之间的相互关系称为逻辑结构。通常分为四类基本结构: 一、集合 结构中的数据元素除了同属于一种类型外,别无其它关系。 二、线性结构 结构中的数据元素之间存在一对一的关系。 三、树形结构 结构中的数据元素之间存在一对多的关系。 四、图状结构或网状结构 结构中的数据元素之间存在多对多的任意关系。,图1.1 四种基本数据结构,第一章 绪 论,数据在计算机中的存放方式(映像)称为数据的物理结构,又称为存储结构。 数据元素在计算机中的两种存储方式: 顺序存储结构和链式存储
5、结构,第一章 绪 论,顺序存储结构的特点:在内存中开辟一组地址连续的空间来存放数据,数据元素之间的逻辑关系通过元素在内存中存放的相对位置来确定。 链式存储结构的特点:在内存中的地址可以连续,也可以不连续。在每一个数据元素中增加一个存放地址的指针,通过该指针来表示数据元素之间的逻辑关系。,第一章 绪 论,数据类型:是一个值的集合和定义在这个值集上的一组操作的总称。在一种程序设计语言中,变量所具有的数据种类。 例 在C语言中 数据类型:基本类型和构造类型 基本类型:整型、浮点型、字符型 构造类型:数组、结构、联合、指针、枚举型,第一章 绪 论,在计算机中,数据类型并非局限于高级语言中的一个具体类型
6、,而是通常用抽象数据类型表示类型。上机实现时,再把抽象数据类型用具体的类型代替。 抽象数据类型ADT:是指基于一类逻辑关系的数据类型以及定义在这个类型上的一组操作。 抽象数据类型与数据类型实质上是一个概念。,第一章 绪 论,抽象数据类型用三元组表示: (D,S,P) D是数据对象 ,S是D上的关系集,P是对D的基本操作集。 ADT定义格式: ADT ADT名 数据对象: 结构关系: 基本操作: ADT ADT名,第一章 绪 论,1.4算法及算法分析 什么是算法? 算法的五个特性: (1)有穷性 一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。 (2)确定性 算法中每一条指令必
7、须有确切的含义。不存在二义性。相同的输入有相同的输出。 (3)可行性 (正确性) 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本操作执行有限次来实现的。 (4)输入 一个算法有零个或多个输入,这些输入取自于某个特定的对象集合。 (5)输出 一个算法有一个或多个输出,这些输出是同输入有着某些特定关系的量。,第一章 绪 论,算法设计的要求 评价一个好的算法有以下几个标准: (1) 正确性(Correctness ) 算法应满足具体问题的需求。 (2) 可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解。 (3) 健壮性(Robustness) 算法应具有容错处
8、理。当输入非法数据时,算法应对其作出反应,而不是产年莫名其妙的输出结果。 (4) 高效率与存储量需求 效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大存储空间。一般,这两者与问题的规模有关。,第一章 绪 论,数据结构上的基本操作 两种基本操作: 加工型操作:插入 删除 更新 引用型操作:查找 读取 算法的描述方法 框图算法描述 自然语言描述 类C语言算法描述,第一章 绪 论,算法分析 算法运行的时间分析和程序运行的时间分析是有区别的。 算法时间效率的度量分析 对解决问题的算法作时间上的度量分析,用T(n)算法运行所需的时间, T(n)是跟问题规模n和基本操作的次数有关,是问题规
9、模n的函数。,第一章 绪 论,int largest(int *array,int a) int currlarge,i ; currlarge=array0; for(i=1;icurrlarge) currlarge=arrayi; return currlarge; 算法运行所需时间:T(n)=cn,第一章 绪 论,for(i=1;i=n;i+) for(j=1;j=n;j+) sum+; 算法运行所需时间:T(n)=cn2 a=b; 算法运行所需时间:T(n)=c 算法的时间复杂度分析只考虑问题规模n的增长率,因而在难以精确计算基本操作执行次数的情况下,只要求出它关于n的增长率即可。我们可以在计算任何算法运行时间代价时,忽略所有的常数和低次项,用大O表示法来表示算法的时间复杂度。,第一章 绪 论,从好到坏表示时间复杂度依次是:常量阶O(1);对数阶O(log n);线性阶O(n);平方阶O(n2);多项式阶O(nk);指数阶O(2n)等。 算法的空间复杂度,第一章 绪 论,小结 数据 数据元素 数据类型 数据结构 数据逻辑结构 数据物理结构 数据逻辑结构的四种基本类型 算法 算法的五个重要特性,
链接地址:https://www.31doc.com/p-2255406.html