課程簡介
Course Introduction
《數(shù)據(jù)結(jié)構(gòu)與算法》是軟件工程、計(jì)算機(jī)及相關(guān)專業(yè)重要的專業(yè)基礎(chǔ)課程。作為軟件工程專業(yè)的核心課程，本課程所討論的知識(shí)內(nèi)容和提倡的技術(shù)方法，無論對(duì)進(jìn)一步學(xué)習(xí)計(jì)算機(jī)領(lǐng)域的其他課程，還是對(duì)從事軟件系統(tǒng)的開發(fā)，都有著不可替代的作用，本課程不僅為《數(shù)據(jù)庫系統(tǒng)原理與實(shí)踐》、《操作系統(tǒng)》、《算法分析與設(shè)計(jì)》、《軟件構(gòu)造》、《計(jì)算機(jī)網(wǎng)絡(luò)》等后繼課程提供必要的知識(shí)基礎(chǔ)，同時(shí)也為理論研究與工程應(yīng)用的專業(yè)人員提供必要的技能訓(xùn)練。通過本課程的學(xué)習(xí)，完成知識(shí)學(xué)習(xí)和技能培養(yǎng)兩方面的任務(wù):
1. 知識(shí)方面:從數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)的角度，系統(tǒng)地學(xué)習(xí)和掌握基本數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)方法，理解并掌握分析、選擇和設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及算法的基本原則和方法，為后繼課程的學(xué)習(xí)打下良好的知識(shí)基礎(chǔ)。
2. 技能方面:通過對(duì)本課程的知識(shí)傳授、算法設(shè)計(jì)和上機(jī)實(shí)踐的訓(xùn)練，培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力、算法抽象能力和計(jì)算思維能力，提高分析問題和解決問題的能力，提高運(yùn)用程序設(shè)計(jì)語言解決實(shí)際問題的能力，進(jìn)而提高學(xué)生設(shè)計(jì)高質(zhì)量軟件的能力。
教學(xué)大綱
Teaching Syllabus
第一章 緒論（3學(xué)時(shí)）
教學(xué)內(nèi)容:問題求解與程序設(shè)計(jì)；數(shù)據(jù)結(jié)構(gòu)的基本概念；算法的基本概念；算法分析。
選講內(nèi)容:算法分析的其他漸進(jìn)符號(hào)。
第二章 線性表（6學(xué)時(shí)）
教學(xué)內(nèi)容:線性表的邏輯結(jié)構(gòu)；線性表順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)；線性表鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)；順序表和鏈表的比較。
選講內(nèi)容:線性表的靜態(tài)鏈表存儲(chǔ)；順序表的動(dòng)態(tài)存儲(chǔ)分配。
第三章 棧和隊(duì)列（4學(xué)時(shí)）
教學(xué)內(nèi)容:棧的邏輯結(jié)構(gòu)；棧的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)；隊(duì)列的邏輯結(jié)構(gòu)；隊(duì)列的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)。
選講內(nèi)容:兩棧共享空間；雙端隊(duì)列。
第四章 字符串和多維數(shù)組（4學(xué)時(shí)）
教學(xué)內(nèi)容:字符串的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，模式匹配算法；數(shù)組的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及尋址；特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)方法。
選講內(nèi)容:稀疏矩陣的轉(zhuǎn)置算法；廣義表。
第五章 樹和二叉樹（9學(xué)時(shí)）
教學(xué)內(nèi)容:樹的邏輯結(jié)構(gòu)；樹的存儲(chǔ)結(jié)構(gòu)；二叉樹的邏輯結(jié)構(gòu)；二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)；樹、森林和二叉樹之間的轉(zhuǎn)換；哈夫曼樹及哈夫曼編碼。
選講內(nèi)容:二叉樹遍歷的非遞歸實(shí)現(xiàn)；線索二叉樹，堆與優(yōu)先隊(duì)列；并查集。
第六章 圖（9學(xué)時(shí)）
教學(xué)內(nèi)容:圖的邏輯結(jié)構(gòu)；圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)；最小生成樹；最短路徑；有向無環(huán)圖。
選講內(nèi)容:圖的其他存儲(chǔ)方法；圖的連通性。
第七章 查找技術(shù)（5學(xué)時(shí)）
教學(xué)內(nèi)容:查找的基本概念及算法性能；線性表的查找技術(shù)；樹表的查找技術(shù)；散列表的查找技術(shù)；各種查找方法的比較。
選講內(nèi)容:分塊查找；插值查找；B+樹。
第八章 排序技術(shù)（8學(xué)時(shí)）
教學(xué)內(nèi)容:排序的基本概念及算法性能；插入排序；交換排序；選擇排序；歸并排序；各種排序算法的比較。
選講內(nèi)容:排序問題的時(shí)間下界；基數(shù)排序。
教學(xué)隊(duì)伍Teaching Members
友情鏈接Links
相關(guān)課程Correlative
Courses
