數(shù)據(jù)結(jié)構(gòu)4數(shù)組

1、計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組1計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組2 數(shù)組是我們最常用的一種數(shù)據(jù)結(jié)構(gòu)，各種計(jì)算機(jī)語言數(shù)組是我們最常用的一種數(shù)據(jù)結(jié)構(gòu)，各種計(jì)算機(jī)語言均有此類型均有此類型。例如：順序表、順序棧、循環(huán)隊(duì)列等。例如：順序表、順序棧、循環(huán)隊(duì)列等。數(shù)組的定義：數(shù)組的定義： 數(shù)組：數(shù)組：是（）個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素是（）個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1an-1,構(gòu)成的占用一塊連續(xù)的內(nèi)存單元的有限序列。構(gòu)成的占用一塊連續(xù)的內(nèi)存單元的有限序列。數(shù)組特點(diǎn)：數(shù)組特點(diǎn)： 1.1.有限個(gè)元素的集合；有限個(gè)元素的集合； 2.2.所

2、有元素具有相同的特性；所有元素具有相同的特性； 3.3.元素名由數(shù)組名和下標(biāo)組成；元素名由數(shù)組名和下標(biāo)組成； 4.4.下標(biāo)值與元素對應(yīng)（代表元素的位置）。下標(biāo)值與元素對應(yīng)（代表元素的位置）。4.1 4.1 數(shù)組的定義及操作數(shù)組的定義及操作計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組3 數(shù)組數(shù)組與與線性表線性表:相同之處相同之處:由若干個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素組由若干個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素組成成.不同之處不同之處: 1.存儲(chǔ)單元連續(xù)與否存儲(chǔ)單元連續(xù)與否 2.數(shù)據(jù)元素在邏輯意義上可分與否數(shù)據(jù)元素在邏輯意義上可分與否 3.操作不同操作不同。計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課

3、件2021-11-16第4章 數(shù)組4. . 數(shù)組的邏輯結(jié)構(gòu)數(shù)組的邏輯結(jié)構(gòu) 一維數(shù)組一維數(shù)組（a a0 0,a,a1 1,a,a2 2,a,a3 3, ,a an-1n-1）滿足）滿足線性關(guān)系；線性關(guān)系； 二維或二維以上數(shù)組：（以二維為例）二維或二維以上數(shù)組：（以二維為例）Amxn= a a . aa00 a01 . a0n-1 10 11 1n-1.a a a m-10 m-11 m-1n-1看元素看元素a a1111有兩個(gè)直接前趨有兩個(gè)直接前趨a a1010和和a a0101兩個(gè)直接后繼兩個(gè)直接后繼a a2121和和a a1212三維數(shù)組三維數(shù)組: :每個(gè)元素有三個(gè)直接前趨和三個(gè)直接后繼每個(gè)

4、元素有三個(gè)直接前趨和三個(gè)直接后繼. .可見可見: :數(shù)組數(shù)組( (除一維數(shù)組外除一維數(shù)組外) )是一種是一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu). .計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組5但是但是: :1)1)可將可將Amxn看成由看成由m m個(gè)行向量組成的向量個(gè)行向量組成的向量, ,即即 Amn= (a00,a01,a0n-1),(a10,a11,a1n-1),(am-10, am-11,am-1n-1) 2)將將Amxn看成由看成由n n個(gè)列向量組成的向量個(gè)列向量組成的向量, ,即即 Amn=( (a00,a10,am-10),(a01,a11,am-1

5、1) (a0n-1,a1n-1,am-1n-1) ) 列向量為線性列向量為線性. .元素元素1 1元素元素2 2元素元素m m看看(ai0,ai1,.ain-1),除除ai0,ain-1 外只有一個(gè)直接前趨和一個(gè)直接后繼外只有一個(gè)直接前趨和一個(gè)直接后繼. .元素元素1 1元素元素2 2元素元素n n計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組6 據(jù)此據(jù)此 數(shù)組可看成是線性表的擴(kuò)展數(shù)組可看成是線性表的擴(kuò)展: :即線性表中的數(shù)據(jù)元即線性表中的數(shù)據(jù)元素本身也是一個(gè)數(shù)據(jù)結(jié)構(gòu)素本身也是一個(gè)數(shù)據(jù)結(jié)構(gòu). . 數(shù)組可表示成兩類線性表數(shù)組可表示成兩類線性表: : 1. 1.以行向量做線性

6、表的一個(gè)元素以行向量做線性表的一個(gè)元素; ; 2. 2.以列向量做線性表的一個(gè)元素以列向量做線性表的一個(gè)元素.計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組7數(shù)組抽象數(shù)據(jù)類型：數(shù)組抽象數(shù)據(jù)類型：數(shù)據(jù)集合：數(shù)據(jù)集合：數(shù)組的數(shù)據(jù)集合可表示為數(shù)組的數(shù)據(jù)集合可表示為a a0 0,a,a1 1a an-1n-1, ,每個(gè)數(shù)據(jù)元素的類每個(gè)數(shù)據(jù)元素的類型為抽象數(shù)據(jù)類型型為抽象數(shù)據(jù)類型:DataType:DataType（限定順序存儲(chǔ)）（限定順序存儲(chǔ)）數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系: :線性關(guān)系線性關(guān)系. .操作集合：操作集合： 各種高級程序設(shè)計(jì)語言的操作各不相同，必備的操作有：各種高級程序設(shè)計(jì)語言的

7、操作各不相同，必備的操作有：（1 1）求數(shù)組元素個(gè)數(shù)）求數(shù)組元素個(gè)數(shù)（2 2）隨機(jī)?。╇S機(jī)?。? 3）隨機(jī)存）隨機(jī)存（4 4）矩陣運(yùn)算）矩陣運(yùn)算計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組8 一般數(shù)組一般數(shù)組: : ( (以二維數(shù)組為例以二維數(shù)組為例) ) 多采用順序存儲(chǔ)多采用順序存儲(chǔ): : (1). (1).按行優(yōu)先順序存儲(chǔ)按行優(yōu)先順序存儲(chǔ) 假設(shè)：假設(shè)：Amn= a00a01a02a0n-1a10a00 a01 a02 a03 a0n-1 a10 a11 a12 a13 a1n-1 am-10 am-11 am-12 am-13 am-1n-1即即 a00,a01,a

8、02a0n-1, a10,a11,.a1n-1 aij的存儲(chǔ)地址的存儲(chǔ)地址: :am-1 ,04.2 4.2 數(shù)組的存儲(chǔ)結(jié)構(gòu)數(shù)組的存儲(chǔ)結(jié)構(gòu): :計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組9 L:為每個(gè)元素所占存儲(chǔ)單元為每個(gè)元素所占存儲(chǔ)單元. .Pascal和和C語言中數(shù)組存儲(chǔ)為此方式語言中數(shù)組存儲(chǔ)為此方式.Loc(aij)=Loc(a00)+(i*n+j)*L(2).列優(yōu)先順序存儲(chǔ)列優(yōu)先順序存儲(chǔ), ,即即 a00,a10,a20am-10, a01,a11,.am-11 aij存儲(chǔ)地址存儲(chǔ)地址: : Loc(aij)=Loc(a00)+(j*m+i)*L Fortra

9、n語言采用此方法語言采用此方法.a00a10a20am-10a01可見可見: :數(shù)組是一種數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)隨機(jī)存儲(chǔ)結(jié)構(gòu). .存取任意元素的時(shí)間相等存取任意元素的時(shí)間相等計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組10推廣推廣: :假設(shè)假設(shè): :AcAc1 1-d-d1 1cc2 2-d-d2 2 例：二維數(shù)組例：二維數(shù)組float a43.float a43.計(jì)算計(jì)算（1 1）數(shù)組元素?cái)?shù)目？數(shù)組元素?cái)?shù)目？ （2 2）若數(shù)組）若數(shù)組Loc(aLoc(a0000)=1000,)=1000,且且L=4,L=4,數(shù)組元素?cái)?shù)組元素a32a32的地址的地址?(?(按行優(yōu)先存儲(chǔ)

10、按行優(yōu)先存儲(chǔ)) )(1)4*3=12(2)Loc(a32)=Loc(a00)+(i*n+j)*L =1000+(3*3+2)*4 =1044Loc(aij)=Loc(ac1c2)+(i-c1 1)*(d2 2-c2 2+1)+(j-c2 2)*L按行優(yōu)先順序存儲(chǔ)：按行優(yōu)先順序存儲(chǔ)：Loc(aij)=Loc(ac1c2)+(j-c2 2)*(d1 1-c1 1+1)+(i-c1 1)*L按列優(yōu)先順序存儲(chǔ)：按列優(yōu)先順序存儲(chǔ)：計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組11特殊矩陣：特殊矩陣：指有一定量的零元素（或相同元素），并且指有一定量的零元素（或相同元素），并且其分布（

11、非零元素的位置）有一定的規(guī)律。其分布（非零元素的位置）有一定的規(guī)律。采用壓縮順序存儲(chǔ)方式采用壓縮順序存儲(chǔ)方式: :只存非零元素只存非零元素, ,節(jié)省空間節(jié)省空間. . 1.1.下三角矩陣下三角矩陣: : 存放形式存放形式: :a00,a10,a11,a20,a21,an-10,an-11, an-1n-1 4.3 4.3 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)a00 0 0.0a10 a11 0 .0 . 0an-10 an-11 . .an-1n-1Ann =可以是可以是0 0和常數(shù)和常數(shù)C C第第1 1行：行： 1 1個(gè)個(gè)第第2 2行：行： 2 2個(gè)個(gè)第第3 3行：行： 3 3個(gè)個(gè) 第第n

12、n行：行： n n個(gè)個(gè) 1+2+3+4+5+n=n(n+1)/2 計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組12非零元素非零元素aijaij存儲(chǔ)地址存儲(chǔ)地址: :Loc(aij)=Loc(a00)+i*(i+1)/2+j*L （0j i n-1）K0123n(n-1)/2n(n+1)/2-1sbk a00a10a11a20an-11an-1n-1計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組13假設(shè)：以一維數(shù)組假設(shè)：以一維數(shù)組sbn(n+1)/2+1作為作為n階下三角矩陣階下三角矩陣A的存儲(chǔ)結(jié)構(gòu)，的存儲(chǔ)結(jié)構(gòu)，A中任意元素中任意元素aij與與sbk

13、對應(yīng)關(guān)系如下：對應(yīng)關(guān)系如下： i(i+1)/2+j 當(dāng)當(dāng)ij時(shí)時(shí) (非零元素非零元素) k= n(n+1)/2 當(dāng)當(dāng)ij時(shí)時(shí) (零零或常數(shù)或常數(shù))其中：其中：sbk:sb0sbn(n+1)/2 -1 sbn(n+1)/2存放常數(shù)或零存放常數(shù)或零計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組142.2.對稱矩陣對稱矩陣對稱矩陣：對稱矩陣：n n階方陣階方陣A A中的元素滿足：中的元素滿足： a aijij = a= ajiji 0 i, j n -1 0 i, j n -1 存儲(chǔ)：可只存儲(chǔ)上三角矩陣或下三角矩陣存儲(chǔ)：可只存儲(chǔ)上三角矩陣或下三角矩陣將將n n* *n n個(gè)元素

14、壓縮存儲(chǔ)到個(gè)元素壓縮存儲(chǔ)到n(n+1)/n(n+1)/2 2個(gè)元素空間中（個(gè)元素空間中（sasa數(shù)組）。數(shù)組）。以按行優(yōu)先存儲(chǔ)為例。以按行優(yōu)先存儲(chǔ)為例。A A矩陣與矩陣與saksak 關(guān)系：關(guān)系：上三角矩陣的存儲(chǔ)類似下三角矩陣，上三角矩陣的存儲(chǔ)類似下三角矩陣，上三角矩陣上三角矩陣自推自推i(i+1)/2+j ijj(j+1)/2+i ijk=計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組15K0123n(n-1)/2n(n+1)/2-1sak a00a10a11a20an-11an-1n-1隱含a01a02a1n-13.3.對角矩陣：對角矩陣： 形狀：形狀：Ann =非零

15、元素帶非零元素帶計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組16例：三對角陣?yán)喝龑顷?Ann =其中非零元素按行優(yōu)先順序存放：其中非零元素按行優(yōu)先順序存放：a00 ,a01 ,a10 , a11, a12, a21, a22, a23, , an-1,n-2 , an-1,n-1 非零元素非零元素aij的地址關(guān)系式：的地址關(guān)系式：Loc(aij)= Loc(a00)+2*i+j(i=0,j=0,1 或或i=n-1,j=n-2,n-1 或或0in-1,j=i-1,i,i+1)推廣：推廣：n階對角陣有階對角陣有（2h-1）條非零元素帶。條非零元素帶。h計(jì)算機(jī)軟件基礎(chǔ)計(jì)算

16、機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組17以上數(shù)組存儲(chǔ)方式與順序存儲(chǔ)線性表類似以上數(shù)組存儲(chǔ)方式與順序存儲(chǔ)線性表類似數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)。數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)。總之：總之：特殊矩陣的壓縮存儲(chǔ)方法：特殊矩陣的壓縮存儲(chǔ)方法： 找出特殊矩陣的非零元素的分布規(guī)律，將其存儲(chǔ)到一個(gè)存找出特殊矩陣的非零元素的分布規(guī)律，將其存儲(chǔ)到一個(gè)存儲(chǔ)空間，只需在算法中按公式計(jì)算即可實(shí)現(xiàn)矩陣元素的隨機(jī)存儲(chǔ)空間，只需在算法中按公式計(jì)算即可實(shí)現(xiàn)矩陣元素的隨機(jī)存取。取。計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組18稀疏因子：設(shè)在稀疏因子：設(shè)在m m* *n n的

17、矩陣中，有的矩陣中，有t t個(gè)非零元素，令個(gè)非零元素，令nmt稱稱 為矩陣的稀疏因子。通常認(rèn)為為矩陣的稀疏因子。通常認(rèn)為 =0.05md=sa.nd; sb-nd=sa.md; sb-td=sa.td; if(sb-td!=0) q=0; for(v=0; vsa.nd; v+) for(p=0; pdataq.i=sa.datap.j; sb-dataq.j=sa.datap.i; sb-dataq.d=sa.datap.d; q+; q q為為sb.datasb.data的下標(biāo)的下標(biāo)以以sa.datasa.data的的j j域次序搜索域次序搜索p p為為sa.datasa.data的下標(biāo)的

18、下標(biāo)676021104171125301943375650sa:03 1911 2520 1134 3740 1765 50766sb:計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組31算法分析：算法分析：上述算法的時(shí)間復(fù)雜度為：上述算法的時(shí)間復(fù)雜度為：O(sa.ndO(sa.ndsa.tdsa.td) )關(guān)鍵在于非零元素個(gè)數(shù)。關(guān)鍵在于非零元素個(gè)數(shù)。當(dāng)：當(dāng)： sa.tdsa.td m m n n 時(shí)，才適合用三元組表時(shí)，才適合用三元組表當(dāng)：當(dāng)： sa.tdsa.td m m n n 時(shí)時(shí), , 不適合用三元組表不適合用三元組表計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)課件課件2021-11-16第4章 數(shù)組32 一般數(shù)組一般數(shù)組, , 按行、列存放，計(jì)算公式。按行、列存放，計(jì)算公式。特殊矩陣：計(jì)算公式。特殊矩陣：