第2章 常用数据结构及其运算1

第第 2章章 常用数据结构及其运算常用数据结构及其运算石油工程学院石油工程学院概述概述图图 查找查找 排序排序 第二章 常用的数据结构及其运算树与二叉树树与二叉树数组数组 线性表线性表 栈栈线性表线性表 顺序表顺序表 线性表线性表 队列队列 线性表线性表 链表链表 2.72.92.82.12.22.32.52.62.42.10 数据处理是指对数据集合中各元素以各种方式进行运算，包括插入、删除、查找、更改、分析。 数据处理效率指的是： （ 1）数据处理速度；（ 2）数据处理过程中占用的计算机存储空间2.1 数据结构概述数据结构概述 数据处理的关键问题是：合理组织大量数据元素在计算机中的存储关系，以 提高数据处理效率，节省计算机存储空间。2.1 数据结构概述数据结构概述数据结构作为一门学科，主要研究以下问题：（ 1）数据集合中各数据元素之间固有的逻辑关系，即数据的逻辑结构；（ 2）各数据元素在计算机中的存储关系，即数据的存储结构；（ 3）对各种数据结构进行的运算。2.1.2 数据结构的基本概念和术语数据结构的基本概念和术语数据数据 (Data):所有能被计算机处理的符号的集合。所有能被计算机处理的符号的集合。数据元素数据元素 (Data Element): 是数据的基本单位，也称之为是数据的基本单位，也称之为 结点结点 (node)或记录或记录 (record), 在计算机程序中通常作为一个整体进行考虑和处理在计算机程序中通常作为一个整体进行考虑和处理。如数据集合如数据集合 N=1,2,3,4,5中中 1-5均为数据元素。均为数据元素。一个数据元素可由若干个一个数据元素可由若干个 数据项数据项 组成。数据项是数据的不可分组成。数据项是数据的不可分割的最小单位。割的最小单位。个个人人书书库库 数据数据元素元素数据对象数据对象 (Data Object)：性质相同的数据元素的集合。是数据的一个子集：性质相同的数据元素的集合。是数据的一个子集。数据对象可以是有限的，也可以是无限的。数据对象可以是有限的，也可以是无限的。例例 :整数的数据对象是整数的数据对象是 -3 ， -2， -1， 0， 1， 2， 3， 英文字符类型的数据对象是英文字符类型的数据对象是 A， B， C， D， E， F， 数据结构数据结构 (Data Structure)：是指带有结构的数据元素的集合。结构是指带有结构的数据元素的集合。结构 : 数据元素之间存在的关系。数据元素之间存在的关系。集合论方法定义结构集合论方法定义结构 S为一个二元组：为一个二元组： S=(D， R)其中：其中： D是数据元素的非空有限集，是数据元素的非空有限集， R是是 定义在定义在 D上关系的非空有限集。上关系的非空有限集。l如如 n维向量的数据元素集合为维向量的数据元素集合为 D=x1,x2, xn， D上的关系上的关系R=,即为线性表。即为线性表。2.1.2 数据结构的基本概念和术语数据结构的基本概念和术语2.1.2 数据结构的基本概念和术语数据结构的基本概念和术语数据的逻辑结构数据的逻辑结构 ：数据元素及其关系的数学特性：数据元素及其关系的数学特性 (逻辑关系逻辑关系 )。通常用前后件关系（或直接前驱与直接后继关系）描述通常用前后件关系（或直接前驱与直接后继关系）描述 , 如一年四季如一年四季，家庭成员等。，家庭成员等。数据类型数据类型 (Data type)： 在一种程序设计语言中，变量所具有的数据在一种程序设计语言中，变量所具有的数据种类。在种类。在 C中数据类型：中数据类型： 基本类型和构造类型基本类型和构造类型 ;基本类型：整型、浮点型、字符型基本类型：整型、浮点型、字符型 ;构造类型：数组、结构、联合、指针、枚举型、自定义。构造类型：数组、结构、联合、指针、枚举型、自定义。数据的物理结构数据的物理结构 (存储结构存储结构 )：是逻辑结构在计算机中的存储表示：是逻辑结构在计算机中的存储表示 (映映象象 )。也就是具体实现。分为顺序存储结构、链式存储结构。也就是具体实现。分为顺序存储结构、链式存储结构。 逻辑结构与物理结构必然一致吗？算法算法 ：是解决某一特定类型问题的有限运算序列，其实现必须借助：是解决某一特定类型问题的有限运算序列，其实现必须借助程序设计语言提供的数据类型及其运算。程序设计语言提供的数据类型及其运算。 算法是解题方案的准确而完整的描述。数据结构与算法数据结构与算法算法的基本特性算法的基本特性 ：(1)有穷性： 一个算法必须在执行有穷步之后结束，且每一步都在有穷时间内完成。(2)确定性： 每一步必须是明确的，不存在二义性。(3)可行性 ： 每一个步骤必须能够实现，可以通过基本运算执行有限次来实现，结果能够达到预期目的。算法的两个基本要素算法的两个基本要素 ：一是对数据对象的运算和操作，：一是对数据对象的运算和操作，二是算法的控制结构。由顺序、选择、循环组合而成二是算法的控制结构。由顺序、选择、循环组合而成。程序 =算法 +数据结构程序设计的核心是算法，处理的对象是数据。评价算法优劣的标准：评价算法优劣的标准： 时间复杂度和空间复杂度时间复杂度和空间复杂度算法的时间复杂度指执行算法所需要的计算工作量。算法的时间复杂度指执行算法所需要的计算工作量。一般情况下一般情况下 ,算法中基本操作重复执行的次数是问题规模算法中基本操作重复执行的次数是问题规模 n的某个的某个函数函数 ,算法的时间量度记作算法的时间量度记作 : T(n)=O(f(n)称作算法的渐近时间复杂度称作算法的渐近时间复杂度 ,简称时间复杂度。简称时间复杂度。时间复杂度函数：时间复杂度函数：常量型：常量型： O(1)多项式型：多项式型： O(n), O(n2), O(nk)对数型：对数型： O(log2n), O(nlog2n)指数型：指数型： O(2n)， O(en)2.1.2 数据结构的基本概念和术语数据结构的基本概念和术语空间复杂度指执行算法需要的内存空间。包括算法程序所占空间空间复杂度指执行算法需要的内存空间。包括算法程序所占空间、初始数据所占存储空间、算法执行过程中需要的额外空间。、初始数据所占存储空间、算法执行过程中需要的额外空间。 S(n)=O(f(n)时间与空间是一对矛盾，要节约空间往往要消耗较多的时间，反时间与空间是一对矛盾，要节约空间往往要消耗较多的时间，反之亦然。之亦然。目前，内存空间足够，应重点考虑时间。目前，内存空间足够，应重点考虑时间。int x=10,y=20;int t;t=x;x=y;y=t;printf(“%d%dn“,x,y );int x=10,y=20;x+=y;y=x-y;x-=y;printf(“%d%dn“,x,y );2.1.2 数据结构的基本概念和术语数据结构的基本概念和术语(1) 枚举法用于解决 “是否存在 “或 “有多少种可能 “等类型的问题。基本思想：根据所提出的问题，列举出所有可能的情况，从中找出能满足给定条件的解。特点 : 算法简单 , 运算量大 . n 常用算法 ：(2) 归纳法用于解决有某种规律的问题。归纳法是通过列举少量的特殊情况，经过分析，最后找出一般的的关系。归纳法在算法设计中应用很广，最常见的便是递推和递归。（ 3）回溯法基本思想就是试探：当算法从一个始点展开后，如果通道受阻，就退回到始点 (或某一特定点 )，然后向另一通道展开，再受阻就再返回到始点，继续展开。特点：该方法描述简明，但效率低，如：走迷宫通道。（ 4）数字模拟法（数字仿真） 通过编制程序，利用数字计算机进行模拟实际问题，称为数字模拟。（ 5）数值法（非直接解法）工程上许多问题过于复杂，没有解析解，如高次方程，某些微分方程等，可以离散化，迭代、逼近等数值方法。第二章 常用的数据结构及其运算概述概述图图 查找查找 排序排序 树与二叉树树与二叉树数组数组 线性表线性表 栈栈线性表线性表 顺序表顺序表 线性表线性表 队列队列 线性表线性表 链表链表 2.72.92.82.12.22.32.52.62.42.102.2 线性表线性表线性结构满足下列条件：线性结构满足下列条件：(1)有且只有一个根结点，它无前件；有且只有一个根结点，它无前件；(2)有且只有一个终结点，它无后件；有且只有一个终结点，它无后件；(3)除根结点和终结点外，其它结点只有一个前件和后件。除根结点和终结点外，其它结点只有一个前件和后件。线性表 (1inear-list):是一组性质相同的数据元素的有限序列。2.2.1线性表的定义和运算线性表的定义和运算例例 1、 26个英文字母组成的字母表个英文字母组成的字母表 （ A， B， C、 、 Z）例例 2、学生健康情况登记表如下：、学生健康情况登记表如下：姓姓 名名 学学 号号 性性 别别 年年 龄龄 健康情况健康情况王小林王小林 790631 男男 18 健康健康陈陈 红红 790632 女女 20 一般一般刘建平刘建平 790633 男男 21 健康健康张张 立立立立 790634 男男 17 神神 经经 衰弱衰弱 . . .2.2.1线性表的定义和运算线性表的定义和运算线性表是由线性表是由 n(n0)个数据元素组成的有限序列个数据元素组成的有限序列 ,表中的每一个数表中的每一个数据元素，除第一个外，每个元素有且只有一个前件，除最后一个据元素，除第一个外，每个元素有且只有一个前件，除最后一个外，外， 每个元素每个元素 有且只有一个后件，即线性表或是一个空表，或表有且只有一个后件，即线性表或是一个空表，或表示为示为 ： (a1， a2， a n)线性表中数据元素的个数线性表中数据元素的个数 n(n 0)称为表的称为表的 长度长度 。n=0时称为时称为 空表空表线性表是一种线性结构，数据元素在线性表中的位置只取决于线性表是一种线性结构，数据元素在线性表中的位置只取决于他们自己的序号，即数据元素之间的相对位置是线性的。他们自己的序号，即数据元素之间的相对位置是线性的。 a1 a2 a3 a4 an所有数据元素所有数据元素 ai在同一个线性表中必须是相同的数据类型。在同一个线性表中必须是相同的数据类型。2.2.1线性表的定义和运算线性表的定义和运算0.初始化一个线性表初始化一个线性表1.求出线性表的长度求出线性表的长度 ;2.存放一个新的数据元素于表的第存放一个新的数据元素于表的第 i个位置个位置 ;3.在第在第 i-1和第和第 i个元素之间插入一个新的数据元个元素之间插入一个新的数据元 素素 ;4.删除第删除第 i个数据元素个数据元素 ;5.将两个或两个以上的线性表合并成一个线性表将两个或两个以上的线性表合并成一个线性表 ;6.将一个线性表拆成两个以上的线性表将一个线性表拆成两个以上的线性表 ;7.复制一个线性表复制一个线性表 ;8.按某个特定的值查找线性表按某个特定的值查找线性表 ;9.对线性表中的数据元素按某个数据项值递增或递减的顺序重新排列对线性表中的数据元素按某个数据项值递增或递减的顺序重新排列 ;线性表的基本运算线性表的基本运算线性表的顺序存储结构具有以下基本特点：线性表的顺序存储结构具有以下基本特点：(1)线性表中所有元素所占的存储空间是连续的；线性表中所有元素所占的存储空间是连续的；(2)线性表中各元素在存储空间中是按逻辑顺序依次存放的。线性表中各元素在存储空间中是按逻辑顺序依次存放的。假设线性表的每个元素需占用假设线性表的每个元素需占用 k个存储单元，且第一个数据元素个存储单元，且第一个数据元素 a0的存的存储地址为储地址为 LOC(a0)， 则线性表中元素则线性表中元素 a i的存储地址的存储地址 : LOC( a i) = LOC (a0)+i*k程序设计语言中，通常定义一个一维数组表示线性表的顺序存储空间程序设计语言中，通常定义一个一维数组表示线性表的顺序存储空间。2.2.1线性表的定义和运算线性表的定义和运算2.2.2 顺序存储线性表顺序存储线性表线性表顺序存储结构的特点线性表顺序存储结构的特点 :(1) 占用连续的内存占用连续的内存 ;(2) 数据元素的逻辑结构和物理结构保持一致数据元素的逻辑结构和物理结构保持一致 ;(3) 只要确定存储顺序表的起始位置只要确定存储顺序表的起始位置 ,表中任意元素可随机存取表中任意元素可随机存取 ; 故该故该 结构亦称随机存储结构。结构亦称随机存储结构。线性表顺序存储结构的缺点线性表顺序存储结构的缺点 :(1)在插入或删除操作时在插入或删除操作时 ,需移动大量的元素需移动大量的元素 ;(2)在给长度变化较大的线性表分配空间时在给长度变化较大的线性表分配空间时 , 必须按最大空间分配必须按最大空间分配 ;从而造成存储空间不能得到充分利用从而造成存储空间不能得到充分利用 ;(3)表的容量难以扩容表的容量难以扩容 ;2.2.2 顺序存储线性表顺序存储线性表(1) 顺序表初始化该操作的实现非常简单，只需将表示顺序表长度的变量 len置为 0即可。以下算法对 顺序表进行初始化，并返回顺序表的长度一返回值即为顺序表的长度 0。Int Init(datatype vLENGTH return 0；2.2.2 顺序存储线性表顺序存储线性表(2) 顺序存储结构的插入运算顺序存储结构的插入运算0 a01 a12 a2 i-1 ai-1i aii+1 ai+1i+2 ai+2 num a num0 a01 a12 a2 i-1 ai-1i xi+1 aii+2 ai+1 num a num插入 x假设线性表的存储空间为假设线性表的存储空间为 V(0:m-1)，长度为，长度为 n(nm ),插入的位置为插入的位置为 i(i表示在第表示在第 i个元素之前插入），插入的新元素是个元素之前插入），插入的新元素是 b,插入过程如下：插入过程如下： 首先处理首先处理 3种异常情况种异常情况 ：a.当存储空间已满当存储空间已满 (n=m)时为上溢错误，不能进行插入，算法结束；时为上溢错误，不能进行插入，算法结束；b.当当 in时，认为在最后一个元素之前插入；时，认为在最后一个元素之前插入；c.当当 ilen) printf(“顺序表已满，无法插入 !n”)；else if (ilen) printf(“该位置不存在 !”)； ，elsefor(j=len； jn-1时，线性表中没有相应元素，算法结束；时，线性表中没有相应元素，算法结束；（ 2）从）从 i+1个元素开始，直到最后一个元素，每一个元素均依次个元素开始，直到最后一个元素，每一个元素均依次往前移动一个位置。往前移动一个位置。（ 3）最后将线性表的长度减小）最后将线性表的长度减小 1.（ 3）顺序表的删除）顺序表的删除（ 3）顺序表的删除）顺序表的删除int delete(char vLENGTH， int len， int i)int j;if (i=len) printf(“该位置不存在 !”)；elsefor (j=i; jlen;j+) /*从第 i个元素到倒数第二个元素 *vj=vj+1 /*每个元素向前移动一个位置 *return(len-1)； /* 户线性表长度减 l，并返回 *删除数据元素为字符型数据且长度为 1en的顺序表 v中的第 i个数据元素第二章 常用的数据结构及其运算概述概述图图 查找查找 排序排序 树与二叉树树与二叉树数组数组 线性表线性表 栈栈线