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

1、第八章 数据结构,数据结构概要 1.数据结构定义： 指数据元素的集合及元素之间的关系和构造方法，可以用二元组表示为：b=（a，r），其中a是数据元素的非空有限集合，r是定义在a上的关系的非空有限集合。 2.要达到的目标： (1)从问题入手，分析和研究数据结构的特性，选择适当的逻辑结构、存储结构及相应的操作方法。 (2)并掌握时间复杂度和空间复杂度的概念。 3. 按逻辑关系分类 线性结构(包括线性表、栈、队列、数组、串等) 非线性结构(树、图),第一部分：线性结构,一、线性表 最常见的一种线性结构，有两种存储方法：顺序存储和链式存储 1、定义： n个元素的有限序列，n0，通常表示为（a1,a2,

2、an） 2、特点： 元素集合中存在唯一称作“第一个”和唯一“最后一个”元素，除第一个元素外，每个元素均只有一个直接前驱；除最后一个元素外，序列中的每个元素只有一个直接后继。 3、存储结构： 顺序存储结构 含义：用一组连续的存储单元存放线性表中的数据元素。 特点：逻辑相邻的元素，物理位置也相邻。 优点和缺点：存取方便，插入删除操作需要移动大量元素。,第一部分：线性结构,. 链式存储结构 含义： 存储数据元素的同时必须存储元素之间的关系。用节点来存储数据元素，节点地址可以连续，也可以不连续。 节点结构： 节点的插入和删除操作 插入操作 删除操作,第一部分：线性结构,4.其他几种链表结构： 双向链表

3、： 每个节点包含两个指针，分别指出当前节点元素的直接前驱和直接后继。 循环链表： 静态链表： 借助数组来描述线性表的链式存储结构,第一部分：线性结构,二、栈和队列 1. 栈 定义 只能通过它的一端来实现数据存储和检索的 线性结构，也称为后进先出（或先进后出）的 线性表。 基本运算 初始化栈：initstack(s) 判栈空: stackempty 入栈:push(s,x) 出栈:pop(s) 读栈顶元素:top(s) 存储结构 顺序存储：（顺序栈）指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针top指示栈顶元素的位置。,第一部分：线性结构,链式存储（链栈）：为了克服 顺

4、序栈可能存在上溢的不足，采 用钻链表作为存储结构的栈。 栈的应用：表达式求值，括号匹配，递归转非递归。 2. 队列 定义：是一种先进先出（fifo）的线性表，只允许在表的一端插入元素，表的另一端删除元素。 基本运算： (1)初始化队 initqueue(q) (2)判队空 empty(q) (3)入队 enqueue(q,x) (4)出队 dequeue(q) (5)读队头元素 frontque(q),第一部分：线性结构,队列的存储结构 顺序存储（顺序队列） 利用一组地址连续的存储单元存放队列中的元素，同时设置队头指针和队尾 指针，分别表示当前的队首元素和队尾元素。 思考:(1)为什么要引入循

5、环队列？ (2)什么叫假溢出？如何形成的？ 链式存储（链队列） 队列的应用： 常用于需要排队的场合：比如操作系统中处理打印任务，离散事件的计算模拟等。,第一部分：线性结构,3 串 即字符串，是一种特殊的线性表，它的数据元素仅由一个字符组成。 串的定义 是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为： s=a1a2an，其中s是串名，单引号括起来的字符序列是串值。 几个相关的基本概念 空串：长度为零的串，不包含任何字符。 空格串：由一个或多个空格组成的串。 子串：由串中任意长度的连续字符构成的序列称为子串。空串是任意串的子串。 串相等：两个串长度相等，且对应位置上的字符也相同。 串比

6、较：比较大小时，以ascii码值作为依据。 基本操作 赋值strassign(s,t): 将串t赋给串s 连接concat(s,t) : 串t接续在串s的尾部，形成一个新串。,第一部分：线性结构,求串长strlength(s) 串比较strcompare(s,t) 返回值-1、0、1分别表示st 求子串substring(s,start,len) 串的存储结构 静态存储(即串的顺序存储结构) 用一组地址连续的存储单元来存储串值的字符序列。（在程序设计语言中可借助字符数组定义串的存储空间）。 链式存储 用链表存储串中的字符，每个节点中可以存储一个字符，也可以存储多个字符，注意存储密度问题,因为它

7、直接影响到串和处理效率。 串的模式匹配 即子串的定位操作，是各种串处理中最重要的运算之一。有以下两种算法： （1）朴素模式匹配算法 基本思想：p432 （2）改进的模式匹配算法 基本思想：p433,第一部分：线性结构,4 数组、矩阵和广义表 （1）数组 定义：线性表的元素又是一个线性表，是定长线性表在维数上的一个扩张。 特点： .数据元素数目固定 .数据元素具有相同数据类型 .数据元素的下标关系具有上下界的约束且下标有序 两个基本运算 其一：给定一组下标，存取相应的数据元素； 其二：给定一组下标，修改相应的数据元素中某个数据项的值。 存储结构 由于数组一般不作插入和删除运算，所以数组中数据元素

8、个数和元素之间的 关系固定不变，因此适合采用顺序存储结构。 .二维数组的存储方式有两种： 行优先： 列优先：,第一部分：线性结构,（2）矩阵 在数据结构中，我们研究的是如何存储矩阵中的元素。 特殊矩阵 指矩阵中的元素分布有一定的规律的矩阵。例如：对称矩阵、三角矩阵、对 角矩阵。 存储时，可以将其压缩存储在一维数组中，并建立起每个非零元素在矩阵中的位置与其 一维护数组中的位置之间的对应关系。 稀疏矩阵 非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律。,第一部分：线性结构,5 广义表 定义 是线性表的推广一，由零个或多个单元素或子表所组成的有限序列。一般记为： ls=（a1,a2,a

9、n）其中ai(1=i=n) 注意与线性表的区别： 基本操作 取表头：head(ls) 取表尾: tail(ls) 特点： 多层次结构，即广义表的元素可以是子表 广义表的元素可以是已经定义好的广义表 是一个递归的表，即广义表的元素可是本广义表的名字 存储结构 通常采用链式存储结构：有两种方法，即同层结点法，表头表尾法,第二部分 非线性结构,一、树 （一）树的定义及运算 1、树的定义 树是n（n=0）个节点的有限集合，当n=0时，称为空树，在任一非空树中： （1）有且仅有一个称为根的节点； （2）其余节点可分为m (m=0) 个互不相交的有限集t1、t2、 、tm,其中ti又都是一棵树， 并且乐为

10、根节点的子树。 （递归定义） 2、树的基本概念 与树相关的概念有： 双亲、孩子、兄弟 节点的度、叶子节点、节点的层次、树的高度、有序（无序）树 3、树的遍历 按照某种次序，获取树中全部节点的信息。,第二部分 非线性结构,（二）二叉树的定义及基本运算、 1、二叉树的定义： 二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、 互不交的二叉树组成。 2、二叉树的运算 二叉树的基本运算是遍历，其它运算都是建立在遍历的基础之上。,第二部分 非线性结构,（三）二叉树的性质（共五个性质） 1、在二叉树的第 i 层上至多有2i-1 个结点。 (i1) 2、深度为 k 的二叉树上至多含 2k-1

11、 个结点（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) 若

12、2in，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。,第二部分 非线性结构,(四) 二叉树的存储结构 1、顺序存储结构 (1) 存储要求： 用一组地址连续的存储单元存储二叉树中的数据元素，节点必须排 成线性序列，并且该序列能反映出节点之间的逻辑关系。 (2) 完全二叉树的存储 完全二叉树的存储 一般二叉树的存储 二者比较得知：对于一般的二叉树，不宜采用顺序存储结构，对于完全 二叉树，采用顺序存储结构既简单，又节省空间,第二部分 非线性结构,2、链式存储结构 可以采用二叉链表或三叉链表来

13、存储二叉树。,第二部分 非线性结构,(五)二叉树的遍历 1、遍历的含义： 指按照某种策略访问树中的每个节点，且仅访问一次。遍历过程的实质是：将树中的节点排成一个线性序列的过程。 2、常见几种遍历： 先序遍历算法 若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 void preorder(bitree root) if(root!=null) return ; elseprintf(“%d”,root-data); preorder(root-lchild); preorder(roolt-rchild); ,第二部分 非线性结构,中序遍历算

14、法： 若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树 void inorder(bitree root) if(root=null) return ; else inorder(root-lchild); printf(“%d”,root-data); inorder(root-rchild); ,第二部分 非线性结构,后序遍历算法： 若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 void postorder(bitree root) if(root=null ) return ; el

15、se postorder(root-lchild); postorder(root-rchild); printf(“%d”,root-data); ,第二部分 非线性结构,层次遍历算法： 从树的根结点出发，首先访问第一层的树的根结点，然后从左到右依次访问 第二层上的节点，其次是第三层上的节点依次类推，自上而下，自左至 右，逐层访问树中各层上的节点。 层次遍历序列： a b e c f d g h k,第二部分 非线性结构,(六) 线索二叉树 1、定义 二叉树的遍历实质：对非线性结构进行线性化操作，使得每个结点 （除第一个和最后一个结点外）在线性序列中有且仅有一个直接前驱和 直接后继。 由于二

16、叉链表的存储结构中，只能找到结点的左、右孩子的信息， 得不到前驱和后继信息，因此引入线索二叉树保存遍历过程中得到的 前驱和后继信息。 2、建立线索二叉树,第二部分 非线性结构,第二部分 非线性结构,对线索链表中结点的约定： 在二叉链表的结点中增加两个标志域，并作如下规定： 若该结点的左子树不空，则lchild域的指针指向其左子树，且左标志域的值为“指针 link”； 否则,lchild域的指针指向其“前驱”，且左标志的值为“线索tread” 。 若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志 域的值为 “指针 link”； 否则，rchild域的指针指向其“后继”，且右标志

17、的值为“线索 thread”。 如此定义的二叉树的存储结构称作“线索链表”,第二部分 非线性结构,思考：画出下列二叉树的中序线索二叉树及其中序线索链表。,第二部分 非线性结构,(七) 二叉树的应用：最优二叉树 1. 哈夫曼树 （1）相关概念： 结点的路径长度：从根结点到该结点的路径上分支的数目。 树的路径长度： 树中每个结点的路径长度之和。 树的带权路径长度定义为： 树中所有叶子结点的带权路径长度之和 wpl(t) = wklk,wpl(t)= 72+52+23+43+92 =60,第二部分 非线性结构,(2)如何构造最优二叉树（huffuman算法） 根据给定的 n 个权值 w1, w2,

18、, 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 构造一棵哈夫曼树。 步骤如下：（右图为哈夫曼编码）,第二

19、部分 非线性结构,（八）树和森林 1、树的存储结构（三种表示方法） (1) 双亲表示法：,第二部分 非线性结构,(2) 孩子表示法,第二部分 非线性结构,（3）孩子兄弟表示法：,第二部分 非线性结构,2、树和林林的遍历 （1）树的遍历： 先根遍历 后根遍历 （2）森林的遍历 先序遍历 中序遍历 3、树、森林和二叉树之间的相互转换 （1）树、森林转换为二叉树 利用孩子兄弟法实现转换（p454例） （2）二叉树转换为树和森林（p454例）,第二部分 非线性结构,三、图 （一）图的定义 与图相关的概念有： 有向图/无向图： 无向完全图/有向完全图： 度、出度和入度： 路径：从一个顶点到另一个顶点的顶

20、点序列 子图： 连通图与连通分量： 强连通图与强连通分量： 网：带权值的图 有向树：有向图恰有一个顶点的入度为0，其余顶点的入度为1.,第二部分 非线性结构,(二) 图的存储结构 1、邻接矩阵表示法： 无向图邻接矩阵,第二部分 非线性结构,第二部分 非线性结构,2、邻接表表示法,第二部分 非线性结构,有向图逆邻接表 在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧。,第二部分 非线性结构,（三）图的遍历 1、深度优先（dfs） 遍历算法： 从图中某个顶点v0 出发，访问此顶点，然后依次从v0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v0有路径相通的顶点都被访问到。 例子

21、：,第二部分 非线性结构,2、广度优先遍历（bfs） 遍历算法： 从图中的某个顶点v0出发，并在访问此顶点之后依次访问v0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和v0有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,第二部分 非线性结构,(四) 生成树及最小生成树 1、生成树的概念 一个连通图的生成树是一个极小连通子图，它包含图中的全部顶点，但只有构成一棵树的n-1条边。 按深度和广度优先搜索可以分别得到不同的生成树，分别称为深度优先生成树和广度优先生成树。 上面图的深度优先生成树和广度优先生成树分别如下：,第二部分 非线性结构,深度优先生成树 广度优先生成树,第二部分 非线性结构,2、最小生成树 由于生成树不唯一，从不同顶点出发可得到不同的生成树，因此如何求解最小生成树有许多实际应用价值。 常见的最小生成树算法有两种：、 （1）普里姆算法（prim） 基本思想： 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成