江苏省计算机三级偏软

江苏省计算机等级考试三级偏软,欣诚教育,第2章 数据结构,主要内容,算法及其描述数据、数据元素和数据结构线性表栈和队列数组树图查找排序,算法及其描述,算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。算法特性：有穷性确定性可行性输入，零个或多个输入。输出，一个或多个输出。,程序并不需要满足有穷性,算法及其描述,算法的描述方式流程图自然语言伪代码程序设计语言,C+,算法及其描述,算法设计要求（评价指标）：正确性健壮性 （如对非法数据的处理和反应）可读性简单性 （采用的数据结构和方法的简单程度）时间效率高存储空间少,算法分析,算法复杂度语句频度，算法中该语句执行的次数。一个算法中所有语句的频度之和构成该算法的运行时间。一个算法的语句频度是其求解问题规模n的函数，记为T(n)。如果有某个函数F(n)，使得当问题规模n趋于无穷大时，有：则将O(F(n)称作算法的时间复杂度。,算法分析,算法复杂度例：下面算法为求n个自然数的和S=1+2+3+n。请给出该算法的语句频度。 sum(int n) int i, s=0; for (i=1;i=n;i+) / n+1次 s=s+i; / n次 printf(“%dn”, s); / 1次 /*sum*/,T(n) = (n+1)+n+1=2n+2,算法复杂度为O(F(n) = O(n),基本概念,数据（Data）：能被计算机识别、存储和处理的的符号的集合，是计算机操作对象的总称。 数值、字符 图形、图像声音、视频数据元素（Data Element） ：数据的基本单位，亦称为结点、元素、顶点和记录等。在计算机程序中通常作为一个整体考虑和处理。（例如：一个学生记录）数据项（Data Item）：数据结构中讨论的最小单位，数据元素是数据项的集合。亦称为域、字段等。（例如：学生记录中的学号。）,数据结构,数据结构：带结构的数据元素的集合。是相互间存在关系的数据元素集合。数据结构包括3部分内容：逻辑结构,指数据之间的相互关系。存储结构,指数据及其关系在计算机中的存储方式，或数据的物理结构。运算,指对数据进行检索、插入、删除、合并、排序、统计、简单计算、转换、输入和输出等操作过程。,数据结构,逻辑结构例如，2行3列的二维数组D = a1,a2,a3,a4,a5,a6R = row, col row=, col=,不同的关系构成不同的结构： 集合、线性结构、树形结构、图（网状）结构,数据结构,逻辑结构线性结构：,数据结构,逻辑结构树形结构：,数据结构,逻辑结构图结构：,数据结构,存储结构数据的存储结构是数据逻辑结构在计算机存储器中的表示（映像），又称物理结构。存储结构包括数据元素的表示和关系的表示。顺序链接索引散列,数据结构,存储结构顺序存储结构将逻辑上相邻的结点存储在物理位置上也相邻的存储单元里，也就是将所有存储结点相继存放在一个连续相邻的存储区里。用存储结点间的位置关系来表示结点之间的逻辑关系。计算机的存储器是由很多存储单元组成的，每个存储单元都有惟一的地址（编号）。每个存储单元的地址编号都是线性连续的。顺序存储结构通常可以用C/C+语言的数组来描述。,数据结构,存储结构顺序存储结构例：用顺序存储方式表示一周7天，设这7天的数据结构为：DS（D, R）DSun, Mon, Tue, Wed, Thu, Fri, SatR = , , , , , ,数据结构,存储结构链接存储结构在存储每个结点信息的同时，需要增加一个指针来表示结点间的逻辑关系。该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。链接存储结构中的每个结点由两部分组成：一部分用于存储结点本身的信息，称为数据域；另一部分用于存储该结点的后继结点（或前驱结点）的存储单元地址，称为指针域。,数据结构,存储结构链接存储结构,数据结构,存储结构索引存储方式索引存储方法是在存储结点信息的同时，建立一个附加的索引表。索引表中每一项称为一个索引项。索引项的一般形式是：（关键字，地址）,数据结构,存储结构索引存储方式,（b）索引表,（a）文件数据区,数据结构,存储结构散列方式基本思想：根据结点的关键字Key直接计算出该结点的存储地址。即以线性表中的每个结点的关键字Key为自变量，通过一个确定的函数关系f，计算出对应的函数值f(key)，然后把这个值解释为一块连续存储空间的存储地址，将结点存储到f(key)所指的存储单元中，使每个关键字和结构中一个的存储地址相对应。,数据结构,存储结构散列方式例：已知一组待存储的关键字为（40，68，6，20，49，24，53，16，1，45，14，88），散列地址为T0.12。假设用除留取余法构造的散列函数为：H(key) = f(key) = key%13。,线性表,线性表是由n（n=0）个具有相同特性的数据元素（结点）a1, a2, a3, , an组成的有限序列。通常记作： L =（a1, a2, a3, , an）n=0 时称为空表；表中 ai-1 是ai 的直接前驱，ai+1 是ai 的直接后继；线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱和直接后继；ai是线性表的第 i 个元素，称 i 为数据元素ai 的序号，每一个元素在线性表中的位置，取决于其序号。,线性表,例1：一组实验数据（41, 21, 34, 53, 62, 71, 76, 45） 例2：26个大写英文字母组成的字母表（A, B, C, , Z） 例3：学生成绩统计表也是一个线性表。,线性表,顺序存储结构用一组地址连续的内存单元依次存放线性表的数据元素。,a1a2ai-1aiai+1an,Loc(ai ) = Loc( a1 )+ ( i 1)* L,Loc( a1 ),Loc(ai ),每个元素占L个存储单元,顺序表通过元素的存储顺序反映线性表元素间的逻辑关系,线性表,顺序存储结构 #define max 100 / 线性表可能的最大长度 typedef struct sequenlist ElemType emax; /定义线性表为一维数组 int n; /当前线性表长度 SqList;,线性表,链式存储结构用一组地址任意的存储单元来存放表中各数据元素。特点：数据元素的逻辑次序和物理次序不一定相同。在存储数据元素时，除了要存储数据元素本身的信息外，还必须附加一个或多个指针用于指向该结点的后继结点或前驱结点的存储地址（或位置）。常见的链表有3种：单链表、循环链表、双链表,线性表,线性表的链式存储结构单链表单链表中结点：,Typedef struct Node ElemType data; Struct Node *next; slink;,线性表,线性表的链式存储结构单链表,head=NULL，则该链表称为空表。,（不带表头结点）,线性表,线性表的链式存储结构单链表,head是头指针,ai-1,a2,a1,头结点,head,（带表头结点）,线性表,线性表的链式存储结构双向链表双向链表中结点：,线性表,线性表的链式存储结构循环链表,线性表,线性表的链式存储结构循环链表,线性表,线性表的链式存储结构双向循环链表,head,(b)空的双向循环链表,（c）非空的双向循环链表,head,a,b,C,线性表的基本运算,线性表的插入运算是指在表的第i（1in+1）个（或符合要求的）位置上，插入一个新的结点x，使长度为n的线性表： ( a1, , ai1 , ai , ai+1 , an ) 变成为长度为n+1的线性表：( a1, , ai1, x, ai, ai+1, an ),线性表的基本运算,顺序表的插入由于顺序表中结点在计算机中是连续存放的，若在第i个结点之前插入一个新结点x，就必须将表中下标位置为i, i+1, , n上的结点依次向后移动到i+1, i+2, , n+1的位置上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结点，直接将x插到表的末尾。新结点插入后，线性表的长度变成n+1。,线性表的基本运算,顺序表的插入在顺序表中插入一个新结点的过程如下： 检查顺序表的存储空间是否已满，若满则停止插入，退出程序运行； 将第in个结点之间的所有结点依次向后移动一个位置，空出第i个位置； 将新结点x插入第i个位置；修改线性表的长度，使其加1； 若插入成功，则函数返回值为1，否则函数值返回值为0。见教材p.45算法2-1,线性表的基本运算,单链表的插入假设指针p指向单链表中某个结点，指针s指向值为x的新待插结点。若将新结点s插入结点p之后，则称为后插；若将新结点s插到结点p之前，则称为前插。后插运算,y,x,p,head,s,线性表的基本运算,单链表的插入后插运算,线性表的基本运算,单链表的插入前插运算,见教材p64算法2-10,线性表的基本运算,双向链表的插入前插运算,线性表的基本运算,双向链表的插入后插运算,线性表的基本运算,线性表的删除运算将线性表中第i个（或符合要求）的数据元素删除，使长度为n的线性表： ( a1, , ai1 , ai , ai+1 , an ) 变成为长度为n-1的线性表：( a1, , ai1, ai+1, an ),线性表的基本运算,顺序表的删除过程： 检查给定结点的删除位置是否正确，若删除位置有错，则显示出错信息，退出程序运行； 把表中第i+1n个结点之间的所有结点依次向前移动一个位置； 将线性表的长度减1。 见教材p46算法2-2,线性表的基本运算,单链表的删除,见教材p65算法2-11,线性表的基本运算,双向链表的删除,顺序表插入和删除运算的时间分析,在线性表顺序存储结构中某个位置上插入和删除一个数据元素时，其插入与删除算法的主要执行时间都耗费在移动数据元素上，而移动元素的个数则取决于插入或删除元素的位置。假设pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动元素次数的期望值（平均次数）应为：,顺序表插入和删除运算的时间分析,同理，假设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动元素次数的期望值（平均次数）应为：,顺序表插入和删除运算的时间分析,假定在线性表任何位置上插入或删除元素都是等概率的，则: pi=1/(n+1) qi = 1/n在等概率情况下，上式可以分别简化为：若顺序表的长度为n，则顺序表的插入算法和删除算法的时间复杂度均为O(n)。,单链表上查找、插入和删除运算的时间分析,设Pi是单链表上查找第i个元素的概率，在长度为n的带头结点的单链表中可能进行查找的位置为i=0, 1, 2, , n。在等概率情况下P1=P2=Pi=1/(n+1)。若查找成功时，则单链表中查找任意位置上数据元素的平均比较次数为：单链表上查找、插入、删除算法的平均时间复杂度为O(n)。,顺序表和链表的比较,空间性能的比较存储密度：存储结点中数据域占用的存储量与存储结点所占用的存储量之比称为存储密度。存储密度越大，则存储空间的利用率就越高。顺序表的存储密度是高于链表的存储密度。但是，顺序表要求事先估计容量，这是比较困难的。,顺序表和链表的比较,时间性能的比较当线性表的主要操作是查找运算时，最好采用顺序存储结构。对于需要频繁地进行插入和删除操作的线性表，最好采用链接存储结构。若链表的插入和删除操作主要发生在表的首、尾两端，采用尾指针表示的单循环链表则是最好的选择。,栈,栈是限定仅能在表尾一端进行插入、删除操作的线性表。,（a1, a2, . , ai -1, ai , ai+1, , an ）,插入,删除,栈,允许进行插入和删除运算的这一端称为栈顶，不允许进行插入和删除运算的另一端则称为栈底；向栈中插入一个新元素称为入栈或压栈，从栈中删除一个元素称为出栈或退栈；记录栈顶元素位置的变量称为栈顶指针，处于栈顶位置的数据元素称为栈顶元素；不含任何数据元素的栈则称为空栈。,栈,栈的特点后进先出,栈,栈的顺序存储结构利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。顺序栈可以用一个一维数组和一个记录栈顶位置的整型变量来实现，数组用于顺序存储栈中所有的数据元素，栈顶指针用于存储栈顶元素的位置。,emax,top,stack,栈,栈的链式存储结构以某种形式的链表作为栈的存储结构，其组织形式与单链表类似。,栈,顺序栈的基本运算,见教材p48 算法2-3，算法2-4,栈,链栈的基本运算,栈,共享栈,栈在递归过程中的作用,所谓递归，是指一个函数、过程或者数据结构，若在其定义的内部又直接或者间接出现有定义自身的应用，则称其是递归的或者是递归定义的。在调用一个函数（程序）的过程中又直接或间接地调用该函数（程序）本身，称为函数的递归调用。,栈在递归过程中的作用,一般函数的调用机制,函数调用顺序 A B C,函数返回顺序 C B A,后调用的函数先返回,函数调用机制可通过栈来实现,计算机正是利用栈来实现函数的调用和返回的,栈在递归过程中的作用,递归函数：一个直接调用自己或通过一系列调用间接调用自己的函数称为递归函数。,A（ ） A( ) ; ,B( ) C( ) C( ); B( ); ,A 直接调用自己,B间接调用自己,栈在递归过程中的作用,递归算法的编写1）将问题用递归的方式描述（定义）2）根据问题的递归描述（定义）编写递归算法递归定义包括两项1）基本项（终止项）：描述递归终止时问题的求解；2）递归项：将问题分解为与原问题性质相同，但规模较小的问题；,栈在递归过程中的作用,递归算法的编写【例3.7】采用递归算法求解正整数n的阶乘（n！）。 正整数n的阶乘的递归定义为：,栈在递归过程中的作用,递归算法的编写/* 用递归方法求n的阶乘的函数 */ float Fact(int n) float f = 0.0; if (n=j）。则其存储分配情况如图所示。,对称阵的压缩存储,在这种压缩结构中，为了便于访问对称矩阵A中元素并能进行处理，我们必须通过给定的一组下标（i, j）找到对称矩阵中任一元素aij在一维数组Bk中的存储位置，即在aij和Bk之间找到一个对应关系。,三角矩阵的压缩存储,以主对角线划分，三角矩阵分为两种：上三角矩阵和下三角矩阵。上三角矩阵，是指下三角（不包括主角线）中的元素均为常数c的n阶方阵。下三角矩阵，主对角线上方均为常数c。在多数情况下，三角矩阵的常数c为0。对于任何一个n阶下三角矩阵都具有下述性质：当ij时，aij=c；同理，对于任何一个n阶上三角矩阵：当ij时，aij=c。,三角矩阵的压缩存储,三角矩阵采用压缩存储方式时，只存储矩阵的下三角元素或上三角元素。如果让矩阵中所有重复元素c共享一个存储单元，那么三角矩阵中n2个元素就可以压缩存储到一维数组Bn(n+1)/2中，其中重复元素c放在数组的最后一个单元中。若按“行优先顺序”存储下三角矩阵中的元素，则矩阵下三角元素的压缩存储情况如下图所示。,三角矩阵的压缩存储,三角矩阵A中任一元素aij在一维数组Bk中的存储位置。上三角关系下三角关系,树,树是由n（n0）个结点组成的有限集合。若n=0，则树是一棵空树；若n0，则树是一棵非空树。一棵非空树满足如下两个条件： 有且仅有一个特定的结点，该结点称为根结点； 除根结点外的其他结点可分为m（m0）个互不相交的有限集合T1, T2, , Tm，其中每个集合本身又是一棵树，这些集合称为根结点的子树。,树的定义,T=A, B, C, D, E, F, G, H, I, J，K，L，MA是根，其余结点可划分为3个互不相交的集合： T1=B, E, F，K，L , T2=C, G , T3=D, H, I, J，M,树,树的定义,树是一种非线性数据结构，其特点是：1）树中每个结点都可以有零个或多个直接后继，若有多个后继结点，则后继结点是该结点的每个子树的根结点。2）除根结点之外的所有结点，有且仅有一个直接前驱。3）数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。4）树型结构中数据元素之间的关系是一对多或者多对一的关系。,树,基本术语1结点的度和树的度结点具有的子树（分支）个数称为结点的度。一棵树中所有结点的度的最大值称为树的度。2叶子结点和分支结点树中度为0的结点称为叶子结点或终端结点，度不为0的结点称为非终端结点或分支结点。,树,基本术语3双亲结点、孩子结点和兄弟结点树中每个结点的子树的根称为该结点的孩子或儿子或子女；相应地，该结点称为孩子结点的双亲或父亲。具有同一个双亲的孩子们之间互称为兄弟。每个结点的祖先是从树的根结点到该结点所经过路径上的所有结点。反之，以某结点为根的子树中的所有结点都称为该结点的子孙。,树,基本术语4结点的层数和树的高度结点的层数从树的根结点开始计算。假设树的根结点为第一层，它的孩子结点为第二层，其余类推。树中结点的最大层数就称为树的高度或深度。5森林森林是m（m0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。6有序树和无序树若树中结点的各子树从左到右是有次序的，且相对次序是不能变换的，则该树被称为有序树，否则称为无序树。,二叉树,定义二叉树是有限的结点集合，这个集合或者为空，或者有一个根结点，它由两棵不相交的分别称为根的左子树和右子树的二叉树组成。左子树和右子树同样又都是一棵二叉树。,二叉树的5种基本形态,二叉树,定义,两棵不同的二叉树,一棵普通的无序树,二叉树,二叉树的性质性质1：在二叉树的第i 层上最多有2i-1个结点。性质2：深度为 h 的二叉树最多有 2h-1 (h=1)个结点。性质3：设二叉树叶子结点数为n0，度为2的结点数为n2，则 n0 = n2 +1。满二叉树：如果深度为 k 的二叉树，有2k-1个结点则称为满二叉树。,二叉树,二叉树的性质完全二叉树：如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树。性质4：具有n个结点的完全二叉树的深度为log2n+1,或 log2n+1,二叉树的性质,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（每层从左到右），则对任一结点i (1=i1，则其双亲是结点 i/2 ；2）2in：结点无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。3）2i+1n：结点无右孩子（结点I为叶子结点）；否则其右孩子是结点2i+1。,二叉树,二叉树的顺序存储结构把二叉树的所有结点，按照一定的次序顺序存放到一组地址连续的存储单元中。对完全二叉树中所有结点进行编号得到一个结点的线性序列，然后将完全二叉树各结点按其编号顺序存放到一个一维数组中，即将完全二叉树上编号为 i 的结点存入一维数组下标为 i 的分量中。对于编号为 i 的结点，若有左孩子，它的左孩子的编号为 2i；若有右孩子，它的右孩子的编号为 2i+1。,二叉树,二叉树的顺序存储结构,二叉树,二叉树的顺序存储结构普通二叉树的顺序存储方法,二叉树,二叉树的链接存储结构,二叉树,二叉树的遍历按一定的次序“访问”二叉树的所有结点，使得每个结点仅被“访问”一次。实际上就是把二叉树的所有结点放入一个线性序列的过程。需要寻找一种规律来系统地访问二叉树的各个结点。三种方式：DLR，LDR，LRD,根,二叉树,二叉树的遍历,其第一个元素值为二叉树中根结点的数据值。,以根结点的数据值为界，将中序遍历序列分为两部分。,其最后一个元素值为二叉树中根结点的数据值。,算法见教材p73,二叉树,二叉树的遍历例有二叉树中序序列为：ABCEFGHD，后序序列为：ABFHGEDC，画出此二叉树。,二叉树,二叉树的遍历【例】假设先序遍历某二叉树的结点次序为ABCDEFGHIJ，中序遍历该二叉树的结点次序为CBEDAGHFJI，试画出此二叉树。,求二叉树的高度运算算法,求二叉树的高度的递归模型如下： 0 若bt = NULL Max f (bt-lchild) , f ( bt-rchild ) + 1,f( bt ) =,求二叉树的高度运算算法,Int BTHeight ( bitree *bt ) int lchilddep, rchilddep; if ( bt = = NULL) return ( 0 ); else lchilddep = BTHeight ( bt -lchild ); rchilddep = BTHeight ( bt-rchild ); return(lchilddeprchilddep)?(lchilddep+1):(rchilddep +1 ); ,求二叉树结点个数运算算法,对应的递归模型如下： 0 若bt = NULL f ( bt -lchild ) + f ( bt-rchild ) +1,f( bt ) =,求二叉树结点个数运算算法,Int NodeCount ( bitree *bt ) int num1, num2; if ( bt = = NULL) return 0; Else num1 = NodeCount ( bt -lchild ); num2 = NodeCount ( bt -rchild ); return ( num1 + num2 +1 ); ,求二叉树叶子结点个数运算算法,对应的递归模型如下： 0 bt = NULL 1 bt为叶子结点 F ( bt -lchild ) + f ( bt -rchild ) 其他情况,F (bt) =,求二叉树叶子结点个数运算算法,Int LeafCount ( bitree *bt ) int num1, num2; if ( bt = = NULL ) return 0; else if ( bt -lchild = = NULL & bt-rchild = = NULL ) return 1; else num1 = LeafCount ( bt -lchild ); num2 = LeafCount ( bt-rchild ); return ( num1 + num2 ); ,树的存储结构,孩子兄弟链表存储结构,Fchild data nsibling,第一个孩子,下一个兄弟,树的存储结构,树的遍历两种方式先根遍历后根遍历,树、二叉树、森林的转换,树、二叉树、森林的转换,图,定义一个图G是由两个集合V(G)和E(G)组成的，图的二元组可定义为：G=(V, E) V(G)是顶点的有穷非空集合，每个顶点都可以标上不同的字符或数字。 E(G)是V中顶点边的有穷集合，而边是V中顶点的偶对。在特殊情况下，E(G)可以是空集。,图的定义,V(G1) = V1, V2, V3, V4 E(G1) = (V1, V2)，(V1, V3)，(V1, V4)， (V2, V3)，(V2, V4)，(V3, V4),V(G3)=V1, V2, V3 E(G3)=， ,图,基本术语 边、链接点、弧、权、网完全图子图度路径和简单路径回路连通图和强连通图,图的基本术语,顶点的度、入度和出度无向图中，与顶点v相邻接的边数称为该顶点的度。有向图中，以顶点v为终点的弧的数目称为顶点v的入度；以顶点v为起点的弧的数目称为顶点v的出度；有向图顶点v的度为该顶点的入度和出度之和。,弧,V1的度为3,V1的出度为2，入度为0,图的基本术语,完全图假设图的边或弧的两个顶点不能相同：有n(n1)/2条边的无向图称为无向完全图。有n(n1)条弧的有向图称为有向完全图。,图的基本术语,路径、回路和路径长度在无向图G中，若存在一个顶点序列（Vp , Vi1 , , Vin , Vq），使(Vp, Vi1)，(Vi1, Vi2)，(Vin, Vq)均为图G的边，则称从顶点Vp到顶点Vq存在一条路径。有向图路径由有向边，组成。路径长度定义为路径上的边数或者弧的数目。若一条路径上除起点Vp和终点Vq可以相同外，其余顶点均不重复出现，则称此路径为简单路径。起点和终点相同的路径（Vp=Vq）称为回路或环。除了起点和终点相同外，其余顶点不相同的回路，称为简单回路。,图的基本术语,子图,图的基本术语,连通、连通分量和连通图在无向图G中，如果从顶点Vi 到顶点Vj 有路径，则称Vi和Vj是连通的。如果图中任意两个不同的顶点Vi和Vj都连通则称G为连通图。无向图G的极大连通子图称为G的连通分量。显然，任何连通图的连通分量即其自身，而非连通图有多个连通分量。,图的基本术语,连通、连通分量和连通图,图的基本术语,强连通、强连通分量和强连通图在有向图G中，如果从顶点Vi到顶点Vj有路径，则称从Vi到Vj是连通的。如果图中任意两个不同的顶点Vi和Vj都存在从Vi到Vj及从Vj到Vi的路径，则称G是强连通图。有向图G的极大强连通子图称为G的强连通分量。显然，强连通图只有一个强连通分量，即其自身，非强连通的有向图有多个强连通分量。,图的基本术语,强连通、强连通分量和强连通图,图的存储结构,图的存储结构至少要保存两类信息： 1）顶点的数据 2）顶点间的关系两种常用的图的存储表示方法： 1）邻接矩阵 2）邻接表,邻接矩阵的定义,假设G = (V, E)是具有n (n1)个顶点的图，则G的邻接矩阵A是一个具有下述性质的nn阶方阵： 1 若(vi,vj)E 或 E 0 否则,Aij =,邻接矩阵的定义,0 1 1 0 1 10 0 1 0 11 0 0 1 1 00 1 1 0 1 10 1 1 0 01 1 0 1 0 0,0 1 1 0 0 00 0 0 1 0 00 1 0 0 1 10 0 0 0 0 10 0 0 1 0 00 1 0 0 1 0,邻接矩阵的特点, 一个图的邻接矩阵表示是惟一的。 对于无向图来说，它的邻接矩阵是关于主对角线对称的，因此，按照压缩存储的思想，只需要存放邻接矩阵的上三角矩阵（或下三角矩阵）。 借助邻接矩阵可以很容易判断出两个顶点是否有边相邻接，查找图中任意一条边或边上的权很方便。 顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1（或wij）或清0；图G占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图。,邻接矩阵的特点,利用邻接矩阵能很容易计算出图中各顶点的度。无向图：有向图：有向图各顶点Vi 的总度数就等于出度与入度之和，即D(Vi)=OD(Vi)+ID(Vi)。,矩阵A中第i行（或第j列）非零元素的个数,矩阵A中第i行非零元素的个数,矩阵A中第i列非零元素的个数,邻接表表示法,1邻接表的组成邻接表是一种顺序和链接相结合的图的存储方法，该方法为图中每个顶点建立一个邻接关系的单链表，并把单链表的表头指针存储到一个数组中。数组下标i表示顶点Vi邻接表表头结点的存储位置。邻接表表头数组称为顶点表。每个顶点都要建立一个邻接关系的单链表。无向图：第i个单链表中的结点表示依赖于顶点Vi的相邻边；有向图：它表示以顶点Vi为尾的弧。 将这个单链表称为顶点Vi的邻接表。单链表中的结点用于存储以该顶点为起点的边的信息，称为边结点或表结点。,邻接表表示法,对于无向图，顶点Vi邻接表中的结点数就是顶点Vi的度数、边数或邻接点数。,邻接表表示法,对于有向图，顶点Vi邻接表中的结点数就是顶点Vi的出度数、出边数或出边邻接点数。,邻接表的特点, 一个图的邻接表表示不是惟一的。 若一个图有n个顶点e条边，对于无向图，其邻接表中需要n+2e个结点，n个顶点构成顶点表，2e个边结点构成邻接表；对于有向图，则其邻接表中需要n+e个结点，n个顶点结点构成顶点表，e个边结点构成邻接表。在边稀疏的情况下，邻接表比邻接矩阵更节省存储空间。,邻接表的特点, 在邻接表中，查找图中某个顶点的边（出边）或邻接点（出边邻接点）很方便，只要从表头数组中取出对应的表头指针，然后从表头指针出发进行查找即可。由于每个邻接表的平均长度为e/n（有向图）或2e/n（无向图），所以查找的时间复杂度为O(e/n)。但是，在有向图的邻接表中，查找顶点Vi的入边或入边邻接点不方便，需要扫描整个邻接表中边结点，其时间复杂度为O(n+e)。 借助于邻接表计算图中某顶点的度很容易。对于无向图，顶点Vi的度就是顶点Vi对应的第i个链表中的结点数；对于有向图，顶点Vi 对应的第i个单链表中的结点个数是顶点Vi的出度，但求顶点的入度比较难，须扫描整个邻接表。,图的遍历,图的遍历是指从任意指定的某个顶点（初始点）出发，按照一定的搜索方法依次访问图中所有顶点，且每个顶点仅被访问一次。从图的初始点到其余顶点可能存在多条路径，因此，在访问了某个结点之后，有可能顺着某条回路又回到了该顶点，即存在回路。为了避免同一个顶点被重复访问，必须记住每个顶点是否被访问过，为此可设置一个辅助数组visitedn，用来记录图中所有被访问过的顶点。根据搜索路径不同，有两种遍历方法： 深度优先搜索遍历（DFS），广度优先搜索遍历（BFS）。,深度优先搜索的基本思想,首先访问初始出发点V0，并将其标记设置为已访问；然后任选一个与V0相邻接且没有被访问的邻接点V1访问，将其标记设置为已访问；再以V1为新的出发点，继续进行深度优先搜索，访问与V1相邻接且没有被访问的任一个顶点V2；重复上述过程，若遇到一个所有邻接点均被访问过的结点，则回到已访问结点序列中最后一个还没有被访问的相邻结点的顶点，再从该顶点出发继续进行深度优先搜索，直到图中所有顶点都被访问过，搜索结束。,深度优先搜索的基本思想,从顶点1出发进行深度优先遍历下面的无向图,V1、V2、V5、V10、V6、V7、V3、V12、V11、V8、V4、V9,广度优先搜索的基本思想,从图G = (V, E)的某个起始点V0出发，首先访问起始点V0，接着依次访问V0所有邻接点V1, V2, ,Vp，然后，分别从这些邻接点V1, V2, , Vp出发，按广度优先遍历的方法，依次访问与其相邻接的所有未被访问过的顶点；其余类推，直到图中所有顶点都被访问到为止。这个过程称为连通图的广度优先搜索遍历，简称BFS。,广度优先搜索的基本思想,对下面的无向图进行广度优先遍历，给出从顶点V1出发进行遍历的结果。,查找的基本概念,查找运算主要是对关键字进行比较，所以通常用平均查找长度作为衡量