【正文】 LL。 else { L=p=new GLNode。 if(str[0]amp。amp。!str[1]) { Ltag=ATOM。 L=str[0]。 } else { ptag=LIST。 for(i=1,j=0。sub[j]=str[i]。i++) j++。 //將str[]中()內的字符序列賦值到數(shù)組sub[]中 sub[j1]=39。\039。 do{ Sever(sub,hstr)。 //取表頭元素序列 CreateGList(p,hstr)。 //創(chuàng)建p的頭表 if(sub[0]) //創(chuàng)建表尾結點p { p=new GLNode。 p=p。 ptag=LIST。 } }while(sub[0])。 p=NULL。 //結束循環(huán)后的為表為空表 } } delete[]sub。delete[]hstr。}5．遍歷廣義鏈表GL的遞歸算法void Traverse_GL(GList GL)遞歸遍歷廣義鏈表GL的執(zhí)行過程：如果GL為空表則輸出”()”，如果GL為原子則輸出dada值。否則，從前往后逐個遞歸遍歷每個子表。算法的實現(xiàn)代碼如下：void Traverse_GL(GList GL){ GList p。 if(!GL) cout()。 else { if(GLtag==ATOM) coutGL。 else { cout39。(39。 p=GL。 while(p) { Traverse_GL(p)。 p=p。 if(p)cout39。,39。 } cout39。)39。 } }}6．對廣義鏈表GL的表頭遍歷的遞歸算法void Head(GList GL)該操作的實現(xiàn)過程類似于算法void Traverse_GL(GList GL)，算法的實現(xiàn)代碼如下：void Head(GList GL){ GList h。 cout廣義表: 。 Traverse_GL(GL)。 coutendl。 if(!GL || GLtag==ATOM) cout為原子或空表不能取表頭\n。 else { cout表頭為: 。 h=GL。 if(htag==ATOM) couth。 else Traverse_GL(h)。 coutendl。 }}7．對廣義鏈表GL的表尾遍歷的遞歸算法void Tail(GList GL)該操作的實現(xiàn)過程類似于算法void Traverse_GL(GList GL)，算法的實現(xiàn)代碼如下：void Tail(GList GL){ GList h。 cout廣義表: 。 Traverse_GL(GL)。 coutendl。 if(!GL || GLtag==ATOM) cout為原子或空表不能取表尾\n。 else { cout表尾為: 。 h=GL。 Traverse_GL(h)。 coutendl。 }}8．廣義鏈表算法演示主程序在主程序中通過調用以上給出的各種基本操作程序實現(xiàn)：（1）創(chuàng)建一個廣義表GL；（2）對GL進行遍歷顯示；（3）求GL的深度；（4）求GL的長度；（5）由GL復制生成GT，并對GT遍歷顯示；（6）遍歷GL的表頭；（7）遍歷GL的表尾。void main(){ GList GL,GT。 AtomType *str=new AtomType[200]。 while(1) { coutinput str:\n。cinstr。 CreateGList(GL,str)。 cout(1)遍歷結果為: 。 Traverse_GL(GL)。 coutendl。 cout(2)廣義表的深度為: 。 coutGListDepth(GL)endl。 cout(3)廣義表的長度為: 。 coutGListLength(GL)endl。 cout(4)廣義表的復制結果為: 。 CopyGList(GT,GL)。 Traverse_GL(GT)。 coutendl。 cout(5)廣義表的表頭遍歷結果為:\n。 Head(GL)。 cout(6)廣義表的表尾遍歷結果為:\n。 Tail(GL)。 }}程序運行演示結果如下：input str:(a,(b,c),((e)))↙(1)遍歷結果為: (a,(b,c),((e)))(2)廣義表的深度為: 3(3)廣義表的長度為: 3(4)廣義表的復制結果為: (a,(b,c),((e)))(5)廣義表的表頭遍歷結果為:廣義表: (a,(b,c),((e)))表頭為: a(6)廣義表的表尾遍歷結果為:廣義表: (a,(b,c),((e)))表尾為: ((b,c),((e)))input str:((a),((b),c),(((d))))↙(1)遍歷結果為: ((a),((b),c),(((d))))(2)廣義表的深度為: 4(3)廣義表的長度為: 3(4)廣義表的復制結果為: ((a),((b),c),(((d))))(5)廣義表的表頭遍歷結果為:廣義表: ((a),((b),c),(((d))))表頭為: (a)(6)廣義表的表尾遍歷結果為:廣義表: ((a),((b),c),(((d))))表尾為: (((b),c),(((d)))) 習 題一、問答題1．常對數(shù)組進行的兩種基本操作是什么？2．二維數(shù)組M56的元素是4個字符（每個字符占用一個存儲單元）組成的串，那么按行優(yōu)先存儲時元素M[3][5]的起始地址與M按列優(yōu)先存儲時的什么元素的起始地址相同？3．稀疏矩陣的壓縮存儲方法有哪兩種？4．如果采用三元組壓縮存儲技術來存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉置操作，這種說法是否正確？5．設整型三角矩陣A44采用壓縮存儲，已知LOC(A[0][0])=100，那么A[3][2]的首地址是多少（每個整數(shù)占用4個字節(jié)）？6．已知稀疏矩陣，畫出A的十字鏈表存儲結構示意圖。7．已知廣義表LS=(a,(b,c,d),e)，那么取出原子b的運算是什么？8．一個廣義表的表頭還是一個廣義表，這種說法對嗎？9．一個廣義表的表尾也一定是一個廣義表，這種說法對嗎？二、填空題1．已知矩陣Amn采用以行為主序的方法存儲，每個元素占用k個字節(jié)的存儲單元，并且A[0][0]的起始地址為m，那么元素A[i][j]的起始地址是（ ）。2．已知矩陣A1020采用以列為主序的方法存儲，每個元素占用2個字節(jié)的存儲單元，并且A[0][0]的起始地址為100，那么元素A[6][12]的起始地址是（ ）。3．已知10階整型對稱矩陣A采用壓縮存儲方式存儲（以行為主序，且LOC(A[0][0])=1），假設每個元素占用4個字節(jié)的存儲單元，那么元素A[8][5]的起始地址是（ ）。4．二維數(shù)組M56的元素是4個字符（每個字符占1個存儲單元）組成的串，那么M按行優(yōu)先（以左下標為主序）存儲時元素M[3][5]的起始地址與M按列優(yōu)先（以右下標為主序）存儲時的元素（ ）的起始地址相同。5．廣義表((a),((b),c),(((d))))的表頭是【 】，表尾是【 】，長度是（ ），深度是（ ）。6．假定計算廣義表p的表頭的操作用Head【p】表示，表尾的操作用Tail【p】表示，給出下列廣義表的運算結果。（1）Head【(a,b,c)】=( )。（2）Tail【(a,b,c)】=( )。（3）Head【((a),(b))】=( )。（4）Tail【((a),(b))】=( )。（5）Head【Tail【(a,b,c)】】=( )。（6）Head【Tail【((a,b),(c,d))】】=( )。（7）Tail【Head【((a,b),(c,d))】】=( )。（8）Tail【Tail【(a,(b,c),((d,e,f)))】】=( )。7．畫出下列廣義表的鏈式存儲結構圖，并求它的長度和深度。（1）((()),a,((b,c),(),d),(((e))))（2）((((a),b)),(((),d),(e,f)))8．(a)、(b)所示的鏈式存儲結構對應的廣義表。三、編程設計1．編寫一個函數(shù)，將整型數(shù)組A[0,…,n1]中的所有奇數(shù)移到偶數(shù)之前，并且要求只用一個元素大小的附加存儲空間，且時間復雜度為O(n)。2．在用三元組順序表示稀疏矩陣的情況下，編寫實現(xiàn)創(chuàng)建矩陣的算法。在創(chuàng)建時輸入的三元組中對行序和列序不做要求。3．在用三元組順序表示稀疏矩陣的情況下，編寫實現(xiàn)稀疏矩陣A和稀疏矩陣B的減法運算：C=AB。并且要求C也是用三元組順序表示的稀疏矩陣。4．在用三元組順序表示稀疏矩陣的情況下，編寫實現(xiàn)稀疏矩陣A和稀疏矩陣B的乘法運算：C=AB。其中矩陣C可以是用通常存儲方式存儲的矩陣。5．在用三元組十字鏈表表示稀疏矩陣的情況下，編寫程序實現(xiàn)兩個稀疏矩陣的加法運算。6．編寫一個算法，將一個廣義表中的元素x替換成y。例如，原廣義表為((a,b),a,(d,a))，將’a’替換成’x’后為((x,b),x,(d,x))。7．編寫一個算法，判斷兩個廣義表是否相等。8．編寫一個函數(shù)，將兩個廣義表合并成為一個廣義表，合并是指兩個廣義表中的元素的合并。例如廣義表 ((a,b),(c))與 (a,(e,f))合并后的結果是((a,b),(c),a,(e,f))。 上機實驗本單元是作為從線性結構到非線性結構的過度來安排的。數(shù)組和廣義表可以看成其元素本身也是其自身結構（遞歸結構）的線性表。廣義表本質上是一種層次結構，自頂向下識別并建立一個廣義表的操作，可視為對某種樹的遍歷操作，其遍歷的訪問動作是建立一個結點。稀疏矩陣的十字鏈表存儲結構也是圖的一種存儲結構。由此可見，本單元的實驗具有承上啟下的作用。通過上機實驗使學生能深入研究數(shù)組的存儲表示和實現(xiàn)技術，進一步熟悉廣義表的存儲結構的特性。實驗題目1 稀疏矩陣運算器【問題描述】稀疏矩陣是那些多數(shù)元素為零的矩陣。利用“稀疏”特點進行存儲和計算可以大大節(jié)省存儲空間，提高計算效率。設計一個能進行稀疏矩陣基本運算的運算器。【基本要求】以三元組順序表表示稀疏矩陣，實現(xiàn)兩個矩陣的相加、相減、相乘運算。稀疏矩陣的輸入形式采用三元組表示，而運算結果的矩陣則以通常的陣列形式顯示輸出?！緶y試數(shù)據(jù)】【實現(xiàn)提示】（1）首先輸入矩陣的行數(shù)和列數(shù)，并判斷基本操作中兩個矩陣的行數(shù)和列數(shù)對于所要求的運算是否相匹配?？深A先設定矩陣的最大行數(shù)和列數(shù)均不超過20。（2）程序可以對三元組的輸入順序加以限制。比如，按行優(yōu)先的順序輸入數(shù)組中的非零元素。（3）在用三元組順序存儲表示稀疏矩陣時，相加、相減的結果矩陣應另行生成，乘積運算的結果矩陣可用二維數(shù)組存儲。實驗題目2 識別廣義表的“表頭”或“表尾”的演示【問題描述】編寫一個程序，建立廣義表的存儲結構，演示在此存儲結構上實現(xiàn)的求廣義表表頭和表尾操作序列的結果?！净疽蟆浚?）設一個廣義表允許分多行輸入，其中可以任意地輸入空格符，原子是不限長的僅由字母和數(shù)字組成的串。（2）廣義表采用鏈式存儲結構存儲，試按廣義表的表頭和表尾分解的方法編寫建立廣義表存儲結構的算法。（3）對已建立存儲結構的廣義表實施操作，并以符號形式顯示結果?！緶y試數(shù)據(jù)】求廣義表((),(e1),(abc,(e2,c,dd)))的表頭和表尾?！緦崿F(xiàn)提示】（1）廣義表串可以利用串的定長存儲或堆分配存儲結構來儲存。（2）輸入廣義表時依靠括號匹配判斷結束，濾掉空格符之后存于一個串變量中。習題參考答案一、問答題1．常對數(shù)組進行的兩種基本操作是什么？2．二維數(shù)組M56的元素是4個字符（每個字符占用一個存儲單元）組成的串，那么按行優(yōu)先存儲時元素M[3][5]的起始地址與M按列優(yōu)先存儲時的什么元素的起始地址相同？3．稀疏矩陣的壓縮存儲方法有哪兩種？4．如果采用三元組壓縮存儲技術來存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉置操作，這種說法是否正確？5．設整型三角矩陣A44采用壓縮存儲，已知LOC(A[0][0])=100，那么A[3][2]的首地址是多少（每個整數(shù)占用4個字節(jié)）？6．已知稀疏矩陣，畫出A的十字鏈表存儲結構示意圖。7．已知廣義表LS=(a,(b,c,d),e)，那么取出原子b的運算是什么？8．一個廣義表的表頭還是一個廣義表，這種說法對嗎？9．一個廣義表的表尾也一定是一個廣義表，這種說法對嗎？二、填空題1．已知矩陣Amn采用以行為主序的方法存儲，每個元素占用k個字節(jié)的存儲單元，并且A[0][0]的起始地址為m，那么元素A[i][j]的起始地址是（ ）。2．已知矩陣A1020采用以列為主序的方法存儲，每個元素占