1、第4章 數(shù)據(jù)的組織結(jié)構(gòu)（一）,4.3 字符串的組織,4.2 利用一維數(shù)組組織數(shù)據(jù)的應(yīng)用實(shí)例,4.1 數(shù)組類(lèi)型,4.4 常用的字符串標(biāo)準(zhǔn)函數(shù)及應(yīng)用實(shí)例,4.5 二維數(shù)組,課前復(fù)習(xí),前三章 數(shù)據(jù)類(lèi)型 - 數(shù)據(jù)結(jié)構(gòu)的一種方式 學(xué)習(xí)新的數(shù)據(jù)的組織形式-數(shù)據(jù)結(jié)構(gòu)的另一種方式,4.1 數(shù)組類(lèi)型,數(shù)組類(lèi)型的應(yīng)用背景 （1）同時(shí)存在若干個(gè)用來(lái)描述同一性質(zhì)且不同個(gè)體的數(shù)據(jù)。 （2）只有將這些數(shù)據(jù)組織在一起形成批量數(shù)據(jù)，共同參與處理，很多操作才具有實(shí)際意義。 例如：在某個(gè)部門(mén)中，需要由全體職工推選一名辦公室主任。假設(shè)有10名候選人準(zhǔn)備參與競(jìng)選。希望編寫(xiě)一個(gè)程序，統(tǒng)計(jì)每個(gè)候選人的得票數(shù)量及選舉結(jié)果。,一維數(shù)組類(lèi)型的

2、定義 定義格式： ； 例如： int vote10; C語(yǔ)言規(guī)定：數(shù)組的下標(biāo)從0開(kāi)始，因此，表示這10個(gè)數(shù)據(jù)的下標(biāo)為09 變量一經(jīng)定義，系統(tǒng)就要為它分配相應(yīng)的存儲(chǔ)空間。在C程序中，系統(tǒng)將會(huì)為每個(gè)數(shù)組型變量分配一片連續(xù)的存儲(chǔ)空間，所需要分配的存儲(chǔ)空間總數(shù)將取決于包含的元素個(gè)數(shù)和每個(gè)元素需要的存儲(chǔ)空間。,一維數(shù)組的初始化 基本格式為： =，.，； 例如：float score5 = 9.2, 9.1, 8.7, 9.1, 8.5;,說(shuō)明： 1）為數(shù)組型變量中的每一個(gè)元素都提供了一個(gè)初始值。此時(shí)，可以省略方括號(hào)內(nèi)的數(shù)組元素?cái)?shù)量。系統(tǒng)將根據(jù)花括號(hào)中包含的初值數(shù)目推測(cè)出數(shù)組含有的元素?cái)?shù)量。 float

3、score = 9.2, 9.1, 8.7, 9.1, 8.5; 2）對(duì)數(shù)組型變量的前面若干個(gè)元素賦予初值。此時(shí)可以使用下面這種書(shū)寫(xiě)形式： int letter26 = 10, 9, 8, 7; 它的執(zhí)行結(jié)果是：將10、9、8、7分別賦予letter數(shù)組中下標(biāo)為0、1、2、3的元素，后面的所有元素賦予初值0。 3）將數(shù)組型變量中的每一個(gè)元素賦予初值0。此時(shí)，可以使用下面這種簡(jiǎn)化的書(shū)寫(xiě)形式： int vote10 = 0;,一維數(shù)組元素的引用及基本操作 數(shù)組元素的引用 數(shù)組的賦值 利用賦值語(yǔ)句為數(shù)組賦值 for (i=0; i10; i+) votei = 0; 調(diào)用標(biāo)準(zhǔn)輸入函數(shù)為數(shù)組賦值 fo

4、r (i=0; i13; i+) scanf(“%f”, ,按照條件對(duì)數(shù)據(jù)進(jìn)行篩選 在遇到的許多問(wèn)題中，經(jīng)常需要從眾多的數(shù)據(jù)中挑選出來(lái)滿(mǎn)足一定條件的數(shù)據(jù)，這就是數(shù)據(jù)的篩選操作。在C程序中，參與篩選操作的批量數(shù)據(jù)可以采用一個(gè)一維數(shù)組型變量組織，篩選的條件用邏輯表達(dá)式表示。,4.2 利用一維數(shù)組組織數(shù)據(jù)的應(yīng)用實(shí)例,例1：在某個(gè)公司中，計(jì)劃由職工們推選一名辦公室主任。假設(shè)有10名候選人準(zhǔn)備參與競(jìng)選。希望編寫(xiě)一個(gè)程序，輸入一組選舉人的投票信息，統(tǒng)計(jì)每個(gè)候選人的得票數(shù)目及選舉結(jié)果。,問(wèn)題分析 用一維數(shù)組記錄每位候選人的得票數(shù)量。 投票通過(guò)循環(huán)輸入介于110之間的整型數(shù)值來(lái)模擬的。例如，輸入3代表某個(gè)職工

5、選舉編碼為3的候選人。 找出最多的得票數(shù)量之后，從所有的候選人中篩選出得票數(shù)量與最高得票數(shù)量相同的人。,算法描述,#include #define NUM 10 /* 候選人人數(shù) */ main( ) int voteNUM = 0; int code, i, winner; /* 職工投票 */ printf(nEnter your selection:n); do scanf(%d, ,程序代碼,/* 輸出選票 */ printf(n The amount of votes is :); for (i=0; ivotewinner) winner = i; /* 輸出得票最高的所有候選人

6、*/ printf(nThe winner :); for (i=winner; iNUM; i+) if (votei=votewinner) printf(%3d,i+1); ,根據(jù)需求對(duì)數(shù)據(jù)進(jìn)行統(tǒng)計(jì) 為了滿(mǎn)足特定的需要，對(duì)一組數(shù)據(jù)的某些特征進(jìn)行統(tǒng)計(jì)是一項(xiàng)經(jīng)常遇到的基本操作。例如，統(tǒng)計(jì)一段文本中某個(gè)字符出現(xiàn)的頻率；統(tǒng)計(jì)學(xué)生考試的平均成績(jī)等等都屬于統(tǒng)計(jì)操作。統(tǒng)計(jì)操作的結(jié)果往往是通過(guò)對(duì)所有數(shù)據(jù)進(jìn)行掃描、判斷或綜合加工得到的。在C程序中，參與統(tǒng)計(jì)操作的批量數(shù)據(jù)可以用一維數(shù)組來(lái)組織，具體統(tǒng)計(jì)過(guò)程可以通過(guò)邏輯判斷、累計(jì)、算術(shù)運(yùn)算等基本操作手段實(shí)現(xiàn)。,例2：在一段文本中，可能會(huì)出現(xiàn)各式各樣的字符。編寫(xiě)

7、一個(gè)程序，從鍵盤(pán)讀入一行文本，完成統(tǒng)計(jì)每個(gè)英文字母出現(xiàn)頻率的操作。,問(wèn)題分析 用一維數(shù)組構(gòu)造26個(gè)用于記錄每個(gè)字母出現(xiàn)次數(shù)的累加器。 對(duì)于輸入的文本字符，可以在讀取時(shí)檢查一下是否為英文字母，而不需要將其存儲(chǔ)起來(lái)。,算法描述,#include #define NUM 26 main( ) int letterNUM = 0; char ch; int i; printf(nEnter text linen); while (ch=getchar() != n) if (A=ch ,程序代碼,例3：每年中央電視臺(tái)都要舉辦青年歌手大獎(jiǎng)賽。假設(shè)有13位評(píng)委參與評(píng)分工作。計(jì)算每位歌手最終得分的方法是：首

8、先去掉一個(gè)最高分和一個(gè)最低分，然后計(jì)算剩余11個(gè)分?jǐn)?shù)的平均值，所得結(jié)果就是選手的最終得分。希望編寫(xiě)一個(gè)程序，幫助工作人員計(jì)算每個(gè)歌手的分?jǐn)?shù)。,問(wèn)題分析 用一維數(shù)組存儲(chǔ) 13位評(píng)委給出的分?jǐn)?shù) 尋找最高分和最低分 計(jì)算剩余11個(gè)分?jǐn)?shù)的平均分,算法描述,#include #define NUM 13 main( ) float scoreNUM; */ int i, minValue, maxValue; float sum; /* 輸入13位評(píng)委給出的分?jǐn)?shù) */ printf(nEnter 13 score:); for (i=0; iNUM; i+) scanf(%f, ,程序代碼,/* 找出最

9、高分、最低分，并同時(shí)累加13個(gè)分?jǐn)?shù)的總和 */ minValue = score0; maxValue = score0; sum = score0; for (i=1; imaxValue) maxValue = scorei; sum = sum+scorei; /* 計(jì)算并輸出歌手的最終得分 */ sum = (sum- minValue-maxValue)/(NUM-2); printf(nFinal score is %6.2f, sum); ,查找問(wèn)題 所謂查找是指根據(jù)某個(gè)給定的條件，在一組數(shù)據(jù)中搜索是否存在滿(mǎn)足該條件的數(shù)據(jù)的過(guò)程。如果存在，則表示查找成功，給出成功的標(biāo)志；否則表示

10、查找不成功，給出失敗的標(biāo)志。在程序中，查找操作的結(jié)果經(jīng)常被用來(lái)作為是否執(zhí)行某項(xiàng)后續(xù)操作的決策依據(jù)。,例4：已知某個(gè)班級(jí)35名學(xué)生的某門(mén)課程的考試成績(jī)。請(qǐng)編寫(xiě)一個(gè)程序，查看在這個(gè)班級(jí)中是否存在不及格的學(xué)生。,問(wèn)題分析 用一維數(shù)組記錄每位學(xué)生的考試成績(jī)，下標(biāo)表示每個(gè)學(xué)生的編號(hào)，元素內(nèi)容表示考試成績(jī)。 查找可以通過(guò)從前往后依次查看每個(gè)元素內(nèi)容的過(guò)程實(shí)現(xiàn)。,算法描述,#include #include #define NUM 35 /*學(xué)生人數(shù)*/ main( ) int scoreNUM; int i; /* 隨機(jī)產(chǎn)生35個(gè)考試成績(jī) */ randomize( ); for (i=0; iNUM;

11、i+) scorei = random(100); /*顯示35名學(xué)生的考試成績(jī)*/ for (i=0; iNUM; i+) printf(nNo.%d: %d, i+1, scorei); ,程序代碼,/*順序查找是否存在不及格的學(xué)生*/ for (i=0; iNUM; i+) if (scorei60) break; /*輸出查找結(jié)果*/ if (iNUM) printf(nNot all pass.); else printf(All pass.); ,例5：已知一個(gè)按非遞減有序排列的整型數(shù)列（12,23,30,45,48,50,67,82,91,103）。請(qǐng)編寫(xiě)一個(gè)程序，查找其中是否存

12、在與給定key相等的數(shù)值。,問(wèn)題分析 二分查找是指每次用key與位于查找區(qū)間中央位置的元素進(jìn)行比較，比較結(jié)果將會(huì)產(chǎn)生下面三種情形之一： 如果相等，說(shuō)明查找成功。 如果key小于中央位置的元素，說(shuō)明如果存在這樣的元素，應(yīng)該位于查找區(qū)間的前半部分。此時(shí)可以將查找區(qū)間縮減為原來(lái)的一半，并在這一半的區(qū)間中繼續(xù)用相同的方式查找。 如果key大于中央位置的元素，說(shuō)明如果存在這樣的元素，應(yīng)該位于查找區(qū)間的后半部分。同樣可以將查找區(qū)間縮減為原來(lái)的一半，并在這一半的區(qū)間中繼續(xù)用相同的方式查找。 可以看出，用key與當(dāng)前查找區(qū)間中央位置的元素比較后，不是找到了，就是將查找區(qū)間縮小了一半。直到查找區(qū)間不存在了，說(shuō)明

13、沒(méi)有要找的key。,算法描述,#include #define NUM 10 main( ) int valueNUM = 12, 23, 30, 45, 48, 50, 67, 82, 91, 103; /* 非遞減整型數(shù)列 */ int low, high, mid, key; printf(nEnter a key:); /* 輸入查找的數(shù)值 */ scanf(%d, /* 確認(rèn)循環(huán)正常出口 */ ,程序代碼,排序問(wèn)題 將一組無(wú)序的數(shù)列重新排列成非遞減或非遞增的順序是一種經(jīng)常需要的操作。例如，在管理學(xué)生成績(jī)的應(yīng)用程序中，可以用一個(gè)數(shù)列表示一個(gè)班級(jí)的學(xué)生成績(jī)，并按照從高到低的順序重新排列，

14、以便確定獲得獎(jiǎng)學(xué)金的學(xué)生。,例6：假設(shè)用戶(hù)通過(guò)鍵盤(pán)輸入一個(gè)整型數(shù)列。請(qǐng)編寫(xiě)一個(gè)程序，將其按照從小到大的順序重新排列。,問(wèn)題分析 首先從n個(gè)數(shù)據(jù)中選擇一個(gè)最小的數(shù)據(jù)，并將它交換到第1個(gè)位置；然后再?gòu)暮竺鎛-1個(gè)數(shù)據(jù)中選擇一個(gè)最小的數(shù)據(jù)，并將它交換到第2個(gè)位置；以此類(lèi)推，直至最后從兩個(gè)數(shù)據(jù)中選擇一個(gè)最小的數(shù)據(jù)，并將它交換到第n-1個(gè)位置為止，整個(gè)排序操作結(jié)束。,算法描述,#include #define NUM 10 /* 參與排序的數(shù)據(jù)個(gè)數(shù) */ main() int dataNUM; /* 存放參與排序的所有整數(shù) */ int i, j, minValue, temp; /* 通過(guò)鍵盤(pán)輸入待排序的整型數(shù)列 */ printf(nEnter %d integers., NUM); for (i=0; iNUM; i+) scanf(%d, ,程序代碼,for (i=0; iNUM-1; i+) minValue = i; for (j=i+1; jNUM; j+) if (datajdata