前言
本節我們來說說C語言中的廣義表，主要介紹廣義表的概念定義，并說明其存盤結構，演算法中將使用到遞回思想，
廣義表是線性表的一種推廣，在資料結構中有廣泛應用，
一、廣義表的概念
1.廣義表的概念
（1）廣義表：也稱串列，是n（n>=0）個元素的有限序列
記作：LS=（a1,a2,…,an）ai(1<=i<=n)是資料元素或廣義表
其中：
LS：廣義表名
n：LS的長度
通常，大寫字母表示廣義表的名稱，小寫字母表示資料元素
（2）原子：當廣義表LS的元素是一個資料元素時，稱為原子
（3）廣義表的子表：當廣義表LS的元素不是一個資料元素時，稱為廣義表的子表
（4）LS的表頭（head）：廣義表非空時，第一個元素a1稱為LS的表頭
（5）LS的表尾（tail）：其余部分（a2,…,an）稱為表尾
舉例：
（1）A=()： A是一個空表，長度n=0
（2）B=(e)，Head(B)=e ，Tail(B)=()：表尾為空的廣義表,長度為1
（3）C=(a,(b,c)) ，Head?=a為原子 ，Tail?=((b,c))為廣義表，表尾長度為1
（4）D=((a,b),c) ，Head(D)=(a,b)為廣義表 ，Tail(D)=?
（5）E=((a,b),c,(d,e))， Head(E)=(a,b)為E的子表 ，Tail(E)=(c,(d,e)) ，Head(Tail(E))=c ， Tail(Tail(E))=((d,e))
結論1：廣義表允許共享子表
結論2：廣義表也允許d遞回的定義
例：G=(a,G) 這里G是一個長度為2的廣義表，第一個元素是原子a，第二個元素是廣義表G自己
2.廣義表的圖型表示
二、廣義表的存盤結構
1.廣義表的存盤結構
（1）由于廣義表中的元素既可以是原子，也可以是廣義表，所以會有原子結點和鏈表結點
（2）每個元素元素所需的空間大小無法統一，所以很難用順序存盤結構表示，通常采用鏈式結構表示
原子結點：tag=0 atom(元素)，只有2個域，標志域和值域
串列結點： tag=1 hp（表頭） tp（表尾），有3個域，標志域、表頭指標域與表尾指標域
注：這種鏈式存盤結構中，為了統一管理這2類結點，采用了共同體（聯合）來定義廣義表的結點型別，
//相關定義
typedef struct GLNode
{
ElemTag tag;//標志域，用以區分原子結點和表結點
union
{
AtomType atom;//原子結點
struct
{
struct GLNode *hp,*tp;
}ptr;//表結點
}
}*GList;
2.廣義表的基本操作（遞回演算法）
（1）求廣義表的長度 ：int GLisitLength(Glist L)
遞回定義：
若L==NULL，長度0
若L！=NULL，長度：1 + GLisitLength(L->ptr.tp)
//求廣義表的長度
int GLisitLength (Glist L)
{
if (!L)
return 0;
return 1+GLisitLength(L->ptr.tp);
}
（2）求廣義表的深度:int GLisitDepth(Glist L)
廣義表：LS=（a1,a2，…,an）
遞回定義：
若L= =NULL，深度1
若L！=NULL，深度：1 + Max(ai)
L->tag==0,原子結點：深度0
//求廣義表的深度
int GLisitDepth (Glist L)
{
if (!L)
return 1;
if (L->tag==0)
return 0;
for (max=0,p=L;p;p=p->ptr.tp)
{
dep = GLisitDepth(p->ptr.hp);
if (dep>max)
max = dep;
}
return max+1;
}
總結
以上簡要介紹了一下廣義表，廣義表還有很多其他的基本操作，在此不一 一贅述，感興趣的話可以再去看看其他的代碼實作，
下一篇將開始介紹非線性結構——樹，篇幅較長，將分為上下兩篇，
ps：代碼非原創，
如有錯誤，歡迎指正，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/271340.html
標籤：其他
上一篇：又是億個小細節：如何讓scanf像gets一樣能讀取帶空格的字串
下一篇：用戶模式和內核模式（執行緒級）