C語言高級編程結構與習題課課件

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

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

3、;系統(tǒng)會為結構類型變量分配內存空間第4頁，共32頁。5結構類型變量中分量的訪問結構類型變量的值由其各個分量構成對分量的訪問一般通過“變量名.分量名”完成結構賦值及訪問的例子：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;結構變量本身可以作為一個整體來使用points0 = p1; points1 = p2;第5頁，共32頁。6結構類型中的分量結構類型中分量的類型可以是任何類型基本數(shù)據類型的分

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

5、構變量的內存布局結構中各分量在內存中順序存放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é)數(shù)的總和struct char_frequency char c; int frequency;sizeof(strcut char_frequency)通

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

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

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

9、 atof(char *str)：將字符串轉換成浮點數(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頁。小明的藥物動力學名詞詞典17第17頁，共32頁。小明的藥物動力學名詞詞典回顧排序：排序的基本思想18對數(shù)組 int szLEN進行排序，可以分為 LEN 個步驟進行。 第 k 步：把第 k 大的數(shù)放在變量 szLEN-k 中；（K=1, 2, 3, 4, , LEN-1, LEN）第18頁，共32頁。小明的藥物動力學名詞詞典回顧排序：冒泡排序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頁。小明的藥物動力學名詞詞典數(shù)據表示：字符串數(shù)組char word100100;字符串大小比較：strcmp(str1, str2)strcmp(wordi, wordi+1) 0字符串內容的交換：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; /字符串數(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)計局完成以下計算任務：從鍵盤輸入兩個正整數(shù)m和n（根據統(tǒng)計需要，m和n最多可以是200位十進制正整數(shù)），計算m和n的和，并打印輸出。

13、第22頁，共32頁。23大整數(shù)的加法計算 83856 + 129476解決輸入的問題：利用字符數(shù)組接收輸入；為了進行計算：把字符數(shù)組轉換成整數(shù)數(shù)組，每個元素 與字符數(shù)組中的每個字符相對應；轉換過程中可以順便更換一下擺放順序，以便符合我們平時的豎式計算習慣；按照規(guī)則進行計算，用數(shù)組元素操作每一位（注意進位）；把操作結果按照“先高位再低位”的順序輸出出來；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-) /假設總和不為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是第一