一、課程性質和特點
資料結構是計算機及應用專業的一門專業基礎課,在計算機軟體設計的各個領域中均會使用到資料結構的有關知識,也是各類計算機應用考核和計算機應用專業研究生考試必考科目。本課程要求學生較全面掌握各種常用資料結構,為學習後續軟體課程提供必要基礎,提高運用資料結構解決實際問題的能力。
二、本課程基本要求
1、從資料結構的邏輯結構、儲存結構和施加與其上的運算三個方面去掌握線性表、棧、佇列、陣列、串、廣義表、樹、圖和檔案等常用的資料結構;
2、掌握在各種常用資料結構上實現的排序和查詢運算;
3、對演算法的時間和空間複雜性有一定的分析能力;
4、針對簡單的應用問題,應能選擇合適的資料結構及設計有效的演算法解決。
三、與相關課程的聯絡
先修課程:離散數學、高階語言程式設計、c程式語言
後續課程:作業系統、資料庫管理系統
課程內容和考核目標
1.1 什麼是資料結構
1.2 資料抽象與抽象資料型別
1.3 物件導向方法
1.4 c++程式設計
1.5 資料結構的描述
1.6 演算法及其效能分析
本章首先給出資料結構常見基本概念和術語,繼而介紹抽象資料型別和物件導向的基本概念,回顧c++語言的基本特徵,最後介紹演算法的效率和演算法分析的基本方法。
1、資料結構的基本概念和術語
資料、資料元素、資料結構、抽象資料型別等基本概念
資料結構的4種邏輯結構和4種常見的儲存結構
2、物件導向方法
物件導向方法、封裝、繼承、多型
3、演算法描述及效能分析
演算法的定義、特徵和評價標準
演算法時間複雜度、空間複雜度和漸進時間複雜度的概念和分析方法
四、作業
習題集1.8,1.12
五、本章建議學習時間:4學時
2.1線性表抽象資料型別
2.2線性表的順序表示
2.3線性的鏈結表示
2.4多項式的算術運算
本章講述線性表抽象資料型別,線性表的順序表示和鏈結表示,線性表的應用。要求在熟悉這些內容的基礎上,能夠針對具體應用問題的要求和性質,選擇和設計合適的儲存結構與有效演算法,解決線性表相關問題。
1、線性表抽象資料型別,邏輯描述和運算
2、線性表的順序儲存和鏈結儲存實現與比較
3、多項式和其他線性表應用
四、作業
習題集2.1 ,2.2 , 2.3, 2.4, 2.8
五、本章建議學習時間:12學時
3.1棧
3.2表示式計算
3.3佇列
本章講述兩種重要的線性結構:棧和佇列,要求在掌握他們特點的基礎上,學會棧和佇列的應用。
1、棧的描述和順序表示
2、利用棧進行表示式的計算和轉換
3、佇列的描述和順序表示,迴圈佇列
四、作業
習題集3.1, 3.5, 3.6
五、本章建議學習時間: 8學時
4.1 串型別的定義
4.2 串的表示和實現
4.2串的模式匹配演算法
在實際工作中,串是應用廣泛的資料型別,也是線性結構的特殊應用。本章從資料結構的角度講述它的抽象資料型別的定義和實現。
串的描述和模式匹配演算法
四、作業
習題集4.3, 4.7, 4.11
五、本章建議學習時間:8學時
5.1陣列的定義
5.2陣列的順序表示和實現
5.3矩陣的壓縮儲存
5.4 廣義表的定義
5.5 廣義表的儲存結構
本章是線性表應用的延續,簡單了解陣列和廣義表。
1、陣列的描述和順序儲存
2、特殊矩陣順序儲存及稀疏矩陣的三元表儲存和十字鍊錶儲存
3、廣義表的定義,求表頭、表尾及廣義表深度
四、作業
5.2,5.10,5.12
五、本章建議學習時間:8學時
6.1樹的基本概念
6.2二叉樹
6.3 遍歷二叉樹和線索二叉樹
6.4樹和森林
6.5哈夫曼樹與哈夫曼編碼
本章講述樹型這一重要的資料結構,樹型結構元素之間有分層關係結構。樹結構為巢狀資料提供一種自然表示和有效解決方案,樹的應用也和遞迴有密切聯絡。
1、樹的定義和術語,二叉樹的定義及基本性質
2、二叉樹的儲存表示
3、二叉樹遍歷及其遞迴演算法,線索二叉樹
4、森林和二叉樹的轉換,樹和森林的儲存表示
5、哈夫曼樹的建立和哈夫曼編碼
四、作業
6.1,6.2,6.3,6.5,6.6,6.15,6.20,6.26
五、本章建議學習時間: 12學時
9.1圖的基本概念
9.2圖的儲存結構
9.3圖的遍歷
9.4拓撲排序和關鍵路徑
9.5最小代價生成樹
9.6最短路徑
本章講述圖這種更一般、更複雜的資料結構型別,圖的應用非常廣泛,本章重點講述圖的描述和圖的儲存結構,以及幾種圖的應用演算法。
1、圖的定義及基本術語
2、圖的儲存表示和遍歷
3、有向圖的拓撲排序和關鍵路徑演算法
4、圖的最小代價生成樹演算法
5、圖的最短路徑演算法
四、作業
7.1,7.4,7.7,7.9,7.11
五、本章建議學習時間:12學時
第9章查詢
9.1 靜態查詢表
(1) 順序表的查詢
(2) 有序表的查詢
9.2 動態查詢
(1) 二叉排序樹和平衡二叉樹
(2) b樹和b+樹
9.3雜湊表
二、學習目的和要求
查詢表是一種在實際應用中大量使用的資料結構,本章主要介紹了這一資料結構。要求熟練掌握靜態查詢表的查詢演算法及其實現,熟練掌握二叉排序樹的插入和查詢演算法及其實現;了解b樹、b+樹的各種操作;掌握雜湊表的造表方法;了解各種雜湊函式和處理衝突的方法。
三、考核知識點和考核要求
1. 靜態查詢表的查詢演算法及其實現
2. 二叉排序樹的插入和查詢演算法及其實現
3. 雜湊表的造表方法
四、作業
9.1,9.2
五、本章建議學習時間: 12學時
10.1基本概念
10.2簡單排序演算法
10.3快速排序
10.4二路合併排序
10.5基數排序
排序是資料處理中一種重要的操作,本章重點講述三種簡單排序、快速排序和二路歸併演算法的設計思路和效率分析,並簡要介紹了基數排序演算法。
1、排序的基本概念
2、簡單排序演算法的設計和效率分析
3、快速排序和二路歸併演算法和效率分析
四、作業
10.1,10.12
五、本章建議學習時間: 4學時
任課教師:袁彩虹
聯絡**:0378-*******
《資料結構》自學指導書
序言1 課程簡介 資料結構是計算機及應用專業的一門專業基礎課,在計算機軟體的各個領域中均會使用到資料結構的有關知識。隨著對軟體發展的需求越來越高 需要越來越多的人挖掘設計高效能軟體技術,以推動社會資訊化的發展。同時,因為無論是系統軟體還是應用軟體,其核心是資料結構及其演算法,所以作為軟體設計技術的理...
自學考試《資料結構》複習指導
第一章 緒論 一 概念 資料結構 是一門研究程式設計中計算機操作的物件以及它們之間的關係和運算的一門學科。資料 是描述額觀事物的數 字元以及所有能輸入到計算機中被電腦程式加工處理的資訊的集合。資料元素 資料元素是資料的基本單位。乙個資料項或多個資料項 域 資料項是資料的最小單位。結點 頂點 記錄。資...
資料結構複習大綱
5.單鏈表中結點的結構,每個域的定義及作用,即lnode型別的定義及結構。6.帶表頭附加結點的鍊錶 迴圈鍊錶 雙向鍊錶的結構特點。7.線性表的每一種運算在單鏈表上實現的演算法及相應的時間複雜度。8.在順序儲存或鏈結儲存的線性表上實現指定功能的演算法的分析和設計。9 josephus問題的求解過程。1...