數(shù)據(jù)結(jié)構(gòu)與算法分析-張曉東

1、中國(guó)海洋大學(xué)本科生課程大綱課程名稱數(shù)據(jù)結(jié)構(gòu)與算法分析Data structures and algorithm analysis課程代碼081302231293課程屬性學(xué)科基礎(chǔ)課時(shí)/學(xué)分48/2.5課程性質(zhì)選修實(shí)踐學(xué)時(shí)16責(zé)任教師張曉東課外學(xué)時(shí)課程屬性：公共基礎(chǔ)/通識(shí)教育/學(xué)科基礎(chǔ)/專業(yè)知識(shí)/工作技能，課程性質(zhì)：必修、選修_、課程介紹1. 課程描述：數(shù)據(jù)結(jié)構(gòu)與算法分析是學(xué)習(xí)利用計(jì)算機(jī)語(yǔ)言編寫質(zhì)量更好的程序以及軟件的一門 課程，是提高計(jì)算機(jī)編程水平的必由之路，為日后學(xué)習(xí)相關(guān)課程打下一個(gè)堅(jiān)實(shí)的基礎(chǔ)。 本課程針對(duì)低年級(jí)地球信息科學(xué)與技術(shù)專業(yè)和勘查技術(shù)與工程專業(yè)本科生學(xué)生開設(shè)， 課程主要內(nèi)容包括：數(shù)據(jù)

2、結(jié)構(gòu)及其算法，文件讀寫，查找和排序算法等。通過課程學(xué) 習(xí)，要求學(xué)生能夠掌握計(jì)算機(jī)存儲(chǔ)（包括內(nèi)存和外存）數(shù)據(jù)的基本方法和常用模式以 及其算法，提高編寫程序、調(diào)試程序的能力，課程結(jié)束后能夠完成較復(fù)雜程序的設(shè)計(jì) 和編制。2. 設(shè)計(jì)思路：本課程引導(dǎo)低年級(jí)地球信息科學(xué)與技術(shù)專業(yè)和勘査技術(shù)與工程專業(yè)學(xué)生掌握利用 計(jì)算機(jī)語(yǔ)言編寫實(shí)用可幕的程序的基礎(chǔ)理論和實(shí)際操作方法，提升自身的科研和工作 技能。課程內(nèi)容的選取基于學(xué)生掌握了一定的計(jì)算機(jī)語(yǔ)言知識(shí)。課程內(nèi)容分為四個(gè)模 塊：數(shù)據(jù)結(jié)構(gòu)介紹；常用的數(shù)據(jù)結(jié)構(gòu)及其算法；文件讀寫；查找和排序算法。這三個(gè) 方面相互關(guān)聯(lián)，互為補(bǔ)充，覆蓋了汁算機(jī)數(shù)據(jù)存儲(chǔ)、管理和處理等的主要模式和

3、方法。3. 課程與其他課程的關(guān)系:本課程需要本科生在完成低年級(jí)階段的計(jì)算機(jī)語(yǔ)言的基礎(chǔ)上開設(shè)。先修課程：C 程序設(shè)計(jì)。二、課程目標(biāo)本課程U標(biāo)是為低年級(jí)地球信息科學(xué)與技術(shù)專業(yè)和勘査技術(shù)與工程專業(yè)學(xué)生提供 一個(gè)深入學(xué)習(xí)計(jì)算機(jī)編程的平臺(tái)，引導(dǎo)并培養(yǎng)學(xué)生使用計(jì)算機(jī)語(yǔ)言來(lái)描述、管理和處 理數(shù)據(jù)的能力，提高計(jì)算機(jī)編程水平。到課程結(jié)束時(shí)，學(xué)生應(yīng)能：（1）熟練掌握常用的計(jì)算機(jī)數(shù)據(jù)在內(nèi)存中存儲(chǔ)的方法及其常用算法；（2）掌握文件的讀寫操作，合理的利用文件存儲(chǔ)數(shù)據(jù)；（3）掌握查找和排序常用的算法；（4）掌握如何編制可靠的程序以及程序調(diào)試的技巧。三、學(xué)習(xí)要求要完成所有的課程任務(wù)，學(xué)生必須：（1）按時(shí)上課，上課認(rèn)真聽講，

4、積極參與課堂討論。（2）按時(shí)完成上機(jī)練習(xí)，對(duì)地質(zhì)數(shù)據(jù)進(jìn)行分析和處理，提交正式的上機(jī)報(bào)告。四、教學(xué)進(jìn)度序號(hào)專題主題計(jì)劃 課時(shí)主要內(nèi)容概述實(shí)驗(yàn)實(shí)踐 內(nèi)容1數(shù)據(jù)結(jié)構(gòu) 概論數(shù)據(jù)結(jié)構(gòu)概 論2什么是數(shù)據(jù)結(jié)構(gòu);基本概念和術(shù)語(yǔ);抽 象數(shù)據(jù)類型的表示和實(shí)現(xiàn);算法和算 法分析2線性表線性表的概 念、定義、 存儲(chǔ)、實(shí)現(xiàn)和應(yīng)用10線性表的類型定義：線性表的順序表 示和實(shí)現(xiàn)：線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)； 一元多項(xiàng)式的表示和相加一元稀疏多 項(xiàng)式訃算器3棧和隊(duì)列棧和隊(duì)列的 定義、存儲(chǔ). 實(shí)現(xiàn)和應(yīng)用8棧；棧的應(yīng)用舉例：棧與遞歸的實(shí)現(xiàn)； 隊(duì)列迷宮求解4串串的表示、 實(shí)現(xiàn)和應(yīng)用2串類型的立義：串的表示和實(shí)現(xiàn)：串 的模式匹配算法；串操

5、作應(yīng)用舉例5數(shù)組和廣 義表數(shù)組的表示 方法、特殊 矩陣的壓縮 存儲(chǔ)和廣義 表的基本操 作2數(shù)組的左義；數(shù)組的順序表示和實(shí)現(xiàn)； 矩陣的壓縮存儲(chǔ)：廣義表的肚義6樹和二叉 樹樹的基本概 念、存儲(chǔ)方 式和基本操 作12樹的基本概念：二叉樹：二叉樹的遍 歷：樹與森林：哈夫曼樹與哈夫曼編 碼哈夫曼樹與 哈夫曼編碼7圖圖的存儲(chǔ)方 式和常用算 法4圖的立義和術(shù)語(yǔ)；圖的存儲(chǔ)結(jié)構(gòu)及其 實(shí)現(xiàn)；圖的遍歷算法；圖的常用其他 算法8査找靜態(tài)査找 表、動(dòng)態(tài)査 找表和哈希表a2靜態(tài)查找表；動(dòng)態(tài)查找表：哈希表9排序多種排序算 法6概述；插入排序；交換排序：選擇排 序；歸并排序內(nèi)部排序算 法比較五. 參考教材與主要參考書1、選用

6、教材：數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）嚴(yán)蔚敏、吳偉民清華大學(xué)出版社2、主要參考書：數(shù)據(jù)結(jié)構(gòu)習(xí)題集（C語(yǔ)言版）嚴(yán)蔚敏、吳偉民清華大學(xué)出版社C語(yǔ)言程序設(shè)計(jì)教程譚浩強(qiáng)高等教育出版社數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析李春葆 清華大學(xué)出版社六、成績(jī)?cè)u(píng)定（-）考核方式 A : A.閉卷考試B.開卷考試C.論文D.考查E.其他（二）成績(jī)綜合評(píng)分體系:成績(jī)綜合評(píng)分體系比例1.課下作業(yè)、課堂討論及平時(shí)表現(xiàn)（上機(jī)）502.平時(shí)測(cè)驗(yàn)03.期末考試50總計(jì)100附：上機(jī)評(píng)分標(biāo)準(zhǔn)評(píng)分標(biāo)準(zhǔn)得分1嚴(yán)格按照上機(jī)要求并及時(shí)完成，基本概念淸晰，解決問題的方案正確、合理， 能提出不同的解決問題方案。90100分2.基本按照上機(jī)要求并及時(shí)完成，基本概念基本淸晰，解決問題的方案基本正 確、基本合理。70-80 分3.不能按照上機(jī)要求，未及時(shí)完成，基本概念不淸晰，解決問題的方案基本不 正確、基本不合理。40-60 分4.不能按照上機(jī)要求，未及時(shí)完成，基本概念不清晰，不能制立正確和合理解 決問題的方案。0-30 分七. 學(xué)術(shù)誠(chéng)信學(xué)習(xí)成果不能造假，如考試作弊、盜取他人學(xué)習(xí)成果、