DS03_线性结构a__陈越主编_数据结构综述.ppt

? 广义表 【例】如何表示一个单位的人员情况。一种简单的表示方法是用一个线性表来表示，其先后顺序按照进单位的时间顺序排列： （张三，李四，王五，钱六，孙七，……） ? 如何体现三个不同部门？比如办公室、生产部、销售部。同一个部门放在一起。那么可以用三个有序序列的子表构成的线性表来表示： （（张三，……），（李四，孙七，……），（王五，钱六，……）） ? 如果想表示这个单位的负责人是谁，可将负责人作为表的第一元素： （丁一，（张三，……），（李四，孙七，……），（王五，钱六，……）） 【定义】上述这类表就是一种“广义表(Generalized List)”。 ? 广义表是线性表的推广。 ? 广义表与线性表一样，也是 由n个元素组成的有序序列。 ? 不同点在于，对于线性表而言， n个元素都是基本的单元素。 ? 而在广义表中，这些元素不仅可以是单元素也可以是另一个广义表。 第3章 线性结构 §3.2.4 广义表与多重链表 19/25 ? 广义表的数据结构可以定义如下： 第3章 线性结构 typedef struct GNode{ int Tag; /*标志域：0表示该结点是单元素，1表示该结点是广义表 */ union { /* 子表指针域Sublist与单元素数据域Data复用，即共用存储空间 */ ElementType Data; struct GNode *SubList; } URegion; struct GNode *Next; /* 指向后继结点 */ } GList; 图3.7 广义表结构 Tag Data Next SubList 0 丁一 0 张三 0 李四 0 孙七 …… 0 钱六 …… …… 0 王五 1 1 1 NULL Header §3.2.4 广义表与多重链表 20/25 ? 多重链表 第3章 线性结构 【定义】在图３.7的例子中，广义表采用链表存储的方式实现。像这种链表，其元素可能还是另一个子链表的起点指针，叫“多重链表”。 一般来说，多重链表中每个结点的指针域会有多个，如前面的例子包含了Next和SubList两个指针域。 但包含两个指针域的链表并不一定是多重链表，比如双向链表不是多重链表。 ? 多重链表在数据结构实现中有广泛的用途，基本上如树、图这样相对复杂的数据结构都可以采用多重链表的方式实现存储。 §3.2.4 广义表与多重链表 21/25 [例3.3] 矩阵可以用二维数组表示，但二维数组表示有两个缺陷： ? 一是数组的大小需要事先确定， ? 另一个是当矩阵包含许多0元素时，将造成大量的存储空间浪费。 例如，对于下面A和B这样的“稀疏矩阵 ”最好是只存储非0元素。 如何用多重链表方式实现存储？ 【分析】 采用一种典型的多重链表——十字链表来存储稀疏矩阵。 ? 链表中用于存放矩阵非0元素的每个结点有两个指针域： 一个是行指针(或称为向右指针)Right， 另一个是列指针（或称为向下指针）Down。 结点的数据域存放元素的行坐标Row、列坐标Col和数值Value。 第3章 线性结构 §3.2.4 广义表与多重链表 22/25 ? 用一个标识域Tag来区分头结点和非0元素结点： 头节点的标识值为“Head”，矩阵非0元素结点的标识值为“Term”。 第3章 线性结构 (a) 结点的总体结构 (b) 矩阵非0元素结点 (c) 头结点 §3.2.4 广义表与多重链表 Tag Down Right URegion Down Right Row Col Value Term Down Right Next Head ? 稀疏矩阵的数据结构可定义为： #define MAXSIZE 50 /* 矩阵最大非0元素个数 */ typedef enum { Head, Term } NodeTag; typedef struct MatrixNode *PtrMatrix; typedef struct TermNode { int Row; int Col; ElementType Value; }; typedef struct MatrixNode { PtrMatrix Down; PtrMatrix Right; NodeTag Tag; union { PtrMatrix Next; TermNode Term; } URegion; }; PtrMatrix HeadNode [MAXSIZE]; 23/25 ? 用一个标识域Tag来区分头结点和非0元素结点： ? 头节点