數(shù)據(jù)結(jié)構(gòu)chapter5數(shù)組和廣義表(已修改)
2025-05-25 01:00 本頁面
【正文】 1 數(shù) 據(jù) 結(jié) 構(gòu) 數(shù)組的定義和運(yùn)算 第 5 章 數(shù)組和廣義表 數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn) 特殊矩陣的壓縮存儲(chǔ) 廣義表 2 數(shù) 據(jù) 結(jié) 構(gòu) 數(shù)組的定義和運(yùn)算 定義 第 5 章 數(shù)組和廣義表 mn m m n n n m A a .... a a .... .... .... .... a .... a a a .... a a 2 1 2 22 21 1 12 11 = n m 也可以看成是 m個(gè)行向量 可以看成是 個(gè)列向量 n 可看成是一種特殊的線性表，其特殊在 于表中的 數(shù)據(jù)元素本身也是一個(gè)線性表 。 數(shù)組是 一組有固定個(gè)數(shù)的元素的集合 。 3 數(shù) 據(jù) 結(jié) 構(gòu) 數(shù)組的定義和運(yùn)算 抽象數(shù)據(jù)類型定義 第 5 章 數(shù)組和廣義表 ADT Array{ }ADT Array 數(shù)據(jù)對(duì)象： D={aj1j2…jn |n0,稱為數(shù)組的維數(shù)， ji是數(shù)組的 第 i維下標(biāo)， 1≤ji≤bi,bi為數(shù)組第 i維的長(zhǎng)度， aj1j2…jn ∈ ElementSet} 數(shù)據(jù)關(guān)系： R={R1,R2,…,R n} Ri={aj1…ji…jn , aj1…ji+1…jn | 1≤jk≤bk, 1≤k≤n, 且 k≠i, 1≤ji≤bi1, aj1…ji…jn , aj1…ji+1…jn ∈ D, i=1,…,n } 基本操作： (A,n,bond1,…,bondn) (A) (A,e,index1,…,indexn) (A,e,index1,…,indexn) 4 數(shù) 據(jù) 結(jié) 構(gòu) 數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn) 類型特點(diǎn) : 第 5 章 數(shù)組和廣義表 1）不 考慮插入和刪除操作； 2）數(shù)組是多維的結(jié)構(gòu)，而存 儲(chǔ)空間是一個(gè)一維的結(jié)構(gòu)。 5 數(shù) 據(jù) 結(jié) 構(gòu) 數(shù)組的定義和運(yùn)算 運(yùn)算 第 5 章 數(shù)組和廣義表 獲得特定位置的元素值； 修改特定位置的元素值。 主要操作是 數(shù)據(jù)元素的定位 ，即給定元素 的下標(biāo)，得到該元素在計(jì)算機(jī)中的存放位置。 其本質(zhì)是 地址計(jì)算問題 。 有兩種順序映象的方式 : 以行序?yàn)橹餍颍? 以列序?yàn)橹餍颉? 6 數(shù) 據(jù) 結(jié) 構(gòu) 數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn) 以行序?yàn)橹餍? 第 5 章 數(shù)組和廣義表 例如： a1,2 a1,1 a1,3 a2,1 a2,2 a2,3 a1,2 a1,1 a1,3 a2,1 a2,2 a2,3 L 二維數(shù)組 Amxn中任一元素 ai,j 的存儲(chǔ)位置 LOC(i,j)=LOC(1,1) + (n (i1)＋ (j1)) 稱為 基地址 或基址。 L 7 數(shù) 據(jù) 結(jié) 構(gòu) 數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn) 以列序?yàn)橹餍? 第 5 章 數(shù)組和廣義表 例如： L 二維數(shù)組 Amxn中任一元素 ai,j 的存儲(chǔ)位置 LOC(i,j)=LOC(1,1) + (m (j1)＋ (i1)) 稱為 基地址 或基址。 L a1,2 a1,1 a1,3 a2,1 a2,2 a2,3 a2,1 a1,1 a1,2 a2,2 a1,3 a2,3 8 數(shù) 據(jù) 結(jié) 構(gòu) 數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn) 第 5 章 數(shù)組和廣義表 三維數(shù)組 A r m n中任一元素 ai,j,k 的存儲(chǔ)位置 LOC(i,j,k)=LOC(1,1,1) + ((i1) m n ＋ (j1) n+(k1)) L j1,j2,j3代替數(shù)組下標(biāo) i,j,k，并且 j1,j2,j3的下限分別為 c1,c2,c3，上 限為 d1,d2,d3,每個(gè)元素占 size個(gè)存儲(chǔ)單元。則 a j1,j2,j3的存儲(chǔ)位置 LOC(j1,j2,j3)=LOC(c1,c2,c3) + ((j1c1) (d2c2+1) (d3c3+1) ＋ (j2c2) (d3c3+1) +(j3c3)) size 9 數(shù) 據(jù) 結(jié) 構(gòu) 數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn) 第 5 章 數(shù)組和廣義表 推廣到一般情況，可得到 n 維數(shù) 組數(shù)據(jù)元素存儲(chǔ)位置的映象關(guān)系： Loc(A[j1][j2]…[j n]=Loc(A[c1][c2]…[c n])+ αi (jici), 1≤i≤n ∑ n i=1 其中： αi=size (dkck+1),1≤i≤n) ∏ n k=i+1 10 數(shù) 據(jù) 結(jié) 構(gòu) 數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn) 第 5 章 數(shù)組和廣義表 例如： 設(shè)有二維數(shù)組 A[10][20]，其每個(gè)元素占 2 個(gè)字節(jié)，第一個(gè)元素 A1,1的存儲(chǔ)地址為 100， 則 按行優(yōu)先 順序存儲(chǔ)時(shí)元素 A6,6的存儲(chǔ)地址為 ? 若 按列優(yōu)先 順序存儲(chǔ)時(shí)元素 A6,6的存儲(chǔ)地址為 ? A 6,6=100+[(61)*20+(61)]*2=310 按行優(yōu)先 按列優(yōu)先 A 6,6=100+[((61)*10+(61)]*2=210 11 數(shù)
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1