課程簡介
人們在運用程式語言編寫程式的過程中發現所有的資料都可以抽象為三種結構，而對這些資料的所有操作都可以轉化為對這三種資料的幾種基本操作，而大多數的程式設計技巧都可以抽象為一些最基本的演算法。於是人們逐步發展了一門稱為資料結構（或資料結構與演算法）的電腦科學，它廣泛應用於計算機領域。
資料結構是資訊與計算專業的核心基礎課程之一。資料是計算機處理的物件，本課程研究的資料是非數值性、結構性的資料。學習本課程要求掌握各種主要資料結構的特點、計算機內的表示方法，以及處理資料的演算法，對於演算法所花費的時間和空間代價的分析也要求有一定程度的了解和掌握。
通過本課程的學習，使學生透徹地理解各種資料物件的特點，學會資料的組織方法和實現方法，並進一步培養基本的良好的程式設計能力。本課程主要包括如下三個方面的內容：
1．基本資料結構： 線性表、棧、佇列、串、陣列和廣義表，掌握它們的特點、表示和實現，對靜態結構要求非常熟練的程式設計上機實現，對動態結構要求逐步熟悉鍊錶的表示，通過模仿實驗教程中的例子，掌握程式設計技巧。強調類 c語言的書寫規範，特別注意引數的區別，輸入輸出的方式和錯誤處理方式，以及抽象資料型別的表示和實現。
能熟練完成以下的應用：多項式的計算、語法檢查、回朔演算法、遞迴演算法、表示式求值、離散事件模擬、文字的編輯和稀疏矩陣進行矩陣運算採用的處理方法。
2．複雜資料結構： 樹、二叉樹、圖。掌握它們的定義和特點、表示和實現，特別注意與基本資料結構的區別，掌握各種遍歷的遞迴和非遞迴演算法，能熟練完成以下的應用：
最優樹、huffman編碼、拓撲排序、關鍵路徑和最短路徑問題。
3．資料結構的應用： 查詢和內部排序。熟練掌握靜態查詢表的查詢方法和實現，了解雜湊表的構造和查詢方法。
掌握各種內部排序方法的基本思想、演算法特點、排序過程以及它們的時間複雜度分析。
《資料結構》教學大綱
課程名稱：資料結構
課程編號：014100028適用專業：計算機、資訊管理
總學時數：60學分數： 4
一、課程的性質、目的與任務
資料結構是計算機科學技術、資訊管理等專業的核心課程之一，是一門理論與工程實踐密切相關的綜合性課程，在計算機學科教學中具有十分重要的作用。大力加強資料結構課程的建設，提高資料結構課程的教學質量，有利於教學改革和教育創新，有利於高階應用型人才和創新人才的培養。
《資料結構》課程是計算機專業的專業基礎課程，介紹計算機領域的常用資料結構以及各種查詢和排序的演算法，是計算機專業學生必修的一門技術基礎課程，也是計算機專業的核心課程。資料結構是計算機專業的一門重要的專業基礎課，主要解決資料的表示和資料的處理，系統介紹三大資料結構及其實現，為作業系統等課程提供必要的知識基礎，為計算機人員提供必要的基本技能。二、課程教學基本要求
本課程介紹常用資料結構之間的邏輯結構、儲存結構和對其施加的運算，如：線性表、棧、佇列、串、陣列、廣義表、樹、圖等。同時還介紹各種查詢和排序的演算法。
通過本門課程的學習，應使學生掌握以下幾個方面的知識：
1：系統學習常用基本資料結構及其在不同儲存方式下的實現，掌握分析、選擇不同的資料結構和儲存結構的原則和方法。
2：學習和掌握在各種儲存結構上實現的各種演算法及其設計思想，從而學習各種分析問題和解決問題的能力。
3：掌握各種演算法的時空效率的分析方法，學會在實際應用中選擇合適的演算法。
4：掌握各種查詢和排序的演算法以及效率，並將其應用在程式設計中。三、課程教學內容體系
第一章：概論
1.1 什麼是資料結構
1.2 基本概念和術語
1.3 抽象資料型別的表現與實現
1.4 演算法和演算法分析
教學要求：理解資料、資料元素、資料項的概念；掌握邏輯結構和儲存結構的關係；理解演算法的基本概念；學會分析演算法的時間複雜性和空間複雜性。
第二章：線性表
2.1 線性表的型別定義
2.2 線性表的順序表示和實現
2.3 線性表的鏈式表示和實現（靜態查詢表不講）
2.4 一元多項式的表示及相加
教學要求：理解線性表的定義和特點；掌握順序表和煉表的特點，掌握在這兩種儲存結構上各種基本運算的實現演算法以及效率的分析，並學習在這兩種儲存結構上進行演算法設計的方法； 以達到利用基本演算法進行較複雜演算法設計的目的。
第三章：棧、佇列
3.1 棧
3.2 棧的應有和舉例
3.2.1 數制轉換
3.3.4 迷宮求解
3.3 棧與遞迴的實現
3.4 佇列
教學要求：理解棧和佇列的定義、特點，學習它們的各種組織方式及演算法；掌握它們的空和滿的判斷條件；並學會它們的簡單應用。
第四章：串
4.1 串型別的定義
4.2 串的表示和實現
4.2.1 定長順序儲存表示
4.2.3 串的塊鏈儲存表示
4.3 串的模式匹配演算法
4.3.1 求字串位置的定位函式
教學要求：了解串的概念，掌握串的基本運算，學習串運算在不同儲存結構下的實現過程。
第五章：多維陣列和廣義表
5.1 陣列的定義
5.2 陣列的順序表現和實現
5.3 矩陣的壓縮儲存
教學要求：領會陣列的定義，陣列的兩種順序儲存結構，並領會幾種特殊矩陣和稀疏矩陣的壓縮儲存方法。
第六章：樹
6.1 樹的定義和基本術語
6.2 二叉樹
6.2.1 二叉樹的定義
6.2.2 二叉樹的性質
6.2.3 二叉樹的儲存結構
6.3 遍歷二叉樹和線索二叉樹
6.3.1 遍歷二叉樹
6.4 樹和森林
6.4.1 樹的儲存結構
6.4.2 森林與二叉樹的轉換
6.4.3 樹和森林的遍歷
6.6 赫夫曼樹及其應用
6.6.1 最優二叉樹（赫夫曼樹）
6.6.2 赫夫曼編碼
教學要求：理解樹型結構的概念和術語，領會二叉樹的定義、形態、性質和儲存結構，掌握二叉樹的各種遍歷演算法極其實現過程，了解樹和森林及其相互轉換；掌握哈夫曼樹極其應用。
第七章：圖
7.1 圖的定義和術語
7.2 圖的儲存結構
7.2.1 陣列表示法
7.2.2 鄰接表
7.2.3 十字鍊錶
7.2.4 鄰接多重表
7.3 圖的遍歷
7.3.1 深度優先搜尋
7.3.2 廣度優先搜尋
7.4 圖的連通性問題
7.4.1 無向圖的連通分量和生成樹
7.4.3 最小生成樹
7.5 有向無環圖及其應用
7.5.1 拓撲排序
7.5.2 關鍵路徑
7.6 最短路徑
7.6.1 從某個源點到其餘各頂點的最短路徑
教學要求：理解圖型結構的概念和術語，掌握圖的鄰接矩陣和鄰接表兩種儲存形式，理解圖的遍歷的基本思想，掌握圖的兩種遍歷的方法和其實現的過程，學會圖在最小生成樹、拓撲排序、最短路徑、關鍵路徑中的應用。
第九章：查詢
9.1 靜態查詢表
9.1.1 順序表的查詢
9.1.2 有序表的查詢
9.1.4 索引順序表的查詢
9.3 雜湊表
9.3.1 什麼是雜湊表
9.3.2 雜湊函式的構造方法
9.3.3 處理衝突的方法
教學要求：掌握查詢表的定義和分類，熟練掌握順序查詢和二分查詢的思想，了解二叉排序樹及其查詢，了解雜湊查詢的思想和有關方法。
第十章：內部排序
10.1 概述
10.2 插入排序
10.2.1 直接插入排序
10.2.2 其他插入排序（表的插入排序不講）
10.2.3 希爾排序
10.3 快速排序
10.4 選擇排序
10.4.1 簡單選擇排序
10.5 歸併排序
教學要求：熟練掌握各種排序方法的思想和特點，如：插入排序、交換排序、選擇排序、分配排序等，學會分析它們的優點和缺點以及時空效能，並學會選擇和應用各種排序方法解決實際問題。
四、學時分配
五、推薦教材及教學參考書
1. 教材
《資料結構》；嚴蔚敏編著；清華大學出版社
2. 教學參考書
《演算法與資料結構（c語言版）》， 範策等編著，機械工業出版社， 2004
《資料結構（c語言版）》， 嚴蔚敏等編著， 清華大學出版社 2004
《資料結構與演算法》，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004
《資料結構實用教程（第二版）》，徐孝凱編著，清華大學出版社 2006
《資料結構輔導與提高實用教程（第二版）》，徐孝凱，清華大學出版社 2003
《資料結構》，謝楚屏等，人民郵電出版社，2001
《演算法與資料結構－c語言描述》，張乃孝等，高等教育出版社，2002
《資料結構》，殷人昆，清華大學出版社，2001
《計算機演算法設計與分析》，蘇德富，電子工業出版社，2001
《演算法與資料結構》，傅清祥，王嘵冬，電子工業出版社，1998
《資料結構－c++與物件導向的途徑》，張乃孝，裘宗燕，高等教育出版社，2001
《資料結構－用物件導向方法與c++描述》，殷人昆等清華大學出版社
《演算法設計與分析》，梁田貴，張鵬編著，冶金工業出版社，2004
六、考核辦法和成績評定標準
根據教學要求進行期末考試，由任課教師根據完成情況進行評定，並最終結合平時成績的考核給出綜合成績。
制定：制定日期：
教案（首頁）
授課時間教案編寫時間
《資料結構》教案
課程簡介 人們在運用程式語言編寫程式的過程中發現所有的資料都可以抽象為三種結構，而對這些資料的所有操作都可以轉化為對這三種資料的幾種基本操作，而大多數的程式設計技巧都可以抽象為一些最基本的演算法。於是人們逐步發展了一門稱為資料結構 或資料結構與演算法 的電腦科學，它廣泛應用於計算機領域。資料結構是資...
資料結構實驗教案
第 1 頁 填表說明 1 每項頁面大小可自行添減 2 教學內容與討論 思考題 作業部分可合二為一。資料結構課程實驗教案 第 2 頁 填表說明 1 每項頁面大小可自行添減 2 教學內容與討論 思考題 作業部分可合二為一。資料結構課程實驗教案 第 3 頁 填表說明 1 每項頁面大小可自行添減 2 教學內...
資料結構與拓撲資料結構
資料結構在gis中對於資料的採集 儲存 查詢 檢索和應用分析等操作方式有著重要的影響，一種高效率的資料結構應該具備以下幾個要求 1 組織的資料能夠表示要素之間的層次關係，便於不同資料聯絡於覆蓋 2 正確反映地理實體之間的空間排列方式和各實體之間的相互關係 3 便於訪問與檢索 4 節省儲存空間，減少資...