C語言高級編程結(jié)構(gòu)與習(xí)題課課件

1、第十八講 C語言高級編程 結(jié)構(gòu)與習(xí)題課北京大學(xué)信息學(xué)院第1頁，共32頁。2 結(jié)構(gòu)的概念 通常，一個學(xué)生的個人信息，包括：學(xué)號、姓名、性別、年齡、各門功課的成績等數(shù)據(jù)，這些數(shù)據(jù)都與一個學(xué)生相關(guān)聯(lián)，類型各不相同。如果將這些數(shù)據(jù)定義為各獨立的簡單變量： Number、Name、Sex、Age、Course1、Course2、這樣就難以反映它們之間的內(nèi)在聯(lián)系。應(yīng)該把它們組織成一個組合項，把它們當(dāng)作一個有機的整體。這個組合項就是結(jié)構(gòu)（Structure）第2頁，共32頁。3結(jié)構(gòu)類型及其定義把多個緊密關(guān)聯(lián)的變量（分量）順序組織在一起，定義成一個新的復(fù)合數(shù)據(jù)類型結(jié)構(gòu)類型定義一個結(jié)構(gòu)類型struct 結(jié)構(gòu)類型

2、名 類型1 分量名1; 類型2 分量名2; .;結(jié)構(gòu)分量的類型可以相同，也可不同同一個結(jié)構(gòu)內(nèi)的分量名不可相同struct point float x; float y;第3頁，共32頁。4結(jié)構(gòu)類型變量的定義結(jié)構(gòu)類型只是定義了一種新的數(shù)據(jù)類型系統(tǒng)并不為這個新類型分配內(nèi)存空間?？梢允褂眯碌慕Y(jié)構(gòu)類型來聲明變量結(jié)構(gòu)類型變量。結(jié)構(gòu)類型變量定義的兩種形式：用已定義的結(jié)構(gòu)定義變量，例如：struct point point1;struct point point2;定義結(jié)構(gòu)的同時定義結(jié)構(gòu)類型的變量，例如：struct city float x, y; int population; city1, city2

3、;系統(tǒng)會為結(jié)構(gòu)類型變量分配內(nèi)存空間第4頁，共32頁。5結(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;結(jié)構(gòu)變量本身可以作為一個整體來使用points0 = p1; points1 = p2;第5頁，共32頁。6結(jié)構(gòu)類型中的分量結(jié)構(gòu)類型中分量的類型可以是任何類型基本數(shù)據(jù)類型的分

4、量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).x第6頁，共32頁。7結(jié)

5、構(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第7頁，共32頁。8結(jié)構(gòu)變量所占內(nèi)存的大小結(jié)構(gòu)變量所占內(nèi)存的大小并不完全等于于各分量所占字節(jié)數(shù)的總和struct char_frequency char c; int frequency;sizeof(strcut char_frequency)通

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

7、大本營，每個點代表屋頂，每個屋頂由其位置坐標(biāo)和其上的人數(shù)表示。第10頁，共32頁。11程序示例：succor.cpp第11頁，共32頁。12結(jié)構(gòu)應(yīng)用示例（2）學(xué)生成績統(tǒng)計定義一個結(jié)構(gòu)，包含學(xué)生的所有信息。struct student int number; char name8; char sex; int age; float course8; ;struct student class1160;第12頁，共32頁。13單個變量、數(shù)組和結(jié)構(gòu)數(shù)組和結(jié)構(gòu)：多個變量的集合數(shù)組通過數(shù)組可定義大量類型相同的變量數(shù)組元素通過“變量下標(biāo)”形式訪問靜態(tài)數(shù)組的大?。〝?shù)組元素的個數(shù)）是預(yù)先確定的，即數(shù)組定義中數(shù)

8、組個數(shù)必須是整數(shù)常量結(jié)構(gòu)結(jié)構(gòu)把一組密切相關(guān)的變量（類型可以不同）組織成一個整體結(jié)構(gòu)的分量通過變量. 分量形式訪問第13頁，共32頁。int a;char str100;scanf(“%d”, &a);gets(str);字符串與數(shù)值從控制臺輸入字符串：scanf()：不能帶空格gets()：可以有空格在一個程序中，盡量只使用一種輸入函數(shù)。當(dāng)既要輸入有空格的字符串，又要輸入數(shù)值時，應(yīng)避免使用以下方式：14那該怎么辦呢？第14頁，共32頁。字符串與數(shù)值在輸入數(shù)值時也使用gets()，得到表示數(shù)值的字符串，再將該字符串轉(zhuǎn)換成數(shù)值。int atoi(char *str)：將字符串轉(zhuǎn)換成整數(shù)double

9、 atof(char *str)：將字符串轉(zhuǎn)換成浮點數(shù)15#include 第15頁，共32頁。字符串與數(shù)值16#include #include #include int main()char s100;double x;int i;gets(s); /* Test of atof */x = atof( s );printf( atof test: ASCII string: %s float: %lfn, s, x );gets(s); /* Test of atoi */i = atoi( s );printf( atoi test: ASCII string: %s integer:

10、 %dn, s, i );return 0;第16頁，共32頁。小明的藥物動力學(xué)名詞詞典17第17頁，共32頁。小明的藥物動力學(xué)名詞詞典回顧排序：排序的基本思想18對數(shù)組 int szLEN進行排序，可以分為 LEN 個步驟進行。 第 k 步：把第 k 大的數(shù)放在變量 szLEN-k 中；（K=1, 2, 3, 4, , LEN-1, LEN）第18頁，共32頁。小明的藥物動力學(xué)名詞詞典回顧排序：冒泡排序19int e;for(int k = 1 ; k = LEN ; k+)for(int i = 0; i szi+1)e = szi+1;szi+1 = szi;szi = e;第19頁，共

11、32頁。小明的藥物動力學(xué)名詞詞典數(shù)據(jù)表示：字符串?dāng)?shù)組char word100100;字符串大小比較：strcmp(str1, str2)strcmp(wordi, wordi+1) 0字符串內(nèi)容的交換：strcpy(str1, str2)char temp100;strcpy(temp, wordi); strcpy(wordi, wordi+1);strcpy(wordi+1, temp);20第20頁，共32頁。21#include #include int main()int n, k, i;char word100100, temp100; /字符串?dāng)?shù)組scanf(%d, &n);fo

12、r(i=0; in; i+) /輸入字符串scanf(%s, wordi);for(k=1; k=n; k+) /排序for(i=0; i0 ) /字符串大小比較strcpy(temp, wordi); /字符串交換strcpy(wordi, wordi+1);strcpy(wordi+1, temp);for(i=0;in;i+) /輸出字符串printf(%sn,wordi);return 0;第21頁，共32頁。22大整數(shù)的加法問題描述 請編寫一個程序幫助統(tǒng)計局完成以下計算任務(wù)：從鍵盤輸入兩個正整數(shù)m和n（根據(jù)統(tǒng)計需要，m和n最多可以是200位十進制正整數(shù)），計算m和n的和，并打印輸出。

13、第22頁，共32頁。23大整數(shù)的加法計算 83856 + 129476解決輸入的問題：利用字符數(shù)組接收輸入；為了進行計算：把字符數(shù)組轉(zhuǎn)換成整數(shù)數(shù)組，每個元素 與字符數(shù)組中的每個字符相對應(yīng)；轉(zhuǎn)換過程中可以順便更換一下擺放順序，以便符合我們平時的豎式計算習(xí)慣；按照規(guī)則進行計算，用數(shù)組元素操作每一位（注意進位）；把操作結(jié)果按照“先高位再低位”的順序輸出出來；838561294768385612947665838674921233312213332第23頁，共32頁。24#define MAX_LEN 201#include int main()int an1MAX_LEN = 0, an2MAX_L

14、EN = 0; int sumMAX_LEN = 0;char seLine1MAX_LEN, seLine2MAX_LEN;printf(please input two integers:n);gets(seLine1);gets(seLine2);int nLen1 = strlen(seLine1);int nLen2 = strlen(seLine2);使用strlen()函數(shù)： 獲得字符串的長度！第24頁，共32頁。25int i, j; /將輸入的兩個字符數(shù)組變成整數(shù)數(shù)組，并倒置for (i = nLen1-1, j=0; i=0; i-, j+)an1j = seLine1i

15、- 0; for (i = nLen2-1, j=0; i=0; i-, j+)an2j = seLine2i - 0; 838560129476065838000006749210000字符數(shù)組整數(shù)數(shù)組第25頁，共32頁。int carry = 0; /進位值for (i = 0; i = 10) sumi -= 10; carry = 1; else carry = 0;i = MAX_LEN -1;while(sumi=0) /找到第一個不為0的位 i-; for(;i = 0; i-) /假設(shè)總和不為0！printf(%d, sumi); /輸出每一位數(shù)printf(n);return

16、 0;65838000006749210000233312000021333226carry第26頁，共32頁。算法的效率素數(shù)問題判斷一個數(shù)是否素數(shù)27int isPrimeNumber(int p)int i, half, isPrime1;if ( p % 2 = 0 ) if ( p = 2 ) return isPrime; isPrime = 0;return isPrime;half = p - 1;for( i = 3; i = half; i = i+2 ) if( p % i = 0 ) isPrime = 0;break;return isPrime;half = p /

17、2; half = sqrt(p);第27頁，共32頁。算法的效率素數(shù)問題驗證哥德巴赫猜想28int GoldbachConjecture(int n) / 驗證偶數(shù)n滿足哥德巴赫猜想int half = n/2; / 求出半數(shù)n/2待用int i, result = 0, isPrime1, isPrime2;for( i = 3; i 2int i; / 循環(huán)變量int isPrime; / 臨時變量 printf(“The primes less than %d are 2”, n);for( i = 3; i 2int number=1; /小于n的素數(shù)的個數(shù)int primes100

18、; /用于存放素數(shù)int i, j; /循環(huán)變量primes0 = 2; /2是第一個素數(shù)printf(“The primes less than %d are 2”, n);for( i = 3; i = n; i = i + 2 ) /判斷i是否被它之前的素數(shù)整除for(j=0; primesj*primesji ) /如果i不能被它之前的素數(shù)整除，則它也是素數(shù)primesnumber = i;number+;printf(“,%d, i);一個效率更高的算法：如果一個數(shù)不是素數(shù)那么它一定是若干個小于它的素數(shù)的乘積，并且它小于在它之前的那個最大素數(shù)的平方。問題：修改這個函數(shù)，求第n個素數(shù)？求小于n的所有素數(shù)第30頁，共32頁。31int nthPrime(int n)int number=1; /小于n的素數(shù)的個數(shù)int *primes = (int *)malloc(sizeof(int)*n); /用于存放素數(shù)int i, j; / 循環(huán)變量primes0 = 2; /2是第一