1 00:00:00,000 --> 00:00:04,080 大家好。 2 00:00:04,080 --> 00:00:11,260 数据结构与算法这一讲我们学习第十二章。 高级数据结构中的广义表。 3 00:00:11,260 --> 00:00:17,530 那我们会介绍广义表的一些概念,以及它的存储和便利的算法。 4 00:00:17,530 --> 00:00:25,330 那我们来看一下, 广义表它跟和线性表的一个关系。 5 00:00:25,330 --> 00:00:30,570 以前的线性表呢,它的表元素都是整齐化一的,同一种数据类型。 6 00:00:30,570 --> 00:00:35,170 甚至我们可以看到它的存储的这个长度也是一致的。 7 00:00:35,170 --> 00:00:40,620 那在有些情况下,我们可能这么一个线性的序列。 8 00:00:40,620 --> 00:00:47,780 它里面的这个表元素可能是具有不同的数据类型,比如说整型啊,然后字符型啊。 9 00:00:47,780 --> 00:00:51,990 而且呢这个表中,可能还有子表。 10 00:00:51,990 --> 00:00:57,120 这样的情况呢,我们就需要广义表来表达它。 11 00:00:57,120 --> 00:01:03,810 广义表呢,它这么一个表达呢,你看起来像是一个线性的。 12 00:01:03,810 --> 00:01:09,330 但是我们这个里面的元素, 它可能有不同的类型。 13 00:01:09,330 --> 00:01:14,780 有一些这个元素,它是不可分的,那我们叫做原子。 14 00:01:14,780 --> 00:01:24,065 还有一些元素,它可能自己就是子表。 那对于这个广义表,因为我们很可能 15 00:01:24,065 --> 00:01:28,790 在别的地方还要引用它,所以我们往往是要给它一个命名。 16 00:01:28,790 --> 00:01:36,730 另外呢,这个表,它的顶层的这个个数我还是应该是确定的。 17 00:01:36,730 --> 00:01:42,100 那这就是,表的长度。 18 00:01:42,100 --> 00:01:46,345 因为有子表的情况,那如果说这个子表,也是像我们现在顶层的 19 00:01:46,345 --> 00:01:50,590 这个广义表这样,一层层给它展开的话, 20 00:01:50,590 --> 00:01:56,580 它很可能有很多层的括号,那这也就是广义表的深度。 21 00:01:56,580 --> 00:02:03,570 如果你是一个递归的情况呢,那可能深度就是无穷的。 那我们 22 00:02:03,570 --> 00:02:11,060 来看这个广义表这样两个重要的概念就是表头和表尾。 23 00:02:11,060 --> 00:02:16,605 表头是广义表的第一个元素,把原来的这个广义表, 24 00:02:16,605 --> 00:02:22,150 它是要包掉一层括号以后,这个x0是它的第一个元素。 25 00:02:22,150 --> 00:02:26,165 这个元素,如果它是原子,那它就是原子 26 00:02:26,165 --> 00:02:30,180 如果它是子表,那我们就是它就是原来这个子表包出来的表头。 27 00:02:30,180 --> 00:02:36,890 那表尾呢,其实可以看作是把这个表头删掉以后, 28 00:02:36,890 --> 00:02:42,690 其它的元素组成的这个新的子表,因此这个表尾你看它是要带上括号的。 29 00:02:42,690 --> 00:02:49,920 这样的定义以后呢,我们就可以很方便地来表达这个广义表。 30 00:02:49,920 --> 00:02:53,930 那我们,可以用这样的一个递归的定义, 31 00:02:53,930 --> 00:02:58,770 能够来对它来进行存储的表达, 32 00:02:58,770 --> 00:03:03,610 以及我们在算法上头呢,其实也是可以利用这样一个结构, 33 00:03:03,610 --> 00:03:10,000 也就是我先处理好这个表头节点,处理完了以后它脱离这个广义表。 34 00:03:10,000 --> 00:03:16,470 然后我用刚才这个策略呢, 去递归地处理其它剩下的元素 35 00:03:16,470 --> 00:03:22,940 所组成的广义表,那就是一个一个的把它包离出来,最后这个广义表就处理完了。 36 00:03:22,940 --> 00:03:28,090 那我们来看广义表的一些形态。 37 00:03:28,090 --> 00:03:31,280 首先呢,最简单的就是纯表。 38 00:03:31,280 --> 00:03:36,610 那这个纯表呢,从我们这个广义表的根结点出发。 39 00:03:36,610 --> 00:03:41,930 我们到达任何一个叶的这样结点呢, 40 00:03:41,930 --> 00:03:46,530 它都是只有一条路径,也就是说这些路径呢它不能够有重入, 41 00:03:46,530 --> 00:03:54,350 也就是任何一个点, 它没有两个指向它的边。 42 00:03:54,350 --> 00:03:58,930 还有一种表呢,就是可重入的, 43 00:03:58,930 --> 00:04:03,440 这种情况呢,譬如像这边这个L1 44 00:04:03,440 --> 00:04:08,060 它就是呢,被两个这个上级的子表, 45 00:04:08,060 --> 00:04:12,680 引用了,那就是呢,它是重入的。 46 00:04:12,680 --> 00:04:20,870 那如果这个重入表,它并没有, 形成一个圈,就是没有这样一个循环的结构呢, 47 00:04:20,870 --> 00:04:28,450 那我们就是一个相当于DAG,也就是有效无环图的这么一个结构, 48 00:04:28,450 --> 00:04:35,200 对于这样的一个表呢,我可以看到它包含回路, 49 00:04:35,200 --> 00:04:42,060 这个时候,如果我一层层展开的话,你是可以无穷无尽地去展开的, 50 00:04:42,060 --> 00:04:49,110 因此这个循环表的深度是无穷大,那我们看这里面有两个回路, 51 00:04:49,110 --> 00:04:52,770 第一个回路呢,就是这个L4这个子表, 52 00:04:52,770 --> 00:04:59,720 它是由元素d和L4自身组成的,它就形成了一个自循环, 53 00:04:59,720 --> 00:05:04,065 而这个 L1和L2呢,它是互相指向, 54 00:05:04,065 --> 00:05:08,410 然后形成了一个间接指向的循环。 55 00:05:08,410 --> 00:05:16,680 那我们再来看这个广义表的形式。 其实我们看这个最大的再入表, 56 00:05:16,680 --> 00:05:22,380 它其实里面由各个不同的子表组成, 57 00:05:22,380 --> 00:05:30,300 你可以一层层地来包, 表E它是由表B和表D组成, 58 00:05:30,300 --> 00:05:37,080 那D呢是这样一个独立的表, 然后B呢就是这样一个表。 59 00:05:37,080 --> 00:05:42,130 然后我们也可以看到, 60 00:05:42,130 --> 00:05:47,180 像表D里面它还要引用表B, 61 00:05:47,180 --> 00:05:52,500 也就是说E呢D呢都指向了B。 62 00:05:52,500 --> 00:05:57,820 就是说B其实是一个再入的一个结构了, 63 00:05:57,820 --> 00:06:04,890 在这个表里面呢,我们对这种可重入的情况,我们都是要对这个子表, 64 00:06:04,890 --> 00:06:09,310 进行一个标号,那比如说这边这个子表B,它第一次出现的时候, 65 00:06:09,310 --> 00:06:13,730 我可以把它展开,就是6,2。 66 00:06:13,730 --> 00:06:20,440 那后面的出现呢,我们就只需要引用它这样的一个名字。 67 00:06:20,440 --> 00:06:27,150 不需要再对它扩展的展开了,这种情况呢对于这种循环递归表是特别有用的。 68 00:06:27,150 --> 00:06:33,920 表F它自身组成了这么一个循环的递归表。 69 00:06:33,920 --> 00:06:38,250 那我们可以看到, 70 00:06:38,250 --> 00:06:42,900 刚才这个图里面呢,我们看到的这些结构, 71 00:06:42,900 --> 00:06:47,550 它其实本质上,我们还可以对应到, 72 00:06:47,550 --> 00:06:54,040 以前学过的这个图的结构,当然除了那个自环的情况, 73 00:06:54,040 --> 00:07:00,530 我们那个原来的图,我们是消除了自环的,我们对这个图呢进行一些限制, 74 00:07:00,530 --> 00:07:05,390 也就是说它有这种再入的情况,那就是再入表。 75 00:07:05,390 --> 00:07:09,310 然后呢,我不允许再入,我就变成了一个纯表。 76 00:07:09,310 --> 00:07:15,820 然后这个纯表,如果是退化成一个线性的纯表, 77 00:07:15,820 --> 00:07:20,555 我们可以看到这上面有一个表的顶点,然后呢其它的这个元素呢, 78 00:07:20,555 --> 00:07:29,950 都是在同一层,就是直接这个根底下铺开, 那就是一个线性表,它们是有一些包含的关系的, 79 00:07:29,950 --> 00:07:34,720 那递归表呢,它是一种带回路的一种特殊的再入表。 80 00:07:34,720 --> 00:07:40,470 广义表在很多场景下都有应用,例如函数的调用。 81 00:07:40,470 --> 00:07:45,010 你可以把这些函数呢,当作一个子表, 82 00:07:45,010 --> 00:07:49,550 那函数里面,可能还有几层,调用几个函数。 83 00:07:49,550 --> 00:07:54,605 另外呢,就是这个函数里面其他的一些功能块, 84 00:07:54,605 --> 00:07:59,660 你可以把它当作原子,也就是说它不可能再扩展为子表,再调用别的东西了, 85 00:07:59,660 --> 00:08:05,430 还有内存空间的这种指针的引用关系,其实也可以看成广义表的一个结构, 86 00:08:05,430 --> 00:08:11,080 有一种人工智能的语言,叫做LISP语言, 87 00:08:11,080 --> 00:08:19,030 它就是很多很多嵌套的括号, 广义表的存储结构,首先我是要区分, 88 00:08:19,030 --> 00:08:23,540 子表和原子,因为原子它就不需要展开了。 89 00:08:23,540 --> 00:08:29,960 那如果我看到这麽一个子表的呢,显然我不能在这一层就给它展开。 90 00:08:29,960 --> 00:08:34,750 我需要再去扩展,对这个子表有一个这样的表达, 91 00:08:34,750 --> 00:08:40,620 那在这种情况下呢,我们是没有带表头, 92 00:08:40,620 --> 00:08:48,210 那如果是我要删除这个结点data, 那我就是需要遍历变异整个广义表。 93 00:08:48,210 --> 00:08:52,480 而且呢,把这个指向data的指针呢, 94 00:08:52,480 --> 00:08:56,940 都给它找到。也就是说, 95 00:08:56,940 --> 00:09:01,400 引用这个data作为第一个元素开始的表向。 96 00:09:01,400 --> 00:09:08,580 那我们都找到了以后呢,修改它们这个指针,成为这个data之后的下一个元素。 97 00:09:08,580 --> 00:09:15,460 然后我们才能够完成这样的一个删除,然后我们把这么一个结点给释放。 98 00:09:15,460 --> 00:09:19,360 这样显然它是不太方便的。 99 00:09:19,360 --> 00:09:23,885 因此呢我可以考虑加入一个表头结点, 100 00:09:23,885 --> 00:09:28,410 来代表这个整个子表的开始。 101 00:09:28,410 --> 00:09:33,075 那因此我们的状态呢,就成为有三个值的这么一个标签。 102 00:09:33,075 --> 00:09:37,740 那就是原子呢,是这个head等于0。 103 00:09:37,740 --> 00:09:43,045 然后子表的占位符,是head等于1。 104 00:09:43,045 --> 00:09:48,350 然后呢这个子表开始的那个结点, 105 00:09:48,350 --> 00:09:53,200 它其实是一个虚结点,就是虚的头结点。 106 00:09:53,200 --> 00:10:00,610 那我们把它标志为-1,那这样标志以后,我对这个子表,我还是删除元素data, 107 00:10:00,610 --> 00:10:07,850 找到了这个data以后,我可以直接的从子表里面给它删除。 108 00:10:07,850 --> 00:10:15,105 因为整个这个子表, 它的他引关系,也就是说别人指向它的这些关系呢, 109 00:10:15,105 --> 00:10:20,250 它都通过这个表头给顶住了,能够把这些信息很好地保持。 110 00:10:20,250 --> 00:10:28,220 那只要在这个子表里面,把这个data的这个元素给删掉就行,它可以化简很多的这个操作。 111 00:10:28,220 --> 00:10:33,375 那我们再看一下,带表头的情况下, 112 00:10:33,375 --> 00:10:38,530 我们对这么一个循环的广义表的一个遍历操作。 113 00:10:38,530 --> 00:10:45,500 那这个遍历操作呢,有点像我们在图里面的伸收的遍历。 114 00:10:45,500 --> 00:10:50,840 那我从这个表的第一个元素开始, 115 00:10:50,840 --> 00:10:55,380 然后如果是一个原子呢, 116 00:10:55,380 --> 00:10:59,920 我就是把它给打印出来,接着再看下一个元素。 117 00:10:59,920 --> 00:11:04,060 如果它是个子表,那我就是要 118 00:11:04,060 --> 00:11:08,200 深入到这个子表里面,然后再去伸收遍历它 119 00:11:08,200 --> 00:11:14,430 的这个相应的这个元素。那这里呢,我们可以看到 120 00:11:14,430 --> 00:11:20,660 这个元素它还是指向一个子表,所以我们又深入到下一层这个子表。 121 00:11:20,660 --> 00:11:28,690 然后我们遍历完这个子表以后呢, 那整个这个外层表的 122 00:11:28,690 --> 00:11:35,890 第一个这个子表就遍历完了。我们就继续深入到, 123 00:11:35,890 --> 00:11:39,920 它的这个第二个这个子表占位符。 124 00:11:39,920 --> 00:11:43,950 然后我们再去遍历它对应的这个子表, 125 00:11:43,950 --> 00:11:48,995 那在这个遍历的时候,我们可以看到, 126 00:11:48,995 --> 00:11:54,040 对这个L2的子表,因为刚才已经是访问过,那我就把L2 127 00:11:54,040 --> 00:12:00,660 这样的一个命名的这样的一个子表呢,我把它的名字打印出来就可以了。 128 00:12:00,660 --> 00:12:04,980 那我们不断这个伸收的访问, 129 00:12:04,980 --> 00:12:12,580 就把整个广义表给遍历完了。 那最后呢,给大家留一下思考。 130 00:12:12,580 --> 00:12:17,075 广义表我们可以看到 131 00:12:17,075 --> 00:12:26,115 它跟这个树和图甚至线性表都有一定的这样的对应关系。 那我们思考一下,它跟我们以前的 132 00:12:26,115 --> 00:12:30,660 树和图是怎么样对应起来的?有哪些异同? 133 00:12:30,660 --> 00:12:35,970 另外呢,我们可以实现一下广义表的遍历算法。 134 00:12:35,970 --> 00:12:41,390 那在所有的数据结构里面呢,遍历算法是一个基础的操作。 135 00:12:41,390 --> 00:12:45,460 你的插入删除还有检索, 136 00:12:45,460 --> 00:12:53,670 可以说都是要建立在遍历的基础上。 谢谢大家。