數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計信息工程系計算機黃取治講師福州理工學(xué)院教案課程名稱系（部）教研室授課教師職稱附件2：案（課程名稱數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計學(xué)分總計：學(xué)時講授： 學(xué)時上機： 學(xué)時實驗/訓(xùn)：學(xué)時其它： 學(xué)時類另IJ（請打J）□公共課□公共選修課□專業(yè)基礎(chǔ)課□專業(yè)必修課□專業(yè)方向選修課□實驗實訓(xùn)課（僅限本科）□公共課□公共選修課□專業(yè)基礎(chǔ)課□專業(yè)必修課□專業(yè)選修課□實驗實訓(xùn)課（僅限高職）授課對象（請打J）□本科□高職□其他使用教材參考資料（注明書名、主編、出版社、出版時間）教學(xué)方法教學(xué)手段考核方式學(xué)生創(chuàng)新精神與實踐能力的培養(yǎng)方法

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程教案(續(xù)頁)授課時間第1周授課方式(請打J)□講授□上機□實驗/訓(xùn)□其它課時安排授課題目(章節(jié)或單位課時)：第一章緒論教學(xué)目的與要求(分了解、熟悉、掌握三個層次)：.了解數(shù)據(jù)結(jié)構(gòu)課程的重要性和課程的基本要求，以及本課程涵蓋的內(nèi)容；.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念；.理解算法描述和簡單的算法分析。教學(xué)重點與難點：.重點是數(shù)據(jù)結(jié)構(gòu)的基本概念.難點是時間復(fù)雜度分析教學(xué)內(nèi)容備注.從后序課(數(shù)據(jù)庫、操作系統(tǒng)、編譯原理、人工智能)的需要和考研兩方面介紹數(shù)據(jù)結(jié)構(gòu)課程的重要性。.通過三個例子講解數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。.介紹基本概念：數(shù)據(jù)的三個層次，數(shù)據(jù)結(jié)構(gòu)的三個要素，數(shù)據(jù)結(jié)構(gòu)的分類，四種存儲結(jié)構(gòu)，抽象數(shù)據(jù)類型，算法，算法的五個特性，對算法設(shè)計的要求，算法描述和算法分析，時間復(fù)雜度和空間復(fù)雜度。.從“百錢買白雞”(“一百兀錢買一百支筆”)的算法例子說明選擇算法的重要性：方案1：for(i=0;i<=100;i++)for(j=0;j<=100;j++)for(k=0;k<=100;k++)if(i+j+k==100&&3*i+2*j+0.5*k==100)printf(“i=%d，j=%d，k=%d”,i,j,k)方案2：for(i=0;i<=20;i++)for(j=0;j<=34-i;j++)if(3*i+2*j+(100-i-j)*0.5==100)printf(“i=%d,j=%d,k=%d”,i,j,100-i-j);方案1內(nèi)層循環(huán)超過100萬次，在某機器上運行了50分鐘；方案2的if語句執(zhí)行525次，運行了2秒鐘，相差1500倍。.算法分析舉例(1)常量階：時間復(fù)雜度為0(1)++x;s=0;語句頻度為1，時間復(fù)雜度為O(1)。fora=ly<=10000;++j){++X；s+=x;}語句頻度為10000,時間復(fù)雜度為O(l)o(2)對數(shù)階：時間復(fù)雜度為O(logn)s=0;for(j=l;j<=n;j*=2)s++;語句頻度為logn,所以時間復(fù)雜度為OQogn)。(3)線性階：時間復(fù)雜度為O(logn)S=0;for(j=l;j<=n;++j)s++;語句頻度為ii,所以時間復(fù)雜度為08)。(4)時間復(fù)雜度為O(nlogn)s=0;for(j=ly<=ny*=2)for(k=l;k<=n;++k)s++;時間復(fù)雜度為O(nlogn)(5)平方階：時間復(fù)雜度為O(logn)s=0;for(j=l;j<=n;++j)for(k=1;k<=n;++k)s++;語句頻度為112,所以時間復(fù)雜度為。(112)。s=0;for(j=l;j<=n;j++)for(k=1;k<=j;++k)s++;語句頻度為n(n+l)/2,所以時間復(fù)雜度仍為O(n2)。(6)立方階：時間復(fù)雜度為O(n3)例：矩陣乘法：nxnfor(i=0;i<n;i++) 〃(n+l)for(j=0;j<n;j++) //n(n+l){C[i][j]=0； //D2for(k=0;k<n;j++) Hni(n+1)c[i][j]=c[i][j]+a[i][k]*b[k]U]; IIn3}

說明：各語句行后的數(shù)字是該語句重復(fù)執(zhí)行的次數(shù)；本算法時間復(fù)雜度為O（n3）6.空間復(fù)雜度算法原地（就地）工作：若所用額外存儲空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地（就地）工作。

教案（末頁）6

教案（末頁）6數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程教案（續(xù)頁）授課時間第周授課方式（請打J）□講授口上機口實驗/訓(xùn)口其它課時安排授課題目（章節(jié)或單位課時）：教學(xué)目的與要求（分了解、熟悉、掌握三個層次）：教學(xué)重點與難點：教學(xué)內(nèi)容備注

教案（末頁）8

教案（末頁）8數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程教案（續(xù)頁）授課時間第周授課方式（請打J）□講授□上機□實驗/訓(xùn)□其它課時安排授課題目（章節(jié)或單位課時）：教學(xué)目的與要求（分了解、熟悉、掌握三個層次）：教學(xué)重點與難點：教學(xué)內(nèi)容備注

教案（末頁）10

教案（末頁）10數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程教案（續(xù)頁）授課時間第周授課方式（請打J）□講授口上機口實驗/訓(xùn)口其它課時安排授課題目（章節(jié)或單位課時）：教學(xué)目的與要求（分了解、熟悉、掌握三個層次）：教學(xué)重點與難點：教學(xué)內(nèi)容備注11

教案（末頁）12

教案（末頁）12數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程教案（續(xù)頁）授課時間第周授課方式（請打J）□講授口上機口實驗/訓(xùn)口其它課時安排授課題目（章節(jié)或單位課時）：教學(xué)目的與要求（分了解、熟悉、掌握三個層次）：教學(xué)重點與難點：教學(xué)內(nèi)容備注13

教案（末頁）14

教案（末頁）14數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程教案（續(xù)頁）授課時間第周授課方式（請打J）□講授□上機□實驗/訓(xùn)□其它課時安排授課題目（章節(jié)或單位課時）：教學(xué)目的與要求（分了解、熟悉、掌握三個層次）：教學(xué)重點與難點：教學(xué)內(nèi)容備注15

教案（末頁）16

教案（末頁）16數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程教案（續(xù)頁）授課時間第周授課方式（請打J）□講授□上機□實驗/訓(xùn)□其它課時安排授課題目（章節(jié)或單位課時）：教學(xué)目的與要求（分了解、熟悉、掌握三個層次）：教學(xué)重點與難點：教學(xué)內(nèi)容備注17

教案（末頁）18

教案（末頁）18數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程教案（續(xù)頁）授課時間第周授課方式（請打J）□講授口上機口實驗/訓(xùn)口其它課時安排授課題目（章節(jié)或單位課時）：教學(xué)目的與要求（分了解、熟悉、掌握三個層次）：教學(xué)重點與難點：教學(xué)內(nèi)容備注19

教案（末頁）20

教案（末頁）20數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程教案（續(xù)頁）授課時間第周授課方式（請打J）□講授□上機□實驗/訓(xùn)□其它課時安排授課題目（章節(jié)或單位課時）：教學(xué)目的與要求（分了解、熟悉、掌握三個層次）：教學(xué)重點與難點：教學(xué)內(nèi)容備注21

教案（末頁）22

教案（末頁）22數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程教案（續(xù)頁）授課時間第周授課方式（請打J）□講授□上機□實驗/訓(xùn)□其它課時安排授課題目（章節(jié)或單位課時）：教學(xué)目的與要求（分了解、熟悉、掌握三個層次）：教學(xué)重點與難點：教學(xué)內(nèi)容備注23

教案（末頁）24

教案（末頁）24數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程教案（續(xù)頁）授課時間第周授課方式（請打J）□講授口上機口實驗/訓(xùn)口其它課時安排授課題目（章節(jié)或單位課時）：教學(xué)目的與要求（分了解、熟悉、掌握三個層次）：教學(xué)重點