廣義表是線性表的推廣和擴展。它被廣泛的應(yīng)用于人工智能等領(lǐng)域的表處理語言LISP語言中。在LISP中,廣義表是基本的數(shù)據(jù)結(jié)構(gòu),甚至程序本身也可以被表示為一系列的廣義表。
由于廣義表列表中的數(shù)據(jù)元素可能具有不同的結(jié)構(gòu),因此難以用順序存儲結(jié)構(gòu)表示,而通常采用鏈式存儲結(jié)構(gòu),每個數(shù)據(jù)元素用一個結(jié)點來表示。而結(jié)點的結(jié)構(gòu)可以為原子或列表,因此需要兩種結(jié)構(gòu)的結(jié)點。常用的廣義表存儲方式可以是頭尾鏈表存儲,其形式定義如下:
廣義表的深度定義為廣義表中括號的重數(shù),是廣義表的一種量度。通過遞歸算法可以求得廣義表的深度,算法描述如下:
而廣義表的復制同樣也可以通過遞歸算法得到實現(xiàn),算法描述如下:
廣義表可以被表示成一個字符串,即廣義表的書寫形式。我們將會給出一個廣義表的書寫形式字符串,請通過如下所示的算法將其轉(zhuǎn)換成廣義表,并將得到的廣義表復制為新的廣義表,計算并輸出新的廣義表的深度。