一、广義表#
- 線形表の拡張
- 線形表では、n 個の要素は基本的な単一要素です
- 广義表では、これらの要素は単一要素だけでなく、他の广義表でもあることができます
> typedef struct GNode *GList; struct GNode {
> int Tag; //タグ領域：0はノードが単一要素を示し、1はノードが广義表を示す
> union { //子表ポインタ領域SubList領域単一要素データ領域Dataの再利用、共用ストレージ
> ElementType Data;
> GList SubList;
> } URegion;
> GList Next; //後続ノードを指す };
二、多重鏈表#
- リストのノードは複数のリストに所属する可能性があります
多重鏈表のノードのポインタ領域は複数あります。例えば、前の例では Next と SubList が含まれていますが、2 つのポインタ領域を含むリストが必ずしも多重鏈表ではありません。例えば、双方向リストは多重鏈表ではありません
- 多重鏈表は広範な用途があります：
基本的には、木やグラフなどの比較的複雑なデータ構造は、多重鏈表を使用してストレージを実装することができます
例：行列のストレージ#
2 次元配列を使用する場合の 2 つの欠点
- 1 つは、配列のサイズを事前に決定する必要があることです
- 2 つ目は、疎行列の場合、大量のストレージスペースの浪費につながります
分析：疎行列を格納するために、典型的な多重鏈表である十字鏈表を使用します
0 以外の要素のみを格納します
- ノードのポインタ領域
行座標 Row、列座標 Col、数値 Value - 同じ行、同じ列を 2 つのポインタ領域でつなぎます；
行ポインタ (または右ポインタ) Right
列ポインタ (または下ポインタ) Down - ヘッドノードと 0 以外の要素ノードを区別するために、タグフィールド Tag を使用します
ヘッドノードのタグ値は「Head」であり、行列の 0 以外の要素ノードのタグ値は「Term」です