数据结构(线性表、树、图)

第八章数据结构,数据结构概要1.数据结构定义：指数据元素的集合及元素之间的关系和构造方法，可以用二元组表示为：B=（A，R），其中A是数据元素的非空有限集合，R是定义在A上的关系的非空有限集合。2.要达到的目标：(1)从问题入手，分析和研究数据结构的特性，选择适当的逻辑结构、存储结构及相应的操作方法。(2)并掌握时间复杂度和空间复杂度的概念。3.按逻辑关系分类线性结构(包括线性表、栈、队列、数组、串等)非线性结构(树、图),第一部分：线性结构,一、线性表最常见的一种线性结构，有两种存储方法：顺序存储和链式存储1、定义：N个元素的有限序列，n0，通常表示为（a1,a2,an）2、特点：元素集合中存在唯一称作“第一个”和唯一“最后一个”元素，除第一个元素外，每个元素均只有一个直接前驱；除最后一个元素外，序列中的每个元素只有一个直接后继。3、存储结构：顺序存储结构含义：用一组连续的存储单元存放线性表中的数据元素。特点：逻辑相邻的元素，物理位置也相邻。优点和缺点：存取方便，插入删除操作需要移动大量元素。,第一部分：线性结构,.链式存储结构含义：存储数据元素的同时必须存储元素之间的关系。用节点来存储数据元素，节点地址可以连续，也可以不连续。节点结构：节点的插入和删除操作插入操作删除操作,第一部分：线性结构,4.其他几种链表结构：双向链表：每个节点包含两个指针，分别指出当前节点元素的直接前驱和直接后继。循环链表：静态链表：借助数组来描述线性表的链式存储结构,第一部分：线性结构,二、栈和队列1.栈定义只能通过它的一端来实现数据存储和检索的线性结构，也称为后进先出（或先进后出）的线性表。基本运算初始化栈：InitStack(S)判栈空:StackEmpty入栈:Push(S,x)出栈:Pop(S)读栈顶元素:Top(s)存储结构顺序存储：（顺序栈）指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针top指示栈顶元素的位置。,第一部分：线性结构,链式存储（链栈）：为了克服顺序栈可能存在上溢的不足，采用钻链表作为存储结构的栈。栈的应用：表达式求值，括号匹配，递归转非递归。2.队列定义：是一种先进先出（FIFO）的线性表，只允许在表的一端插入元素，表的另一端删除元素。基本运算：(1)初始化队InitQueue(Q)(2)判队空Empty(Q)(3)入队EnQueue(Q,x)(4)出队DeQueue(Q)(5)读队头元素FrontQue(Q),第一部分：线性结构,队列的存储结构顺序存储（顺序队列）利用一组地址连续的存储单元存放队列中的元素，同时设置队头指针和队尾指针，分别表示当前的队首元素和队尾元素。思考:(1)为什么要引入循环队列？(2)什么叫假溢出？如何形成的？链式存储（链队列）队列的应用：常用于需要排队的场合：比如操作系统中处理打印任务，离散事件的计算模拟等。,第一部分：线性结构,3串即字符串，是一种特殊的线性表，它的数据元素仅由一个字符组成。串的定义是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为：S=a1a2an，其中S是串名，单引号括起来的字符序列是串值。几个相关的基本概念空串：长度为零的串，不包含任何字符。空格串：由一个或多个空格组成的串。子串：由串中任意长度的连续字符构成的序列称为子串。空串是任意串的子串。串相等：两个串长度相等，且对应位置上的字符也相同。串比较：比较大小时，以ASCII码值作为依据。基本操作赋值strAssign(s,t):将串t赋给串s连接Concat(s,t):串t接续在串s的尾部，形成一个新串。,第一部分：线性结构,求串长StrLength(s)串比较StrCompare(s,t)返回值-1、0、1分别表示st求子串SubString(s,start,len)串的存储结构静态存储(即串的顺序存储结构)用一组地址连续的存储单元来存储串值的字符序列。（在程序设计语言中可借助字符数组定义串的存储空间）。链式存储用链表存储串中的字符，每个节点中可以存储一个字符，也可以存储多个字符，注意存储密度问题,因为它直接影响到串和处理效率。串的模式匹配即子串的定位操作，是各种串处理中最重要的运算之一。有以下两种算法：（1）朴素模式匹配算法基本思想：P432（2）改进的模式匹配算法基本思想：P433,第一部分：线性结构,4数组、矩阵和广义表（1）数组定义：线性表的元素又是一个线性表，是定长线性表在维数上的一个扩张。特点：.数据元素数目固定.数据元素具有相同数据类型.数据元素的下标关系具有上下界的约束且下标有序两个基本运算其一：给定一组下标，存取相应的数据元素；其二：给定一组下标，修改相应的数据元素中某个数据项的值。存储结构由于数组一般不作插入和删除运算，所以数组中数据元素个数和元素之间的关系固定不变，因此适合采用顺序存储结构。.二维数组的存储方式有两种：行优先：列优先：,第一部分：线性结构,（2）矩阵在数据结构中，我们研究的是如何存储矩阵中的元素。特殊矩阵指矩阵中的元素分布有一定的规律的矩阵。例如：对称矩阵、三角矩阵、对角矩阵。存储时，可以将其压缩存储在一维数组中，并建立起每个非零元素在矩阵中的位置与其一维护数组中的位置之间的对应关系。稀疏矩阵非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律。,第一部分：线性结构,5广义表定义是线性表的推广一，由零个或多个单元素或子表所组成的有限序列。一般记为：LS=（a1,a2,an）其中ai(1=0)个互不相交的有限集T1、T2、Tm,其中Ti又都是一棵树，并且乐为根节点的子树。（递归定义）2、树的基本概念与树相关的概念有：双亲、孩子、兄弟节点的度、叶子节点、节点的层次、树的高度、有序（无序）树3、树的遍历按照某种次序，获取树中全部节点的信息。,第二部分非线性结构,（二）二叉树的定义及基本运算、1、二叉树的定义：二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。2、二叉树的运算二叉树的基本运算是遍历，其它运算都是建立在遍历的基础之上。,第二部分非线性结构,（三）二叉树的性质（共五个性质）1、在二叉树的第i层上至多有2i-1个结点。(i1)2、深度为k的二叉树上至多含2k-1个结点（k1）3、对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。4、具有n个结点的完全二叉树的深度为log2n+1,第二部分非线性结构,5、若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：(1)若i=1，则该结点是二叉树的根，无双亲,否则，编号为i/2的结点为其双亲结点;(2)若2in，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若2i+1n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。,第二部分非线性结构,(四)二叉树的存储结构1、顺序存储结构(1)存储要求：用一组地址连续的存储单元存储二叉树中的数据元素，节点必须排成线性序列，并且该序列能反映出节点之间的逻辑关系。(2)完全二叉树的存储完全二叉树的存储一般二叉树的存储二者比较得知：对于一般的二叉树，不宜采用顺序存储结构，对于完全二叉树，采用顺序存储结构既简单，又节省空间,第二部分非线性结构,2、链式存储结构可以采用二叉链表或三叉链表来存储二叉树。,第二部分非线性结构,(五)二叉树的遍历1、遍历的含义：指按照某种策略访问树中的每个节点，且仅访问一次。遍历过程的实质是：将树中的节点排成一个线性序列的过程。2、常见几种遍历：先序遍历算法若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。voidPreOrder(BiTreeroot)if(root!=null)return;elseprintf(“%d”,root-data);PreOrder(root-lchild);PreOrder(roolt-rchild);,第二部分非线性结构,中序遍历算法：若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树voidInOrder(BiTreeroot)if(root=null)return;elseInOrder(root-lchild);printf(“%d”,root-data);InOrder(root-rchild);,第二部分非线性结构,后序遍历算法：若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。voidPostOrder(BiTreeroot)if(root=null)return;elsePostOrder(root-lchild);PostOrder(root-rchild);printf(“%d”,root-data);,第二部分非线性结构,层次遍历算法：从树的根结点出发，首先访问第一层的树的根结点，然后从左到右依次访问第二层上的节点，其次是第三层上的节点依次类推，自上而下，自左至右，逐层访问树中各层上的节点。层次遍历序列：ABECFDGHK,第二部分非线性结构,(六)线索二叉树1、定义二叉树的遍历实质：对非线性结构进行线性化操作，使得每个结点（除第一个和最后一个结点外）在线性序列中有且仅有一个直接前驱和直接后继。由于二叉链表的存储结构中，只能找到结点的左、右孩子的信息，得不到前驱和后继信息，因此引入线索二叉树保存遍历过程中得到的前驱和后继信息。2、建立线索二叉树,第二部分非线性结构,第二部分非线性结构,对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域的值为“指针Link”；否则,Lchild域的指针指向其“前驱”，且左标志的值为“线索Tread”。若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为“指针Link”；否则，rchild域的指针指向其“后继”，且右标志的值为“线索Thread”。如此定义的二叉树的存储结构称作“线索链表”,第二部分非线性结构,思考：画出下列二叉树的中序线索二叉树及其中序线索链表。,第二部分非线性结构,(七)二叉树的应用：最优二叉树1.哈夫曼树（1）相关概念：结点的路径长度：从根结点到该结点的路径上分支的数目。树的路径长度：树中每个结点的路径长度之和。树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和WPL(T)=WkLk,WPL(T)=72+52+23+43+92=60,第二部分非线性结构,(2)如何构造最优二叉树（Huffuman算法）根据给定的n个权值w1,w2,wn，构造n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树;在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;,WPL(T)=74+94+53+42+21=89,第二部分非线性结构,从F中删去这两棵树，同时加入刚生成的新树。重复(2)和(3)两步，直至F中只含一棵树为止。(3)举例：已知权值W=5,6,2,9,7构造一棵哈夫曼树。步骤如下：（右图为哈夫曼编码）,第二部分非线性结构,（八）树和森林1、树的存储结构（三种表示方法）(1)双亲表示法：,第二部分非线性结构,(2)孩子表示法,第二部分非线性结构,（3）孩子兄弟表示法：,第二部分非线性结构,2、树和林林的遍历（1）树的遍历：先根遍历后根遍历（2）森林的遍历先序遍历中序遍历3、树、森林和二叉树之间的相互转换（1）树、森林转换为二叉树利用孩子兄弟法实现转换（P454例）（2）二叉树转换为树和森林（P454例）,第二部分非线性结构,三、图（一）图的定义与图相关的概念有：有向图/无向图：无向完全图/有向完全图：度、出度和入度：路径：从一个顶点到另一个顶点的顶点序列子图：连通图与连通分量：强连通图与强连通分量：网：带权值的图有向树：有向图恰有一个顶点的入度为0，其余顶点的入度为1.,第二部分非线性结构,(二)图的存储结构1、邻接矩阵表示法：无向图邻接矩阵,第二部分非线性结构,第二部分非线性结构,2、邻接表表示法,第二部分非线性结构,有向图逆邻接表在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧。,第二部分非线性结构,（三）图的遍历1、深度优先（DFS）遍历算法：从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。例子：,第二部分非线性结构,2、广度优先遍历（BFS）遍历算法：从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,第二部分非线性结构,(四)生成树及最小生成树1、生成树的概念一个连通图的生成树是一个极小连通子图，它包含图中的全部顶点，但只有构成一棵树的n-1条边。按深度和广度优先搜索可以分别得到不同的生成树，分别称为深度优先生成树和广度优先生成树。上面图的深度优先生成树和广度优先生成树分别如下：,第二部分非线性结构,深度优先生成树广度优先生成树,第二部分非线性结构,2、最小生成树由于生成树不唯一，从不同顶点出发可得到不同的生成树，因此如何求解最小生成树有许多实际应用价值。常见的最小生成树算法有两种：、（1）普里姆算法（Prim）基本思想：取图中任意一个顶点v作为生成树的根，之后往生成树上添加新的顶点w。在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n-1个顶点为止。,第二部