计算机软件基础.ppt

《计算机软件基础.ppt》由会员分享，可在线阅读，更多相关《计算机软件基础.ppt（92页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、陣列結構陣列結構 Chapter 21資料結構導論資料結構導論-C語言實作語言實作2.1 前言l陣列(Array)結構具有以下重要特徵：n一個陣列可以包含許多個陣列元素，陣列元素之個數又稱為陣列之大小。n同一個陣列裡的元素都具備相同的資料型態(Data Type)。n為方便資料的存取，可將陣列設計成一維(Dimension)、二維、三維，.，甚至更多維的陣列。2資料結構導論資料結構導論-C語言實作語言實作2.1 前言n宣告一個陣列時，作業系統會在記憶體空間指定一個起始位置給該陣列，並且根據陣列的資料型態和大小來配予一組連續的記憶體位置。n陣列元素在記憶體中的位置是連續且相鄰的，因此只要透過一套

2、簡單的陣列元素位址計算公式，便能得知某陣列元素所在之記憶體位置。n 經由陣列索引(Index)，可以迅速且直接地存取陣列中的元素資料。3資料結構導論資料結構導論-C語言實作語言實作2.2 宣告陣列 l宣告陣列時須定義下列幾項屬性：n陣列的資料型態。n陣列的名稱。n陣列的維度，即中括號()的個數。n陣列每一維度的元素個數，亦即陣列大小。n陣列元素的初值，此項可以省略。4資料結構導論資料結構導論-C語言實作語言實作2.2 宣告陣列 l以C語言為例，宣告陣列的語法如下：5資料結構導論資料結構導論-C語言實作語言實作2.2.1 一維陣列【例1】宣告一個可以用來存放6次考試成績的整數陣列。int gra

3、des6=83,75,92,74,88,93;6資料結構導論資料結構導論-C語言實作語言實作2.2.2 二維陣列【例2】宣告二維陣列。7資料結構導論資料結構導論-C語言實作語言實作2.2.2 二維陣列【例3】宣告grades506為一個可以用來儲存50位同學之5次資料結構考試成績之二維陣列。int grades506;8資料結構導論資料結構導論-C語言實作語言實作2.3 陣列的表示法 l一維陣列的表示法l二維陣列的表示法l三維陣列的表示法l多維度陣列的表示法l上三角矩陣l下三角矩陣l我們將陣列與矩陣視為同義詞9資料結構導論資料結構導論-C語言實作語言實作2.3.1 一維陣列的表示法lAn=A0

4、，A1，An-1l假設n一維陣列A在記憶體的起始位置為。n每個陣列元素所需的儲存空間是z個位元組(Byte)。n陣列元素Ai的記憶體位址為Loc(Ai)。l則：Loc(Ai)=A的起始位址+Ai相對於陣列起始位置之位移 =+i z。10資料結構導論資料結構導論-C語言實作語言實作2.3.1 一維陣列的表示法【例1】設陣列A是一個大小為10的一維陣列，且陣列A在記憶體之起始位置為1000，且每個元素都需要2個位元組的儲存空間。則 A7的記憶體位置為何？【解答】Loc(A7)=A的起始位址+A7相對於陣列起始位置之位移=1000+7 2=1014。11資料結構導論資料結構導論-C語言實作語言實作2

5、.3.1 一維陣列的表示法【例2】設d100 為一個實數陣列，每一個元素佔4個位元組。若d10的位址為2000，則d88的位址為何？【解答】Loc(d88)=d10的位址+d88相對於d10之位移 =2000+(88-10)4 =2312。12資料結構導論資料結構導論-C語言實作語言實作2.3.1 一維陣列的表示法lAf:t=Af，Af-1，.，A0，A1，.，At 。l假設n一維陣列Af在記憶體的起始位置為。n每個陣列元素所需的儲存空間是z個位元組(Byte)。n陣列元素Ai的記憶體位址為Loc(Ai)。l則：Loc(Ai)=A的起始位址+Ai相對於陣列起始位置之位移 =+(i-f)z。13

6、資料結構導論資料結構導論-C語言實作語言實作2.3.1 一維陣列的表示法【例3】設A-15:25在記憶體的起始位置為123，且每一元素佔4個位元組，則A3的位址為何？【解答】Loc(A3)=A-15:25的起始位址+A3相對於A-15:25之位移=123+(3-(-15)4=195。14資料結構導論資料結構導論-C語言實作語言實作2.3.2 二維陣列的表示法 lBmn=B00，B01，Bm-1n-1 。l共計有mn 個元素。15資料結構導論資料結構導論-C語言實作語言實作2.3.2 二維陣列的表示法 l將二維的陣列元素轉換成一維排列的方式有下列兩種：n以列為主(Row Major)。n以行為主

7、(Column Major)。16資料結構導論資料結構導論-C語言實作語言實作2.3.2 二維陣列的表示法 l以列為主(Row Major)的表示法：l假設n假設二維陣列B在記憶體的起始位置為。n陣列之個別元素所需的記憶體空間大小為z。n陣列元素Bij的記憶體位址為Loc(Bij)。l則：LocRM(Bij)=B的起始位址+Bij相對於陣列起始位置之位移 =+(i n+j)z。17資料結構導論資料結構導論-C語言實作語言實作2.3.2 二維陣列的表示法 l以行為主(Column Major)的表示法：l假設n假設二維陣列B在記憶體的起始位置為。n陣列之個別元素所需的記憶體空間大小為z。n陣列元

8、素Bij的記憶體位址為Loc(Bij)。l則：LocCM(Bij)=B的起始位址+Bij相對於陣列起始位置之位移 =+(j m+i)z。18資料結構導論資料結構導論-C語言實作語言實作2.3.2 二維陣列的表示法【例1】已知A12之記憶體位置為22，且A24和A42 之記憶體位置分別為30和40，則A55之位置為何？【解答】因為A24的記憶體位置30小於A42 的記憶體位置40，可見該陣列是採以列為主排列。因此：LocRM(Aij)=A的起始位址+Aij相對於陣列起始位置之位移 =+(i n+j)z。19資料結構導論資料結構導論-C語言實作語言實作2.3.2 二維陣列的表示法 LocRM(A2

9、4)=A12的位址+A24相對於A12之位移 =22+(2-1)n+(4-2)z =22+(n+2)z=30。所以，nz+2z=8(1)LocRM(A42)=A12的位址+A42相對於A12之位移 =22+(4-1)n+(2-2)z =22+(3n+0)z=40。所以，3nz=18，nz=6(2)，將(2)代入(1)得到 6+2z=8，z=1，代入(2)得到 n=6，因此 20資料結構導論資料結構導論-C語言實作語言實作2.3.2 二維陣列的表示法 LocRM(A55)=A12的位址+A55相對於A12之位移 =22+(5-1)n+(5-2)z =22+(4 6+3)1 =49。21資料結構導

10、論資料結構導論-C語言實作語言實作2.3.2 二維陣列的表示法【例2】設Af1:t1f2:t2 為一個二維陣列宣告，其記憶體起始位置為，每個元素所佔的記憶體空間為z。則陣列元素Aij之位置為何？【解答】n已知Af1f2在記憶體之起始位置為，且每個元素所佔的記憶體空間為 z。n設二維陣列A共有m列n行，則m=t1-f1+1，n =t2-f2+1。22資料結構導論資料結構導論-C語言實作語言實作2.3.2 二維陣列的表示法n以列為主 LocRM(Aij)=Af1f2的起始位址+Aij相對於Af1f2之位移 =+(i-f1)n+(j-f2)zn以行為主 LocCM(Aij)=Af1f2的起始位址+A

11、ij相對於Af1f2之位移 =+(j-f2)m+(i-f1)z 23資料結構導論資料結構導論-C語言實作語言實作2.3.3 三維陣列的表示法 int cubic323=1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9;l 它包括3個平面，每個平面有2列及3行。平面 列 行24資料結構導論資料結構導論-C語言實作語言實作2.3.3 三維陣列的表示法l假設我們宣告了一個三維陣列Clmnn l 代表第一個維度的大小。n m 代表第二個維度的大小。n n 代表第三個維度的大小。n共計有 lmn 個陣列元素。l假設nC000在記憶體中的起始位置為。n陣列之個別元素所需的記憶體空間大

12、小為z。25資料結構導論資料結構導論-C語言實作語言實作2.3.3 三維陣列的表示法l以列為主(Row Major)的表示法：n共計有 l 個平面，每個平面有 m 列與 n 行。LocRM(Cijk)=+(imn+jn+k)zl以行為主(Column Major)的表示法：n共計有 n 個平面，每個平面有 l 列與 m 行。LocCM(Cijk)=+(klm+jl+i)z 26資料結構導論資料結構導論-C語言實作語言實作2.3.4 多維度陣列的表示法 l假設n n 維度陣列Ds1s2s3sn在記憶體中的起始位置為。n其中s1，s2，sn分別為D陣列的第1維、第2維，第n維的元素個數。n每個陣列

13、元素所須要的記憶體儲存空間為z。27資料結構導論資料結構導論-C語言實作語言實作2.3.4 多維度陣列的表示法 l以列為主(Row Major)的表示法：LocRM(Di1i2in)=+(i1s2s3sn-1sn +i2s3s4sn-1sn +i3s4s5sn-1sn +in-3sn-2sn-1sn +in-2sn-1sn +in-1sn +in)z。28資料結構導論資料結構導論-C語言實作語言實作2.3.4 多維度陣列的表示法 l以行為主(Column Major)的表示法：LocCM(Di1i2in)=+(ins1s2sn-2sn-1 +in-1s1s2sn-3sn-2 +in-2s1s2

14、sn-4sn-3 +i3s1s2 +i2s1 +i1)z。29資料結構導論資料結構導論-C語言實作語言實作2.3.5 對角線矩陣的表示法 l對角線矩陣(Diagonal Matrix)n是一個方陣。n除了對角線的元素值可能不為0外，其餘元素值均為0。n亦即，矩陣元素vi,j=0，i j。30資料結構導論資料結構導論-C語言實作語言實作2.3.5 對角線矩陣的表示法 l對角線矩陣(Diagonal Matrix)n對角線矩陣DMmm共有m個非0元素。n我們可以直接用一個一維陣列Xm來表示對角線矩陣。n亦即Xi=DMii。31資料結構導論資料結構導論-C語言實作語言實作2.3.6 下三角矩陣的表示

15、法 l下三角矩陣(Lower Triangular Matrix)n它是一個方陣。n對角線以上(不含對角線)的元素值均為 0。32資料結構導論資料結構導論-C語言實作語言實作2.3.6 下三角矩陣的表示法 l假設n下三角矩陣式的陣列X在記憶體之起始位置為。n且每個陣列元素所需的記憶體空間為z。l採以列為主的儲存策略，則 LocRM(Xi,j)=+(i(i+1)/2+j)z。33資料結構導論資料結構導論-C語言實作語言實作2.3.6 下三角矩陣的表示法【例1】設Xnn為一個下三角矩陣，若要用一個一維陣列Ym來表示X，則m的最小值應該宣告為何？【解答】m=1+2+3+.+n =n(n+1)/2。3

16、4資料結構導論資料結構導論-C語言實作語言實作2.3.7 上三角矩陣的表示法 l上三角矩陣(Upper Triangular Matrix)n它是一個方陣。n對角線以下(不含對角線)的元素值均為 0。35資料結構導論資料結構導論-C語言實作語言實作2.3.7 上三角矩陣的表示法 l假設n下三角矩陣式的陣列X在記憶體之起始位置為。n且每個陣列元素所需的記憶體空間為z。l採以行為主的儲存策略，則 LocCM(Xi,j)=+(j(j+1)/2+i)z。36資料結構導論資料結構導論-C語言實作語言實作2.4 一維陣列的應用 l2.4.1 計數器(Counter)l2.4.2 暫存(Temporary

17、Store)l2.4.3 取代(Substitution)l2.4.4 索引(Indexing)l2.4.5 搜尋(Searching)l2.4.6 排序(Sorting)37資料結構導論資料結構導論-C語言實作語言實作2.4.1 計數器(Counter)l i=i+1;(或 i+;)。l int countn;/宣告 .counti=counti+1;/計數器+1 或 counti+;/計數器+138資料結構導論資料結構導論-C語言實作語言實作#include#include void dicetoss(int*count,int n);void main(void)int count6=0

18、;int i,n;clrscr();printf(請輸入擲骰子的次數:);scanf(%d,&n);dicetoss(count,n);2_dice_toss.c(p.2-26)39資料結構導論資料結構導論-C語言實作語言實作 printf(nn-);printf(n 共計投擲%2d 次，其中,n);for(i=0;i 6;i+)printf(n%d 點出現%2d 次,i+1,counti);printf(n-n);/*/*利用一個亂數產生函數(式)來模擬骰子的投擲*/*/void dicetoss(int*count,int n)int i,point;for(i=0;i n;i+)poin

19、t=rand()%6;countpoint=countpoint+1;40資料結構導論資料結構導論-C語言實作語言實作2.4.2 暫存(Temporary Store)l質數：大於1的數，除了1與本身以外沒有任何一個數能夠整除它時，該數稱為質數。n 2是最小的質數。n 3、5、7均是質數。n 4、6不是質數，因為4可以被2整除，6可以被2、3整除。41資料結構導論資料結構導論-C語言實作語言實作2.4.2 暫存(Temporary Store)l如何找出小於等於100的所有質數呢？l第一種方法：n根據質數的定義，判斷5是否為質數時，須將5除以2、3、4，只要能被其中一個數整除，那麼5就非質數，

20、否則5就是質數。n依此類推，判斷x是否為質數時，須將x除以2、3、4.、x-1，只要能被其中一個數整除，那麼x就非質數，否則x就是質數。42資料結構導論資料結構導論-C語言實作語言實作2_prime1.c(p.2-30)#include void main(void)int n,count=0;int i,j;enum boolean isprime;enum boolean false,true;clrscr();printf(請輸入大於 1 的整數:);scanf(%d,&n);printf(n不大於%d 的質數有.nn,n);43資料結構導論資料結構導論-C語言實作語言實作/*質數的定義

21、：一個正整數，除了 1 和本身以外沒有別的因數：一個正整數，除了 1 和本身以外不能被其他的數所整除 */for(i=1;i=n;i+)isprime=true;switch(i)case 1:/*1 非質數 */isprime=false;break;case 2:/*2 是最小的質數*/break;default:for(j=2;j 不大於%d 的質數共有%d 個,n,count);45資料結構導論資料結構導論-C語言實作語言實作2.4.2 暫存(Temporary Store)l第二種方法：n將第1個找到的質數暫存於prime0，將第2個找到的質數暫存於prime1，將第3個找到的質數暫

22、存於prime2，依此類推。n要判斷一個整數x是否為質數時，我們只須取出prime陣列裡已經找到的質數來當做除數，將x除以這些質數，如果都不能被這些質數整除，即可斷定x為質數。n因此，要判斷6是否為質數時，只須分別判斷6是否能被2、3、5整除即可，只要能被其中一個質數整除，6就非質數。因6能被2整除，非質數，不須再判斷能否被3、5整除了。46資料結構導論資料結構導論-C語言實作語言實作2_prime2.c(p.2-33)#include#include#define N 120int find_prime(int*prime,int n);void main(void)int i,n,coun

23、t=0;int primeN=0;clrscr();printf(請輸入大於 1 的整數:);scanf(%d,&n);printf(n不大於%d 的質數有.nn,n);/*找出不大於 n 的所有質數 */count=find_prime(prime,n);47資料結構導論資料結構導論-C語言實作語言實作/*印出不大於 n 的所有質數 */for(i=0;i=count;i+)printf(%d,primei);if(i+1)%15=0)/*每印滿 15 個質數就跳下一行*/printf(nn);printf(nn小於等於%d 的質數共有%d 個,n,count+1);/*找出=n 的所有質數

24、，採用以下定義 */*質數的定義：一個正整數，不能被小於本身的所有質數所整除 */*被找到的質數站存在陣列prime之中 */*-*/int find_prime(int*prime,int n)enum boolean isprime;enum boolean false,true;int i,j,count=-1;48資料結構導論資料結構導論-C語言實作語言實作 for(i=2;i=n;i+)isprime=true;switch(i)case 2:/*2 是最小的質數*/prime+count=i;break;default:for(j=0;primej!=0&primej=sqrt(i

25、)&isprime=true;j+)if(i%primej)=0)/*非質數 */isprime=false;else;if(isprime=true)prime+count=i;return count;49資料結構導論資料結構導論-C語言實作語言實作2.4.3 取代(Substitution)l要印出l則可用陣列來儲存花色和點數以取代之 50資料結構導論資料結構導論-C語言實作語言實作2_cards.c(p.2-36)#include char cf4=6,5,4,3;/*黑桃,梅花,方塊,紅心*/char cp132=A,2,3,4,5,6,7,8,9,10,J,Q,K;void mai

26、n(void)int i,j;clrscr();for(i=0;i=3;i+)for(j=0;j=12;j+)printf(%c%c%c,cfi,cpj0,cpj1);printf(n);51資料結構導論資料結構導論-C語言實作語言實作2.4.4 索引(Indexing)l索引：利用某一個陣列的元素值來當做另一個陣列的索引值。l尋找出眾數及其出現頻率 n一維陣列x15是一個含有15個元素的整數陣列，且陣列中的元素值均介於0與5之間。我們稱陣列x中出現次數最多的數為眾數。n宣告一個整數陣列count6，然後用counti來記錄x陣列中 i 的出現次數。n亦即 countxi=countxi+;5

27、2資料結構導論資料結構導論-C語言實作語言實作2_freq.c(p.2-38)#include#define N 15 /*輸入 15 個整數 */#define NUMBER 6 /*輸入的整數必須介於 0 至 5 之間*/int frequency(int*count);void main(void)int i,n;int xN=0;int countNUMBER=0;clrscr();printf(請輸入15個整數 i，0=i=5:n);53資料結構導論資料結構導論-C語言實作語言實作 for(i=0;i N;i+)scanf(%d,&xi);countxi=countxi+1;n=fr

28、equency(count);printf(n眾數為%d，共出現%d 次n,n,countn);54資料結構導論資料結構導論-C語言實作語言實作/*尋找眾數(當同時有好幾個最大者時，以輸入值較小者為眾數)*/int frequency(int*count)int i;int most_freq_no=count0;int n=0;/*眾數*/printf(ncount陣列之內容為:);printf(n-);for(i=0;i count%d=%d,i,counti);printf(%d 出現%d 次),i,counti);if(counti most_freq_no)most_freq_no=

29、counti;n=i;printf(n-);return n;55資料結構導論資料結構導論-C語言實作語言實作2.4.5 搜尋(Searching)l搜尋(Search)：從一群資料中找出滿足特定條件的資料之動作稱之。l搜尋條件通常有：n大於、等於、小於、大於或等於、不等於、小於或等於等多種組合。56資料結構導論資料結構導論-C語言實作語言實作2.4.5.1 循序搜尋法(Sequential Search)l循序搜尋法(Sequential Search)：就是從頭到尾一筆一筆地搜尋、比較。【例1】找出鍵值大於70的資料？n必須從d0開始逐筆加以比對，直到比完d7為止(共計比較8次)n結果找到

30、d2、d4、d5、d7等4筆資料57資料結構導論資料結構導論-C語言實作語言實作2.4.5.2 二元搜尋法(Binary Search)l二元搜尋法的特徵如下：n資料須事先經過排序。n每次都從可能有符合條件的一組資料中，拿第中間筆資料(假設di)出來跟鍵值k相比。n每次比較完之後，大約可以捨去一半的資料，所以搜尋的速度很快。58資料結構導論資料結構導論-C語言實作語言實作2.4.5.2 二元搜尋法(Binary Search)【例2】二元搜尋法。n 找出鍵值等於120的資料？59資料結構導論資料結構導論-C語言實作語言實作2.4.5.2 二元搜尋法(Binary Search)【例2】二元搜尋

31、法。n找出鍵值大於70的資料？60資料結構導論資料結構導論-C語言實作語言實作2_b_search.c(p.2-46)#include#define Size 8#define true 1void print_array_data(int*d,int n);int binary_search(int*d,int low_index,int high_index,int key,int*index);/*列印陣列元素值 */void print_array_data(int*d,int n)int i;printf(陣列元素 d0 1 2 3 4 5 6 7 n);printf(-n);pri

32、ntf(鍵 值=);for(i=0;i key|dhigh_index key)/*not found*/return(-1);count=-1;while(low_index dmiddle)low_index=middle+1;/*下一回合須搜尋後半部*/else if(key=low_index&key=di)/*比較前面幾筆是否同鍵值*/index+count=i-;i=middle+1;while(i -1)for(i=0;i 共找到%d 筆！nn,count+1);else printf(n=找不到鍵值%d！nn,key);65資料結構導論資料結構導論-C語言實作語言實作2.4.6

33、 排序(Sorting)l排序(SORT)：乃將原始資料依照某個特定的次序加以重新排列。l排序時須指定：n用哪一個資料項來排序？被用來排序的資料項又稱為鍵(Key)n排序的順序遞增：即由小到大。遞減：即由大到小。66資料結構導論資料結構導論-C語言實作語言實作2.4.6.1 氣泡浮昇排序法(Bubble Sort)l假設我們已經宣告了一個整數陣列dn，用來存放編號為0、1、2、.、n-1的n筆資料。且d0=v0、d1=v1、d2=v2、.dn-2=vn-2、dn-1=vn-1。67資料結構導論資料結構導論-C語言實作語言實作2.4.6.1 氣泡浮昇排序法(Bubble Sort)l採用氣泡浮昇

34、排序法的將一組資料依鍵值遞增排序之步驟說明如下：n第1回合：從第0筆資料開始一直到第n-1筆資料，持續比較相鄰兩筆資料之大小，若vi大於vi+1，則須將兩者交換位置，亦即須將vi 儲存到di+1，vi+1 儲存到di。換言之，必須保持小的在前，大的在後之順序。在第1回合處理完後，陣列中最大的數值已經被存放到dn-1的位置。68資料結構導論資料結構導論-C語言實作語言實作2.4.6.1 氣泡浮昇排序法(Bubble Sort)n第2回合：從第0筆資料開始一直到第n-2筆資料，持續比較相鄰兩筆資料之大小，若vi大於vi+1，則須將兩者交換位置，亦即須將vi 儲存到di+1，vi+1 儲存到di。在

35、第2回合處理完後，陣列中第2大數的值已經被存放到dn-2的位置。n重複執行上述步驟，共計(n-1)回合，即可將陣列資料排列成由小到大的遞增順序。69資料結構導論資料結構導論-C語言實作語言實作2.4.6.1 氣泡浮昇排序法(Bubble Sort)【例2】氣泡浮昇排序法。70資料結構導論資料結構導論-C語言實作語言實作2.4.6.1 氣泡浮昇排序法(Bubble Sort)【例2】氣泡浮昇排序法。71資料結構導論資料結構導論-C語言實作語言實作2_b_sort.c(p.2-55)#include#define Size 9void print_org_data(const int d,int

36、n);void print_array_data(const int d,int n);void swap(int*x,int*y);void bubble_sort_ascending(int d,int n);/*列印排序前的鍵值資料(陣列 d 共有 n 個元素)*/void print_org_data(const int d,int n)int i;clrscr();printf(陣列元素 d0 1 2 3 4 5 6 7 8n);printf(-n);printf(=);72資料結構導論資料結構導論-C語言實作語言實作 for(i=0;i n;i+)printf(%2d ,di);p

37、rintf(n-n);/*印出陣列 d 的內容(陣列 d 共有 n 個元素)*/void print_array_data(const int d,int n)int i;for(i=0;i n;i+)printf(%2d ,di);printf(n);73資料結構導論資料結構導論-C語言實作語言實作/*將 x,y 兩變數之值互換 */void swap(int*x,int*y)int z=*x;*x=*y;*y=z;/*氣泡浮昇排序法(1.陣列 d 共有 n 個元素 2.遞增排序)*/void bubble_sort_ascending(int d,int n)int i,j;for(i=0

38、;i n-1;i+)for(j=0;j dj+1)swap(&dj,&dj+1);printf(第%d回合=,i+1);print_array_data(d,n);74資料結構導論資料結構導論-C語言實作語言實作void main(void)int dSize=83,66,55,21,88,18,33,47,3;print_org_data(d,Size);/*列印排序前之鍵值資料*/*將陣列 d 裡的 Size 個鍵值遞增排序*/bubble_sort_ascending(d,Size);75資料結構導論資料結構導論-C語言實作語言實作2.5 二維陣列的應用 l2.5.1 轉置矩陣(Tran

39、spose Matrix)l2.5.2 對稱矩陣(Symmetric Matrix)l2.5.3 反射矩陣(Reflection Matrix)l2.5.4 矩陣相加(Matrix Addition)l2.5.5 矩陣相減(Matrix Subtraction)l2.5.6 矩陣乘積(Matrix Multiplication)l2.5.7 稀疏矩陣(Sparse Matrix)76資料結構導論資料結構導論-C語言實作語言實作2.5.1 轉置矩陣(Transpose Matrix)l設M是一個mn矩陣，而TM為其轉置矩陣，則：n TM為一個nm矩陣。n M的第0列元素成為TM的第0行元素，M的

40、第1列元素成為TM的第1行元素，M的第m-1列元素成為TM的第m-1行元素。n 亦即 TMji=Mij。77資料結構導論資料結構導論-C語言實作語言實作2.5.1 轉置矩陣(Transpose Matrix)【例1】轉置矩陣。78資料結構導論資料結構導論-C語言實作語言實作2_t_matrix.c(p.2-60)#include void main(void)int M1010=0,TM1010=0;int i,j,m,n;/*輸入矩陣 M 之元素值，並產生轉置矩陣 TM */clrscr();printf(請輸入二維矩陣 Mmn 之大小，即 m n 之值:);scanf(%d%d,&m,&n

41、);printf(n請按【列】之順序輸入矩陣 M 的元素值:n);for(i=0;i m;i+)for(j=0;j n;j+)scanf(%d,&Mij);/*輸入矩陣 M 的元素值 */TMji=Mij;/*TM 為矩陣 M 的轉置矩陣*/79資料結構導論資料結構導論-C語言實作語言實作 /*列印出原始矩陣 M */printf(n矩陣 M%d%d 的元素資料如下:n,m,n);for(i=0;i m;i+)for(j=0;j n;j+)printf(%3d,Mij);printf(n);/*列印出轉置矩陣 TM */printf(nn轉置矩陣 TM%d%d 的元素資料如下:n,n,m);f

42、or(i=0;i n;i+)for(j=0;j m;j+)printf(%3d,TMij);printf(n);80資料結構導論資料結構導論-C語言實作語言實作2.5.2 對稱矩陣(Symmetric Matrix)l 對稱矩陣為一方陣，且元素值vij=vji。81資料結構導論資料結構導論-C語言實作語言實作2.5.3 反射矩陣(Reflection Matrix)l反射矩陣(RMmxn)是將原始矩陣(Mmxn)進行水平方向的鏡射。82資料結構導論資料結構導論-C語言實作語言實作2.5.4 矩陣相加(Matrix Addition)lcij=aij+bij。【例1】矩陣相加。83資料結構導論資

43、料結構導論-C語言實作語言實作2.5.5 矩陣相減(Matrix Subtraction)lcij=aij-bij。【例1】矩陣相減。84資料結構導論資料結構導論-C語言實作語言實作2.5.6 矩陣乘積(Matrix Multiplication)85資料結構導論資料結構導論-C語言實作語言實作2.5.6 矩陣乘積(Matrix Multiplication)【例1】矩陣乘積。86資料結構導論資料結構導論-C語言實作語言實作2_m_matrix.c(p.2-71)#include void main(void)int a1010=0,b1010=0,c1010=0;int i,j,k,m,n,

44、n1,p;/*輸入矩陣 a 之元素值 */clrscr();printf(請輸入二維矩陣 amn 之大小，即 m n 之值:);scanf(%d%d,&m,&n);printf(n請按【列】之順序輸入矩陣 a 的元素值:n);for(i=0;i m;i+)for(j=0;j a 矩陣之行數必須等於 b 矩陣之列數，請重新輸入！n);else break;printf(n請按【列】之順序輸入矩陣 b 的元素值:n);for(i=0;i n;i+)for(j=0;j p;j+)scanf(%d,&bij);/*輸入矩陣 b 的元素值*/*cnp=amn*bnp */for(i=0;i m;i+)f

45、or(j=0;j p;j+)for(k=0;k n;k+)cij=cij+aik*bkj;88資料結構導論資料結構導論-C語言實作語言實作 /*-*/*列印出矩陣 c */*-*/printf(n);printf(a x b 之結果如下:n);for(i=0;i m;i+)for(j=0;j p;j+)printf(%3d,cij);printf(n);89資料結構導論資料結構導論-C語言實作語言實作2.5.7 稀疏矩陣(Sparse Matrix)l一個矩陣中，若大多數的元素值均為0，則稱該矩陣為稀疏矩陣。l這裡所謂的元素值為0在應用上包括幾種涵義：n真的為0。n為虛值(Null Value)，亦即沒有資料值 90資料結構導論資料結構導論-C語言實作語言實作2.5.7 稀疏矩陣(Sparse Matrix)【例1】稀疏矩陣的表示法。91資料結構導論資料結構導論-C語言實作語言實作2.5.7 稀疏矩陣(Sparse Matrix)【例2】試設計一個用以表示三維稀疏矩陣的表示法。【解答】設三維稀疏矩陣SMmxnxo各維之大小 分別為m、n、o，且稀疏矩陣中非0元素 共計p個。92資料結構導論資料結構導論-C語言實作語言實作