資源描述：
《數(shù)據(jù)結(jié)構(gòu)與算法 課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第五章.數(shù)組和廣義表（Chapter5.ArraysandGeneralizedLists）§5.1數(shù)組的定義數(shù)組和廣義表都是數(shù)據(jù)元素為結(jié)構(gòu)類型的一種特殊的線性表。數(shù)組的每一個(gè)元素的結(jié)構(gòu)都是相同的。數(shù)組通常分為二維數(shù)組、三維數(shù)組…和n維數(shù)組。2-Array=(D,R)D={aij
2、i=0,1,…,d1-1,j=0,1,…,d2-1,aij∈D0}R={ROW,COL}ROW={
3、0≤i≤d1-1,0≤j≤d2-2,aij,ai,j+1∈D}COL={
4、0≤i≤d1-
5、2,0≤j≤d2-1,aij,ai+1,j∈D}D0為某數(shù)據(jù)對(duì)象，d1,d2為整數(shù)。下面是二維數(shù)組的定義：下面是多維數(shù)組的定義：n-Array=(D,R)D={aj1j2…jn
6、ji=0,1,…,di-1,i=1,2,…,n,(n>0),aj1j2…jn∈D0}R={R1,R2,…,Rn}Ri={
7、0≤jk≤dk-1,1≤k≤n,且k≠i,0≤ji≤di-2,aj1...ji…jn,aj1...ji+1…jn∈D,D0為某數(shù)據(jù)對(duì)象，di為整數(shù)。i=2,3,…,
8、n}求每個(gè)給定下標(biāo)的數(shù)據(jù)元素的存儲(chǔ)地址：§5.2數(shù)組的順序存儲(chǔ)數(shù)組的順序存儲(chǔ)有兩種存儲(chǔ)方式：即按行優(yōu)先（rowmajororder）存儲(chǔ)或按列優(yōu)先（columnmajororder）存儲(chǔ)。Loc(j1,j2,…,jn)=Loc(0,0,…,0)+[d2*…*dn*j1+d3*…*dn*j2+...+dn*jn-1+jn]*l=Loc(0,0,…,0)+(∑ji∏dk+jn)*li=1k=i+1n-1n這就說(shuō)明了多維數(shù)組是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)?！?.3矩陣壓縮存儲(chǔ)矩陣是很多科學(xué)與工程計(jì)算中常使用的數(shù)據(jù)結(jié)構(gòu)。在實(shí)際
9、應(yīng)用中，很多矩陣存在大量零元素或重復(fù)元素，為節(jié)省存儲(chǔ)空間，可對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)。=Loc(0,0,…,0)+∑ci*jii=1n其中ci=l,ci-1=di*ci,1＜i≤n特殊矩陣：這類矩陣由于零元素或重復(fù)元素的分布很有規(guī)律，可以很容易地把矩陣壓縮存儲(chǔ)在一個(gè)一維數(shù)數(shù)組中。An×nBm，即B[k]=A[i][j]，需求出下標(biāo)映射函數(shù)k=f(i,j)。上三角矩陣0對(duì)角矩陣000下三角矩陣ajiaij對(duì)稱矩陣稀疏矩陣：這類矩陣非零元素很少，但它們的分布沒有規(guī)律，因此在壓縮存儲(chǔ)時(shí)須同時(shí)存儲(chǔ)非零元素的下標(biāo)和值?？捎萌?/p>
10、元組表（listof3-tuples）來(lái)存儲(chǔ)（行號(hào)，列號(hào)，值）。如下三角矩陣有映射k=i(i-1)/2+j(i≥j),Aij=Bk(i≥j)，Aij=0(i11、ct{tripledata[MAXNUM+1];intmu,nu,tu;}matrix;稀疏矩陣還可用帶行索引的二元組表、十字鏈表等表示。最常用的一種算法是求矩陣的轉(zhuǎn)置：因三元組表是按行優(yōu)先排序的，故需先確定轉(zhuǎn)置后矩陣各行的元素個(gè)數(shù)，預(yù)留出位置再進(jìn)行轉(zhuǎn)置。ijv1212211253345522566ijv1212112252435523656A’作業(yè)9.設(shè)有上三角矩陣（aij)n×n，將其上三角元素逐行存于數(shù)組B(1:m)中，使得B[k]=aij，且k=f1(i)+f2(j)+c。試推導(dǎo)函數(shù)f1、f2和常數(shù)項(xiàng)c，
12、其中1≤i，j≤n。10.設(shè)計(jì)一個(gè)算法，將數(shù)組A(1:n)中的元素循環(huán)右移k位，要求只用一個(gè)元素的附加空間，元素移動(dòng)或交換次數(shù)為O(n)?！?.4廣義表的定義廣義表又稱列表，其每一個(gè)元素的結(jié)構(gòu)都可能是不同的。Lists=(D,R)D={di
13、i=1,2,…,n,n≥0,且di∈D0或di∈Lists}R={LR}LR={
14、di-1,di∈D,2≤i≤n}通常廣義表記著：LS=(d1,d2,d3,...,dn)其中D0為某數(shù)據(jù)對(duì)象，di可以是原子（atom），也可以是廣義表，稱為L(zhǎng)S的子表（sub
15、list）。其中第一個(gè)元素d1稱為表LS的表頭（head），由余下元素組成的表(d2,d3,...,dn)稱為L(zhǎng)S的表尾（tail）。廣義表中括號(hào)的重?cái)?shù)稱為廣義表的深度。函數(shù)Head與函數(shù)Tail分別求廣義表的表頭和表尾。函數(shù)Depth求廣義表的深度。如下列均為廣義表：1、A=()3、C=(a,(a,b,c))4、D=(A,B,C,d)5、E=(E,e)2、B=(a)1、
