Download presentation
Presentation is loading. Please wait.
1
Chapter 2 陣列結構 資料結構導論 - C語言實作
2
2.1 前言 「陣列」(Array)結構具有以下重要特徵： 一個陣列可以包含許多個陣列元素，陣列元素之個數又稱為陣列之大小。
同一個陣列裡的元素都具備相同的資料型態(Data Type)。 為方便資料的存取，可將陣列設計成一維(Dimension)、二維、三維，...，甚至更多維的陣列。 資料結構導論 - C語言實作
3
2.1 前言 宣告一個陣列時，作業系統會在記憶體空間指定一個起始位置給該陣列，並且根據陣列的資料型態和大小來配予一組連續的記憶體位置。
陣列元素在記憶體中的位置是連續且相鄰的，因此只要透過一套簡單的陣列元素位址計算公式，便能得知某陣列元素所在之記憶體位置。 經由陣列索引(Index)，可以迅速且直接地存取陣列中的元素資料。 資料結構導論 - C語言實作
4
2.2 宣告陣列 宣告陣列時須定義下列幾項屬性： 陣列的資料型態。 陣列的名稱。 陣列的維度，即中括號([ ])的個數。
陣列每一維度的元素個數，亦即陣列大小。 陣列元素的初值，此項可以省略。 資料結構導論 - C語言實作
![2.2 宣告陣列 宣告陣列時須定義下列幾項屬性： 陣列的資料型態。 陣列的名稱。 陣列的維度，即中括號([ ])的個數。](http://slidesplayer.com/slide/15038733/91/images/4/2.2+%E5%AE%A3%E5%91%8A%E9%99%A3%E5%88%97+%E5%AE%A3%E5%91%8A%E9%99%A3%E5%88%97%E6%99%82%E9%A0%88%E5%AE%9A%E7%BE%A9%E4%B8%8B%E5%88%97%E5%B9%BE%E9%A0%85%E5%B1%AC%E6%80%A7%EF%BC%9A+%E9%99%A3%E5%88%97%E7%9A%84%E8%B3%87%E6%96%99%E5%9E%8B%E6%85%8B%E3%80%82+%E9%99%A3%E5%88%97%E7%9A%84%E5%90%8D%E7%A8%B1%E3%80%82+%E9%99%A3%E5%88%97%E7%9A%84%E7%B6%AD%E5%BA%A6%EF%BC%8C%E5%8D%B3%E4%B8%AD%E6%8B%AC%E8%99%9F%28%5B+%5D%29%E7%9A%84%E5%80%8B%E6%95%B8%E3%80%82.jpg "陣列每一維度的元素個數，亦即陣列大小。 陣列元素的初值，此項可以省略。 資料結構導論 - C語言實作.")
5
2.2 宣告陣列 以C語言為例，宣告陣列的語法如下： 資料結構導論 - C語言實作
6
2.2.1 一維陣列 【例1】宣告一個可以用來存放6次考試成績的整數陣列。
int grades[6] = {83, 75, 92, 74, 88, 93}; 資料結構導論 - C語言實作
7
2.2.2 二維陣列 【例2】宣告二維陣列。 資料結構導論 - C語言實作
8
2.2.2 二維陣列 【例3】宣告grades[50][6]為一個可以用來儲存50位同學之5次資料結構考試成績之二維陣列。
int grades[50][6] ; 資料結構導論 - C語言實作
![2.2.2 二維陣列 【例3】宣告grades[50][6]為一個可以用來儲存50位同學之5次資料結構考試成績之二維陣列。](http://slidesplayer.com/slide/15038733/91/images/8/2.2.2+%E4%BA%8C%E7%B6%AD%E9%99%A3%E5%88%97+%E3%80%90%E4%BE%8B3%E3%80%91%E5%AE%A3%E5%91%8Agrades%5B50%5D%5B6%5D%E7%82%BA%E4%B8%80%E5%80%8B%E5%8F%AF%E4%BB%A5%E7%94%A8%E4%BE%86%E5%84%B2%E5%AD%9850%E4%BD%8D%E5%90%8C%E5%AD%B8%E4%B9%8B5%E6%AC%A1%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E8%80%83%E8%A9%A6%E6%88%90%E7%B8%BE%E4%B9%8B%E4%BA%8C%E7%B6%AD%E9%99%A3%E5%88%97%E3%80%82.jpg "int grades[50][6] ; 資料結構導論 - C語言實作.")
9
2.3 陣列的表示法 一維陣列的表示法 二維陣列的表示法 三維陣列的表示法 多維度陣列的表示法 上三角矩陣 下三角矩陣
我們將「陣列」與「矩陣」視為同義詞 資料結構導論 - C語言實作
10
2.3.1 一維陣列的表示法 A[n] = {A[0]，A[1]，…，A[n-1]} 假設 則： 一維陣列A在記憶體的起始位置為α。
每個陣列元素所需的儲存空間是z個位元組(Byte) 。 陣列元素A[i]的記憶體位址為Loc(A[i]) 。 則： Loc(A[i]) = A的起始位址 + A[i]相對於陣列起始位置之位移 = α + i z。 資料結構導論 - C語言實作
![2.3.1 一維陣列的表示法 A[n] = {A[0]，A[1]，…，A[n-1]} 假設 則： 一維陣列A在記憶體的起始位置為α。](http://slidesplayer.com/slide/15038733/91/images/10/2.3.1+%E4%B8%80%E7%B6%AD%E9%99%A3%E5%88%97%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%B3%95+A%5Bn%5D+%3D+%7BA%5B0%5D%EF%BC%8CA%5B1%5D%EF%BC%8C%E2%80%A6%EF%BC%8CA%5Bn-1%5D%7D+%E5%81%87%E8%A8%AD+%E5%89%87%EF%BC%9A+%E4%B8%80%E7%B6%AD%E9%99%A3%E5%88%97A%E5%9C%A8%E8%A8%98%E6%86%B6%E9%AB%94%E7%9A%84%E8%B5%B7%E5%A7%8B%E4%BD%8D%E7%BD%AE%E7%82%BA%CE%B1%E3%80%82.jpg "每個陣列元素所需的儲存空間是z個位元組(Byte) 。 陣列元素A[i]的記憶體位址為Loc(A[i]) 。 則： Loc(A[i]) = A的起始位址 + A[i]相對於陣列起始位置之位移. = α + i z。 資料結構導論 - C語言實作.")
11
2.3.1 一維陣列的表示法 【例1】設陣列A是一個大小為10的一維陣列，且陣列A在記憶體之起始位置為1000，且每個元素都需要2個位元組的儲存空間。則 A[7]的記憶體位置為何？ 【解答】 Loc(A[7]) = A的起始位址 + A[7]相對於陣列起始位置之位移 = 2 = 1014。 資料結構導論 - C語言實作
![2.3.1 一維陣列的表示法 【例1】設陣列A是一個大小為10的一維陣列，且陣列A在記憶體之起始位置為1000，且每個元素都需要2個位元組的儲存空間。則 A[7]的記憶體位置為何？ 【解答】](http://slidesplayer.com/slide/15038733/91/images/11/2.3.1+%E4%B8%80%E7%B6%AD%E9%99%A3%E5%88%97%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%B3%95+%E3%80%90%E4%BE%8B1%E3%80%91%E8%A8%AD%E9%99%A3%E5%88%97A%E6%98%AF%E4%B8%80%E5%80%8B%E5%A4%A7%E5%B0%8F%E7%82%BA10%E7%9A%84%E4%B8%80%E7%B6%AD%E9%99%A3%E5%88%97%EF%BC%8C%E4%B8%94%E9%99%A3%E5%88%97A%E5%9C%A8%E8%A8%98%E6%86%B6%E9%AB%94%E4%B9%8B%E8%B5%B7%E5%A7%8B%E4%BD%8D%E7%BD%AE%E7%82%BA1000%EF%BC%8C%E4%B8%94%E6%AF%8F%E5%80%8B%E5%85%83%E7%B4%A0%E9%83%BD%E9%9C%80%E8%A6%812%E5%80%8B%E4%BD%8D%E5%85%83%E7%B5%84%E7%9A%84%E5%84%B2%E5%AD%98%E7%A9%BA%E9%96%93%E3%80%82%E5%89%87+A%5B7%5D%E7%9A%84%E8%A8%98%E6%86%B6%E9%AB%94%E4%BD%8D%E7%BD%AE%E7%82%BA%E4%BD%95%EF%BC%9F+%E3%80%90%E8%A7%A3%E7%AD%94%E3%80%91.jpg "Loc(A[7]) = A的起始位址 + A[7]相對於陣列起始位置之位移 = 2 = 1014。 資料結構導論 - C語言實作.")
12
2.3.1 一維陣列的表示法 【例2】設d[100] 為一個實數陣列，每一個元素佔4個位元組。若d[10]的位址為2000，則d[88]的位址為何？ 【解答】 Loc(d[88]) = d[10]的位址 + d[88]相對於d[10]之位移 = (88-10) = 2312。 資料結構導論 - C語言實作
![2.3.1 一維陣列的表示法 【例2】設d[100] 為一個實數陣列，每一個元素佔4個位元組。若d[10]的位址為2000，則d[88]的位址為何？ 【解答】](http://slidesplayer.com/slide/15038733/91/images/12/2.3.1+%E4%B8%80%E7%B6%AD%E9%99%A3%E5%88%97%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%B3%95+%E3%80%90%E4%BE%8B2%E3%80%91%E8%A8%ADd%5B100%5D+%E7%82%BA%E4%B8%80%E5%80%8B%E5%AF%A6%E6%95%B8%E9%99%A3%E5%88%97%EF%BC%8C%E6%AF%8F%E4%B8%80%E5%80%8B%E5%85%83%E7%B4%A0%E4%BD%944%E5%80%8B%E4%BD%8D%E5%85%83%E7%B5%84%E3%80%82%E8%8B%A5d%5B10%5D%E7%9A%84%E4%BD%8D%E5%9D%80%E7%82%BA2000%EF%BC%8C%E5%89%87d%5B88%5D%E7%9A%84%E4%BD%8D%E5%9D%80%E7%82%BA%E4%BD%95%EF%BC%9F+%E3%80%90%E8%A7%A3%E7%AD%94%E3%80%91.jpg "Loc(d[88]) = d[10]的位址 + d[88]相對於d[10]之位移 = (88-10) 4 = 2312。 資料結構導論 - C語言實作.")
13
2.3.1 一維陣列的表示法 A[f:t] = {A[f] ，A[f-1] ，... ， A[0] ，
A[1] ， ... ，A[t] } 。 假設 一維陣列A[f]在記憶體的起始位置為α。 每個陣列元素所需的儲存空間是z個位元組(Byte) 。 陣列元素A[i]的記憶體位址為Loc(A[i])。 則： Loc(A[i]) = A的起始位址 + A[i]相對於陣列起始位置之位移 = α + (i-f) z。 資料結構導論 - C語言實作
![2.3.1 一維陣列的表示法 A[f:t] = {A[f] ，A[f-1] ，... ， A[0] ，](http://slidesplayer.com/slide/15038733/91/images/13/2.3.1+%E4%B8%80%E7%B6%AD%E9%99%A3%E5%88%97%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%B3%95+A%5Bf%3At%5D+%3D+%7BA%5Bf%5D+%EF%BC%8CA%5Bf-1%5D+%EF%BC%8C...+%EF%BC%8C+A%5B0%5D+%EF%BC%8C.jpg "A[1] ， ... ，A[t] } 。 假設. 一維陣列A[f]在記憶體的起始位置為α。 每個陣列元素所需的儲存空間是z個位元組(Byte) 。 陣列元素A[i]的記憶體位址為Loc(A[i])。 則： Loc(A[i]) = A的起始位址 + A[i]相對於陣列起始位置之位移. = α + (i-f) z。 資料結構導論 - C語言實作.")
14
2.3.1 一維陣列的表示法 【例3】設A[-15:25]在記憶體的起始位置為123，且每一元素佔4個位元組，則A[3]的位址為何？
【解答】 Loc(A[3]) = A[-15:25]的起始位址 + A[3]相對於A[-15:25]之位移 = (3-(-15)) 4 = 195。 資料結構導論 - C語言實作
![2.3.1 一維陣列的表示法 【例3】設A[-15:25]在記憶體的起始位置為123，且每一元素佔4個位元組，則A[3]的位址為何？](http://slidesplayer.com/slide/15038733/91/images/14/2.3.1+%E4%B8%80%E7%B6%AD%E9%99%A3%E5%88%97%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%B3%95+%E3%80%90%E4%BE%8B3%E3%80%91%E8%A8%ADA%5B-15%3A25%5D%E5%9C%A8%E8%A8%98%E6%86%B6%E9%AB%94%E7%9A%84%E8%B5%B7%E5%A7%8B%E4%BD%8D%E7%BD%AE%E7%82%BA123%EF%BC%8C%E4%B8%94%E6%AF%8F%E4%B8%80%E5%85%83%E7%B4%A0%E4%BD%944%E5%80%8B%E4%BD%8D%E5%85%83%E7%B5%84%EF%BC%8C%E5%89%87A%5B3%5D%E7%9A%84%E4%BD%8D%E5%9D%80%E7%82%BA%E4%BD%95%EF%BC%9F.jpg "【解答】 Loc(A[3]) = A[-15:25]的起始位址 + A[3]相對於A[-15:25]之位移 = (3-(-15)) 4 = 195。 資料結構導論 - C語言實作.")
15
2.3.2 二維陣列的表示法 B[m][n] = {B[0][0]，B[0][1]，…， B[m-1][n-1] } 。
資料結構導論 - C語言實作
![2.3.2 二維陣列的表示法 B[m][n] = {B[0][0]，B[0][1]，…， B[m-1][n-1] } 。](http://slidesplayer.com/slide/15038733/91/images/15/2.3.2+%E4%BA%8C%E7%B6%AD%E9%99%A3%E5%88%97%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%B3%95+B%5Bm%5D%5Bn%5D+%3D+%7BB%5B0%5D%5B0%5D%EF%BC%8CB%5B0%5D%5B1%5D%EF%BC%8C%E2%80%A6%EF%BC%8C+B%5Bm-1%5D%5Bn-1%5D+%7D+%E3%80%82.jpg "資料結構導論 - C語言實作.")
16
2.3.2 二維陣列的表示法 將二維的陣列元素轉換成一維排列的方式有下列兩種： 以列為主(Row Major) 。
以行為主(Column Major) 。 資料結構導論 - C語言實作
17
2.3.2 二維陣列的表示法 以列為主(Row Major)的表示法： 假設 則： 假設二維陣列B在記憶體的起始位置為α 。
陣列之個別元素所需的記憶體空間大小為z 。 陣列元素B[i][j]的記憶體位址為Loc(B[i][j]) 。 則： LocRM(B[i][j]) = B的起始位址 + B[i][j]相對於陣列起始位置之位移 = α + (i n + j) z 。 資料結構導論 - C語言實作
18
2.3.2 二維陣列的表示法 以行為主(Column Major)的表示法： 假設 則： 假設二維陣列B在記憶體的起始位置為α 。
陣列之個別元素所需的記憶體空間大小為z 。 陣列元素B[i][j]的記憶體位址為Loc(B[i][j]) 。 則： LocCM(B[i][j]) = B的起始位址 + B[i][j]相對於陣列起始位置之位移 = α + (j m + i) z 。 資料結構導論 - C語言實作
19
2.3.2 二維陣列的表示法 【例1】已知A[1][2]之記憶體位置為22，且A[2][4]和A[4][2] 之記憶體位置分別為30和40，則A[5][5]之位置為何？ 【解答】 因為A[2][4]的記憶體位置30小於A[4][2] 的記憶體位置40，可見該陣列是採「以列為主」排列。因此： LocRM(A[i][j]) = A的起始位址 + A[i][j]相對於陣列起始位置之位移 = α + (i n + j) z。 資料結構導論 - C語言實作
![2.3.2 二維陣列的表示法 【例1】已知A[1][2]之記憶體位置為22，且A[2][4]和A[4][2] 之記憶體位置分別為30和40，則A[5][5]之位置為何？ 【解答】 因為A[2][4]的記憶體位置30小於A[4][2] 的記憶體位置40，可見該陣列是採「以列為主」排列。因此：](http://slidesplayer.com/slide/15038733/91/images/19/2.3.2+%E4%BA%8C%E7%B6%AD%E9%99%A3%E5%88%97%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%B3%95+%E3%80%90%E4%BE%8B1%E3%80%91%E5%B7%B2%E7%9F%A5A%5B1%5D%5B2%5D%E4%B9%8B%E8%A8%98%E6%86%B6%E9%AB%94%E4%BD%8D%E7%BD%AE%E7%82%BA22%EF%BC%8C%E4%B8%94A%5B2%5D%5B4%5D%E5%92%8CA%5B4%5D%5B2%5D+%E4%B9%8B%E8%A8%98%E6%86%B6%E9%AB%94%E4%BD%8D%E7%BD%AE%E5%88%86%E5%88%A5%E7%82%BA30%E5%92%8C40%EF%BC%8C%E5%89%87A%5B5%5D%5B5%5D%E4%B9%8B%E4%BD%8D%E7%BD%AE%E7%82%BA%E4%BD%95%EF%BC%9F+%E3%80%90%E8%A7%A3%E7%AD%94%E3%80%91+%E5%9B%A0%E7%82%BAA%5B2%5D%5B4%5D%E7%9A%84%E8%A8%98%E6%86%B6%E9%AB%94%E4%BD%8D%E7%BD%AE30%E5%B0%8F%E6%96%BCA%5B4%5D%5B2%5D+%E7%9A%84%E8%A8%98%E6%86%B6%E9%AB%94%E4%BD%8D%E7%BD%AE40%EF%BC%8C%E5%8F%AF%E8%A6%8B%E8%A9%B2%E9%99%A3%E5%88%97%E6%98%AF%E6%8E%A1%E3%80%8C%E4%BB%A5%E5%88%97%E7%82%BA%E4%B8%BB%E3%80%8D%E6%8E%92%E5%88%97%E3%80%82%E5%9B%A0%E6%AD%A4%EF%BC%9A.jpg "LocRM(A[i][j]) = A的起始位址 + A[i][j]相對於陣列起始位置之位移 = α + (i n + j) z。 資料結構導論 - C語言實作.")
20
2.3.2 二維陣列的表示法 LocRM(A[2][4]) = A[1][2]的位址 + A[2][4]相對於A[1][2]之位移
= 22 + ((2-1) n + (4-2)) z = 22 + (n + 2) z = 30。 所以，nz + 2z = 8 …………(1) LocRM(A[4][2]) = A[1][2]的位址 + A[4][2]相對於A[1][2]之位移 = 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 ，因此 資料結構導論 - C語言實作
![2.3.2 二維陣列的表示法 LocRM(A[2][4]) = A[1][2]的位址 + A[2][4]相對於A[1][2]之位移](http://slidesplayer.com/slide/15038733/91/images/20/2.3.2+%E4%BA%8C%E7%B6%AD%E9%99%A3%E5%88%97%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%B3%95+LocRM%28A%5B2%5D%5B4%5D%29+%3D+A%5B1%5D%5B2%5D%E7%9A%84%E4%BD%8D%E5%9D%80+%2B+A%5B2%5D%5B4%5D%E7%9B%B8%E5%B0%8D%E6%96%BCA%5B1%5D%5B2%5D%E4%B9%8B%E4%BD%8D%E7%A7%BB.jpg "= 22 + ((2-1) n + (4-2)) z. = 22 + (n + 2) z = 30。 所以，nz + 2z = 8 …………(1) LocRM(A[4][2]) = A[1][2]的位址 + A[4][2]相對於A[1][2]之位移. = 22 + ((4-1) n + (2-2)) z. = 22 + (3n + 0) z = 40。 所以，3nz = 18 ，nz = 6 …………(2) ，將(2)代入(1)得到 z = 8，z = 1，代入(2) 得到 n = 6 ，因此. 資料結構導論 - C語言實作.")
21
2.3.2 二維陣列的表示法 LocRM(A[5][5]) = A[1][2]的位址 + A[5][5]相對於A[1][2]之位移 = 22 + ((5-1) n + (5-2)) z = 22 + (4 6 + 3) = 49。 資料結構導論 - C語言實作
22
2.3.2 二維陣列的表示法 【例2】設A[f1:t1][f2:t2] 為一個二維陣列宣告，其記憶體起始位置為α，每個元素所佔的記憶體空間為z。則陣列元素A[i][j]之位置為何？ 【解答】 已知A[f1][f2]在記憶體之起始位置為α，且每個元素所佔的記憶體空間為 z。 設二維陣列A共有m列n行，則 m = t1-f1+1， n = t2-f2+1。 資料結構導論 - C語言實作
![2.3.2 二維陣列的表示法 【例2】設A[f1:t1][f2:t2] 為一個二維陣列宣告，其記憶體起始位置為α，每個元素所佔的記憶體空間為z。則陣列元素A[i][j]之位置為何？ 【解答】 已知A[f1][f2]在記憶體之起始位置為α，且每個元素所佔的記憶體空間為 z。](http://slidesplayer.com/slide/15038733/91/images/22/2.3.2+%E4%BA%8C%E7%B6%AD%E9%99%A3%E5%88%97%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%B3%95+%E3%80%90%E4%BE%8B2%E3%80%91%E8%A8%ADA%5Bf1%3At1%5D%5Bf2%3At2%5D+%E7%82%BA%E4%B8%80%E5%80%8B%E4%BA%8C%E7%B6%AD%E9%99%A3%E5%88%97%E5%AE%A3%E5%91%8A%EF%BC%8C%E5%85%B6%E8%A8%98%E6%86%B6%E9%AB%94%E8%B5%B7%E5%A7%8B%E4%BD%8D%E7%BD%AE%E7%82%BA%CE%B1%EF%BC%8C%E6%AF%8F%E5%80%8B%E5%85%83%E7%B4%A0%E6%89%80%E4%BD%94%E7%9A%84%E8%A8%98%E6%86%B6%E9%AB%94%E7%A9%BA%E9%96%93%E7%82%BAz%E3%80%82%E5%89%87%E9%99%A3%E5%88%97%E5%85%83%E7%B4%A0A%5Bi%5D%5Bj%5D%E4%B9%8B%E4%BD%8D%E7%BD%AE%E7%82%BA%E4%BD%95%EF%BC%9F+%E3%80%90%E8%A7%A3%E7%AD%94%E3%80%91+%E5%B7%B2%E7%9F%A5A%5Bf1%5D%5Bf2%5D%E5%9C%A8%E8%A8%98%E6%86%B6%E9%AB%94%E4%B9%8B%E8%B5%B7%E5%A7%8B%E4%BD%8D%E7%BD%AE%E7%82%BA%CE%B1%EF%BC%8C%E4%B8%94%E6%AF%8F%E5%80%8B%E5%85%83%E7%B4%A0%E6%89%80%E4%BD%94%E7%9A%84%E8%A8%98%E6%86%B6%E9%AB%94%E7%A9%BA%E9%96%93%E7%82%BA+z%E3%80%82.jpg "設二維陣列A共有m列n行，則 m = t1-f1+1， n = t2-f2+1。 資料結構導論 - C語言實作.")
23
2.3.2 二維陣列的表示法 以列為主 LocRM(A[i][j]) = A[f1][f2]的起始位址 A[i][j]相對於A[f1][f2]之位移 = α + ((i-f1) n + (j-f2)) z 以行為主 LocCM(A[i][j]) = A[f1][f2]的起始位址 A[i][j]相對於A[f1][f2]之位移 = α + ((j-f2) m + (i-f1)) z 資料結構導論 - C語言實作
24
2.3.3 三維陣列的表示法 int cubic[3][2][3] = { {1,2,3,4,5,6}, {7,8,9,1,2,3},
{4,5,6,7,8,9}}; 它包括3個平面，每個平面有2列及3行。 平面 列 行 資料結構導論 - C語言實作
![2.3.3 三維陣列的表示法 int cubic[3][2][3] = { {1,2,3,4,5,6}, {7,8,9,1,2,3},](http://slidesplayer.com/slide/15038733/91/images/24/2.3.3+%E4%B8%89%E7%B6%AD%E9%99%A3%E5%88%97%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%B3%95+int+cubic%5B3%5D%5B2%5D%5B3%5D+%3D+%7B+%7B1%2C2%2C3%2C4%2C5%2C6%7D%2C+%7B7%2C8%2C9%2C1%2C2%2C3%7D%2C.jpg "{4,5,6,7,8,9}}; 它包括3個平面，每個平面有2列及3行。 平面 列 行. 資料結構導論 - C語言實作.")
25
2.3.3 三維陣列的表示法 假設我們宣告了一個三維陣列C[l][m][n] 假設 l 代表第一個維度的大小。 m 代表第二個維度的大小。
陣列之個別元素所需的記憶體空間大小為z 。 資料結構導論 - C語言實作
![2.3.3 三維陣列的表示法 假設我們宣告了一個三維陣列C[l][m][n] 假設 l 代表第一個維度的大小。 m 代表第二個維度的大小。](http://slidesplayer.com/slide/15038733/91/images/25/2.3.3+%E4%B8%89%E7%B6%AD%E9%99%A3%E5%88%97%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%B3%95+%E5%81%87%E8%A8%AD%E6%88%91%E5%80%91%E5%AE%A3%E5%91%8A%E4%BA%86%E4%B8%80%E5%80%8B%E4%B8%89%E7%B6%AD%E9%99%A3%E5%88%97C%5Bl%5D%5Bm%5D%5Bn%5D+%E5%81%87%E8%A8%AD+l+%E4%BB%A3%E8%A1%A8%E7%AC%AC%E4%B8%80%E5%80%8B%E7%B6%AD%E5%BA%A6%E7%9A%84%E5%A4%A7%E5%B0%8F%E3%80%82+m+%E4%BB%A3%E8%A1%A8%E7%AC%AC%E4%BA%8C%E5%80%8B%E7%B6%AD%E5%BA%A6%E7%9A%84%E5%A4%A7%E5%B0%8F%E3%80%82.jpg "陣列之個別元素所需的記憶體空間大小為z 。 資料結構導論 - C語言實作.")
26
2.3.3 三維陣列的表示法 以列為主(Row Major)的表示法： 以行為主(Column Major)的表示法：
共計有 l 個平面，每個平面有 m 列與 n 行。 LocRM(C[i][j][k]) = α + (imn + jn + k) z 以行為主(Column Major)的表示法： 共計有 n 個平面，每個平面有 l 列與 m 行。 LocCM(C[i][j][k]) = α + (klm + jl + i) z 資料結構導論 - C語言實作
27
2.3.4 多維度陣列的表示法 假設 n 維度陣列D[s1][s2][s3]…[sn]在記憶體中的起始位置為α。
其中s1，s2，…，sn分別為D陣列的第1維、第2維，…，第n維的元素個數。 每個陣列元素所須要的記憶體儲存空間為z。 資料結構導論 - C語言實作
![2.3.4 多維度陣列的表示法 假設 n 維度陣列D[s1][s2][s3]…[sn]在記憶體中的起始位置為α。](http://slidesplayer.com/slide/15038733/91/images/27/2.3.4+%E5%A4%9A%E7%B6%AD%E5%BA%A6%E9%99%A3%E5%88%97%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%B3%95+%E5%81%87%E8%A8%AD+n+%E7%B6%AD%E5%BA%A6%E9%99%A3%E5%88%97D%5Bs1%5D%5Bs2%5D%5Bs3%5D%E2%80%A6%5Bsn%5D%E5%9C%A8%E8%A8%98%E6%86%B6%E9%AB%94%E4%B8%AD%E7%9A%84%E8%B5%B7%E5%A7%8B%E4%BD%8D%E7%BD%AE%E7%82%BA%CE%B1%E3%80%82.jpg "其中s1，s2，…，sn分別為D陣列的第1維、第2維，…，第n維的元素個數。 每個陣列元素所須要的記憶體儲存空間為z。 資料結構導論 - C語言實作.")
28
2.3.4 多維度陣列的表示法 以列為主(Row Major)的表示法：
LocRM(D[i1][i2]…[in]) = α + (i1s2s3…sn-1sn + i2s3s4…sn-1sn + i3s4s5…sn-1sn + … + in-3sn-2sn-1sn + in-2sn-1sn + in-1sn + in) z 。 資料結構導論 - C語言實作
29
2.3.4 多維度陣列的表示法 以行為主(Column Major)的表示法：
LocCM(D[i1][i2]…[in]) = α + (ins1s2…sn-2sn-1 + in-1s1s2…sn-3sn-2 + in-2s1s2…sn-4sn-3 + … + i3s1s2 + i2s1 + i1) z 。 資料結構導論 - C語言實作
30
2.3.5 對角線矩陣的表示法 對角線矩陣(Diagonal Matrix) 是一個「方陣」 。
除了對角線的元素值可能不為0外，其餘元素值均為0。 亦即，矩陣元素vi,j = 0，i ≠ j。 資料結構導論 - C語言實作
31
2.3.5 對角線矩陣的表示法 對角線矩陣(Diagonal Matrix) 對角線矩陣DM[m][m]共有m個非0元素。
我們可以直接用一個一維陣列X[m]來表示對角線矩陣。 亦即X[i]= DM[i][i]。 資料結構導論 - C語言實作
![2.3.5 對角線矩陣的表示法 對角線矩陣(Diagonal Matrix) 對角線矩陣DM[m][m]共有m個非0元素。](http://slidesplayer.com/slide/15038733/91/images/31/2.3.5+%E5%B0%8D%E8%A7%92%E7%B7%9A%E7%9F%A9%E9%99%A3%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%B3%95+%E5%B0%8D%E8%A7%92%E7%B7%9A%E7%9F%A9%E9%99%A3%28Diagonal+Matrix%29+%E5%B0%8D%E8%A7%92%E7%B7%9A%E7%9F%A9%E9%99%A3DM%5Bm%5D%5Bm%5D%E5%85%B1%E6%9C%89m%E5%80%8B%E9%9D%9E0%E5%85%83%E7%B4%A0%E3%80%82.jpg "我們可以直接用一個一維陣列X[m]來表示對角線矩陣。 亦即X[i]= DM[i][i]。 資料結構導論 - C語言實作.")
32
2.3.6 下三角矩陣的表示法 下三角矩陣(Lower Triangular Matrix) 它是一個「方陣」。
對角線以上(不含對角線)的元素值均為 0。 資料結構導論 - C語言實作
33
2.3.6 下三角矩陣的表示法 假設 採「以列為主」的儲存策略，則 下三角矩陣式的陣列X在記憶體之起始位置為α。
且每個陣列元素所需的記憶體空間為z。 採「以列為主」的儲存策略，則 LocRM(Xi,j)= + ((i(i+1))/2 + j) z 。 資料結構導論 - C語言實作
34
2.3.6 下三角矩陣的表示法 【例1】設X[n][n]為一個下三角矩陣，若要用一個一維陣列Y[m]來表示X，則m的最小值應該宣告為何？
【解答】 m = n = n(n+1)/2。 資料結構導論 - C語言實作
![2.3.6 下三角矩陣的表示法 【例1】設X[n][n]為一個下三角矩陣，若要用一個一維陣列Y[m]來表示X，則m的最小值應該宣告為何？](http://slidesplayer.com/slide/15038733/91/images/34/2.3.6+%E4%B8%8B%E4%B8%89%E8%A7%92%E7%9F%A9%E9%99%A3%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%B3%95+%E3%80%90%E4%BE%8B1%E3%80%91%E8%A8%ADX%5Bn%5D%5Bn%5D%E7%82%BA%E4%B8%80%E5%80%8B%E4%B8%8B%E4%B8%89%E8%A7%92%E7%9F%A9%E9%99%A3%EF%BC%8C%E8%8B%A5%E8%A6%81%E7%94%A8%E4%B8%80%E5%80%8B%E4%B8%80%E7%B6%AD%E9%99%A3%E5%88%97Y%5Bm%5D%E4%BE%86%E8%A1%A8%E7%A4%BAX%EF%BC%8C%E5%89%87m%E7%9A%84%E6%9C%80%E5%B0%8F%E5%80%BC%E6%87%89%E8%A9%B2%E5%AE%A3%E5%91%8A%E7%82%BA%E4%BD%95%EF%BC%9F.jpg "【解答】 m = n = n(n+1)/2。 資料結構導論 - C語言實作.")
35
2.3.7 上三角矩陣的表示法 上三角矩陣(Upper Triangular Matrix) 它是一個「方陣」。
對角線以下 (不含對角線)的元素值均為 0。 資料結構導論 - C語言實作
36
2.3.7 上三角矩陣的表示法 假設 採「以行為主」的儲存策略，則 下三角矩陣式的陣列X在記憶體之起始位置為α。
且每個陣列元素所需的記憶體空間為z。 採「以行為主」的儲存策略，則 LocCM(Xi,j)= + ((j(j+1))/2 + i) z 。 資料結構導論 - C語言實作
37
2.4 一維陣列的應用 2.4.1 計數器(Counter) 2.4.2 暫存(Temporary Store)
2.4.3 取代(Substitution) 2.4.4 索引(Indexing) 2.4.5 搜尋(Searching) 2.4.6 排序(Sorting) 資料結構導論 - C語言實作
38
2.4.1 計數器(Counter) i = i + 1; (或 i++; ) 。 int count[n]; //宣告 ...
count[i] = count[i] + 1; //計數器 + 1 或 count[i]++ ; //計數器 + 1 資料結構導論 - C語言實作
![2.4.1 計數器(Counter) i = i + 1; (或 i++; ) 。 int count[n]; //宣告 ...](http://slidesplayer.com/slide/15038733/91/images/38/2.4.1+%E8%A8%88%E6%95%B8%E5%99%A8%28Counter%29+i+%3D+i+%2B+1%3B+%28%E6%88%96+i%2B%2B%3B+%29+%E3%80%82+int+count%5Bn%5D%3B+%2F%2F%E5%AE%A3%E5%91%8A+....jpg "count[i] = count[i] + 1; //計數器 + 1. 或. count[i]++ ; //計數器 + 1. 資料結構導論 - C語言實作.")
39
2_dice_toss.c (p.2-26) #include <stdio.h>
#include <math.h> void dicetoss(int *count, int n); void main(void) { int count[6] = {0}; int i, n; clrscr(); printf("請輸入擲骰子的次數 : "); scanf("%d",&n); dicetoss(count, n); 資料結構導論 - C語言實作
40
printf("\n\n---------------------------");
printf("\n 共計投擲 %2d 次，其中",n); for(i = 0; i < 6; i++) printf("\n %d 點出現 %2d 次",i+1,count[i]); printf("\n \n"); } /********************************************/ /* 利用一個亂數產生函數(式)來模擬骰子的投擲 */ void dicetoss(int *count, int n) { int i, point; for(i = 0; i < n; i++) point = rand() % 6 ; count[point] = count[point] + 1; 資料結構導論 - C語言實作
41
2.4.2 暫存(Temporary Store) 「質數」：大於1的數，除了1與本身以外沒有任何一個數能夠整除它時，該數稱為質數。
2是最小的質數。 3、5、7均是質數。 4、6不是質數，因為4可以被2整除，6可以被2、3整除 。 資料結構導論 - C語言實作
42
2.4.2 暫存(Temporary Store) 如何找出小於等於100的所有質數呢？ 第一種方法：
根據質數的定義，判斷5是否為質數時，須將5除以2、3、4，只要能被其中一個數整除，那麼5就非質數，否則5就是質數。 依此類推，判斷x是否為質數時，須將x除以2、3、4...、x-1，只要能被其中一個數整除，那麼x就非質數，否則x就是質數。 資料結構導論 - C語言實作
43
2_prime1.c (p.2-30) #include <stdio.h> 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 的質數有...\n\n",n); 資料結構導論 - C語言實作
44
/* 質數的定義：一個正整數，除了 1 和本身以外沒有別的因數：一個正整數，除了 1 和本身以外不能被其他的數所整除 */
/* 質數的定義：一個正整數，除了 1 和本身以外沒有別的因數：一個正整數，除了 1 和本身以外不能被其他的數所整除 */ for(i = 1; i <= n; i++) { isprime = true; switch(i) { case 1 : /* 1 非質數 */ isprime = false; break; case 2 : /* 2 是最小的質數 */ default : for(j = 2; j < i; j++) { if((i % j) == 0) { /* i 可被 j 整除，非質數 */ } else; 資料結構導論 - C語言實作
45
if(count % 15 == 0) /* 每印滿15個質數就跳下一行 */ printf("\n\n"); else; }
if(isprime == true) { /* 印出質數 */ count ++; printf("%3d ",i); if(count % 15 == 0) /* 每印滿15個質數就跳下一行 */ printf("\n\n"); else; } printf("\n\n==> 不大於 %d 的質數共有 %d 個",n,count); 資料結構導論 - C語言實作
46
2.4.2 暫存(Temporary Store) 第二種方法：
將第1個找到的質數暫存於prime[0]，將第2個找到的質數暫存於prime[1]，將第3個找到的質數暫存於prime[2]，依此類推。 要判斷一個整數x是否為質數時，我們只須取出prime陣列裡已經找到的質數來當做除數，將x除以這些質數，如果都不能被這些質數整除，即可斷定x為質數。 因此，要判斷6是否為質數時，只須分別判斷6是否能被2、3、5整除即可，只要能被其中一個質數整除，6就非質數。因6能被2整除，非質數，不須再判斷能否被3、5整除了。 資料結構導論 - C語言實作
47
2_prime2.c (p.2-33) #include <stdio.h> #include <math.h>
#define N 120 int find_prime(int *prime, int n); void main(void) { int i, n, count = 0; int prime[N] = {0}; clrscr(); printf("請輸入大於 1 的整數 : "); scanf("%d",&n); printf("\n不大於 %d 的質數有...\n\n",n); /*找出不大於 n 的所有質數 */ count = find_prime(prime, n); 資料結構導論 - C語言實作
48
for(i = 0; i <= count; i++) { printf("%d ",prime[i]);
if((i+1) % 15 == 0) /* 每印滿 15 個質數就跳下一行 */ printf("\n\n"); } printf("\n\n小於等於 %d 的質數共有 %d 個",n,count+1); /* 找出 <= n 的所有質數，採用以下定義 */ /* 質數的定義：一個正整數，不能被小於本身的所有質數所整除 */ /* 被找到的質數站存在陣列prime[]之中 */ /* */ int find_prime(int *prime, int n) enum boolean isprime; enum boolean {false,true}; int i, j, count = -1; 資料結構導論 - C語言實作
![for(i = 0; i <= count; i++) { printf( %d ,prime[i]);](http://slidesplayer.com/slide/15038733/91/images/48/for%28i+%3D+0%3B+i+%3C%3D+count%3B+i%2B%2B%29+%7B+printf%28+%25d+%2Cprime%5Bi%5D%29%3B.jpg "if((i+1) % 15 == 0) /* 每印滿 15 個質數就跳下一行 */ printf( \n\n ); } printf( \n\n小於等於 %d 的質數共有 %d 個 ,n,count+1); /* 找出 <= n 的所有質數，採用以下定義 */ /* 質數的定義：一個正整數，不能被小於本身的所有質數所整除 */ /* 被找到的質數站存在陣列prime[]之中 */ /* */ int find_prime(int *prime, int n) enum boolean isprime; enum boolean {false,true}; int i, j, count = -1; 資料結構導論 - C語言實作.")
49
for(i = 2; i <= n; i++) { isprime = true; switch(i) {
case 2 : /* 2 是最小的質數 */ prime[++count] = i; break; default : for(j = 0; prime[j] != 0 && prime[j] <= sqrt(i) && isprime == true; j++) if((i % prime[j]) == 0) /* 非質數 */ isprime = false; else; } if(isprime == true) return count; 資料結構導論 - C語言實作
50
2.4.3 取代(Substitution) 要印出 則可用陣列來儲存花色和點數以取代之 資料結構導論 - C語言實作
51
2_cards.c (p.2-36) #include <stdio.h>
char cf[4] = {6, 5, 4, 3}; /* 黑桃,梅花,方塊,紅心 */ char cp[13][2] = {"A ", "2 ", "3 ", "4 ", "5 ", "6 ", "7 ", "8 ", "9 ", "10", "J ", "Q ", "K "}; void main(void) { int i, j; clrscr(); for(i = 0; i <= 3; i++) { for(j = 0; j <= 12; j++) { printf("%c%c%c ",cf[i],cp[j][0],cp[j][1]); } printf("\n"); 資料結構導論 - C語言實作
52
2.4.4 索引(Indexing) 「索引」：利用某一個陣列的元素值來當做另一個陣列的索引值。 尋找出眾數及其出現頻率
一維陣列x[15]是一個含有15個元素的整數陣列，且陣列中的元素值均介於0與5之間。我們稱陣列x中出現次數最多的數為「眾數」。 宣告一個整數陣列count[6]，然後用count[i]來記錄x陣列中 i 的出現次數。 亦即 count[x[i]] = count[x[i]]++ ; 資料結構導論 - C語言實作
53
2_freq.c (p.2-38) #include <stdio.h>
#define N /* 輸入 15 個整數 */ #define NUMBER 6 /* 輸入的整數必須介於 0 至 5 之間 */ int frequency(int *count); void main(void) { int i,n; int x[N] = {0}; int count[NUMBER] = {0}; clrscr(); printf("請輸入15個整數 i ，0 <= i <= 5 :\n"); 資料結構導論 - C語言實作
54
count[x[i]] = count[x[i]] + 1; } n = frequency(count);
for(i = 0; i < N; i++) { scanf("%d",&x[i]); count[x[i]] = count[x[i]] + 1; } n = frequency(count); printf("\n眾數為 %d ，共出現 %d 次\n",n,count[n]); 資料結構導論 - C語言實作
![count[x[i]] = count[x[i]] + 1; } n = frequency(count);](http://slidesplayer.com/slide/15038733/91/images/54/count%5Bx%5Bi%5D%5D+%3D+count%5Bx%5Bi%5D%5D+%2B+1%3B+%7D+n+%3D+frequency%28count%29%3B.jpg "for(i = 0; i < N; i++) { scanf( %d ,&x[i]); count[x[i]] = count[x[i]] + 1; } n = frequency(count); printf( \n眾數為 %d ，共出現 %d 次\n ,n,count[n]); 資料結構導論 - C語言實作.")
55
/* 尋找眾數(當同時有好幾個最大者時，以輸入值較小者為眾數) */ int frequency(int *count) { int i;
/* 尋找眾數(當同時有好幾個最大者時，以輸入值較小者為眾數) */ int frequency(int *count) { int i; int most_freq_no = count[0]; int n = 0; /* 眾數 */ printf("\ncount陣列之內容為 : "); printf("\n "); for(i = 0; i <= NUMBER-1 ; i++) { printf("\n ==> count[%d] = %d",i,count[i]); printf(" (%d 出現 %d 次)",i,count[i]); if(count[i] > most_freq_no) most_freq_no = count[i]; n = i; } return n; 資料結構導論 - C語言實作
56
2.4.5 搜尋(Searching) 搜尋(Search)：從一群資料中找出滿足特定條件的資料之動作稱之。 搜尋條件通常有：
大於、等於、小於、大於或等於、不等於、小於或等於等多種組合。 資料結構導論 - C語言實作
57
2.4.5.1 循序搜尋法(Sequential Search)
【例1】找出鍵值大於70的資料？ 必須從d[0]開始逐筆加以比對，直到比完d[7]為止(共計比較8次) 結果找到d[2]、d[4]、d[5]、d[7]等4筆資料 資料結構導論 - C語言實作
58
2.4.5.2 二元搜尋法(Binary Search) 二元搜尋法的特徵如下： 資料須事先經過排序。
每次都從可能有符合條件的一組資料中，拿第中間筆資料(假設d[i])出來跟鍵值k相比。 每次比較完之後，大約可以捨去一半的資料，所以搜尋的速度很快。 資料結構導論 - C語言實作
59
二元搜尋法(Binary Search) 【例2】二元搜尋法。 找出鍵值等於120的資料？ 資料結構導論 - C語言實作
60
二元搜尋法(Binary Search) 【例2】二元搜尋法。 找出鍵值大於70的資料？ 資料結構導論 - C語言實作
61
2_b_search.c (p.2-46) #include <stdio.h> #define Size 8
#define true 1 void 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("陣列元素 d[0] [1] [2] [3] [4] [5] [6] [7] \n"); printf(" \n"); printf("鍵 值 ==>"); for(i = 0; i < n; i++) { printf("%3d ",d[i]); } printf("\n\n"); 資料結構導論 - C語言實作
62
if(d[low_index] > key || d[high_index] < key ) /* not found */
/* 二元搜尋法 */ int binary_search(int *d, int low_index, int high_index, int key, int *index) { int i, middle, count; if(d[low_index] > key || d[high_index] < key ) /* not found */ return (-1); count=-1; while(low_index <= high_index){ middle = (low_index + high_index)/2; if(key > d[middle]) low_index = middle + 1; /* 下一回合須搜尋後半部 */ else { if(key < d[middle]) high_index = middle - 1; /* 下一回合須搜尋前半部 */ else { /* key == d[middle] */ index[++count] = middle; /* 找到了 */ /* 須再比較前後筆鍵值是否相同 */ 資料結構導論 - C語言實作
![if(d[low_index] > key || d[high_index] < key ) /* not found */](http://slidesplayer.com/slide/15038733/91/images/62/if%28d%5Blow_index%5D+%3E+key+%7C%7C+d%5Bhigh_index%5D+%3C+key+%29+%2F%2A+not+found+%2A%2F.jpg "/* 二元搜尋法 */ int binary_search(int *d, int low_index, int high_index, int key, int *index) { int i, middle, count; if(d[low_index] > key || d[high_index] < key ) /* not found */ return (-1); count=-1; while(low_index <= high_index){ middle = (low_index + high_index)/2; if(key > d[middle]) low_index = middle + 1; /* 下一回合須搜尋後半部 */ else { if(key < d[middle]) high_index = middle - 1; /* 下一回合須搜尋前半部 */ else { /* key == d[middle] */ index[++count] = middle; /* 找到了 */ /* 須再比較前後筆鍵值是否相同 */ 資料結構導論 - C語言實作.")
63
while(i >= low_index && key == d[i]) /* 比較前面幾筆是否同鍵值 */
/* 須再比較前後筆鍵值是否相同 */ i = middle - 1; while(i >= low_index && key == d[i]) /* 比較前面幾筆是否同鍵值 */ index[++count] = i--; i = middle + 1; while(i <= high_index && key == d[i]) /* 比較後面幾筆是否同鍵值 */ index[++count] = i++; return (count); } return (-1); 資料結構導論 - C語言實作
![while(i >= low_index && key == d[i]) /* 比較前面幾筆是否同鍵值 */](http://slidesplayer.com/slide/15038733/91/images/63/while%28i+%3E%3D+low_index+%26%26+key+%3D%3D+d%5Bi%5D%29+%2F%2A+%E6%AF%94%E8%BC%83%E5%89%8D%E9%9D%A2%E5%B9%BE%E7%AD%86%E6%98%AF%E5%90%A6%E5%90%8C%E9%8D%B5%E5%80%BC+%2A%2F.jpg "/* 須再比較前後筆鍵值是否相同 */ i = middle - 1; while(i >= low_index && key == d[i]) /* 比較前面幾筆是否同鍵值 */ index[++count] = i--; i = middle + 1; while(i <= high_index && key == d[i]) /* 比較後面幾筆是否同鍵值 */ index[++count] = i++; return (count); } return (-1); 資料結構導論 - C語言實作.")
64
int d[Size]={14, 33, 48, 50, 87, 93, 120, 121}; /* 已遞增排序 */ int key;
void main(void) { int d[Size]={14, 33, 48, 50, 87, 93, 120, 121}; /* 已遞增排序 */ int key; int i, count=-1; /* 共有多少筆資料滿足搜尋條件 */ int index[Size]; /* 儲存滿足條件之鍵值之索引位值 */ clrscr( ); while(true){ print_array_data(d, Size); printf("請輸入要搜尋的鍵值(結束時輸入-1) : "); scanf("%d",&key); if(key == -1) break; else; 資料結構導論 - C語言實作
![int d[Size]={14, 33, 48, 50, 87, 93, 120, 121}; /* 已遞增排序 */ int key;](http://slidesplayer.com/slide/15038733/91/images/64/int+d%5BSize%5D%3D%7B14%2C+33%2C+48%2C+50%2C+87%2C+93%2C+120%2C+121%7D%3B+%2F%2A+%E5%B7%B2%E9%81%9E%E5%A2%9E%E6%8E%92%E5%BA%8F+%2A%2F+int+key%3B.jpg "void main(void) { int d[Size]={14, 33, 48, 50, 87, 93, 120, 121}; /* 已遞增排序 */ int key; int i, count=-1; /* 共有多少筆資料滿足搜尋條件 */ int index[Size]; /* 儲存滿足條件之鍵值之索引位值 */ clrscr( ); while(true){ print_array_data(d, Size); printf( 請輸入要搜尋的鍵值(結束時輸入-1) : ); scanf( %d ,&key); if(key == -1) break; else; 資料結構導論 - C語言實作.")
65
count = binary_search(d, 0, Size-1, key, index); if(count > -1){
for(i = 0; i <= count; i++) printf("\n在 d[%d] 找到了鍵值 %d！",index[i],key); printf(" ==>共找到 %d 筆！\n\n",count+1); } else printf("\n==>找不到鍵值 %d ！\n\n",key); 資料結構導論 - C語言實作
66
2.4.6 排序(Sorting) 排序(SORT)：乃將原始資料依照某個特定的次序加以重新排列。 排序時須指定： 用哪一個資料項來排序？
被用來排序的資料項又稱為「鍵(Key)」 排序的順序 遞增：即由小到大。 遞減：即由大到小。 資料結構導論 - C語言實作
67
氣泡浮昇排序法(Bubble Sort) 假設我們已經宣告了一個整數陣列d[n]，用來存放編號為0、1、2、...、n-1的n筆資料。且 d[0] = v0、 d[1] = v1、 d[2] = v2、... d[n-2] = vn-2、 d[n-1] = vn-1。 資料結構導論 - C語言實作
![氣泡浮昇排序法(Bubble Sort) 假設我們已經宣告了一個整數陣列d[n]，用來存放編號為0、1、2、...、n-1的n筆資料。且. d[0] = v0、 d[1] = v1、](http://slidesplayer.com/slide/15038733/91/images/67/%E6%B0%A3%E6%B3%A1%E6%B5%AE%E6%98%87%E6%8E%92%E5%BA%8F%E6%B3%95%28Bubble+Sort%29+%E5%81%87%E8%A8%AD%E6%88%91%E5%80%91%E5%B7%B2%E7%B6%93%E5%AE%A3%E5%91%8A%E4%BA%86%E4%B8%80%E5%80%8B%E6%95%B4%E6%95%B8%E9%99%A3%E5%88%97d%5Bn%5D%EF%BC%8C%E7%94%A8%E4%BE%86%E5%AD%98%E6%94%BE%E7%B7%A8%E8%99%9F%E7%82%BA0%E3%80%811%E3%80%812%E3%80%81...%E3%80%81n-1%E7%9A%84n%E7%AD%86%E8%B3%87%E6%96%99%E3%80%82%E4%B8%94.+d%5B0%5D+%3D+v0%E3%80%81+d%5B1%5D+%3D+v1%E3%80%81.jpg "d[2] = v2、... d[n-2] = vn-2、 d[n-1] = vn-1。 資料結構導論 - C語言實作.")
68
2.4.6.1 氣泡浮昇排序法(Bubble Sort) 採用氣泡浮昇排序法的將一組資料依「鍵值遞增」排序之步驟說明如下： 第1回合：
從第0筆資料開始一直到第n-1筆資料，持續比較相鄰兩筆資料之大小，若vi大於vi+1，則須將兩者交換位置，亦即須將vi 儲存到d[i+1]，vi+1 儲存到d[i]。換言之，必須保持小的在前，大的在後之順序。 在第1回合處理完後，陣列中最大的數值已經被存放到d[n-1]的位置。 資料結構導論 - C語言實作
69
2.4.6.1 氣泡浮昇排序法(Bubble Sort) 第2回合：
從第0筆資料開始一直到第n-2筆資料，持續比較相鄰兩筆資料之大小，若vi大於vi+1，則須將兩者交換位置，亦即須將vi 儲存到d[i+1]，vi+1 儲存到d[i]。 在第2回合處理完後，陣列中第2大數的值已經被存放到d[n-2]的位置。 重複執行上述步驟，共計(n-1)回合，即可將陣列資料排列成由小到大的遞增順序。 資料結構導論 - C語言實作
70
氣泡浮昇排序法(Bubble Sort) 【例2】氣泡浮昇排序法。 資料結構導論 - C語言實作
71
氣泡浮昇排序法(Bubble Sort) 【例2】氣泡浮昇排序法。 資料結構導論 - C語言實作
72
2_b_sort.c (p.2-55) #include <stdio.h> #define Size 9
void print_org_data(const int d[], int 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("陣列元素 d[0] [1] [2] [3] [4] [5] [6] [7] [8]\n"); printf(" \n"); printf("<排序前> ==> "); 資料結構導論 - C語言實作
73
printf("\n-------------------------------------------------\n");
for(i = 0; i < n; i++) { printf("%2d ",d[i]); } printf("\n \n"); /* 印出陣列 d 的內容(陣列 d 共有 n 個元素) */ void print_array_data(const int d[], int n) int i; printf("\n"); 資料結構導論 - C語言實作
74
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; i < n-1; i++){ for(j = 0; j < n-1; j++){ if(d[j] > d[j+1]) swap(&d[j], &d[j+1]); printf(" 第%d回合 ==> ",i+1); print_array_data(d, n); 資料結構導論 - C語言實作
75
print_org_data(d, Size); /* 列印排序前之鍵值資料 */ /* 將陣列 d 裡的 Size 個鍵值遞增排序 */
void main(void) { int d[Size]={83,66,55,21,88,18,33,47,3}; print_org_data(d, Size); /* 列印排序前之鍵值資料 */ /* 將陣列 d 裡的 Size 個鍵值遞增排序 */ bubble_sort_ascending(d, Size); } 資料結構導論 - C語言實作
76
2.5 二維陣列的應用 2.5.1 轉置矩陣(Transpose Matrix) 2.5.2 對稱矩陣(Symmetric Matrix)
2.5.3 反射矩陣(Reflection Matrix) 2.5.4 矩陣相加(Matrix Addition) 2.5.5 矩陣相減(Matrix Subtraction) 2.5.6 矩陣乘積(Matrix Multiplication) 2.5.7 稀疏矩陣(Sparse Matrix) 資料結構導論 - C語言實作
77
2.5.1 轉置矩陣(Transpose Matrix)
設M是一個mn矩陣，而TM為其轉置矩陣，則： TM為一個nm矩陣。 M的第0列元素成為TM的第0行元素， M的第1列元素成為TM的第1行元素，…， M的第m-1列元素成為TM的第m-1行元素。 亦即 TM[j][i] = M[i][j]。 資料結構導論 - C語言實作
78
2.5.1 轉置矩陣(Transpose Matrix)
【例1】轉置矩陣。 資料結構導論 - C語言實作
79
2_t_matrix.c (p.2-60) #include <stdio.h> void main(void) {
int M[10][10] = {0}, TM[10][10] = {0}; int i, j, m, n; /* 輸入矩陣 M 之元素值，並產生轉置矩陣 TM */ clrscr(); printf("請輸入二維矩陣 M[m][n] 之大小，即 m n 之值 : "); scanf("%d %d",&m,&n); printf("\n請按【列】之順序輸入矩陣 M 的元素值:\n"); for(i = 0; i < m; i++){ for(j = 0; j < n; j++){ scanf("%d",&M[i][j]); /* 輸入矩陣 M 的元素值 */ TM[j][i] = M[i][j]; /* TM 為矩陣 M 的轉置矩陣 */ } 資料結構導論 - C語言實作
80
printf("\n矩陣 M[%d][%d] 的元素資料如下 : \n",m,n); for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) { printf(" %3d",M[i][j]); } printf("\n"); /* 列印出轉置矩陣 TM */ printf("\n\n轉置矩陣 TM[%d][%d] 的元素資料如下 : \n",n,m); for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { printf(" %3d",TM[i][j]); 資料結構導論 - C語言實作
![printf( \n矩陣 M[%d][%d] 的元素資料如下 : \n ,m,n); for(i = 0; i < m; i++) {](http://slidesplayer.com/slide/15038733/91/images/80/printf%28+%5Cn%E7%9F%A9%E9%99%A3+M%5B%25d%5D%5B%25d%5D+%E7%9A%84%E5%85%83%E7%B4%A0%E8%B3%87%E6%96%99%E5%A6%82%E4%B8%8B+%3A+%5Cn+%2Cm%2Cn%29%3B+for%28i+%3D+0%3B+i+%3C+m%3B+i%2B%2B%29+%7B.jpg "for(j = 0; j < n; j++) { printf( %3d ,M[i][j]); } printf( \n ); /* 列印出轉置矩陣 TM */ printf( \n\n轉置矩陣 TM[%d][%d] 的元素資料如下 : \n ,n,m); for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { printf( %3d ,TM[i][j]); 資料結構導論 - C語言實作.")
81
2.5.2 對稱矩陣(Symmetric Matrix)
對稱矩陣為一方陣，且元素值vij = vji。 資料結構導論 - C語言實作
82
2.5.3 反射矩陣(Reflection Matrix)
反射矩陣(RMmxn)是將原始矩陣(Mmxn)進行水平方向的鏡射。 資料結構導論 - C語言實作
83
2.5.4 矩陣相加(Matrix Addition)
cij=aij+bij。 【例1】矩陣相加。 資料結構導論 - C語言實作
84
2.5.5 矩陣相減(Matrix Subtraction)
cij=aij-bij。 【例1】矩陣相減。 資料結構導論 - C語言實作
85
2.5.6 矩陣乘積(Matrix Multiplication)
86
2.5.6 矩陣乘積(Matrix Multiplication)
【例1】矩陣乘積。 資料結構導論 - C語言實作
87
2_m_matrix.c (p.2-71) #include <stdio.h> void main(void) {
int a[10][10] = {0}, b[10][10] = {0}, c[10][10] ={0}; int i, j, k, m, n, n1, p; /* 輸入矩陣 a 之元素值 */ clrscr(); printf("請輸入二維矩陣 a[m][n] 之大小，即 m n 之值 : "); scanf("%d%d",&m,&n); printf("\n請按【列】之順序輸入矩陣 a 的元素值:\n"); for(i = 0; i < m; i++) { for(j = 0; j < n; j++) { scanf("%d",&a[i][j]); /* 輸入矩陣 a 的元素值 */ } printf("\n"); 資料結構導論 - C語言實作
88
while(1) { /* while(true) */
/* 輸入矩陣 b 之元素值 */ while(1) { /* while(true) */ printf("\n請輸入二維矩陣 b[n][p] 之大小，即 n 與 p 之值 : "); scanf("%d%d",&n1,&p); if(n != n1) printf("==> a 矩陣之行數必須等於 b 矩陣之列數，請重新輸入！\n"); else break; } printf("\n請按【列】之順序輸入矩陣 b 的元素值:\n"); for(i = 0; i < n; i++) { for(j = 0; j < p; j++) { scanf("%d",&b[i][j]); /* 輸入矩陣 b 的元素值 */ /* c[n][p] = a[m][n] * b[n][p] */ for(i = 0; i < m; i++) for(j = 0; j < p; j++) for(k = 0; k < n; k++) c[i][j] = c[i][j] + a[i][k] * b[k][j]; 資料結構導論 - C語言實作
89
/*------------------*/ /* 列印出矩陣 c */ printf("\n");
printf("a x b 之結果如下:\n"); for(i = 0; i < m; i++) { for(j = 0; j < p; j++) printf("%3d ",c[i][j]); } 資料結構導論 - C語言實作
90
2.5.7 稀疏矩陣(Sparse Matrix) 一個矩陣中，若大多數的元素值均為0，則稱該矩陣為「稀疏矩陣」。
這裡所謂的元素值為0在應用上包括幾種涵義： 真的為0。 為虛值(Null Value) ，亦即沒有資料值 資料結構導論 - C語言實作
91
2.5.7 稀疏矩陣(Sparse Matrix) 【例1】稀疏矩陣的表示法。 資料結構導論 - C語言實作
92
2.5.7 稀疏矩陣(Sparse Matrix) 【例2】試設計一個用以表示三維稀疏矩陣的表示法。
【解答】設三維稀疏矩陣SMmxnxo各維之大小 分別為m、n、o，且稀疏矩陣中非0元素 共計p個。 資料結構導論 - C語言實作
Similar presentations
