大數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)（C語言版）大數(shù)據(jù)結(jié)構(gòu)的基本概念PAGE16PAGE17實用標(biāo)準(zhǔn)文檔文案大全第1章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)結(jié)構(gòu)之美無處不在：說到結(jié)構(gòu)，任何一件事物都有自己的結(jié)構(gòu)，就如可以看得見且觸摸得到的課桌、椅子，還有看不見卻也存在的化學(xué)中的分子、原子。可見，一件事物只要存在，就一定會有自己的結(jié)構(gòu)。一幅畫的生成，作家在揮毫潑墨之前，首先要在數(shù)尺素絹之上做結(jié)構(gòu)上的統(tǒng)籌規(guī)劃、謀篇布局。一件衣服的制作，如果在制作之前沒有對衣服的袖、領(lǐng)、肩、襟、身等各個部位周密籌劃，形成一個合理的結(jié)構(gòu)系統(tǒng)，便無法縫制出合體的衣服。還有教育管理系統(tǒng)的結(jié)構(gòu)、通用技術(shù)的學(xué)科結(jié)構(gòu)和課堂教學(xué)結(jié)構(gòu)等。試想一下，管理大量數(shù)據(jù)是否也需要用到數(shù)據(jù)結(jié)構(gòu)呢？本章知識要點：數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)類型和抽象數(shù)據(jù)類型算法和算法分析1.1數(shù)據(jù)結(jié)構(gòu)的基本概念計算機科學(xué)是一門研究數(shù)據(jù)表示和數(shù)據(jù)處理的科學(xué)。數(shù)據(jù)是計算機化的信息，它是計算機可以直接處理的最基本和最重要的對象。無論是進(jìn)行科學(xué)計算，還是數(shù)據(jù)處理、過程控制、對文件的存儲和檢索以及數(shù)據(jù)庫技術(shù)等計算機應(yīng)用，都是對數(shù)據(jù)進(jìn)行加工處理的過程。因此，要設(shè)計出一個結(jié)構(gòu)良好而且效率較高的程序，必須研究數(shù)據(jù)的特性、數(shù)據(jù)間的相互關(guān)系及其對應(yīng)的存儲表示，并利用這些特性和關(guān)系設(shè)計出相應(yīng)的算法和程序。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第1頁。計算機在發(fā)展的初期，其應(yīng)用圍是數(shù)值計算，所處理的數(shù)據(jù)都是整型、實型和布爾型等簡單數(shù)據(jù)，以此為加工、處理對象的程序設(shè)計稱為數(shù)值型程序設(shè)計。隨著計算技術(shù)的發(fā)展，計算機逐漸進(jìn)入到商業(yè)、制造業(yè)等其他領(lǐng)域，廣泛地應(yīng)用于數(shù)據(jù)處理和過程控制中。與此相對應(yīng)，計算機所處理的數(shù)據(jù)也不再是簡單的數(shù)值，而是字符串、圖形、圖像、語音和視頻等復(fù)雜的數(shù)據(jù)。這些復(fù)雜的數(shù)據(jù)不僅量大，而且具有一定的結(jié)構(gòu)。例如，一幅圖像是一個由簡單數(shù)值組成的矩陣，一個圖形中的幾何坐標(biāo)可以組成表。此外，語言編譯過程中所使用的棧、符號表和語法樹，操作系統(tǒng)中用到的隊列、磁盤目錄樹等，都是有結(jié)構(gòu)的數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)所研究的就是這些有結(jié)構(gòu)的數(shù)據(jù)，因此，數(shù)據(jù)結(jié)構(gòu)知識無論是對研制系統(tǒng)軟件還是對開發(fā)應(yīng)用軟件來說，都非常重要，是學(xué)習(xí)軟件知識和提高軟件設(shè)計水平的重要基礎(chǔ)。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第1頁。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第2頁。

1.1.1數(shù)據(jù)結(jié)構(gòu)的研究容大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第2頁。在計算機發(fā)展的初期，人們使用計算機的目的主要是處理數(shù)值計算問題。當(dāng)使用計算機來解決一個具體問題時，一般需要經(jīng)過如下幾個步驟：首先要從該具體問題中抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計或選擇一個求解此數(shù)學(xué)模型的算法，最后編出程序進(jìn)行調(diào)試、測試，得到最終的解答。例如，用計算機進(jìn)行全球天氣預(yù)報時，可以通過求解一組球面坐標(biāo)系下的二階橢圓偏微分方程來實現(xiàn)。隨著計算機應(yīng)用領(lǐng)域的擴大和軟、硬件的發(fā)展，非數(shù)值計算問題變得越來越重要。據(jù)統(tǒng)計，目前非數(shù)值計算問題的處理占用了90%以上的機器時間。這類問題涉及的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程式來描述。因此，解決這類問題的關(guān)鍵不再是數(shù)學(xué)分析和計算方法，而是要設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)主要研究非數(shù)值計算問題，下面通過具體實例加以說明。例1-1學(xué)生信息檢索系統(tǒng)。當(dāng)系統(tǒng)需要查找某個學(xué)生的有關(guān)情況，或需要查詢某個專業(yè)或年級的學(xué)生的有關(guān)情況時，只要建立了相關(guān)的數(shù)據(jù)結(jié)構(gòu)，按照某種算法編寫了相關(guān)程序，就可以實現(xiàn)計算機自動檢索。為此，可以在學(xué)生信息檢索系統(tǒng)中建立一按學(xué)號順序排列的學(xué)生信息表和若干分別按、專業(yè)和年級順序排列的索引表，如表1-1～表1-4所示。由這4表構(gòu)成的文件便是學(xué)生信息檢索系統(tǒng)的數(shù)學(xué)模型。表1-1學(xué)生基本信息表學(xué)號姓名性別專業(yè)年級2011010001崔志永男計算機科學(xué)與技術(shù)2011級2011030005淑芳女軟件工程2011級2012040010陸麗女?dāng)?shù)學(xué)與應(yīng)用數(shù)學(xué)2012級2012030012志強男軟件工程2012級2012010012淑芳女計算機科學(xué)與技術(shù)2012級2013040001王寶國男數(shù)學(xué)與應(yīng)用數(shù)學(xué)2013級2013010001石國利男計算機科學(xué)與技術(shù)2013級2013030001文茜女軟件工程2013級大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第3頁。表1-2索引表大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第3頁。姓名索引號姓名索引號姓名索引號崔志永1志強4石國利7淑芳2，5王寶國6文茜8陸麗3表1-3專業(yè)索引表專業(yè)索引號計算機科學(xué)與技術(shù)1，5，7軟件工程2，4，8數(shù)學(xué)與應(yīng)用數(shù)學(xué)3，6表1-4年級檢索表年級索引號年級索引號2011級1，22013級6，7，82012級3，4，5諸如此類的還有查詢問題、考試成績查詢問題和企業(yè)進(jìn)銷存管理系統(tǒng)等。在這類文檔管理系統(tǒng)的數(shù)學(xué)模型中，計算機處理的對象之間通常存在著一種簡單的線性關(guān)系，因此，這類數(shù)學(xué)模型可稱為線性的數(shù)據(jù)結(jié)構(gòu)。例1-2計算機系統(tǒng)組成結(jié)構(gòu)，如圖1-1所示。圖1-1計算機系統(tǒng)組成結(jié)構(gòu)圖計算機系統(tǒng)由硬件系統(tǒng)和軟件系統(tǒng)組成，硬件系統(tǒng)由CPU、存儲器、輸入/輸出設(shè)備和外設(shè)組成，軟件系統(tǒng)由系統(tǒng)軟件和應(yīng)用軟件組成。如果把它們視為數(shù)據(jù)元素，則這些元素之間呈現(xiàn)的是一種層次關(guān)系，從上到下按層進(jìn)行展開，可形成一棵倒立的“樹”，最上層是“樹根”，依層向下射出“結(jié)點”和“樹葉”。同樣是樹結(jié)構(gòu)的還有某個單位的組織機構(gòu)、國家行政區(qū)域規(guī)劃、書籍目錄等。在這類問題中，計算機處理的對象是樹結(jié)構(gòu)，元素之間是一對多的層次關(guān)系，這類數(shù)學(xué)模型被稱為樹的數(shù)據(jù)結(jié)構(gòu)。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第4頁。例1-3最短路徑問題。從城市A到城市B有多條線路可達(dá)，但每條線路的交通成本不同，那么，應(yīng)怎樣選擇一條線路，使得從城市A出發(fā)到達(dá)城市B所花費的費用最低呢？可以將這類問題抽象為圖的最短路徑問題。如圖1-2所示，圖中的頂點代表城市，有向邊代表兩個城市之間的通路，邊上的權(quán)值代表兩個城市之間的交通費。求解A到B的最低費用，就是要在有向圖從A點到B點的多條路徑中，尋找到一條各邊權(quán)值之和最小的路徑，即求該圖的最短路徑。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第4頁。同樣是圖結(jié)構(gòu)的還有網(wǎng)絡(luò)工程圖、教學(xué)計劃編排問題和比賽編排問題等。在這類問題中，元素之間是多對多的網(wǎng)狀關(guān)系，這類數(shù)學(xué)模型被稱為圖的數(shù)據(jù)結(jié)構(gòu)。由以上3個例子可見，描述這類非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。因此，可以說“數(shù)據(jù)結(jié)構(gòu)”課程主要是在研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作的學(xué)科。1968年，“數(shù)據(jù)結(jié)構(gòu)”第一次在美國被確定為一門獨立的課程。同年，著名的美國計算機科學(xué)家D.E.Knuth教授編著了《計算機程序設(shè)計技巧》的第一卷《基本算法》，這是第一本系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)以及運算的著作。20世紀(jì)60年代末到70年代初，出現(xiàn)了大型程序，程序與數(shù)據(jù)相對獨立，結(jié)構(gòu)化程序設(shè)計成為程序設(shè)計方法學(xué)的主要容，人們越來越感到數(shù)據(jù)結(jié)構(gòu)的重要，認(rèn)為程序設(shè)計的實質(zhì)就是為所處理的問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，并加之一種好的算法。數(shù)據(jù)結(jié)構(gòu)在計算機科學(xué)中是一門綜合性較強的專業(yè)基礎(chǔ)課，是操作系統(tǒng)、數(shù)據(jù)庫、人工智能等課程的基礎(chǔ)。同時，數(shù)據(jù)結(jié)構(gòu)技術(shù)也廣泛地應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)以及各種工程技術(shù)領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)涉及的知識面十分廣，可以認(rèn)為它是介于數(shù)學(xué)、計算機硬件和軟件之間的一門核心課程。數(shù)據(jù)結(jié)構(gòu)與其他課程間的關(guān)系如圖1-3所示。圖1-2最短路徑問題圖1-3數(shù)據(jù)結(jié)構(gòu)與其他課程的關(guān)系學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的是為了了解計算機處理對象的特性，將實際問題中所涉及的處理對象在計算機中表示出來，并對它們進(jìn)行處理。對于計算機專業(yè)的學(xué)生，不學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，幾乎無法繼續(xù)前行，因為幾乎所有的程序和軟件都要用到某種或某些數(shù)據(jù)結(jié)構(gòu)。例如，在面向?qū)ο蟪绦蛟O(shè)計中，一個對象在嚴(yán)格意義上來說就是一個數(shù)據(jù)結(jié)構(gòu)，而哪個程序不使用對象呢？可以這樣說，不懂?dāng)?shù)據(jù)結(jié)構(gòu)，就編不出什么像樣的程序和軟件。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第5頁。此外，數(shù)據(jù)結(jié)構(gòu)在軟件工程和計算機學(xué)科的其他領(lǐng)域也發(fā)揮著非常重要甚至是極為關(guān)鍵的作用。例如，對大型數(shù)據(jù)庫的管理、為互聯(lián)網(wǎng)提供索引服務(wù)、云計算和云存儲等都需要廣泛使用數(shù)據(jù)結(jié)構(gòu)。在軟件工程領(lǐng)域，數(shù)據(jù)結(jié)構(gòu)被單獨提取出來，作為軟件設(shè)計與實現(xiàn)過程的一個階段。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第5頁。1.1.2基本概念和術(shù)語在系統(tǒng)地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)知識之前，先來學(xué)習(xí)一下數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項等基本概念和術(shù)語的確切含義。數(shù)據(jù)（Data）是信息的載體，能夠被計算機識別、存儲和加工處理。它是計算機程序加工的原料，應(yīng)用程序處理各種各樣的數(shù)據(jù)。計算機科學(xué)中，數(shù)據(jù)就是計算機加工處理的對象，它可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。數(shù)值數(shù)據(jù)是一些整數(shù)、實數(shù)或復(fù)數(shù)，主要用于工程計算、科學(xué)計算和商務(wù)處理等；非數(shù)值數(shù)據(jù)包括字符、文字、圖形、圖像和語音等。數(shù)據(jù)元素（DataElement）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點、頂點和記錄等。例如，學(xué)生信息檢索系統(tǒng)里學(xué)生信息表中的一個記錄、計算機系統(tǒng)組成結(jié)構(gòu)中狀態(tài)樹的一個狀態(tài)以及最短路徑問題中的一個頂點等，都被稱為一個數(shù)據(jù)元素。有時，一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。例如，學(xué)生信息檢索系統(tǒng)中學(xué)生信息表的每一個數(shù)據(jù)元素都是一個學(xué)生記錄，它包括學(xué)生的學(xué)號、、性別、專業(yè)和年級數(shù)據(jù)項。這些數(shù)據(jù)項可以分為兩種：一種叫做初等數(shù)據(jù)項，如學(xué)生的性別、年級等，這些數(shù)據(jù)項是數(shù)據(jù)處理時不能再分割的最小單位；另一種叫做組合數(shù)據(jù)項，如學(xué)生的成績，它可以再劃分為由多門不同課程成績組成的更小項。數(shù)據(jù)項（Data

Item）是組成數(shù)據(jù)元素的有獨立含義且不可分割的最小單位，如表1-1中的學(xué)號、和年級等都是數(shù)據(jù)項。數(shù)據(jù)項有名和值之分，數(shù)據(jù)項名是一個數(shù)據(jù)項的標(biāo)識，用變量定義，而數(shù)據(jù)項值是它的一個可能取值。例如，表1-1中的2011010001是數(shù)據(jù)項“學(xué)號”的一個取值。數(shù)據(jù)項具有一定的類型，依數(shù)據(jù)項的取值類型而定。數(shù)據(jù)對象（Data

Object）是相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)集合的一個子集。在某個具體問題中，數(shù)據(jù)元素具有相同的性質(zhì)（但元素值不一定相等），屬于同一個數(shù)據(jù)對象，數(shù)據(jù)元素是數(shù)據(jù)元素類的一個實例。例如，在最短路徑問題中，所有的頂點都是一個數(shù)據(jù)元素類，頂點A和頂點B各自代表一個城市，是該數(shù)據(jù)元素類中的兩個實例，其數(shù)據(jù)元素的值分別為A和B。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第6頁。數(shù)據(jù)結(jié)構(gòu)（Data

Structure）是指互相之間存在著一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。在計算機中，數(shù)據(jù)元素不是孤立的，它們之間存在著這樣或那樣的關(guān)系，這種數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)。一個數(shù)據(jù)結(jié)構(gòu)包含兩個要素：一個是數(shù)據(jù)元素的集合；另一個是關(guān)系的集合。在形式上，數(shù)據(jù)結(jié)構(gòu)通?？梢圆捎靡粋€二元組來表示。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第6頁。數(shù)據(jù)結(jié)構(gòu)的形式定義為一個二元組：Data_Structure=(D,R)其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)。1．邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型，與數(shù)據(jù)的存儲形式無關(guān)。根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常有下列4類基本的邏輯結(jié)構(gòu)，如圖1-4所示。（a）集合結(jié)構(gòu)（b）線性結(jié)構(gòu)

（c）樹結(jié)構(gòu)

（d）圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)圖1-44類基本邏輯結(jié)構(gòu)示意圖（1）集合結(jié)構(gòu)。結(jié)構(gòu)中數(shù)據(jù)元素間的關(guān)系是“屬于同一個集合”。集合是元素關(guān)系極為松散的一種結(jié)構(gòu)。（2）線性結(jié)構(gòu)。結(jié)構(gòu)中數(shù)據(jù)元素之間存在著一對一的線性關(guān)系。（3）樹結(jié)構(gòu)。結(jié)構(gòu)中數(shù)據(jù)元素之間存在著一對多的層次關(guān)系。（4）圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。結(jié)構(gòu)中數(shù)據(jù)元素之間存在著多對多的任意關(guān)系。例1-4有一數(shù)據(jù)結(jié)構(gòu)采用二元組描述為D_S=(D,R)，其中：D={a,b,c,d,e,f,g}R={<e,d>,<d,c>,<c,a>,<a,b>,<b,f

>,<f,g>}根據(jù)已知條件，對應(yīng)的圖形如圖1-5所示。圖1-5對應(yīng)D_S的邏輯結(jié)構(gòu)示意圖從例1-4可以看出，一個數(shù)據(jù)元素有且只有一個前驅(qū)（除第1個結(jié)點外），有且僅有一個后繼（除最后一個結(jié)點外）。數(shù)據(jù)元素之間為一對一的關(guān)系，即線性關(guān)系。這種數(shù)據(jù)結(jié)構(gòu)就是線性結(jié)構(gòu)。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第7頁。由于集合是數(shù)據(jù)元素之間關(guān)系極為松散的一種結(jié)構(gòu)，因此也可用其他結(jié)構(gòu)來表示。故數(shù)據(jù)的4類基本邏輯結(jié)構(gòu)可概括如下：大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第7頁。線性結(jié)構(gòu)——線性表、棧、隊、串、數(shù)組、廣義表非線性結(jié)構(gòu)——集合結(jié)構(gòu)、樹、圖2．存儲結(jié)構(gòu)研究數(shù)據(jù)結(jié)構(gòu)的目的是為了在計算機中實現(xiàn)對它的操作，為此還需要研究如何在計算機中表示一個數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（又稱為映像）稱為數(shù)據(jù)的存儲結(jié)構(gòu)（或稱物理結(jié)構(gòu)）。它所研究的是數(shù)據(jù)結(jié)構(gòu)在計算機中的實現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中元素的表示及元素間關(guān)系的表示。數(shù)據(jù)的存儲結(jié)構(gòu)可采用順序存儲或鏈?zhǔn)酱鎯Φ姆椒ā＃?）順序存儲結(jié)構(gòu)。是把邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中，由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)是一種最基本的存儲表示方法，通常借助于程序設(shè)計語言中的數(shù)組來實現(xiàn)。（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)。對邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過附設(shè)的指針字段來表示，由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。鏈?zhǔn)酱鎯Y(jié)構(gòu)通常借助于程序設(shè)計語言中的指針來實現(xiàn)。如圖1-6所示為復(fù)數(shù)5.0-5.3i的兩種存儲結(jié)構(gòu)示意圖。除了通常采用的順序存儲方法和鏈?zhǔn)酱鎯Ψ椒ㄍ?，有時為了查找的方便，還會采用索引存儲方法和散列存儲方法。3．?dāng)?shù)據(jù)運算討論數(shù)據(jù)結(jié)構(gòu)的目的是為了在計算機中實現(xiàn)操作運算。為了能有效地處理數(shù)據(jù)，提高數(shù)據(jù)運算的執(zhí)行效率，應(yīng)按一定的邏輯結(jié)構(gòu)把數(shù)據(jù)組織起來，并選擇適當(dāng)?shù)拇鎯Ψ椒▽?shù)據(jù)存儲到計算機，然后對其進(jìn)行運算。圖1-6復(fù)數(shù)5.0-5.3i的兩種存儲結(jié)構(gòu)示意圖大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第8頁。數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上的，每一種邏輯結(jié)構(gòu)都有一個運算的集合，如插入、刪除和修改等。這些運算實際上是在數(shù)據(jù)元素上施加一系列抽象的操作（只考慮這些操作要做什么，而無須考慮如何做），只有在確定了存儲結(jié)構(gòu)后，才能具體實現(xiàn)這些運算。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第8頁。數(shù)據(jù)的運算主要有修改、插入、刪除、查找和排序等。其中，查找運算是一個很重要的運算過程，修改、插入、刪除和排序中都包含著查找運算。排序本身就是元素之間通過查找相互比較的過程，修改、插入和刪除則要通過查找來確定其操作的位置。1.1.3數(shù)據(jù)結(jié)構(gòu)課程的容數(shù)據(jù)結(jié)構(gòu)與數(shù)學(xué)、計算機硬件和軟件有十分密切的關(guān)系。數(shù)據(jù)結(jié)構(gòu)技術(shù)也廣泛應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)及各種工程技術(shù)領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)課程集中討論軟件開發(fā)過程中的設(shè)計階段，同時涉及編碼和分析階段的若干基本問題。此外，為了構(gòu)造出好的數(shù)據(jù)結(jié)構(gòu)及其實現(xiàn)，還需要考慮數(shù)據(jù)結(jié)構(gòu)及其實現(xiàn)的評價與選擇。因此，數(shù)據(jù)結(jié)構(gòu)的容可歸納為3個部分：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)運算。簡而言之，按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的存儲方式將其存入計算機的存儲器中，并在這些數(shù)據(jù)上定義一個運算集，是數(shù)據(jù)結(jié)構(gòu)課程的基本容，如表1-5所示。表1-5數(shù)據(jù)結(jié)構(gòu)課程的基本容容層次數(shù)據(jù)表示數(shù)據(jù)處理抽象邏輯結(jié)構(gòu)基本運算實現(xiàn)存儲結(jié)構(gòu)算法評價不同數(shù)據(jù)結(jié)構(gòu)的比較及算法分析數(shù)據(jù)結(jié)構(gòu)主要研究怎樣合理地組織數(shù)據(jù)，建立合適的結(jié)構(gòu)，提高執(zhí)行程序所用的時空效率。數(shù)據(jù)結(jié)構(gòu)的核心技術(shù)是分解與抽象。通過對問題的抽象，舍棄數(shù)據(jù)元素的具體容，從而得到邏輯結(jié)構(gòu)；同樣，通過分解，將數(shù)據(jù)處理劃分成各種功能實現(xiàn)，再通過抽象舍棄實現(xiàn)細(xì)節(jié)，就得到數(shù)據(jù)運算的定義。由此可將許多具體問題轉(zhuǎn)換為數(shù)據(jù)結(jié)構(gòu)，這是一個從具體（即具體問題）到抽象（即數(shù)據(jù)結(jié)構(gòu)）的過程。然后，通過增加對實現(xiàn)細(xì)節(jié)的考慮，進(jìn)一步得到存儲結(jié)構(gòu)和實現(xiàn)運算，從而完成設(shè)計任務(wù)，這是一個從抽象（即數(shù)據(jù)結(jié)構(gòu)）到具體（即具體實現(xiàn)）的過程。熟練地掌握這兩個過程，是數(shù)據(jù)結(jié)構(gòu)課程在專業(yè)技能培養(yǎng)方面的基本目標(biāo)。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第9頁。數(shù)據(jù)結(jié)構(gòu)課程不僅講授數(shù)據(jù)信息在計算機中的組織和表示方法，同時也重在培養(yǎng)高效解決復(fù)雜問題的能力。不同的數(shù)據(jù)結(jié)構(gòu)適用于不同的應(yīng)用，例如，B樹就特別適用于數(shù)據(jù)庫和文件系統(tǒng)，而哈希表則常常在編譯器里面使用等。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第9頁。1.2數(shù)據(jù)類型和抽象數(shù)據(jù)類型運用抽象數(shù)據(jù)類型來描述數(shù)據(jù)結(jié)構(gòu)，則在設(shè)計一個軟件系統(tǒng)時，不必首先考慮其中包含的數(shù)據(jù)對象以及操作在不同處理器中的表示和實現(xiàn)細(xì)節(jié)，而可以在構(gòu)成軟件系統(tǒng)的每個相對獨立的模塊上定義一組數(shù)據(jù)和相應(yīng)的操作（把這些數(shù)據(jù)的表示和操作細(xì)節(jié)留在模塊部解決），在更高的層次上進(jìn)行軟件的分析和設(shè)計，從而提高軟件的整體性能和利用率。數(shù)據(jù)結(jié)構(gòu)是一種抽象，它將數(shù)據(jù)的個體屬性去除，只考慮數(shù)據(jù)元素之間的關(guān)系。通過步步抽象，可不斷地突出“做什么”，而將“怎么做”隱藏起來，即將一切用戶不必了解的細(xì)節(jié)封裝起來，從而簡化了問題。所以，抽象是程序設(shè)計中最基本的思想方法。1.2.1數(shù)據(jù)類型數(shù)據(jù)類型（DataType）是一個值的集合和定義在這個值集上的一組操作的總稱。數(shù)據(jù)類型中定義了兩個集合，即該類型的取值圍及該類型中可允許使用的一組運算。數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念。在用高級語言編寫的程序中，每個變量、常量或表達(dá)式都有一個它所屬的確定的數(shù)據(jù)類型。數(shù)據(jù)類型顯式或隱含地規(guī)定了在程序執(zhí)行期間變量或表達(dá)式所有可能的取值圍，以及在這些值上允許進(jìn)行的操作。在高級程序設(shè)計語言中，數(shù)據(jù)類型可分為兩類：一類是原子類型，另一類則是結(jié)構(gòu)類型。原子類型的值是不可分解的，例如，C語言中的整型、字符型、浮點型和雙精度型等基本類型，分別用關(guān)鍵字int、char、float和double表示。而結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成的，因此是可分解的，并且它的成分可以是原子的，也可以是結(jié)構(gòu)的。例如，數(shù)組的值由若干分量組成，每個分量可以是整數(shù)，也可以是數(shù)組等。在某種意義上，數(shù)據(jù)結(jié)構(gòu)可以看成是一種數(shù)據(jù)類型，而數(shù)據(jù)類型則可以看成是由一種數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作所組成的。1.2.2抽象數(shù)據(jù)類型抽象就是抽取出實際問題的本質(zhì)，將無限多的關(guān)系種類里面的非關(guān)鍵屬性去除，只取其中的共性來設(shè)計數(shù)據(jù)結(jié)構(gòu)。例如，對于數(shù)據(jù)元素A、B、C而言，它們之間的關(guān)系可以是A在B的前面，B在C的前面；或者C在B的前面，B在A的前面。顯然，對于個體的數(shù)據(jù)元素而言，這是兩種不同的結(jié)構(gòu)。但拋開個體數(shù)據(jù)元素就會發(fā)現(xiàn)，這兩種結(jié)構(gòu)實際上是一種數(shù)據(jù)結(jié)構(gòu)類型——線性結(jié)構(gòu)。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第10頁。抽象數(shù)據(jù)類型（AbstractDataType，ADT）是指一個數(shù)學(xué)模型及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性，而與其在計算機部如何表示和實現(xiàn)無關(guān)，即不論其部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，就不會影響到其外部的使用。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第10頁。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念。例如，各種計算機都擁有的整數(shù)類型就是一個抽象數(shù)據(jù)類型，盡管在不同處理器上的實現(xiàn)方法可能不同，但由于其定義的數(shù)學(xué)特性相同，在用戶看來都是相同的。因此，“抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。但在另一方面，抽象數(shù)據(jù)類型的疇更廣，它不再局限于前述各處理器中已定義并實現(xiàn)的數(shù)據(jù)類型，還包括用戶在設(shè)計軟件系統(tǒng)時自己定義的數(shù)據(jù)類型。為了提高軟件的重用性，在近代程序設(shè)計方法學(xué)中，要求在構(gòu)成軟件系統(tǒng)的每個相對獨立的模塊上，定義一組數(shù)據(jù)和應(yīng)用于這些數(shù)據(jù)上的一組操作，并在模塊的部給出這些數(shù)據(jù)的表示及其操作的細(xì)節(jié)，而在模塊的外部使用的只是抽象的數(shù)據(jù)及抽象的操作。這也就是面向?qū)ο蟮某绦蛟O(shè)計方法。抽象數(shù)據(jù)類型的定義可以由一種數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作所組成，而數(shù)據(jù)結(jié)構(gòu)又包括數(shù)據(jù)元素及元素間的關(guān)系，因此，抽象數(shù)據(jù)類型一般可以由數(shù)據(jù)對象、數(shù)據(jù)對象上關(guān)系的集合以及對數(shù)據(jù)對象的基本操作的集合來定義。抽象數(shù)據(jù)類型的特征是使用與實現(xiàn)相分離，實行封裝和信息隱蔽。也就是說，在設(shè)計抽象數(shù)據(jù)類型時，要把類型的定義與其實現(xiàn)分離開來。和數(shù)據(jù)結(jié)構(gòu)的形式定義相對應(yīng)，抽象數(shù)據(jù)類型可用以下三元組表示：ADT=(D,S,P)其中，D是數(shù)據(jù)元素的有限集；S是D上的關(guān)系集；P是對D的基本操作集。抽象數(shù)據(jù)類型的定義格式如下：ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>結(jié)構(gòu)關(guān)系：<結(jié)構(gòu)關(guān)系的定義>基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名例1-5給出線性表的抽象數(shù)據(jù)類型的定義。ADTList{數(shù)據(jù)元素：所有ai屬于同一數(shù)據(jù)對象，i=1，2，…，n，n≥0；結(jié)構(gòu)關(guān)系：所有數(shù)據(jù)元素ai（i=1，2，…，n-1）存在次序關(guān)系<ai,ai+1>，a1無前趨，an無后繼；基本操作：設(shè)L為List，則有大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第11頁。InitList(L)：初始化線性表；大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第11頁。ListLength(L)：求線性表的表長；GetData(L,i)：取線性表的第i個元素；InsList(L,i,b)：在線性表的第i個位置插入元素b；DelList(L,i)：刪除線性表的第i個數(shù)據(jù)元素；}ADTList;1.3算法和算法分析著名的計算機科學(xué)家N.Wirth教授給出了一個對計算機科學(xué)的發(fā)展影響深遠(yuǎn)的公式：算法+數(shù)據(jù)結(jié)構(gòu)=程序，足以說明算法和數(shù)據(jù)結(jié)構(gòu)關(guān)系緊密，是程序設(shè)計的兩大要素，二者相輔相成，缺一不可。在進(jìn)行算法設(shè)計時，先要確定相應(yīng)的數(shù)據(jù)結(jié)構(gòu)；而在討論某一種數(shù)據(jù)結(jié)構(gòu)時，也必然要涉及相應(yīng)的算法。下面就從算法特性、算法描述和算法性能分析3個方面對算法進(jìn)行介紹。1.3.1算法特性算法（Algorithm）是為解決特定問題而規(guī)定的一系列操作。一個算法應(yīng)該具有下列5個重要特性：（1）有窮性。一個算法必須在執(zhí)行有窮步之后結(jié)束，即必須在有限時間完成。（2）確定性。算法的每一步必須有確切的定義，無二義性。算法的執(zhí)行對應(yīng)著的相同的輸入僅有唯一路徑。（3）可行性。算法中的每一步都可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次得以實現(xiàn)。（4）輸入。一個算法具有零個或多個輸入，這些輸入取自特定的數(shù)據(jù)對象集合。（5）算法的含義與程序十分相似，但又有區(qū)別。一個程序不一定滿足有窮性，例如操作系統(tǒng)，只要整個系統(tǒng)不遭破壞，它將永遠(yuǎn)不會停止，即使沒有作業(yè)需要處理，它仍處于動態(tài)等待中。因此，操作系統(tǒng)不是一個算法。另一方面，程序中的指令必須是機器可執(zhí)行的，而算法中的指令則無此限制。算法代表了對問題的解，而程序則是算法在計算機上的特定實現(xiàn)。一個算法若用程序設(shè)計語言來描述，則它就是一個程序。例1-6不符合有窮性。voidtest(void){大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第12頁。 intn=8;大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第12頁。 while(n%8==0) n+=8; printf("%d\n",n); }例1-7無輸出的算法沒有任何意義。GetSum(intnum){ intsum=0; for(i=1;i<=num;i++) sum+=i;}當(dāng)用算法解決某一特定類型問題時，可以選擇不同的數(shù)據(jù)結(jié)構(gòu)，而選擇的恰當(dāng)與否會直接影響到算法的效率。反之，一種數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣可由不同算法的執(zhí)行效果來體現(xiàn)。一個算法的優(yōu)劣應(yīng)從以下幾個方面來評價：（1）正確性。在合理的數(shù)據(jù)輸入下，能夠在有限的運行時間得到正確的結(jié)果。（2）可讀性。一個算法應(yīng)當(dāng)思路清晰、層次分明、簡單明了和易讀易懂?？勺x性強的算法有助于人們對算法的理解，而難懂的算法易于隱藏錯誤，且難以調(diào)試和修改。（3）健壯性。當(dāng)輸入不合法數(shù)據(jù)時，應(yīng)能做出正確反應(yīng)或適當(dāng)處理，不致引起嚴(yán)重后果。（4）高效性。高效性包括時間和空間兩個方面。時間高效是指算法設(shè)計合理，執(zhí)行效率高，可以用時間復(fù)雜度來度量；空間高效是指算法占用的存儲容量合理，可以用空間復(fù)雜度來度量。1.3.2算法描述算法可以使用各種不同的方法來描述。最簡單的方法是使用自然語言。用自然語言來描述算法的優(yōu)點是簡單，且便于人們閱讀算法，缺點是不夠嚴(yán)謹(jǐn)?？梢允褂贸绦蛄鞒虉D、N-S圖等算法描述工具，其特點是描述過程簡潔明了。用以上兩種方法描述的算法不能夠直接在計算機上執(zhí)行。若要將它轉(zhuǎn)換成可執(zhí)行的程序，還有一個編程的問題?？梢灾苯邮褂媚撤N程序設(shè)計語言來描述算法，不過直接使用程序設(shè)計語言并不容易，而且不太直觀，常常需要借助于注釋才能使人看明白。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第13頁。為了解決理解與執(zhí)行之間的矛盾，常常使用一種稱為偽碼語言的描述方法來進(jìn)行算法描述。偽碼語言介于程序設(shè)計語言和自然語言之間，忽略程序設(shè)計語言中一些嚴(yán)格的語法規(guī)則與描述細(xì)節(jié)，因此，它比程序設(shè)計語言更容易描述和被人理解，且比自然語言更接近程序設(shè)計語言。它雖然不能直接執(zhí)行，但可以很容易地被轉(zhuǎn)換成程序設(shè)計語言。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第13頁。例1-8設(shè)計一個算法，打印出所有的“水仙花數(shù)”?！八苫〝?shù)”是指一個3位數(shù)，其各位數(shù)字的立方和等于該數(shù)本身。算法設(shè)計如下：for(n=100～999){ 每個數(shù)分解出個位，十位，百位; 令k=個位數(shù)*100+十位數(shù)*10+百位數(shù);p=(個位數(shù))3+(十位數(shù))3+(百位數(shù))3; if(k==p) printf(n);}大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第14頁。

1.3.3算法性能分析大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第14頁。通過算法分析，可判斷一個算法實際是否可行，并可在同一問題存在多個算法時幫助選擇性能較優(yōu)的算法。評價一個算法的性能，主要從算法執(zhí)行時間與占用存儲空間大小兩方面考慮，即從算法執(zhí)行所需的時間和存儲空間來判斷一個算法的優(yōu)劣。當(dāng)然，設(shè)計者希望選用一個占用存儲空間小、運行時間短并且其他性能也好的算法，但在現(xiàn)實中很難做到十全十美，因為上述要求有時會相互抵觸。要節(jié)約算法的執(zhí)行時間，往往要以犧牲更多的空間為代價；而為了節(jié)省空間，又可能要以犧牲更多的時間為代價。因此，只能根據(jù)具體情況有所側(cè)重。若該程序使用次數(shù)較少，則應(yīng)力求算法簡明易懂，易于轉(zhuǎn)換為上機的程序。當(dāng)一個算法被轉(zhuǎn)換成程序并在計算機上執(zhí)行時，其運行所需要的時間主要取決于下列因素：硬件的速度。書寫程序的語言。編譯程序所生成的目標(biāo)代碼質(zhì)量。代碼優(yōu)化較好的編譯程序，其生成的程序質(zhì)量較高。問題的規(guī)模。例如，求100以的素數(shù)與求1000以的素數(shù)，其執(zhí)行時間必然是不同的。1．算法耗費的時間和語句頻度一個算法的執(zhí)行時間是指算法中所有語句執(zhí)行時間的總和。每條語句的執(zhí)行時間等于該條語句的執(zhí)行次數(shù)乘以執(zhí)行一次所耗用的實際時間。語句頻度是指該語句在一個算法中被重復(fù)執(zhí)行的次數(shù)。一個算法的時間耗費就是該算法中所有語句頻度之和。例1-9求兩個n階矩陣的乘積算法。for(i=1;i<=n;i++) //頻度為n+1for(j=1;j<=n;j++) //頻度為n*(n+1){c[i][j]=0; //頻度為n2 for(k=1;k<=n;k++) //頻度為n2*(n+1) c[i][j]=c[i][j]+a[i][k]*b[k][j] //頻度為n3該算法中，所有語句的頻度之和，即算法的執(zhí)行時間，用T(n)表示，則大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第15頁。T(n)=2n3+3n2+2n+1大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第15頁。2．問題規(guī)模和算法的時間復(fù)雜度為便于比較同一問題的不同算法，通常以算法中基本操作重復(fù)執(zhí)行的頻度作為度量標(biāo)準(zhǔn)。原操作是指從算法中選取一種對所研究問題是基本運算的操作，用問題規(guī)模增加的函數(shù)來表征，以此作為時間量度。算法中，語句的總執(zhí)行次數(shù)f(n)是問題規(guī)模n的函數(shù)，根據(jù)f(n)隨n的變化情況，可確定T(n)的數(shù)量級（OrderofMagnitude）。這里用O來表示數(shù)量級，給出算法的時間復(fù)雜度概念。算法的時間復(fù)雜度T(n)是該算法的時間量度，記作T(n)=O(f(n))它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復(fù)雜度，簡稱時間復(fù)雜度。數(shù)學(xué)符號O的嚴(yán)格數(shù)學(xué)定義為：若T(n)和f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則T(n)=O(f(n))表示：存在正的常數(shù)C和no，使得當(dāng)n≥no時，滿足0≤T(n)≤Cf(n）。例1-10賦值語句。++x;s=0;語句頻度為1，時間復(fù)雜度為O(1)。例1-11簡單循環(huán)。for(i=1;i<=n;++i){ ++X;S+=X;}語句頻度為n，時間復(fù)雜度為O(n)。例1-12雙重循環(huán)。for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}語句頻度為n*n，時間復(fù)雜度為O(n2)。例1-13又一個雙重循環(huán)。for(j=1;j<=n;++j)for(k=1;k<=j;++k){++x;s+=x;}大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第16頁。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第16頁。語句頻度近似于n2/2，所以時間復(fù)雜度仍為O(n2)。3．常用算法的時間復(fù)雜度數(shù)據(jù)結(jié)構(gòu)中常用的時間復(fù)雜度頻率計數(shù)有以下幾種：一個沒有循環(huán)的算法，其基本運算次數(shù)與問題規(guī)模n無關(guān)，記作O(1)，也稱作常數(shù)階；一個只有一重循環(huán)的算法，其基本運算次數(shù)與問題規(guī)模n呈線性增長關(guān)系，記作O(n)，也稱作線性階；其余常用的還有平方階O(n2)、立方階O(n3)、對數(shù)階O(log2n)和指數(shù)階O(2n)等。不同數(shù)量級對應(yīng)的時間復(fù)雜度值存在著如下關(guān)系：O(1)<O(log2n)<O(n)<O(n*log2n)<O(n2)<O(n3)<O(2n)<O(n!)不同數(shù)量級對應(yīng)的時間復(fù)雜度曲線如圖1-7所示。一般情況下，隨著n增大，T(n)增長較慢的算法為最優(yōu)的算法。顯然，時間復(fù)雜度為指數(shù)階O(2n)的算法效率極低，當(dāng)n值稍大時，程序?qū)o法應(yīng)用。圖1-7常見數(shù)量級的漸近增長趨勢4．算法的空間復(fù)雜度作為量度，簡稱空間復(fù)雜度。它也是問題規(guī)模n的函數(shù)，記作S(n)=O(f(n))，表示的是該算法在運行過程中所耗費的輔助存儲空間。如果一個算法所耗費的存儲空間與問題規(guī)模n無關(guān)，記作S(n)=O(1)。一個算法所耗費的存儲空間包括3類：算法本身所占用的存儲空間、算法的輸入/輸出所占用的存儲空間和算法在運行過程中臨時占用的輔助存儲空間。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第17頁。算法輸入/輸出所占用的存儲空間，由算法解決的問題規(guī)模決定，不隨算法的改變而改變。算法本身所占用的存儲空間與實現(xiàn)算法的程序代碼長度有關(guān)，代碼越長，占用的存儲空間越大。算法在運行過程中臨時占用的輔助存儲空間隨算法的不同而不同，有的不隨問題規(guī)模的大小改變，而有的與解決問題的規(guī)模n有關(guān)，它隨n大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第17頁。例1-14將一維數(shù)組a中的n個數(shù)據(jù)逆序存放到原數(shù)組中，給出實現(xiàn)該問題的兩種算法。算法1：for(i=0;i<n;i++)b[i]=a[n-i-1];for(i=0;i<n;i++)a[i]=b[i];算法2：for(i=0;i<n/2;i++){ t=a[i]; a[i]=a[n-i-1]; a[n-i-1]=t;}算法1的空間復(fù)雜度為O(n)，需要一個大小為n的輔助數(shù)組b。算法2的空間復(fù)雜度為O(1)，僅需要一個變量t，與問題規(guī)模沒有關(guān)系。1.4本章小結(jié)本章介紹了數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語，以及算法和算法時間復(fù)雜度的分析方法。主要容如下：1．掌握數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算集合3個部分。2．邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的區(qū)別大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第18頁。邏輯結(jié)構(gòu)定義了數(shù)據(jù)元素之間的邏輯關(guān)系。存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機中的實現(xiàn)。一種邏輯結(jié)構(gòu)可采用不同的存儲方式存放在計算機中，但無論哪種存儲方式，都必須能反映出要求的邏輯關(guān)系。大數(shù)據(jù)結(jié)構(gòu)的基本概念全文共21頁，當(dāng)前為第18頁。3．抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型是指由用戶定義的表示應(yīng)用問題的數(shù)學(xué)模型，以及定義在這個模型上的一組操作的總稱。具體包括3部分：數(shù)據(jù)對象、數(shù)據(jù)對象上關(guān)系的集合以及對數(shù)據(jù)對象的基本操作的集合。4．