第3章基本数据结构2.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第三章基本数据结构,面条结构,索引结构,拓扑结构,直接编码,游程长度编码,链码,块码,四叉树,数据结构的基本概念,数据,数据就是采用计算机能够识别、存储和处理的方式，对现实世界的事物进行的描述。,数据就是计算机化的信息。,数据元素,数据元素是数据的基本单位，即数据集合中的个体。,有时也把数据元素称作,结点,、,记录,、,表、目,等。一个数据元素可由一个或多个数据项组成，数据项是有独立含义的数据最小单位，有时也把数据项称作域、字段等。,数据结构,数据结构概念一般包括三个方面的内容：数据之间的,逻辑关系,、数据在计算机中的,存储方式,以及在这些数据上定义的,运算集合,。,（,1,）数据的逻辑结构。,数据的逻辑结构是数据间关系的描述，它只抽象地反映数据元素间的逻辑关系，而不管其在计算机中的存储方式。,数据的逻辑结构分为线性结构和非线性结构。,（,2,）数据的存储结构。,数据的存储结构是逻辑结构在计算机存储器里的实现。按其结点各域的性质可分成两大类：,一类是存放自身值的域（信息域）。,另一类是存放该结点与其它结点的关系的域（指针）。,（,3,）数据的运算。,数据的运算定义在数据的逻辑结构上，运算的具体实现要在存储结构上进行。,常用的运算有：检索、插入、删除、更新、排序等。,info,link,info,数据存储方式,1,、顺序存储结构,主要用于线性的数据结构，它把,逻辑上相邻的数据元素存储在物理上,相邻的存储单元里，结点之间的关系,由存储单元的邻接关系来体现。,例如，线性表（,k1,，,k2,，,k3,，,k4,，,k5,），假定每个结点占一个存储单元，,结点,k,存放在,200,号单元中，则顺序存,储实现如右图所示。,k,1,k,2,k,3,k,5,k,4,200,201,202,203,204,顺序结构的主要特点是：,（,1,）结点中只有自身信息域，没有连接信息域。因此，存储密度大，存储空间利用率高。,（,2,）可以通过计算直接确定数据结构中第,i,个结点的存储地址,L,，计算公式为：,Li,L0,（,i-1,）,m,其中，,L0,为第一个结点的存储地址，,m,为每个结点占用的存储单元个数。,（,3,）插入、删除运算会引起大量结点的移动。,2,、链式存储结构,链式存储结构就是在每个结点中至少包括一个指针域，用指针来体现数据元素之间逻辑上的联系。可以把逻辑上相邻的两个元素存放在物理上不相邻的存储单元中。,例如，线性表（,k1,，,k2,，,k3,，,k4,，,k5,）可以用链式存储，如下页图所示。,链式存储结构的主要特点：,（,1,）结点中除自身信息外，还有表示连接信息的指针域，因此比顺序存储结构的存储密度小，存储空间利用率低。,（,2,）逻辑上相邻的结点物理上不必邻接，可用于线性表、树、图等多种逻辑结构的存储表示。,（,3,）插入、删除操作灵活方便，不必移动结点，只要改变结点中的指针值即可。,线性表,线性表的基本概念,1,、线性表的定义,线性表是最简单、最常用、最基本的一种数据结构。线性表的逻辑结构是,n,个数据元素的有限序列：,（,a1,，,a2,，,.,，,an,）,表中元素的个数门定义为线性表的长度（,n=0,），,n=0,的表称为空表。,2,、线性表的结构特征,（,1,）数据元素呈线性关系；,（,2,）必存在唯一的一个被称为“第一个”的数据元素；,（,3,）必存在唯一的一个被称为“最后一个”的数据元素；,（,4,）除第一个元素外，每个元素都有且只有一个前驱元素；,（,5,）除最后一个元素外，每个元素都有且只有一个后继元素；,（,6,）所有数据元素,ai,，在同一个线性表中必须是相同的数据类型。,3,、线性表的种类,按其存储结构可分为：,（,1,）顺序表,用顺序存储结构存储的线性表称为顺序表。,（,2,）链表,用链式存储结构存储的线性表称为链表。,4,、线性表的基本运算,（,1,）在两个确定的元素之间插入一个新的元素；,（,2,）删除线性表中某个元素；,（,3,）按某种要求查找线性表中的一个元素，需要时，还可找到元素进行值的更新。,顺序表和一维数组,1,、顺序表的定义,用一组地址连续的存储单元依次存放线性表的数据元素，这种顺序分配存储方式的表，称为顺序表。,2,、顺序表的结构特点,（,1,）将表的数据元素按其逻辑顺序依次存放到一组地址连续的存储单元中；,（,2,）逻辑上相邻元素的存储地址也是相邻的，线性表的逻辑关系隐含在存储单元的邻接关系中。,（,3,）数据元素的数据类型相同；,（,4,）每一个元素占用同样大小的存储单元。,3,、顺序表与一维数组的关系,高级语言里的一维数组是用顺序方式存储的线性表，因此，一维数组也称为顺序表。一维数组的各元素下标与线性表中的元素序号一一对应。,例如：,用一维数组,A(1,n),存储线性表（,a,1,，,a,2,，,a,3,，,.,，,a,n,）,时，,A,（,k,）,的值就是表中第,k,个数据元素,a,k,。,即数组的下标可看成是线性表中数据元素的相对地址。,4,、顺序表的插入与删除运算,（,1,）插入运算,在线性表（,a,1,，,a,2,，,a,i,a,i+1,，,，,a,n,）,的第,i,个位置前插入元素,x,，,使之成为（,a,1,，,a,2,，,x,，,a,i,a,i+1,，,，,a,n,）。,a,1,a,2,a,i,a,i+1,a,n,单元编号 存储空间,1,2,i,i+1,n,n+1,a,1,a,2,a,i,a,i+1,a,n,单元编号 存储空间,1,2,i,i+1,n,n+1,a,1,a,2,a,i,a,i+1,a,n,单元编号 存储空间,1,2,i,i+1,n,n+1,a,1,a,2,a,i,a,i+1,a,n,x,单元编号 存储空间,1,2,i,i+1,n,n+1,（,2,）删除,在线性表（,a,1,，,a,2,，,，,a,i-1,，,a,i,，,a,i+1,，,，,a,n,）,中删除第,i,个数据元素，使之成为（,a,1,，,a,2,，,，,a,i-1,，,a,i+1,，,，,a,n,）。,a,1,a,2,a,i,a,i+1,a,n,单元编号 存储空间,1,2,i,i+1,n,a,1,a,2,a,n,单元编号 存储空间,1,2,i,i+1,n,a,i+1,链表,1,、单链表（线性链表）,单链表就是链式存储的线性表，其结点除信息域外还含有一个指针域，用来指出其后继结点的位置。,链表的插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可。,info,（,信息域）,link,（,指针域）,2,、循环链表,循环链表和单链表的差别在于链表中最后一个结点的指针域不为“,NULL”,，,而指向第一个结点，整个链表成为一个由链指针相链结的环。,结点,1,结点,2,结点,n,3,、双向链表,除设有指向后继结点的指针，还设一个指向前驱结点的指针，称这种含有两个指针域的结点构成的链表为双向链表。,栈（,stack,）,1,、,栈的定义,栈,（,stack,）,是一种特殊的线性表，其元素均按,“,后进先出,”,的原则进行操作。因其运算规则受到一定约束和限定，故又称限定性数据结构。,2,、栈的结构,a,n,a,3,a,2,a,1,栈顶,Top,栈底,Bottom,出栈,Pop,入栈,Push,表头,表尾,3,、栈的特点,（,1,）栈是按“,先进后出,”（,LIFO,）,的原则进行操作；,（,2,）表尾称为栈顶（,Top,），,表头称为栈底（,Bottom,）；,（,3,）,表中无元素时称为空栈。,（,4,）栈的插入和删除运算被限定仅在表尾进行。,（,5,）栈的物理存储可以用顺序存储结构,，也可以用链式存储结构。,4,、栈的运算,进栈操作,退栈操作,设置一个空栈,判定某个栈是否为空栈,读取栈顶元素等。,Top,栈顶,栈底,链栈,1,、,队列的定义,队列是一种特殊的线性表，其元素均按,“,先进先出,”,的原则进行操作。因其运算规则受到一定约束和限定，也是限定性数据结构。,队列（,Queue,）,2,、队列的结构,a,1,a,2,a,3 ,a,n,出队列,（删除）,入队列,（插入）,队头,（,Front,）,队尾,（,Rear,）,3,、队列的特点,（,1,）队列是按“,先进先出,”（,FIFO,）,的原则进行操作；,（,2,）限定所有的插入只能在表的一端进行，这一端称为队尾（,Rear,）。,（,3,）,限定所有的删除都在表的另一端进行的线性表，这一端称为队头（,Front,）。,（,4,）,表中无元素时称为空队列。,（,5,）队列的物理存储可以用顺序存储结构，也可以用链式存储结构。,4,、队列的运算,插入一个新的队尾元素（入队列）,删除队头元素（出队列）,设置一个空队列,判定某个队列是否是空队列,读取队头元素等,队列的插入与删除,A,A,B,B,B,C,B,C,D,C,D,E,C,D,F,R,初态,F,R,插入,A,F,R,插入,B,F,R,删除,A,F,R,插入,C,F,R,插入,D,F,R,删除,B,插入,E,F,R,环状队列,1,、串的特点,串可以看作一维字符数组，但其长度不恒定。,2,、串的运算,串不可作四则运算，可做删除、插入操作,，,还可以取子串（,Substring,）。,3,、串的存储,串可以按顺序结构存储，也可以用链表表示。,串（,String,）,1,、树的定义,树（,Tree,）,是由一个或多个结点组成的有限集合,T,其中有一个特定的称为根（,Root,）,的结点；其余结点可分为,m,（,m,0,）,个互不相交的有限集,T,1,，,T,2,，,T,3,，,，,T,m,，,其中每一个集合本身又是一棵树，且称为根的子树（,Subtree,）。,树和二叉树,树与二叉树的定义和术语,A,A,B,D,C,E,G,F,H,J,I,度,（,Degree,）：,一个结点的子树个数称为该结点的度（,Degree,）；,树中各结点的度的最大值被定义为该树的度；,树林,：,0,棵或多棵不相交的树的集合称为树林。,2,、二叉树定义,二叉树（,Binary Tree,）是,n,（,n=0,）,个结点的有限集，它或为空树,(n=0,），,或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉树组成。,A,B,C,D,E,F,G,H,I,A,A,B,A,C,注意：,（,1,）二叉树不是树的特殊情况，是两个概念；,（,2,）树和二叉树之间最主要的差别是：二叉树的结点的子树要区分左子树和右子树。,树的存储结构可以采用具有多个指针域的,多重链表,，结点中指针域的个数由树的,度,来决定。,树的存储结构,通常使用具有两个指针域的,二叉链表,作二叉树的存储结构。,二叉树的存储结构,1,、,树与二叉树之间的对应关系,每一棵树都能唯一地转换到它所对应的二叉树。,2、,树转换成对应二叉树的方法,凡是兄弟就用线连接起来，对每个非终端结点，除其最左孩子外，删去该结点与其他孩子结点的连线，再以根结点为轴心，顺时针旋转,45,。,，即得相应的二叉树。,在树所对应的二叉树中，一个结点的左孩子是它原来在树里的第一个孩子，右孩子是它在原来树里的下一个兄弟。,树的二叉树表示,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,A,B,C,E,F,G,D,H,I,J,顺时针旋转,45,。,长兄左链父,弟弟右链兄,兄弟依次手拉手,遍历：,是按一定的次序，系统地访问该结构中的所有结点，使每个结点恰被访问一次。,二叉树的遍历（周游）,1,、,前序遍历二叉树算法,(NLR),访问根结点；,前序遍历左子树；,前序遍历右子树。,（根,左,右）,对于上图使用前序遍历，则处理顺序为：,ABEFCGDHIJ,。,A,B,C,E,F,G,D,H,I,J,2,、中序遍历二叉树的算法,(LNR),若二叉树不空，则依次进行下列操作：,中序遍历左子树；,访问根结点；,中序遍历右子树。,（左,根,右）,A,B,C,E,F,G,D,H,I,J,对于上图，使用中序遍历，则处理顺序为：,EFBGCHIJDA,。,3,、后序遍历二叉树的算法（,LRN,）,若二叉树不空，则依次进行下列操作：,后序遍历左子树；,后序遍历右子树；,访问非根结点。,（左,右,根）,A,B,C,E,F,G,D,H,I,J,对于上图，使用后序遍历，则处理顺序为：,FEGJIHDCBA,。,图,图的相关概念,通常用,G=,（,V,，,E,）,代表一个图，图中的,结点又称为顶点,，,V,是结点的有穷集合（非空），,相关的结点偶对称为边（或弧）,，,E,是边的有穷集合（,E,可为空集，对应的图中只有顶点,没有边）。,1,、无向图,：,图中代表一条边的结点偶对如果是无序的，则称此图为无向图。,2,、有向图,：,图中代表一条边的结点偶对如果是有序的，则称此图为有向图。,V,1,V,2,V,3,V,4,出度,入度,（出度为,0,）,“终端结点”,n,个顶点的无向图边的最大数目是,n,（,n-1,）,/2,。,n,个顶点的有向图边的最大数目为,n,2,3,、相邻结点,：,若（,V,1,，,V,2,）,E,，,则称,V,1,和,V,2,是相邻结点。边（,V,1,，,V,2,）是,V,1,和,V,2,相关联的边。,4,、度,：,一个结点的度是与该结点相关联的边的数目。,（,1,）入度,：,对于有向图，则把以结点,V,i,，,为终点的边的数目称为结点,V,i,的入度；,（,2,）出度,：,把以,V,i,为始点的边的数目称为,V,i,的。,（,3,）终端结点,：,出度为,0,的结点称为终端结点。,5,、路径,：,在图,G,（,V,，,E,）,中，若（,V,p,，,V,i1,）、（,V,i1,，,V,i2,）,、,、（,V,in,，,V,g,）,都在,E,中，则称结点序列,V,p,、,V,i1,、,V,i2,、,、,V,in,、,V,g,为从结点,V,p,到结点,V,g,的一条路径。,（,1,）路径的长度,：,即路径上边的数目。,（,2,）简单路径,：,如果一条路径上的结点除,V,p,，和,V,g,可以相同外，其他结点都不相同，则称此路径为一简单路径。,（,3,）回路：,V,p,=V,g,的简单路径称为回路（或环）。,6,、连通,：,在无向图,G,（,V,，,E,）,中，如果从,V,1,到,V,2,有一条路径（相应的从,V,2,到,V,1,也一定有一条路径），则称,V,l,和,V,2,是连通的。若图中任意两个结点,V,i,和,V,j,（,V,i,V,j,），,都是连通的，则称无向图,G,是连通的。,7,、强连通,：,在有向图中，若对于任意两个结点,V,i,和,V,j,（,V,i,V,j,），,都有一条从,V,i,到,V,j,的路径，同时还有一条从,V,j,到,V,i,的路径，则称有向图是强连通的。,1,、图的相邻矩阵表示法,相邻矩阵是表示结点间的相邻关系的矩阵，若,G,是一个具有,n,个结点的图，则,G,的相邻矩阵是如下定义的,nn,矩阵。,1,，若（,Vi,，,Vj,）,是图,G,的边,Ai,，,j=,0,，,若（,Vi,，,Vj,）,不是图,G,的边,V,1,V,2,V,3,V,4,G,1,图,G,1,的相邻矩阵为：,0 1 1 1,A1=1 0 1 1,1 1 0 0,1 0 0 0,图的存储,V,1,V,5,V,4,G,2,V,3,V,2,V,1,V,2,V,3,V,4,网络,V,5,5,2,6,8,3,4,11,10,图,G,2,的相邻矩阵为：,0 1 0 0 0,1 0 0 0 1,A2=0 1 0 1 0,1 0 0 0 0,0 0 0 1 0,网络图,的相邻矩阵为：,0 3 5 8 0,3 0 6 4 11,A=4 6 0 2 0,8 4 2 0 10,0 11 0 10 0,2,、图的邻接表表示法,用邻接表法表示图需要一个顺序存储的,结点表,和,n,个链接存储的,边表,。,（,1,）,结点表的每个表目对应图的一个结点。每个表目包括,两个字段,：,一个是结点的数据或指向结点数据的指针,；,另一个是指向此结点的边表的指针,。,（,2,）,图的每个结点都有一个边表，一个结点的边表的每个表目对应于该结点相关联的一条边。每个表目包括,两个字段,：,一个是与此边相关联的另一个结点在结点表中的序号,；,另一个是指向边表的下一个表目的指针,。,V,1,V,2,V,3,V,4,1,2,3,4,结点表,2,1,1,1,3,3,2,3,4,4,V,1,V,3,V,2,V,4,G,1,另一相关结点的序号,无向图,G,l,用邻接表法表示如下：,边表,1,、深度优先遍历,基本思想,：从图中某个,V,出发，首先访问此结点，然后依次从,V,的未被访问的邻接结点出发进行深度优先遍历，直至图中所有和,V,有路径相通的结点均被访问到。若此时图中尚有结点未被访问，则另选图中一个未被访问的结点作始点，重复上述过程，直至图中所有结点都被访问到为止。,遍历,1,2,3,4,5,6,7,8,上图，按深度优先遍历的访问次序为：,1-2-4-8-5-3-6-7,。,2,、广度优先遍历,基本思想,：,从某个结点,V,出发，首先访问此结点，然后依次访问,V,邻接的未被访问的结点，然后再分别从这些结点出发进行广度优先遍历，直至图中所有被访问过的结点的相邻结点都被访问到。若此时图中尚有结点未被访问，则另选图中一个未曾访问的结点作始点，重复上述过程，直至图中所有结点都被访问到为止。,上图，按广度优先遍历的访问次序为：,1-2-3-4-5-6-7-8,