數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱課程英文名稱：DataOrganization課程編號(hào)：0500600學(xué)分:32+16（實(shí)驗(yàn)）學(xué)時(shí):3.0一、課程教學(xué)對(duì)象數(shù)學(xué)與計(jì)算科學(xué)學(xué)院信息與計(jì)算科學(xué)專業(yè)的本科學(xué)生。二、課程性質(zhì)及教學(xué)目的課程性質(zhì)：本課程是數(shù)學(xué)與計(jì)算科學(xué)學(xué)院信息與計(jì)算科學(xué)本科專業(yè)的核心專業(yè)課。課程包括理論教學(xué)（32學(xué)時(shí)）和課內(nèi)實(shí)驗(yàn)（16學(xué)時(shí)）兩個(gè)環(huán)節(jié)。目的和任務(wù)：使學(xué)生獲得計(jì)算機(jī)科學(xué)各領(lǐng)域的數(shù)據(jù)結(jié)構(gòu)知識(shí)及有關(guān)的應(yīng)用軟件所要用到的各種數(shù)據(jù)結(jié)構(gòu)知識(shí)；從數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)的角度系統(tǒng)地學(xué)習(xí)和掌握常用基本數(shù)據(jù)結(jié)構(gòu)及其不同的實(shí)現(xiàn)方法，了解并掌握分析、比較和選擇不同數(shù)據(jù)結(jié)構(gòu)及不同存儲(chǔ)結(jié)構(gòu)、不同算法實(shí)現(xiàn)的原則和方法，為后繼課程的學(xué)習(xí)打下良好的基礎(chǔ)，?掌握常用的數(shù)據(jù)結(jié)構(gòu)及內(nèi)在的邏輯關(guān)系，掌握計(jì)算機(jī)軟件設(shè)計(jì)中的算法知識(shí)；提高軟件設(shè)計(jì)和編程技能。學(xué)會(huì)初步對(duì)不同的存儲(chǔ)結(jié)構(gòu)和相應(yīng)算法的對(duì)比，有一定的算法改進(jìn)能力。通過(guò)學(xué)習(xí)本門課程，學(xué)生應(yīng)該了解典型的數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系；應(yīng)該具有結(jié)合實(shí)際應(yīng)用，設(shè)計(jì)出高效算法和數(shù)據(jù)結(jié)構(gòu)的能力；初步具備結(jié)合專業(yè)應(yīng)用，將數(shù)據(jù)結(jié)構(gòu)知識(shí)用于專業(yè)程序設(shè)計(jì)中的能力。本課程是一門實(shí)踐性較強(qiáng)的課程。學(xué)生應(yīng)結(jié)合理論教學(xué)的進(jìn)度，通過(guò)對(duì)本課程的知識(shí)傳遞、算法設(shè)計(jì)和上機(jī)實(shí)踐的訓(xùn)練，進(jìn)一步加深對(duì)數(shù)據(jù)結(jié)構(gòu)和算法的理解，培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力、邏輯思維能力和程序設(shè)計(jì)的能力，提高分析問(wèn)題和解決問(wèn)題的能力和實(shí)際動(dòng)手能力。該課程概念性、實(shí)踐性很強(qiáng)，教學(xué)中強(qiáng)調(diào)理論聯(lián)系實(shí)際，并結(jié)合現(xiàn)代計(jì)算機(jī)技術(shù)，在教學(xué)方法與手段方面進(jìn)行改革。三、對(duì)先修知識(shí)的要求C++程序設(shè)計(jì)、離散數(shù)學(xué)等四、課程的主要內(nèi)容、基本要求和學(xué)時(shí)分配建議（總學(xué)時(shí)數(shù):理論課32學(xué)時(shí)）知識(shí)模塊知識(shí)點(diǎn)要求學(xué)時(shí)學(xué)習(xí)方式課外學(xué)習(xí)要求1、緒論1.1數(shù)據(jù)結(jié)構(gòu)的基本概念C1課堂講授1.2算法計(jì)算法分析C1課堂講授2、線性表2.1線性表的邏輯結(jié)構(gòu)B1課堂講授2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)A1課堂講授2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)A1課堂講授2.4順序表和單鏈表的比較B1課堂講授2.5線性表的其他存儲(chǔ)方式C1課堂講授2.6應(yīng)用舉例C1課堂講授3、特殊線性表?xiàng)?、?duì)列和串3.1棧A1課堂講授3.2隊(duì)列B1課堂講授3.3串B1課堂講授3.4應(yīng)用舉例C1課堂講授4、廣義線性4.1多維數(shù)組B1課堂講授表——多維數(shù)組和廣義表4.2矩陣的壓縮存儲(chǔ)B1課堂講授4.3廣義表B1課堂講授4.4應(yīng)用舉例C1課堂講授5、樹和二叉樹5.1樹的邏輯、存儲(chǔ)結(jié)構(gòu)B1課堂講授5.2二叉樹的邏輯結(jié)構(gòu)B1課堂講授5.3二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)A1課堂講授5.4應(yīng)用舉例C1課堂講授6、圖6.1圖的邏輯結(jié)構(gòu)B1課堂講授6.2圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)A1課堂講授6.3圖的連通性B1課堂講授6.4應(yīng)用舉例C1課堂講授7、查找技術(shù)7.1概述C1課堂講授7.2線性表的查找技術(shù)A1課堂講授7.3樹表的查找技術(shù)B1課堂講授7.4散列表的查找技術(shù)A課堂講授8、排序技術(shù)8.1插入排序A1課堂講授8.2交換排序B1課堂講授8.3選擇排序A1課堂講授8.4歸并排序C1課堂講授五、建議使用教材及參考書I、理論課教材：王紅梅，胡明，王濤等.數(shù)據(jù)結(jié)構(gòu)（C++版）[M].北京：清華大學(xué)出版社，2005.72、實(shí)驗(yàn)課教材：王紅梅，胡明，王濤等.數(shù)據(jù)結(jié)構(gòu)（C++版）學(xué)習(xí)輔導(dǎo)與實(shí)驗(yàn)指導(dǎo)[M].北京：清華大學(xué)出版社，2005.93、主要參考書：[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京清華大學(xué)出版社,1997[2]齊得昱.數(shù)據(jù)結(jié)構(gòu)與算法[M].北京：清華大學(xué)出版社，2003[3]辛運(yùn)幃，劉憬等.數(shù)據(jù)結(jié)構(gòu)與算法[M].北京：高等教育出版社,2006[4]傅清祥，王曉東.算法與數(shù)據(jù)結(jié)構(gòu)[M].北京：電子工業(yè)出版社，2001[5]陳慧南.數(shù)據(jù)結(jié)構(gòu)與算法一C++語(yǔ)言描述.[M].高等教育出版社，2005六、課程考核方式以閉卷考試為主，結(jié)合平時(shí)成績(jī)和上機(jī)實(shí)驗(yàn)報(bào)告評(píng)定成績(jī)。其中平時(shí)成績(jī)占10%(含作業(yè)和考勤)，上機(jī)實(shí)驗(yàn)報(bào)告占20%,期末筆試考試成績(jī)占70%。七、課內(nèi)實(shí)驗(yàn)環(huán)節(jié)及要求(16學(xué)時(shí))序號(hào)實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)?zāi)康募耙髮W(xué)時(shí)1基礎(chǔ)實(shí)驗(yàn)(1)在一維整型數(shù)組中順序查找與給定值相等的元素(2)在一個(gè)數(shù)組中確定第k小的元素(至少采用兩種方法求解)(1)比較順序查找最好、最壞和平均的時(shí)間性能(2)比較解決相同問(wèn)題的不同算法的時(shí)間性能22線性表實(shí)驗(yàn)(1)建立含有若干個(gè)元素的順序表(2)用頭插法(或尾插法)建立帶頭結(jié)點(diǎn)的單鏈表(3)對(duì)已建立的順序表、(1)掌握線性表的的順序及鏈接存儲(chǔ)結(jié)構(gòu)(2)驗(yàn)證順序表、單鏈表及其基本操作的實(shí)現(xiàn)(3)掌握數(shù)據(jù)結(jié)構(gòu)及算法的2單鏈表實(shí)現(xiàn)插入、刪除、查找等基本操作程序?qū)崿F(xiàn)的基本方法3特殊線性表——棧、隊(duì)列和串實(shí)驗(yàn)(1)建立一個(gè)空棧，對(duì)已建立的棧進(jìn)行插入、刪除、取棧頂元素等基本操作(2)建立一個(gè)空隊(duì)列，對(duì)已建立的隊(duì)列進(jìn)行插入、刪除、取隊(duì)頭元素等基本操作(3)創(chuàng)建兩個(gè)串，采用順序存儲(chǔ)，并實(shí)現(xiàn)串的插入、刪除、求子串等基本操作(1)掌握棧的順序存儲(chǔ)、隊(duì)列的鏈接存儲(chǔ)及串的順序存儲(chǔ)結(jié)構(gòu)(2)掌握棧、隊(duì)列、串的操作特性(3)掌握基于順序棧、鏈隊(duì)列及順序串的基本操作的實(shí)現(xiàn)方法24廣義線性表——多維數(shù)組和廣義表實(shí)驗(yàn)(1)建立一個(gè)n*n的對(duì)稱矩陣，并用一維數(shù)組存儲(chǔ)(2)采用頭尾表示法建立廣義表并求其深度(1)掌握對(duì)稱矩陣的壓縮存儲(chǔ)方法及尋址方法(2)掌握廣義表的邏輯結(jié)構(gòu)、頭尾表示法存儲(chǔ)結(jié)構(gòu)及其基本操作在頭尾表示法上的實(shí)現(xiàn)方法25樹和二叉樹實(shí)驗(yàn)(1)采用孩子兄弟表示法建立一棵樹，并實(shí)現(xiàn)樹的前序遍歷操作(2)建立一顆含有n個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲(chǔ)，前序(或中序、后序)遍歷該二叉樹(1)掌握樹的邏輯結(jié)構(gòu)及孩子兄弟存儲(chǔ)結(jié)構(gòu)(2)掌握基于樹的孩子兄弟存儲(chǔ)結(jié)構(gòu)的遍歷方法(3)掌握二叉樹的邏輯結(jié)構(gòu)及二叉鏈表存儲(chǔ)結(jié)構(gòu)(4)掌握基于二叉鏈表存儲(chǔ)的二叉樹的遍歷操作的實(shí)現(xiàn)26圖實(shí)驗(yàn)(1)建立一個(gè)無(wú)向圖的鄰接矩陣存儲(chǔ)，對(duì)其進(jìn)行深度優(yōu)先、廣度優(yōu)先遍歷(2)建立一個(gè)有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)，對(duì)其進(jìn)行深度優(yōu)先、廣度優(yōu)先遍歷(1)掌握?qǐng)D的邏輯結(jié)構(gòu)、鄰接矩陣存儲(chǔ)結(jié)構(gòu)及鄰接表存儲(chǔ)結(jié)構(gòu)(2)掌握?qǐng)D在鄰接矩陣存儲(chǔ)結(jié)構(gòu)下和鄰接表存儲(chǔ)結(jié)構(gòu)下遍歷算法的實(shí)現(xiàn)27查找技術(shù)試驗(yàn)(1)對(duì)給定的數(shù)組，利用順序查找算法，查找數(shù)組中與給定值相等的元素(2)對(duì)給定的一組無(wú)序序歹IJ,建立一顆二叉排序樹，并對(duì)建立的二叉排序樹實(shí)現(xiàn)查找操作(3)對(duì)給定的一組整數(shù)和散列函數(shù)，采用線性探測(cè)法處理沖突構(gòu)造散列表，并設(shè)計(jì)一個(gè)查找算法，驗(yàn)證查找性能(1)掌握順序查找算法、折半查找算法的基本思想、實(shí)現(xiàn)方法及時(shí)間性能(2)掌握二叉排序樹的定義、特性、建立方法及查找性能，并實(shí)現(xiàn)基于二叉排序