数据结构与算法学习笔记（第四章串、数组、广义表）（3）广义表

朱雀 2023-03-12 09:06 114阅读 0赞

### 目录 ###

*  广义表
 *   *  性质
     *  广义表和线性表的区别：
     *  广义表优势和应用：
     *  广义表基本运算：

# 广义表 #

*  **又称列表，是n>=0个元素a0,a1,…,an-1的有限序列，其中每一个ai是个原子或者广义表（套娃）**，举个例子：（注意空表也是广义表的元素）(0,1,…,n-1均为下标）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70]
 *  广义表通常记作:**LS=(a1,a2,…,an)(0,1,…,n-1均为下标） 其中LS是表名，n为表的长度，每一个ai为表的元素**
 *  大写字母表示广义表，比如A、B广义表等，小写字母表示原子，比如c，d原子等
 *  表头：  
    ![在这里插入图片描述][20200514163146346.png]
 *  表尾：  
    ![在这里插入图片描述][20200514163222383.png]
 *  广义表举例：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 1]

## 性质 ##

*  广义表中的数据元素有相对次序：一个直接前驱和一个直接后继。（表头表尾除外，广义表相对次序和线性表一样）
 *  广义表的长度定义为最外层括号（总广义表的括号的内一层括号）所包含的元素的个数,如：  
    ![在这里插入图片描述][20200514163303159.png]
 *  广义表的深度定义为该广义表全部展开后（广义表内无大写字母后）所含括号的重数（几重括号），如：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 2]
 *  广义表可以为其他广义表共享（可理解为其他广义表里的元素也属于该广义表），如：  
    ![在这里插入图片描述][20200514163316404.png]
 *  广义表可以是一个递归的表，如：  
    ![在这里插入图片描述][20200514163332610.png]

## 广义表和线性表的区别： ##

*  **广义表可看成线性表的推广，线性表是广义表的特例**

## 广义表优势和应用： ##

*  **广义表结构相当灵活，在某种前提下，广义表可兼容线性表、数组、树和有向图等各种常用的数据结构**
 *  剩下的优势和应用我以图片方式放送。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 3]

## 广义表基本运算： ##

*  求表头GetHead(L)：（L是广义表）非空广义表的第一个元素，可以是一个原子，也可以是一个子表
 *  求表尾GetTail(L)：（L是广义表）非空广义表除去表头元素以外其他元素所构成的表。注意！表尾一定是一个表！
 *  举例子：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70]: /images/20230312/0ebc4aae54ac414cb41122017fb53dd0.png
[20200514163146346.png]: /images/20230312/4cd550159c734edeaed648e3ecd2acf1.png
[20200514163222383.png]: /images/20230312/099e0ad7cdf54729baf1b89bca0b6821.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 1]: /images/20230312/0fdbbae3840e4cb9845c94c44c3c5d29.png
[20200514163303159.png]: /images/20230312/11bcbbd4adf349b0852fb5556d6b864d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 2]: /images/20230312/20c1d617425a4ba0958df1bb1b50385c.png
[20200514163316404.png]: /images/20230312/094061caf55f4a8abb44787f624885e2.png
[20200514163332610.png]: /images/20230312/13758d9f14b04426b05662c202fa90ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 3]: /images/20230312/b0746c622f7347b6bf1ac727fe56114d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 4]: /images/20230312/60d3f2fb2f164bf8b992a3d37d6cfb63.png