算法与数据结构基础.ppt

1/82,第六章 算法与数据结构基础,计算机程序主要对数据进行加工和处理。 程序中需要说明,数据结构:数据的组织形式和存储方式,算法:操作数据的步骤和方法,数据结构,算法,6.1 数据结构基本概念,随着计算机技术的发展,其应用领域越来越广。计算机应用已不在局限于数值计算，更多地用于数据处理和信息管理等非数值计算。,例如：学生、图书、财务和人事等信息管理系统。,每个学生对应一个数据，由学号、姓名、性别和出生日期等多个数据项构成，通常对学生信息进行插入、删除或查找等操作。,3/82,数据结构的定义,数据结构是指具有相同特征、相互之间有关联的数据集合。 现实世界中每个对象都可以映像成数据元素。数据元素可以由一个数、一个字符或一个名字等单个数据项组成，也可以由多个数据项组成。,数据元素、结点,数据结构中数据元素都具有某种共同特征 数据结构中数据元素之间存在着某种关系,4/82,向量2，43，68，45，32是数据结构,每个数据元素由一个数据项组成数据元素之间有位置上的前后关系,每个数据元素由一个数据项组成数据元素之间有位置上的前后关系,季度名称组成的集合是数据结构： 春，夏，秋，冬,家庭成员祖父、父亲、儿子是数据结构,每个数据元素由一个数据项组成数据元素之间有层次上的高低关系,5/82,数据结构是指带有结构特性的数据元素集合。 主要研究： 数据集合中数据元素之间所固有的关系，即数据逻辑结构； 数据处理时数据在计算机中的存储关系，即数据存储结构(物理结构)； 对数据所进行的操作,即算法。,6/82,数据逻辑结构,数据结构中数据元素之间所固有的关系描述成前后件(前驱与后继)关系。数据之间前后件关系是它们之间的逻辑关系，与它们在计算机中的存储位置无关，因此将这种关系称为逻辑结构。,7/82,一个数据结构可以表示为 S = ( D, R ),季节数据结构可以定义成 S=(D,R) 其中: D= 春, 秋, 冬, 夏 R= (春,夏), (夏,秋), (秋,冬) ,S表示数据结构,D数据元素集合,向量数据结构可以定义成 S=(D,R) 其中: D=2,43,68,45,32 R=(2,43),(43,68),(68,45), (45,32),8/82,线性结构：,一般来说,数据之间有集合,线性,树型和图形 4 种基本逻辑结构。,数据元素之间是一对一的关系 除第一个结点无前件外,其他结点都 只有一个前件 除最后一个结点无后件外,其他结点都只有一个后件,9/82,数据之间存在一对多的关系 一个结点最多有一个前件,可以有多个后件 前件与后件之间有层次关系,一般来说,数据之间有集合,线性,树型和图形 4 种基本逻辑结构。,树型结构：,10/82,数据元素之间存在多对多的关系 一个结点可以有多个前件和多个后件,一般来说,数据之间有集合,线性,树型和图形 4 种基本逻辑结构。,图形结构：,11/82,一般来说,数据之间有集合,线性,树型和图形 4 种基本逻辑结构。,集合：是一种松散结构，数据元素之间的关系只是同属于一个集合，可以用其他结构来表示。,12/82,数据物理结构,数据在计算机存储器中的存储方式称为数据物理结构(数据存储结构)。 在数据存储结构中，不仅要存放各个数据元素信息，还要存放数据元素之间前后件关系信息。数据元素在计算机中通常有四种存储方式：顺序、链式、索引和散列。,13/82,顺序存储结构,顺序存储结构是在内存中开辟一块连续内存单元用于存放数据，逻辑上相邻的结点在物理位置上也相邻。 即：结点之间的逻辑关系由存储单元的相邻关系来体现。,14/82,有如下顺序关系 a, b, c, d ,例如：,a,地址,2000H,2001H,c,2002H,2003H,d,数据,顺序存储结构,如果在b和c之间增加新数据x构成 a,b,x,c,d的顺序关系,应该如何存储？,b,15/82,链式存储结构,链式存储结构中，结点由两部分组成： 用于存放数据元素(数据域) 用于存放前件或后件的存储地址(指针域) 即：通过指针反映数据元素之间的逻辑关系,16/82,链式存储结构,有如下顺序关系 a, b, c ,例如：,a,2000,b,c,3001,1003,3001,1003,17/82,顺序存储结构与链式存储结构比较,顺序存储结构： 优点：每个结点占用存储空间最少 缺点：如果数据元素很多，则可能找不到一块足够大的连续存储单元 不能很好利用存储单元,容易产生碎片,链式存储结构: 优点：充分利用所有存储单元 缺点：每个结点占用较多存储单元,18/82,链式存储的插入,J,L,U ,在J,L之间插入接点S,链式存储的删除,J,L,U ,删除接点L,显然,链式存储的插入和删除操作比较简单、方便,19/82,6.2 算法基本概念,程序包含两方面的内容： 对数据的描述 对操作的描述 算法就是操作步骤，是解决“做什么”和“怎么做”的问题。算法是程序的灵魂，广义来说，为解决一个问题而采取的方法和步骤就称为算法。,20/82,计算机算法分为： 数值算法 非数值算法,各种数学问题的解法,常用于事物管理领域，如排序、查询,算法是定义在逻辑结构上的操作，独立于计算机，但算法的实现依赖于数据的存储结构。,21/82,算法的特征,可行性 确定性 有穷性 输入 输出,采取的方法和步骤可行，结果另人满意。,算法中的每一个步骤都必须确定，不能产生歧义。,执行算法时从外界取得必要的信息。一个算法可以有零或多个输入。,算法得到的结果就是输出,没有输出的算法是没有意义的,一个算法应该有一个或多个输出。,算法必须由有限步组成，并能在有效时间内完成。,22/82,算法描述方法, 计算,写出其算法。,分析：,1、展开上面算式 S=1+2+3+99+100,23/82, 计算,写出其算法。,main() int s=0; s=1; s=s+2; s=s+3; s=s+99; s=s+100; printf(“s=%d/n”,s); ,利用程序设计中的顺序结构,很不理想算法,24/82,用于描述算法的工具很多，通常有流程图、N-S图、自然语言和伪代码等工具。,自然语言：带序号的人类语言描述方法。,将变量s清0； 将变量n置1； 把s+n的值赋给s； 把n+1的值赋给n； 判断 n 100？是否成立，若成立，转3；否则转6 6. 输出s的值;,S=1+2+3+99+100,特点:易懂却不直观,对复杂算法描述很困难,易产生歧义。,若成立,25/82,伪代码法：是一种假的代码不能被计算机所理解，但可以用你熟悉的计算机语言的语句加上自然语言构成。,26/82,用于描述算法的工具很多，通常有流程图、N-S图、自然语言和伪代码等工具。,流程图法：用一些图框、线条以及文字说明 来形象地、直观地描述算法。,符号说明：,27/82,开始,0 S,1 n,Sn S,n1 n,输出S,结束,T,F,n 100,S=1+2+3+99+100,优点:直观形象 缺点:算法复杂时,篇幅 较多,费时且不方便修改。,28/82,N-S图: 完全去掉了带箭头的流程线、算法的所有处理步骤都写在一个大矩形框内, 框内还可以包含一些从属于它的小矩形框, 适于结构化程序设计。,29/82,算法评价,在计算机程序设计中,某一任务的算法设计得优与劣,将直接影响程序的运行效率、稳定性和可维护性。通常从以下4个方面评价一个算法。,正确性 可读性 健壮性 执行效率,算法本身没有语法错误,执行时输入正确数据能够得到正确结果.,算法要容易理解和阅读,容易实现，同时也要便于程序维护和完善。,指算法执行的时间性能和空间性能 。,算法能够对输入的各种数据给予适当的提示和处理 。,30/82,算法复杂度,算法复杂度是对算法效率的度量，是评价算法优劣的重要依据。 一个算法复杂度高低体现在运行该算法所需要资源的多少。,时间资源 空间(即存储器)资源,因而,算法复杂度包含时间复杂度和空间复杂度。,时间复杂度指执行算法所需时间 : 执行时间=语句执行时间语句执行次数,空间复杂度指在算法执行过程中,所占用附加空间数量,31/82,6.3 典型数据结构,数据逻辑结构分为: 线性结构 非线性结构,有且只有一个开始结点和一个终端结点，并且每个结点最多只有一个前件和一个后件，线性结构也称为线性表。栈、队列、数组和串等是特殊线性表,非线性结构包括树和图,32/82,6.3.1 线性表,线性表是一组特征相同数据的有限序列，表示为 L=(a1, a2 , a3 an)。,非空线性表的特征: 除a1无前件外,其它任意数据元素ai有且只有一个前件ai-1 。 除了an无后件外,其它任意数据元素ai有且只有一个后件ai+1。,线性表中数据元素个数n(n0)称为线性表长度。当n=0时,称为空表。在非空线性表中，每个数据元素都有一个确定位置，其位置取决于它的序号。,a1是第一个元素， a2 是第二个元素， an是最后一个元素。,33/82,向量2，43，68，45，32是线性表。,季度名称 春，夏，秋，冬是线性表。,学生基本信息: (20040001,刘强,男,1984/02/13,14001, 机械制造), (20040002,王晓红,女,1986/05/06,14001,机械制造), (20040003,李明,男,1984/10/25,14001,机械制造) 是线性表。,34/82,线性表顺序存储结构具有以下两个基本特点： 线性表中所有元素所占的存储空间是连续的。 线性表中各元素在存储空间中按逻辑顺序依次存放,即线性表的逻辑结构与存储结构相一致。,线性表通常采用顺序存储结构或链式存储结构。,由此可以看出:,在线性表的顺序存储结构中,其前后两个元素在存储空间中是紧邻的，前件元素一定存放在后件元素的前面。,35/82,例如：线性结构 a1，a2，a3，其中每个数据元素占2个存储空间，假设存储a1的首地址为2000。,2000,a1,占2个字节,a2,a3,2004,2002,占2个字节,占2个字节,存储地址：,结论：假设一个数据元素占用d个字节,线性表的首地址Addr(a1)为K，则存储任意一个数据元素ai的首地址为: Addr(ai)= Addr(a1)+(i-1)d=K+(i-1)d 其中 1 i n,优点：可以方便地随机读取表中任意元素 缺点：插入和删除运算需要移动大量元素，浪费大 量时间，时间效率较低。,36/82,线性表的链式存储,用一组存储单元(可以连续，也可以不连续)存储线性表中数据元素。为了反映数据元素之间的逻辑关系，每个数据元素由两部分组成： 1用于存放数据元素(数据域) 2用于存放前件或后件的存储地 址(指针域),结点之间逻辑关系由指针域来确定,37/82,单链表,定义：每个结点只有一个指针域的链表,head,每个单链表都有一个头指针，存放表中第一个结点的存储地址。 每个结点指针域存放后件结点的存储地址，最后一个结点无后件结点，指针域为空，用NULL或 表示。,38/82,循环链表,循环链表中增设一个表头结点，其数据域的值可以任意或根据情况来设置，指针域指向第一个结点。,将单链表最后一个结点的空指针域改为指向该链表的第一个结点，即首尾相连。,空循环链表,非空循环链表,注意头指针和表头结点的区别,39/82,循环链表特点： 从表中任一结点出发，均可以找到其它所有结点； 在任何情况下，带有表头结点的循环链表中至少有一个结点存在，从而使空表和非空表运算统一。 循环链表运算与单链表区别： 对单链表进行操作时，要判断是否是表尾，即指针是否为NULL； 而对循环链表操作时，要判断是否是头指针。,40/82,6.3.2 栈,定义：栈是只能在表的一端进行插入和删除运算的线性表。,通常将允许插入和删除运算的一端称为栈顶(top)，另一端称为栈底 (bottom),不含元素的栈称为空栈。 向栈中插入元素称为入栈。 从栈中删除元素称为出栈。,41/82,设有一个栈S=a1,a2,an，入栈顺序是a1、a2最后是an。栈的状态如图所示：,a1,a2,an,栈底bottom,栈顶top,入栈,出栈,栈特点：后进先出。,故也称为“先进后出”表或“后进先出”表,42/82,栈的基本运算,栈初始化：构造一个空栈。 空栈判断：判断栈是否为空。 入栈：在栈顶插入一个元素。 出栈：在栈顶删除一个元素。 读栈：仅读取栈顶数据，并不删除元素。,43/82,栈的顺序存储,设用变量top表示栈顶位置，用n表示栈中最多能容纳元素的个数。,栈顺序存储结构是用一块连续存储区域存放栈中元素。连续区域的低地址一端作为栈底，栈底固定不变。,44/82,入栈运算,S1：如果top=n，则栈已满，提示入栈失败(栈“上溢”错误)，并结束入栈； S2：top+1 top； S3：将新元素放在当前栈顶位置(top)上。,a1,a2,a3,bottom,top,a4,45/82,出栈运算,S1：如果top=0，则栈为空，提示出栈失败(栈“下溢”错误)，并结束出栈； S2：将当前栈顶(top)元素赋给一个变量； S3：top 1 top。,a3,top,a1,a2,bottom,46/82,例如，容量为6的栈中已有3个元素,如图所示：,1,2,3,4,5,6,A,C,B,bottom,top,X、Y两个元素先后入栈,X,Y,元素Y出栈,47/82,6.3.3 队 列,允许在一端进行插入、而在另一端进行删除的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。,入队,退队,队尾,a,b,c,队头,48/82,队列的基本运算,初始化队列 空队列判断 入队运算 出队运算 读队头元素 队列长度,49/82,队列顺序存储及其常用运算,队列的特点: 先进先出 入队和出队运算时队头和队尾位置要发生变化,队头 front(指向第一个元素的前一个单元位置) 队尾 rear(指向最后一个元素的位置) 队列中容纳元素个数为n,50/82,创建一个空队列,并令 front= rear=-1,1.初始化队列,front,-1,2,0,1,rear,51/82,2. 入队运算,S1：如果rear=n-1，则队列已满，提示入队失败(队列“上溢”错误)，并结束入队； S2：rear+1 rear； S3：将新元素放在当前队列位置(rear)上,front,rear,-1,2,0,1,A,B,C,52/82,3. 退队运算,S1：如果front=rear，则队列已空,提示退队失败(队列“下溢”错误),并结束退队； S2：front+1 front; S3：取front所指元素,front,rear,-1,2,0,1,A,B,C,此时虽然队列有空位置，但也不能插入新结点。,53/82,循环队列,将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，这样可以把退队的空间利用起来。,0,2,3,1,0,2,1,3,4,54/82,循环队列的运算,1.初始化队列,创建一个空队列,并令 front= rear=0,1,3,2,4,0,front,rear,55/82,S1: 先判断队列是否已满，若队满则入队失败，否则元素入队 S2: (rear+1)%nrear当rear+1=n时，0 rear S3:将新元素放在当前队尾位置（rear）。,循环队列的运算,2.入队运算,1,3,2,4,0,rear,front,a,b,c,例如：插入结点a,b,c,显然,再插入两个结点后front=rear,此时为满队列,56/82,循环队列的运算,3.出队(退队)运算,S1: 先判断队列是否为空，若队空则出队失败（上溢） S2: (front+1)%nfront当front+1=n时，0 front,0,2,1,3,4,a,b,c,rear,front,例如：删除结点a,显然,再删除两个结点后front=rear,此时为空队列,因此：通常需要增加一个变量用来标识当front=rear时，队列是满还是空。,57/82,6.3.5 树,树是一种常用的非线性结构，树是由n(n0)个结点组成的有限集合。当n=0时，称为空树；否则，有且仅有一个根结点，当n1时，其余结点被分成m(m0)个互不相交的子集T1，T2,.,Tm，每个子集又是一棵树。 树是递归定义的，即一棵树由根及若干子树构成，每棵子树又是由更小的子树构成。,58/82,结点的度：一个结点所拥有后件个数 树的度：树中所有结点的最大度,根,子结点,叶结点,59/82,结点的层次从根结点算起，根结点在第一层，根的直接后继结点在第二层，同一层上所有结点的后继结点均在下一层。,1,2,3,4,树中结点的最大层次称为树的深度或高度,60/82,6.3.6 二叉树,非空二叉树有且只有一个根结点； 每个结点最多有两棵子树, 且有左右之分,二叉树是另一种树形结构，每个结点最多只有两个后件(即最大度为2)。,特点：,61/82,二叉树有五种基本形态,62/82,二叉树基本性质,性质一：,在二叉树的第i层上，最多有2i-1个结点(i1).,性质二：,深度为k的二叉树最多有2k-1个结点(k1).,性质三：,对于任意一棵二叉树，度为0的结点(即叶子结点)总比度为2的结点多一个.,63/82,满二叉树,如果一个深度为k的二叉树拥有2k-1个结点，则称它为满二叉树。,每一层的结点数都达到最大值, 叶子结点都在最下面的同一层上,完全二叉树,一棵深度为k的二叉树, 如果第一层到第k-1层是一棵满二叉树, 第k层上的结点数没有达到最大值2k-1, 但这些结点都满放在该层最左边, 则称此二叉树为完全二叉树。,如果某个结点没有左子树,则它一定没有右子树,64/82,注：满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。,65/82,完全二叉树性质：,12个结点的完全二叉树,性质一：,具有n个结点的完全二叉树的深度为 log2n+1。其中，log2n 表示取log2n的整数部分。,66/82,完全二叉树性质：,性质二：,在有n个结点的完全二叉树中, 将所有结点按从上到下, 从左到右的顺序用自然数1, 2, , n进行编号, 则对于编号为k的结点有如下结论：,k=1时, 该结点为根结点。 k1时, 该结点的父结点编号为int(k/2)。 2k=n时, 编号为k的结点的左子结点编号为2k, 否则无左子结点。 2k+1=n时, 编号为k的结点的右子结点编号为 2k+1, 否则无右子结点。,1,2,3,4,5,6,7,10,11,9,8,12,67/82,二叉树的顺序存储,二叉树顺序存储是指用一组连续存储单元存储二叉树中的结点。结点存储顺序是按着从上到下、从左到右顺序。,1 2 3 4 5 6 7,按照完全二叉树每个结点编号的顺序存放结点,通过结点的编号准确地反映结点之间的逻辑关系。,1,2,3,4,5,6,7,68/82,非完全二叉树顺序存储,A,C,B,E,G,F,1 2 3 4 5 6 7,显然,顺序结构适用于完全二叉树，对于非完全二叉树，会浪费许多存储空间。,69/82,二叉树链式存储,二叉树每个结点由数据域和指针域组成 。,两个指针域： o 一个用于指向左子结点 o 一个用于指向右子结点,常见二叉树结点结构如图：,数据域,存储左子结点的存储地址,存储右子结点的存储地址,70/82,二叉树链式存储,A,T,X,B,C,P,Z,Y,BT,71/82,二叉树的遍历,遍历二叉树是指按照某种顺序访问二叉树中每个结点的过程，每个结点被访问一次且仅一次。 根据对根访问的次序，二叉树的遍历分为先序遍历、中序遍历和后序遍历。,72/82,先序遍历,访问根结点 先序遍历左子树 先序遍历右子树,A,遍历结果：,T,B,Z,X,C,P,Y,因为左子树空，故遍历右子树,73/82,中序遍历,中序遍历左子树 访问根结点 中序遍历右子树,A,T,Z,B,C,X,Y,P,因为左子树空,遍历结果：,74/82,后序遍历左子树 后序遍历右子树 访问根结点,后序遍历,遍历结果：,A,T,Z,B,C,X,Y,P,因为左子树空，故遍历右子树,75/82,6.4 典型算法,对非数值型数据通常有插入、删除、查找和排序等操作。其中查找和排序是数据处理中比较重要的算法。,查找又称检索，是指在数据集合中查找某个数据元素的过程。若存在这样数据元素,则查找成功；否则，查找失败。,6.4.1 查找,76/82,1 顺序查找,适用于线性表，其基本方法是 ：,从线性表中第一个元素开始，依次将线性表中的元素与给定值进行比较。 若相等，则查找成功； 若直到最后一个元素，还没找到与给定值相等的元素，则查找失败。,77/82,例如：在顺序表( 88, 15, 23, 80, 63, 8, 86, 46, 71, 101 )中, 查找 值为71的数据元素。,从线性表中第一个元素88开始, 依次将 线性表中元素与71进行比较。 直到第九个元素为71, 查找成功。,特点：顺序查找算法简单,但是执行效率较低,在下列两种情况下,只能使用顺序查找法： 线性表是线性链表。 线性表是顺序表，但表中元素无序排列。,此题比较了9次,78/82,2 二分查找,又称折半查找, 要求被查找的表采用顺序存储结构且数据元素按数据值升序或降序排列, 即二分查找法只适用于有序表。,基本思想是(设顺序表升序排列)： 将给定值与中间位置元素比较,若相等,则 查找成功； 若给定值小于元素值,则继续对前半部分 再进行折半查找； 若给定值大于中间位置元素值,则继续对后半部分再进行折半查找。,79/82,例：在有序顺序表(8，15，23，46，63，71，80，86，88，101)中，用折半查找法查找值为 71 的数据元素。,key=71 8 15 23 46 63 71 80 86 88 101 1 2 3 4 5 6 7 8 9 10,第一次查找mid=5,第二次查找mid=8,第三次查找mid=6,71 80 86 88 101 6 7 8 9 10,6371,故在后半部分进行折半查找,8671,故在前半部分进行折半查找,71 80 6 7,71=71,查找成功,80/82,2.排序算法,排序是将一组无序数据按值递增(或递减)进行重新排列。,三类基本排序方法,交换排序法,选择排序法,插入排序法,81/82,1交换排序法,在排序过程中, 通过数据元素之间不断地进行比较与交换, 最终达到排序目的。 冒泡排序法的基本思想是： 对所有相邻元素进行比较，若逆顺，则将其交换，最终达到有序化。,82/82,交换排序法,原序列：,42,23,16,47,11,45,13,49,42,23,16,47,11,45,13,49,第1 遍,第2遍,第3遍,第4遍,第5遍,第