ds-1《數(shù)據(jù)結(jié)構(gòu)C++版》PPT及練習(xí)答案

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個(gè)概念，在高級語言中，用以刻畫（程序）操作對象的特性。是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。數(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)（存儲(chǔ)結(jié)構(gòu)），數(shù)據(jù)結(jié)構(gòu)基本操作的實(shí)現(xiàn)；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：位、元素和數(shù)據(jù)域數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)形式有：順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)邏輯結(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)例三維實(shí)體造型問題左圖的機(jī)械零件可以分解成三個(gè)基本的實(shí)體模型通過布爾運(yùn)算+和-操作得到右圖構(gòu)成了一個(gè)樹型的數(shù)據(jù)結(jié)構(gòu)，每一個(gè)節(jié)點(diǎn)為一個(gè)基本實(shí)體模型或通過布爾運(yùn)算得到的復(fù)合實(shí)體模型邏輯結(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)來存儲(chǔ)數(shù)列“10,20,30,40”數(shù)列的順序存儲(chǔ)結(jié)構(gòu)數(shù)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖，是面向問題的，反映了數(shù)據(jù)內(nèi)部的構(gòu)成方式；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)屬于具體實(shí)現(xiàn)的視圖，是面向計(jì)算機(jī)的。一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)，而采用不同的存儲(chǔ)結(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ù)的存儲(chǔ)結(jié)構(gòu)：如何將線性表、樹、圖等數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)到計(jì)算機(jī)的存儲(chǔ)器中，其核心是如何有效地存儲(chǔ)數(shù)據(jù)以及數(shù)據(jù)之間的邏輯關(guān)系；（3）算法：如何基于數(shù)據(jù)的某種存儲(chǔ)結(jié)構(gòu)實(shí)現(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是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。包括：原子類型、固定聚合類型和可變聚合類型。是與具體計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)方式無關(guān)的數(shù)據(jù)類型是由一個(gè)邏輯上的數(shù)學(xué)模型以及定義在該模型上的一組操作構(gòu)成可以用三元組定義(D,S,P)D是數(shù)據(jù)對象S是D上的關(guān)系集P是對D的基本操作集1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)基本概念—抽象數(shù)據(jù)類型在軟件系統(tǒng)開發(fā)的全過程中，對客觀現(xiàn)實(shí)中存在的事物，存在三個(gè)觀察層面應(yīng)用層是用戶通過物理觀察得到的客觀事物的視圖，是可以用自然語言描述的，或用圖形、圖像、音頻、視頻等物理量表達(dá)的在概念層次上的數(shù)據(jù)。邏輯層（抽象層）是從應(yīng)用層次抽象出來的數(shù)據(jù)視圖，利用抽象數(shù)據(jù)類型進(jìn)行形式化描述。實(shí)現(xiàn)層明確地表示出了數(shù)據(jù)的組織與存儲(chǔ)結(jié)構(gòu)，并用某種具體的程序設(shè)計(jì)語言進(jìn)行代碼實(shí)現(xiàn)。抽象數(shù)據(jù)類型在設(shè)計(jì)ADT時(shí)，把ADT的定義、設(shè)計(jì)和實(shí)現(xiàn)分開來。定義部分只包含數(shù)據(jù)的邏輯結(jié)構(gòu)和所允許的操作集合，一方面，ADT的使用者依據(jù)這些定義來使用ADT，即通過操作集合對該ADT進(jìn)行操作；另一方面，ADT的實(shí)現(xiàn)者依據(jù)這些定義來完成該ADT各種操作的具體實(shí)現(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)造一個(gè)空的集合。 Destroy() 操作結(jié)果：銷毀集合。 IsEmpty() 操作結(jié)果：判斷集合是否為空，如為空，則返回TRUE；

否則返回FALSE。

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

返回FALSE；否則返回TRUE。

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

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

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

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

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

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

一個(gè)元素，返回FALSE。

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

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

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

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

查找：在數(shù)據(jù)結(jié)構(gòu)中尋找某個(gè)滿足特定要求的數(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é)束語句輸入和輸出語句邏輯運(yùn)算約定

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

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

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