數(shù)據(jù)結(jié)構(gòu)——使用C語言朱戰(zhàn)立數(shù)組PPT課件

1、5.1 5.1 數(shù)組的基本概念數(shù)組的基本概念1.數(shù)組的定義數(shù)組是n(n1)個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,.,an-1構(gòu)成的占用一塊地址連續(xù)的內(nèi)存單元的有限序列。 數(shù)組中任意一個(gè)元素可以用該元素在數(shù)組中的位置來表示，數(shù)組元素的位置通常稱作數(shù)組的下標(biāo)。 第1頁/共31頁相同之處是它們都是若干個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,.,an-1構(gòu)成的有限序列。不同之處是：（1）數(shù)組要求其元素占用一塊地址連續(xù)的內(nèi)存單元空間，而線性表無此要求；（2）線性表的元素是邏輯意義上不可再分的元素，而數(shù)組中的每個(gè)元素還可以是一個(gè)數(shù)組；（3）數(shù)組的操作主要是向某個(gè)下標(biāo)的數(shù)組元素中存數(shù)據(jù)和取某個(gè)下標(biāo)的數(shù)

2、組元素，這和線性表的插入、刪除操作不同。數(shù)組符合線性結(jié)構(gòu)的定義。數(shù)組和線性表相比， 線性結(jié)構(gòu)（包括線性表、堆棧、隊(duì)列、串）的順序存儲(chǔ)結(jié)構(gòu)實(shí)際就是使用數(shù)組來存儲(chǔ)?？梢?，數(shù)組是其他數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)，是軟件設(shè)計(jì)中最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。 第2頁/共31頁2.數(shù)組的實(shí)現(xiàn)機(jī)制()、一維數(shù)組（一維數(shù)組（n個(gè)元素）中任一元素個(gè)元素）中任一元素ai Loc(ai)=LOC(a)+i*k (0i n)( () )、一個(gè)一個(gè)m行行n列的二維數(shù)組列的二維數(shù)組LOC(aij)=LOC(a00)+(i*n+j)*k (0im，0jn)注：注：C C語言中數(shù)組元素采用語言中數(shù)組元素采用行主序行主序的存放方法，即的

3、存放方法，即行優(yōu)先行優(yōu)先順順序。序。a0的內(nèi)存單元地址每個(gè)元素所需的字節(jié)個(gè)數(shù)每個(gè)元素所需的字節(jié)個(gè)數(shù)a00的內(nèi)存單元地址第3頁/共31頁 a0,0 a0,1 a0,n-1 a1,0 a1,1 a1,n-1 am-1,0 am-1,1 am-1,n-1 Amn=一個(gè)mn的二維數(shù)組可以看成是m行的一維數(shù)組，或者n列的一維數(shù)組。第4頁/共31頁3.數(shù)組抽象數(shù)據(jù)類型數(shù)據(jù)集合：數(shù)組的數(shù)據(jù)集合可以表示為a0, a1, a2, ., an-1，每個(gè)數(shù)據(jù)元素的數(shù)據(jù)類型為抽象數(shù)據(jù)元素類型DataType。操作集合：(1)求數(shù)組元素個(gè)數(shù)ArrayLength(D) (2)取數(shù)組元素Get(D, i)(3)存數(shù)組元素

4、Storage(D, i, x) 第5頁/共31頁5.2 5.2 動(dòng)態(tài)數(shù)組動(dòng)態(tài)數(shù)組 數(shù)組有靜態(tài)存儲(chǔ)結(jié)構(gòu)的數(shù)組和動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)的數(shù)組兩種，它們的區(qū)別在于：靜態(tài)數(shù)組在定義時(shí)就必須給出數(shù)組個(gè)數(shù)；動(dòng)態(tài)數(shù)組是在具體申請(qǐng)存儲(chǔ)單元空間時(shí)才給出數(shù)組元素的個(gè)數(shù)。 第6頁/共31頁例5-2 定義有3行、4列整數(shù)類型的二維數(shù)組a，先逐行分別給數(shù)組元素賦數(shù)據(jù)1，2，.，12，然后顯示數(shù)組中的數(shù)值。要求分別把申請(qǐng)二維動(dòng)態(tài)數(shù)組的過程和釋放二維動(dòng)態(tài)數(shù)組的過程編寫成函數(shù)。int *Make2DArray(int row, int col) int *a, i; a = (int *)calloc(row , sizeof(in

5、t *); for (i = 0; i row; i+) ai = (int *)calloc(col , sizeof(int); return a;第7頁/共31頁void Diliver2DArray(int *a, int row) int i; for(i = 0; i row; i+) free(ai); free(a);#include #include #include #include “Array.h”第8頁/共31頁void main(void) int i, j, c;int row = 3, col = 4, *a; a = Make2DArray(row, col)

6、; c = 1; for(i = 0; i row; i+) for(j = 0; j col; j+) aij = c; c+; for(i = 0; i row; i+) for(j = 0; j col; j+) printf(%5d, aij); printf(n); Diliver2DArray(a, row);第9頁/共31頁程序運(yùn)行輸出結(jié)果如下：1 2 3 45 6 7 89 10 11 12123456789101112a00a03a20a23a1a1a3a第10頁/共31頁注意，二維動(dòng)態(tài)數(shù)組的全部存儲(chǔ)空間不是一次申請(qǐng)的，所以二維動(dòng)態(tài)數(shù)組的每一維數(shù)組在物理上是連續(xù)的，而全部二維

7、動(dòng)態(tài)數(shù)組在物理上不一定是連續(xù)的。第11頁/共31頁5.3 5.3 特殊矩陣特殊矩陣 特殊矩陣:指有許多值相同的元素或有許多零元素、且值相同的元素或零元素的分布有一定規(guī)律的矩陣。1.幾種特殊矩陣的壓縮存儲(chǔ):(1)n階對(duì)稱矩陣 在一個(gè)n階方陣A中，若元素滿足下述性質(zhì)： aij=aji （1i,jn） 第12頁/共31頁則稱A為n階對(duì)稱矩陣。如圖5.1是一個(gè)5階對(duì)稱矩陣。 1 5 1 3 7 a11 5 0 8 0 0 a21 a22 1 8 9 2 6 a31 a32 a33 3 0 2 5 1 . 7 0 6 1 3 an1 an2 an3 ann n階對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只要存

8、儲(chǔ)矩陣中上三角或下三角中的元素，讓每兩個(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間，這樣，能節(jié)約近一半的存儲(chǔ)空間。第13頁/共31頁 在這個(gè)下三角矩陣中，第i行恰有i個(gè)元素，元素總數(shù)為n(n+1)/2，這樣就可將n2個(gè)數(shù)據(jù)元素壓縮存儲(chǔ)在n(n+1)/2個(gè)存儲(chǔ)單元中。 假設(shè)以一維數(shù)組va作為n階對(duì)稱矩陣A的壓縮存儲(chǔ)單元，k為一維數(shù)組va的下標(biāo)序號(hào)，aij為n階對(duì)稱矩陣A中i行j列的數(shù)據(jù)元素(其中1i,jn ），其數(shù)學(xué)映射關(guān)系為： i(i-1)/2+j-1 當(dāng)ij j(j-1)/2+i-1 當(dāng)ijk=第14頁/共31頁(2)n階三角矩陣 以主對(duì)角線劃分， n階三角矩陣有n階上三角矩陣和n階下三角矩陣兩種。 n階上

9、三角矩陣如下圖 (a)所示，它的下三角（不包括主對(duì)角線）中的元素均為0（或常數(shù)）。n階下三角矩陣正好相反，它的主對(duì)角線上方均為0（或常數(shù)），如下圖 (b)所示。 注：在大多數(shù)情況下， n階三角矩陣常數(shù)為零。第15頁/共31頁 a11 a12 a 1n a11 c c c a22 a 2n a21 a22 c . c c a nn an1 an2 an n (a)上三角矩陣 (b)下三角矩陣 第16頁/共31頁 假設(shè)以一維數(shù)組sa作為n階下三角矩陣A的壓縮存儲(chǔ)單元，k為一維數(shù)組va的下標(biāo)序號(hào)，aij為n階下三角矩陣A中i行j列的數(shù)據(jù)元素(其中1i,jn ），其數(shù)學(xué)映射關(guān)系為： i(i-1)/2+

10、j-1 當(dāng)ijn(n+1)/2 （或空） 當(dāng)ijk=注：此時(shí)一維數(shù)組sa的數(shù)據(jù)元素個(gè)數(shù)為(n(n+1)/2)+1個(gè)，其中數(shù)組sa的最后一個(gè)位置存儲(chǔ)A中數(shù)值不為0的那個(gè)常數(shù)。第17頁/共31頁例5.3 為節(jié)省內(nèi)存，n階對(duì)稱矩陣采用壓縮存儲(chǔ)，要求：（1）編寫實(shí)現(xiàn)C = A + B操作的函數(shù)。設(shè)矩陣A、矩陣B和矩陣C均采用壓縮存儲(chǔ)方式存儲(chǔ)，矩陣元素均為整數(shù)類型。（2）編寫一個(gè)采用壓縮存儲(chǔ)的n階對(duì)稱矩陣的輸出函數(shù)，要求輸出顯示成矩陣形式，設(shè)矩陣元素均為整數(shù)類型。（3）設(shè)矩陣A和矩陣B為如下所示的矩陣，編寫一個(gè)用矩陣A和矩陣B作為測(cè)試?yán)拥臏y(cè)試上述函數(shù)的主程序。第18頁/共31頁void Add(int

11、 a, int b, int c, int n) int i; for(i = 0; i = n*(n+1)/2-1; i+) ci = ai + bi;void Print(int a, int n) int i, j, k; for(i = 1; i = n; i+) for(j = 1; j = j)k = i * (i - 1) / 2 + j - 1; else k = j * (j - 1) / 2 + i - 1;printf(%d , ak); printf(n); 第19頁/共31頁#include （矩陣加和輸出函數(shù)同上，省略）void main(void) int a =

12、 1,2,4,3,5,6, b = 10,20,40,30,50,60,c6; /*注意元素的排列次序*/ int n = 3; Add(a, b, c, n); Print(c, n);第20頁/共31頁5.4 5.4 稀疏矩陣稀疏矩陣 1.概念 (1) 稀疏矩陣 矩陣中非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素個(gè)數(shù)。 (2) 稠密矩陣 一個(gè)不稀疏的矩陣。 (3) 稀疏矩陣壓縮存儲(chǔ)方法 只存儲(chǔ)稀疏矩陣中的非零元素，實(shí)現(xiàn)方法是:將每個(gè)非 零元素用一個(gè)三元組（i，j，aij）來表示，則每個(gè)稀疏矩 陣可用一個(gè)來表示。第21頁/共31頁50000000000370000000001900000000000025

13、00017011001,3,11,1,5,17,2,2,25,4,1,19,5,4,37,6,7,50(a)(b)1234567123456列 號(hào)行 號(hào)稀疏矩陣和對(duì)應(yīng)的三元組線性表 第22頁/共31頁2. 2. 三元組順序表三元組順序表 指用順序表存儲(chǔ)的三元組線性表。指用順序表存儲(chǔ)的三元組線性表。 typedef struct int i; int j; elemtype d; DataType; typedef struct int md; int nd; int td; TriType;第23頁/共31頁112456.0123456MaxSize-1.352147.111725193750

14、.Size=6676mdndtdijd第24頁/共31頁3.稀疏矩陣的三元組鏈表(1)三元組鏈表 用鏈表存儲(chǔ)的三元組線性表。(2)行指針數(shù)組結(jié)構(gòu)的三元組鏈表 把每行非零元素三元組組織成一個(gè)單鏈表，再設(shè)計(jì)一個(gè)指針類型的數(shù)組存儲(chǔ)所有單鏈表的頭指針。(3)三元組十字鏈表 把非零元素三元組按行和按列組織成單鏈表，這樣稀疏矩陣中的每個(gè)非零元素三元組結(jié)點(diǎn)都將既勾鏈在行單鏈表上，又勾鏈在列單鏈表上，形成十字形狀。第25頁/共31頁三元組鏈表中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域由稀疏矩陣非零元的行號(hào)、列號(hào)和元素值組成。稀疏矩陣三元組線性表的帶頭結(jié)點(diǎn)的三元組鏈表結(jié)構(gòu)如圖所示，其中頭結(jié)點(diǎn)的行號(hào)域存儲(chǔ)了稀疏矩陣的行數(shù)，列號(hào)域存儲(chǔ)了稀疏矩陣的列數(shù)。 這種三元組鏈表的缺點(diǎn)是實(shí)現(xiàn)矩陣運(yùn)算操作算法的時(shí)間復(fù)雜度高，因?yàn)樗惴ㄖ腥粢L問某行某列中的一個(gè)元素時(shí)，必須從頭指針進(jìn)入后逐個(gè)結(jié)點(diǎn)查找。為降低矩陣運(yùn)算操作算法的時(shí)間復(fù)雜度，提出了行指針數(shù)組結(jié)構(gòu)的三元組鏈表，其結(jié)構(gòu)如圖所示：第26頁/共31頁012345123456517311225119437750 列號(hào)非零元素行指針數(shù)組行號(hào)頭指針第27頁/共31頁 行指針數(shù)組結(jié)構(gòu)的三元組鏈表對(duì)于從某行進(jìn)入后找某列元素的操作比較容易實(shí)現(xiàn)，但對(duì)于從某列進(jìn)入后找某行元素的操作就不容易實(shí)現(xiàn)，