数据结构一章绪论ppt课件

1、第一章第一章 绪论绪论11 根本术语根本术语12 数据构造的定义及研讨的内容数据构造的定义及研讨的内容121 数据的逻辑构造数据的逻辑构造122 数据的存储构造数据的存储构造123 数据的运算数据的运算13 算法算法131 算法的概念及特性算法的概念及特性132 算法的描画算法的描画133 算法的评价算法的评价14 学习数据构造的意义和目的学习数据构造的意义和目的 11 根本术语 数据Data是人们商定的符号，用它来表示客观事物及其活动，是信息的载体。数据是计算机程序加工处置的对象。 数据元素Data Element是数据的根本单位，在计算机程序中通常作为一个整体进展思索和处置，在不同的情况下

2、，又可以称为元素、结点、顶点或记录。数据是由数据元素构成的。 数据项Data Item是构成数据元素不可分割的具有独立含义的最小标识单位。假设数据元素可再分，那么数据元素是由假设干个数据项组成；如数据元素不可再分，数据元素和数据项是同一概念，如整型数据就是不可再分的。 数据类型Data Type是一个值的集合和定义在这个值集上一组操作的总称。按值的不同特性，高级程序设计言语中的数据类型可分为原子类型和构造类型两类。 第一章第一章 绪论绪论12 数据构造的定义及研讨的内容数据构造的定义及研讨的内容数据构造Data Structure：按照某种逻辑关系组织起来的一批数据，用一定的存储方式存储在计算

3、机的存储器中，并在这些数据上定义一个运算的集合，就称为一个数据构造Data Structure。数据构造重点研讨的内容：1数据的逻辑构造：即数据之间的逻辑关系。2数据的存储构造：即数据及数据之间的关系在计算机存储器中的表示。3数据的运算：即对数据施加的各种操作。 数据的逻辑构造 数据的逻辑构造Logical Structure：的是数据元素之间的逻辑关系。它是人们根据实践问题的需求和问题本身所含数据之间的内在联络而笼统出来的数学模型，与如何利用计算机存储和处置无关，所以被称为数据的逻辑构造。由于数据的逻辑构造是数学模型，可以借助数学方法来表示，详细的可以用离散数学中关系代数的二元组表示：Dat

4、a_Structure =D，S通常取S中的一个关系rj来进展讨论，rj可以表示为数据元素的序偶的集合。假设集合中有序偶，表示数据元素di和dj之间有rj这种关系。用二元组表示的数据的逻辑构造，有如下的常用术语1前趋结点、后继结点、相邻结点2开场结点、终端结点、内部结点数据的逻辑构造还可以利用更笼统的图形表示 v数据的逻辑构造有两大类：数据的逻辑构造有两大类：v1线性构造：经典的线性构造是线性表。线性构造：经典的线性构造是线性表。v 线性构造的逻辑特征是：有且仅有一个开场结点和一个终端结点线性构造的逻辑特征是：有且仅有一个开场结点和一个终端结点，其他的内部结点都有且仅有一个前趋结点和一个后继结

5、点，也就是，其他的内部结点都有且仅有一个前趋结点和一个后继结点，也就是说构造中的数据元素间存在着一对一的相互关系。说构造中的数据元素间存在着一对一的相互关系。v2非线性构造：经典的非线性构造有树形构造和图形构造。非线性构造：经典的非线性构造有树形构造和图形构造。v 树形构造的逻辑特征是：有且仅有一个开场结点，可有假设干树形构造的逻辑特征是：有且仅有一个开场结点，可有假设干个终端结点，其他的内部结点都有且仅有一个前趋结点，可以有假设个终端结点，其他的内部结点都有且仅有一个前趋结点，可以有假设干个后继结点，也就是说构造中的数据元素间存在着一对多的层次关干个后继结点，也就是说构造中的数据元素间存在着

6、一对多的层次关系。系。v 图形构造的逻辑特征是：可有假设干个开场结点和终端结点，图形构造的逻辑特征是：可有假设干个开场结点和终端结点，其他的内部结点可以有假设干个前趋结点和假设干个后继结点，也就其他的内部结点可以有假设干个前趋结点和假设干个后继结点，也就是说构造中的数据元素间存在着多对多的网状关系。是说构造中的数据元素间存在着多对多的网状关系。表1.1 某校围棋社团学生简表学号姓名性别出生日期职务01黄家正男1982-08-05团长02赵 芳女1981-08-15组长03王 明女1983-04-01组长04王 红女1982-06-28组员05张小才男1984-03-17组员06马立伟男1983

7、-10-12组员07孙 刚男1982-07-05组员08刘 永男1982-12-09组员 例例1.1 在表在表1.1中，八名学生按学号从小到大陈中，八名学生按学号从小到大陈列，构成一个线性构造。假设表示这种逻辑构列，构成一个线性构造。假设表示这种逻辑构造的关系为造的关系为r1，那么，那么r1可以定义为学生按学号可以定义为学生按学号顺序递增陈列的关系，该线性构造的逻辑构造顺序递增陈列的关系，该线性构造的逻辑构造可用二元组表示为：可用二元组表示为：L =D，S，r1SD =01，02，03，04，05，06，07，08 r 1 =， ，图1.1 线性构造的图示 例例1.2 在表在表1.1中，学生之

8、间还存在着指点与被指中，学生之间还存在着指点与被指点关系，其中点关系，其中01号学生为团长，直接指点号学生为团长，直接指点02和和03号学生，他们分别是组长，号学生，他们分别是组长，02号学生直接指点号学生直接指点04和和05号学生，号学生，03号学生直接指点号学生直接指点06、07和和08号学生号学生，假设表示这种逻辑构造的关系为，假设表示这种逻辑构造的关系为r2，那么，那么r2可以可以定义为学生之间的指点与被指点关系，该数据构造定义为学生之间的指点与被指点关系，该数据构造的逻辑构造可用二元组表示为：的逻辑构造可用二元组表示为：T =D，S，r2SD =01，02，03，04，05，06，0

9、7，08r2 =， ， 0 10 20 30 40 50 60 70 8图1.2 树形构造的图示例例1.3 在表在表1.1中，学生之间还有好友关系，如中，学生之间还有好友关系，如01和和02、03、05号是好友，号是好友，02和和04号是好友，号是好友，03和和05号是好友，号是好友，04和和05、06号是好友，号是好友，06和和07之间是好友，之间是好友，08无好友，假设表示无好友，假设表示这种逻辑构造的关系为这种逻辑构造的关系为r3，那么，那么r3可以定义为学生之间的好可以定义为学生之间的好友关系，该数据构造的逻辑构造可用二元组表示为：友关系，该数据构造的逻辑构造可用二元组表示为：G =D

10、，S，r3SD =01，02，03，04，05，06，07，08r3 =，数据的存储构造 数据的存储构造Storage Structure，是指数据的逻辑构造到计算机存储器的映射。对于数据的逻辑构造G =D，S，在映射中，一方面要将数据集D中的数据元素存放到存储器中，另一方面还要表达关系集S，常见的表达关系S的方式有显示和隐含两种。常用的实现数据存储构造的方法有如下四种：1顺序存储2链接存储3索引存储4散列存储四种存储方法，可以单独运用，也可以组合起来对数据构造进展存储映象。同一种逻辑构造采用不同的存储方法，可以得到不同的存储构造。针对详细的运用，某种数据构造选择何种存储构造主要思索运算的方便

11、及效率。存储构造的描画：数据的存储构造是数据的逻辑构造用计算机言语的实现，它是依赖于计算机言语的，因此可以借用高级言语中提供的数据类型如数组、指针等来描画它。l1顺序存储顺序存储l根本思想是：把逻辑上相邻的数据元素存储在物理位置上相邻的根本思想是：把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。存储单元里。l数据元素间的逻辑关系由存储单元的邻接关系来表达，也就是说数据元素间的逻辑关系由存储单元的邻接关系来表达，也就是说逻辑关系上相邻物理位置上也相邻，数据元素的逻辑次序与物理逻辑关系上相邻物理位置上也相邻，数据元素的逻辑次序与物理次序一致。这是一种隐含表达关系的存储方法，关系隐含在存储次

12、序一致。这是一种隐含表达关系的存储方法，关系隐含在存储位置上。位置上。 l数据元素在存储区域中是延续存放的，这种存储方法称为顺序存数据元素在存储区域中是延续存放的，这种存储方法称为顺序存储构造储构造Sequential Storage Structure，通常用计算机高级，通常用计算机高级言语中的数组来描画。言语中的数组来描画。 l2链接存储链接存储l根本思想是：经过附加指针域表示数据元素之间的关系。根本思想是：经过附加指针域表示数据元素之间的关系。l这种存储方法不要求逻辑上相邻的数据元素存储位置上也相邻，这种存储方法不要求逻辑上相邻的数据元素存储位置上也相邻，数据元素间的逻辑关系是经过附加指

13、示其他数据元素位置的地址数据元素间的逻辑关系是经过附加指示其他数据元素位置的地址信息指针而得到的，这是一种显示表达关系的存储方法。信息指针而得到的，这是一种显示表达关系的存储方法。l数据元素在存储区域中可以是延续的，也可以是不延续的，通常数据元素在存储区域中可以是延续的，也可以是不延续的，通常用计算机高级言语中的指针来描画，称为链接存储构造用计算机高级言语中的指针来描画，称为链接存储构造Linked Storage Structure。 l由于不要求存储空间的延续性，很适宜动态存储管理由于不要求存储空间的延续性，很适宜动态存储管理 例例1.4 用上述两种方法存储有序序列用上述两种方法存储有序序

14、列A=99， 123，134，假设每个数据元素占，假设每个数据元素占2个字个字 节，即一个存储单元为两个字节。节，即一个存储单元为两个字节。图1.4 关系的映像方法l 3索引存储索引存储l 根本思想是：除了存储数据元素，还要建立一个或假设干个附加的根本思想是：除了存储数据元素，还要建立一个或假设干个附加的索引表来标识数据元素的地址。索引表来标识数据元素的地址。l 索引表中的每一项称为索引项，是用来标识一个或一组数据元素的索引表中的每一项称为索引项，是用来标识一个或一组数据元素的存储位置。索引项普通方式为关键字，地址，其中的关键字是存储位置。索引项普通方式为关键字，地址，其中的关键字是用来标识数

15、据元素的数据项。用来标识数据元素的数据项。l 假设每个数据元素对应一个索引项，那么该索引表为稠密索引假设每个数据元素对应一个索引项，那么该索引表为稠密索引Dense Index。假设一组数据元素对应一个索引项，那么该索引。假设一组数据元素对应一个索引项，那么该索引表称为稀疏索引表称为稀疏索引Sparse Index。l 索引存储方法主要是用于实现快速查找而设计的一种存储方式。索引存储方法主要是用于实现快速查找而设计的一种存储方式。l 4散列存储散列存储l 根本思想是：根据数据元素的关键字直接计算出该结点的存储地址根本思想是：根据数据元素的关键字直接计算出该结点的存储地址，通常称为关键字地址转换

16、法。在此方法中需求设计一个散列函，通常称为关键字地址转换法。在此方法中需求设计一个散列函数，以关键字为自变量，散列函数值即为地址。数，以关键字为自变量，散列函数值即为地址。l 用这种存储方法设计的存储构造最适宜按关键字进展查找，但数据用这种存储方法设计的存储构造最适宜按关键字进展查找，但数据元素之间的关系曾经无法在存储构造上表达。元素之间的关系曾经无法在存储构造上表达。 数据的运算数据的运算也称操作是指对数据元素进展加工和处置。运算的种类很多，详细视运用的要求而设置运算的种类。对每种数据构造设置一些根本运算操作，使得不同运用都能经过这些操作实现对数据构造的各种访问，是数据构造中研讨的一个重要方

17、面。数据构造的根本操作普通包括查找、插入、删除、更新、排序等。这些根本运算实践是在笼统的数据上所施加的一系列笼统的操作，所谓笼统的操作，就是不涉及详细的运用，只知道这些操作应该完成的功能，但无须思索“如何完成。这些运算的粒度很小，是构造复杂运算的根底。数据根本运算的定义是基于数据的逻辑构造，每种经典的逻辑构造都有一个运算的集合。数据的运算是定义在数据的逻辑构造上而实如今数据的存储构造上的 。 数据的运算是经过算法来描画的 。在讨论任何一种数据构造时，都应该将数据的逻辑构造、数据的存储构造和数据的运算这三方面看成一个整体，不要孤立地了解一个方面，而要留意它们之间的联络 13 算法算法的概念及特性

18、算法Algorithm是处理特定问题的方法和步骤，是由假设干条指令组成的有限序列。一个算法必需具有以下五个特性：1有穷性：对于恣意一组合法输入值，一个算法必需总是在执行有穷步骤后终了，有限时间内完成。2确定性：算法中每条指令都确切地规定了所应执行的操作，使算法的执行者或阅读者能明确其含义及如何执行，不致产生二义性或多义性；另外，在同一条件下，一个算法只能有一条执行途径。3可行性：算法中的每一步都是可行的，都可以经过手工或机器可以接受的有限次操作在有限时间内完成。4输入：一个算法有0个或多个输入，这些输入是算法所需的初始量或待处置的对象，来自某个特定的对象集合。 5输出：一个算法有1个或多个输出

19、，这些输出与输入有着某种特定的关系。算法的描画算法的描画 算法普通可以采用自然言语、程序流程图、伪码、算法普通可以采用自然言语、程序流程图、伪码、高级程序设计言语等描画。高级程序设计言语等描画。算法的评价算法的评价 通常从定性和定量两方面来评价一个算法通常从定性和定量两方面来评价一个算法 算法的定性评价，是从算法的设计者和运用者角度算法的定性评价，是从算法的设计者和运用者角度来衡量优劣的来衡量优劣的 1正确性正确性Correctness是指算法该当满足是指算法该当满足详细问题的需求，即对合理的输入，算法都会得出详细问题的需求，即对合理的输入，算法都会得出正确的结果，这是设计和评价一个算法的首要

20、条件正确的结果，这是设计和评价一个算法的首要条件，否那么其他的评价规范也就无从谈起。，否那么其他的评价规范也就无从谈起。2可读性可读性Readablity是指算法被了解的难是指算法被了解的难易程度。易程度。3强壮性强壮性Robustness是指算法对输入的非是指算法对输入的非法数据恰当地作出反映或进展相应处置的才干。法数据恰当地作出反映或进展相应处置的才干。4简单性简单性Simplicity是指一个算法所采用的是指一个算法所采用的逻辑构造、存储构造以及处置过程的简单程度。逻辑构造、存储构造以及处置过程的简单程度。 l 算法的定量评价l1时间复杂度Time Complexity是一个算法运转时所

21、耗费的系统时间，也就是算法的时间效率。 l每条语句反复执行的次数称为语句的频度Frenquency countl当不思索算法运转的软硬件环境时，算法所耗费的时间就是该算法中一切简单语句的频度之和。 l普通情况，在讨论算法的时间效率时，主要思索当问题规模n趋向无穷大时，时间复杂度T(n)的数量级，亦称为算法的渐近时间复杂度，那么T(n)= O(f(n) 。l 记号“O是一个数学符号，其数学定义是： l 设T(n)和f(n)均为正整数n的函数，假设存在两个正整数M和n0，使得当nn0时，都有 | T(n)| M | f(n)| 存在，那么T(n)= O(f(n)。lim T(n) / f(n) =

22、 Mnu在多数情况下，当一个算法中有假设干个循环语句时，算法的时间复杂度是由嵌套循环中最内层循环语句的频度决议的。需求留意的是，假设算法中包括对其他函数或算法的调用，计算算法的时间复杂度时还要分析被调用算法或函数的时间复杂度。例例1.5 求一维数组元素中的最大值求一维数组元素中的最大值 int sum(int a,int n) int i,s; 1 s= a0; /*1次次*/2 for(i=1;in; i+; ) /*n次次*/3 if (s ai) s= ai; /*n-1次次*/4 return s; /*1次次*/ T1(n)= 1+n+n-1+1=2n+1 T1(n)=O(n) ，即

23、，即f(n)=n例例1.6 两个两个n阶方阵相加阶方阵相加void Matrixadd(int a ,int b ,int c ,int n) int i,j;1 for (i=0;in;i+) /*n+1次次*/2 for (j=0;jn;j+) /* n(n+1)次次*/3 cij=aij+bij; /* n2次次*/T2(n)= n+1+ n(n+1)+ n2=2n2+2n+1T2(n)=O(n2)，即，即f(n)=n2 例例1.7 求两个求两个n阶方阵的乘积阶方阵的乘积void Matrixmlt(int a ,int b ,int c ,int n) int i,j,k;1 for

24、(i=0;in;i+) /*n+1次次*/2 for (j=0;jn;j+) /* n(n+1)次次*/3 cij=0; /* n2次次*/4 for (k=0;kn;k+) /* n2(n+1)次次*/5 cij= cij+aik*bkj; /* n3次次*/ T3(n)= n+1+ n(n+1)+ n2+ n2(n+1)+ n3=2n3+3n2+2n+1T3(n)= O(n3) ，即，即f(n)=n3 l最好时间复杂度、最坏时间复杂度和平均时间复杂度最好时间复杂度、最坏时间复杂度和平均时间复杂度 l例例1.8 在一维数组中查找指定的元素在一维数组中查找指定的元素l int search(int a,int x,int n)l int i;l1 for(i=0;in; i+; ) l2 if (ai=x) ruturn i+1; l3 return 0; l l最好时间复杂度为最好时间复杂度为O(1)l最坏时间复杂度为最坏时间复杂度为O(n)l平均