主編姜力
山東理工大學工程技術學院
電子資訊系
目錄概述3
課程大綱4
實驗大綱9
實驗一線性表順序儲存結構的描述及基本操作---------12
實驗二線性表鏈式儲存結構的描述及基本操作13
實驗三棧儲存結構的描述及應用演算法設計19
實驗四佇列儲存結構的描述及應用演算法設計21
實驗五二叉樹的儲存結構的兩種描述方法24
實驗六二叉樹的基本操作實現26
實驗七圖儲存結構的描述及基本操作實現28
實驗八查詢演算法、排序基本演算法35
概述《資料結構》在電腦科學與技術專業中是一門必修的綜合性專業基礎課，對資料結構的研究不僅涉及計算機硬體的研究範圍，而且和計算機的軟體研究有著密切的關係，無論是編譯原理還是作業系統，都涉及到資料元素在儲存器中的分配問題；在研究資訊檢索時也必須考慮如何組織資料，以便查詢和訪問元素更為方便。
因此，可以認為資料結構是介於數學、計算機硬體和計算機軟體三者之間的一門核心課程。學習本課程的目的是使學生了解計算機處理物件的特性，能將實際問題中所設計的處理物件在計算機中表示出來並對它們進行處理。學習本課程的任務是通過演算法訓練來提高學生的思維能力，通過程式設計的技能訓練來提高學生的綜合應用能力和專業素質。
為今後學習程式設計特別是系統程式和大型應用程式的設計打下重要基礎。
要求學生通過實驗學會分析研究計算機加工的資料物件的特性，通過演算法設計及除錯能夠運用所學知識選擇適當的資料結構、儲存結構和編寫相應的演算法，初步掌握演算法的時間與空間效能分析技巧，得到複雜程式設計的訓練。
資料結構課程教學大綱
課程名稱：資料結構（data structures）
課程編號：172321
總學時數：72學時（其中含實驗教學 16學時
學分：4.5學分
課程類別：必修
先修課程：離散數學、c語言
教材：《資料結構 》(c語言版)（清華大學出版社、編者：嚴蔚敏）
參考書目：寧正元編著，《資料結構》，水利水電出版社，2023年6月
《課程內容簡介》：
《資料結構》是計算機程式設計的重要理論技術基礎，是計算機學科的核心課程。第一章綜述資料、資料結構和抽象資料型別等基本概念；第二至第七章從抽象資料型別的角度，分別討論線性表、棧、佇列、串、陣列、廣義表、樹和二叉樹以及圖等基本型別資料結構及其應用；第八章綜合介紹作業系統和編譯程式中涉及的動態儲存管理的基本技術；第九章至第十一章討論查詢和排序，介紹了各種實現方法，並從時間上進行定性或定量餓分析和比較；第十二章介紹常用的檔案結構。
一、課程性質、目的和要求
《資料結構》是電腦科學與技術專業必修的綜合性專業基礎課，學習本課程的目的是使學生了解計算機處理物件的特性，能將實際問題中所設計的處理物件在計算機中表示出來並對它們進行處理。課程的任務是通過演算法訓練來提高學生的思維能力，通過程式設計的技能訓練來提高學生的綜合應用能力和專業素質。為今後學習程式設計特別是系統程式和大型應用程式的設計打下重要基礎。
要求學生學會分析研究計算機加工的資料物件的特性，能夠通過運用所學知識在實際應用中選擇適當的資料結構、儲存結構和相應的演算法，初步掌握演算法的時間與空間效能分析技巧，得到複雜程式設計的訓練。
二、教學內容、要點和課時安排
《資料結構》授課課時分配表
本課程的教學內容共分12章。
第一章：緒論
主要內容是：資料結構的一些基本概念：資料、資料元素、資料結構、儲存結構、資料型別、抽象資料型別、演算法等。演算法的時間複雜性和空間複雜性的評價。
重點：基本概念與術語
難點：抽象資料型別
第二章：線性表
主要內容是：線性表的定義和線性表的順序、鏈式儲存結構。線性表的插入、刪除等運算的演算法。重點：線性表的操作演算法
難點：線性表演算法設計
第三章：棧與佇列
主要內容是：棧的定義、順序、鏈式儲存、進出棧運算及雙棧操作。棧在非遞迴和遞迴演算法中的應用。佇列的定義、順序、鏈式儲存、入隊和出隊運算。
重點：棧和佇列的操作演算法
難點：棧的應用和佇列的應用
第四章：串
主要內容是：字串的定義、順序儲存和運算、串的模式匹配演算法。
重點：字串的運算演算法
難點：串的模式匹配演算法
第五章：陣列和廣義表
主要內容是：陣列及其運算、陣列的順序儲存、稀疏矩陣的三元組線性表表示、順序儲存、十字鏈儲存及相關運算。廣義表的定義、儲存結構及運算。
重點：特殊矩陣與稀疏矩陣
難點：稀疏矩陣
第六章：樹
主要內容是：樹的概念和樹的各種表示、二叉樹的定義、性質、儲存結構和生成演算法。二叉樹的遍歷運算和線索的應用。
二叉排序樹的定義、查詢、插入、刪除和生成演算法。哈夫曼樹的定義和生成過程、哈夫曼編碼。一般樹的儲存結構、樹和森林之間的相互轉換及樹與森林遍歷。
重點：二叉樹的運算、哈夫曼樹及編碼
難點：哈夫曼樹及編碼
第七章：圖
主要內容是：圖的定義和基本術語、圖的儲存結構。主要指鄰接矩陣和鄰接表。
圖的深度和廣度優先搜尋遍歷、產生圖的最小生成樹的普利姆演算法和克魯斯卡爾演算法。求圖中從一頂點到其餘各項頂點最短路徑的狄克斯特拉演算法和每對頂點之間最短路徑的佛洛伊德演算法。
拓撲排序的概念及演算法、關鍵路徑的概念及演算法。
重點：圖的儲存和演算法
難點：最小生成樹、狄克斯特拉演算法
第八章：動態儲存管理
主要內容是：動態儲存概念、可利用空間表及分配方法、邊界標識法和夥伴系統。
重點：動態儲存概念、可利用空間表及分配方法
難點：可利用空間表及分配方法
第九章：查詢
主要內容是：查詢的有關概念、順序查詢和二分查詢、索引查詢和分塊查詢，雜湊的概念，構造雜湊函式，處理衝突的方法，雜湊表的插入和查詢演算法。
平衡二叉樹的定義及調整演算法，b_樹的定義及查詢、插入和刪除關鍵字的過程。
重點：各種查詢演算法
難點：平衡二叉樹的定義及調整演算法、雜湊表
第十章：內部排序
主要內容是：排序的有關概念、直接插入排序和希爾排序、直接選擇排序和堆排序、氣泡排序和快速排序。歸併排序和基數排序。
重點：各種排序演算法
難點：希爾排序、直接選擇排序和堆排序
第十一章：外部排序
主要內容是：外存資訊的訪問、外部排序的方法。
重點：外部排序的方法
難點：外部排序的方法
第十章：檔案
主要內容是：檔案的概念，外儲存器的組織，外儲存器資訊交換的基本單位——頁面的含義。
順序檔案和索引檔案的組織、按擴充雜湊和可擴充雜湊檔案的組織、多重鏈結表檔案和倒排檔案的組織。
重點：檔案的概念
難點：順序檔案和索引檔案的組織
三、教學方法
根據該課程理論性強、抽象、難度大的特點，以教師課堂講授為主，教學方法採用多**技術手段，並結合學生的實際情況進行大量課外作業練習與上機實踐練習。
四、成績考核方式
考試採取筆試，滿分100分。
五、制定本大綱的有關說明
1、本教學大綱是電腦科學與技術本科專業和資訊管理與資訊系統本科專業《資料結構》課程的基本內容。這些內容是通過講課、實驗和實訓等教學環節進行教學的。
2、本課程是一門介於數學、計算機硬體和計算機軟體三者之間的綜合基礎課程。既有抽象的理論分析又有很強的實踐性，涉及知識面較廣。為了使學生便於理解講課內容，在教學過程中要穿插安排一定數量的實踐環節。
使學生在學完本課程後，能夠運用所學的知識，分析和解決實際的問題，為具有開發非數值計算程式設計、研發其它系統程式和設計大型應用程式打下堅實的理論基礎和實踐基礎。
3、因課程涉及的圖形較多並且演算法比較複雜，需採用多**教室教學。
4、作業通過布置課後習題的形式進行，每週上交一次作業。通過課後練習、上機除錯程式加以完善。以便使學生掌握通過對實際問題的抽象，捨去資料元素的具體內容，得到其邏輯結構，再通過抽象捨棄實現細節，得到運算的定義，從而完成設計任務的方法，達到能夠獨立設計出一般、複雜程式的目的。
5、本課程必須在專業技術基礎課：c語言、離散數學等課程的基礎上開設。是作業系統、資料庫系統等後續課程的基礎，也是設計和實現其它系統程式和大型應用程式的重要基礎。
6、主講教師根據本大綱，制定具體的授課計畫。
大綱執筆者：姜力
大綱審定者：
分管教學負責人簽字：
《資料結構》(172321)實驗(上機)教學大綱
學科部(系): 工程技術學院電子資訊系執筆人: 姜力審核人:王軍
一、 課程基本情況
總學時72，教學計畫實驗學時16，實際開出實驗學時16。
本課程為電腦科學與技術本科專業基礎課。
二、實驗教學目的和要求
1、掌握各實驗專案的基本原理、方法和實驗內容和步驟。
2、熟練掌握線性表、樹和圖型結構。
3、能獨立編寫演算法和除錯程式。
4、了解三種資料結構的具體應用。
三、學時分配及實驗專案表
學時分配及實驗專案表（本課程實驗共安排16學時，其中16學時為必選實驗）。
四、實驗課的考核
資料結構實驗指導書
第一部分課程概述 資料結構是計算機程式設計的重要理論技術基礎，它不僅是計算機學科的核心課程，而且已成為其它立功專業的熱門選修課。資料結構實驗可以使學生對資料結構課程所教授的內容通過實驗環節加以實踐，提高學生的程式設計 編寫及除錯能力，是一門基礎的實驗課程。第二部分實驗要求 通過實驗，學生對常用資料結...
資料結構實驗指導書
實驗名稱資料結構試驗 課程名稱資料結構 專業班級學生姓名 學號成績 指導老師實驗日期 2010年3月 5月 實驗報告如列印，紙張用a4，左裝訂 頁邊距 上下2.5cm，左2.5cm，右2.0cm 字型 字型小四號，1.25倍行距。驗證性 綜合性實驗報告應包含的主要內容 一 實驗目的及要求 1 實驗目...
資料結構實驗指導書
山東大學軟體學院 資料結構 演算法與應用 實驗指導書 一 實驗要求 1 採用良好的程式設計風格 關鍵操作要有注釋。2 程式能夠執行，顯示執行結果。二 開發工具 microsoft visual c eclipse ide for c 三 實驗時間 地點 一 實驗目的 1 熟悉開發工具的使用。2 掌握...