數(shù)據(jù)結(jié)構(gòu)課程大綱2

數(shù)據(jù)結(jié)構(gòu)課程大綱

課程名稱：數(shù)據(jù)結(jié)構(gòu)/DataStructure

課程編號(hào)：ab08224202課程屬性：專(zhuān)業(yè)基礎(chǔ)課

授課對(duì)象：信息管理與信息系統(tǒng)專(zhuān)業(yè)本科生總學(xué)時(shí)/學(xué)分：48/3

開(kāi)課學(xué)期：第4學(xué)期課程負(fù)責(zé)人：

先修課程：C++程序設(shè)計(jì)

一、課程概述

數(shù)據(jù)結(jié)構(gòu)是信息管理與信息系統(tǒng)專(zhuān)業(yè)的專(zhuān)業(yè)基礎(chǔ)課。課程通過(guò)介紹常用的數(shù)據(jù)結(jié)構(gòu)和算

法，要求學(xué)生掌握線性表、堆棧、隊(duì)列、數(shù)組、字符串、樹(shù)等典型數(shù)據(jù)結(jié)構(gòu)的建立和實(shí)現(xiàn)方

法，熟悉常用的遞歸、排序和查找方法，理解算法的設(shè)計(jì)步驟、能從時(shí)間和空間復(fù)雜性兩個(gè)

角度對(duì)算法的進(jìn)行評(píng)估，為信息系統(tǒng)的設(shè)計(jì)和開(kāi)發(fā)奠定良好的算法分析基礎(chǔ)。通過(guò)本課程的

教學(xué)我們希望能夠使學(xué)生在理解常用數(shù)據(jù)結(jié)構(gòu)和算法原理的基礎(chǔ)上，能運(yùn)用C++等面向?qū)?/p>

象程序設(shè)計(jì)語(yǔ)言進(jìn)行實(shí)現(xiàn)，初步具備用計(jì)算機(jī)程序解決現(xiàn)實(shí)世界中較復(fù)雜問(wèn)題的能力。

二、課程目標(biāo)

在課程結(jié)束時(shí)，學(xué)生應(yīng)該能夠：

1.掌握常用數(shù)據(jù)結(jié)構(gòu)和算法的基本原理與實(shí)現(xiàn)方法；

2.熟悉算法的正確性、時(shí)間復(fù)雜性和空間復(fù)雜性分析；

3.學(xué)會(huì)運(yùn)用基本的遞歸、排序和查找算法解決具體問(wèn)題；

4.了解線性表、堆棧、隊(duì)列、數(shù)組、字符串、樹(shù)等典型數(shù)據(jù)結(jié)構(gòu)。

三、主要內(nèi)容及其基本要求

本課程須完成的基本教學(xué)內(nèi)容和要求如下：

1.緒論。主要講解數(shù)據(jù)結(jié)構(gòu)的基本概念、算法的書(shū)寫(xiě)及算法分析基礎(chǔ)，要求學(xué)生理解

算法的書(shū)寫(xiě)規(guī)范、正確性證明，以及算法的時(shí)間與空間復(fù)雜性分析基礎(chǔ)，了解算法效率的評(píng)

價(jià)準(zhǔn)則；

2.線性表、堆棧和隊(duì)列。主要講解鏈表、堆棧和隊(duì)列的概念、基本原理，要求掌握三

類(lèi)數(shù)據(jù)結(jié)構(gòu)的建立與實(shí)現(xiàn)方法，了解相關(guān)算法的復(fù)雜性分析；

3.遞歸。講授遞歸過(guò)程的基本原理，要求學(xué)生能靈活運(yùn)用面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言實(shí)現(xiàn)

遞歸算法，理解遞歸過(guò)程與堆棧之間的效率比較及相互轉(zhuǎn)換，了解遞歸在回溯等問(wèn)題上的應(yīng)

用；

4.數(shù)組和字符串。本章著重講解數(shù)組和字符串的相關(guān)操作，要求理解矩陣的組織方法,

并了解相關(guān)算法的復(fù)雜性分析。；

5.樹(shù)。通過(guò)本章講解，要求學(xué)生掌握樹(shù)和森林的定義和基本原理，能熟練掌握二叉樹(shù)

的創(chuàng)建、遍歷等基本算法，理解二叉樹(shù)的線索化、森林的遍歷及其與二叉樹(shù)之間的相互轉(zhuǎn)換,

了解樹(shù)在查找、排序、壓縮算法等領(lǐng)域的應(yīng)用；

6.圖。主要講解圖的基本概念、圖的存儲(chǔ)結(jié)構(gòu)與遍歷算法、拓?fù)渑判?、關(guān)鍵路徑與最

短路徑、最小支撐樹(shù)。要求學(xué)生掌握?qǐng)D的存儲(chǔ)與遍歷操作，能利用圖解決簡(jiǎn)單的網(wǎng)絡(luò)問(wèn)題和

最短路徑等問(wèn)題。

7.排序。通過(guò)講解插入、交換、選擇、合并四種主要排序算法，要求學(xué)生在掌握其基

本原理與實(shí)現(xiàn)方法的基礎(chǔ)上，對(duì)各種排序算法的穩(wěn)定性、時(shí)間效率、空間復(fù)雜性有一個(gè)清晰

的認(rèn)識(shí)，能在實(shí)踐編程過(guò)程中熟練運(yùn)用高效的排序方法完成排序；

8.查找。主要講解順序查找、基于關(guān)鍵詞比較的查找和二叉樹(shù)查找，要求學(xué)生理解

各種查找算法的基本原理及基本的查找算法分析，能針對(duì)不同問(wèn)題靈活運(yùn)用較為高效的算法

進(jìn)行查找。

9.隨機(jī)數(shù)。通過(guò)本章的學(xué)習(xí)，使學(xué)生掌握簡(jiǎn)單隨機(jī)數(shù)產(chǎn)生方法，了解隨機(jī)數(shù)在密碼、

抽樣、仿真及數(shù)值分析等領(lǐng)域的應(yīng)用。

四、教學(xué)方式和考試方式

課堂講授為主，適量課后作業(yè)。提供PowerPoint課程講義。

考試方式為閉卷考試。任課教師根據(jù)學(xué)生的作業(yè)（10%）,期中（20%）和期末考試（70%）

三方面評(píng)定綜合成績(jī)?？己藘?nèi)容以算法的程序?qū)崿F(xiàn)為主。

五、參考教材

教材：

1.劉大有等，《數(shù)據(jù)結(jié)構(gòu)》（第2版），北京：高等教育出版社，2010年。

參考書(shū)目：

1.［美］維斯著，張懷勇等譯.數(shù)據(jù)結(jié)構(gòu)與算法分析C++描述（第三版），人民郵電出版

社,2007年.

2.［美］薩尼著，汪詩(shī)林等譯.數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用-C++語(yǔ)言描述，機(jī)械工業(yè)出版

社,2000年.

3.王紅梅，胡明，王濤編著.數(shù)據(jù)結(jié)構(gòu)（C++版）第2版，清華大學(xué)出版社,2011年.

六、教學(xué)內(nèi)容及課時(shí)分配

章節(jié)內(nèi)容學(xué)習(xí)要點(diǎn)備注

第一章數(shù)據(jù)結(jié)構(gòu)概念重點(diǎn)介紹算法

緒論算法的時(shí)間復(fù)雜性

（3學(xué)時(shí)）算法正確性證明分析

算法分析基礎(chǔ)

線性表的存儲(chǔ)結(jié)構(gòu)

第二章鏈表重點(diǎn)講授鏈?zhǔn)?/p>

線性表、堆棧和隊(duì)列堆棧堆棧和隊(duì)列的

（8學(xué)時(shí)）隊(duì)列實(shí)現(xiàn)

堆棧與隊(duì)列的應(yīng)用

遞歸的定義和執(zhí)行過(guò)程

第三章

遞歸實(shí)現(xiàn)與堆棧

遞歸

遞歸的效率分析

（4學(xué)時(shí)）

遞歸的應(yīng)用

第四章數(shù)組

重點(diǎn)講授數(shù)組

數(shù)組與字符串矩陣

與字符串

（4學(xué)時(shí)）字符串

樹(shù)的基本概念

二叉樹(shù)

第五章

線索二叉樹(shù)重點(diǎn)講授二叉

樹(shù)

樹(shù)和森林樹(shù)

（10學(xué)時(shí)）

壓縮與哈夫曼樹(shù)

樹(shù)的應(yīng)用

圖的基本概念

圖的存儲(chǔ)結(jié)構(gòu)

第六章

圖的遍歷算法重點(diǎn)講授圖的

圖

拓?fù)渑判虼鎯?chǔ)與遍歷

（8學(xué)時(shí)）

關(guān)鍵路徑與最短路徑問(wèn)題

最小支撐樹(shù)

插入排序

第七章交換排序

排序選擇排序

（4學(xué)時(shí)）合