第6章 数据结构

1、第第6 6章章 数据结构数据结构第第6章章 数据结构数据结构6.1 概念和术语概念和术语 （掌握（掌握)6.2 线性结构（掌握）线性结构（掌握）6.3 树形结构（了解）树形结构（了解）6.4 图状结构（了解）图状结构（了解）6.5 文件（了解）文件（了解）第第6章章 数据结构数据结构v重点：重点：基本概念和术语基本概念和术语线性结构线性结构v难点：难点：数据存储结构数据存储结构6.1 概念和术语概念和术语数据处理：数据处理：数据：数据：数值数据数值数据和和非数值数据非数值数据（字符串、图像、音频、视频（字符串、图像、音频、视频等）；等）；处理：处理：既可以是既可以是算术运算算术运算，也可以是，

2、也可以是插入、删除、查找和排序插入、删除、查找和排序 等操作。等操作。n 数据结构要解决的问题：数据结构要解决的问题：编写程序时：编写程序时：面对的是面对的是逻辑结构逻辑结构（数据的一种抽象表示，更符（数据的一种抽象表示，更符 合人们习惯）；合人们习惯）；程序执行时：程序执行时：由支持相应结构的编译程序自动把逻辑结构映射由支持相应结构的编译程序自动把逻辑结构映射 成成物理结构物理结构，从而简化程序的编写，减轻编程，从而简化程序的编写，减轻编程 人员的工作量。人员的工作量。数据结构讨论数据结构讨论描述现实世界实体的数学模型及其上的操作在描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现

3、。计算机中的表示和实现。6.1 概念和术语概念和术语v数据数据信息的载体信息的载体，所有能被输入到计算机中且被计算机处理所有能被输入到计算机中且被计算机处理的符号的集合的符号的集合。可以是数值数据，也可以是非数值数据。可以是数值数据，也可以是非数值数据。例如：例如：图像、声音、文本等。图像、声音、文本等。v数据元素数据元素数据的基本单位数据的基本单位，具有完整、确定的实际意义，在计算，具有完整、确定的实际意义，在计算机中通常作为一个整体考虑。一般由若干机中通常作为一个整体考虑。一般由若干数据项数据项组成。组成。 例如：例如：张三的基本情况张三的基本情况学号、姓名、性别、年龄等。学号、姓名、性别

4、、年龄等。v数据项数据项数据不可分割的最小单位数据不可分割的最小单位。分为。分为数据项名数据项名和和数据项值数据项值。 例如：例如：年龄（数据项名）年龄（数据项名）19、20（数据项值）（数据项值）6.1 概念和术语概念和术语v数据对象（数据元素类）数据对象（数据元素类）性质相同的数据元素的集合，是数据的一个子集性质相同的数据元素的集合，是数据的一个子集。 在某个具体问题中，数据元素都具有相同的性质，属于在某个具体问题中，数据元素都具有相同的性质，属于 同一数据对象，数据元素是数据元素类的一个实例。同一数据对象，数据元素是数据元素类的一个实例。 例如：例如：学生管理系统学生管理系统某大学学生的

5、基本情况某大学学生的基本情况（数据）（数据） 本科生的基本情况本科生的基本情况（数据对象）（数据对象） 某本科生张三的基本情况（某本科生张三的基本情况（数据元素数据元素）又比如：又比如：字符集字符集A,B,CA,B,Cv数据结构数据结构互相之间存在着一种或多种关系的数据元素的集合。互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素不是孤立的，它们之间存在着在任何问题中，数据元素不是孤立的，它们之间存在着这样和那样的关系，这种数据之间的关系称为结构。这样和那样的关系，这种数据之间的关系称为结构。6.1 概念和术语概念和术语v数据结构数据结构包括数据的包括数据的逻辑结构逻辑结构和

6、数据的和数据的物理结构物理结构。v1 1、数据的逻辑结构、数据的逻辑结构从具体问题抽象出来的从具体问题抽象出来的数学模型数学模型，描述的是，描述的是数据元素之数据元素之间的逻辑关系间的逻辑关系。即即数据的组织形式数据的组织形式。不涉及数据元素在。不涉及数据元素在计算机中具体的存储方式。计算机中具体的存储方式。v2 2、数据的物理结构（存储结构）、数据的物理结构（存储结构）数据在计算机中的表示，研究数据在计算机中的表示，研究数据结构在计算机中的实数据结构在计算机中的实现方法现方法，包括数据结构中元素的表示及数据元素间关系，包括数据结构中元素的表示及数据元素间关系的表示。的表示。6.1 概念和术语

7、概念和术语v1 1、数据的逻辑结构、数据的逻辑结构v数据元素间的逻辑结构有数据元素间的逻辑结构有四种基本类型：四种基本类型：v1）集合：）集合：数据元素除了数据元素除了“同属于一个集合同属于一个集合”外，没有其外，没有其他关系。他关系。v2）线性结构）线性结构数据元素之间存在着数据元素之间存在着一对一的关系一对一的关系，例如，例如线性表、栈、线性表、栈、队列队列等。等。例如：例如：按学号排列的学生数据。按学号排列的学生数据。6.1 概念和术语概念和术语v3）树形结构）树形结构数据元素之间存在着数据元素之间存在着一对多的关系一对多的关系，例如树、二，例如树、二叉树和森林等。例如：一个单位的工作人

8、员之间叉树和森林等。例如：一个单位的工作人员之间的关系。的关系。6.1 概念和术语概念和术语v4）图状结构）图状结构数据元素之间存在着数据元素之间存在着多对多的关系多对多的关系，也称，也称网状结构网状结构，如，如无向图和有向图无向图和有向图等。等。例如：例如：高速公路交通图。高速公路交通图。6.1 概念和术语概念和术语v2、数据的物理结构、数据的物理结构(存储结构存储结构)v数据的物理结构数据的物理结构可以采用可以采用顺序存储顺序存储或者或者链式存储。链式存储。v1）顺序存储）顺序存储逻辑上相邻的元素逻辑上相邻的元素存储存储在物理位置也相邻在物理位置也相邻的存储单元中。的存储单元中。 常借助于

9、常借助于程序设计语言中的程序设计语言中的数组数组来实现来实现。v2）链式存储）链式存储逻辑上相邻的元素不要求其物理位置相邻逻辑上相邻的元素不要求其物理位置相邻，元素间的逻，元素间的逻辑关系通过附设的辑关系通过附设的指针指针字段来表示。字段来表示。常借助于常借助于程序设计程序设计语言中的语言中的指针指针来实现。来实现。6.1 概念和术语概念和术语v 顺序存储：顺序存储：数据元素的存储地址是连续的数据元素的存储地址是连续的v 链式存储链式存储:数据元素的存储地址不要求是连续的。数据元素的存储地址不要求是连续的。有相邻的数据元素有相邻的数据元素a和和b，分别采用顺序和链式存储如下，分别采用顺序和链式

10、存储如下图所示：图所示：abba&b顺序存储顺序存储链式存储链式存储6.2 线性结构线性结构v 线性结构的特点：在线性结构的特点：在非空非空有限集上有限集上 只有一个首结点和一个尾结点。只有一个首结点和一个尾结点。 每个每个元素元素有且只有一个有且只有一个直接直接前驱（第一个前驱（第一个元素元素除外）除外）。 每个每个元素元素有且只有一个有且只有一个直接直接后继（最后一个后继（最后一个元元素素除外）。除外）。 数据元素之间存在着一对一的关系数据元素之间存在着一对一的关系。v 常见线性结构：常见线性结构： 线性表线性表 栈栈 队列队列6.2.1 线性表线性表v1、线性表、线性表(Line

11、ar List) ：是由是由n(n0)个数据元素个数据元素(结点结点)a1，a2， an组成组成的的有限序列有限序列。该序列中的所有结点具有。该序列中的所有结点具有相同的数相同的数据类型据类型。其中数据元素的个数。其中数据元素的个数n称为称为线性表的长线性表的长度度。当当n=0时，称为时，称为空表空表。当当n0时，将非空的线性表记作：时，将非空的线性表记作：(a1，a2，an)6.2.1 线性表线性表v1、线性表、线性表(Linear List) ：a a1 1称为线性表的称为线性表的首结点首结点，a an n称为称为线性表线性表尾结点尾结点。a a1 1，a a2 2，aai-1i-1都是都

12、是a ai i(2(2i in)n)的的前驱前驱，其中其中a ai-1i-1是是a ai i的的直接前驱直接前驱；a ai+1i+1，a ai+2i+2，aan n都是都是a ai i(1(1i in-1)n-1)的的后继后继，其中其中a ai+1i+1是是a ai i的的直接后继直接后继。6.2.1 线性表线性表v2、线性表的顺序存储、线性表的顺序存储线性表的顺序存储是指用一组线性表的顺序存储是指用一组地址连续地址连续的存储单的存储单元元依次依次存储线性表中的各个元素。使得存储线性表中的各个元素。使得逻辑结构逻辑结构上相邻的数据元素存储在相邻的物理存储单元上相邻的数据元素存储在相邻的物理存储

13、单元。采用顺序存储结构的线性表通常称为采用顺序存储结构的线性表通常称为顺序表顺序表。高级语言中采用数组来表示线性表的顺序存储。高级语言中采用数组来表示线性表的顺序存储。6.2.1 线性表线性表v2、线性表的顺序存储、线性表的顺序存储v（1）顺序表的存储结构）顺序表的存储结构假设线性表中的第一个数据假设线性表中的第一个数据元素的存储地址为：元素的存储地址为：LOC（b1），每一个数据元），每一个数据元素占素占m个字节，则线性表中个字节，则线性表中第第i个元素个元素bi在计算机存储空在计算机存储空间中的存储地址为：间中的存储地址为：LOC (bi) = LOC (b1) + (i-1)m 6.2.

14、1 线性表线性表v2、线性表的顺序存储、线性表的顺序存储v（2）顺序表的插入操作）顺序表的插入操作要在第要在第i（1in）个元素之前插入一个新元素时）个元素之前插入一个新元素时，首先要将第，首先要将第i个到第个到第n个元素依次后移一位，然个元素依次后移一位，然后将新元素插入到第后将新元素插入到第i项。插入结束后，线性表的项。插入结束后，线性表的长度就增加了长度就增加了1。6.2.1 线性表线性表v2、线性表的顺序存储、线性表的顺序存储v（3）顺序表的删除操作）顺序表的删除操作要删除第要删除第i（1in）个元素时，则要从第）个元素时，则要从第i + 1个个元素开始，直到第元素开始，直到第n个元素

15、之间共个元素之间共ni个元素依次个元素依次向前移动一个位置。删除结束后，线性表的长度向前移动一个位置。删除结束后，线性表的长度就减小了就减小了1。6.2.1 线性表线性表v2、线性表的顺序存储、线性表的顺序存储v顺序存储的特点：顺序存储的特点：无需为表示结点间的逻辑关系而增加额外的存储无需为表示结点间的逻辑关系而增加额外的存储空间空间 。顺序存储使线性表具有顺序存储使线性表具有随机访问随机访问的特点。的特点。进行插入、删除操作时需大量移动数据元素，效进行插入、删除操作时需大量移动数据元素，效率较低率较低 。6.2.1 线性表线性表v3、线性表的链式存储、线性表的链式存储线性表的链表存储可用线性

16、表的链表存储可用连续或不连续连续或不连续的存储单元的存储单元来存储线性表中的元素，但是元素之间的逻辑关来存储线性表中的元素，但是元素之间的逻辑关系需要用系需要用“指针指针”来指示来指示。分配给每个结点的存储单元一般分为两个域：分配给每个结点的存储单元一般分为两个域：n一个域用来存储数据元素的信息，称为一个域用来存储数据元素的信息，称为数据域数据域 ；n另一个域用来存储直接后继结点的地址，称为指针域另一个域用来存储直接后继结点的地址，称为指针域。 6.2.1 线性表线性表v3、线性表的链式存储、线性表的链式存储v（1）在线性链表中查找指定的元素）在线性链表中查找指定的元素在非空线性链表中寻找包含

17、元素值在非空线性链表中寻找包含元素值x的结点的结点 ：从头指针指向的结点开始向后沿指针进行扫描，从头指针指向的结点开始向后沿指针进行扫描，直到后面已经没有结点或下一个结点的数据域为直到后面已经没有结点或下一个结点的数据域为x为止。为止。6.2.1 线性表线性表v3、线性表的链式存储、线性表的链式存储v（2）线性链表的插入操作）线性链表的插入操作v（3）线性链表的删除操作）线性链表的删除操作6.2.1 线性表线性表v3、线性表的链式存储、线性表的链式存储v链式存储的特点：链式存储的特点：由于增加了结点的指针域，空间开销比较大由于增加了结点的指针域，空间开销比较大 。链表失去了数组随机读取的优点链

18、表失去了数组随机读取的优点 。进行插入、删除操作时进行插入、删除操作时不需不需大量移动数据元素，大量移动数据元素，效率较高。效率较高。6.2.2 栈（栈（Stack）v1、栈的定义、栈的定义栈实际上是一种特殊的线性表。在限定栈实际上是一种特殊的线性表。在限定仅在表尾仅在表尾一端进一端进行插入或删除操作的线性表。行插入或删除操作的线性表。先进后出先进后出（Fist In Last Out，缩写为，缩写为FILO）栈顶栈顶:允许插入删除的一端称为栈顶。另一端称为栈底。允许插入删除的一端称为栈顶。另一端称为栈底。 顺序存储顺序存储链式存储链式存储a1a2aian bottomtop进栈（进栈（pus

19、h）出栈出栈(pop)6.2.2 栈（栈（Stack）v2、顺序栈进栈和出栈操作、顺序栈进栈和出栈操作 6.2.3 队列队列(Queue)v队列的定义队列的定义队列是另一种限定性的线性表，它只允许在表的队列是另一种限定性的线性表，它只允许在表的一端插一端插入元素入元素，而在，而在另一端删除元素另一端删除元素。队列具有队列具有先进先出先进先出FIFO (Fist In Fist Out)的特性。的特性。在队列中，允许插入的一端叫做队尾在队列中，允许插入的一端叫做队尾(rear)，允许删除的，允许删除的一端则称为队头一端则称为队头(front)。a1 , a2 , , an出队出队入队入队队尾队尾

20、队首队首6.3 树形结构树形结构v树形结构的特点树形结构的特点数据元素之间存在着数据元素之间存在着一对一对多多的关系的关系。非线性结构，每个元素有一个直接前驱，但可能有多个非线性结构，每个元素有一个直接前驱，但可能有多个直接后继直接后继v树形结构的应用树形结构的应用人类社会的族谱、各种社会机构的组织形式等具有明显人类社会的族谱、各种社会机构的组织形式等具有明显层次关系的结构。层次关系的结构。6.3.1 树的定义树的定义v1、树的定义、树的定义树是树是n（0）个结点的）个结点的有限集合有限集合。当。当n=0时，称为时，称为空树空树。 在一棵在一棵非空树非空树T T中：中：有一个特定的结点称为有一

21、个特定的结点称为树的根结点树的根结点；当当n1时，除根结点之外的其余结点被分成时，除根结点之外的其余结点被分成m（m1）个互不相交的集）个互不相交的集合合T1，T2，Tm，其中每一个集合，其中每一个集合Ti （1im）本身又是一棵树，并且称为）本身又是一棵树，并且称为根结点的子树根结点的子树。6.3.1 树的定义树的定义v2、树的基本术语、树的基本术语 结点：结点：一个数据元素及其若干指向其子树的分支。一个数据元素及其若干指向其子树的分支。结点的度：结点的度：结点所拥有的结点所拥有的子树的个数子树的个数称为结点的度。称为结点的度。树的度：树的度：树中结点度的树中结点度的最大值最大值。根结点：根

22、结点：即没有前驱的结点。即没有前驱的结点。叶子结点：叶子结点：树中度为树中度为0的结点，又称终端结点。的结点，又称终端结点。度不为度不为0的的结点称为非叶子结点结点称为非叶子结点6.3.1 树的定义树的定义孩子结点、双亲结点：孩子结点、双亲结点：一个结点的子树的根称为该结点的一个结点的子树的根称为该结点的孩子结点或子结点；相应地，该结点是其孩子结点的双孩子结点或子结点；相应地，该结点是其孩子结点的双亲结点或父结点亲结点或父结点。兄弟结点：兄弟结点：具有同一个父结点的子结点互称为兄弟结点。具有同一个父结点的子结点互称为兄弟结点。堂兄弟：堂兄弟：即双亲位于同一层的结点（但并非同一双亲）。即双亲位于

23、同一层的结点（但并非同一双亲）。祖先：祖先：即从根到该结点所经分支的所有结点。即从根到该结点所经分支的所有结点。子孙：子孙：即该结点下层子树中的任意结点。即该结点下层子树中的任意结点。6.3.1 树的定义树的定义结点的层数：结点的层数：从根到该结点的层数（从根到该结点的层数（根结点第一层根结点第一层）。）。树的深度：树的深度：指所有结点最大的层数（指所有结点最大的层数（Max各结点的层次各结点的层次）。）。树的度：树的度：所有结点度的最大值（所有结点度的最大值（Max各结点的度各结点的度）。）。想想这棵树的深度和度是多少？6.3.1 树的定义树的定义v 有序树：有序树：一棵树中结点的各子树一棵

24、树中结点的各子树从左到右是有次序从左到右是有次序的，即若的，即若交换了某结点各子树的相对位置，则构成不同的树，则称为交换了某结点各子树的相对位置，则构成不同的树，则称为有序树。有序树。v 无序树：无序树：反之，若结点各子树可互换位置，则称为无序树。反之，若结点各子树可互换位置，则称为无序树。v 森林：森林：零棵或有限棵不相交的树的集合成为森林。零棵或有限棵不相交的树的集合成为森林。BDIEHFCGJK6.3.2 二叉树二叉树1、二叉树的概念二叉树的概念二叉树：二叉树：有限个结点（有限个结点（n0）的集合，该集合或者为）的集合，该集合或者为空空、 或者由一个称为根的结点及两个不相交的、被分别称为

25、或者由一个称为根的结点及两个不相交的、被分别称为左子左子树树和和右子树右子树的二叉树组成。当集合为空时，称该二叉树为空的二叉树组成。当集合为空时，称该二叉树为空二叉树。二叉树。n 逻辑结构：逻辑结构： 一对二（一对二（1 1：2 2） n 基本特征基本特征: : 每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2 2的结点）；的结点）； 左子树和右子树次序不能颠倒（左子树和右子树次序不能颠倒（有序树有序树）。）。6.3.2 二叉树二叉树1、二叉树的概念二叉树的概念二叉树具有二叉树具有5种基本形态：种基本形态： n满二叉树：满二叉树：在二叉树中，如果所有分支结点都存在

26、左子树和在二叉树中，如果所有分支结点都存在左子树和 右子树，并且所有叶子结点都在同一层上，这样的一棵二叉右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。树称作满二叉树。6.3.2 二叉树二叉树1、二叉树的概念二叉树的概念完全二叉树：完全二叉树：一棵深度为一棵深度为k的有的有n个结点的二叉树，对树中的个结点的二叉树，对树中的 结点按从上至下、从左到右的顺序进行编号，如果编号为结点按从上至下、从左到右的顺序进行编号，如果编号为i（1in）的结点与满二叉树中编号为的结点与满二叉树中编号为i的结点在二叉树中的的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。位置相同，则这棵二

27、叉树称为完全二叉树。特点：特点：叶子结点只能出现在叶子结点只能出现在最下层和次最下层最下层和次最下层，且最下层的，且最下层的 叶子结点集中在树的叶子结点集中在树的左部左部。注意：注意：一个满二叉树必定是一棵完全二叉树，而完全二叉树一个满二叉树必定是一棵完全二叉树，而完全二叉树 未必是未必是满二叉树。满二叉树。6.3.2 二叉树二叉树满二叉树满二叉树完全二叉树完全二叉树非完全二叉树非完全二叉树6.3.2 二叉树二叉树2、二叉树的主要性质二叉树的主要性质性质性质1: 在二叉树的第在二叉树的第i层上最多有层上最多有个结（个结（i1）。）。性质性质2: 深度为深度为k的二叉树最多有的二叉树最多有个结（

28、个结（k1）。）。提问：提问：第第i i层上层上至少至少有有 个结点？个结点？1 1提问：提问：深度为深度为k k时至少有时至少有 个结点？个结点？k k性质性质3: 具有具有n n个结点的完全二叉树的深度必为个结点的完全二叉树的深度必为log2n1性质性质4: 对完全二叉树，若从上至下、从左至右编号，则对完全二叉树，若从上至下、从左至右编号，则编号为编号为i 的结点，其左孩子编号必为的结点，其左孩子编号必为2i，其右孩子编号必，其右孩子编号必为为2i1；其双亲的编号必为；其双亲的编号必为i/2（i1 时为根时为根, ,除外除外）。）。 6.3.2 二叉树二叉树3 3、二叉树的存储结构、二叉树

29、的存储结构(1)(1)顺序存储结构顺序存储结构用一组连续的存储单元（数组）存放二叉树中的结点。用一组连续的存储单元（数组）存放二叉树中的结点。 一般是按照二叉树结点一般是按照二叉树结点从上至下、从左到右从上至下、从左到右的顺序存储。的顺序存储。完全二叉树和满二叉树采用顺序存储比较合适，完全二叉树和满二叉树采用顺序存储比较合适，树中结点树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置以及结点之间的关系。值确定结点

30、在二叉树中的位置以及结点之间的关系。 按二叉树的结点按二叉树的结点“自上而下、从左至右自上而下、从左至右”编号，用一组连续编号，用一组连续的存储单元存储。的存储单元存储。123456789问：问：顺序存储后能否复原成唯一对应的二叉树形状？顺序存储后能否复原成唯一对应的二叉树形状？答：答：若是完全若是完全/ /满二叉树则可以做到唯一复原。满二叉树则可以做到唯一复原。 而且有规律：下标值为而且有规律：下标值为i的双亲，其左孩子的下标值必为的双亲，其左孩子的下标值必为2i， 其右孩子的下标值必为其右孩子的下标值必为2i1（即性质即性质4）T0一般不用一般不用6.3.2 二叉树二叉树41讨论：讨论：不

31、是完全二叉树怎么办？不是完全二叉树怎么办？答：答：一律转为完全二叉树！一律转为完全二叉树！方法很简单，将各层空缺处统统补上方法很简单，将各层空缺处统统补上“虚结点虚结点”，其内容为空。，其内容为空。123456789.16ABECD缺点：缺点：浪费空间；插入、删除不便浪费空间；插入、删除不便 6.3.2 二叉树二叉树(2) 链式存储结构链式存储结构 用链表来表示一棵二叉树。链表中每个结点由三个域组成，用链表来表示一棵二叉树。链表中每个结点由三个域组成，除了除了数据域数据域外，还有两个外，还有两个指针域指针域，分别用来给出该结点的左，分别用来给出该结点的左子结点和右子结点所在的链结点的存储地址。

32、子结点和右子结点所在的链结点的存储地址。非完全二叉树的链式存储非完全二叉树的链式存储43例：例： ABECD6.3.2 二叉树二叉树6.4 图状结构图状结构图图状结构的特点状结构的特点数据元素之间存在着数据元素之间存在着多对多多对多的关系。的关系。图状结构的应用图状结构的应用铁路交通图、通信网络结构、人与人之间的社会关系铁路交通图、通信网络结构、人与人之间的社会关系等。等。6.4 图状结构图状结构1. 图的定义和术语图的定义和术语n G（V，E）; 其中其中V vi | vidata object ； E ( vi,vj) | vi, vj V P(vi, vj) 。 G表示一个图，表示一个图

33、，V是图是图G中顶点的集合中顶点的集合，顶点集合构成数据，顶点集合构成数据 对象（对象（data object），顶点就代表数据元素，），顶点就代表数据元素，E是图是图G中中 边的集合边的集合，集合，集合E中中P(vi,vj)表示顶点表示顶点vi和顶点和顶点vj之间有一条之间有一条 直接连线，即偶对直接连线，即偶对(vi,vj)表示图中的一条边表示图中的一条边。 abcd(b) 无向图无向图G2 (a) 有向图有向图G1 acbde6.4 图状结构图状结构1. 图的定义和术语图的定义和术语n 有向图：有向图：在一个图中，如果任意两个顶点构成的偶对在一个图中，如果任意两个顶点构成的偶对E是有序的

34、，即顶点之间的连线是有方向的，是有序的，即顶点之间的连线是有方向的， 称该称该图为有向图。图为有向图。n 无向图：无向图：在一个图中，如果任意两个顶点构成的偶对在一个图中，如果任意两个顶点构成的偶对 ( vi,vj)E是无序的，即顶点之间的连线是没有方向的，称是无序的，即顶点之间的连线是没有方向的，称该图为无向图。该图为无向图。n 无向图中，无向图中，顶点之间的连线称为顶点之间的连线称为边边，用顶点的，用顶点的无序偶对无序偶对 ( vi ,vj)来表示。来表示。n 有向图中，有向图中，顶点之间的连线称为顶点之间的连线称为弧弧，用顶点的，用顶点的有序偶对有序偶对 来表示。来表示。6.4 图状结构

35、图状结构n 无向完全图：无向完全图：在一个无向图中，如果在一个无向图中，如果任意两个顶点都有任意两个顶点都有 一条边直接连接一条边直接连接，称该图为无向完全图。，称该图为无向完全图。 n 有向完全图：有向完全图：在一个有向图中，如果在一个有向图中，如果任意两个顶点都有任意两个顶点都有 方向互为相反的两条弧相连接方向互为相反的两条弧相连接，称该图为有向完全图。，称该图为有向完全图。 n 顶点顶点v的的度度：指连接该顶点的边数，通常记为指连接该顶点的边数，通常记为TD(v)。n 顶点顶点v的的入度入度：指以该顶点为指以该顶点为终点终点的弧的数目，记为的弧的数目，记为ID(v);n 顶点顶点v的的出

36、度出度：指以该顶点为：指以该顶点为始点始点的弧的数目，记为的弧的数目，记为OD(v); TD(v)= ID(v)+ OD(v)1. 图的定义和术语图的定义和术语6.4 图状结构图状结构n 路径：路径：在无向图中，在无向图中，顶点顶点vp到顶点到顶点vq之间的路径之间的路径是指顶点是指顶点 序列序列vp,vi1,vi2,vim, vq。其中。其中,(vp,vi1) ,(vi1,vi2), ,(vim, vq) 分别为图中的边。分别为图中的边。n 路径的长度：路径的长度：路径上路径上边的数目边的数目称为路径长度。称为路径长度。n 回路回路(环环)：始点和终点是同一个顶点的路径。始点和终点是同一个顶

37、点的路径。n 简单路径：简单路径：顶点不重复出现的路径。顶点不重复出现的路径。例：例：1. 图的定义和术语图的定义和术语6.4 图状结构图状结构v2、图的存储结构图的存储结构v图的存储结构比较复杂，表现在：图的存储结构比较复杂，表现在： 任意顶点之间可能存在联系，无法以数据元素在存储区中的物理位任意顶点之间可能存在联系，无法以数据元素在存储区中的物理位置来表示元素之间的关系；置来表示元素之间的关系； 图中顶点的度不一样，有的可能相差很大，若按度数最大的顶点设图中顶点的度不一样，有的可能相差很大，若按度数最大的顶点设计结构，则会浪费很多存储单元，反之按每个顶点自己的度设计不计结构，则会浪费很多存

38、储单元，反之按每个顶点自己的度设计不同的结构，又会影响操作。同的结构，又会影响操作。6.4 图状结构图状结构1）邻接矩阵邻接矩阵v它用两个数组分别存储它用两个数组分别存储数据元素数据元素（顶点顶点）的信息）的信息和数据元素之间的和数据元素之间的关系关系（边或弧边或弧）的信息。元素）的信息。元素之间的关系的信息用一个二维数组来表示。之间的关系的信息用一个二维数组来表示。6.4 图状结构图状结构v无向图的邻接矩阵无向图的邻接矩阵v无权无向图的邻接矩阵无权无向图的邻接矩阵1 若若(vi , vj) E，即，即vi , vj邻接邻接0 若若(vi , vj) E，即，即vi , vj不邻接不邻接Aij

39、 =(a) 无向图无向图 abcd0 1 1 11 0 1 11 1 0 11 1 1 0(b) 邻接矩阵邻接矩阵6.4 图状结构图状结构带权无向图的邻接矩阵带权无向图的邻接矩阵 权值可以理解为节点间的距离、运输成本等等权值可以理解为节点间的距离、运输成本等等无向图的邻接矩阵是无向图的邻接矩阵是对称方阵对称方阵，对于顶点，对于顶点v vi i，其度数是第，其度数是第i i行行的非的非0 0元素的个数，边数是上元素的个数，边数是上( (或下或下) )三角形矩阵中非三角形矩阵中非0 0元素个数。元素个数。v有向图的邻接矩阵有向图的邻接矩阵无权有向图无权有向图6.4 图状结构图状结构v带权有向图的邻

40、接矩阵带权有向图的邻接矩阵6.4 图状结构图状结构6.6 外存数据组织外存数据组织v数据通常以文件的方式组织并存储在外存。数据通常以文件的方式组织并存储在外存。v文件管理文件管理如何高效管理以文件形式存储在外存上的海量数据，使如何高效管理以文件形式存储在外存上的海量数据，使用户能够方便使用。用户能够方便使用。文件管理文件管理研究如何对外存上的数据进行组织。研究如何对外存上的数据进行组织。6.6.1 文件文件v文件（文件（File）通常指的是存储在外存上通常指的是存储在外存上性质相同性质相同的记录的集合，记录是文件中可以存取的数据基本的记录的集合，记录是文件中可以存取的数据基本单位。单位。按记录类型不同分为两类：按记录类型不同分为两类：操作系统的文件操作系统的文件n一维的连续的一维的连续的字符序列字符序列、无结构、无解释。、无结构