算法及算法分析2

1、算法及算法分析 算法算法是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。一個(gè)算法應(yīng)滿足以下五個(gè)重要特性五個(gè)重要特性：1 1有窮性有窮性 2 2確定性確定性 3 3可行性可行性4 4有輸入有輸入 5 5有輸出有輸出算法算法1 1有窮性有窮性 對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間有限時(shí)間內(nèi)完成； 2 2確定性確定性 對(duì)于每種情況每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且并且在任何條件下，算法都只有一在任何條件下，算法都只有一

2、條執(zhí)行路徑；條執(zhí)行路徑；例: (1)begin (2)n=1 (3)n=n+1 (4)repeat (3) (5)end例: (1)begin (2)n=1 (3)n=n+1 (4)if n=100 do (5),else repeat(3) (5)output n (6)end3 3可行性可行性 算法中的所有操作都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之；4 4有輸入有輸入 輸入作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過(guò)程中輸入，而有的算法表面上可以沒(méi)有輸入，實(shí)際上已被嵌入算法之中； 5 5有輸出有輸出 它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息

3、加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。課堂思考例：從n個(gè)整數(shù)元素中找出最大值。文字描述流程圖算法設(shè)計(jì)的原則算法設(shè)計(jì)的原則設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1正確性正確性2. . 可讀性可讀性3健壯性健壯性4高效率與低存儲(chǔ)量需求高效率與低存儲(chǔ)量需求 c c程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； 通常以第 c c 層意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。 d d程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)

4、據(jù)都能得出滿足要求 的結(jié)果；的結(jié)果；a a程序中不含語(yǔ)法錯(cuò)誤；程序中不含語(yǔ)法錯(cuò)誤；b b程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；2. . 可讀性可讀性 算法主要是為了人的閱讀與交流閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行。因此算法應(yīng)該易易于人的理解于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試；例：例：a = ab； b = ab； a = ab；3健壯性健壯性 當(dāng)輸入的數(shù)據(jù)當(dāng)輸入的數(shù)據(jù)非法非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)地作出反映或進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出生莫名奇妙的

5、輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。以便在更高的抽象層次上進(jìn)行處理。4高效率與低存儲(chǔ)量需求高效率與低存儲(chǔ)量需求 通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間。兩者都與問(wèn)題的規(guī)模有關(guān)。 同一問(wèn)題可以采用多種算法實(shí)現(xiàn)。如何同一問(wèn)題可以采用多種算法實(shí)現(xiàn)。如何比較算法執(zhí)行效率？比較算法執(zhí)行效率？ 算法描述的語(yǔ)言不同算法描述的語(yǔ)言不同 算法執(zhí)行的環(huán)境不同算法執(zhí)行的環(huán)境不同 其他因素其他因素 所以不能用絕對(duì)執(zhí)行時(shí)間進(jìn)行比較所

6、以不能用絕對(duì)執(zhí)行時(shí)間進(jìn)行比較 算法執(zhí)行時(shí)間需通過(guò)依據(jù)該算法編制的程序在算法執(zhí)行時(shí)間需通過(guò)依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間來(lái)度量。其方法通常有兩種：計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間來(lái)度量。其方法通常有兩種：事后統(tǒng)計(jì)事后統(tǒng)計(jì)：計(jì)算機(jī)內(nèi)部進(jìn)行執(zhí)行時(shí)間和實(shí)際占用空間的：計(jì)算機(jī)內(nèi)部進(jìn)行執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)。統(tǒng)計(jì)。 問(wèn)題：必須先運(yùn)行依據(jù)算法編制的程序；依賴(lài)問(wèn)題：必須先運(yùn)行依據(jù)算法編制的程序；依賴(lài)軟硬件環(huán)境，容易掩蓋算法本身的優(yōu)劣；沒(méi)有實(shí)際價(jià)值。軟硬件環(huán)境，容易掩蓋算法本身的優(yōu)劣；沒(méi)有實(shí)際價(jià)值。事前分析事前分析：求出該算法的一個(gè)時(shí)間界限函數(shù)。：求出該算法的一個(gè)時(shí)間界限函數(shù)。1.3.3 算法效率

7、的度量算法效率的度量與此相關(guān)的因素有：與此相關(guān)的因素有： 依據(jù)算法選用何種策略；依據(jù)算法選用何種策略； 問(wèn)題的規(guī)模；問(wèn)題的規(guī)模； 程序設(shè)計(jì)的語(yǔ)言；程序設(shè)計(jì)的語(yǔ)言； 編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量；編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量； 機(jī)器執(zhí)行指令的速度；機(jī)器執(zhí)行指令的速度； 撇開(kāi)軟硬件等有關(guān)部門(mén)因素，可以認(rèn)為一個(gè)特定撇開(kāi)軟硬件等有關(guān)部門(mén)因素，可以認(rèn)為一個(gè)特定算法算法“運(yùn)行工作量運(yùn)行工作量”的大小，只依賴(lài)于問(wèn)題的規(guī)模的大小，只依賴(lài)于問(wèn)題的規(guī)模（通常用（通常用n n表示），或者說(shuō)，它表示），或者說(shuō)，它是問(wèn)題規(guī)模的函數(shù)是問(wèn)題規(guī)模的函數(shù)。 算法中算法中基本操作重復(fù)執(zhí)行的次數(shù)基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模

8、是問(wèn)題規(guī)模n n的某個(gè)函數(shù)，其時(shí)間量度記作的某個(gè)函數(shù)，其時(shí)間量度記作 T(n)=O(f(n)T(n)=O(f(n)，稱(chēng)作，稱(chēng)作算法的漸近時(shí)間復(fù)雜度算法的漸近時(shí)間復(fù)雜度( (Asymptotic Time complexityAsymptotic Time complexity) )，簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度時(shí)間復(fù)雜度。 一般地，常用一般地，常用最深層循環(huán)內(nèi)最深層循環(huán)內(nèi)的語(yǔ)句中的原操作的語(yǔ)句中的原操作的的執(zhí)行頻度執(zhí)行頻度( (重復(fù)執(zhí)行的次數(shù)重復(fù)執(zhí)行的次數(shù)) )來(lái)表示。來(lái)表示。 “O”O(jiān)”的定義：的定義： 若若f(n)f(n)是正整數(shù)是正整數(shù)n n的一個(gè)函數(shù)，則的一個(gè)函數(shù)，則 O(f(n)O(f(n)表

9、示表示 M M0 0 ，使得當(dāng)，使得當(dāng)n n n n0 0時(shí)，時(shí)，| f(n) | | f(n) | M M | f(n| f(n0 0) | ) | 。表示表示時(shí)間復(fù)雜度時(shí)間復(fù)雜度的階有：的階有： O(1)O(1) ：常量時(shí)間階：常量時(shí)間階 O (n)O (n)：線性時(shí)間：線性時(shí)間階階 O(O(n)n) ：對(duì)數(shù)時(shí)間階：對(duì)數(shù)時(shí)間階 O(nO(nn)n) ：線性對(duì)數(shù)時(shí)：線性對(duì)數(shù)時(shí)間階間階算法分析應(yīng)用舉例 O (nO (nk k) )： k k2 2 ，k k次方時(shí)間階次方時(shí)間階例例 兩個(gè)兩個(gè)n n階方陣的乘法階方陣的乘法 for(i=1for(i=1，i=n; +i)i=n; +i) for(j

10、=1; j=n; +j) for(j=1; j=n; +j) cij=0 ; cij=0 ; for(k=1; k=n; +k) for(k=1; k=n; +k) cij+=aikcij+=aik* *bkj ; bkj ; 由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從1 1到到n n，則總次數(shù)為：，則總次數(shù)為： n nn nn=nn=n3 3時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為T(mén)(n)=O(nT(n)=O(n3 3) )例例 +x; s=0 ;+x; s=0 ; 將將x x自增看成是基本操作，則語(yǔ)句頻度為，自增看成是基本操作，則語(yǔ)句頻度為，即時(shí)間復(fù)雜度為即時(shí)間復(fù)雜度為(1) (1) 。

11、如果將如果將s=0s=0也看成是基本操作，則語(yǔ)句頻度為，其時(shí)也看成是基本操作，則語(yǔ)句頻度為，其時(shí)間復(fù)雜度仍為間復(fù)雜度仍為(1)(1)，即常量階。，即常量階。例例 for(i=1; i=n; +i)for(i=1; i=n; +i) +x; s+=x ; +x; s+=x ; 語(yǔ)句頻度為：語(yǔ)句頻度為：2n2n，其時(shí)間復(fù)雜度為：，其時(shí)間復(fù)雜度為：O(n) O(n) ，即為線性，即為線性階。階。例例 for(i=1; i=n; +i)for(i=1; i=n; +i)for(j=1; j=n; +j)for(j=1; j=n; +j) +x; s+=x ; +x; s+=x ; 語(yǔ)句頻度為：語(yǔ)句頻度

12、為：2n2n2 2 ，其時(shí)間復(fù)雜度為：，其時(shí)間復(fù)雜度為：O(nO(n2 2) ) ，即為，即為平方階。平方階。 定理定理：若若A(n)=a A(n)=a m m n n m m +a +a m-1m-1 n n m-1m-1 +a +a1 1n+an+a0 0是一個(gè)是一個(gè)m m次多項(xiàng)式，則次多項(xiàng)式，則A(n)=O(nA(n)=O(n m m) )例例 for(i=2;i=n;+i)for(i=2;i=n;+i) for(j=2;j=i-1;+j) for(j=2;j=i-1;+j) +x; ai,j=x; +x; ai,j=x; 語(yǔ)句頻度為：語(yǔ)句頻度為： 1+2+3+1+2+3+n-2=(1+

13、n-2) +n-2=(1+n-2) (n-2)/2(n-2)/2 =(n-1)(n-2)/2 =n=(n-1)(n-2)/2 =n2 2-3n+2-3n+2 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(nO(n2 2) )，即此算法的時(shí)間復(fù)雜度為平方，即此算法的時(shí)間復(fù)雜度為平方階。階。 一個(gè)算法時(shí)間為一個(gè)算法時(shí)間為O(1)O(1)的算法，它的基本運(yùn)算執(zhí)行的算法，它的基本運(yùn)算執(zhí)行的次數(shù)是固定的。因此，總的時(shí)間由一個(gè)常數(shù)（即的次數(shù)是固定的。因此，總的時(shí)間由一個(gè)常數(shù)（即零次多項(xiàng)式）來(lái)限界。而一個(gè)時(shí)間為零次多項(xiàng)式）來(lái)限界。而一個(gè)時(shí)間為O(nO(n2 2) )的算法則的算法則由一個(gè)二次多項(xiàng)式來(lái)限界。由一個(gè)二次多項(xiàng)式來(lái)限

14、界。 以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。其關(guān)系為：其關(guān)系為： O(1)O(O(1)O(n)O(n)O(nn)O(n)O(nn)O(nn)O(n2 2)O(n)O(n3 3) ) 指數(shù)時(shí)間的關(guān)系為：指數(shù)時(shí)間的關(guān)系為： O(2O(2n n)O(n!)O(n)O(n!)O(nn n) ) 當(dāng)當(dāng)n n取得很大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)取得很大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需時(shí)間上非常懸殊。因此，只要有人能將間算法在所需時(shí)間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時(shí)間算法中的任何一個(gè)算法化簡(jiǎn)為多項(xiàng)式時(shí)現(xiàn)有指數(shù)時(shí)間算法中的任何一個(gè)算法化簡(jiǎn)為多項(xiàng)式時(shí)間算法，

15、那就取得了一個(gè)偉大的成就。間算法，那就取得了一個(gè)偉大的成就。 有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問(wèn)題的輸入數(shù)據(jù)集不同而不同。還隨問(wèn)題的輸入數(shù)據(jù)集不同而不同。例例1 1：素?cái)?shù)的判斷算法。素?cái)?shù)的判斷算法。Void prime( int n)Void prime( int n)/ /* * n n是一個(gè)正整數(shù)是一個(gè)正整數(shù) * */ / int i=2 ; int i=2 ; while ( (n% i)!=0 & iwhile ( (n% i)!=0 & i* *1.0 sqrt(n) ) 1.0sqrt(n) )1.0sqrt(n)

16、 )printf(“&d printf(“&d 是一個(gè)素?cái)?shù)是一個(gè)素?cái)?shù)n” , n) ;n” , n) ;elseelseprintf(“&d printf(“&d 不是一個(gè)素?cái)?shù)不是一個(gè)素?cái)?shù)n” , n) ;n” , n) ; 嵌套的最深層語(yǔ)句是嵌套的最深層語(yǔ)句是i+i+；其頻度由條件；其頻度由條件( (n% ( (n% i)!=0 & ii)!=0 & i* *1.0 sqrt(n) ) 1.0 sqrt(n) ) 決定，顯然決定，顯然i i* *1.0 1.01 & change; -i)for (i=n-1; change=TURE;

17、 i1 & change; -i)for (j=0; ji; +j)for (j=0; jaj+1) if (ajaj+1) aj aj+1 ; aj aj+1 ; change=TURE ; change=TURE ; 最好情況：最好情況：0 0次次 最壞情況：最壞情況：1+2+3+1+2+3+ +n-1=n(n-1)/2+n-1=n(n-1)/2 平均時(shí)間復(fù)雜度為：平均時(shí)間復(fù)雜度為： O(nO(n2 2) ) 空間復(fù)雜度空間復(fù)雜度( (Space complexitySpace complexity) ) ：是指算法：是指算法編寫(xiě)成程序后，在計(jì)算機(jī)中運(yùn)行時(shí)所需存儲(chǔ)空間大小編寫(xiě)成程序

18、后，在計(jì)算機(jī)中運(yùn)行時(shí)所需存儲(chǔ)空間大小的度量。記作：的度量。記作： S(n)=O(f(n) S(n)=O(f(n) 其中：其中： n n為問(wèn)題的規(guī)模為問(wèn)題的規(guī)模( (或大小或大小) )該存儲(chǔ)空間一般包括三個(gè)方面：該存儲(chǔ)空間一般包括三個(gè)方面： 指令常數(shù)變量所占用的存儲(chǔ)空間指令常數(shù)變量所占用的存儲(chǔ)空間; ; 輸入數(shù)據(jù)所占用的存儲(chǔ)空間輸入數(shù)據(jù)所占用的存儲(chǔ)空間; ; 輔助輔助( (存儲(chǔ)存儲(chǔ)) )空間。空間。 一般地，算法的一般地，算法的空間復(fù)雜度空間復(fù)雜度指的是指的是輔助空間輔助空間。 一維數(shù)組一維數(shù)組anan： 空間復(fù)雜度空間復(fù)雜度 O(n)O(n) 二維數(shù)組二維數(shù)組anmanm： 空間復(fù)雜度空間復(fù)雜

19、度 O(nO(n* *m)m)1.3.4 算法的空間分析算法的空間分析例，有若干學(xué)生數(shù)據(jù)（學(xué)生數(shù)小于例，有若干學(xué)生數(shù)據(jù)（學(xué)生數(shù)小于50），），每個(gè)學(xué)生數(shù)據(jù)包含學(xué)號(hào)（每個(gè)學(xué)生學(xué)號(hào)是惟每個(gè)學(xué)生數(shù)據(jù)包含學(xué)號(hào)（每個(gè)學(xué)生學(xué)號(hào)是惟一的，但學(xué)生記錄不一定按學(xué)號(hào)順序存放）、一的，但學(xué)生記錄不一定按學(xué)號(hào)順序存放）、姓名、班號(hào)和若干門(mén)課程成績(jī)（每個(gè)學(xué)生所姓名、班號(hào)和若干門(mén)課程成績(jī)（每個(gè)學(xué)生所選課程數(shù)目可能不等，但最多不超過(guò)選課程數(shù)目可能不等，但最多不超過(guò)6門(mén)）。門(mén)）。要求設(shè)計(jì)一個(gè)程序輸出每個(gè)學(xué)生的學(xué)號(hào)、要求設(shè)計(jì)一個(gè)程序輸出每個(gè)學(xué)生的學(xué)號(hào)、姓名和平均分以及每門(mén)課程（課程編號(hào)從姓名和平均分以及每門(mén)課程（課程編號(hào)從16

20、）的平均分。）的平均分。設(shè)計(jì)方案設(shè)計(jì)方案1 1：將學(xué)生的全部數(shù)據(jù)項(xiàng)放在一個(gè)：將學(xué)生的全部數(shù)據(jù)項(xiàng)放在一個(gè)表中，一個(gè)學(xué)生的全部數(shù)據(jù)對(duì)應(yīng)一條記錄。由于表中，一個(gè)學(xué)生的全部數(shù)據(jù)對(duì)應(yīng)一條記錄。由于課程最多可選課程最多可選6 6門(mén)，對(duì)應(yīng)的成績(jī)項(xiàng)也應(yīng)有門(mén)，對(duì)應(yīng)的成績(jī)項(xiàng)也應(yīng)有6 6個(gè)。對(duì)個(gè)。對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下：應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下：struct stud int no;/*學(xué)號(hào)學(xué)號(hào)*/char name10;/*姓名姓名*/int bno;/*班號(hào)班號(hào)*/int deg1;/*課程課程1分?jǐn)?shù)分?jǐn)?shù)*/int deg2;/*課程課程2分?jǐn)?shù)分?jǐn)?shù)*/int deg3;/*課程課程3分?jǐn)?shù)分?jǐn)?shù)*/int deg4;/*課程課

21、程4分?jǐn)?shù)分?jǐn)?shù)*/int deg5;/*課程課程5分?jǐn)?shù)分?jǐn)?shù)*/int deg6;/*課程課程6分?jǐn)?shù)分?jǐn)?shù)*/;nonamebnodeg1deg2deg3deg4deg5deg61張斌張斌99017882639285838劉麗劉麗9902659572788079特點(diǎn)：特點(diǎn)：存儲(chǔ)空間：中（若學(xué)生沒(méi)有選該課程，對(duì)應(yīng)空間仍存在）存儲(chǔ)空間：中（若學(xué)生沒(méi)有選該課程，對(duì)應(yīng)空間仍存在）算法時(shí)間：少算法時(shí)間：少算法簡(jiǎn)潔性差：算法完全依賴(lài)數(shù)據(jù)結(jié)構(gòu)算法簡(jiǎn)潔性差：算法完全依賴(lài)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)方案設(shè)計(jì)方案2 2：將學(xué)生的全部數(shù)據(jù)項(xiàng)放在一個(gè)表：將學(xué)生的全部數(shù)據(jù)項(xiàng)放在一個(gè)表中，但一個(gè)學(xué)生的一門(mén)課程成績(jī)對(duì)應(yīng)一條記錄。中，但一個(gè)學(xué)生的

22、一門(mén)課程成績(jī)對(duì)應(yīng)一條記錄。這樣成績(jī)項(xiàng)只需要一個(gè)，為了區(qū)分不同課程成績(jī)，這樣成績(jī)項(xiàng)只需要一個(gè)，為了區(qū)分不同課程成績(jī)，需增加一個(gè)課程編號(hào)項(xiàng)。對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下：需增加一個(gè)課程編號(hào)項(xiàng)。對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下：struct stud int no;/*學(xué)號(hào)學(xué)號(hào)*/char name10;/*姓名姓名*/int bno;/*班號(hào)班號(hào)*/int cno;/*課程編號(hào)課程編號(hào)*/int deg;/*課程分?jǐn)?shù)課程分?jǐn)?shù)*/;nonamebnocnodeg1張斌張斌99011781張斌張斌99012821張斌張斌99013631張斌張斌99014921張斌張斌99015851張斌張斌99016838劉麗劉麗99021

23、658劉麗劉麗99022958劉麗劉麗99023728劉麗劉麗99024788劉麗劉麗99025808劉麗劉麗9902679特點(diǎn)：特點(diǎn)：存儲(chǔ)空間：大存儲(chǔ)空間：大算法時(shí)間：多算法時(shí)間：多算法簡(jiǎn)潔性：好算法簡(jiǎn)潔性：好設(shè)計(jì)方案設(shè)計(jì)方案3 3：將學(xué)生的學(xué)號(hào)、姓名和班號(hào)放：將學(xué)生的學(xué)號(hào)、姓名和班號(hào)放在一個(gè)表中，將成績(jī)數(shù)據(jù)放在另一個(gè)表中，兩者在一個(gè)表中，將成績(jī)數(shù)據(jù)放在另一個(gè)表中，兩者通過(guò)學(xué)號(hào)關(guān)聯(lián)。前者一個(gè)學(xué)生對(duì)應(yīng)一個(gè)記錄，后通過(guò)學(xué)號(hào)關(guān)聯(lián)。前者一個(gè)學(xué)生對(duì)應(yīng)一個(gè)記錄，后者一門(mén)課程成績(jī)對(duì)應(yīng)一條記錄。對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)者一門(mén)課程成績(jī)對(duì)應(yīng)一條記錄。對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下：如下：struct stud1 int no;/*學(xué)號(hào)學(xué)號(hào)*/char name10;/*姓名姓名*/int bno;/*班號(hào)班號(hào)*/;struct stud2 int no;/*學(xué)號(hào)學(xué)號(hào)*/int cno;/*課程編號(hào)課程編號(hào)*/int deg;/*分?jǐn)?shù)分?jǐn)?shù)*/;nonamebno1張斌張斌99018劉麗劉麗9902no