1、1,1,構(gòu)造數(shù)據(jù)類型,第六章,例題：求10個(gè)數(shù)的平均數(shù),5,5,主要內(nèi)容,數(shù)組概述 一維數(shù)組 二維數(shù)組 字符數(shù)組 結(jié)構(gòu)體類型,6,6,float、int、 char等都是簡單類型。 簡單類型變量的特點(diǎn)是一個(gè)變量描述一個(gè)數(shù)據(jù)。 構(gòu)造數(shù)據(jù)類型變量描述的是一組數(shù)據(jù)。 一個(gè)構(gòu)造類型變量包含若干個(gè)簡單數(shù)據(jù)類型或若干個(gè)構(gòu)造類型的數(shù)據(jù)。,1、數(shù)組概述,7,7,數(shù)組是一種構(gòu)造數(shù)據(jù)類型。 數(shù)組由若干個(gè)同類型的數(shù)據(jù)元素連續(xù)排列而成。 一個(gè)數(shù)組類型的變量值, 按數(shù)組元素的順序存放在內(nèi)存中一片連續(xù)的內(nèi)存單元中。 每個(gè)數(shù)組元素占據(jù)一個(gè)獨(dú)立的空間。,8,8,按數(shù)組元素的類型不同，數(shù)組又可分為： 數(shù)值數(shù)組 字符數(shù)組 指針數(shù)

2、組 結(jié)構(gòu)數(shù)組等,1、數(shù)組概述,9,9,數(shù)組在內(nèi)存中的存放,例：A5（A為有5個(gè)元素的數(shù)組變量）,第1個(gè)數(shù)組元素,第5個(gè)數(shù)組元素,數(shù)組名表示內(nèi)存首地址， 是地址常量,下標(biāo)從0開始,編譯時(shí)分配連續(xù)內(nèi)存,10,10,對(duì)數(shù)組的操作：,定義數(shù)組變量; 引用數(shù)組中的元素; 對(duì)數(shù)組進(jìn)行初始化-為數(shù)組元素賦初值; 數(shù)組型變量的輸入和輸出;,11,11,格式： 基本類型 數(shù)組名數(shù)組元素的個(gè)數(shù);,1、定義數(shù)組類型的變量：,每一個(gè)數(shù)組元素的類型,數(shù)組變量名,12,12,定義數(shù)組變量時(shí)考慮的因素：,數(shù)組元素的類型;（基本類型） 數(shù)組變量名稱; 數(shù)組的維數(shù); 每一維數(shù)組元素的個(gè)數(shù);,13,13,定義數(shù)組變量時(shí)考慮的因素

3、：,例： int a10; char ch20; float b56;,一維數(shù)組,二維數(shù)組,14,14,對(duì)數(shù)組的操作：,定義數(shù)組變量; 引用數(shù)組中的元素; 對(duì)數(shù)組進(jìn)行初始化-為數(shù)組元素賦初值; 數(shù)組型變量的輸入和輸出;,15,15,2、引用數(shù)組中的元素,格式：數(shù)組名下標(biāo)1下標(biāo)2下標(biāo)n; 考慮因素： 引用哪一個(gè)數(shù)組數(shù)組名; 數(shù)組元素在數(shù)組中的位置數(shù)組下標(biāo);,16,16,2、引用數(shù)組中的元素,例： int a10; char ch20; float b56;,a3,chi,b23,定義,引用,17,17,主要內(nèi)容,數(shù)組概述 一維數(shù)組 二維數(shù)組 字符數(shù)組 結(jié)構(gòu)體類型,18,18,一、定義一維數(shù)組變量

4、 二、引用一維數(shù)組變量的元素 三、初始化一維數(shù)組變量 四、對(duì)數(shù)組進(jìn)行輸入和輸出 五、應(yīng)用舉例,2、一維數(shù)組,定義,例：,格式： 類型說明符 數(shù)組名常量表達(dá)式;,int a5;,char c20;,float x10;,定義一個(gè)數(shù)組元素為整型的, 包含五個(gè)數(shù)組元素的一維數(shù)組,定義一個(gè)數(shù)組元素為字符型的, 包含20個(gè)數(shù)組元素的一維數(shù)組,定義一個(gè)數(shù)組元素為浮點(diǎn)型的, 包含10個(gè)數(shù)組元素的一維數(shù)組,決定數(shù)組元素的類型,用戶為數(shù)組起的名字,決定數(shù)組元素個(gè)數(shù),20,20,例：,int a10;,char c20;,float x9;,定義一個(gè)數(shù)組元素為實(shí)型的, 包含9 個(gè)數(shù)組元素的一維數(shù)組,定義一個(gè)數(shù)組元

5、素為字符型的, 包含 20 個(gè)數(shù)組元素的一維數(shù)組,定義一個(gè)數(shù)組元素為整型的, 包含10 個(gè)數(shù)組元素的一維數(shù)組,21,說明：,1.數(shù)組名定名規(guī)則和變量名相同，遵循標(biāo)識(shí)符定名規(guī)則。 2.在定義數(shù)組時(shí)，需要指定數(shù)組中元素的個(gè)數(shù)，方括弧中的常量表達(dá)式用來表示元素的個(gè)數(shù)，即數(shù)組長度。 3.常量表達(dá)式中可以包括常量和符號(hào)常量，但不能包含變量。也就是說，C語言不允許對(duì)數(shù)組的大小作動(dòng)態(tài)定義，即數(shù)組的大小不依賴于程序運(yùn)行過程中變量的值。,22,22,二、引用一維數(shù)組變量的數(shù)組元素,原則： 數(shù)組型變量必須先定義, 后使用。 只能逐個(gè)引用數(shù)組元素, 不能直接引用整個(gè)數(shù)組型變量。 數(shù)組下標(biāo)從 0 開始。,a0,a1,

6、a2,例如, 定義數(shù)組a: int a3, 數(shù)組元素為：,23,23,二、引用一維數(shù)組變量的數(shù)組元素,原則： 數(shù)組型變量必須先定義, 后使用。 只能逐個(gè)引用數(shù)組元素, 不能直接引用整個(gè)數(shù)組型變量。 數(shù)組下標(biāo)從 0 開始。,a0,a1,a2,例如, 定義數(shù)組a: int a3, 數(shù)組元素為：,對(duì)數(shù)組變量的處理只能一個(gè)數(shù)組元素一個(gè)數(shù)組元素地處理,24,24,二、引用形式：,例如：,數(shù)組名下標(biāo),a2 = 1;,i = 1;j = 2; k = 3; ai+j = bk;,a2,25,注意： 定義數(shù)組時(shí)用到的“數(shù)組名常量表達(dá)式” 和引用數(shù)組元素時(shí)用到的“數(shù)組名下標(biāo)” 是有區(qū)別的。 例如 int a10

7、; t=a6;,26,26,使用數(shù)組編程:,步驟：,定義數(shù)組; 對(duì)數(shù)組進(jìn)行初始化; 引用數(shù)組, 對(duì)數(shù)組進(jìn)行相應(yīng)的操作; 對(duì)結(jié)果數(shù)組進(jìn)行輸出;,例. 使用數(shù)組編程, 計(jì)算出前10項(xiàng) fibonacci 數(shù)列, 要求一行打印5個(gè)數(shù)。,怎么做？,27,27,例： 計(jì)算出 fibonacci 數(shù)列前 10 項(xiàng) , 要求一行打印5個(gè)數(shù)。,目標(biāo)1：使用數(shù)組存放這10個(gè)數(shù);,目標(biāo)2：輸出時(shí), 一行打印5個(gè)數(shù),定義整型數(shù)組f：int f10,輸出fi, i：09 輸出5個(gè)數(shù)換一次行。,28,28,f1 ：第二項(xiàng), 為1;,f0 ：第一項(xiàng), 為0;,f0 = 1;,f1 = 1;,從第三項(xiàng)開始, 每一項(xiàng)為： 它

8、的前兩項(xiàng)之和, 即： fi = fi-1+ fi-2;（i：29）,計(jì)算 fibonacci 中的項(xiàng)：,int f10;,f0 = 1; f1 = 1;,f,for(i = 2;i10;i+) fi = fi-1+fi-2;,for(i = 0;i10;i+) if ( i %5 = = 0 ) printf(n); printf(%4d, fi); ,1 1 2 3 5 8 13 21 34 55,8,13,21,34,55,5,3,執(zhí)行過程：,1,1,30,31,32,32,一、定義一維數(shù)組變量 二、引用一維數(shù)組變量的元素 三、初始化一維數(shù)組變量 四、對(duì)數(shù)組進(jìn)行輸入和輸出 五、應(yīng)用舉例,2

9、、一維數(shù)組,33,33,三、初始化一維數(shù)組變量,順序指定全部元素的初始值: 格式：int a5 = 1, 2, 3, 4, 5; 結(jié)果： a0=1, a1=2, a2=3, a3=4, a4= 5,在定義數(shù)組的同時(shí), 為數(shù)組元素指定值。 有4種方式：,34,34,指定部分元素的初始值: 格式：int a5 = 1, 0, 1; 結(jié)果： 數(shù)組a的前面三個(gè)元素賦了指定的初始值, 其他元素自動(dòng)被賦為 0 值; a0 = 1, a1 = 0, a2 = 1, a3 = 0, a4 = 0。,35,35,指定部分元素的初始值: 格式：int a5 = 1, 0, 1; 結(jié)果： 數(shù)組a的前面三個(gè)元素賦了指

10、定的初始值, 其他元素自動(dòng)被賦為 0 值; a0 = 1, a1 = 0, a2 = 1, a3 = 0, a4 = 0。,希望對(duì)數(shù)組中的第三個(gè)元素賦值為 5 , 初始化語句怎樣寫？,int a5= 0, 0, 5 ,36,36,初始化時(shí)不指定數(shù)組元素的個(gè)數(shù): int b = 1, 2, 3; 結(jié)果： b數(shù)組中只包含3個(gè)元素 每個(gè)數(shù)組元素的值為： b0 = 1, b1 = 2, b2 = 3。 隱含定義數(shù)組的元素個(gè)數(shù);,37,37,數(shù)組的靜態(tài)存儲(chǔ): static int a5; 結(jié)果： 在編譯時(shí), 在靜態(tài)存儲(chǔ)區(qū)中數(shù)組a被分配給5個(gè)數(shù)組元素的空間, 并被自動(dòng)初始化為全零。 各個(gè)數(shù)組元素的值： a

11、0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0,38,38,一、定義一維數(shù)組變量 二、引用一維數(shù)組變量的元素 三、初始化一維數(shù)組變量 四、對(duì)數(shù)組進(jìn)行輸入和輸出 五、應(yīng)用舉例,2、一維數(shù)組,39,39,四、對(duì)數(shù)組進(jìn)行輸入和輸出,C 語言規(guī)定, 對(duì)數(shù)組的使用只能逐個(gè)引用數(shù)組元素, 不能一次引用整個(gè)數(shù)組變量。 同樣, 對(duì)數(shù)組的輸入和輸出也是依次對(duì)每個(gè)元素進(jìn)行的。 即：printf和scanf語句的操作對(duì)象是每個(gè)數(shù)組元素。,例： 輸入10 個(gè)數(shù)到數(shù)組a中, 然后將它們輸出。,怎么做？,40,41,42,42,一、定義一維數(shù)組變量 二、引用一維數(shù)組變量的元素 三、初始化一維數(shù)

12、組變量 四、對(duì)數(shù)組進(jìn)行輸入和輸出 五、應(yīng)用舉例,2、一維數(shù)組,43,43,五、應(yīng)用舉例,1、排序 1、冒泡法排序 2、選擇法排序 2、查找 1、順序查找 2、折半查找,44,44,用數(shù)組編程時(shí)，可以這樣思考：,在存儲(chǔ)器中有一片連續(xù)的內(nèi)存區(qū)，名稱為a。,將需要處理的一組數(shù)據(jù)，依次放入這片連續(xù)內(nèi)存區(qū)的每一個(gè)單元中。對(duì)應(yīng)的名稱分別為：,a0,a1,a2,a3, ,an-2,an-1,a0,a1,a2,a3,a-2,a-1,根據(jù)問題的需要，對(duì)這組數(shù)據(jù)中的每一個(gè)數(shù)據(jù)元素進(jìn)行相應(yīng)的處理，處理時(shí)的訪問方式為：a i ，即：數(shù)組a中下標(biāo)為i的位置處的數(shù)組元素。,45,45,1. 有一個(gè)一維數(shù)組, 有 10 個(gè)

13、整數(shù)存放其中, 找出其中最大的一個(gè)數(shù)。,數(shù)組a,max,=,a0;,for( i=1;imax ) max=ai;,定義,main() int i, max, x10;,printf(enter data:n); for(i = 0;i10;i+) scanf(%d, ,max = x0; for(i = 1;imax) max = xi;,輸入,處理,輸出,printf(max = %dn, max); ,47,47,2. 用冒泡法對(duì) 10 個(gè)整數(shù)按從小到大的順序排列。,什么是冒泡法排序？ 排序的過程 核心程序段 完整程序,怎么做？,48,48,冒泡法排序的思想,假設(shè)有 n 個(gè)數(shù), 將相鄰的

14、兩個(gè)數(shù)依次進(jìn)行比較, 使小的在前, 大的在后, 那么第一輪比較 n-1 次就把最大的數(shù)排到了最后。 第二輪比較 n-2 次, 就把次大的數(shù)排到了倒數(shù)第二, 依此類推, 直到第 n-1 輪比較1 次, 將最小的數(shù)排到了第一, 算法結(jié)束。 算法的整體思路是讓大的數(shù)不斷地往下沉, 小的數(shù)不斷地往上冒, 所以叫冒泡排序法。,int a5,13 21 90 32 -1,13 21 32 90 -1,第一輪的結(jié)果： 將最大的數(shù)移到了最后一個(gè)位置（n-1）。,13 21 32 -1 90,a0 a1 a2 a3 a4,第一輪 21 13 90 32 -1,13 21 90 32 -1,int a5,13 2

15、1 32 -1 90,a0 a1 a2 a3 a4,13 21 32 -1 90,13 21 -1 32 90,第二輪 13 21 32 -1 90,第二輪的結(jié)果： 將第二大的數(shù)移到了 n-2 的位置。,int a5,a0 a1 a2 a3 a4,13 21 -1 32 90,第三輪 13 21 -1 32 90,13 -1 21 32 90,第三輪的結(jié)果： 將第三大的數(shù)移到了 n-3 的位置。,int a5,a0 a1 a2 a3 a4,第四輪 13 -1 21 32 90,-1 13 21 32 90,-1 13 21 32 90,結(jié)果：,最后一輪的結(jié)果： 將最小的數(shù)移到了第 0 的位置。

16、,排序程序段：,54,55,55,五、應(yīng)用舉例,1、排序 1、冒泡法排序 2、選擇法排序 2、查找 1、順序查找 2、折半查找,引例：從一組數(shù)中，找出其中最大的一個(gè)數(shù)。,引例：從一組數(shù)中，找出其中最大的一個(gè)數(shù)。,引例：從一組數(shù)中，找出其中最大的一個(gè)數(shù)。,59,59,3. 選擇法排序,要求：將n個(gè)數(shù)按照從大到小的順序排列。 前提：n個(gè)數(shù)放入一個(gè)一維數(shù)組中。 選擇法排序的思想： 第一次, 從n個(gè)數(shù)中, 找出一個(gè)最大的, 放到第一個(gè)數(shù)組元素的位置處。 第二次, 從剩下的n-1個(gè)數(shù)中, 找出一個(gè)最大的, 放到第二個(gè)數(shù)組元素的位置處。 以此類推, 第n-1次, 從剩下的兩個(gè)數(shù)中, 找出一個(gè)最大的放到第n

17、-1個(gè)數(shù)組元素的位置處。,61,62,62,寫一選擇法排序算法（小大） 寫一冒泡法排序算法（大?。?思考題：,63,63,五、應(yīng)用舉例,1、排序 1、冒泡法排序 2、選擇法排序 2、查找 1、順序查找 2、折半查找,64,64,關(guān)于查找：,首先，待查找的數(shù)據(jù)放在一個(gè)一維數(shù)組中； 問題：到這樣一個(gè)一維數(shù)組中去尋找一個(gè)滿足某種特征的數(shù)組元素，如果找到，返回一個(gè)整數(shù)值，標(biāo)志這個(gè)數(shù)在數(shù)組中的位序；如果找不到，返回整數(shù)0。 查找的方法：計(jì)算機(jī)中有許多的查找方法，在這里，我們只介紹兩個(gè)方法：順序查找和折半查找。,65,65,1、順序查找,順序查找方法適用于無序存放的一組數(shù)據(jù)。 查找從一維數(shù)組的最后一個(gè)數(shù)組

18、元素開始比較，直到找到指定的數(shù)組元素或已到達(dá)數(shù)組的頭部依然沒找到。,66,66,1、順序查找,說明： 如果待查找的數(shù)據(jù)有n個(gè)，那么，我們定義一個(gè)擁有n+1個(gè)數(shù)組元素的一維數(shù)組； 其中，下標(biāo)為0的數(shù)組元素留作他用，待查找的數(shù)據(jù)從下標(biāo)為1的位置開始存放。 查找時(shí)，首先將指定的數(shù)據(jù)放入下標(biāo)為0的位置，然后開始查找。,67,67,順序查找過程：,順序查找時(shí)的內(nèi)存狀態(tài)：,0號(hào)單元空置,數(shù)據(jù)元素從1號(hào)單元開始存放,68,68,順序查找過程：,ST,假設(shè)給定值 key = 64， 要求,n,k,k,64,k,k,K=7,STk = key,， 問: k = ?,69,69,順序查找過程：,ST,假設(shè)給定值 e = 60， 要求 STk = e， 問: k = ?,n,k,k,60,k,k,K=0,k,關(guān)鍵代碼：,71,71,查找的結(jié)果：,如果在查找表中存在要查找的元素，則返回該元素所在的位置的下標(biāo)； 如果在查找表中不存在要查找的元素，則返回整數(shù) 0； 程序描述如下：,73,73,2、折半查找,若數(shù)組中的數(shù)據(jù)已經(jīng)按照從小到大的順序排好序，則查找過程可以基于折半進(jìn)行。 折半查找又稱為二分查找。,74,74,折半查找基本思想,先與“中間位置”的數(shù)組元素值比較，若相等則查找成功，否則： 將給定值與中間位置的數(shù)組元素值比較，如果： 給定值中間位置的數(shù)組元素值, 則在后半部繼續(xù)進(jìn)行折半查找