數(shù)據(jù)結(jié)構(gòu)第五章數(shù)組與廣義表-資料下載頁
2025-10-02 17:00本頁面
【導(dǎo)讀】數(shù)組和廣義表可看成是一種特殊的線性表。素本身也是一種數(shù)據(jù)結(jié)構(gòu)。唯一可供使用的數(shù)據(jù)類型。由于數(shù)組中各元素具有統(tǒng)一的類型，處理比其它復(fù)雜的結(jié)構(gòu)更為簡單。二維數(shù)組可以看成是由若干個行向量組成的向量，也可以看成是若干。在C語言中，一個二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型。設(shè)一3維數(shù)組A[4][2][3]，存貯。行優(yōu)先順序——將數(shù)組元素按行排列，第i+1個行向量緊接在第。序推廣到多維數(shù)組，可規(guī)定為先排最右的下標。二維數(shù)組Amn按“行優(yōu)先順序”存儲在內(nèi)存中，假設(shè)每個元素占。因為aij位于第i行、第j列，前面i-1行一共有。分析：aij前一共有i-c1行，二維數(shù)組一共有d2-c2+1列，故這i-. 在高級語言編制程序時，將一個矩陣描述為一個二維數(shù)組。矩陣在這種存儲表示之下，可以對其元素進行隨機存取，各種矩陣。則稱A為對稱矩陣。對稱矩陣的存儲表示。在這個下三角矩陣中，第i行恰有i+1個元素，元素總數(shù)為：。aij和sa[k]之間對應(yīng)關(guān)系。若i<j，則aij是在上三角矩陣中。因為aij=aji，所以只要交
【正文】 表結(jié)點 tp hp tag=1 原子結(jié)點 tag=0 tp atom 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 534 廣義表的存儲結(jié)構(gòu) typedef enum{atom,list}elemtag。 typedef struct GLnode{ Elemtag tag。 union{ AtomType atom。 struct GLnode *hp。 //表結(jié)點的表頭指針 }。 struct GLnode *tp。 // 指向下一個元素結(jié)點 } *GList。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 535 廣義表的存儲結(jié)構(gòu) ? 廣義表的運算 ? 創(chuàng)建空的廣義表 : initGList(amp。L)。 ? 銷毀廣義表 : destroyGList(amp。L)。 ? 復(fù)制廣義表 : copyGList(amp。T, L)。 ? 求廣義表的長度 : length(L)。 ? 求廣義表的深度 : depth(L)。 ? 求廣義表的表頭 : getHead(L)。 ? 求廣義表的表尾 : getTail(L)。 ? 插入一個元素使其成為新的表頭 : insertFirst(amp。L, e)。 ? 刪除表頭元素 : deleteFirst(amp。L, amp。e)。 ? 判斷表是否空 : isEmpty(L)。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 536 廣義表的存儲結(jié)構(gòu) ? 廣義表作為 ADT ADT Glist{ 數(shù)據(jù)對象 : D={ei |i=1,2,…, n。 n ?0, ei ?AtomSet 或 ei ?Glist} 數(shù)據(jù)關(guān)系 : R={(ei1 , ei ) | ei ? D} 基本操作 : initGList(amp。L)。 操作結(jié)果 : 創(chuàng)建空表 。 destroyGList(amp。L)。 初始條件 : 廣義表 L已存在 操作結(jié)果 : 銷毀廣義表 …. } //Glist。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 537 廣義表的存儲結(jié)構(gòu) ? 求廣義表的深度 設(shè)： LS = (a1, a2, …, an) ， 例如，對于廣義表 E ( B (a, b), D ( B (a, b), C (u, (x, y, z)), A ( ) ) ) 按遞歸算法分析： Depth (E) = 1+Max { Depth (B), Depth (D) } Depth (B) = 1+Max { Depth (a), Depth (b) } = 1 Depth (D) = 1+Max { Depth (B), Depth (C), Depth (A)} 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 538 廣義表的存儲結(jié)構(gòu) Depth (C) = 1+Max { Depth (u), Depth ((x, y, z)) } Depth (A) = 1 Depth (u) = 0 Depth ((x, y, z)) = 1+Max {Depth (x), Depth (y), Depth (z) } = 1 Depth (C) = 1+Max { Depth (u), Depth ((x, y, z)) } = 1+Max {0, 1} = 2 Depth (D) = 1+Max { Depth (B), Depth (C),Depth (A)} = 1+Max {1, 2, 1} = 3 Depth (E) = 1+Max { Depth (B), Depth (D) } = 1+Max {1, 3} = 4 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 539 廣義表的存儲結(jié)構(gòu) Int depth ( GList *ls ) { //廣義表 ls 用擴展的線性鏈表存儲，函數(shù)返回 ls的深度 if ( ls == NULL ) return 1。 //空表 GList *temp = ls。 int m = 0。 //m 表示當前層元素的最大深度 while ( temp != NULL ) { //橫掃廣義表的每個元素 if ( temp→tag == LIST ) { //子表深度 int n = depth ( temp→ hp )。 if ( nm ) m = n。 } //不是子表不加深度 temp = temp→ tp。 //temp指向下一個元素 } return m+1。 } 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 540 習(xí)題 ? 本章習(xí)題參見教師網(wǎng)頁：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1