數(shù)據(jù)結(jié)構(gòu)-第五章數(shù)組和廣義表1(嚴蔚敏)_第1頁
數(shù)據(jù)結(jié)構(gòu)-第五章數(shù)組和廣義表1(嚴蔚敏)_第2頁
數(shù)據(jù)結(jié)構(gòu)-第五章數(shù)組和廣義表1(嚴蔚敏)_第3頁
數(shù)據(jù)結(jié)構(gòu)-第五章數(shù)組和廣義表1(嚴蔚敏)_第4頁
數(shù)據(jù)結(jié)構(gòu)-第五章數(shù)組和廣義表1(嚴蔚敏)_第5頁
已閱讀5頁,還剩22頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

嚴習題集的5.185.30共2題第5章作業(yè)預告:1數(shù)據(jù)結(jié)構(gòu)課程的學習:2第5章數(shù)組和廣義表(Arrays&Lists)①元素的值并非原子類型,可以再分解,表中元素也是一個線性表(即廣義的線性表)。②所有數(shù)據(jù)元素仍屬同一數(shù)據(jù)類型。5.1數(shù)組的定義5.2數(shù)組的順序表示和實現(xiàn)5.3矩陣的壓縮存儲5.4廣義表的定義5.5廣義表的存儲結(jié)構(gòu)數(shù)組和廣義表的特點:一種特殊的線性表35.1數(shù)組的定義數(shù)組:由一組名字相同、下標不同的變量構(gòu)成注意:這里討論的數(shù)組與高級語言中的數(shù)組有所區(qū)別:高級語言中的數(shù)組是順序結(jié)構(gòu);而這里的數(shù)組既可以是順序的,也可以是鏈式結(jié)構(gòu),用戶可根據(jù)需要選擇。答:對的。因為——①數(shù)組中各元素具有統(tǒng)一的類型;②數(shù)組元素的下標一般具有固定的上界和下界,即數(shù)組一旦被定義,它的維數(shù)和維界就不再改變。③數(shù)組的基本操作比較簡單,除了結(jié)構(gòu)的初始化和銷毀之外,只有存取元素和修改元素值的操作。判斷:“數(shù)組的處理比其它復雜的結(jié)構(gòu)要簡單”,對嗎?4二維數(shù)組的特點:一維數(shù)組的特點:1個下標,ai是ai+1的直接前驅(qū)2個下標,每個元素ai,j受到兩個關(guān)系(行關(guān)系和列關(guān)系)的約束:一個m×n的二維數(shù)組可以看成是m行的一維數(shù)組,或者n列的一維數(shù)組。N維數(shù)組的特點:n個下標,每個元素受到n個關(guān)系約束一個n維數(shù)組可以看成是由若干個n-1維數(shù)組組成的線性表。a11a12…a1n

a21a22…a2n

…………

am1am2…amn

Amn=5N維數(shù)組的數(shù)據(jù)類型定義n_ARRAY=(D,R)其中:Ri={<aj1,j2,…ji…jn,aj1,j2,…ji+1…jn

>|

aj1,j2,…ji…jn,aj1,j2,…ji+1…jn

D}數(shù)據(jù)關(guān)系:R={R1,R2,….Rn}數(shù)據(jù)對象:D={aj1,j2…jn|ji為數(shù)組元素的第i維下標,aj1,j2…jn

Elemset}數(shù)組的抽象數(shù)據(jù)類型定義略,參見教材P90構(gòu)造數(shù)組、銷毀數(shù)組、讀數(shù)組元素、寫數(shù)組元素基本操作:65.2數(shù)組的順序存儲表示和實現(xiàn)問題:計算機的存儲結(jié)構(gòu)是一維的,而數(shù)組一般是多維的,怎樣存放?解決辦法:事先約定按某種次序?qū)?shù)組元素排成一列序列,然后將這個線性序列存入存儲器中。例如:在二維數(shù)組中,我們既可以規(guī)定按行存儲,也可以規(guī)定按列存儲。注意:若規(guī)定好了次序,則數(shù)組中任意一個元素的存放地址便有規(guī)律可尋,可形成地址計算公式;約定的次序不同,則計算元素地址的公式也有所不同;C和PASCAL中一般采用行優(yōu)先順序;FORTRAN采用列優(yōu)先。7補充:計算二維數(shù)組元素地址的通式

設(shè)一般的二維數(shù)組是A[c1..d1,c2..d2],這里c1,c2不一定是0或1無論規(guī)定行優(yōu)先或列優(yōu)先,只要知道以下三要素便可隨時求出任一元素的地址(意義:數(shù)組中的任一元素可隨機存?。憾S數(shù)組列優(yōu)先存儲的通式為:LOC(aij)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+i-c1)]*Lac1,c2…ac1,d2…aij…

ad1,c2…ad1,d2

Amn=單個元素長度aij之前的行數(shù)數(shù)組基址總列數(shù),即第2維長度aij本行前面的元素個數(shù)①開始結(jié)點的存放地址(即基地址)②維數(shù)和每維的上、下界;③每個數(shù)組元素所占用的單元數(shù)則行優(yōu)先存儲時的地址公式為:

LOC(aij)=LOC(ac1,c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L8a(0,0)a(0,1)……a(0,3)a(1,0)a(1,1)……a(1,3)………………………………a(3,2)………………………………………………a(6,0)…………a(6,3)01230123456例1:如何求出a(3,2)的存儲地址?要事先確定:①是行優(yōu)先方式還是列優(yōu)先方式?②數(shù)組的首地址是多少?③每個元素的長度?否則無法求出結(jié)果9例3:已知二維數(shù)組Am,m按行存儲的元素地址公式是:

Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K,請問按列存儲的公式相同嗎?答:盡管是方陣,但公式仍不同。應為:Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K例2〖軟考題〗:一個二維數(shù)組A,行下標的范圍是1到6,列下標的范圍是0到7,每個數(shù)組元素用相鄰的6個字節(jié)存儲,存儲器按字節(jié)編址。那么,這個數(shù)組的體積是

個字節(jié)。288答:Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=28810例4:〖00年計算機系考研題〗:設(shè)數(shù)組a[1…60,1…70]的基地址為2048,每個元素占2個存儲單元,若以列序為主序順序存儲,則元素a[32,58]的存儲地址為

。根據(jù)列優(yōu)先公式Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K得:LOC(a32,58)=2048+[(58-1)*60+(32-1)]*2=8950答:請注意審題!想一想:若數(shù)組是a[0…59,0…69],結(jié)果是否仍為8950?8950維界雖未變,但此時的a[32,58]不再是原來的a[32,58]11Loc(j1,j2,…jn)=LOC(0,0,…0)+若是N維數(shù)組,其中任一元素的地址該如何計算?其中Cn=L,Ci-1=bi×Ci,1<i≤n每個元素長度數(shù)組基址前面若干元素占用的地址字節(jié)總數(shù)第i維長度與所存元素個數(shù)有關(guān)的系數(shù),可用遞推法求出教材已給出低維優(yōu)先的地址計算公式(見P93(5-2)式)該式稱為n維數(shù)組的映像函數(shù):三維數(shù)組且列優(yōu)先時的元素地址要會計算!12例5:【??瓶佳匈Y格考試】假設(shè)有三維數(shù)組A7×9×8,每個元素用相鄰的6個字節(jié)存儲,存儲器按字節(jié)編址。已知A的起始存儲位置(基地址)為1000,末尾元素A[6][8][7]的第一個字節(jié)地址為多少?若按高地址優(yōu)先存儲時,元素A[4][7][6]的第一個字節(jié)地址為多少?

答:

①末尾元素A[6][8][7]的第1個字節(jié)地址=1000+(7×9×8)×6-6=4018

②按高地址優(yōu)先存儲時,元素A[4][7][6]的第1個字節(jié)地址=提示:將第3維看作“頁碼”,前面兩維就是每頁上的二維數(shù)組。(高維地址計算通式參見清華殷人昆教材的解釋)3586只要計算出任一數(shù)組元素的地址,就能對其輕松地進行讀寫操作!計算地址的意義:13#defineMAX_ARRAY_DIM8//假設(shè)最大維數(shù)為8typedefstruct{ELemType*base;//數(shù)組元素基址intdim;//數(shù)組維數(shù)int*bound;//數(shù)組各維長度信息保存區(qū)基址int*constants;//數(shù)組映像函數(shù)常量的基址}Array;即Ci信息保存區(qū)數(shù)組的基本操作函數(shù)說明(有5個)(請閱讀教材P93-95)N維數(shù)組的順序存儲表示(見教材P93)14^……行指針向量a11a12…^a1nam1am2…^amn補充:數(shù)組的鏈式存儲方式—用帶行指針向量的單鏈表來表示。注:鏈式數(shù)組的運算請參見“稀疏矩陣的轉(zhuǎn)置”注意:本章所討論的數(shù)組與高級語言中的數(shù)組有所區(qū)別:高級語言中的數(shù)組只是順序結(jié)構(gòu);而本章的數(shù)組既可以是順序的,也可以是鏈式結(jié)構(gòu),用戶可根據(jù)需要選擇。155.3矩陣的壓縮存儲討論:1.什么是壓縮存儲?若多個數(shù)據(jù)元素的值都相同,則只分配一個元素值的存儲空間,且零元素不占存儲空間。2.所有二維數(shù)組(矩陣)都能壓縮嗎?未必,要看矩陣是否具備以上壓縮條件。3.什么樣的矩陣具備以上壓縮條件?

一些特殊矩陣,如:對稱矩陣,對角矩陣,三角矩陣,稀疏矩陣等。4.什么叫稀疏矩陣?矩陣中非零元素的個數(shù)較少(一般小于5%)重點介紹稀疏矩陣的壓縮和相應的操作。16一、稀疏矩陣的壓縮存儲問題:如果只存儲稀疏矩陣中的非零元素,那這些元素的位置信息該如何表示?解決思路:對每個非零元素增開若干存儲單元,用來存放其所在的行號和列號,便可準確反映該元素所在位置。實現(xiàn)方法:將每個非零元素用一個三元組(i,j,aij)來表示,則每個稀疏矩陣可用一個三元組表來表示。二、稀疏矩陣的操作17例2:寫出右圖所示稀疏矩陣的壓縮存儲形式。0

1290000

00000-30001400

0240000

18000015

00-700(1,2,12)

,(1,3,9),(3,1,-3),(3,5,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)解:至少有4種存儲形式。法1:用線性表表示P67:0

1290000

00000-30001400

024

0000

18000015

00-700()例1:三元素組表中的每個結(jié)點對應于稀疏矩陣的一個非零元素,它包含有三個數(shù)據(jù)項,分別表示該元素的

、

。行下標列下標元素值18法2:用三元組矩陣表示:0

1290000

00000-30001400

024

0000

18000015

00-700121213931-3351443245218611564-7注意:為更可靠描述,通常再加一行“總體”信息:即總行數(shù)、總列數(shù)、非零元素總個數(shù)668ijvalue稀疏矩陣壓縮存儲的缺點:012345678將失去隨機存取功能!19法三:用帶輔助向量的三元組表示。方法:增加2個輔助向量:①記錄每行非0元素個數(shù),用NUM(i)表示;②記錄稀疏矩陣中每行第一個非0元素在三元組中的行號,用POS(i)表示。76531211202NUM(i)6543POS(

i)21i0

1290000

00000-30001400

024

0000

18000015

00-700-7461516182524341453-3139311221866vji0123456783用途:便于高效訪問稀疏矩陣中任一非零元素。POS(i)如何計算?POS(1)=1POS(i)=POS(i-1)+NUM(i-1)用途后續(xù)20法四:用十字鏈表表示用途:方便稀疏矩陣的加減運算方法:每個非0元素占用5個域rightdownvji同一列中下一非零元素的指針同一行中下一非零元素的指針十字鏈表的特點:①每行非零元素鏈接成帶表頭結(jié)點的循環(huán)鏈表;②每列非零元素也鏈接成帶表頭結(jié)點的循環(huán)鏈表。則每個非零元素既是行循環(huán)鏈表中的一個結(jié)點;又是列循環(huán)鏈表中的一個結(jié)點,即呈十字鏈狀。122100H19311825稀疏矩陣的加減運算容易實現(xiàn)21例3:下面的三元組表表示一個稀疏矩陣,試還原出它的稀疏矩陣。64612221123134445366116ijvalue01234566460

0000

00000000

0000

0000

0000

20012

000

30000

0040

06016

00022typedefstruct{

Triple

data[MAXSIZE+1];//三元組表,以行為主序存入一維向量

data[]中intmu;//矩陣總行數(shù)intnu;//矩陣總列數(shù)inttu;//矩陣中非零元素總個數(shù)}TsMatrix;三元組表的順序存儲表示(見教材P98)對三元組表data[]的整體定義

#defineMAXSIZE125000//設(shè)非零元素最大個數(shù)125000typedefstruct{inti;//元素行號intj;//元素列號ElemTypee;//元素值}Triple;對表中每個結(jié)點的結(jié)構(gòu)定義23二、稀疏矩陣的操作

0

12

9

0000

00000-3

000

14

00

0

24

0000

18

000015

00

-7

000

0–3001512

000180

90024000

0000-70

0140000

00000(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)(1,3,-3)(1,6,15)(2,1,12)(2,5,18)(3,1,9)(3,4,24)(4,6,-7)(5,3,14)已知三元組表a.data求三元組表b.data轉(zhuǎn)置后MT(以轉(zhuǎn)置運算為例,加減用十字鏈表)目的:24答:肯定不正確!除了:(1)每個元素的行下標和列下標互換(即三元組中的i和j互換);還需要:(2)T的總行數(shù)mu和總列數(shù)nu也要互換;(3)重排三元組內(nèi)各元素順序,使轉(zhuǎn)置后的三元組也按行(或列)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論