數(shù)據(jù)結(jié)構(gòu)東北大學(xué)

孟凡榮2009年3月數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)指導(dǎo)

1課程簡(jiǎn)介

2章節(jié)目錄

3數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)

4實(shí)驗(yàn)課題

5學(xué)習(xí)方法

6考試指導(dǎo)

1課程簡(jiǎn)介課程性質(zhì)專(zhuān)業(yè)技術(shù)基礎(chǔ)課先修課程離散數(shù)學(xué)、C/C++語(yǔ)言程序設(shè)計(jì)學(xué)時(shí)安排總學(xué)時(shí)64學(xué)時(shí)（含16學(xué)時(shí)實(shí)驗(yàn)）

1課程簡(jiǎn)介教學(xué)要求

從課程性質(zhì)上講，本課程是一門(mén)專(zhuān)業(yè)技術(shù)基礎(chǔ)課。其教學(xué)要求是：學(xué)會(huì)從問(wèn)題分析入手，研究數(shù)據(jù)在計(jì)算機(jī)中的數(shù)據(jù)結(jié)構(gòu)特性，為應(yīng)用所涉及到的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)機(jī)構(gòu)及其相應(yīng)的操作算法。1課程簡(jiǎn)介教學(xué)要求本課程的學(xué)習(xí)過(guò)程也是進(jìn)行復(fù)雜程序設(shè)計(jì)的訓(xùn)練過(guò)程，要求初步掌握基本的算法設(shè)計(jì)技術(shù)，以及算法的時(shí)間和空間性能的分析方法，會(huì)書(shū)寫(xiě)符合軟件工程規(guī)范的程序文檔，為今后的計(jì)算機(jī)軟件程序開(kāi)發(fā)奠定良好的基礎(chǔ)。1課程簡(jiǎn)介教學(xué)要求本課程是一門(mén)實(shí)踐性很強(qiáng)的課程，因此在學(xué)習(xí)過(guò)程中，除了掌握課程的基本知識(shí)內(nèi)容之外，還應(yīng)上機(jī)完成實(shí)驗(yàn)課題和做好課后習(xí)題。上機(jī)前，必須對(duì)課程內(nèi)容做到真正的消化和理解，特別是對(duì)于算法的學(xué)習(xí)，應(yīng)掌握它們的設(shè)計(jì)思想、編寫(xiě)程序并能上機(jī)正確調(diào)試運(yùn)行。

1課程簡(jiǎn)介課程內(nèi)容本課程分為四個(gè)知識(shí)單元，共7章18課。第1單元，數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)；第2單元，常用數(shù)據(jù)結(jié)構(gòu)；第3單元，數(shù)據(jù)結(jié)構(gòu)及算法應(yīng)用；第4單元，數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)。2章節(jié)目錄第1章數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)第2章基本數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列第4章樹(shù)和圖第5章查找表和文件第6章數(shù)據(jù)結(jié)構(gòu)及算法應(yīng)用2章節(jié)目錄第1課數(shù)據(jù)結(jié)構(gòu)基本概念

1數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象

2數(shù)據(jù)結(jié)構(gòu)的定義及分類(lèi)3數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型4數(shù)據(jù)結(jié)構(gòu)的描述與實(shí)現(xiàn)2章節(jié)目錄第2課算法基礎(chǔ)

1算法的概念

2算法的描述3算法分析基礎(chǔ)

4算法設(shè)計(jì)基礎(chǔ)2章節(jié)目錄第3課順序表

1順序表的存儲(chǔ)結(jié)構(gòu)

2順序表的基本操作3有序順序表4順序表的簡(jiǎn)單應(yīng)用2章節(jié)目錄第4課線(xiàn)性鏈表

1鏈表的存儲(chǔ)結(jié)構(gòu)

2鏈表的基本操作

3有序鏈表

4鏈表的簡(jiǎn)單應(yīng)用2章節(jié)目錄第5課字符串

1串的邏輯結(jié)構(gòu)

2串的順序存儲(chǔ)結(jié)構(gòu)

3串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

4串的模式匹配

2章節(jié)目錄第6課數(shù)組

1數(shù)組的邏輯結(jié)構(gòu)

2數(shù)組的存儲(chǔ)結(jié)構(gòu)

3特殊矩陣的存儲(chǔ)

2章節(jié)目錄第7課棧

1棧的邏輯結(jié)構(gòu)

2順序棧

3鏈棧

4棧的簡(jiǎn)單應(yīng)用2章節(jié)目錄第8課隊(duì)列

1隊(duì)列的邏輯結(jié)構(gòu)

2鏈隊(duì)列

3循環(huán)隊(duì)列

4隊(duì)列的簡(jiǎn)單應(yīng)用2章節(jié)目錄第9課二叉樹(shù)

1樹(shù)和二叉樹(shù)的邏輯結(jié)構(gòu)

2二叉樹(shù)的性質(zhì)3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)4二叉樹(shù)的遍歷

2章節(jié)目錄第10課樹(shù)和森林

1樹(shù)的存儲(chǔ)結(jié)構(gòu)2樹(shù)、森林與二叉樹(shù)3樹(shù)和森林的遍歷

2章節(jié)目錄第11課圖

1圖的邏輯結(jié)構(gòu)

2圖的存儲(chǔ)結(jié)構(gòu)3圖的遍歷

2章節(jié)目錄第12課查找表

1查找表的概念

2靜態(tài)查找表3二叉排序樹(shù)

4散列（Hash）表

2章節(jié)目錄第13課文件

1文件的概念

2索引文件3散列文件

2章節(jié)目錄第14課排序1排序的基本概念2插入排序5歸并排序3快速排序6多關(guān)鍵字排序4堆排序7外部排序

2章節(jié)目錄第15課線(xiàn)性結(jié)構(gòu)應(yīng)用

1約瑟夫環(huán)

2靜態(tài)鏈表應(yīng)用

3三元組求解稀疏矩陣

4實(shí)用型線(xiàn)性鏈表5一元多項(xiàng)式運(yùn)算

2章節(jié)目錄第15課線(xiàn)性結(jié)構(gòu)應(yīng)用

6棧與遞歸7簡(jiǎn)單背包問(wèn)題8地圖著色問(wèn)題

9共享?xiàng)?0子集劃分2章節(jié)目錄第16課樹(shù)形結(jié)構(gòu)應(yīng)用

1全線(xiàn)索鏈表

2表達(dá)式求值3哈夫曼樹(shù)

4等價(jià)類(lèi)劃分5樹(shù)的形態(tài)

2章節(jié)目錄第17課圖形結(jié)構(gòu)應(yīng)用

1迷宮問(wèn)題

2無(wú)向圖的連通性應(yīng)用

3有向無(wú)環(huán)圖應(yīng)用

4最短路徑問(wèn)題

2章節(jié)目錄第18課數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)

1問(wèn)題求解策略

2

0-1背包問(wèn)題3數(shù)據(jù)結(jié)構(gòu)程序?qū)崿F(xiàn)4數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)實(shí)例3數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)實(shí)驗(yàn)教學(xué)要求數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專(zhuān)業(yè)的核心課程。通過(guò)本課程的實(shí)驗(yàn)，使學(xué)生加深對(duì)課程內(nèi)容的理解，培養(yǎng)將原理應(yīng)用于實(shí)際的能力，提高軟件編程設(shè)計(jì)及算法應(yīng)用的綜合素質(zhì)。本課程實(shí)驗(yàn)要求所編寫(xiě)的程序能夠正常運(yùn)行，并提交實(shí)驗(yàn)報(bào)告。3數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告內(nèi)容（1）實(shí)驗(yàn)?zāi)康恼f(shuō)明課題的目的和任務(wù)。應(yīng)包括對(duì)問(wèn)題的需求分析，具體有數(shù)據(jù)的輸入的形式和輸入值的范圍；數(shù)據(jù)輸出的形式；程序的功能等。3數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告內(nèi)容（2）實(shí)驗(yàn)原理包括課題的程序中所用到的抽象數(shù)據(jù)類(lèi)型的定義、主程序的流程以及各程序模塊之間的調(diào)用關(guān)系。3數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告內(nèi)容（3）實(shí)驗(yàn)步驟實(shí)現(xiàn)課題設(shè)計(jì)中定義的所有數(shù)據(jù)類(lèi)型及存儲(chǔ)結(jié)構(gòu)；對(duì)每個(gè)模塊及操作寫(xiě)出偽碼算法。3數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)實(shí)驗(yàn)步驟啟動(dòng)編程環(huán)境定義存儲(chǔ)結(jié)構(gòu)定義基本操作設(shè)計(jì)基本操作算法編寫(xiě)源代碼設(shè)計(jì)主算法和主程序調(diào)試源程序

3數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)源程序調(diào)試全局變量及包含頭文件存儲(chǔ)結(jié)構(gòu)定義結(jié)構(gòu)創(chuàng)建及銷(xiāo)毀操作屬性操作查找操作更新操作主程序

3數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告內(nèi)容（4）程序運(yùn)行及結(jié)果分析列出包括輸入和輸出的測(cè)試結(jié)果；對(duì)程序調(diào)試中所遇問(wèn)題的解決方法及分析；算法的時(shí)空分析及改進(jìn)設(shè)想；經(jīng)驗(yàn)和體會(huì)。3數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告內(nèi)容（5）實(shí)驗(yàn)文檔必要的程序使用說(shuō)明及帶注釋的源程序及調(diào)試文件的電子版。4實(shí)驗(yàn)課題實(shí)驗(yàn)1順序表基本操作及應(yīng)用實(shí)現(xiàn)順序表的基本操作，包括順序表的創(chuàng)建、查找、求長(zhǎng)度、插入、刪除、遍歷等函數(shù)。應(yīng)用參考題目

1.1學(xué)生成績(jī)統(tǒng)計(jì)

1.2有序表求并

1.3字典維護(hù)

4實(shí)驗(yàn)課題實(shí)驗(yàn)2單鏈表基本操作及應(yīng)用實(shí)現(xiàn)單鏈表的基本操作，包括順序表的創(chuàng)建、查找、求長(zhǎng)度、插入、刪除、遍歷等函數(shù)。應(yīng)用參考題目

2.1約瑟夫環(huán)

2.2一元多項(xiàng)式相加

2.3商品維護(hù)4實(shí)驗(yàn)課題實(shí)驗(yàn)3順序棧基本操作及應(yīng)用實(shí)現(xiàn)棧的基本操作，包括棧的創(chuàng)建、銷(xiāo)毀、出棧、入棧、取棧頂元素、判棧空等函數(shù)。應(yīng)用參考題目

3.1數(shù)制轉(zhuǎn)換

3.2算術(shù)表達(dá)式求值

3.3停車(chē)場(chǎng)管理4實(shí)驗(yàn)課題實(shí)驗(yàn)4隊(duì)列基本操作及應(yīng)用實(shí)現(xiàn)隊(duì)列的基本操作，包括隊(duì)列的創(chuàng)建、銷(xiāo)毀、出隊(duì)、入隊(duì)、取對(duì)頭元素、判隊(duì)列空等函數(shù)。應(yīng)用參考題目

4.1存儲(chǔ)緩沖區(qū)問(wèn)題

4.2迷宮最短路徑問(wèn)題

4.3楊輝三角形

4實(shí)驗(yàn)課題實(shí)驗(yàn)5二叉樹(shù)基本操作及應(yīng)用實(shí)現(xiàn)二叉樹(shù)的初始化、創(chuàng)建、查找、遍歷、插入、刪除和判空樹(shù)等基本操作。應(yīng)用參考題目

5.1哈夫曼編碼

5.2表達(dá)式求值

5.3因特網(wǎng)查詢(xún)4實(shí)驗(yàn)課題實(shí)驗(yàn)6圖的基本操作及應(yīng)用實(shí)現(xiàn)圖結(jié)構(gòu)的初始化、創(chuàng)建、查找、遍歷、插入、刪除等基本操作。應(yīng)用參考題目

6.1無(wú)向圖的關(guān)節(jié)點(diǎn)問(wèn)題

6.2最小生成樹(shù)

6.3迷宮問(wèn)題4實(shí)驗(yàn)課題實(shí)驗(yàn)7查找表基本操作實(shí)現(xiàn)實(shí)現(xiàn)靜態(tài)查找表、二叉排序樹(shù)及哈希表的基本操作。應(yīng)用參考題目

7.1分塊查找應(yīng)用

7.2二叉排序樹(shù)應(yīng)用

7.3哈希表應(yīng)用4實(shí)驗(yàn)課題實(shí)驗(yàn)8排序算法實(shí)現(xiàn)實(shí)現(xiàn)希爾排序、快速排序、堆排序、二路歸并排序和基數(shù)排序的基本操作。應(yīng)用參考題目

8.1排序算法應(yīng)用

8.2排序算法比較

8.3計(jì)數(shù)式基數(shù)排序4實(shí)驗(yàn)課題實(shí)驗(yàn)9數(shù)據(jù)結(jié)構(gòu)綜合應(yīng)用實(shí)現(xiàn)類(lèi)似迷宮問(wèn)題、銀行排隊(duì)問(wèn)題等綜合應(yīng)用算法。應(yīng)用參考題目

9.1背包問(wèn)題

9.2表達(dá)式求值

9.3智能搜索5學(xué)習(xí)方法預(yù)備知識(shí)課程內(nèi)容體系存儲(chǔ)結(jié)構(gòu)與基本操作循序漸進(jìn)實(shí)驗(yàn)?zāi)芰Φ湫蛻?yīng)用算法綜合應(yīng)用5學(xué)習(xí)方法預(yù)備知識(shí)

C與C++

Turbo3.0C/C++VisualC++5學(xué)習(xí)方法預(yù)備知識(shí)-引用參數(shù)&問(wèn)題

C++語(yǔ)言的引用調(diào)用的參數(shù)傳遞方式。在形參表中，以&打頭的參數(shù)即為引用參數(shù)。

標(biāo)準(zhǔn)C不支持引用參數(shù)，對(duì)此需進(jìn)行轉(zhuǎn)換。5學(xué)習(xí)方法預(yù)備知識(shí)-引用參數(shù)&問(wèn)題含有引用參數(shù)的函數(shù)如下：

Status

DestroyTriplet(Triplet&T)

{//操作結(jié)果：三元組T被銷(xiāo)毀

free(T);

T=NULL;

returnOK;

}5學(xué)習(xí)方法預(yù)備知識(shí)-引用參數(shù)&問(wèn)題轉(zhuǎn)換后的標(biāo)準(zhǔn)C程序如下：StatusDestroyTriplet(Triplet*T)

//將&T改為*T

{//操作結(jié)果：三元組T被銷(xiāo)毀

free(*T);//將T改為*T

*T=NULL;//將T改為*T

returnOK;

}5學(xué)習(xí)方法預(yù)備知識(shí)-引用參數(shù)&問(wèn)題另外，如果調(diào)用該函數(shù)，實(shí)參前應(yīng)加&。如調(diào)用DestroyTriplet()的語(yǔ)句為：

DestroyTriplet(T);

相應(yīng)的標(biāo)準(zhǔn)C程序調(diào)用語(yǔ)句為：

DestroyTriplet(&T);5學(xué)習(xí)方法預(yù)備知識(shí)-引用參數(shù)&問(wèn)題在調(diào)用DestroyTriplet()的兩程序中，兩實(shí)參T的類(lèi)型是相同的。在轉(zhuǎn)換過(guò)程中，遇到&*或*&可“抵消”，即將*&T轉(zhuǎn)換為T(mén)。5學(xué)習(xí)方法預(yù)備知識(shí)-typedef類(lèi)型定義只要在定義結(jié)構(gòu)體時(shí)使用typedef，則在指明結(jié)構(gòu)體的類(lèi)型時(shí)就不必加struct。如：

StatusClearList(SqList&L)5學(xué)習(xí)方法預(yù)備知識(shí)-變量定義問(wèn)題

C++允許在執(zhí)行語(yǔ)句中變量使用之前定義變量。而標(biāo)準(zhǔn)C語(yǔ)言是不允許的。如：

voidPrintUser(Spacep[])

{

//輸出p數(shù)組所指的已分配空間

for(inti=0;i<MAX;i++)……5學(xué)習(xí)方法預(yù)備知識(shí)-動(dòng)態(tài)申請(qǐng)空間問(wèn)題

在C++中可用new申請(qǐng)空間，如一條語(yǔ)句如下：

p=new

Chunk;在標(biāo)準(zhǔn)C中要改為：

p=(Chunk*)malloc(sizeof(Chunk));5學(xué)習(xí)方法預(yù)備知識(shí)-輸入輸出語(yǔ)句在C++中可用cout<<T[0]<<''<<T[1]<<''<<T[2]

<<endl;

好處是不必給出格式符。這樣，當(dāng)變量的類(lèi)型發(fā)生變化時(shí)，不必修改語(yǔ)句。5學(xué)習(xí)方法預(yù)備知識(shí)-輸入輸出語(yǔ)句但在標(biāo)準(zhǔn)C中必須改為：

printf(“%d%d%d\n”,T[0],T[1],T[2]);//當(dāng)ElemType的類(lèi)型變化時(shí)，要

//相應(yīng)改變printf()的格式符5學(xué)習(xí)方法課程內(nèi)容體系（1）數(shù)據(jù)結(jié)構(gòu)定義邏輯結(jié)構(gòu)-存儲(chǔ)結(jié)構(gòu)-基本操作（2）數(shù)據(jù)結(jié)構(gòu)應(yīng)用基本結(jié)構(gòu)-常用結(jié)構(gòu)-復(fù)雜結(jié)構(gòu)（3）數(shù)據(jù)結(jié)構(gòu)算法應(yīng)用線(xiàn)形結(jié)構(gòu)-樹(shù)形結(jié)構(gòu)-圖形結(jié)構(gòu)5學(xué)習(xí)方法存儲(chǔ)結(jié)構(gòu)與基本操作

順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)索引存儲(chǔ)散列存儲(chǔ)結(jié)構(gòu)創(chuàng)建及銷(xiāo)毀屬性操作查找操作更新操作5學(xué)習(xí)方法循序漸進(jìn)

簡(jiǎn)單數(shù)組-順序表-單鏈表-字符串-二叉樹(shù)-圖簡(jiǎn)單基本操作-復(fù)雜基本操作簡(jiǎn)單應(yīng)用-高級(jí)應(yīng)用-綜合應(yīng)用5學(xué)習(xí)方法實(shí)驗(yàn)?zāi)芰?/p>

基本操作實(shí)現(xiàn)簡(jiǎn)單應(yīng)用實(shí)現(xiàn)簡(jiǎn)單綜合應(yīng)用實(shí)現(xiàn)復(fù)雜綜合應(yīng)用實(shí)現(xiàn)

5學(xué)習(xí)方法典型應(yīng)用算法一元多項(xiàng)式表達(dá)式求值哈夫曼樹(shù)最小生成樹(shù)拓?fù)渑判?/p>

……5學(xué)習(xí)方法綜合應(yīng)用

迷宮問(wèn)題背包問(wèn)題排隊(duì)時(shí)間模擬工程關(guān)鍵路徑局部與全局最優(yōu)問(wèn)題

……6考試指導(dǎo)考試題型

單選題填空題算法應(yīng)用題算法分析題算法設(shè)計(jì)題

6考試指導(dǎo)單選題在一個(gè)單鏈表中，已知*q結(jié)點(diǎn)是*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在*q和*p之間插入結(jié)點(diǎn)*s，則執(zhí)行操作A.s->next=p->next;p->next=s;B.s->next=p;p->next=sC.q->next=s;s->next=p;D.p->next=s;s->next=q;6考試指導(dǎo)單選題假設(shè)一個(gè)棧的輸入序列為A，B，C，D，則借助一個(gè)棧所得到的輸出序列不可能是A．A，B，C，D

B．D，C，B，AC.A，C，D，B

D.D，A，B，C6考試指導(dǎo)單選題在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后引起了不平衡，設(shè)最低(最接近于葉子)的不平衡點(diǎn)是A，并已知A的左、右孩子的平衡因子分別為-1和0，則應(yīng)進(jìn)行的平衡旋轉(zhuǎn)是A．LL型

B．LR型

C．RL型

D．RR型6考試指導(dǎo)單選題有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中

A.第i行1的元素之和

B.第i列1的元素之和

C.第i行0的元素個(gè)數(shù)

D.第i列非0的元素個(gè)數(shù)6考試指導(dǎo)單選題在分塊索引查找的順序表中查找，算法中采用的技術(shù)是

A.窮舉法

B.貪心法

C.分治法

D.回溯法

6考試指導(dǎo)填空題數(shù)據(jù)的邏輯結(jié)構(gòu)包括線(xiàn)性