一、廣義表#
- 是線性表的推廣
- 對於線性表而言，n 個元素都是基本的單元素
- 廣義表中，這些元素不僅可以是單元素也可以是另一個廣義表
> typedef struct GNode *GList; struct GNode {
> int Tag; //標誌域:0表示結點是單元素，1表示結點是廣義表
> union { //子表指針域SubList域單元素數據域Data複用，共用存儲空間
> ElementType Data;
> GList SubList;
> } URegion;
> GList Next; //指向後繼結點 };
二、多重鏈表#
- 鏈表中的結點可能隸屬於多個鏈
多重鏈表中結點的指針域會有多個，如前面例子包含 Next 和 SubList;
但包含兩個指針域的鏈表並不一定是多重鏈表，比如在雙向鏈表不是多重鏈表
- 多重鏈表具有廣泛的用途:
基本上如樹、圖這樣相對複雜的數據結構都可以採用多重鏈表的方式實現存儲
eg: 存儲矩陣#
用二維數組有兩個缺陷
- 一是數組的大小需要事先確定
- 二是對於稀疏矩陣會造成大量的存儲空間浪費
分析：用一種典型多重鏈表 ———十字鏈表來存儲稀疏矩陣
只存儲非 0 元素
- 節點的指針域
行坐標 Row、列坐標 Col、數值 Value - 每個結點通過兩個值針域，把同行、同列串起來；
行指針 (或稱為向右指針) Right
列指針 (或稱為向下指針) Down - 用一個標識域 Tag 來區分頭結點和非 0 元素結點
頭結點的標識值為 "Head", 矩陣非 0 元素節點的標識值為 "Term"