數(shù)據(jù)結(jié)構(gòu)學習指導

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

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

1課程簡介

2章節(jié)目錄

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

4實驗課題

5學習方法

6考試指導

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

1課程簡介教學要求

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

1課程簡介課程內(nèi)容本課程分為四個知識單元，共7章18課。第1單元，數(shù)據(jù)結(jié)構(gòu)基礎；第2單元，常用數(shù)據(jù)結(jié)構(gòu)；第3單元，數(shù)據(jù)結(jié)構(gòu)及算法應用；第4單元，數(shù)據(jù)結(jié)構(gòu)實驗。2章節(jié)目錄第1章數(shù)據(jù)結(jié)構(gòu)與算法基礎第2章基本數(shù)據(jù)結(jié)構(gòu)第3章棧和隊列第4章樹和圖第5章查找表和文件第6章數(shù)據(jù)結(jié)構(gòu)及算法應用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)的描述與實現(xiàn)2章節(jié)目錄第2課算法基礎

1算法的概念

2算法的描述3算法分析基礎

4算法設計基礎2章節(jié)目錄第3課順序表

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

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

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

2鏈表的基本操作

3有序鏈表

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

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

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

3串的鏈式存儲結(jié)構(gòu)

4串的模式匹配

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

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

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

3特殊矩陣的存儲

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

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

2順序棧

3鏈棧

4棧的簡單應用2章節(jié)目錄第8課隊列

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

2鏈隊列

3循環(huán)隊列

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

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

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

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

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

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

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

2圖的存儲結(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)應用

1約瑟夫環(huán)

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

3三元組求解稀疏矩陣

4實用型線性鏈表5一元多項式運算

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

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

9共享棧10子集劃分2章節(jié)目錄第16課樹形結(jié)構(gòu)應用

1全線索鏈表

2表達式求值3哈夫曼樹

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

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

1迷宮問題

2無向圖的連通性應用

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

4最短路徑問題

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

1問題求解策略

2

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

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

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

1.1學生成績統(tǒng)計

1.2有序表求并

1.3字典維護

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

2.1約瑟夫環(huán)

2.2一元多項式相加

2.3商品維護4實驗課題實驗3順序?；静僮骷皯脤崿F(xiàn)棧的基本操作，包括棧的創(chuàng)建、銷毀、出棧、入棧、取棧頂元素、判棧空等函數(shù)。應用參考題目

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

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

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

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

4.2迷宮最短路徑問題

4.3楊輝三角形

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

5.1哈夫曼編碼

5.2表達式求值

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

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

6.2最小生成樹

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

7.1分塊查找應用

7.2二叉排序樹應用

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

8.1排序算法應用

8.2排序算法比較

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

9.1背包問題

9.2表達式求值

9.3智能搜索5學習方法預備知識課程內(nèi)容體系存儲結(jié)構(gòu)與基本操作循序漸進實驗能力典型應用算法綜合應用5學習方法預備知識

C與C++

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

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

標準C不支持引用參數(shù)，對此需進行轉(zhuǎn)換。5學習方法預備知識-引用參數(shù)&問題含有引用參數(shù)的函數(shù)如下：

Status

DestroyTriplet(Triplet&T)

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

free(T);

T=NULL;

returnOK;

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

//將&T改為*T

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

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

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

returnOK;

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

DestroyTriplet(T);

相應的標準C程序調(diào)用語句為：

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

StatusClearList(SqList&L)5學習方法預備知識-變量定義問題

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

voidPrintUser(Spacep[])

{

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

for(inti=0;i<MAX;i++)……5學習方法預備知識-動態(tài)申請空間問題

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

p=new

Chunk;在標準C中要改為：

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

<<endl;

好處是不必給出格式符。這樣，當變量的類型發(fā)生變化時，不必修改語句。5學習方法預備知識-輸入輸出語句但在標準C中必須改為：

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

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

順序存儲鏈式存儲索引存儲散列存儲結(jié)構(gòu)創(chuàng)建及銷毀屬性操作查找操作更新操作5學習方法循序漸進

簡單數(shù)組-順序表-單鏈表-字符串-二叉樹-圖簡單基本操作-復雜基本操作簡單應用-高級應用-綜合應用5學習方法實驗能力

基本操作實現(xiàn)簡單應用實現(xiàn)簡單綜合應用實現(xiàn)復雜綜合應用實現(xiàn)

5學習方法典型應用算法一元多項式表達式求值哈夫曼樹最小生成樹拓撲排序

……5學習方法綜合應用

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

……6考試指導考試題型

單選題填空題算法應用題算法分析題算法設計題

6考試指導單選題在一個單鏈表中，已知*q結(jié)點是*p結(jié)點的前驅(qū)結(jié)點，若在*q和*p之間插入結(jié)點*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考試指導單選題假設一個棧的輸入序列為A，B，C，D，則借助一個棧所得到的輸出序列不可能是A．A，B，C，D

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

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

B．LR型

C．RL型

D．RR型6考試指導單選題有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中

A.第i行1的元素之和

B.第i列1的元素之和

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

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

A.窮舉法

B.貪心法

C.分治法

D.回溯法

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