第10講-復合數(shù)據(jù)結構——數(shù)組與結構

1、第十講：復合數(shù)據(jù)結構數(shù)組與結構北京大學 信息科學技術學院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;有沒有一種 更簡便的方式，可以一次定義一組變量？內容題要 復合數(shù)據(jù)結構 數(shù)組 結構數(shù)組數(shù)組 是 什么？數(shù)組 是 一組變量數(shù)組 是 一組 具有編號 的 變量如何聲明 一個數(shù)組int sz10; 數(shù)組的類型數(shù)組名數(shù)組中變量的數(shù)目必須是一個常量數(shù)組 中 變量 的 編號int sz10; 數(shù)組中變量的編號 從 0 開始； 到 數(shù)組

3、的長度1 結束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ù)組變量賦值 的 一種特殊方式 聲明時賦值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)結構正向 遍歷int szLEN; for(int i = 0; i = 0; i-) szi 通過遍歷 實現(xiàn) 對 數(shù)組變量 的 控制臺賦值int szLEN; for(int i = 0; i LEN; i+)scanf(“%d”, &(szi);通過遍歷 實現(xiàn) 對 數(shù)組變量 的 控制臺輸出int szLEN; for(int i = 0; i LEN; i+)printf(“%dn

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

6、） 定義一個整數(shù) 存放獲獎者人數(shù) 對村民從0開始編號（最后一個編號是127） 村民按照編號順序上報數(shù)字；程序將村民上報的數(shù)字存放在對應編號的數(shù)組變量中。 遍歷村民上報的數(shù)字，若上報數(shù)字與幸運數(shù)相等，則 將村民編號添加到幸運者數(shù)組中； 并將獲獎者人數(shù)加1 最后，打印出獲獎者編號和獲得的獎金數(shù)額#define LUCKY_M 2345#define LUCKY_M 2345 /財政盈余財政盈余#define POPULATION 128 #define POPULATION 128 /村民數(shù)量村民數(shù)量int main( )int main( ) int peoplePOPULATION; int

7、peoplePOPULATION; /記錄所有村民上報數(shù)字的數(shù)組記錄所有村民上報數(shù)字的數(shù)組 int luckyPeoplePOPULATION;int luckyPeoplePOPULATION; /幸運者數(shù)組，記錄獲獎者編號幸運者數(shù)組，記錄獲獎者編號 int nLucky=0; int nLucky=0; /獲獎者人數(shù)獲獎者人數(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); ); /讀入村民報

8、的數(shù)字，數(shù)組下標就是村民的編號讀入村民報的數(shù)字，數(shù)組下標就是村民的編號 for (i=0; iPOPULATION; i+) for (i=0; iPOPULATION; i+) if ( peoplei = LUCKY_M ) if ( peoplei = LUCKY_M ) luckyPeoplenLucky = i; luckyPeoplenLucky = i; nLucky +; nLucky +; /輸出獲獎者編號及所獲獎金數(shù)額輸出獲獎者編號及所獲獎金數(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結構 結構的結構的概念概念 通常，一個學生的個人信息，包括：學號、姓名、性

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

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

12、型變量分配內存空間27結構類型變量中分量的訪問 結構類型變量的值由其各個分量構成 對分量的訪問一般通過“變量名變量名.分量名分量名”完成 結構賦值及訪問的例子：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結構變量本身可以作為一個整體來使用結構變量本身可以作為一個整體來使用points0 = p1; points1 = p2;29結構類型中的分量 結構類型中分量的類型可以是任何類型 基本

13、數(shù)據(jù)類型的分量struct point float x, y; 其他類型的分量：結構類型、數(shù)組類型 分量的類型不能是未定義的結構類型 分量的類型不能是正在定義的結構類型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、結構變量的內存布局 結構中各分量在內存中順序存放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é)數(shù)的總和struct char_frequency char c; int frequency;sizeof(strcut char_frequency)通常為通常為8，

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

16、3NiiiipspeedyxtotalTime122)5 . 01 (2(圖中原點是大本營，每個點代表屋頂，每個屋頂由其位置坐標和其上的人數(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; / 屋頂坐標屋頂坐標. int p; / 屋頂上的人數(shù)屋頂上

17、的人數(shù). rfsMAX_ROOF_NUM; double totalTime = 0; / 救援總時間救援總時間. 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)處理每一個屋頂，計算救援時間用循環(huán)處理每一個屋頂，計算救援

18、時間 . for (i=0; iroof_num; i+) / 首先計算從大本營到屋頂?shù)碾p程航行時間，并累加到總救援時間中首先計算從大本營到屋頂?shù)碾p程航行時間，并累加到總救援時間中 . totalTime += 2 * sqrt(rfsi.x*rfsi.x + rfsi.y*rfsi.y) / SPEED; / 然后計算被求人員上船和下船所耗費的總時間，并累加到總救援時間中然后計算被求人員上船和下船所耗費的總時間，并累加到總救援時間中 . totalTime += rfsi.p * (UP + DOWN); / 打印出救援總時間打印出救援總時間. 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結構應用示例（2）學生成績統(tǒng)計n定義一個結構，包含學生的所有信息。struct student int number; char name8; char sex; int age; float course8; ;struct student class1160;37單個變量、數(shù)組和結構 數(shù)組和結

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

21、har title16; / 職稱職稱 int age; / 年齡年齡;struct student_s / 學生結構學生結構 char name32; / 姓名姓名 char sex; / 性別性別 int age; / 年齡年齡;struct class_s / 班級結構班級結構 struct teacher_s teacher; / 教師教師 struct student_s students180; / 所有學生所有學生 int student_num; / 學生人數(shù)學生人數(shù);習題習題1.接收從控制臺輸出的兩個整數(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ù) （假設輸入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ù) （假設輸入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;