數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)指導(dǎo)

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

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

1課程簡介

2章節(jié)目錄

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

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

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

6考試指導(dǎo)

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

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

從課程性質(zhì)上講，本課程是一門專業(yè)技術(shù)基礎(chǔ)課。其教學(xué)要求是：學(xué)會(huì)從問題分析入手，研究數(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課程簡介教學(xué)要求本課程的學(xué)習(xí)過程也是進(jìn)行復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程，要求初步掌握基本的算法設(shè)計(jì)技術(shù)，以及算法的時(shí)間和空間性能的分析方法，會(huì)書寫符合軟件工程規(guī)范的程序文檔，為今后的計(jì)算機(jī)軟件程序開發(fā)奠定良好的基礎(chǔ)。1課程簡介教學(xué)要求本課程是一門實(shí)踐性很強(qiáng)的課程，因此在學(xué)習(xí)過程中，除了掌握課程的基本知識內(nèi)容之外，還應(yīng)上機(jī)完成實(shí)驗(yàn)課題和做好課后習(xí)題。上機(jī)前，必須對課程內(nèi)容做到真正的消化和理解，特別是對于算法的學(xué)習(xí)，應(yīng)掌握它們的設(shè)計(jì)思想、編寫程序并能上機(jī)正確調(diào)試運(yùn)行。

1課程簡介課程內(nèi)容本課程分為四個(gè)知識單元，共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章樹和圖第5章查找表和文件第6章數(shù)據(jù)結(jié)構(gòu)及算法應(yīng)用2章節(jié)目錄第1課數(shù)據(jù)結(jié)構(gòu)基本概念

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

2數(shù)據(jù)結(jié)構(gòu)的定義及分類3數(shù)據(jù)類型和抽象數(shù)據(jù)類型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順序表的簡單應(yīng)用2章節(jié)目錄第4課線性鏈表

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

2鏈表的基本操作

3有序鏈表

4鏈表的簡單應(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棧的簡單應(yīng)用2章節(jié)目錄第8課隊(duì)列

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

2鏈隊(duì)列

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

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

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

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

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

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

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

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

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

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

1查找表的概念

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

4散列（Hash）表

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

1文件的概念

2索引文件3散列文件

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

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

1約瑟夫環(huán)

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

3三元組求解稀疏矩陣

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

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

6棧與遞歸7簡單背包問題8地圖著色問題

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

1全線索鏈表

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

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

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

1迷宮問題

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

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

4最短路徑問題

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

1問題求解策略

2

0-1背包問題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ī)專業(yè)的核心課程。通過本課程的實(shí)驗(yàn)，使學(xué)生加深對課程內(nèi)容的理解，培養(yǎng)將原理應(yīng)用于實(shí)際的能力，提高軟件編程設(shè)計(jì)及算法應(yīng)用的綜合素質(zhì)。本課程實(shí)驗(yàn)要求所編寫的程序能夠正常運(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明課題的目的和任務(wù)。應(yīng)包括對問題的需求分析，具體有數(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ù)類型的定義、主程序的流程以及各程序模塊之間的調(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ù)類型及存儲(chǔ)結(jié)構(gòu)；對每個(gè)模塊及操作寫出偽碼算法。3數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)實(shí)驗(yàn)步驟啟動(dòng)編程環(huán)境定義存儲(chǔ)結(jié)構(gòu)定義基本操作設(shè)計(jì)基本操作算法編寫源代碼設(shè)計(jì)主算法和主程序調(diào)試源程序

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

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

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

1.2有序表求并

1.3字典維護(hù)

4實(shí)驗(yàn)課題實(shí)驗(yàn)2單鏈表基本操作及應(yīng)用實(shí)現(xiàn)單鏈表的基本操作，包括順序表的創(chuà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)建、銷毀、出棧、入棧、取棧頂元素、判?？盏群瘮?shù)。應(yīng)用參考題目

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

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

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

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

4.2迷宮最短路徑問題

4.3楊輝三角形

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

5.1哈夫曼編碼

5.2表達(dá)式求值

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

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

6.2最小生成樹

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

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

7.2二叉排序樹應(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)類似迷宮問題、銀行排隊(duì)問題等綜合應(yīng)用算法。應(yīng)用參考題目

9.1背包問題

9.2表達(dá)式求值

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

C與C++

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

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

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

Status

DestroyTriplet(Triplet&T)

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

free(T);

T=NULL;

returnOK;

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

//將&T改為*T

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

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

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

returnOK;

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

DestroyTriplet(T);

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

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

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

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

voidPrintUser(Spacep[])

{

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

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

在C++中可用new申請空間，如一條語句如下：

p=new

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

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

<<endl;

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

printf(“%d%d%d\n”,T[0],T[1],T[2]);//當(dāng)ElemType的類型變化時(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)用線形結(jié)構(gòu)-樹形結(jié)構(gòu)-圖形結(jié)構(gòu)5學(xué)習(xí)方法存儲(chǔ)結(jié)構(gòu)與基本操作

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

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

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

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

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

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

……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)單選題在平衡二叉樹中插入一個(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)包括線性