数组广义表

　　一、数组，为n(>0)个元素的，有穷序列，记作A = (a₁,a₂,...,a_n)，a_i(n>=i>=1) 或者为相同数据类型的原子项，或者为相同定义的数组B_i；a_i为原子项时，数组的维度为1，为数组B_i时，数组的维度为a_i的维度+1；

　　1、数组的顺序存储，按行优先存储，按列优先存储；

低维下标大小升序排列存放，按行优先存储

高维下标到低维下标升序排列，按列优先存储

　　2、

　　二、广义表，是由n(>=0)个元素，组成的有穷序列，记作，LS = (d₁,d₂,...,d_n)， d_i或是原子或是子广义表，d₁为表头(head)，剩余元素构成的子表 (d₂,...d_n)为表尾(tail)

　　1、广义表特点

　　（1）、为递归结构；

　　（2）、数据元素宏观上为线性关系，微观上体现出复杂的多维关系；

　　2、广义表的存储结构

　　广义表，LS = (d₁,d₂,...d_n)，中的数据元素d_i，或是原子或是子广义表，具有不同的结构，很难用顺序存储表示，通常采取链式存储来表示；

　　（1）、头尾链表存储结构；

　　表GList，是由若干tag为LIST即1的数据元素，采取链式存储构成，每个数据元素的头尾指针，指向具体的数据（或为原子或为广义表）；

typedef enum{ATOM, LIST} ElemTag; /* 标记类型 */
typedef struct GLNode{
    ElemTag tag;   /* 数据元素类型 标记 */
    union{
        AtomType atom; /* 原子, 数据元素 */
        struct{
            struct GLNode *hp; /* head pointer */
            struct GLNode *tp; /* tail pointer */
        }htp;         /* 广义表(头尾指针), 数据元素 */
    }atom_htp; /* 联合体(原子、广义表) */
}GLNode, *GList; /* 定义广义表及广义表指针数据类型 */

　　（2）、扩展线性链表存储结构；

　　表GList至少有一个结点（空表时），每个结点由原子或一个表尾指针构成，当tag为0时，结点存储原子，尾指针指向尾元素，当tag为1时，结点存储广义表指针，尾指针指向尾元素；

typedef enum{ATOM, LIST} ElemTag; /* 标记类型 */
typedef struct GLNode{
    ElemTag tag;   /* 数据元素类型标记 */
    union{
        AtomType atom; /* 原子,数据元素 */        
        struct GLNode *hp; /* head pointer */        
    }atom_htp; /* 联合体(原子、广义表) */
    struct GLNode *tp; /* tail pointer */    
}GLNode, *GList; /* 定义广义表及广义表指针数据类型 */

数组 广义表

数组广义表