“數(shù)據(jù)結(jié)構(gòu)”是信息管理與信息系統(tǒng)專業(yè)一門重點(diǎn)專業(yè)基礎(chǔ)課程，也是學(xué)科專業(yè)核心專業(yè)基礎(chǔ)課程之一，屬于專業(yè)學(xué)位必修課程。本課程的教學(xué)任務(wù)是針對(duì)大量的信息處理對(duì)象，介紹對(duì)象信息與數(shù)據(jù)表示的各種抽象的、基本的邏輯結(jié)構(gòu)及其上的基本運(yùn)算操作。通過研究各種基本數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系和它們?cè)谟?jì)算機(jī)中的存儲(chǔ)表示方式，初步建立數(shù)據(jù)結(jié)構(gòu)上基本運(yùn)算操作的正確性概念，同時(shí)，結(jié)合各種典型問題討論其上的各種基本運(yùn)算操作及其基本算法，講授各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、適用范圍，以及對(duì)一些基本算法效率的定性和定量分析方法，為后續(xù)課程提供必要的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)。

《數(shù)據(jù)結(jié)構(gòu)A》在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課，不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)、編譯程序及其它系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。

課程教學(xué)內(nèi)容與基本要求

（一）緒論（ 3 學(xué)時(shí)）

1．主要內(nèi)容： （1）介紹什么是數(shù)據(jù)結(jié)構(gòu)； （2）基本概念和術(shù)語 : 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象，以及數(shù)據(jù)結(jié)構(gòu)的定義、邏輯結(jié)構(gòu)、 物理結(jié)構(gòu)（理解）數(shù)據(jù)類型、抽象數(shù)據(jù)類型； （3）抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)； （4）算法和算法分析 : 算法的概念、算法設(shè)計(jì)的要求以及算法效率的度量。 2．基本要求 （1）了解學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性； （2）掌握數(shù)據(jù)結(jié)構(gòu)的定義及相關(guān)概念和術(shù)語； （3）了解抽象數(shù)據(jù)類型的定義、表示與實(shí)現(xiàn)方法； （4）理解算法的概念、特點(diǎn)并掌握度量其效率的基本方法。 3．自學(xué)內(nèi)容： 類 C語言的書寫規(guī)范。

（二）線性表（ 6 學(xué)時(shí)）

1．主要內(nèi)容： （1）線性表的抽象數(shù)據(jù)類型定義和相關(guān)概念：數(shù)據(jù)項(xiàng)、記錄、文件等； （2）線性表順序存儲(chǔ)表示和基本操作的實(shí)現(xiàn)； （3）線性表的鏈?zhǔn)酱鎯?chǔ)表示和基本操作的實(shí)現(xiàn)； （4）稀疏多項(xiàng)式的抽象數(shù)據(jù)類型定義、表示和加法的實(shí)現(xiàn)。

2．基本要求 （1）掌握線性表的定義和特點(diǎn)； （2）熟練掌握線性表的順序存儲(chǔ)表示和插入、刪除、查找等實(shí)現(xiàn)算法； （3）熟練掌握單鏈表、循環(huán)鏈表、雙向鏈表三種鏈表的表示，以及單鏈表的查找、插 入、刪除、創(chuàng)建等實(shí)現(xiàn)算法。 3．自學(xué)內(nèi)容： 靜態(tài)鏈表。

（三）棧和隊(duì)列（ 5 學(xué)時(shí)）

1．主要內(nèi)容： （1）棧和隊(duì)列的結(jié)構(gòu)特性和抽象數(shù)據(jù)類型定義； （2）棧和隊(duì)列的順序存儲(chǔ)表示和實(shí)現(xiàn)； （3）棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示和實(shí)現(xiàn)； （4）棧和隊(duì)列在程序設(shè)計(jì)中的應(yīng)用。 2．基本要求 （1）掌握棧和隊(duì)列兩種抽象數(shù)據(jù)類型的特點(diǎn)； （2）掌握棧的兩種存儲(chǔ)表示和實(shí)現(xiàn)，特別注意棧滿棧空的條件； （3）掌握隊(duì)列的兩種存儲(chǔ)表示和實(shí)現(xiàn)，特別注意隊(duì)滿隊(duì)空的條件； （4）了解遞歸算法與棧的關(guān)系。 3．自學(xué)內(nèi)容： 鏈棧，離散事件模擬

（四）串（ 3 學(xué)時(shí)）

1．主要內(nèi)容： （1）串的抽象數(shù)據(jù)類型定義； （2）串的表示和實(shí)現(xiàn) : 定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)和堆分配存儲(chǔ)結(jié)構(gòu)； （3）串的各種基本操作的實(shí)現(xiàn)及其應(yīng)用； （4）串的模式匹配操作。 2．基本要求 （1）熟悉串的一些基本操作的定義，并能利用基本操作實(shí)現(xiàn)串的其它操作； （2）掌握串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)以及基本操作的實(shí)現(xiàn)； （3）掌握串的堆分配存儲(chǔ)結(jié)構(gòu)以及基本操作的實(shí)現(xiàn)； （4）掌握串的簡(jiǎn)單模式匹配算法，理解 KMP 算法。 3．自學(xué)內(nèi)容： 串操作的應(yīng)用實(shí)例。

（五）數(shù)組和廣義表（ 4 學(xué)時(shí)）

1．主要內(nèi)容： （1）數(shù)組的抽象數(shù)據(jù)類型定義及其順序表示和實(shí)現(xiàn)； （2）特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)； （3）廣義表的抽象數(shù)據(jù)類型定義和存儲(chǔ)結(jié)構(gòu)。 2．基本要求 （1）了解數(shù)組的兩種存儲(chǔ)表示方法，并掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算 方法；

（2）掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式； （3）熟悉稀疏矩陣的三元組順序表存儲(chǔ)結(jié)構(gòu)下的一般轉(zhuǎn)置和快速轉(zhuǎn)置算法；了解十字 鏈表等存儲(chǔ)結(jié)構(gòu)； （4）掌握廣義表的結(jié)構(gòu)特點(diǎn)、取表頭表尾操作，及其存儲(chǔ)表示方法。 3．自學(xué)內(nèi)容： 采用十字鏈表存儲(chǔ)結(jié)構(gòu)創(chuàng)建稀疏矩陣。

（六）樹和二叉樹（ 10 學(xué)時(shí)）

1．主要內(nèi)容： （1）樹的抽象數(shù)據(jù)類型定義和基本術(shù)語； （2）二叉樹的抽象數(shù)據(jù)類型定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)； （3）二叉樹的遍歷； （4）線索二叉樹的定義、遍歷及線索化二叉樹； （5）樹的存儲(chǔ)結(jié)構(gòu)、樹和森林的遍歷以及與二叉樹的轉(zhuǎn)換； （6）Huffman 樹及其應(yīng)用。 2．基本要求 （1）掌握樹型結(jié)構(gòu)的特點(diǎn)和基本術(shù)語； （2）熟練掌握二叉樹的性質(zhì)，了解相應(yīng)的證明方法； （3）了解二叉樹的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，熟練掌握二叉鏈表存儲(chǔ)結(jié)構(gòu)； （4）熟練掌握二叉樹三種遍歷的遞歸算法和中序遍歷非遞歸算法，能靈活運(yùn)用遍歷算 法實(shí)現(xiàn)二叉樹的其他操作； （5）熟練掌握二叉樹的線索化過程，以及在中序線索二叉樹上找結(jié)點(diǎn)的前驅(qū)與后繼的 方法； （6）熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹和森林與二叉樹的轉(zhuǎn)換方法； （7）了解 Huffman 樹的特性，掌握建立 Huffman 樹和 Huffman 編碼的方法。 3．自學(xué)內(nèi)容： 先序、后序遍歷二叉樹非遞歸算法，層次遍歷二叉樹算法。

（七）圖（ 9 學(xué)時(shí)）

1．主要內(nèi)容： （1）圖的定義和術(shù)語； （2）圖的四種存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法（鄰接矩陣） 、鄰接表、十字鏈表和鄰接多重表； （3）圖的兩種遍歷策略：深度優(yōu)先遍歷和廣度優(yōu)先遍歷； （4）圖的連通性和最小生成樹； （5）有向無環(huán)圖及其應(yīng)用：拓?fù)渑判蚝完P(guān)鍵路徑； （6）最短路徑問題。 2．基本要求 （1）熟悉圖的定義和術(shù)語； （2）了解圖的存儲(chǔ)結(jié)構(gòu)，熟練掌握數(shù)組表示法（鄰接矩陣）和鄰接表存儲(chǔ)表示； （3）熟練掌握?qǐng)D的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法； （4）掌握無向連通帶權(quán)圖的最小生成樹求解算法； （5）了解有向無環(huán)圖、 AOV網(wǎng)、 AOE網(wǎng)及其在實(shí)際中的應(yīng)用，熟悉拓?fù)渑判蛩惴ê完P(guān) 鍵路徑算法； （6）熟悉兩種最短路徑問題求解算法。