---

前言

在备考软件设计师中级考试的过程中，我遇到了些许挑战，也收获了宝贵的经验。为了帮助其他同样正在为这门考试（证书）奋斗的朋友们，我决定将我的笔记整理出来，与大家分享。这些笔记不仅包含了书本上的知识，还加入了我对重点和难点的个人理解以及考试技巧，力求帮助大家更加高效地复习。我希望这份笔记能够成为你备考路上的一份支持，也祝愿你在考试中取得理想的成绩。

如果有写的不好或者需要改进的地方，恳请在评论区指正！

---

阅读之前，公式温馨提示：向上取整, 运算称为Ceiling，用数学符号⌈⌉ （上有起止，开口向下）表示,。 向下取整, 运算称为Floor，用数学符号⌊⌋ （下有起止，开口向上）表示。 注意，向上取整和向下取整是针对有浮点数而言的; 若整数向上取整和向下取整， 都是整数本身。

---

# 第3章 数据结构【上】(5分)

3.1 线性结构

3.1.1 线性表

1. 线性表的定义

   线性表是n个元素的有限序列，通常记为(a₁,a₂,…,a_n)。其特点如下。

   • 存在唯一的一个称为“第一个”的元素
   • 存在唯一的一个称为“最后一个”的元素。
   • 除了表头外，表中的每一个元素均只有唯一的直接前驱。
   • 除了表尾外，表中的每一个元素均只有唯一的直接后继。

2. 线性表的存储结构

   1. 顺序存储
      线性表的顺序存储是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑关系相邻的两个元素在物理位置上也相邻。在这种存储方式下，存储逻辑关系无须占用额外的存储空间。其优点是可以随机存取表中的元素，缺点是插入和删除操作需要移动大量的元素。
      一般地，在线性表的顺序存储结构中，第i个元素a_i的存储位置为
      $LOC(a_i)=LOC(a_1)+(i-1)\times L$
      式中，LOC(a₁)为表中第一个元素的存储位置；L为表中每个元素所占空间的大小。

      1. 取值
         顺序表取值算法的时间复杂度为O(1)。
      2. 查找
         顺序表按值查找算法的平均时间复杂度为O(n)。
      3. 插入
         一般情况下，在第i（1≤i≤n）个位置插入一个元素时，需从最后一个元素即第n个元素开始，依次向后移动一个位置，直至第i个元素（共n-i+1个元素），仅当插入位置i=n+1时，才无须移动结点。
         顺序表插入算法的平均时间复杂度为O(n)。

   2. 链式存储
      线性表的链式存储是指用节点来存储数据元素，节点的空间可以是连续的，也可以是不连续的，因此存储数据元素的同时必须存储元素之间的逻辑关系。节点空间只有在需要的时候才申请，无须事先分配。最基本的节点结构如图3-1所示。
      

      其中，数据域用于存储数据元素的值，指针域则存储当前元素的直接前驱或直接后继信息，指针域中的信息称为指针(链)。n个节点通过指针连成一个链表，若节点中只有一个指针域，则称为线性链表(单链表)。如图3-2所示。
      

      【函数】设线性表中的元素是整型，则单链表结点类型的定义为：

      typedef struct node{
        int data; /*结点的数据域，此处假设为整型*/
        struct node*next;  /*结点的指针域*/
      }NODE,*LinkList;
      

      线性表采用链表作为存储结构时，不能进行数据元素的随机访问，但其优点是插入和删除操作不需要移动元素。

      在链式存储结构中，只需要一个指针（称为头指针，如图3-2 中的 head) 指向第一个结点，就可以顺序地访问到表中的任意一个元素。
      在链式存储结构下进行插入和利除，其实质都是对相关指针的修改。在单链表中，若在P所指结点后插入新元素结点（s所指结点，已经生成)，如图3-3（a） 所示，其基本步骤如下。

      ① s->next = p->next;
      ② p->next = s;
      

      即先将p所指结点的后继结点指针赋给s所指结点的指针域，然后将p所指结点的指针城修改为指向s所指结点。
      

      同理，在单链表中删除p所指结点的后继结点时（如图3-3(b)所示），步骤如下。

      ① q = p -> next;
      ② p -> next = p -> next -> next;
      ③ free(q);
      

      即先令临时指针q指向待删除的结点，然后修改p所指结点的指针域为指向p所指结点的后继的后继结点，从而将元素b所在的结点从链表中州除，最后释放q 所指结点的空间。在实际应用中，为了简化对链表状态的判定和处理，特别引入一个不存储数据元素的结点，称为头结点，将其作为链表的第一个结点并令头指针指向该结点。
      下面给出单链表上查找、插入和删除运算的实现过程。
      【函数】单链表的插入运算……
      【函数】单链表的删除运算

3. 取值：

   链表中逻辑相邻的结点并没有存储在物理相邻的单元中，给定的结点位置序号i，只能从链表的⾸元结点出发，顺着链域next逐个结点向下访问
   取值算法的最坏时间复杂度是O(n)
   取值算法的平均时间复杂度是O(n)

4. 查找

   查找过程与顺序表类似，从首元结点出发，依次将结点值和给定值e进行比较，返回查找结果
   查找算法的平均时间复杂度是O(n)

5. 插入

   在上面图3-3

   插入算法的平均时间复杂度是O(n)

当线性表采用链表作为存储结构时，不能对数据元素进行随机访问，但是具有插入和删除操作不需要移动元素的优点。

根据结点中指针域的设置方式，还有其他几种链表结构。

• 双向链表。每个结点包含两个指针，分别指出当前元素的直接前驱和直接后继。其特点是可以从表中任意的结点出发，从两个方向上遍历链表。
• 循环链表。在单向链表（或双向链表）的基础上令表尾结点的指针指向链表的第一个结点，构成循环链表。其特点是可以从表中任意结点开始遍历整个链表。
• 静态链表。借助数组来描述线性表的链式存储结构，用数组元素的下标表示元素所在结点的指针。

若双向链表中结点的 front 和 next 指针域分别指示当前结点的直接前驱和直接后继，则在双向链表中插入结点*s时指针的变化情况如图3-4（a） 所示，其操作过程可表示为：

   1. s->front = p->front;
   2. p->front->next = s; //或者表示为 s->front->next=s;
   3. s->next=p;
   4. p->front=s;

在双向链表中删除结点时指针的变化情况如图3-4(b)所示，其操作过程可表示为：

   1. p->front->next = p->next;
   2. p->next->front = p->front; free(p);

3.1.1.1 总结

存储结构

• 顺序表

  • 优点：支持随机存取、存储密度高
  • 缺点：大片连续空间分配不方便，改变容量不方便

• 链表

  • 优点：离散的小空间分配方便，改变容量方便
  • 缺点：不可随机存取，存储密度低

如果没有给出最好最坏平均时间复杂度的话就默认是平均时间复杂度

顺序表：

• 采用顺序存储，优点是可以随机存取表中的元素；
• 缺点是插入和删除操作需要移动大量的元素。
• 时间复杂度
  • 插入、删除操作最好时间复杂度为O(1)
  • 平均和最坏时间复杂度都为O(n)
  • 查找最好、最坏、平均情况都为O(1)

单链表：

• 采用链式存储，优点是插入和删除操作不需要移动大量的元素，只需要修改指针；
• 缺点是不能随机访问表中的元素。
• 时间复杂度
  • 查找、插入、删除操作最好时间复杂度为O(1)
  • 平均和最坏时间复杂度都为O(n)

3.1.2 栈和队列

1. 栈

   1. 栈的定义及基本运算
      栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。只允许在一端进行插入或删除操作的线性表。栈的修改是按先进后出的原则进行的。因此，栈又称为先进后出(FILO，或后进先出）的线性表。栈进行插入和删除操作的一端称为栈顶Top，另一端称为栈底Bottom。不含数据元素的栈称为空栈。递归使用栈。
      对栈进行的基本操作有以下几种。

      • 置空栈 InitStack(S)：创建一个空栈S。
      • 判栈空 Empty(S)：当栈S为空栈时返回真值；否则返回假值。top==0
      • 入栈 Push(S, x)：将元素x加入栈项，并更新栈项指针。
      • 出栈 Pop(S)：将栈项元素从栈中删除，并更新栈顶指针。若需要得到栈顶元素的值，可将 Pop(S)定义为一个函数，它返回栈顶元素的值。
      • 读栈顶元素 Top(S)：返回栈项元素的值，但不修改栈顶指针。

      判断栈空或栈满【掌握】

      • 判断栈空的条件
        • 初始化top=-1
        • top==-1
      • 判断栈满的条件
        • 初始化top=0
        • top==MaxSize
      • 判断共享栈满的条件
        • 初始化：0号栈栈顶top0=-1;1号栈栈顶top1=MaxSize
        • top0+1==top1

   2. 栈的存储结构

      1. 顺序存储。栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针 top 指示栈项元素的位置。采用顺序存储结构的栈也称为顺序栈。在这种存储方式下，需要预先定义（或申请）栈的存储空间，也就是说，栈空间的容量是有限的。因此，在顺序栈中，当一个元素入栈时，需要判断是否栈满（栈空间中没有空闲单元），若栈满，则元素不能入栈。
      2. 栈的链式存储。用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必另外设置头指针，链表的头指针就是栈顶指针。链栈的表示如图3-5 所示。
      3. 栈的应用。栈的典型应用包括表达式求值、括号匹配等，在计算机语言的实现以及将递归过程转变为非递归过程的处理中，栈有重要的作用。
         

2. 队列

   1. 队列的定义及基本运算
      队列是一种先进先出(FITFO)的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入元素的一端称为队尾(Rear)，允许删除元素的一端称为队头(Front)。

      对队列进行的基本操作如下。
      (1)置队空 InitQueue(Q)：创建一个空的队列Q。
      (2)判队空 Empty(Q)：判断队列是否为空。
      (3)入队 EnQueue(Q. x)：将元素x加入到队列Q的队尾，并更新队尾指针。
      (4)出队 DeQueue(Q)：将队头元素从队列Q中删除，并更新队头指针。
      (5)读队头元素 Frontque(Q)：返回队头元素的值，但并不更新队头指针。

   2. 队列的存储结构

      1. 顺序表存储。
         队列的顺序存储结构又称为顺序队列，它也是利用一组地址连续的存储单元存放队列中的元素。由于队列中元素的插入和删除限定在表的两端进行，因此设置队头指针和队尾指针，分别指出当前的队头和队尾。
         下面设顺序队列Q的容量为6，其队头指针为 front，队尾指针为 rear，头、尾指针和队列中元素之间的关系如图3-6所示。
         

         在顺序队列中，为了降低运算的复杂度，元素入队时只修改队尾指针，元素出队时只修改队头指针。由于顺序队列的存储空间容量是提前设定的，所以队尾指针会有一个上限值，当队尾指针达到该上限时，就不能只通过修改队尾指针来实现新元素的入队操作了。若将顺序队列假想成一个环状结构（通过整除取余运算实现)，则可维持入队、出队操作运算的简单性，如图3-7 所示，称之为循环队列。
         

         设循环队列Q的容量为 MAXSIZE，初始时队列为空，且 Q.rear 和 Q.front 都等于0，如图3-8（a）所示。
         元素入队时，修改队尾指针Q.rear = (Q.rear+1)% MAXSIZE，如图3-8 (b）所示。
         元素出队时，修改队头指针Q.front =(Q.front+1)% MAXSIZE，如图3-8（c） 所示。
         根据队列操作的定义，当出队操作导致队列变为空时，则有 Q.rear—Q.front, 如图3-8 (d)所示；若入队操作导致队列满，则 Q.rear—Q.front，如图3-8(e) 所示。
         在队列空和队列满的情况下，循环队列的队头、队尾指针指向的位置是相同的，此时仅仅根据 Q.rear 和 Q.fromt之间的关系无法断定队列的状态。为了区别队空和队满的情况，可采用以下两种处理方式：其一是设置一个标志，以区别头、尾指针的值相同时队列是空还是满：其二是牺牲一个存储单元，约定以“队列的尾指针所指位置的下一个位置是队头指针时”表示队列满，如图3-8（f） 所示，而头、尾指针的值相同时表示队列为空。
         

      2. 链式存储。

         队列的链式存储也称为链队列。这里为了便于操作，给链队列添加一个头结点，并令头指针指向头结点。因此，队列为空的判定条件是头指针和尾指针的值相同，且均指向头结点。队列的一种链式存储如图3-9 所示。
         

      3. 队列的应用

         队列结构常用于处理需要排队的场合，例如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。

      4. 求队列长度【以下为补充】

         对于非循环队列,尾指针和头指针的差值便是队列长度，而对于循环队列,差值可能为负数，所以需要将差值加上 MAXQSIZE,然后与 MAXQSIZE 求余。

      5. 入队

         入队操作是指在队尾插入一个新的元素。
         【算法步骤】

         1. 判断队列是否为满，若满则返回ERROR
         2. 将新元素插入队尾
         3. 队尾指针加1

      6. 出队

         出队操作是将队头元素删除。
         【算法步骤】

         1. 判断队列是否为空，若空则返回ERROR
         2. 保存队头元素
         3. 队头指针加1

      7. 取队头元素
         当队列非空时，此操作返回当前队头元素的值，队头指针保持不变。

3.1.2.1 做题技巧

方式一

• 从0-M-1，直接标序号0、1、2、3、4、5.
• 容量=6，队尾=1，队头=5，长度=3
• 带入选项中的公式，得出答案等于队头5，即是正确答案。

方式二

• 按照题目意思进行计算，+M防止下溢出，%M是防止上溢出
  

• 栈的特点是后进先出，若用单链表作为栈的存储结构，并用头指针作为栈顶指针，则入栈和出栈操作都不需要遍历链表

• 循环单链表

  • 入队列和出队列操作都不需要遍历链表

• 采用循环队列的优点：入队和出队操作都不需要移动队列中的其他元素

3.1.3 串

总结

字符串是线性结构，空格也是字符串
字串是指由主串中任意长度连续的字符构成的序列

例如：
主串：abc
字串：a、b、c、ab、bc
ac不是字串，因为它不是主串中连续的字符

串的匹配模式

朴素模式匹配：
时间复杂度：最好情况O(m)，最坏情况O(n*m)，平均情况O(n+m)
比较次数：最好情况m次，最坏情况(n-m+1)*m次，平均情况1/2(n-m+1)次

串的前缀：包含第一个字符并且不包含最后一个字符的子串
串的后缀：包含第一个字符并且不包含最后一个字符的子串

求next[]：第i个字符的值等于前 1 ~ i-1 个字符串组成的串中
最长相等前后缀的长度+1

特殊的next[1]=0，next[2]=1

1. 串的定义及基本运算
   串是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为S=$a_1{a}_2...a_n$，其中S是串名，$a_1{a}_2...a_n$是串值。
   下面介绍串的几个基本概念。
   (1) 空串：长度为零的串，空串不包含任何字符。
   (2) 空格串：由一个或多个空格组成的串。
   (3) 子串：由串中任意长度的连续字符构成的序列。含有子串的串称为主串。子串在主串中的位置指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。
   (4) 串相等：指两个串长度相等且对应位置上的字符也相同。
   (5) 串比较：两个串比较大小时以字符的 ASCIL 码值作为依据。比较操作从两个串的第一个字符开始进行，字符的 ASCII 码值大者所在的串为大；若其中一个串先结束，则以串长较大者为大。

   对串进行的基本操作有以下几种。
   (1) 赋值操作 StrAssign(s, D)：将串t的值赋给串S。
   (2) 连接操作 Concat(s,t)：将串t接续在串、的尾部，形成一个新串。
   (3) 求串长 StrLength(s)：返回串s的长度。
   (4) 串比较 StrCompare(s, b)：比较两个串的大小。
   (5) 求子串 SubString(s, start, len)：返回串s中从 start 开始的、长度为len 的字符序列。

2. 串的链式存储

   1. 串的静态存储：定长存储结构
      串的顺序存储结构是用一组地址连续的存储单元来存储串值的字符序列。由于串中的元素为字符，所以可通过程序语言提供的字符数组定义串的存储空间，也可以根据串长的需要动态申请字符串的空间。

   2. 串的链式存储：块链
      串也可采用链表方式作为存储结构，当用链表存储串中的字符时，每个节点中可以存储一个字符，也可以存储多个字符，要考虑存储密度的问题。在链式存储结构中，节点大小的选择和顺序存储方法中数组空间大小的选择一样重要，它直接影响对串处理的效率。

   3. 串的模式匹配
      子串的定位操作通常称为串的模式匹配，它是各种串处理系统中最重要的运算之一。子串也称为模式串。

      1. 朴素的模式匹配算法（暴力匹配）
         朴素的模式匹配算法也称为布鲁特一福斯算法，其基本思想是：从主串的第一个字符起与模式串的第一个字符比较，若相等则继续逐个字符进行后续的比较，否则从主串的第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和主串中的一个连续的字符序列相等，则称匹配成功，否则称匹配失败。
         该算法在最好情况下匹配算法的时间复杂度为 O(n+m)，而在最坏情况下的时间复杂度为 O(n×m)。
      2. 改进的模式匹配算法
         改进的模式匹配算法又称为 KMP 算法，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回潮主串的指针，而是利用己经得到的“部分匹配”的结果，将模式串向后“滑动”尽可能远的距离，再继续进行比较。
         此算法的时间复杂度为 O(n+m)。

      补充以上内容

      1. 暴力匹配算法（Brute-Force）：
         • 这是一种简单直接的模式匹配算法。
         • 从主串的第一个字符开始，逐个比较主串和模式串的对应字符。
         • 如果某个字符不匹配，则主串和模式串的指针分别回溯到下一个位置再进行比较。
         • 如果模式串的指针达到末尾，表示匹配成功，返回匹配的起始位置。
         • 如果主串的指针达到末尾仍未匹配成功，则表示匹配失败。
         • 时间复杂度：最好情况O(m)，最坏情况O(n*m)，平均情况O(n+m),m是模式串，n是主串

      2. KMP算法（Knuth-Morris-Pratt）：
         • KMP算法利用模式串中的匹配信息，避免不必要的回溯。
         • 具体来说，KMP算法通过构建一个模式串的部分匹配表，即next数组。
         • next数组保存了模式串中不匹配时，应该回溯的位置。
         • 在匹配过程中，当某个字符不匹配时，根据next数组的值进行指针的调整。
         • 这样可以使得模式串指针不回溯到之前已经比较过的位置，提高匹配效率。

      这些是常见的串模式匹配算法，其中KMP算法相对于暴力匹配算法在时间复杂度上有更好的优化。但在具体的应用场景中，可以根据实际情况选择合适的算法来进行模式匹配操作。

   4. 串的前缀：包含第一个字符并且不包含最后一个字符的子串

      串的后缀：包含最后一个字符并且不包含第一个字符的子串

      第i个字符的next值=从1~i-1串中最长相等前后缀长度+1

      特殊情况：next[1]=0，next[2]=1

3.2 数组、矩阵和广义表

3.2.1 数组

1. 数组的定义及基本运算
   n维数组是一种“同构”的数据结构，其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。
   数组结构的特点是：数据元素数目固定；数据元素具有相同的类型；数据元素的下标关系具有上下界的约束且下标有序。
   对数组进行的基本运算有以下两种。
   （1）给定一组下标，存取相应的数据元素。
   （2）给定一组下标，修改相应的数据元素中某个数据项的值。

2. 数组的顺序存储
   一旦定义了数组，结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
   由于计算机的内存结构是一维线性的，因此存储多维数组时必须按照某种方式进行降维处理，即将数组元素排成一个线性序列，这就产生了次序约定问题。对二维数组有两种存储方式：一种是以列为主序的存储方式：另一种是以行为主序的存储方式。
   设每个数据元素占用L个单元，m、n为数组的行数和列数，$Loc(a_{1}1)$表示元素a11的地址，那么以行为主序优先存储的地址计算公式为

   $Loc(a_{ij})=Loc(a_{11})+((i-1)n+(j-1))L$

   同样的，以列为主序优先存储的地址计算公式为

   $Loc(a_{ij})=Loc(a_{1}1)+((j-1)m+(i-1))L$

【总结】

3.2.2 矩阵

1. 特殊矩阵
   若矩阵中元素（或非0元素）的分布有一定的规律，则称之为特殊矩阵。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。
   若矩阵$A_{n\times n}$中的元素特点为$a_{ij}=a_{ji}(1\le i,j\le n)$，则称之为n阶对称矩阵。
   若对称矩阵中的每一对元素仅占用一个存储单元，那么可将n^2个元素压缩存储到能存放n(n+1)2 个元素的存储空间中。不失一般性，以行为主序存储下三角（包括对角线）中的元素。假设以一维数组 B[n(n+1)/2]作为n阶对称矩阵A中元素的存储空间，则B[k](1≤k＜n(n+1)/2)与矩阵元素$a_{ij}(a_{ji})$之间存在者一一对应的关系，如下所示。

   $$y=\{\begin{array}{l}\frac{i(i-1)}{2}+j,i\ge j\\ \frac{j(j-1)}{2}+i,i＜j\end{array}\text{\hspace{1em}(1)}$$

   若以行为主序将n阶三对角矩阵$A_{n\times n}$的非0元素山存储在一维数组 B[k](1≤k≤3×n-2)中，则元素位置之间的对应关系为k=2i+j-2
   下标从0开始$k=2i+j+1$
   下标从1开始 $k=3\times (i-1)-1+j-i+1+1=2i+j-2,(1\le i，j\le n)$

2. 稀疏矩阵

   在一个矩阵中，若非0元素的个数远远少于0元素的个数，且非0元素的分布没有规律，则称之为稀疏矩阵。对于稀疏矩阵，存储非0 元素时必须同时存储其位置（即行号和列号)，所以三元组（i,j,a,）可唯一确定矩阵4中的一个元素。由此，一个稀疏矩阵可由表示非0元素的三元组及其行、列数唯一确定。图3-13所示的是一个6行7列的稀疏矩阵，其三元组表为((1,2,12),(1,3,9),3,1,-3),3,6,14),(4,3,24), (5,2,18),(6,1,15),(6,4,-7))。

【总结】

设有一个 n*n 的矩阵，若矩阵中的任意一个元素都有Ai,j= Aj,i 则该矩阵为对称矩阵
稀疏矩阵的三元组表的顺序存储结构称为三元组顺序表，
常用的三元组表的链式存储结构是十字链表。

设有一个的矩阵，若矩阵中的任意一个元素都有则该矩阵为对称矩阵

【做题技巧】
下方的公式都是基于存储的一维数组下标是从1开始的，在软考的题目里面是适用的。
如果一维数组的下标是从0开始的，那需要在后面补上一个减1。

• 对称矩阵按行存储下三角和主对角线并且下标从0(A_{0,0})开始

  • $$y=\{\begin{array}{l}\frac{i(i+1)}{2}+j+1,i\ge j\\ \frac{j(j+1)}{2}+i+1,i＜j\end{array}\text{\hspace{1em}(1)}$$

• 对称矩阵按行存储下三角和主对角线并且下标从1(A_{1,1})开始

  • $$y=\{\begin{array}{l}\frac{i(i-1)}{2}+j,i\ge j\\ \frac{j(j-1)}{2}+i,i\le j\end{array}\text{\hspace{1em}(1)}$$

• 三对角矩阵按行存储并且下标从0$(A_{0,0})$开始：$A_{i,j}=2i+j+1$

• 三对角矩阵按行存储并且下标从1$(A_{1,1})$开始：$A_{i,j}=2i+j-2$

• 验证答案：把题目中的值带入选项中，带0和1

3.2.3 广义表

广义表在往年考试中目前只出了一题，可以作为了解看看（如有其他习题，可在评论进行补充）

1. 设L为广义表，将head(L)定义为取非空广义表的第一个元素，tail(L)定义为取非空广义表除第一个元素外剩余元素构成的广义表。
   若广义表L=((x, y, z), a, (u, t, w))，则从L中取出原子项y的运算是 （62） 。（2009年上半年）
   （62） A. head(tail(tail(L))) B. tail(head(head(L)))
   C. head(tail(head(L))) D. tail(tail(head(L)))

3.3 树

3.3.1 树与二叉树的定义

3.3.1.1 树的定义及基本运算

树是(n≥0)个节点的有限集合，1=0 时称为空树，在任一非空树中：
(1) 有且仅有一个称为根的节点。
(2) 其余的节点可分为m(m≥0)个互不相交的子集下T，⋯，T,，其中每个子集本身又是一棵树，并称其为根节点的子树。
树的递归定义表明了树的固有特性，也就是一棵树由若干棵子树构成，而子树又由更小的子树构成。

树中的基本概念如下。
(1) 双亲和孩子。节点的子树的根称为该节点的孩子：该节点称为其子节点的双亲。
(2) 兄弟。具有相同双亲的节点互为兄弟。
(3) 节点的度。一个节点的子树的个数记为该节点的度。
(4) 叶子节点。也称为终端节点，指度为零的节点。
(5) 内部节点。度不为零的节点称为分支节点或非终端节点。除根节点之外，分支节点也称为内部节点。
(6) 节点的层次。根为第一层，根的孩子为第二层，以此类推。
(7) 树的高度。一棵树的最大层次数记为树的高度(或深度)。
(8) 有序(无序)树。若将树中的节点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树：否则称为无序树。
(9) 森林。是m(m≥0)棵互不相交的树的集合。

【考点】树的常考性质

1. 树中的结点数=总度数+1

2. 度为m的树、m叉树的区别

   度为m的树	m叉树
   任意结点的度≤m（最多m个孩子）	任意结点的度≤m（最多m个孩子）
   至少有一个结点度=m（有m个孩子）	允许所有结点的度都＜m
   一定是非空树，至少有m+1个结点	可以是空树

3. 度为m的树第i层至多有$m^{i-1}$个结点（i≥1）

4. 高度为h的m叉树至多有$\frac{m^h-1}{m-1}$个结点

5. 高度为h的m叉树至少有h个结点，高度为h、度为m的树至少有h+m-1个结点
   

6. 具有n个结点的m叉树的最小高度为$\lceil lo{g}_m(n(m-1)+1)\rceil$ 向上取整, 运算称为Ceiling，用数学符号⌈⌉ （上有起止，开口向下）表示,。 向下取整, 运算称为Floor，用数学符号⌊⌋

3.3.1.2 二叉树

1. 二叉树的定义
   二叉树(Binary Tree)是 n(n≥0)个节点的有限集合，它或者是空树(-0)，或者是由一个根节点及两棵互不相交的、分别称为左子树和右子树的二叉树所组成。
   二叉树与树的区别如下。

   • 二叉树的节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
   • 二叉树的节点的最大度为2，而树中不限制节点的度数。

   

3.3.2 二叉树的性质

1. 【考点】二叉树具有以下重要性质：

   1. 在二叉树的第i层上最多有$2^{i-1}$个结点（i＞=1），如二叉树的第三层上最多有4个结点。

   2. 深度为k的二叉树最多有$2^k-1个结点$（k＞=1），如深度为3的二叉树最多有7个结点。

   3. 对任何一棵二叉树，如果其叶子结点数为$n_0$，度为2的结点数为$n_2$，则$n_0=n_2+1$。

      设非空二叉树中度为0、1和2的结点个数分别为$n_0、n_1和n_2$，则$n_0=n_2+1$(叶子结点比二分支结点多一个)

      说人话：度为2的结点（该结点有两个分支）+1=叶子结点数（度为0的结点）

      总边数（从下往上）$B=n-1$=（从上往下）$B=n_2✖\stackrel{◯}{R}2+n_1✖\stackrel{◯}{R}1$
      

   4. 具有n个结点的完全二叉树的深$\lfloor lo{g}_{2}n\rfloor +1或\lceil lo{g}_2(n+1)\rceil$（⌊log₂n⌋表示不大于log_2n的最大整数），如具有9个结点的完全二叉树的深度为$\lfloor lo{g}_{2}9\rfloor +1=4$。$\lfloor lo{g}_{2}1024\rfloor +1=11$

   5. 对于完全二叉树，可以由结点数n推出度为0、1和2的结点个数为$n_0、n_1和n_2$

      1. 若完全二叉树有2k（偶数）个结点，则必有$n_1=1，n_0=k，n_2=k-1$
      2. 若完全二叉树有2k-1（奇数）个结点，则必有$n_1=0，n_0=k，n_2=k-1$

   6. 对一棵有n 个结点的完全二叉树(深度为$\lfloor lo{g}_{2}n\rfloor +1)$的结点按层序编号(从第1层到第$\lfloor lo{g}_{2}n\rfloor +1$层，每层从左到右)，每一层的结点个数恰好是上一层结点个数的二倍。因此，从一个结点的编号就可推知其父、左、右儿子、兄弟等结点的编号，如图 16-4 所示。例如，对于结点i有如下关系：

      1. 仅当i=1时,结点i为根节点;若i＞1,则结点i的双亲结点为⌊i/2⌋。
      2. 若 2i＞n,则结点i无左孩子，即结点i为叶子结点;若 2i≤n，则结点i的左孩子是结点 2i。
      3. 若2i+1＞n，则结点i无右孩子;若 2i+1≤n，则结点i的右孩子是结点 2i十1。
      4. 当i为奇数且不为1时,结点：的左兄弟是结点i-1,否则结点，无左兄弟。
      5. 当i为偶数且小于几时,结点i的右兄弟是结点i+1,否则结点。无右兄弟。

7. 具有n个结点的二叉树有$\frac{(2n)!}{(n+1)!\ast n!}$种

8. 二叉树的存储结构

   1. 顺序存储结构

      二叉树的顺序存储结构方法是将二叉树的所有结点，按照一定的线性次序存储到连续的存储单元中，使得结点在这个序列中的相互位登能反映出结点之间的逻辑关系。

      1. 完全二叉树的顺序存储结构
         在一棵具有n 个结点的完全二叉树中，从树根起，自上而下,逐层从左到右给所有结点编号，就能得到一个反映整个二叉树结构的线性序列，如图 16-5 所示．其中，每个结点的编号就作为结点的名称。
         将数组下标作为结点名称(编号),就可将二叉树中所有结点的标号存储在一个一维数组中。图16-5中的二叉树的顺序存储结构如图 16-6 所示。

         

      2. 一般二叉树的顺序存储结构

         对于一般的二叉树采用顺序存储时，为了能用结点在数组中的位置来表示结点之间的逻辑关系，也必须按近似满二叉树的形式来存储树中的结点。在最坏情况下，一个深度为k且只有k个结点的右单支树却需要长度为2^k-1的一维数组。例如，只有3 个结点的右单支树，如图 16-7（a)所示，添上一些实际不存在的虚结点后，成为一棵近似满二叉树，相应的顺序存储结构如图 16-7(b)所示。

         
         

         在最坏情况下，一个深度为k且只有k个结点的二叉树（单支树）需要$2^k-1$个存储单元。

      • 对于完全二叉树而言，顺序结构既简单又节省存健空间；对于一般的二叉数，顺序结构将造成存储空间的浪费，顺序结构适用于完全二叉树，一般二叉树更适合使用链式存储结构。

   2. 链式存储结构

      设计不同的结点结构可构成不同形式的链式存储结构。由二叉树的定义得知，二叉树的结点（如图16-8(a))由一个数据元素和分别指向其左、右于树的两个分支构成，则表示二叉树的链表中的结点至少包含3个域：数据域和左、右指针域，如图 16-8(b)所示。有时，为了便于找到结点的双亲，还可在结点结构中增加一个指向其双亲结点的指针域，如图 16-8©所示。利用这两种结点结构所得二叉树的存储结构分别称之为二叉链表和三叉链表，如图 16-9 所示。链表的头指针指向二叉树的根结点。在含有n个结点的二叉链表中有n+1个空链域。n个结点的三叉链表n+2个空指针域。

【考点】

• 顺序存储需要维护结点和左、右孩子的关系：结点编号为n，则左孩子为 2n，右孩子为2n+ 1。
• 链式存储有二叉链表和三叉链表。对于n个结点的二叉树，二叉链表的空指针为n + 1，三叉链表的空指针为n + 2。

3.3.3 二叉树的遍历

表16-2 遍历定义

先序遍历	中序遍历	后序遍历
若二叉树为空，则空操作，否则： （1）访问根节点 （2）先序遍历左子树 （3）先序遍历右子树	若二叉树为空，则空操作，否则： （1）中序遍历左子树 （2）访问根节点 （3）中序遍历右子树	若二叉树为空，则空操作，否则： （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根节点

例题 图16-17（a）所示二叉树进行先序、中序和后序遍历，并写出对应的遍历序列

（1)对二叉树进行先序遍历,访问节点的先后次序如园 16-17(b)序号顺序所示，二叉树的先序序列为ABDCEF。
(2)对二叉树进行中序遍历,访问节点的先后次序如园 16-17©序号顺序所示,二叉树的中序序列为DBAECF。
(3)对二叉树进行后序這历,访问节点的先后次序如图 16-17(d)序号顺序所示,二叉树的后序序列为DBEFCA。

• 技巧（遍历二叉树比作开门）
• 

2. 根据遍历序列确定二叉树

   由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树。

   1. 根据先序序列和中序序列确定二叉树

      由先序序列确定根；由中序序列确定左右子树

      已知二叉树的先序和中序序列，构造出相应的二叉树

      先序：A B C D E F G H I J

      中序：C D B F E A I H G J

      解：1、由先序知根为A，则由中序知左子树CDBFE，右子树IHGJ

      

      2、再分别在左、右子树的序列中找出根、左子树、右子树序列

      

      3、以此类推，直到得到二叉树

      

   2. 根据后续序列和中序序列确定二叉树

   • 例题：已知一颗二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，请画出这两棵二叉树。

     (1)由后序遍历特征,根结点必在后序序列尾部，即根结点是A;
     (2)由中序遍历特征，根结点必在其中间,而且其左部必全部是左于树子孙(BDCE),其右部必全部是右子树子孙(FHG)；
     (3)继而,根据后序中的 DECB 子序列可确定B为 A的左孩子,根据 HGF 子序列可确定F为A的右孩子;依此类推,可以唯一地确定一棵二叉树，如图16-19 所示。
     

     点拔：

     由一棵二叉村的先序序列和后序序列不能唯一确定一棵二叉树,因为无法确定左右于树两部分。例如，如果有先序序列 AB,后序序列 BA,可以确定A 为根结点,但无法确定B为左子树还是右于树。

3.3.4 线索二叉树

若n个节点的二叉树采用链表作存储结构，则链表中含有 n+1 个空指针域，利用这些空指针域来存放指向节点的前驱和后继信息。线索链表的节点结构如图3-6所示。

若二叉树的二叉链表采用图8-6 所示的节点结构，则相应的链表称为线索链表，其中指向节点前驱、后继的指针称为线索，加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。

平衡二叉树或者是空树，或者是具有如下特征的二叉排序树：

(1)左子树和右子树的深度之差的绝对值不超过1

(2)左子树和右子树也是平衡二叉树；

若将二叉树上结点的平衡因子(Balance Factor,BF)定义为该结点左子树和右子树的深度之差，则平衡二叉树上所有结点的平衡因子只可能是一1、0 和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。图 16-35 所示为两棵平衡二叉树，而图 16-36 所示为两棵不平衡的二叉树，结点中的值为该结点的平衡因子。

【上面了解即可，考点如下】

• 平衡二叉树：二叉树中的任意一个结点的左右子树高度之差的绝对值不超过 1。
  • 关注分支结点即可，叶子结点满足上述要求。
• 二叉排序树：
  • 根结点的关键字大于左子树所有结点的关键字，小于右子树所有结点的关键字，左右子树也是一颗二叉排序树。【大左右小】
  • 中序遍历得到的序列是有序序列
• 最坏的查找情况是单枝树（即高度ℎ为n）要查找ℎ。

3.3.5 最优二叉树（哈夫曼树）

哈夫曼树(Huffman tree)又称最优二叉树，是一类带权路径长度最短的二叉树。哈夫曼树的定义，涉及路径,路径长度、权等概念，下面先给出这些概念的定义。

(1)路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

(2)路径长度：路径上的分支数目称作路径长度。

(3)树的路径长度：从树根到每一结点的路径长度之和。

(4)权：赋子某个实体的一个量，是对实体的某个或某些属性的数值化描述。在数据结构中,实体有结点(元素）和边(关系）两大类，所以对应有结点权和边权。如果在一棵树中的结点上带有权值，则对应的就有带权树等概念。

(5)结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。

(6)树的带权路径长度：树中所有叶于结点的带权路径长度之和，通常记作$WPL=\sum _{k=1}^n{W}_{kLk}$ 。

（7)哈夫曼树：假设有 m 个权值(w₁，w₂,⋯，w_m)，可以构造一棵含n个叶子结点的二叉树，每个叶子结点的权为w_i，则其中带权路径长度 WPL 最小的二叉树称作最优二叉树或哈夫曼树。

例题：图16-27中所示的3棵二叉树，都含4个叶子结点a、b、c、d，分别带权7、5、2、4，其中为哈夫曼树的是？

它们的带权路径长度分别为：
(a)树：WPL=7×2+5×2+2×2+4×2=36
(b)树：WPL=7×3+5×3+2×1+4×2=46
©树：WPL=7×1+5×2+2×3+4×3=35
其中，©树的 WPL 最小,可以验证，它就是哈夫曼树。

【做题画法】

• 从前往后找两个权值最小
• 小左大右
• 加入末尾
• 权值相同从前往后
• 用时再调

【考点】

• 二叉树具有以下性质：度为2的结点(双分支结点)数比度为0(叶子结点)数正好少1。而根据最优二叉树(哈夫曼树)的构造过程可知，最优二叉树中只有度为2和0的结点，因此，其结点总数为2n-1。
• 哈夫曼树中权值最小的两个结点互为兄弟节点
• 哈夫曼树中叶子结点的权值越小则距离树根越远、叶子结点的权值越大则距离树根越近
• 码长：$2^x\ge 字符个数$，例如有a,b,c,d,e,f6个字符，则该文件中的字符码长应为3,$2^x\ge 6，则x=3$

二叉树类别

3.4 图

3.4.1 图的定义与存储

1. 图的定义

   图(Graph)G 由V 和E两个集合组成，记为G=(V,E)。其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集合，这些顶点偶对称为边。通常，也将图G 的顶点集合和边集合分别记为V(G)和 E(G)。E(G)可以是空集，此时图G 中只有顶点而没有边。

2. 有向图

   若图G 中的每条边都是有方向的,则称G 为有向围，如图 20-1(a)所示。在有向图中，顶点对<x,y>是有序的，它称为从顶点x到顶点y的一条有向边。因此，<x,y>和<y,x>是不同的两条边。顶点用一对尖括号括起来，x是有向边的始点，y是有向边的终点，<x,y>也称作一条弧，x为弧尾，y为弧头。

3. 无向图

   若图G中的每条边都是没有方向的，则称G 为无向图，如图 20-1(b)所示。在无向图中，顶点对(x,y）是无序的，它称为顶点x和顶点y相关联的一条边。这条边没有特定的方向，在无向图中(x,y）和(y,x)是同一条边。顶点用一对圆括号括起来。

   

• 无论是无向图还是有向图，顶点数为n，边数为e，则所有顶点的度数之和为2e

---

1. 子图：假设有两个图G=(V,E)和G’=(V’,E’)，如果$V^{\prime }\subseteq V$且$E^{\prime }\subseteq E$，则称G’为G的子图。图20-2所示为图20-1中有向图G₁和无向图G₂子图的一些例子。Graph图=(Vertex顶点,Edge边)

   

2. 无向完全图和有向完全图：对于含有n个顶点的无向图,若具有n(n一1)/2条边，則称为无向完全图。对于含有n个顶点的有向图,若具有n(n一1)条弧，则称为有向完全图。

3. 稀疏图和稠密图：有很少条边或弧（如$e<nlo{g}_{2}n$，n为顶点个数）的图称为稀疏图，反之称为稠密图。

4. 权和图：在实际应用中，每条边可以标上具有某种含义的数值，该数值称为该边上的权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。

5. 邻接点：对于无向图G，如果图的边$(v,v^{\prime })\in E$，则称为定点v和v’互为邻接点。边(v,v’)依附于顶点v和v‘ ，或者说边(v,v’)与顶点v和v’相关联。【废话】

   【白话】有边/弧相连的两个顶点之间的关系；存在$(v_i,v_j)，则称v_i和v_j互为邻接点，存在<v_i,v_j>，则成v_i邻接到v_j，v_j邻接于v_i$

   （无向图），<有向图>

6. 度、入度和出度：顶点v的度是指和v相关联的边的数目，记为TD(v)。例如，图20-1(b)中顶点v_3的度是3。

   

   对于有向图，顶点 v的度分为度和出度。入度是以顶点，为头的弧的数目，记为ID(v);出度是以顶点，为尾的弧的数目，记为 OD(v)。顶点v的度为TD(v)=ID(v)+ OD(v)。例如，图 20-1(a)中$G_1的顶点v_1的入度ID(v_1)=1,出度OD(v_1)=2,顶点V_1的度为TD(v_1)=ID(v_1)+OD(v_1)=3$。一般地，$如果顶点v_i的度记为TD(v_i)$,那么一个有n个顶点，e条边的图，满足如下关系：$e=\frac{1}{2}{\sum }_{i=1}^{n}TD(v_i)$

7. 路径和路径长度：在无向图G中，从顶点v到顶点v‘的路径是一个顶点序列$（v=v_{i,0}，v_{i,1}，...,v_{i,m}=v^{\prime })，其中(vi,j-1,vi,j)\in E,1\le j\le m$。如果G是有向图，则路径也是有向的，顶点序列应满足$<vi,j-1,vi,j>\in E,i\le j\le m$。路径长度是一条路径上经过的边或弧的数目。

8. 回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环。

9. 简单路径、简单回路或简单环：序列中顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

10. 连通、连通图和连通分量：在无向图G中，如果从顶点v到顶点v‘有路径，则称v和v’是连通的。如果对于图中任意两个顶点$v_i,v_j\in V,v_i和v_j$都是连通的，则称G是连通图。图20-3（b）中的$G_2$就是一个连通图，而图20-3（a）中的$G_3$是非连通图，但$G_3$有2个连通分量，如图20-3（b)所示。所谓连通分量，指的是无向图中的极大连通子图。

    非连通无向图的边数=n(n-1)/2+1
    

11. 强连通图和强连通分量：在有向图G中，如果任意两个顶点都连通，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。图20-1（a）中$G_1$不是强连通图，它有两个强连通分量，如图20-4所示。

    • 连通图(无向图)最少：n-1，最多$\frac{n(n-1)}{2}$
    • 强连通图(有向图)最少n，最多n(n-1)

12. 连通图的生成树：一个极小连通子图,它含有图中全部顶点，但只有足以构成一棵树的n-1条边,这样的连通子图称为连通图的生成树。图20-5 所示为$G_3$中最大连通分量的一棵生成树。如果在一棵生成树上添加一条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。

13. 有向树和生成森林：有一个顶点的入度为0，其余顶点的入度均为1的有向图称为有向树。一个有向图的生成森林是由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。图 20-6 所示为其一例。

3.4.1.2 图的存储结构

1. 邻接矩阵表示法

   邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：
   $$A[i][j]=\{\begin{array}{l}1,若<v_i,v_j>或(V_i,V_j)\in E\\ 0,反之\end{array}$$
   例如，图20-1中所示的G1和G2的邻接矩阵如图20-7所示。

   

   i表示行，j表示列，由i指向j

   

   特别：完全图的邻接矩阵中，对角元素为0，其余为1

   

   1. 有向图的邻接矩阵可能是不对称的。
   2. 顶点的出度=第i行元素之和
   3. 顶点的入度=第i列元素之和
   4. 顶点的度= 第i行元素之和+第i列元素之和

   • 点拔：无向图的邻接矩阵是对称矩阵。

   如G是网，则邻接矩阵可以定义为：

$$A[i][j]=\{\begin{array}{l}{w}_{i,j}若<v_i,v_j>或(V_i,V_j)\in E\\ \infty 反之\end{array}$$
其中，$w_{i,j}$表示边上的权值；∞表示计算机允许的、大于所有边上权值的数。例如，图20-8所示为一个有向图和它的邻接矩阵。

• 点拔

 > 在使用邻接矩阵表示图时，在不带权的图中,0表示两个点之间不连通，1表示两点连通。
 > 在带权的因中，若两点之间不连通，則用∞表示,两点连通則直接在邻换矩阵中相应位置上标注权值可。		

用邻接矩阵表示法表示图，除了一个用于存储邻接矩阵的二维数组外，还需要用一个一维数组来存储顶点信息。

2. 采用邻接矩阵表示创建无向图

   已知一个图的点和边，使用邻接矩阵表示法来创建此图的方法比较简单，下面以一个无向网为例来说明创建图的算法。

   【算法】

   【算法分析】

   该算法的时间复杂度为$O(n_2)$。

3. 邻接矩阵表示法的优缺点

   1. 优点

      1. 便于判断两个顶点之间是否有边，即根据A[i][j]=0或1来判断。
      2. 便于计算各个顶点的度。对于无向图，邻接矩阵第i行元素之和就是顶点i的度；对于有向图，第i行元素之和就是顶点i的出度，第i列元素之和就是顶点i的入度。

   2. 缺点

      1. 不便于增加和删除顶点
      2. 不便于统计边的数目，需要扫描领接矩阵所有元素才能统计完毕，时间复杂度为$O(n^2)$。
      3. 空间复杂度高。如果是有向图,n个顶点需要n^2个单元存储边。如果是无向图，因其邻接矩阵是对称的，所以对规模较大的邻接矩阵可以采用压缩存储的方法，仅存储下三角(或上三角）的元素，这样需要n(n-1)/2个单元即可。但无论以何种方式存储，邻接矩阵表示法的空间复杂度均为 $O(n^2)$,这对于稀疏图而言尤其浪费空间.

例题：

---

1. 邻接表表示法

   邻接表是图的一种链式存储结构，链接表由两部分组成：表头结点表和边表。

   一个图的邻接矩阵表示是唯一地，但其邻接表表示不唯一。

2. 采用邻接表表示法创建无向图

   【算法】

   【算法分析】

   该算法的时间复杂度是O(n+e)。建立有向图的邻接表与此类似，每读入一个顶点对序号<i,j>，仅需生成一个邻接点序号为j的边表结点，并将其插入到v_i的边链表头部即可。若要创建网的邻接表，可以将边的权值存储在数据域中。

3. 邻接表表示法的优缺点

   1. 优点

      1. 便于增加和删除顶点
      2. 便于统计边的数目，按顶点表顺序扫描所有边表可得到边的数目。
      3. 空间效率高。对于一个具有n个顶点e条边的图G,若G 是无向图，则在其邻接表表示中有n个顶点表结点和 2e 个边表结点;若G是有向图，则在其邻接表表示中有 n 个顶点表结点和。个边表结点。因此,邻接表表示的空间复杂度为 O(n十e),适合表示稀疏图。

   2. 缺点

      1. 不便于判断顶点之间是否有边
      2. 不便于计算有向图各个顶点的度

3.4.1.3 考点

图的概念

• 无向图：连接顶点的边是无向边
• 有向图：连接顶点的边是有向边（弧）
• 无向完全图有条$\frac{n(n-1)}{2}$边
• 有向完全图有条n*(n-1)边
• 有向图和无向图的所有顶点度数之和为2e。（e 为边数）
• 有向图和无向图的边数$e=\frac{顶点度数之和}{2}$
• 连通图：无向图中任意两个顶点之间都有路径，最少有n-1条边，最多有$\frac{n(n-1)}{2}$条边
• 强连通图：有向图中任意两个顶点之间都有路径，最少n条边，最多有n*(n-1)条边

邻接矩阵和邻接表

• 邻接矩阵
  • 邻接矩阵更适合存储稠密图（边数很多的图）
  • 完全图（每个顶点都和剩余的顶点有一条边）更适合采用邻接矩阵存储
  • 无向图邻接矩阵：非零元素个数为 2e（e 为边数）
  • 无向图的邻接矩阵是对称矩阵
  • A[i][j]=1 表示顶点 i 和顶点 j 之间有一条无向边
  • A[i][j]=0 表示顶点 i 和顶点 j 之间没有边
  • 对于无向图，顶点 i 的度等于邻接矩阵第 i 行（列）中非零元素个数
  • 有向图邻接矩阵：非零元素个数为 e（e 为边数）
    • 有向图的邻接矩阵不一定是对称矩阵
  • A[i][j]=1 表示顶点 i 和顶点 j 之间有一条有向边
  • A[i][j]=0 表示顶点 i 和顶点 j 之间没有边
  • 对于有向图，顶点 i 的出度等于第 i 行非零元素个数，入度等于第 i 列非零元素个数，顶点 i的度=顶点 i 的出度+入度
• 邻接表
  • 邻接表更适合存储稀疏图（边数很少的图）
  • 无向图采用邻接表存储有 2e 个表结点（e 为边数）
  • 有向图采用邻接表存储有 n+e 个表结点（n 为结点数，e 为边数）

3.4.2 图的遍历

3.4.2.1 深度优先搜索

深度优先搜索(Depth First Seareh.DFS)遍历类似于树的先序遍历;是树的先序通历的推广。对于一个连通图，深度优先遍历的过程如下：
(1)从图中某个顶点 v出发,访问V。
(2)找出刚访问过的顶点的第一个未被访问的邻接点，访问该顶点，以该顶点为新顶点，重复此步骤，直至刚访问过的顶点没有未被访问的邻接点为止。
(3)返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。
(4)重复步骤(2）和(3），直至图中所有顶点都被访问过,遍历结束。
以图 20-15(a)中所示的无向图 G。为例，深度优先搜崇遍历图的过程如图 20-15(b)所示。

(1)从顶点v₁出发,访问v₁。
(2)在访问了顶点v₁之后,选择第一个未被访问的邻接点 v₂，访问v₂，以v₂为新顶点,重复此步，访问v₄，v₈，v₅。在访问了v₅之后,由于v₅的邻接点都已被访问,此步结束。
(3)搜索从v₅回到 v₈由于同样的理由，搜索继续回到v₄，v₂直至v₁此时由于 v₁的另一个邻接点未被访问，则搜索又从v₁到v₃,再继续进行下去。由此，得到的顶点访问序列为：
v₁ -> v₂ ->v₄ -> v₈ ->v₅ -> v₃ ->v₆->v₇
图 20-15(b)中所示的所有顶点加上标有实箭头的边，构成一棵以v₁为根的树，称为深度优先生成树，如图 20-16所示。

3.4.2.2 广度优先搜索

广度优先搜索(Breadth First Search,BFS)遍历类似干树孩层次边遍历的过程，广度优先搜索遍历的过程如下：

1. 从图中某个顶点，出发,访问V。
2. 依次访问，的各个未曾访问过的邻接点。
3. 分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。
4. 重复步骤(3），直至图中所有已被访问的顶点的邻接点都被访问到。
   例如，对图G。进行广度优先搜索遍历的过程如图 20-17 所示，具体过程如下。

【总结考点】

• 广度、深度优先遍历采用邻接矩阵存储时间复杂度为$O(n^2)$
• 广度、深度优先遍历采用邻接表存储时间复杂度为O(n+e)。
  （其中 n 为顶点数，e 为边数）
• 使用队列对图进行广度优先遍历

3.4.4 拓扑排序和关键路径

1. AOV网

   在有向图中，若一顶点表示活动，用有向边表示活动之间的优先关系，则称这样的有向图为以顶点表示活动的网，简称 AOV网。
   在 AOV 网中不应出现有向环。不存在回路的 AOV 网称为有向无环图或 DAG 图。检测的方法是对有向图构造其从顶点开始的拓扑有序序列，若图中所有顶点都在它的拓扑有序序列中，则该 AOV 网中必定不存在环。
   

2. 拓扑排序及其算法
   拓扑排序的时间复杂度为O(n+e)。

【考点】
在有向无环图 G 的拓扑序列中，顶点$v_i$在$v_j$之前，则：
可能存在弧$<v_i,v_j>$，一定不存在弧$<v_j,v_i>$。
可能存在$v_i$到$v_j$的路径，一定不存在$v_j$到$v_i$的路径

3.4 总结

1. 图的存储方式有两类：①以边集合方式表示的邻接矩阵;②以链接方式表示的邻接表、十字链表和邻接多重表。
2. 图的通历有深度优先搜索遍历和广度优先搜索遍历两种。深度优先搜索遍历借助栈结构实现,广度优先搜索遍历借助队列结构实现。
3. 构造最小生成树的算法有普里姆算法和克鲁斯卡尔算法两种,其中普里姆算法适合求稠密网的最小生成树，克鲁斯卡尔算法适合求稀疏网的最小生成树。
4. 求最短路径的算法有两种：①迪杰斯特拉算法用于求源点到各顶点的最短路径;②弗洛供德算法用于求每一对顶点之间的最短路径。

---

ps：感谢您在万众文章中阅读了鄙人的笔记，谢谢
这一篇的笔记是真的很难整理 ε(┬┬﹏┬┬)3 ！！！由于本人用的是MWeb Pro书写markdown笔记，markdown的数学公式与此网站的格式不同，需要手动修改很多公式的格式，如果有出现格式问题，麻烦在评论区指出，谢谢ｂ（￣▽￣）ｄ！

---

这份笔记由我在备考软件设计师中级考试的过程中编写，包含了我对知识点的理解与总结。如果您觉得这份笔记对您有帮助，并希望分享给更多的人，我十分乐意。但请在转载时务必注明出处，以尊重作者的劳动成果，感谢您的理解与支持。

在此特别强调，本人编写笔记的所需部分资源均源于网络公开资源，旨在为大家提供一个学习和交流的内容，未经原作者授权，如若不慎侵犯您的合法权益，请您立即通过有效联系方式通知我，并附上相关证明材料。一旦核实无误，我将在第一时间删除涉事资源，全力保障您的合法权利不受损害。

---

• 每篇一句：“只要自己沉得住气，那些看似不起波澜的日复一日，终会在未来的某天里，让你看到坚持的意义。”
• 如果觉得对您有用，请点个赞或者收藏鼓励我持续更新吧！
• 恭喜您，已挑战成功第三关上，请前往第三关下进行挑战吧【点击即可跳转】