2 数据结构(2学时)

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构,第一部分：基本知识,第二部分：线性结构,第三部分：非线性结构,第四部分：线性表的查找和排序,1,一、基本概念,1、,数据,:是描述客观事物并能为计算机加工处理的符号的集合。,2、,数据元素,：是数据的基本单位，即数据集合中的个体。,有些情况下也把数据元素称为结点、记录等。一个数据元素可由一个或多个数据项组成。,3、,数据项,：是有独立含义的数据最小单位，有时也把数据项称为域、字段等。,第一部分：基本知识,2,4、什么是数据结构？,数据结构（Data Structure）是指数据元素的组织形式和相互关系。,数据结构一般包括以下三方面的内容：,数据的逻辑结构,数据的物理结构,数据的运算,3,二、数据的逻辑结构：,数据的逻辑结构,从逻辑上抽象地反映数据元素间的结构关系，它与数据在计算机中的存储表示方式无关。,数据的逻辑结构有两大类：,线性结构，非线性结构。,1、线性结构的逻辑特征是：有且仅有一个始端结点和一个终端结点，并且除两个端点结点外的所有结点都有且仅有一个前趋结点和一个后继结点。线性表、堆栈、队列、数组、串等都是线性结构。,2、非线性结构的逻辑特征是：一个结点可以有多个前趋结点和后继结点。如树形结构、图等。,4,三、数据的物理结构,数据的物理结构是逻辑结构在计算机存储器里的映像，也称为存储结构。,数据的存储结构可用以下四种基本存储方法：,1、,顺序存储方法,把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。,2、,链式存储方法,不要求逻辑上相邻的结点在物理位置上也相邻，结点之间的逻辑关系是由附加的指针字段表示的。,3、,索引存储方法,在存储结点信息的同时，还建立附加的索引表。,4、,散列存储方法,根据结点的关键字直接计算出该结点的存储地址。,5,四、数据的运算,数据的运算是指对数据施加的操作。它是定义在数据的逻辑结构上的，但运算的具体实现要在物理结构上进行。,数据的每种逻辑结构都有一个运算的集合，常用的运算有,检索、插入、删除、更新、排序,等。,6,五、算法,1算法的性质,一个算法就是一种解题的方法，更严格地讲，算法必须满足以下准则：,有穷性,：一个算法的执行步骤必须是有限的。,确定性,：算法中的每一个操作步骤的含义必须明确。,可行性,：算法中的每一个操作步骤都是可以执行的。,输入,：一个算法一般都要求有一个或多个输入量。,输出,：一个算法至少产生一个输出量，它是算法对输入量的执行结果。,7,2、算法性能分析：,求解同一个问题，可以有多种不同的算法，那么如何衡量一个算法的好坏呢？,显然，首先算法应是正确可行的。,其次，通常还要考虑如下三方面的问题：,（l）执行算法所耗费的时间。,（时间复杂度）,（2）执行算法所占用的存储空间。,（空间复杂度）,（3）算法是否易于理解，易于编码，易于调试。,8,第二部分：线性结构,一、基本特点：,数据元素有限并有序。,线性结构的数据元素可排成一个线性队列：a,1,，a,2,，a,3,，a,n,其中， a,1,为起始元素，a,n,为终点元素，a,i,为索引号为i的数据元素。,又称为,线性表,。,9,二、常见的线性结构（线性表）：,顺序表、链表、堆栈、队列、数组、字符串等 。,1、顺序表,(理解特点),2、线性链表,(单向链表、双向链表、循环链表),3、堆栈,(先进后出)：口袋装大米,4、队列,(先进先出)：排队买大米,10,1顺序表,当线性表采用顺序存储结构时称之为顺序表。在顺序表中，数据元素按逻辑次序依次放在一组,地址连续,的存储单元里。由于逻辑上相邻的元素存放在内存的相邻单元里，所以顺序表的逻辑关系蕴含在存储单元的邻接关系中。,在高级语言中，可以直接用数组实现。,11,顺序表的特点如下：,物理上相邻的元素在逻辑上也相邻。,可随机存取。,存储密度大，空间利用率高。,对顺序表可进行插入、删除等操作，但运算效率低，需要大量的数据元素移位。,12,2单链表,采用链式存储结构的链表是用一组任意的存储单元来存放线性表的数据元素，这组存储单元,既可以是连续的，也可以是不连续的，,甚至可以是零星分布在内存中的任何位置上，从而可以大大提高存储器的使用效率。,在线性链表中，每个元素结点除存储自身的信息外，还要用指针域额外存储一个指向其直接后继的信息（即后继的存储位置：地址）。,对链表的访问总是从链表的头部开始，,根据每个结点中存储的后继结点的地址信息，顺链进行的。,每个结点只有一个指针域时，称为单链表。,13,单链表中，插入删除一个数据元素，仅仅需要修改该结点的前一个和后一个结点的指针域，非常简便，但要访问表中的任一元素，都必须从头指针开始，顺链查找，无法随机访问。,优点：插入、删除操作时移动的元素少。,缺点：所有的操作都必须顺链操作，访问不方便。,14,将顺序表与链表作一比较，可以看出：,顺序存储的访问是随机访问，而链式存储的访问是顺链进行的顺序访问。,顺序存储下插入、删除平均移动一半元素，效率不高，而链式存储下插入、删除效率高。,顺序存储空间利用率高，链式存储需额外增加地址指针的存储，增加空间耗费。,15,3栈与队列,栈与队列是两种特殊的线性表。即它们的逻辑结构与线性表相同，只是其插入、删除运算仅限制在线性表的一端或两端进行。,16,（l）栈,栈是仅限于在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为,栈顶,，另一端称为,栈底,。,当表中没有元素时称为,空栈,。,栈的特点是：,后进先出(LIFOLast In,First Out)。,如：入栈顺序为l，2，3，4，5，,则出栈顺序为5，4，3，2，l。,栈的基本运算有五种：,置空栈、判空栈、进栈（又称压栈）、出栈、取栈顶。,17,栈也可以分成采用顺序结构的顺序栈和采用链结构的链栈。,顺序存储的,顺序栈,利用一组地址连续的存储单元依次存放从栈底到栈顶的若干数据元素。,链式存储的,链栈,链栈是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行。链栈中每个数据 元素用一个结点表示，栈顶指针作为链栈的头指针。,18,（2）队列,队列是一种操作受限的线性表，它只允许在线性表的一端进行数据元素的插入操作，而在另一端才能进行数据,元素的删除操作。,其允许插入的一端称为,队尾,，允许删除的另一端称为,队头,。,特点：,先进先出(FIFOFirst In,First Out)。,同栈的操作类似，队列的基本操作也有五种：,置空队列、判队列空、入队列、出队列、取队头元素。,队列也可以分成采用顺序结构的,顺序队列,和采用链结构的,链队列,。,19,第三部分：非线性结构,一、树,1、树：是一个或多个结点元素组成的有限集合T，且满足条件如下：,（l）有且仅有一个结点没有前趋结点，称为根结点（root）。,（2）除根结点外，其余所有结点有且仅有一个直接前趋结点。,（3）包括根结点在内，每个结点可以有多个直接后继结点。,20,2、树结构的重要术语与概念：,叶子（或终端结点）,：没有后继结点的结点。,分支结点：,非叶子结点。,结点的度：,一个结点的子树数目就称为该结点的度。,树的度：,树中各结点的度的最大值称为该树的度。,子结点：,某结点子树的根称为该结点的子结点。,父结点：,相对于某结点的子树的根，称为该结点的,子树的父结点。,兄弟：,具有同一父结点的子结点称为兄弟。,21,结点的层次：,根结点的层次数是l，其他任何结点的层数等它的父结点的层数加1。,树的深度：,一棵树中，结点的最大层次数就是树的深度。,森林：,森林是n棵树的集合（n=0），任何一棵树，删去根结点，就变成了森林。对树中的每个结点来说，其子树的集合就是一个森林。,22,二、二叉树,（每个结点只有最多两个分支）,1、 二叉树结构也是非线性结构中重要的一类，它是有序树，,不是树的特殊结构,。在二叉树中，每个结点最多只有两棵子树，一个是,左子树,，一个是,右子树,。,二叉树有五种基本形态：它可以是空二叉树，根可以有空的左子树或空的右子树，或左、右子树皆为空。,必须注意一般树与二叉树的概念不同：树至少有一个结点，而二叉树可以是空；其次，二叉树是有序树，其结点的子树要区分为左子树和右子树，既使某结点只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树，而树中则无此区分。,23,2、 二叉树的性质：,性质1：在二叉树的第i层上至多有,2,i-1,个结点（i0）。,性质2：深度为k的二叉树至多有,2,k,-1,个结点（k0）。,满二叉树和完全二叉树是两种特殊形式的二叉树。,一棵深度为k且有2,k,-1个结点的二叉树称为,满二叉树,。,若一棵二叉树至多只有下面的两层上的结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为,完全二叉树,。,满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。,24,3、 二叉树的存储结构：,（l）顺序存储：,将完全二叉树的所有结点按照自上而下，自左向右的次序连续编号，并存储在一片连续的存储单元中。,（2）链式存储：,顺序存储容易造成空间浪费，并具有顺序存储结构固有的缺点：添加、删除伴随着大量结点的移动。,对于一般的二叉树，较好的方法是用二叉链表来表示。表中每个结点都具有三个域：左指针域Lchild、数据域Data、右指针域Rchild。其中，指针Lchild和Rchild分别指向当前结点的左孩子和右孩子。,25,4、 二叉树的遍历：,所谓遍历，是指按某种次序，依次对某结构中的所有数据元素访问且仅访问一次。,由于二叉树结构的非线性特点，它的遍历远比线性结构复杂，其算法都是递归的。有三种遍历方式：,先序遍历：访问根结点；先序遍历左子树；先序遍历右子树。（DLR）,中序遍历：中序遍历左子树；访问根结点；中序遍历右子树。（LDR）,后序遍历：后序遍历左子树；后序遍历右子树；访问根结点。（LRD）,26,三、图,（一个图G由点V(G)和边E(G)两个集合组成）,图是一种重要的、比树更复杂的非线性数据结构。,邻接点：,有边相连的点。,顶点的度,：与每个顶点相连的边数。,在有向图中，有入度（进的边数）和出度（出的边数）之分。,路径：,某一顶点到达另一顶点所经过的顶点序列。两个顶点之间可以有多条路径。,网络：,如果图G(V,E)中每一条边都赋有反映这条边的某种特性的数值，则称此图为一个网络，称与边相关的数值为该边的,权,。,27,图的存储结构,（1）邻接矩阵：,特点：,邻接矩阵是一种静态存储结构。,当图动态改变时，需改变邻接矩阵的大小，效率低。,矩阵大小与顶点个数相符，与边（弧）数目无关，易产生稀疏矩阵，造成空间浪费。,（2）邻接表：,采用动态的链式存储结构来保存信息。,28,第四部分：线性表的查找和排序,一、查找：,所谓,查找,（Search），又称检索，就是在一个含有n个数据元素的集合中，根据一个给定的值k，找出其关键字值等于给定值k的数据元素。,线性表的查找，常用的有如下三种方法：,顺序查找。,二分法查找。,分块查找。,29,1顺序查找,从第1个数据元素开始，逐个把数据的元素的关键字值与给定值比较，若找到某数据元素的关键字值与给定值相等，则查找成功；若遍历整个线性表都未找到，则查找失败。,30,2二分法查找,（先对关键字排序，然后再对排序好的数据查找。）,当顺序存储的线性表己经按关键字有序时，可以使用二分法查找。,二分法查找的基本思路是：由于查找表中的,数据元素按关键字有序,（假设为增序），则查找时不必逐个顺序比较，而先与中间数据元素的关键字比较。若相等，则查找成功；若不等，即把给定值与中间数据元素的关键字值比较，若给定值小于中间数据元素的关键字值，则在前半部分进行二分查找，否则在后半部分进行二分查找。这样，每进行一次比较，就将查找区间缩短为原来的一半。,31,3分块查找,（先分块：块间有序、块内无序）,分块查找是介于顺序查找与二分法查找之间的一种查找方法，又称索引顺序查找。,它的基本思想是：,分块,：将数据划分为若干数据块，数据在块内无序，但块间有序，也就是说，第一块内的最大数据比后继所 有块内的所有数据都小（假设按数据递增有序），后面的每一块内的所有数据都大于它前面的所有块的最大数据，同 时又小于后继所有块内的所有数据。,32,查找,：分两步进行。,块间：建立一个各块最大关键字值表，将待查数据在该表中按二分法或顺序查找进行，通过块间查找确定数据所在块。用二分法可以提高块间查找的效率。,块内：在块内按顺序查找方式直接查找元素。,由于块间查找用了二分法，所以整个算法的效率要比顺序查找高，但事先要将数据进行分块，这在一定程度上增加了额外的时间开销。,33,二、排序,排序,又称为,分类,，它是数据处理中经常使用的一种运算，是将一组数据元素（记录）按其排序码进行递增或递减的运算操作。排序分内排序和外排序。,内排序,整个排序运算在内存中进行。,外排序,对外存储器中的数据进行排序操作。,34,1插入法排序,把N个数据元素的序列分成两部分，一个是己排好序的有序部分，另一个是未排好序的未排序部分；把未排好序的元素逐个与己排好序的元素比较，并插入到有序部分的合适位置，最后得到一个新的有序序列。,35,【例13一5】插入法排序（线性表长度n=8）。,初始序列：49 38 65 97 76 13 27 49,（l）【38 49 65 97 76 13 27 49,（2）【38 49 6597 76 13 27 49,（3）【38 49 65 97 76 13 27 49,（4）【38 49 65 79 9713 27 49,（5）【13 38 49 65 76 97 27 49,（6）【13 27 38 49 65 76 97 49,（7）【13 27 38 49 49 65 76 97,36,2选择排序,每一轮排序中，将第i个元素与从序列第i+1到n的 n-I+1（i1，2，3，n-l）个元素中选出的、值最小的一个元素进行比较，若该最小元素比第i个元素小，则将两者交换。i从1开始，重复此过程，直到in-1。,简单地说，通过交换位置，选最小的放在第一，次小的放在第二，依此类推，直到元素序列的最后为止。,37,【例13一6】选择排序（线性表长度n8）。,初始序列：,49,38 65 97 76,13,27,49,（1）13,38,65 97 76 49,27,49,（2）13 27,65,97 76 49,38,49,（3）13 27 38,97,76,49,65,49,（4）13 27 38 49,76,97 65,49,（5）13 27 38 49,49,97,65,76,（6）13 27 38 49,49,65,97,76,（7）13 27 38 49,49,65 76 97,38,当相同关健字值经过排序仍保持原来先后位置时，称所用的排序方法是,稳定的,；反之，若相同关键字值经排序后发生位置交换，则所用的排序方法是,不稳定的,。,选择排序是一种稳定的排序方法。,39,3冒泡排序,冒泡法排序需要进行n一l轮排序过程。,第一轮：从a,1,开始，两两比较a,i,、a,i+1,（il，2，n-l）的大小，若a,i, a,i+1,小则交换a,i,与a,i+1,。当第一轮完成时，最大元素将被交换到最后一位（第n位）。,第二轮：仍然从a,1,开始，两两比较a,i,、a,i+1,（il，2，n-2）的大小，注意此时的处理范围从第一轮的整个序列n个数据元素比较n-1次（il，2，n-l），变成了n-1个数据元素比较n-2次（il，2，n-2）。当第二轮完成时，最大元素将被交换到次后一位（第n-1位）。,第n-1轮：只需比较最初两个元素，就完成了整个线性表的排序。,40,【例13一7】冒泡排序过程（线性表长度n二7）。,初始状态：【65 97 76 13 27 49 58,第一轮（il6）65 76 13 27 49 58 97,第二轮（il5）65 13 27 49 5876 97,第三轮（il4）13 27 49 5865 76 97,第四轮（il3）13 27 49 58 65 76 97,第五轮（il2）13 2749 58 65 76 97,第六轮（i1）13 27 49 58 65 76 97,41,4归并排序,将两个或两个以上的有序表组合成一个新的有序表。,将每个元素看成一个长度为1的子序列，把相邻子序列两两合并，得到一个新的子序列，如此重复，最后得到长度为n的一个新的有序序列。,42,【例13一8】归并排序过程（线性表长度n7）。,初始序列：25 57 48 37 12 92 86,（l） 25 57 37 48 12 92 86（两两合并）,（2）25 37 48 57 12 86 92（两两合并）,（3）12 25 37 48 57 86 92（两两合并）,43,