【正文】 =()A是一個空表，長度為0，深度為1，不存在表頭和表尾。如[]中的廣義表D。L,S) 其操作結(jié)果為，由廣義表串S創(chuàng)建廣義表L；（3）復制CopyGList(amp。對于子表結(jié)點，設置指向頭表的指針域hp和指向表尾的指針域tp；而對于原子結(jié)則設置數(shù)據(jù)域atom。在C++語言中用以下結(jié)構類型來表示廣義表。 //定義廣義表的表頭 (hp)、表尾 (tp)指針域ptr的類型為無名結(jié)構體 }Data。 //空表的深度為1 if(GLtag==ATOM)return(0)。 if(!GL) h=0。 Ttag=Ltag。,39。void Sever(AtomType* amp。,39。 else if(ch==39。 //從str中刪除hstr else str[0]=39。取str中所有子表組成的串sub，執(zhí)行4）。 AtomType* sub=new AtomType[n+1]。amp。 for(i=1,j=0。 p=p。算法的實現(xiàn)代碼如下：void Traverse_GL(GList GL){ GList p。 if(p)cout39。 if(!GL || GLtag==ATOM) cout為原子或空表不能取表頭\n。 Traverse_GL(GL)。void main(){ GList GL,GT。 cout(2)廣義表的深度為: 。 cout(5)廣義表的表頭遍歷結(jié)果為:\n。4．二維數(shù)組M56的元素是4個字符（每個字符占1個存儲單元）組成的串，那么M按行優(yōu)先（以左下標為主序）存儲時元素M[3][5]的起始地址與M按列優(yōu)先（以右下標為主序）存儲時的元素（ ）的起始地址相同。（6）Head【Tail【((a,b),(c,d))】】=( )。3．在用三元組順序表示稀疏矩陣的情況下，編寫實現(xiàn)稀疏矩陣A和稀疏矩陣B的減法運算：C=AB。8．編寫一個函數(shù)，將兩個廣義表合并成為一個廣義表，合并是指兩個廣義表中的元素的合并。實驗題目1 稀疏矩陣運算器【問題描述】稀疏矩陣是那些多數(shù)元素為零的矩陣。比如，按行優(yōu)先的順序輸入數(shù)組中的非零元素。（2）輸入廣義表時依靠括號匹配判斷結(jié)束，濾掉空格符之后存于一個串變量中。【測試數(shù)據(jù)】求廣義表((),(e1),(abc,(e2,c,dd)))的表頭和表尾?？深A先設定矩陣的最大行數(shù)和列數(shù)均不超過20。由此可見，本單元的實驗具有承上啟下的作用。例如，原廣義表為((a,b),a,(d,a))，將’a’替換成’x’后為((x,b),x,(d,x))。2．在用三元組順序表示稀疏矩陣的情況下，編寫實現(xiàn)創(chuàng)建矩陣的算法。（4）Tail【((a),(b))】=( )。2．已知矩陣A1020采用以列為主序的方法存儲，每個元素占用2個字節(jié)的存儲單元，并且A[0][0]的起始地址為100，那么元素A[6][12]的起始地址是（ ）。 Traverse_GL(GT)。 Traverse_GL(GL)。 coutendl。 }}7．對廣義鏈表GL的表尾遍歷的遞歸算法void Tail(GList GL)該操作的實現(xiàn)過程類似于算法void Traverse_GL(GList GL)，算法的實現(xiàn)代碼如下：void Tail(GList GL){ GList h。 Traverse_GL(GL)。 while(p) { Traverse_GL(p)。}5．遍歷廣義鏈表GL的遞歸算法void Traverse_GL(GList GL)遞歸遍歷廣義鏈表GL的執(zhí)行過程：如果GL為空表則輸出”()”，如果GL為原子則輸出dada值。 //取表頭元素序列 CreateGList(p,hstr)。 L=str[0]。)39。 while(str[n])n++。3）Ltag=LIST。,39。(39。amp。則將str復制到hstr中并使str=NULL。str,AtomType* amp。T,GList L) //用遞歸方法完成由廣義表L復制得到廣義表T的操作{ if(!L)T=NULL。 //返回廣義表GL的深度max+1}2．求廣義表GL的長度的遞歸算法int GListLength(GList GL)該算法的遞歸過程是，廣義表GL的長度值=GL的尾表的長度值+1。 GList pp。 //定義結(jié)點的數(shù)據(jù)域data的類型為AtomType struct{GLNode *hp,*tp。（說明：用【】作為基本操作的函數(shù)符號以示區(qū)別。2．廣義表的基本操作廣義表的基本操作主要有：（1）初始化InitGList(amp。用□表示原子，用○表示廣義表，可以用圖形形象地將[](a)。廣義表的這一特點在處理具有層次特點的線性結(jié)構問題時有著獨特的功能。 Print_OL(MM)。 39。 Olink p。 coutCreate Cross Matrix:\n輸入行數(shù)和列數(shù)m n: \n 。 pdown=qdown。 qright=p。 if(![i]||[i]jj){ pright=[i]。 M,int i,int j,Etype e)的功能是，在十字鏈表M中隨機插入一個非零元素e的三元組(i,j,e)。 =new Olink[n]。2．十字鏈的初始化初始化操作void Init_OL(CrossListamp。稀疏矩陣A5。 Print1_TSM(A)。 coutA+B的和為:\n。 } Trans_TSM(A,C)。 while(1) { cout輸入兩個行、列相同的矩陣：。 [k].e=s。j。 Frpot(Anum,A)。 } return 0。e,int i,int j,int rpot[],TSMatrix M){ int k=rpot[i]。 //求每行非零元素的個數(shù) rpot[0]=1。void Frpot(int rpot[],TSMatrix M){ int* num=new int[]。 A)實現(xiàn)三元組矩陣的減法運算A=MN。q++。 int p=1,q=1,r=1。 [q].e=[p].e。col。 for(col=0。由num可算出轉(zhuǎn)置矩陣B的每行元素中第一個元素的初始位置序列cpot。 [n].i=j。 =。(2,1,7)，(4,2,9)224。由于三元組表中的元素是按行號遞增的順序排列，在行號相同的情況下再按列號遞增排列。i++) //以矩陣的形式輸出A的值 { for(j=0。j++) A[i*n+j]=0。 cout[i].e)\n。 。 cout輸入 i j e:\n。其中，、。 //此處定義數(shù)組元素的類型為整型以便于上機操作struct Triple //定義三元組結(jié)構類型{ int i,j。其主要操作有：（1）創(chuàng)建CreatSMatrix(amp。通常認為，當δ≤n為稀疏矩陣。帶狀區(qū)域若包含主對角線上下各b條對角線上的元素，那么b稱為該帶狀陣的半帶寬，該帶狀陣的帶寬為m=(2b+1)。1．對稱矩陣的壓縮存儲若n階方陣Ann中的元素a[i][j]滿足性質(zhì)：，則稱A為n階對稱矩陣。1 2 3 4 5↙2 3 4 5 6↙3 4 5 6 7↙4 5 6 7 8↙21 22 23 24 25↙22 23 24 25 26↙23 24 25 26 27↙24 25 26 27 28↙31 32 33 34 35↙32 33 34 35 36↙33 34 35 36 37↙34 35 36 37 38↙A3結(jié)果為:第1頁:1 2 3 4 52 3 4 5 63 4 5 6 74 5 6 7 8第2頁:21 22 23 24 2522 23 24 25 2623 24 25 26 2724 25 26 27 28第3頁:31 32 33 34 3532 33 34 35 3633 34 35 36 3734 35 36 37 38以行為主序的順序輸入A[2*3*2*3]中的36個元素的值。 Arrayoutput(A3)。 coutA2結(jié)果為:\n。void main(){ Array A1,A2,A22,A3,A4。 //初始化數(shù)組A for(s[0]=0。 } }7．矩陣的轉(zhuǎn)置操作操作int Trans(Array amp。 default: //三維以上按左下標優(yōu)先的一維數(shù)組格式輸出 cout維數(shù)為大于3\n按左下標為主序輸出所有元素的值:\n。s[0]++) { cout第s[0]+1頁:\n。s[0][0]。}6．數(shù)組的按行序輸出操作操作void Arrayoutput(Array A)的功能是，按左下標為主序，輸出一維、二維、三維和多維數(shù)組A中的元素。:39。 for(i=0。i++) { if(script[i]=[i]|| script[i]0) return 0。 return [off]。 off+= script[i]*[i]。}3．根據(jù)下標(script)提取數(shù)組元素的操作操作int Value(Array A,int* script,EType amp。 //計算數(shù)組元素的總數(shù) [i]=bounds[i]。int InitArray(Array amp。 //便于上機操作定義數(shù)組類型為整型（int）struct Array{ EType *base。對于以行為主序的n維數(shù)組，數(shù)組元素a(j0,j1,...,jn1)的地址計算公式為：其中為數(shù)組元素a[0][0]...[0]的地址，L為每個元素所占內(nèi)存的字節(jié)數(shù)，b0,b1,...,bn1為每一維的長度。1．數(shù)組的兩種順序存儲方法（1）以行（左下標）為主序的存儲結(jié)構該存儲結(jié)構以最左面的下標為主序，右下標優(yōu)先變化，即下標變化順序是從右到左。（2）讀取操作Value(Array A,int* script,EType amp。如果一個向量的所有元素又都是向量（或稱子向量），且這些子向量具有相同的上限和下限標號，那么這種特殊形式的向量稱為數(shù)組。在前面討論的線性結(jié)構中，其數(shù)據(jù)元素都是非結(jié)構的原子類型，元素的值是不可再分解的。從邏輯結(jié)構上看，n維數(shù)組Array中各元素的位置由該元素的下標唯一確定，一旦給定一組下標(j0,j1,j2,…,jn1)，都存在唯一的一個與其相對應的元素值a稱為數(shù)組元素，記為a(j0,j1,j2,…,jn1)。 A,int* script,EType e)：該操作根據(jù)下標script修改數(shù)組A中的元素為e的值。（2）以列（右下標）為主序的存儲結(jié)構該存儲結(jié)構以最右面的下標為主序，左下標優(yōu)先變化，即下標變化順序是從左到右。【】已知A456為按左下標為主序存儲的3維數(shù)組，每個元素占4個存儲單元，并且元素A[0][0][0]的首地址為1000，分別計算元素A[1][2][3]、A[3][2][0]和A[1][3][5]的首地址。 //數(shù)組維界向量基地址 int *constent。 =new int[dim]。 //分配數(shù)組元素的存儲空間 [dim1]=1。int Value(Array A,int* script,EType amp。}簡化的提取數(shù)組元素操作函數(shù)EType Value(Array A,int* script)，該操作對下標越界不做檢查。如果下標合理返回1表示修改成功，否則返回0表示操作失敗。 return 1。 cout以行為主序的順序輸入A。 cout]中的length個元素的值。s[0][0]。s[1]++) coutValue(A,s) 。s[1]++) { for(s[2]=0。i++)len*=[i]。int Trans(Arrayamp。s[1][1]。 //定義A1為一維數(shù)組長度為5 ArrayInput(A1)。 coutA2的轉(zhuǎn)置矩陣為:\n。 coutA4結(jié)果為:\n。在高級語言程序設計中，通常是用二維數(shù)組來存儲矩陣元素的。A中元素A[i][j]與M中元素M[k]的對應關系是：(a)(b)所示?？蓪挒閙的n階方陣Ann中的非零元素壓縮存儲到一維數(shù)組B[(n1)m+1]中。2．稀疏矩陣的三元組表示在稀疏矩陣的壓縮存儲過程中，可以只考慮非零元素的存儲以達到壓縮矩陣存儲空間的目的。C) 其功能是求稀疏矩陣A、B的和C；（4）減法SubMatrix(A,B,amp。struct TSMatrix{ Triple data[MAXSIZE+1]。void Create_TSM(TSMatrix amp。 }w