C语言数据结构——广义表

落日映苍穹つ 2022-12-20 02:20 113阅读 0赞

C语言数据结构中，广义表和数组一样，也是线性表的一种推广！

**广义表的定义：**  
广义表 LS 为n（n≥0）个元素的有穷序列，记作：  
**LS = （d1, d2, … dn）**  
其中：  
**di**：或为**原子项**（为具体数值，用小写字母表示）；或为**子广义表**（简称子表，用大写字母表示）。  
**n**：为广义表的长度；当n等于0时，广义表LS为空表。  
当LS不为空时，即（n≥1时），称**d1为表头（head）**；**剩余所有元素**构成的**子表(d2, d3, …dn)称为表尾（tail）**。

**广义表的基本操作：**  
1.计算表头函数head（LS），定义如下：  
![在这里插入图片描述][20201109191412774.png_pic_center]  
2.计算表尾函数tail (LS),定义如下：  
![在这里插入图片描述][20201109191502922.png_pic_center]  
3.计算表深度函数depth (LS)，定义如下：  
![在这里插入图片描述][20201109191550366.png_pic_center]  
结合实例理解：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center]  
**广义表的存储结构：**  
广义表LS = （d1, d2, …,dn）中的数据元素di或是原子，或是子广义表，具有不同的结构，很难用顺序存储结构表示，通常采用**链式存储结构**来表示。

链式存储结构主要有两种方法：

**1.头、尾链表存储结构；**  
策略：根据广义表的head和tail操作定义对数据元素进行分割和存储组织。  
tag=1表示表结点；tag=0表示原子结点；在表结点中包含两个指针域，分别为hp(指示表头)和tp（指示表尾）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 1]  
**头尾链表存储的特征：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 2]  
**头尾链表存储结构的实例：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 3]

**2.扩展线性链表存储结构。**  
策略:对链表结构进行扩展，元素结点除支持存储原子数据外，可对子广义表进行组织管理。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 4]  
**扩展线性链表存储结构的特征：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 5]  
**扩展线性链表存储结构的实例：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 6]  
总结:  
**广义表的特点：**  
1.为递归结构；  
2.数据元素宏观为线性关系。  
**广义表的存储方案：**  
1.有两种存储方案：头尾链表存储结构和扩展线性链表存储结构；  
2…可表达广义表的递归结构，并体现数据元素直接的关系；  
3.存储方案并不唯一。

[20201109191412774.png_pic_center]: /images/20221120/1fcecabc856f4544aecb2488aea44374.png
[20201109191502922.png_pic_center]: /images/20221120/7a4e140a10a04d0f9ce33fee264e1dff.png
[20201109191550366.png_pic_center]: /images/20221120/3f5b7d747a9b4f829244aff2937759cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/7211bb7492a84c3898a3d9313371d803.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/2020110919280295.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201109192958253.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201109193142730.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201109193428502.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20201109193612361.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201109193724522.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center