數據結構東北大學

孟凡榮2009年3月數據結構學習指導

1課程簡介

2章節目錄

3數據結構實驗

4實驗課題

5學習方法

6考試指導

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

1課程簡介教學要求

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

1課程簡介課程內容本課程分為四個知識單元，共7章18課。第1單元，數據結構基礎；第2單元，常用數據結構；第3單元，數據結構及算法應用；第4單元，數據結構實驗。2章節目錄第1章數據結構與算法基礎第2章基本數據結構第3章棧和隊列第4章樹和圖第5章查找表和文件第6章數據結構及算法應用2章節目錄第1課數據結構基本概念

1數據結構的研究對象

2數據結構的定義及分類3數據類型和抽象數據類型4數據結構的描述與實現2章節目錄第2課算法基礎

1算法的概念

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

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

1順序表的存儲結構

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

1鏈表的存儲結構

2鏈表的基本操作

3有序鏈表

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

1串的邏輯結構

2串的順序存儲結構

3串的鏈式存儲結構

4串的模式匹配

2章節目錄第6課數組

1數組的邏輯結構

2數組的存儲結構

3特殊矩陣的存儲

2章節目錄第7課棧

1棧的邏輯結構

2順序棧

3鏈棧

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

1隊列的邏輯結構

2鏈隊列

3循環隊列

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

1樹和二叉樹的邏輯結構

2二叉樹的性質3二叉樹的存儲結構4二叉樹的遍歷

2章節目錄第10課樹和森林

1樹的存儲結構2樹、森林與二叉樹3樹和森林的遍歷

2章節目錄第11課圖

1圖的邏輯結構

2圖的存儲結構3圖的遍歷

2章節目錄第12課查找表

1查找表的概念

2靜態查找表3二叉排序樹

4散列（Hash）表

2章節目錄第13課文件

1文件的概念

2索引文件3散列文件

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

2章節目錄第15課線性結構應用

1約瑟夫環

2靜態鏈表應用

3三元組求解稀疏矩陣

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

2章節目錄第15課線性結構應用

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

9共享棧10子集劃分2章節目錄第16課樹形結構應用

1全線索鏈表

2表達式求值3哈夫曼樹

4等價類劃分5樹的形態

2章節目錄第17課圖形結構應用

1迷宮問題

2無向圖的連通性應用

3有向無環圖應用

4最短路徑問題

2章節目錄第18課數據結構程序設計

1問題求解策略

2

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

3數據結構實驗源程序調試全局變量及包含頭文件存儲結構定義結構創建及銷毀操作屬性操作查找操作更新操作主程序

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

1.1學生成績統計

1.2有序表求并

1.3字典維護

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

2.1約瑟夫環

2.2一元多項式相加

2.3商品維護4實驗課題實驗3順序棧基本操作及應用實現棧的基本操作，包括棧的創建、銷毀、出棧、入棧、取棧頂元素、判棧空等函數。應用參考題目

3.1數制轉換

3.2算術表達式求值

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

4.1存儲緩沖區問題

4.2迷宮最短路徑問題

4.3楊輝三角形

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

5.1哈夫曼編碼

5.2表達式求值

5.3因特網查詢4實驗課題實驗6圖的基本操作及應用實現圖結構的初始化、創建、查找、遍歷、插入、刪除等基本操作。應用參考題目

6.1無向圖的關節點問題

6.2最小生成樹

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

7.1分塊查找應用

7.2二叉排序樹應用

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

8.1排序算法應用

8.2排序算法比較

8.3計數式基數排序4實驗課題實驗9數據結構綜合應用實現類似迷宮問題、銀行排隊問題等綜合應用算法。應用參考題目

9.1背包問題

9.2表達式求值

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

C與C++

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

C++語言的引用調用的參數傳遞方式。在形參表中，以&打頭的參數即為引用參數。

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

Status

DestroyTriplet(Triplet&T)

{//操作結果：三元組T被銷毀

free(T);

T=NULL;

returnOK;

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

//將&T改為*T

{//操作結果：三元組T被銷毀

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

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

returnOK;

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

DestroyTriplet(T);

相應的標準C程序調用語句為：

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

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

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

voidPrintUser(Spacep[])

{

//輸出p數組所指的已分配空間

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

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

p=new

Chunk;在標準C中要改為：

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

<<endl;

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

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

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

順序存儲鏈式存儲索引存儲散列存儲結構創建及銷毀屬性操作查找操作更新操作5學習方法循序漸進

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

基本操作實現簡單應用實現簡單綜合應用實現復雜綜合應用實現

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

……5學習方法綜合應用

迷宮問題背包問題排隊時間模擬工程關鍵路徑局部與全局最優問題

……6考試指導考試題型

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

6考試指導單選題在一個單鏈表中，已知*q結點是*p結點的前驅結點，若在*q和*p之間插入結點*s，則執行操作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考試指導單選題在平衡二叉樹中插入一個結點后引起了不平衡，設最低(最接近于葉子)的不平衡點是A，并已知A的左、右孩子的平衡因子分別為-1和0，則應進行的平衡旋轉是A．LL型

B．LR型

C．RL型

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

A.第i行1的元素之和

B.第i列1的元素之和

C.第i行0的元素個數

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

A.窮舉法

B.貪心法

C.分治法

D.回溯法

6考試指導填空題數據的邏輯結構包括線性