第10講-復(fù)合數(shù)據(jù)結(jié)構(gòu)——數(shù)組與結(jié)構(gòu)

1、第十講：復(fù)合數(shù)據(jù)結(jié)構(gòu)數(shù)組與結(jié)構(gòu)北京大學(xué) 信息科學(xué)技術(shù)學(xué)院2013年12月#include int main()int a, b;int e;scanf(%d, &a);scanf(%d, &b);if(a b)e = a;a = b;b = e; printf(%d %dn, a, b); return 0;#include int main()int a, b, c;int e;scanf(%d, &a);scanf(%d, &b);scanf(%d, &c);if(a b)e = a;a = b;b = e;if(b c)e = b;b = c;c = e;if(a b)e = a;a =

2、 b;b = e;printf(%d %d %dn, a, b, c); return 0;如果要求：1. 接收用戶輸入的10個數(shù)字2. 輸出的10個數(shù)字按照 從小到大 的順序排列難道需要這樣定義10個變量嗎？int a, b, c, d, e, f, g, h, i, j;有沒有一種 更簡便的方式，可以一次定義一組變量？內(nèi)容題要 復(fù)合數(shù)據(jù)結(jié)構(gòu) 數(shù)組 結(jié)構(gòu)數(shù)組數(shù)組 是 什么？數(shù)組 是 一組變量數(shù)組 是 一組 具有編號 的 變量如何聲明 一個數(shù)組int sz10; 數(shù)組的類型數(shù)組名數(shù)組中變量的數(shù)目必須是一個常量數(shù)組 中 變量 的 編號int sz10; 數(shù)組中變量的編號 從 0 開始； 到 數(shù)組

3、的長度1 結(jié)束0 1 2 3 4 5 6 7 8 9如何訪問 數(shù)組 中 的 變量int sz10;sz0 = 1;sz1 = 3;sz2 = 7;sz8 = 16;sz9 = 12; sz2; 數(shù)組名變量編號數(shù)組變量賦值 的 一種特殊方式 聲明時(shí)賦值int sz5 =12, 3, 7, 28, -2; #include int main()int sz10;int i;for( ; ; ) ;for(i = 0; i 10; i+)printf(%d , szi);return 0;程序填空；要求：1.接收用戶輸入的10個數(shù)字2.存放在數(shù)組sz中#include int main()int s

4、z10;int i;for( i=0 ; i 10 ; i+)scanf(%d, &(szi);for(i = 0; i 10; i+)printf(%d , szi);return 0;數(shù)組 的 遍歷通過 循環(huán)結(jié)構(gòu)正向 遍歷int szLEN; for(int i = 0; i = 0; i-) szi 通過遍歷 實(shí)現(xiàn) 對 數(shù)組變量 的 控制臺賦值int szLEN; for(int i = 0; i LEN; i+)scanf(“%d”, &(szi);通過遍歷 實(shí)現(xiàn) 對 數(shù)組變量 的 控制臺輸出int szLEN; for(int i = 0; i LEN; i+)printf(“%dn

5、”, szi);數(shù)組 的 應(yīng)用示例當(dāng)程序要處理一組類型相同、含義類似的數(shù)據(jù)時(shí)，應(yīng)該使用數(shù)組游戲：過年抽獎 一個村莊，有128個村民 村長對村民說： 今年村里出現(xiàn)了財(cái)政盈余M元； M是20003000之間的一個整數(shù) 準(zhǔn)備通過抽獎的方式把錢發(fā)給村民 游戲規(guī)則如下： 每個村民上報(bào)一個在20003000元之間的整數(shù) 如果有人上報(bào)的數(shù)字和M相等，就把錢發(fā)給這些人 如果只有一個村民猜對，就把M元錢全部發(fā)給他 如果有多個人村民猜對，就把M元錢平均分配給這些村民村長邀請我們編寫一個程序， 實(shí)現(xiàn)村里財(cái)政盈余的自動分配編程的基本思路 定義一個數(shù)組 存放所有村民上報(bào)的數(shù)據(jù) 定義一個數(shù)組 存放獲獎?wù)叩木幪枺ㄐ疫\(yùn)者數(shù)組

6、） 定義一個整數(shù) 存放獲獎?wù)呷藬?shù) 對村民從0開始編號（最后一個編號是127） 村民按照編號順序上報(bào)數(shù)字；程序?qū)⒋迕裆蠄?bào)的數(shù)字存放在對應(yīng)編號的數(shù)組變量中。 遍歷村民上報(bào)的數(shù)字，若上報(bào)數(shù)字與幸運(yùn)數(shù)相等，則 將村民編號添加到幸運(yùn)者數(shù)組中； 并將獲獎?wù)呷藬?shù)加1 最后，打印出獲獎?wù)呔幪柡瞳@得的獎金數(shù)額#define LUCKY_M 2345#define LUCKY_M 2345 /財(cái)政盈余財(cái)政盈余#define POPULATION 128 #define POPULATION 128 /村民數(shù)量村民數(shù)量int main( )int main( ) int peoplePOPULATION; int

7、peoplePOPULATION; /記錄所有村民上報(bào)數(shù)字的數(shù)組記錄所有村民上報(bào)數(shù)字的數(shù)組 int luckyPeoplePOPULATION;int luckyPeoplePOPULATION; /幸運(yùn)者數(shù)組，記錄獲獎?wù)呔幪栃疫\(yùn)者數(shù)組，記錄獲獎?wù)呔幪?int nLucky=0; int nLucky=0; /獲獎?wù)呷藬?shù)獲獎?wù)呷藬?shù) int i; int i; /循環(huán)變量循環(huán)變量 for (i=0; iPOPULATION; i+) for (i=0; iPOPULATION; i+) scanf(“%d”, scanf(“%d”, &(peoplei)&(peoplei); ); /讀入村民報(bào)

8、的數(shù)字，數(shù)組下標(biāo)就是村民的編號讀入村民報(bào)的數(shù)字，數(shù)組下標(biāo)就是村民的編號 for (i=0; iPOPULATION; i+) for (i=0; iPOPULATION; i+) if ( peoplei = LUCKY_M ) if ( peoplei = LUCKY_M ) luckyPeoplenLucky = i; luckyPeoplenLucky = i; nLucky +; nLucky +; /輸出獲獎?wù)呔幪柤八@獎金數(shù)額輸出獲獎?wù)呔幪柤八@獎金數(shù)額 for (i=0; inLucky; i+) for (i=0; inLucky; i+) printf(%d %dn, luc

9、kyPeoplei, LUCKY_M / nLucky); printf(%d %dn, luckyPeoplei, LUCKY_M / nLucky); return 0; return 0; 回顧排序：冒泡排序回顧排序：冒泡排序int i, k, e, szLEN;for(i = 0; i LEN; i+)scanf(“%d”, &(szi);for(k = 1 ; k = LEN ; k+)for(i = 0; i szi+1)e = szi+1;szi+1 = szi;szi = e;#define LEN 10結(jié)構(gòu) 結(jié)構(gòu)的結(jié)構(gòu)的概念概念 通常，一個學(xué)生的個人信息，包括：學(xué)號、姓名、性

10、別、年齡、各門功課的成績等數(shù)據(jù)，這些數(shù)據(jù)都與一個學(xué)生相關(guān)聯(lián)，類型各不相同。如果將這些數(shù)據(jù)定義為各獨(dú)立的簡單變量：n Number、Name、Sex、Age、Course1、Course2、 這樣就難以反映它們之間的內(nèi)在聯(lián)系。應(yīng)該把它們組織成一個組合項(xiàng)，把它們當(dāng)作一個有機(jī)的整體。這個組合項(xiàng)就是結(jié)構(gòu)（結(jié)構(gòu)（Structure）25結(jié)構(gòu)類型及其定義 把多個緊密關(guān)聯(lián)的變量（分量分量）順序組織在一起，定義成一個新的復(fù)合數(shù)據(jù)類型結(jié)構(gòu)類型結(jié)構(gòu)類型 定義一個結(jié)構(gòu)類型定義一個結(jié)構(gòu)類型struct 結(jié)構(gòu)類型名結(jié)構(gòu)類型名 類型類型1 分量名分量名1; 類型類型2 分量名分量名2; .; 結(jié)構(gòu)分量的類型可以相同，也可

11、不同 同一個結(jié)構(gòu)內(nèi)的分量名不可相同26struct point float x; float y;結(jié)構(gòu)類型變量的定義 結(jié)構(gòu)類型只是定義了一種新的數(shù)據(jù)類型一種新的數(shù)據(jù)類型 系統(tǒng)并不為這個新類型分配內(nèi)存空間。 可以使用新的結(jié)構(gòu)類型來聲明變量結(jié)構(gòu)類型變量。 結(jié)構(gòu)類型變量結(jié)構(gòu)類型變量定義的兩種形式： 用已定義的結(jié)構(gòu)定義變量，例如：struct point point1;struct point point2; 定義結(jié)構(gòu)的同時(shí)定義結(jié)構(gòu)類型的變量，例如：struct city float x, y; int population; city1, city2; 系統(tǒng)會為結(jié)構(gòu)類型變量分配內(nèi)存空間系統(tǒng)會為結(jié)構(gòu)類

12、型變量分配內(nèi)存空間27結(jié)構(gòu)類型變量中分量的訪問 結(jié)構(gòu)類型變量的值由其各個分量構(gòu)成 對分量的訪問一般通過“變量名變量名.分量名分量名”完成 結(jié)構(gòu)賦值及訪問的例子：float dx, dy;struct point float x, y; p1, p2, points2;p1.x = p1.y = 3.5f;p2.x = p2.y = 1.5f;dx = p1.x - p2.x;dy = p1.y - p2.y;28結(jié)構(gòu)變量本身可以作為一個整體來使用結(jié)構(gòu)變量本身可以作為一個整體來使用points0 = p1; points1 = p2;29結(jié)構(gòu)類型中的分量 結(jié)構(gòu)類型中分量的類型可以是任何類型 基本

13、數(shù)據(jù)類型的分量struct point float x, y; 其他類型的分量：結(jié)構(gòu)類型、數(shù)組類型 分量的類型不能是未定義的結(jié)構(gòu)類型 分量的類型不能是正在定義的結(jié)構(gòu)類型struct city char name32; struct city city1;x;struct city struct point float x, y; location; int population; char name32;city1;struct city struct point location; int population; char name32;city1; (city1.location).x30

14、結(jié)構(gòu)變量的內(nèi)存布局 結(jié)構(gòu)中各分量在內(nèi)存中順序存放struct square struct point int x, y; p1, p2; sq1;sq1.p1.x = 10;sq1.p1.y = 20;sq1.p2.x = 100;sq1.p2.y = 200;主存儲器sq1.p1.x1020100200*sq1.p1.ysq1.p2.xsq1.p2.y結(jié)構(gòu)變量所占內(nèi)存的大小 結(jié)構(gòu)變量所占內(nèi)存的大小并不完全等于于各分量所占字節(jié)數(shù)的總和struct char_frequency char c; int frequency;sizeof(strcut char_frequency)通常為通常為8，

15、而非，而非5這是編譯器在編譯時(shí)的一個特殊要求。這是編譯器在編譯時(shí)的一個特殊要求。31結(jié)構(gòu)應(yīng)用示例（1）救援 洪水淹沒了很多房子，只有屋頂還是安全的。被困的人們都爬上了屋頂?，F(xiàn)在救生船每次都從大本營出發(fā)，到各屋頂救人，救了人之后將人送回大本營。 救生船每次從大本營出發(fā)，以速度50米/分鐘時(shí)向下一個屋頂，達(dá)到一個屋頂后，救下其上的所有人，每人上船1分鐘，船原路返回，達(dá)到大本營，每人下船0.5分鐘。 假設(shè)大本營與任意一個屋頂?shù)倪B線不穿過其它屋頂。 輸入：第一行是屋頂數(shù)n，其后n行，每行是每個屋頂?shù)淖鴺?biāo)和人數(shù) 輸出：第一行是所有人都到達(dá)大本營并登陸所用的時(shí)間，其后n行，每行是每個屋頂?shù)淖鴺?biāo)和人數(shù)323

16、3NiiiipspeedyxtotalTime122)5 . 01 (2(圖中原點(diǎn)是大本營，每個點(diǎn)代表屋頂，每個屋頂由其位置坐標(biāo)和其上的人數(shù)表示。34#include #include #include #define MAX_ROOF_NUM 1000#define SPEED 50.0#define UP 1.0#define DOWN 0.5int main() int roof_num; / 屋頂數(shù)屋頂數(shù). scanf(%d, &roof_num); / 輸入屋頂數(shù)輸入屋頂數(shù). struct roof float x, y; / 屋頂坐標(biāo)屋頂坐標(biāo). int p; / 屋頂上的人數(shù)屋頂上

17、的人數(shù). rfsMAX_ROOF_NUM; double totalTime = 0; / 救援總時(shí)間救援總時(shí)間. int i; / 循環(huán)控制變量循環(huán)控制變量. /用循環(huán)處理每一個屋頂，輸入屋頂位置及人數(shù)數(shù)用循環(huán)處理每一個屋頂，輸入屋頂位置及人數(shù)數(shù). for (i=0; iroof_num; i+)35 /用循環(huán)處理每一個屋頂，輸入屋頂位置及人數(shù)用循環(huán)處理每一個屋頂，輸入屋頂位置及人數(shù). for (i=0; iroof_num; i+ scanf(%f%f%d,&(rfsi.x), &(rfsi.y), &(rfsi.p); / 用循環(huán)處理每一個屋頂，計(jì)算救援時(shí)間用循環(huán)處理每一個屋頂，計(jì)算救援

18、時(shí)間 . for (i=0; iroof_num; i+) / 首先計(jì)算從大本營到屋頂?shù)碾p程航行時(shí)間，并累加到總救援時(shí)間中首先計(jì)算從大本營到屋頂?shù)碾p程航行時(shí)間，并累加到總救援時(shí)間中 . totalTime += 2 * sqrt(rfsi.x*rfsi.x + rfsi.y*rfsi.y) / SPEED; / 然后計(jì)算被求人員上船和下船所耗費(fèi)的總時(shí)間，并累加到總救援時(shí)間中然后計(jì)算被求人員上船和下船所耗費(fèi)的總時(shí)間，并累加到總救援時(shí)間中 . totalTime += rfsi.p * (UP + DOWN); / 打印出救援總時(shí)間打印出救援總時(shí)間. printf(Total Time is: %

19、.2lfn, totalTime); / 依次打印出各屋頂?shù)奈恢眉叭藬?shù)依次打印出各屋頂?shù)奈恢眉叭藬?shù). for (i=0; iroof_num; i+) printf(Roof ID: %d %.2f %.2f %dn, i+1, rfsi.x, rfsi.y, rfsi.p); return 0;36結(jié)構(gòu)應(yīng)用示例（2）學(xué)生成績統(tǒng)計(jì)n定義一個結(jié)構(gòu)，包含學(xué)生的所有信息。struct student int number; char name8; char sex; int age; float course8; ;struct student class1160;37單個變量、數(shù)組和結(jié)構(gòu) 數(shù)組和結(jié)

20、構(gòu)：多個變量的集合多個變量的集合 數(shù)組 通過數(shù)組可定義大量類型相同類型相同的變量 數(shù)組元素通過“變量變量下標(biāo)下標(biāo)”形式訪問 靜態(tài)數(shù)組的大小（數(shù)組元素的個數(shù)）是預(yù)先確定的，即數(shù)組定義中數(shù)組個數(shù)必須是整數(shù)常量 結(jié)構(gòu) 結(jié)構(gòu)把一組密切相關(guān)的變量（類型可以不同）密切相關(guān)的變量（類型可以不同）組織成一個整體 結(jié)構(gòu)的分量通過變量變量. 分量分量形式訪問單個變量、數(shù)組和結(jié)構(gòu)38n更加復(fù)雜的數(shù)據(jù)定義更加復(fù)雜的數(shù)據(jù)定義n結(jié)構(gòu)中的數(shù)組結(jié)構(gòu)中的數(shù)組n結(jié)構(gòu)中的結(jié)構(gòu)結(jié)構(gòu)中的結(jié)構(gòu)n結(jié)構(gòu)數(shù)組結(jié)構(gòu)數(shù)組復(fù)雜結(jié)構(gòu)示例：教師、學(xué)生、班級struct teacher_s / 教師結(jié)構(gòu)教師結(jié)構(gòu) char name32; / 姓名姓名 c

21、har title16; / 職稱職稱 int age; / 年齡年齡;struct student_s / 學(xué)生結(jié)構(gòu)學(xué)生結(jié)構(gòu) char name32; / 姓名姓名 char sex; / 性別性別 int age; / 年齡年齡;struct class_s / 班級結(jié)構(gòu)班級結(jié)構(gòu) struct teacher_s teacher; / 教師教師 struct student_s students180; / 所有學(xué)生所有學(xué)生 int student_num; / 學(xué)生人數(shù)學(xué)生人數(shù);習(xí)題習(xí)題1.接收從控制臺輸出的兩個整數(shù) （假設(shè)是兩個正整數(shù)）2.輸出這兩個數(shù)的最大公約數(shù)#include in

22、t main() int a, b, t; scanf(%d%d, &a, &b); / a和和b的最大共數(shù)也是的最大共數(shù)也是b和和a%b的最大公約數(shù)的最大公約數(shù) t = a % b; while (t != 0) a = b; b = t; t = a % b; printf(%dn, b); return 0;1.接收從控制臺輸出的一組整數(shù) （假設(shè)輸入n n個整數(shù)，n n = 100 = 100）2.按輸入相反的順序輸出這組整數(shù)#include #define MAX 100int main() int aMAX, i, j, n, t; scanf(%d, &n); for (i = 0

23、; i n; i+) scanf(%d, &ai); for (i = 0, j = n-1; i j; i+, j-) t = ai; ai = aj; aj = t; for (i = 0; i n; i+) printf(%dn, ai); return 0;#include #define MAX 100int main() int aMAX, i, j, n, t; scanf(%d, &n); for (i = 0; i n; i+) scanf(%d, &ai); for (i = 0, j = n-1; i j; i+, j-) t = ai; ai = aj; aj = t; for (i = 0; i n; i+) printf(%dn, ai); return 0;1.接收從控制臺輸出的一組整數(shù) （假設(shè)輸入n n個整數(shù)，n n = 100 = 100）2.將數(shù)組中后m m個數(shù)移動到數(shù)組頭部3.要求不能使用輔助數(shù)組#include #define MAX 100int main() int aMAX, i, j, m, n, t; scanf(%d%d, &n, &m); for (i = 0; i n; i+) scanf(%d, &ai); for (j = 0; j 0; i-) ai = ai-1; a0 = t; for (i = 0; i n;