大家好。
数据结构与算法这一讲我们学习第十二章。 高级数据结构中的广义表。
那我们会介绍广义表的一些概念，以及它的存储和便利的算法。
那我们来看一下， 广义表它跟和线性表的一个关系。
以前的线性表呢，它的表元素都是整齐化一的，同一种数据类型。
甚至我们可以看到它的存储的这个长度也是一致的。
那在有些情况下，我们可能这么一个线性的序列。
它里面的这个表元素可能是具有不同的数据类型，比如说整型啊，然后字符型啊。
而且呢这个表中，可能还有子表。
这样的情况呢，我们就需要广义表来表达它。
广义表呢，它这么一个表达呢，你看起来像是一个线性的。
但是我们这个里面的元素， 它可能有不同的类型。
有一些这个元素，它是不可分的，那我们叫做原子。
还有一些元素，它可能自己就是子表。 那对于这个广义表，因为我们很可能
在别的地方还要引用它，所以我们往往是要给它一个命名。
另外呢，这个表，它的顶层的这个个数我还是应该是确定的。
那这就是，表的长度。
因为有子表的情况，那如果说这个子表，也是像我们现在顶层的
这个广义表这样，一层层给它展开的话，
它很可能有很多层的括号，那这也就是广义表的深度。
如果你是一个递归的情况呢，那可能深度就是无穷的。 那我们
来看这个广义表这样两个重要的概念就是表头和表尾。
表头是广义表的第一个元素，把原来的这个广义表，
它是要包掉一层括号以后，这个x0是它的第一个元素。
这个元素，如果它是原子，那它就是原子
如果它是子表，那我们就是它就是原来这个子表包出来的表头。
那表尾呢，其实可以看作是把这个表头删掉以后，
其它的元素组成的这个新的子表，因此这个表尾你看它是要带上括号的。
这样的定义以后呢，我们就可以很方便地来表达这个广义表。
那我们，可以用这样的一个递归的定义，
能够来对它来进行存储的表达，
以及我们在算法上头呢，其实也是可以利用这样一个结构，
也就是我先处理好这个表头节点，处理完了以后它脱离这个广义表。
然后我用刚才这个策略呢， 去递归地处理其它剩下的元素
所组成的广义表，那就是一个一个的把它包离出来，最后这个广义表就处理完了。
那我们来看广义表的一些形态。
首先呢，最简单的就是纯表。
那这个纯表呢，从我们这个广义表的根结点出发。
我们到达任何一个叶的这样结点呢，
它都是只有一条路径，也就是说这些路径呢它不能够有重入，
也就是任何一个点， 它没有两个指向它的边。
还有一种表呢，就是可重入的，
这种情况呢，譬如像这边这个L1
它就是呢，被两个这个上级的子表，
引用了，那就是呢，它是重入的。
那如果这个重入表，它并没有， 形成一个圈，就是没有这样一个循环的结构呢，
那我们就是一个相当于DAG，也就是有效无环图的这么一个结构，
对于这样的一个表呢，我可以看到它包含回路，
这个时候，如果我一层层展开的话，你是可以无穷无尽地去展开的，
因此这个循环表的深度是无穷大，那我们看这里面有两个回路，
第一个回路呢，就是这个L4这个子表，
它是由元素d和L4自身组成的，它就形成了一个自循环，
而这个 L1和L2呢，它是互相指向，
然后形成了一个间接指向的循环。
那我们再来看这个广义表的形式。 其实我们看这个最大的再入表，
它其实里面由各个不同的子表组成，
你可以一层层地来包， 表E它是由表B和表D组成，
那D呢是这样一个独立的表， 然后B呢就是这样一个表。
然后我们也可以看到，
像表D里面它还要引用表B，
也就是说E呢D呢都指向了B。
就是说B其实是一个再入的一个结构了，
在这个表里面呢，我们对这种可重入的情况，我们都是要对这个子表，
进行一个标号，那比如说这边这个子表B，它第一次出现的时候，
我可以把它展开，就是6，2。
那后面的出现呢，我们就只需要引用它这样的一个名字。
不需要再对它扩展的展开了，这种情况呢对于这种循环递归表是特别有用的。
表F它自身组成了这么一个循环的递归表。
那我们可以看到，
刚才这个图里面呢，我们看到的这些结构，
它其实本质上，我们还可以对应到，
以前学过的这个图的结构，当然除了那个自环的情况，
我们那个原来的图，我们是消除了自环的，我们对这个图呢进行一些限制，
也就是说它有这种再入的情况，那就是再入表。
然后呢，我不允许再入，我就变成了一个纯表。
然后这个纯表，如果是退化成一个线性的纯表，
我们可以看到这上面有一个表的顶点，然后呢其它的这个元素呢，
都是在同一层，就是直接这个根底下铺开， 那就是一个线性表，它们是有一些包含的关系的，
那递归表呢，它是一种带回路的一种特殊的再入表。
广义表在很多场景下都有应用，例如函数的调用。
你可以把这些函数呢，当作一个子表，
那函数里面，可能还有几层，调用几个函数。
另外呢，就是这个函数里面其他的一些功能块，
你可以把它当作原子，也就是说它不可能再扩展为子表，再调用别的东西了，
还有内存空间的这种指针的引用关系，其实也可以看成广义表的一个结构，
有一种人工智能的语言，叫做LISP语言，
它就是很多很多嵌套的括号， 广义表的存储结构，首先我是要区分，
子表和原子，因为原子它就不需要展开了。
那如果我看到这麽一个子表的呢，显然我不能在这一层就给它展开。
我需要再去扩展，对这个子表有一个这样的表达，
那在这种情况下呢，我们是没有带表头，
那如果是我要删除这个结点data， 那我就是需要遍历变异整个广义表。
而且呢，把这个指向data的指针呢，
都给它找到。也就是说，
引用这个data作为第一个元素开始的表向。
那我们都找到了以后呢，修改它们这个指针，成为这个data之后的下一个元素。
然后我们才能够完成这样的一个删除，然后我们把这么一个结点给释放。
这样显然它是不太方便的。
因此呢我可以考虑加入一个表头结点，
来代表这个整个子表的开始。
那因此我们的状态呢，就成为有三个值的这么一个标签。
那就是原子呢，是这个head等于0。
然后子表的占位符，是head等于1。
然后呢这个子表开始的那个结点，
它其实是一个虚结点，就是虚的头结点。
那我们把它标志为－1，那这样标志以后，我对这个子表，我还是删除元素data，
找到了这个data以后，我可以直接的从子表里面给它删除。
因为整个这个子表， 它的他引关系，也就是说别人指向它的这些关系呢，
它都通过这个表头给顶住了，能够把这些信息很好地保持。
那只要在这个子表里面，把这个data的这个元素给删掉就行，它可以化简很多的这个操作。
那我们再看一下，带表头的情况下，
我们对这么一个循环的广义表的一个遍历操作。
那这个遍历操作呢，有点像我们在图里面的伸收的遍历。
那我从这个表的第一个元素开始，
然后如果是一个原子呢，
我就是把它给打印出来，接着再看下一个元素。
如果它是个子表，那我就是要
深入到这个子表里面，然后再去伸收遍历它
的这个相应的这个元素。那这里呢，我们可以看到
这个元素它还是指向一个子表，所以我们又深入到下一层这个子表。
然后我们遍历完这个子表以后呢， 那整个这个外层表的
第一个这个子表就遍历完了。我们就继续深入到，
它的这个第二个这个子表占位符。
然后我们再去遍历它对应的这个子表，
那在这个遍历的时候，我们可以看到，
对这个L2的子表，因为刚才已经是访问过，那我就把L2
这样的一个命名的这样的一个子表呢，我把它的名字打印出来就可以了。
那我们不断这个伸收的访问，
就把整个广义表给遍历完了。 那最后呢，给大家留一下思考。
广义表我们可以看到
它跟这个树和图甚至线性表都有一定的这样的对应关系。 那我们思考一下，它跟我们以前的
树和图是怎么样对应起来的？有哪些异同？
另外呢，我们可以实现一下广义表的遍历算法。
那在所有的数据结构里面呢，遍历算法是一个基础的操作。
你的插入删除还有检索，
可以说都是要建立在遍历的基础上。 谢谢大家。
Prof. Ming Zhang 张铭教授
