數(shù)據(jù)結(jié)構(gòu)

徐虹/Jxgl/HomePage/Default.asp說明總學(xué)時：

64(學(xué)時)=50（課時）+14（實驗）行課時間:第1~13周周學(xué)時:平均每周4學(xué)時上機安排待定考試時間：課程結(jié)束上機安排13級計算機數(shù)媒專業(yè)1、2班指導(dǎo)老師:時間：5-11周地點:計算機學(xué)院機房教材與參考書王紅梅,胡明,王濤.數(shù)據(jù)結(jié)構(gòu)（C++版）第2版.清華大學(xué)出版社萬健，《數(shù)據(jù)結(jié)構(gòu)實用教程》（C++版），電子工業(yè)出版社嚴(yán)蔚敏，《數(shù)據(jù)結(jié)構(gòu)》，清華大學(xué)出版社CliffordA.Shaffer,《數(shù)據(jù)結(jié)構(gòu)與算法分析》，電子工業(yè)出版社SartajSahni,《數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用》,機械工業(yè)出版社嚴(yán)蔚敏，《數(shù)據(jù)結(jié)構(gòu)題集》，清華大學(xué)出版社3.課程的內(nèi)容與組織1.數(shù)據(jù)結(jié)構(gòu)的研究對象課程簡介數(shù)據(jù)是現(xiàn)實世界的數(shù)字化研究數(shù)據(jù)在計算機中的表示、關(guān)聯(lián)、存儲與處理方法2.課程的性質(zhì)與定位數(shù)據(jù)組織與結(jié)構(gòu)是計算機科學(xué)最基本內(nèi)容，是人才信息素質(zhì)的脊梁培養(yǎng)數(shù)據(jù)抽象能力，算法設(shè)計能力以及構(gòu)造算法思維方法基本概念、基本結(jié)構(gòu)、基本技術(shù)三層次用C++描述算法，突出算法實質(zhì)例題、習(xí)題、典型題例、實習(xí)范例、課程設(shè)計全方位訓(xùn)練1.數(shù)據(jù)結(jié)構(gòu)的研究對象

我們生活在一個物質(zhì)的世界，計算機工作者又面對著數(shù)字的世界，如果將物質(zhì)世界中的事與物數(shù)字化，那么它們在計算機中的表現(xiàn)均為數(shù)據(jù)。這些數(shù)據(jù)來源于現(xiàn)實，表征著具體的意義，而且在計算機中有著統(tǒng)一的表示方法，因而成為被計算機程序處理的符號集合。研究數(shù)據(jù)在計算機中的表示方法、關(guān)聯(lián)方法、存儲方法以及在其上的典型處理方法，就構(gòu)成了數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容。

2.《數(shù)據(jù)結(jié)構(gòu)》課程的性質(zhì)與地位由于數(shù)據(jù)是計算機處理的對象，使用計算機的過程就是對數(shù)據(jù)進行加工處理的過程，因而數(shù)據(jù)的組織與結(jié)構(gòu)被確立為計算機科學(xué)中最為基本內(nèi)容。80年代初,《數(shù)據(jù)結(jié)構(gòu)》課程就已成為國內(nèi)計算機專業(yè)教學(xué)計劃中的核心課程。

人類解決問題的思維方式可分為推理方式和算法方式兩大類。推理方式憑借公理系統(tǒng)思維方法通過數(shù)學(xué)訓(xùn)練得到。算法方式則是憑借構(gòu)造性思維，從具體操作規(guī)范入手，通過操作過程的構(gòu)造實施來解決特定問題。

數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)過程，是算法構(gòu)造性思維方法的訓(xùn)練過程，技能培養(yǎng)的重要程度不亞于知識傳授。本門課程教學(xué)難點在于讓學(xué)生理解、習(xí)慣算法構(gòu)造思維方法。培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力，算法設(shè)計能力以及創(chuàng)造性思維方法，才能夠舉一反三、觸類旁通，從而達(dá)到應(yīng)用知識解決復(fù)雜問題的目的。

數(shù)據(jù)結(jié)構(gòu)是重要的專業(yè)基礎(chǔ)課，是計算機科學(xué)的核心課程，是計算機理論與技術(shù)的重要基石。該課程在大學(xué)二年級下學(xué)期開設(shè)，具有承上啟下的重要作用，既要對前一年學(xué)習(xí)的軟件技術(shù)進行總結(jié)提高，又要為后續(xù)專業(yè)課程提供基礎(chǔ)。它貫通始終，是計算機科學(xué)與技術(shù)人才素質(zhì)培養(yǎng)框架中的中堅課程，對學(xué)生的軟件開發(fā)能力培養(yǎng)有至關(guān)重要的作用，將為學(xué)生今后的專業(yè)生涯打下牢固基礎(chǔ)。2.《數(shù)據(jù)結(jié)構(gòu)》課程的性質(zhì)與地位3.課程的內(nèi)容與組織以抽象數(shù)據(jù)類型為中心，采用面向?qū)ο蟮男掠^點，將教學(xué)內(nèi)容分為基本概念、基本結(jié)構(gòu)、基本算法三個層次，并貫穿了計算機科學(xué)中的一些重要的問題求解技術(shù)，符合認(rèn)知規(guī)律。使用熟悉的標(biāo)準(zhǔn)C++作為算法描述的語言，使之與大多數(shù)院校講授的第一語言銜接，便于將讀者的注意力集中在算法的理解上。這就使數(shù)據(jù)結(jié)構(gòu)的表示得以簡化，突出了算法表示的實質(zhì)。例題、習(xí)題、典型題例、實習(xí)范例、課程設(shè)計全方位訓(xùn)練4.成績計算平時成績:30%

考勤+作業(yè)+半期考試+上機+實驗報告+課堂表現(xiàn)考試成績:70%學(xué)生的考核資格按下述原則審查：

學(xué)生有以下情況之一者，不能參加課程成績考核，該課程的考核成績以零分處理。在確定學(xué)籍處理、授予學(xué)士學(xué)位時，該門課程以考核不及格門次參加統(tǒng)計。全期曠課累計達(dá)該課程教學(xué)時數(shù)五分之一（含五分之一）以上者；全期缺交該課程任課教師布置作業(yè)三分之一（含三分之一）以上者；或全期所交該課程作業(yè)，雖達(dá)到任課教師布置作業(yè)三分之二以上，但所交作業(yè)的準(zhǔn)確度、整潔度有二分之一不合格者；全期缺做該課程實習(xí)、實驗或缺交實習(xí)、實驗報告達(dá)三分之一（含三分之一）以上者；或全期參加該課程實習(xí)、實驗，所交實習(xí)、實驗報告都在三分之二以上，但有二分之一不合格者；未經(jīng)批準(zhǔn)或未辦理選課手續(xù)，擅自修讀該門課程者。目錄

第一章：緒論第二章：線性表第三章：棧和隊列第四章：串、數(shù)組和廣義表第五章：樹第六章：圖第七章：查找

第八章：內(nèi)部排序第一章緒論數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念算法和算法分析程序設(shè)計的實質(zhì)是什么?數(shù)據(jù)表示：將數(shù)據(jù)存儲在計算機（內(nèi)存）中數(shù)據(jù)處理：處理數(shù)據(jù)，設(shè)計方案（算法）數(shù)據(jù)結(jié)構(gòu)問題起源于程序設(shè)計

利用計算機求解問題的一般過程?計算機不能分析問題并產(chǎn)生問題的解決方案，必須由人來分析問題，確定問題的解決方案，編寫程序，然后讓計算機執(zhí)行程序最終獲得問題的解。1.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的引論例1圖書館的書目檢索系統(tǒng)自動化問題在書目自動檢索系統(tǒng)中可以建立一張按等錄順序號排列的書目文件和三張分別按書名、作者名和分類號順序排列的索引表，如下所示：001002003004高等數(shù)學(xué)理論力學(xué)高等數(shù)學(xué)線形代數(shù)樊映川羅遠(yuǎn)祥華羅庚欒汝書S01L01S01S02高等數(shù)學(xué)理論力學(xué)線形代數(shù)001,003,…002,…004,…LS002,001,003特點：計算機按某個特定的要求進行查詢.處理對象之間存在一種簡單的線形關(guān)系,這類模型可以稱為簡單的線形數(shù)據(jù)結(jié)構(gòu).按書名排列樊映川華羅庚欒汝書001,003,004,按作者排列按索引號排列例2:計算機和人的對弈問題對奕的過程是在一定的規(guī)則下隨機進行的,因此,計算機必須對對弈過程之中可能發(fā)生的情況以及相應(yīng)的對策都考慮周全.這個關(guān)系不是線形的,從一個棋盤可以派生出幾個格局,如下圖:

“樹根”是對奕開始之前的棋盤格局,而所有的“葉子”是可能出現(xiàn)的結(jié)局,對奕的過程就是從樹根沿樹叉到達(dá)某個葉子的過程.******************(a)棋盤格式示例(b)井字棋對弈樹的局部*例3七巧板涂色問題

如何表示區(qū)域之間的鄰接關(guān)系？結(jié)論：綜合上面三個例子,描述這類非數(shù)值計算性問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程,而是諸如表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu).數(shù)據(jù)結(jié)構(gòu)定義:

數(shù)據(jù)結(jié)構(gòu)是一門非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等的學(xué)科.數(shù)據(jù)結(jié)構(gòu)的地位

《數(shù)據(jù)結(jié)構(gòu)》是計算機科學(xué)中一門綜合性的專業(yè)基礎(chǔ)課。可以認(rèn)為數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機硬件、計算機軟件三者之間的一門核心課程。1.2基本概念數(shù)據(jù)（Data)

客觀事物的符號表示，能輸入到計算機中并被計算機中程序處理的符號的總稱。數(shù)據(jù)元素(Dataelement)

數(shù)據(jù)的基本單位，可由數(shù)據(jù)項組成。數(shù)據(jù)類型(DataType)

是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念，在高級語言中，用以刻畫（程序）操作對象的特性。是一個值的集合和定義在這個值集上的一組操作的總稱。數(shù)據(jù)對象(DataObject)

性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。數(shù)據(jù)結(jié)構(gòu)(DataStructure)

相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素之間的相互關(guān)系稱為結(jié)構(gòu)。有下列四種基本結(jié)構(gòu)：（1）集合（2）線形結(jié)構(gòu)（3）樹形結(jié)構(gòu)（4）圖狀結(jié)構(gòu)(網(wǎng)狀結(jié)構(gòu)）。

集合線性樹圖數(shù)據(jù)結(jié)構(gòu)的二元組表示：Data_Structure=(D,S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集數(shù)據(jù)結(jié)構(gòu)類型數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義：Data_Structure=[D,S,P]

其中：D是數(shù)據(jù)元素的有限集

S是上下關(guān)系的有限集

P是對數(shù)據(jù)對象的基本操作數(shù)據(jù)的物理結(jié)構(gòu)（存儲結(jié)構(gòu)），數(shù)據(jù)結(jié)構(gòu)基本操作的實現(xiàn)；數(shù)據(jù)的存儲結(jié)構(gòu)：位、元素和數(shù)據(jù)域數(shù)據(jù)結(jié)構(gòu)的存儲形式有：順序存儲鏈?zhǔn)酱鎯壿嫿Y(jié)構(gòu)例學(xué)生選課問題該問題可以用三張數(shù)據(jù)表來表示，每張表中每條記錄為數(shù)據(jù)元素如表中數(shù)據(jù)元素是無序的，則數(shù)據(jù)表構(gòu)成集合結(jié)構(gòu)如表中數(shù)據(jù)元素是有序的，則數(shù)據(jù)表構(gòu)成線性結(jié)構(gòu)學(xué)生表課程表選課表學(xué)號姓名課程號課程名稱學(xué)號課程號成績S0001張三C0001數(shù)據(jù)結(jié)構(gòu)S0001C000185S0002李四C0002操作系統(tǒng)S0001C000376S0005王五C0003編譯原理S0002C000190C0004數(shù)據(jù)庫原理S0002C000483S0003C000292邏輯結(jié)構(gòu)例三維實體造型問題左圖的機械零件可以分解成三個基本的實體模型通過布爾運算+和-操作得到右圖構(gòu)成了一個樹型的數(shù)據(jù)結(jié)構(gòu)，每一個節(jié)點為一個基本實體模型或通過布爾運算得到的復(fù)合實體模型邏輯結(jié)構(gòu)例地圖表示問題左圖的地圖經(jīng)抽象可以得到右圖的結(jié)構(gòu)右圖構(gòu)成了圖狀的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)例分別用順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)來存儲數(shù)列“10,20,30,40”數(shù)列的順序存儲結(jié)構(gòu)數(shù)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖，是面向問題的，反映了數(shù)據(jù)內(nèi)部的構(gòu)成方式；數(shù)據(jù)的存儲結(jié)構(gòu)屬于具體實現(xiàn)的視圖，是面向計算機的。一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲結(jié)構(gòu)來存儲，而采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率往往是不同的。

本書討論非數(shù)值問題的數(shù)據(jù)組織和處理，主要內(nèi)容如下：（1）數(shù)據(jù)的邏輯結(jié)構(gòu)：線性表、樹、圖等數(shù)據(jù)結(jié)構(gòu)，其核心是如何組織待處理的數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系；（2）數(shù)據(jù)的存儲結(jié)構(gòu)：如何將線性表、樹、圖等數(shù)據(jù)結(jié)構(gòu)存儲到計算機的存儲器中，其核心是如何有效地存儲數(shù)據(jù)以及數(shù)據(jù)之間的邏輯關(guān)系；（3）算法：如何基于數(shù)據(jù)的某種存儲結(jié)構(gòu)實現(xiàn)插入、刪除、查找等基本操作，其核心是如何有效地處理數(shù)據(jù)；（4）常用數(shù)據(jù)處理技術(shù)：查找技術(shù)、排序技術(shù)、索引技術(shù)等。數(shù)據(jù)類型綜述數(shù)據(jù)類型可以分為原子類型——值不可以分解結(jié)構(gòu)類型——值由若干成分按某種結(jié)構(gòu)組成。抽象數(shù)據(jù)類型（ADT）

ADT是一個值的集合和定義在這個值集上的一組操作的總稱。包括：原子類型、固定聚合類型和可變聚合類型。是與具體計算機內(nèi)部表示和實現(xiàn)方式無關(guān)的數(shù)據(jù)類型是由一個邏輯上的數(shù)學(xué)模型以及定義在該模型上的一組操作構(gòu)成可以用三元組定義(D,S,P)D是數(shù)據(jù)對象S是D上的關(guān)系集P是對D的基本操作集1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)基本概念—抽象數(shù)據(jù)類型在軟件系統(tǒng)開發(fā)的全過程中，對客觀現(xiàn)實中存在的事物，存在三個觀察層面應(yīng)用層是用戶通過物理觀察得到的客觀事物的視圖，是可以用自然語言描述的，或用圖形、圖像、音頻、視頻等物理量表達(dá)的在概念層次上的數(shù)據(jù)。邏輯層（抽象層）是從應(yīng)用層次抽象出來的數(shù)據(jù)視圖，利用抽象數(shù)據(jù)類型進行形式化描述。實現(xiàn)層明確地表示出了數(shù)據(jù)的組織與存儲結(jié)構(gòu)，并用某種具體的程序設(shè)計語言進行代碼實現(xiàn)。抽象數(shù)據(jù)類型在設(shè)計ADT時，把ADT的定義、設(shè)計和實現(xiàn)分開來。定義部分只包含數(shù)據(jù)的邏輯結(jié)構(gòu)和所允許的操作集合，一方面，ADT的使用者依據(jù)這些定義來使用ADT，即通過操作集合對該ADT進行操作；另一方面，ADT的實現(xiàn)者依據(jù)這些定義來完成該ADT各種操作的具體實現(xiàn)。抽象數(shù)據(jù)類型例ADTSet //集合的抽象數(shù)據(jù)類型{

數(shù)據(jù)對象：D＝{ai|ai∈ElemType,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R={ai≠aj|ai,aj∈D}基本操作： Init() 操作結(jié)果：構(gòu)造一個空的集合。 Destroy() 操作結(jié)果：銷毀集合。 IsEmpty() 操作結(jié)果：判斷集合是否為空，如為空，則返回TRUE；

否則返回FALSE。

Insert(e) 操作結(jié)果：在集合中加入一個元素。如元素已存在，

返回FALSE；否則返回TRUE。

Remove(e) 操作結(jié)果：在集合中移除一個元素。如元素存在，

則返回TRUE；否則返回FALSE。 IsMember(e) 操作結(jié)果：判斷在集合中是否存在元素。 FindFirst(&e) 操作結(jié)果：找到集合中的第一個元素。

如成功，返回TRUE；如果集合為空，返回FALSE抽象數(shù)據(jù)類型例 FindFirst(&e) 操作結(jié)果：找到集合中的第一個元素。

如成功，返回TRUE；如果集合為空，返回FALSE FindNext(&e) 初始條件：已經(jīng)執(zhí)行過FindFirst或FindNext操作

操作結(jié)果：在上一次查找的前提下，找到集合中的下

一個元素；如成功，返回TRUE；如上次查找已到最后

一個元素，返回FALSE。

Union(s) 操作結(jié)果：與另一個集合s做并運算，返回并集。 Intersection(s)操作結(jié)果：與另一個集合s做交運算，返回交集。 Difference(s) 操作結(jié)果：與另一個集合s做差運算，返回差集。}數(shù)據(jù)操作描述數(shù)據(jù)的基本操作：

插入：在數(shù)據(jù)結(jié)構(gòu)的指定位置添加新的數(shù)據(jù)元素。

刪除：去掉數(shù)據(jù)結(jié)構(gòu)中某個指定的數(shù)據(jù)元素。

更新：改變數(shù)據(jù)結(jié)構(gòu)中某個數(shù)據(jù)元素的值。

查找：在數(shù)據(jù)結(jié)構(gòu)中尋找某個滿足特定要求的數(shù)據(jù)元素。

排序：重新安排數(shù)據(jù)元素的邏輯順序關(guān)系，使之值按從小到大或從大到小的順序排列。操作的分類加工型操作——操作改變了（操作之前的）結(jié)構(gòu)的值。引用型操作——不改變值，只是查詢或求得結(jié)構(gòu)的值。操作的描述

語言的描述預(yù)定義常量和類型

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼

typedefintStatus;數(shù)據(jù)結(jié)構(gòu)的表示用類型定義（typedef）描述，數(shù)據(jù)元素類型約定為ElemType，可以是C語言中任何數(shù)據(jù)類型?；静僮鞯乃惴ㄓ靡韵滦问胶瘮?shù)來描述函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）

{

//算法說明語句序列

}//函數(shù)名

C++中操作的描述賦值語句循環(huán)語句選擇語句注釋結(jié)束語句輸入和輸出語句邏輯運算約定

用C++描述算法函數(shù)形式函數(shù)類型函數(shù)名(形參及類型說明){

函數(shù)語句部分return(表達(dá)式值)；

}函數(shù)中的形式參數(shù)有兩種傳值方式若為一般變量名，則為單向傳值參數(shù)，若在變量前面增加“&”符號，則為雙向傳地址參數(shù)。例如有一個函數(shù)為voidswap(&i,&j,k)，則i，j為雙向傳地址參數(shù)，k為單向傳值參數(shù)。函數(shù)的說明部分與函數(shù)的實現(xiàn)部分分離在C++中，用函數(shù)來描述算法時，為使之與面象對象的程序設(shè)計相匹配，一般將函數(shù)的說明部分與函數(shù)的實現(xiàn)部分分離