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

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

2、組元素，這和線性表的插入、刪除操作不同。數(shù)組符合線性結(jié)構(gòu)的定義。數(shù)組和線性表相比， 線性結(jié)構(gòu)（包括線性表、堆棧、隊列、串）的順序存儲結(jié)構(gòu)實際就是使用數(shù)組來存儲。可見，數(shù)組是其他數(shù)據(jù)結(jié)構(gòu)實現(xiàn)順序存儲結(jié)構(gòu)的基礎，是軟件設計中最基礎的數(shù)據(jù)結(jié)構(gòu)。 第2頁/共31頁2.數(shù)組的實現(xiàn)機制()、一維數(shù)組（一維數(shù)組（n個元素）中任一元素個元素）中任一元素ai Loc(ai)=LOC(a)+i*k (0i n)( () )、一個一個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)存單元地址每個元素所需的字節(jié)個數(shù)每個元素所需的字節(jié)個數(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=一個mn的二維數(shù)組可以看成是m行的一維數(shù)組，或者n列的一維數(shù)組。第4頁/共31頁3.數(shù)組抽象數(shù)據(jù)類型數(shù)據(jù)集合：數(shù)組的數(shù)據(jù)集合可以表示為a0, a1, a2, ., an-1，每個數(shù)據(jù)元素的數(shù)據(jù)類型為抽象數(shù)據(jù)元素類型DataType。操作集合：(1)求數(shù)組元素個數(shù)ArrayLength(D) (2)取數(shù)組元素Get(D, i)(3)存數(shù)組元素

4、Storage(D, i, x) 第5頁/共31頁5.2 5.2 動態(tài)數(shù)組動態(tài)數(shù)組 數(shù)組有靜態(tài)存儲結(jié)構(gòu)的數(shù)組和動態(tài)存儲結(jié)構(gòu)的數(shù)組兩種，它們的區(qū)別在于：靜態(tài)數(shù)組在定義時就必須給出數(shù)組個數(shù)；動態(tài)數(shù)組是在具體申請存儲單元空間時才給出數(shù)組元素的個數(shù)。 第6頁/共31頁例5-2 定義有3行、4列整數(shù)類型的二維數(shù)組a，先逐行分別給數(shù)組元素賦數(shù)據(jù)1，2，.，12，然后顯示數(shù)組中的數(shù)值。要求分別把申請二維動態(tài)數(shù)組的過程和釋放二維動態(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頁程序運行輸出結(jié)果如下：1 2 3 45 6 7 89 10 11 12123456789101112a00a03a20a23a1a1a3a第10頁/共31頁注意，二維動態(tài)數(shù)組的全部存儲空間不是一次申請的，所以二維動態(tài)數(shù)組的每一維數(shù)組在物理上是連續(xù)的，而全部二維

7、動態(tài)數(shù)組在物理上不一定是連續(xù)的。第11頁/共31頁5.3 5.3 特殊矩陣特殊矩陣 特殊矩陣:指有許多值相同的元素或有許多零元素、且值相同的元素或零元素的分布有一定規(guī)律的矩陣。1.幾種特殊矩陣的壓縮存儲:(1)n階對稱矩陣 在一個n階方陣A中，若元素滿足下述性質(zhì)： aij=aji （1i,jn） 第12頁/共31頁則稱A為n階對稱矩陣。如圖5.1是一個5階對稱矩陣。 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階對稱矩陣中的元素關于主對角線對稱，故只要存

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

9、三角矩陣如下圖 (a)所示，它的下三角（不包括主對角線）中的元素均為0（或常數(shù)）。n階下三角矩陣正好相反，它的主對角線上方均為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ù)組sa作為n階下三角矩陣A的壓縮存儲單元，k為一維數(shù)組va的下標序號，aij為n階下三角矩陣A中i行j列的數(shù)據(jù)元素(其中1i,jn ），其數(shù)學映射關系為： i(i-1)/2+

10、j-1 當ijn(n+1)/2 （或空） 當ijk=注：此時一維數(shù)組sa的數(shù)據(jù)元素個數(shù)為(n(n+1)/2)+1個，其中數(shù)組sa的最后一個位置存儲A中數(shù)值不為0的那個常數(shù)。第17頁/共31頁例5.3 為節(jié)省內(nèi)存，n階對稱矩陣采用壓縮存儲，要求：（1）編寫實現(xiàn)C = A + B操作的函數(shù)。設矩陣A、矩陣B和矩陣C均采用壓縮存儲方式存儲，矩陣元素均為整數(shù)類型。（2）編寫一個采用壓縮存儲的n階對稱矩陣的輸出函數(shù)，要求輸出顯示成矩陣形式，設矩陣元素均為整數(shù)類型。（3）設矩陣A和矩陣B為如下所示的矩陣，編寫一個用矩陣A和矩陣B作為測試例子的測試上述函數(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) 稀疏矩陣 矩陣中非零元素的個數(shù)遠遠小于矩陣元素個數(shù)。 (2) 稠密矩陣 一個不稀疏的矩陣。 (3) 稀疏矩陣壓縮存儲方法 只存儲稀疏矩陣中的非零元素，實現(xiàn)方法是:將每個非 零元素用一個三元組（i，j，aij）來表示，則每個稀疏矩 陣可用一個來表示。第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列 號行 號稀疏矩陣和對應的三元組線性表 第22頁/共31頁2. 2. 三元組順序表三元組順序表 指用順序表存儲的三元組線性表。指用順序表存儲的三元組線性表。 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)三元組鏈表 用鏈表存儲的三元組線性表。(2)行指針數(shù)組結(jié)構(gòu)的三元組鏈表 把每行非零元素三元組組織成一個單鏈表，再設計一個指針類型的數(shù)組存儲所有單鏈表的頭指針。(3)三元組十字鏈表 把非零元素三元組按行和按列組織成單鏈表，這樣稀疏矩陣中的每個非零元素三元組結(jié)點都將既勾鏈在行單鏈表上，又勾鏈在列單鏈表上，形成十字形狀。第25頁/共31頁三元組鏈表中每個結(jié)點的數(shù)據(jù)域由稀疏矩陣非零元的行號、列號和元素值組成。稀疏矩陣三元組線性表的帶頭結(jié)點的三元組鏈表結(jié)構(gòu)如圖所示，其中頭結(jié)點的行號域存儲了稀疏矩陣的行數(shù)，列號域存儲了稀疏矩陣的列數(shù)。 這種三元組鏈表的缺點是實現(xiàn)矩陣運算操作算法的時間復雜度高，因為算法中若要訪問某行某列中的一個元素時，必須從頭指針進入后逐個結(jié)點查找。為降低矩陣運算操作算法的時間復雜度，提出了行指針數(shù)組結(jié)構(gòu)的三元組鏈表，其結(jié)構(gòu)如圖所示：第26頁/共31頁012345123456517311225119437750 列號非零元素行指針數(shù)組行號頭指針第27頁/共31頁 行指針數(shù)組結(jié)構(gòu)的三元組鏈表對于從某行進入后找某列元素的操作比較容易實現(xiàn)，但對于從某列進入后找某行元素的操作就不容易實現(xiàn)，