數據結構(南京理工大學提供的慕課課程)

課程性質

課程定位

數據結構課程是信息管理與信息系統專業的重要課程之一，是一門綜合性專業基礎課，介於數學、計算機硬體和計算機軟體三者之間，是作業系統、資料庫技術、高級程式設計以及信息系統開發等課程的基礎，其相關技術方法廣泛套用於信息科學、系統工程、計算機科學技術及各種工程技術領域。

適應專業

數據結構課程適合信息管理與信息系統專業等專業學習。

開課信息

該課程開課一次，開課時間為2020年05月08日~2020年05月28日，授課教師是朱保平教師，學時安排為4小時每周，已有1951人參加。

課程簡介

數據結構課程介紹了數據結構的基本概念、原理和算法設計基本思想；線性表、堆疊、佇列、串和組數等常用線性結構的算法模型和套用；樹和二叉樹、圖和網等典型非線性結構的算法模型和套用；查找和排序等典型數據結構算法設計等內容。

課程大綱

01緒論

本章主要講述數據結構的基本概念、數據結構的研究對象、數據結構的四種形式、抽象數據類型的定義、算法的特徵與算法複雜度計算的基本方法。

課時

1.1 數據結構概述

1.2 算法與算法分析

02線性表

本章主要講述線性表的類定義，包括線性表的順序存儲結構的類定義和基本操作、線性表的鏈式存儲結構的類定義和基本操作。循環鍊表和雙向鍊表的基本操作。

課時

2.1 線性表順序存儲結構的類定義

2.2 線性順序表的基本操作

2.3 線性表的鏈式表示

2.4 單鍊表的基本操作

2.5 循環鍊表與雙向鍊表

03棧和佇列

本章講述2 種特殊和線性表-棧和佇列。主要講述棧和佇列的類定義、基本操作及其套用。

課時

3.1 順序棧的類定義及基本操作

3.2 棧的鏈式存儲結構及棧的套用

3.3 佇列的類定義及其實現

04樹和二叉樹

本章講述樹的定義、二叉樹的定義及性質、二叉樹的遍歷方法、二叉樹的類定義及其基本操作、樹的存儲結構、樹與二叉樹的轉換方法和哈夫曼(Huffman)樹及套用。

課時

4.1 樹的定義及基本術語

4.2 二叉樹的定義及性質

4.3 二叉樹的存儲及遍歷

4.4二叉樹的類定義及基本操作

4.5 樹的存儲結構、樹和二叉樹的轉換

4.6 哈夫曼(Huffman)樹及套用

05圖

本章講述圖的定義用基本術語、圖的存儲結構、圖的類定義及其基本操作、圖的2種遍歷方法、最小生成樹的2種生成方法、拓撲排序、關鍵路徑和最短路徑求解算法。

課時

5.1 圖的定義和術語

5.2 圖的儲存結構

5.3 圖的定義及基本操作

5.4 圖的遍歷

5.5 最小生成樹

5.6 拓撲排序

5.7 關鍵路徑

5.8 最短路徑

06查找

本章講述靜態查找表和動態查找表2種查找方法。主要內容包括順序查找和二分查找方法；二叉排序樹、平衡二叉樹、B-樹和哈希表的存儲方法和基本操作的實現。

課時

6.1 靜態查找表

6.2 二叉排序樹

6.3 平衡二叉樹

6.4 B-樹

6.5 哈希表

07內部排序

本章主要講述內部排序的各種排序方法。

課時

7.1 插入類排序

7.2 交換類排序

7.3 選擇類排序

7.4 其他排序方法

（註：課程大綱排版從左到右列）

課前預備

預備知識：學習數據結構課程需具備程式設計語言C++知識。

授課目標

通過該課程的教學，使學生了解計算機套用中數據對象的特性，學會中套用中根據現實世界中的問題選擇適當的數據邏輯結構和存儲結構以及相應算法，掌握一些計算機處理任務中所需要進行的數據抽象化和結構化處理方法，並且培養基本的程式設計技能。

所獲榮譽

2020年，該課程被中華人民共和國教育部認定為首批國家級一流本科課程。

教師簡介

朱保平：南京理工大學副教授，長期從事離散數學、數據結構、編譯原理和形式語言與自動機等課程的教學工作，出版《離散數學》、數據結構》和《形式語言與自動機》等教材。