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

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

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

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

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

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

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

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

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