計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科

1、數(shù)據(jù)結(jié)構(gòu),第一講 緒 論,計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)（本科）,,● 關(guān)于該課程和課程學(xué)習(xí),● 數(shù)據(jù)結(jié)構(gòu)的基本術(shù)語,● 數(shù)據(jù)結(jié)構(gòu)的分類和表示,● 數(shù)據(jù)結(jié)構(gòu)的算法評(píng)價(jià),● 數(shù)據(jù)結(jié)構(gòu)的算法工具,目 錄,教學(xué)要求 理解數(shù)據(jù)結(jié)構(gòu)的基本術(shù)語，掌握邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的概念。 理解各類數(shù)據(jù)結(jié)構(gòu)的特征及表示方法。 理解數(shù)據(jù)結(jié)構(gòu)的評(píng)價(jià)標(biāo)準(zhǔn)，掌握時(shí)間復(fù)雜性的分析方法。 了解數(shù)據(jù)結(jié)構(gòu)使用的算法工具。,●下單元導(dǎo)學(xué),,,

2、一、關(guān)于該課程和課程學(xué)習(xí),1、關(guān)于課程,,◎ 課程任務(wù)：掌握各種數(shù)據(jù)結(jié)構(gòu)的特征、性質(zhì) 、表示和操 作運(yùn)算， 掌握對(duì)數(shù)據(jù)進(jìn)行搜索和排序等運(yùn)算 的基本方法,◎ 課程性質(zhì)：屬專業(yè)基礎(chǔ)課和技術(shù)基礎(chǔ)課，是該專業(yè)的主干 課程 之一,◎ 課程屬性：中央統(tǒng)設(shè)，4個(gè)學(xué)分,◎ 課程特點(diǎn)：概念多，算法多，算法分析難,◎ 文字教材：殷人昆編著《數(shù)據(jù)結(jié)構(gòu)》、徐孝

3、凱等編的實(shí)驗(yàn) 指導(dǎo)、習(xí)題解答和中央電大編的形成性考核冊(cè),,,2、關(guān)于課程學(xué)習(xí),,◎課堂輔導(dǎo)：重點(diǎn)內(nèi)容講授、難題解析,◎上機(jī)實(shí)驗(yàn)：做實(shí)驗(yàn)指導(dǎo)書中的七個(gè),◎平時(shí)作業(yè)：形成性考核冊(cè)中的全部題目，提交 4次，批改2次，檢查完成情況2次,◎上機(jī)考試：期末進(jìn)行，按題目自行編程、調(diào)試， 一個(gè)小時(shí)完成◎考核方法：作業(yè)和實(shí)驗(yàn)15%，上機(jī)

4、考試15%， 期末閉卷筆試統(tǒng)考70%,,,3、《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)模式 ---- 單元循環(huán)式 根據(jù)課程內(nèi)容的內(nèi)在聯(lián)系將其分成若干單元，以單元循環(huán)重復(fù)教學(xué)。 第一循環(huán)是參考輔導(dǎo)教師的導(dǎo)學(xué)意見，學(xué)生初讀主教材該單元的內(nèi)容，思考對(duì)主要知識(shí)點(diǎn)的理解并提出疑難 第二循環(huán)是學(xué)生在校園網(wǎng)“專業(yè)論壇”的本課程平臺(tái)就單元內(nèi)容提問和討論，或用電子郵件和電話方式向請(qǐng)求輔導(dǎo)

5、教師解答 第三循環(huán)是輔導(dǎo)教師在廣泛收集學(xué)生提問的基礎(chǔ)上，篩選出帶有普遍性的問題，進(jìn)行集中答疑 第四循環(huán)是學(xué)生完成《形成性考核冊(cè)》中相應(yīng)的作業(yè) 第五循環(huán)是從《實(shí)驗(yàn)指導(dǎo)書》中選擇一兩個(gè)與單元內(nèi)容相關(guān)的實(shí)驗(yàn)上機(jī)編程調(diào)式 第六循環(huán)是學(xué)生借助《數(shù)據(jù)結(jié)構(gòu)課程網(wǎng)站》（sjjg.ougz.com.cn）的“同步練習(xí)”平臺(tái)按6種題型進(jìn)行練習(xí)和測試 第七循環(huán)是輔導(dǎo)教師作單元小結(jié)，并提出下單元的

6、導(dǎo)學(xué)意見,二、基本術(shù)語,1、數(shù)據(jù)—用文字符號(hào)、數(shù)字符號(hào)及其它規(guī)定的符號(hào)對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)的抽象描述,2、數(shù)據(jù)元素—數(shù)據(jù)整體中相對(duì)獨(dú)立的單位,3、數(shù)據(jù)結(jié)構(gòu),◎數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的聯(lián)系 ◎數(shù)據(jù)結(jié)構(gòu)有邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之分 ◎物理結(jié)構(gòu)是一種邏輯結(jié)構(gòu)在存儲(chǔ)器中的存儲(chǔ)方式，存貯方式有順序、鏈接、索引、散列等多種，所以一種邏輯結(jié)構(gòu)可以采用多種物理結(jié)構(gòu)存貯 ◎邏輯結(jié)構(gòu)所關(guān)注的是數(shù)據(jù)之間的聯(lián)系，是這種聯(lián)系的抽象描述 ◎通

7、常所說的數(shù)據(jù)結(jié)構(gòu)就是指邏輯結(jié)構(gòu),,三、數(shù)據(jù)結(jié)構(gòu)的分類及表示方法,實(shí)例：教務(wù)處人事簡表（表1—1）,◎目錄行包括六個(gè)數(shù)據(jù)項(xiàng)，這些定義了表的結(jié)構(gòu) ◎共有十條記錄，一個(gè)記錄就是一個(gè)數(shù)據(jù)元素 ◎“職工號(hào)”的值能唯一地標(biāo)識(shí)一個(gè)記錄，該數(shù)據(jù)項(xiàng)叫做 關(guān)鍵項(xiàng),設(shè)表1—1中只考慮年齡大小的排列 ◎圖形表示,◎二元組表示 line＝ (K，R) K＝{01，02，03，04，05，06，07，08，09，10}

8、R＝{r} r＝{〈05,01〉, 〈01,03〉, 〈03,08〉, 〈08,02〉, 〈02,07〉, 〈07,04〉, 〈04,06〉, 〈06,09〉, 〈09,10〉},◎結(jié)構(gòu)特點(diǎn)：數(shù)據(jù)元素之間最多只有一個(gè)前驅(qū)，最多只有一個(gè)后繼，元素之間是一對(duì)一聯(lián)系，即1︰1,1、線性結(jié)構(gòu),,設(shè)表1—1中只考慮領(lǐng)導(dǎo)和被領(lǐng)導(dǎo)關(guān)系,◎圖形表示,◎二元組表示 tree＝(K，R) K＝{01,05,03,

9、08,04,06,02,07,09,10} R＝{r} r＝{〈 01,02〉, 〈01,03〉, 〈01,04〉, 〈02,05〉, 〈03,06〉，〈03,07〉, 〈03,08〉, 〈04,09〉,〈04,10〉},◎結(jié)構(gòu)特點(diǎn)：每個(gè)元素最多有一個(gè)前驅(qū)，但可有多個(gè)后繼，元素之間是一對(duì)多關(guān)系，即1︰N，有層次關(guān)系,2、樹形結(jié)構(gòu),3、圖形結(jié)構(gòu) 設(shè)表1—1中只考慮個(gè)人之間的關(guān)系,◎ 圖示,◎二元組表示

10、 graph＝(K，R) K＝ {01，02，03，04，05，06，07，08，09，10} R＝{r} r＝{(01,02)，(01,05)，(04,01)，(02,03)，(05,03)，(03,06)，(07,06)，(07,10)，(08,07)，(04,07)，(04,09)},◎特點(diǎn)：每個(gè)元素可以有多個(gè)前驅(qū)和多個(gè)后即 N︰M ，包含回路，無層次關(guān)系。

11、 ◎圖有有向圖和無向圖之分。,,四、算法評(píng)價(jià),1、算法,◎算法即解決特定問題的方法，可以描述為“數(shù)據(jù)結(jié)構(gòu)＋程序語言” ◎?qū)ν粋€(gè)問題，不同人所設(shè)計(jì)的算法互不同 ◎本課程的目的就是要對(duì)特定的問題，按照具體要求，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)出較好的算法,2、算法評(píng)價(jià)標(biāo)準(zhǔn),◎正確性——合理的數(shù)據(jù)輸入下，在有限的運(yùn)行時(shí)間內(nèi)得出正確的結(jié)果 ◎健壯性——對(duì)不合理的數(shù)據(jù)輸入的反應(yīng)和處理能力 ◎可讀性——供人們閱讀的方便程度

12、◎簡單性——采用數(shù)據(jù)結(jié)構(gòu)和方法的簡單程度 ◎時(shí)間復(fù)雜度（計(jì)算復(fù)雜度）——算法運(yùn)行時(shí)間的相 對(duì)量度 ◎空間復(fù)雜度——算法運(yùn)行中臨時(shí)占用空間大小的量度,3、時(shí)間復(fù)雜度（Time Complexity）,◎算法運(yùn)行時(shí)間約等于計(jì)算機(jī)執(zhí)行一個(gè)簡單操作的時(shí)間與算法所包含簡單操作次數(shù)之積 ◎任何一個(gè)算法最終都分解成簡單操作來具體執(zhí)行，減小這種簡單操作的次數(shù)是本課程能有所作為的 ◎算法包含的簡單操作次數(shù)的多少叫做時(shí)間復(fù)雜度

13、 ◎若解決一個(gè)問題的規(guī)模為n，則TC＝f (n),例1：累加求和,原算法：int sum(int b[ ],int n) { int s＝0; for(int i＝0;i<n;i++) s+＝b[i]; return s;},分解算法： 簡

14、單操作次數(shù)： s＝0 // 1 i＝0; // 1 mark1:if(i>=n) goto mark2; // n+1

15、 s+＝b[i]; // n i++; // n goto mark1; // n mark2:return s; // 1

16、 TC＝f(n) ＝4n+4,,例2： 矩陣相加,原算法： void Matrixadd(int a[MS][MS], intb [MS][MS], int c[MS][MS],int n) //MS為大于等于n的常量 {

17、 int i,j; for (i＝0;i<n;i++) for (j＝0;j<n;j++) c[i][j] ＝a[i][j]+b[i][j]; },分解算法： 簡單操作次數(shù)： i＝0;

18、 // 1 mark1:if(!(i<n)) goto mark4; // n+1 j＝0; // n mark2:if(!(j<n)) goto mark3;

19、 // n(n+1) c[I][j] ＝a[I][j]+b[I][j]; // n﹡n j++; // n﹡n goto mark2; //

20、n﹡n mark3: i++ // n goto mark1; // n mark4: ; TC＝f(n) ＝4n² + 5n + 2,,,,4

21、、空間復(fù)雜性（Space Complexity）,◎ 算法運(yùn)行中占用空間包括算法本身占用，輸入輸出數(shù)據(jù)占用和運(yùn)行中的臨時(shí)占 ◎ 同一個(gè)問題，算法不同，運(yùn)行中的臨時(shí)空間不同，即空間復(fù)雜性不同 ◎ SC只考慮在運(yùn)行中為局部變量分配的存貯空間的大小，一般也以數(shù)量級(jí)表示,,,五、算法工具 1、 采用VC+ + 程序設(shè)計(jì)語言作為編程工具 2、 一般以類（包括模板類）方式描述 3、 關(guān)注的是實(shí)現(xiàn)函數(shù)，整個(gè)

22、程序（頭文件、 實(shí)現(xiàn)文件和主文件的組合）一般不給出 4、涉及C++ 語法問題，一般不多解釋,,,第一單元導(dǎo)學(xué) 1、單元組成：第2章至第4章，共3章。 2、共性：相同的邏輯結(jié)構(gòu) --- 線性結(jié)構(gòu)。數(shù)組是順序存儲(chǔ)的線性表，鏈表是鏈?zhǔn)酱鎯?chǔ)的線性表，棧和隊(duì)列是運(yùn)算位置被限定的線性表。 3、教學(xué)要求：掌握順序表的定義、特點(diǎn)和基本運(yùn)算，數(shù)組的存儲(chǔ)方式，單鏈表的定義和基本運(yùn)算，棧和隊(duì)列的特點(diǎn)、存儲(chǔ)結(jié)構(gòu)和