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

第第 2章章 常用数据结构及其运算常用数据结构及其运算石油工程学院石油工程学院概述概述图图 查找查找 排序排序 第二章 常用的数据结构及其运算树与二叉树树与二叉树数组数组 线性表线性表 栈栈线性表线性表 顺序表顺序表 线性表线性表 队列队列 线性表线性表 链表链表 2.72.92.82.12.22.32.52.62.42.10 数据处理是指对数据集合中各元素以各种方式进行运算，包括插入、删除、查找、更改、分析。 数据处理效率指的是： （ 1）数据处理速度；（ 2）数据处理过程中占用的计算机存储空间2.1 数据结构概述数据结构概述 数据处理的关键问题是：合理组织大量数据元素在计算机中的存储关系，以提高 数据处理效率 ，节省计算机存储空间。2.1 数据结构概述数据结构概述数据结构作为一门学科，主要研究以下问题：（ 1）数据集合中各数据元素之间固有的逻辑关系，即数据的逻辑结构；（ 2）各数据元素在计算机中的存储关系，即数据的存储结构；（ 3）对各种数据结构进行的运算。2.1 数据结构概述数据结构概述无序表 有序表35167885432933215446162129333543465478852.1 概述概述2.1.2 数据结构的基本概念和术语数据结构的基本概念和术语数据数据 (Data):所有能被计算机处理的符号的集合。所有能被计算机处理的符号的集合。数据元素数据元素 (Data Element):是数据的基本单位，是数据的基本单位， 也称之为也称之为 结点结点(node)或记录或记录 (record),在计算机程序中通常作为一个整体进行考虑在计算机程序中通常作为一个整体进行考虑和处理。和处理。如数据集合如数据集合 N=1,2,3,4,5中中 1-5均为数据元素。均为数据元素。一个数据元素可由若干个一个数据元素可由若干个 数据项数据项 组成。数据项是数据的不组成。数据项是数据的不可分割的最小单位。可分割的最小单位。个个人人书书库库 数据数据元素元素2.1 概述概述2.1.2 数据结构的基本概念和术语数据结构的基本概念和术语数据对象数据对象 (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.1.2 数据结构的基本概念和术语数据结构的基本概念和术语数据的逻辑结构：数据元素及其关系的数学特性数据的逻辑结构：数据元素及其关系的数学特性 (逻辑关系逻辑关系 )，通常用前后件关系（或直接前驱与直接后继关系）描述通常用前后件关系（或直接前驱与直接后继关系）描述 , 如一年如一年四季，家庭成员等。四季，家庭成员等。数据类型数据类型 (Data type)： 在一种程序设计语言中，变量所具有的在一种程序设计语言中，变量所具有的数据种类。在数据种类。在 C中数据类型：中数据类型： 基本类型和构造类型基本类型和构造类型 ;基本类型：整型、浮点型、字符型基本类型：整型、浮点型、字符型 ;构造类型：数组、结构、联合、指针、枚举型、自定义。构造类型：数组、结构、联合、指针、枚举型、自定义。数据的物理结构数据的物理结构 (存储结构存储结构 )：是逻辑结构在计算机中的存储表：是逻辑结构在计算机中的存储表示示 (映象映象 )。也就是具体实现。分为顺序存储结构、链式存储结构。也就是具体实现。分为顺序存储结构、链式存储结构。 逻辑结构与物理结构必然一致吗？算法：是解决某一特定类型问题的有限运算序列，其实现必须算法：是解决某一特定类型问题的有限运算序列，其实现必须借助程序设计语言提供的数据类型及其运算。借助程序设计语言提供的数据类型及其运算。2.1 概述概述2.1.2 数据结构的基本概念和术语数据结构的基本概念和术语数据结构与算法数据结构与算法算法的基本特性算法的基本特性 ：(1)有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。(2)确定性 每一步必须是明确的，不存在二义性。(3)可行性 每一个步骤必须能够实现，可以通过基本运算执行有限次来实现，结果能够达到预期目的。算法的两个基本要素：一是对数据对象的运算和操作，二是算算法的两个基本要素：一是对数据对象的运算和操作，二是算法的控制结构。由顺序、选择、循环组合而成。法的控制结构。由顺序、选择、循环组合而成。2.1 概述概述2.1.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.1.3 算法分析技术初步算法分析技术初步空间复杂度指执行算法需要的内存空间。包括算法程序所空间复杂度指执行算法需要的内存空间。包括算法程序所占空间、初始数据所占存储空间、算法执行过程中需要的额占空间、初始数据所占存储空间、算法执行过程中需要的额外空间。外空间。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.72.92.82.12.22.32.52.62.42.102.2 线性表线性表线性结构满足下列两个条件：线性结构满足下列两个条件：（ 1）有且只有一个根结点；）有且只有一个根结点；（ 2）每一个结点最多有一个前件，也最多有一个后件。）每一个结点最多有一个前件，也最多有一个后件。2.2.1线性表的定义线性表的定义2.2.2线性表的顺序存储结构（顺序表）线性表的顺序存储结构（顺序表）2.2.3线性表的链式存储结构（链表）线性表的链式存储结构（链表）2.2.4顺序表顺序表 和链表的比较和链表的比较2.2.1线性表的定义和运算线性表的定义和运算例例 1、 26个英文字母组成的字母表个英文字母组成的字母表（ A， B， C、 、 Z）v例例 2、某校从、某校从 1978年到年到 1983年某种型号的计算机拥有量的变年某种型号的计算机拥有量的变化情况。化情况。（ 6， 17， 28， 50， 92， 188）例例 3、学生健康情况登记表如下：、学生健康情况登记表如下：姓姓 名名 学学 号号 性性 别别 年年 龄龄 健康情况健康情况王小林王小林 790631 男男 18 健康健康陈陈 红红 790632 女女 20 一般一般刘建平刘建平 790633 男男 21 健康健康张张 立立立立 790634 男男 17 神神 经经 衰弱衰弱 . . .2.2.1线性表的定义和运算线性表的定义和运算线性表是由线性表是由 n(n0)个数据元素组成的有限序列个数据元素组成的有限序列 ,表中的表中的每一个数据元素，除第一个外，每个元素有且只有一每一个数据元素，除第一个外，每个元素有且只有一个前件，除最后一个外，有且只有一个后件，即线性个前件，除最后一个外，有且只有一个后件，即线性表或是一个空表，或表示为表或是一个空表，或表示为 (a1， a2， a n)线性表中数据元素的个数线性表中数据元素的个数 n(n 0)称为表的称为表的 长度长度 。n=0时称为时称为 空表空表线性表是一种线性结构，数据元素在线性表中的位线性表是一种线性结构，数据元素在线性表中的位置只取决于他们自己的序号，即数据元素之间的相置只取决于他们自己的序号，即数据元素之间的相对位置是线性的。对位置是线性的。2.2.1线性表的定义和运算线性表的定义和运算a1 a2 a3 a4 an所有数据元素所有数据元素 ai在同一个线性表中必须是相同的数据类型。在同一个线性表中必须是相同的数据类型。非空线性表具有如下结构特征：非空线性表具有如下结构特征：（ 1）有且只有个根结点）有且只有个根结点 a1，它无前件；，它无前件；（ 2）有且只有一个终端结点）有且只有一个终端结点 an，它无后件；，它无后件；（ 3）除根结点与终端节点外，其他所有结点有且只）除根结点与终端节点外，其他所有结点有且只有一个前件，也有且只有一个后件。有一个前件，也有且只有一个后件。2.2.1线性表的定义和运算线性表的定义和运算0.初始化一个线性表初始化一个线性表1.求出线性表的长度求出线性表的长度 ;2.存放一个新的数据元素于表的第存放一个新的数据元素于表的第 i个位置个位置 ;3.在第在第 i-1和第和第 i个元素之间插入一个新的数据元个元素之间插入一个新的数据元 素素 ;4.删除第删除第 i个数据元素个数据元素 ;5.将两个或两个以上的线性表合并成一个线性表将两个或两个以上的线性表合并成一个线性表 ;6.将一个线性表拆成两个以上的线性表将一个线性表拆成两个以上的线性表 ;7.复制一个线性表复制一个线性表 ;8.按某个特定的值查找线性表按某个特定的值查找线性表 ;9.对线性表中的数据元素按某个数据项值递增或递减的对线性表中的数据元素按某个数据项值递增或递减的顺序重新排列顺序重新排列 ;线性表的基本运算线性表的基本运算2.2.2顺序存储线性表顺序存储线性表线性表的顺序存储结构具有以下基本特点：线性表的顺序存储结构具有以下基本特点：(1)线性表中所有元素所占的存储空间是连续的；线性表中所有元素所占的存储空间是连续的；(2)线性表中各元素在存储空间中是按逻辑顺序依次存放的线性表中各元素在存储空间中是按逻辑顺序依次存放的。假设线性表的每个元素需占用假设线性表的每个元素需占用 k个存储单元，且第一个数据个存储单元，且第一个数据元素元素 a0的存储地址为的存储地址为 LOC(a0)， 则线性表中元素则线性表中元素 a i的存储地的存储地址址 : LOC( a i) = LOC (a0)+i*k程序设计语言中，通常定义一个一维数组表示线性表的顺程序设计语言中，通常定义一个一维数组表示线性表的顺序存储空间。序存储空间。2.2.2顺序存储线性表顺序存储线性表2.2.2顺序存储线性表顺序存储线性表线性表顺序存储结构的特点线性表顺序存储结构的特点 :(1)占用连续的内存占用连续的内存 ;(2)数据元素的逻辑结构和物理结构保持一致数据元素的逻辑结构和物理结构保持一致 ;(3)只要确定存储顺序表的起始位置只要确定存储顺序表的起始位置 ,表中任意元素可随机表中任意元素可随机存取存取 ; 故该结构亦称随机存储结构。故该结构亦称随机存储结构。线性表顺序存储结构的缺点线性表顺序存储结构的缺点 :(1)在插入或删除操作时在插入或删除操作时 ,需移动大量的元素需移动大量的元素 ;(2)在给长度变化较大的线性表分配空间时在给长度变化较大的线性表分配空间时 ,必须按最大空必须按最大空间分配间分配 ;使存储空间不能得到充分利用使存储空间不能得到充分利用 ;(3)表的容量难以扩容表的容量难以扩容 ;2.2.2.1顺序表初始化建立一个容量为 m的空线性表的顺序存储空间的 C+描述如下：template /模板声明， T为类型参数T* Init_sq_List(int m, int *n)T *v；v=new Tm;/动态存储空间*n=0;/线性表长度置 0return v；2.2.2顺序存储线性表顺序存储线性表2.2.2顺序存储线性表顺序存储线性表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,插入过程如下插入过程如下：（ 1）首先处理）首先处理 3种异常情况：种异常情况：a.当存储空间已满当存储空间已满 (n=m)时为上溢错误，不能进行插入，算法结束；时为上溢错误，不能进行插入，算法结束；b.当当 in时，认为在最后一个元素之前插入；时，认为在最后一个元素之前插入；c.当当 i/模板声明，模板声明， T为类型参数为类型参数void Ins_sq_list(T *v, int m, int *n, int i, T b)int k;if(*n=m)/存储空间已满，上溢错误存储空间已满，上溢错误cout*n)i=*n;/默认为在最后一个元素之后插入默认为在最后一个元素之后插入if(i=i;k-)/从最后一个元素开始，直到第从最后一个元素开始，直到第 i个元素均后移一个位个元素均后移一个位置置vk+1=vk;vi=b;/插入新元素插入新元素*n=*n+1;/线性表长度增加线性表长度增加 12.2.2顺序存储线性表顺序存储线性表2.2.2.2顺序存储结构的插入运算顺序存储结构的插入运算2.2.2顺序存储线性表顺序存储线性表2.2.2.3删除删除2918566335253147V(1:10)18566335253147V(1:10)185663352547V(1:10)删除 29删除 31假设线性表的存储空间为假设线性表的存储空间为 V(0:m-1)，长度为，长度为 n(nm),删除删除的位置为的位置为 i(i表示删除第表示删除第 i个元素），删除过程如下：个元素），删除过程如下：（ 1）首先处理）首先处理 2种异常情况：种异常情况：a.当线性表为空当线性表为空 (n=0)时为上溢错误，不能进行删除，算时为上溢错误，不能进行删除，算法结束；法结束；b.当当 in-1时，线性表中没有相应元素，算法结束时，线性表中没有相应元素，算法结束；（ 2）从）从 i+1个元素开始，直到最后一个元素，每一个元个元素开始，直到最后一个元素，每一个元素均依次往前移动一个位置。素均依次往前移动一个位置。（ 3）最后将线性表的长度减小）最后将线性表的长度减小 1.2.2.2顺序存储线性表顺序存储线性表2.2.2.3顺序存储结构的删除运算顺序存储结构的删除运算template/模板声明，模板声明， T为类型参数为类型参数void Del_sq_list(T *v, int m, int *n, int i)int k;if(*n=0)/空表，上溢错误空表，上溢错误cout*n-1)|(i0)/线性表中没有这个元素线性表中没有这个元素cout“There is not su