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

數(shù)據(jù)結(jié)構(gòu)（C語言版本）

9/21/2023前言傳統(tǒng)的數(shù)值計(jì)算領(lǐng)域發(fā)展到非數(shù)值計(jì)算領(lǐng)域從簡單的數(shù)值發(fā)展到一般的符號，進(jìn)而發(fā)展到具有一定結(jié)構(gòu)的數(shù)據(jù)。針對每一種新的應(yīng)用領(lǐng)域的處理對象，如何選擇合適的數(shù)據(jù)表示（結(jié)構(gòu)），如何有效地組織計(jì)算機(jī)存貯，并在此基礎(chǔ)上又如何有效地實(shí)現(xiàn)對象之間的“運(yùn)算”關(guān)系。傳統(tǒng)的解決數(shù)值計(jì)算的許多理論、方法和技術(shù)已不能滿足解決非數(shù)值計(jì)算問題的需要，必須進(jìn)行新的探索。數(shù)據(jù)結(jié)構(gòu)就是研究和解決這些問題的重要基礎(chǔ)理論。因此，“數(shù)據(jù)結(jié)構(gòu)”課程已成為計(jì)算機(jī)類專業(yè)的一門重要專業(yè)基礎(chǔ)課。計(jì)算機(jī)應(yīng)用數(shù)據(jù)處理的對象目前面臨的主要問題9/21/2023第1章緒論[目的]介紹數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語以及學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義。[要求]了解本章介紹的各種基本概念和術(shù)語，掌握算法描述和分析的方法。[重點(diǎn)]了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算三方面的概念及相互關(guān)系。[難點(diǎn)]算法復(fù)雜度的分析方法。9/21/20231.1引言

眾所周知，二十世紀(jì)四十年代，電子數(shù)字計(jì)算機(jī)問世的直接原因是解決彈道學(xué)的計(jì)算問題。早期，電子計(jì)算機(jī)的應(yīng)用范圍，幾乎只局限于科學(xué)和工程的計(jì)算，其處理的對象是純數(shù)值性的信息，通常，人們把這類問題稱為數(shù)值計(jì)算。近三十年來，電子計(jì)算機(jī)的發(fā)展異常迅猛，這不僅表現(xiàn)在計(jì)算機(jī)本身運(yùn)算速度不斷提高、信息存儲量日益擴(kuò)大、價(jià)格逐步下降，更重要的是計(jì)算機(jī)廣泛地應(yīng)用于情報(bào)檢索、企業(yè)管理、系統(tǒng)工程等方面，已遠(yuǎn)遠(yuǎn)超出了科技計(jì)算的范圍，而滲透到人類社會活動的一切領(lǐng)域。與此相應(yīng)，計(jì)算機(jī)的處理對象也從簡單的純數(shù)值性信息發(fā)展到非數(shù)值性的和具有一定結(jié)構(gòu)的信息。9/21/2023因此，再把電子數(shù)字計(jì)算機(jī)簡單地看作是進(jìn)行數(shù)值計(jì)算的工具，把數(shù)據(jù)僅理解為純數(shù)值性的信息，就顯得太狹隘了?，F(xiàn)代計(jì)算機(jī)科學(xué)的觀點(diǎn)，是把計(jì)算機(jī)程序處理的一切數(shù)值的、非數(shù)值的信息，乃至程序統(tǒng)稱為數(shù)據(jù)（Data），而電子計(jì)算機(jī)則是加工處理數(shù)據(jù)（信息）的工具。由于數(shù)據(jù)的表示方法和組織形式直接關(guān)系到程序?qū)?shù)據(jù)的處理效率，而系統(tǒng)程序和許多應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)相當(dāng)復(fù)雜，處理對象又多為非數(shù)值性數(shù)據(jù)。因此，單憑程序設(shè)計(jì)人員的經(jīng)驗(yàn)和技巧已難以設(shè)計(jì)出效率高、可靠性強(qiáng)的程序。于是，就要求人們對計(jì)算機(jī)程序加工的對象進(jìn)行系統(tǒng)的研究，即研究數(shù)據(jù)的特性以及數(shù)據(jù)之間存在的關(guān)系——數(shù)據(jù)結(jié)構(gòu)（DateStructure）。9/21/20231.2數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡史及其在計(jì)算機(jī)科學(xué)中所處的地位發(fā)展史：1、“數(shù)據(jù)結(jié)構(gòu)”作為一門獨(dú)立的課程在國外是從1968年才開始設(shè)立的。2、1968年美國唐·歐·克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。9/21/2023地位：“數(shù)據(jù)結(jié)構(gòu)”在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。數(shù)據(jù)結(jié)構(gòu)這一門課的內(nèi)容不僅是一般程序設(shè)計(jì)（特別是非數(shù)值性程序設(shè)計(jì)）的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)。9/21/2023

1.3什么是數(shù)據(jù)結(jié)構(gòu)

計(jì)算機(jī)解決一個具體問題時，大致需要經(jīng)過下列幾個步驟：首先要從具體問題中抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)一個解此數(shù)學(xué)模型的算法（Algorithm），最后編出程序、進(jìn)行測試、調(diào)整直至得到最終解答。尋求數(shù)學(xué)模型的實(shí)質(zhì)是分析問題，從中提取操作的對象，并找出這些操作對象之間含有的關(guān)系，然后用數(shù)學(xué)的語言加以描述。計(jì)算機(jī)算法與數(shù)據(jù)的結(jié)構(gòu)密切相關(guān)，算法無不依附于具體的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法的選擇和效率。運(yùn)算是由計(jì)算機(jī)來完成，這就要設(shè)計(jì)相應(yīng)的插入、刪除和修改的算法。也就是說，數(shù)據(jù)結(jié)構(gòu)還需要給出每種結(jié)構(gòu)類型所定義的各種運(yùn)算的算法。直觀定義：數(shù)據(jù)結(jié)構(gòu)是研究程序設(shè)計(jì)中計(jì)算機(jī)操作的對象以及它們之間的關(guān)系和運(yùn)算的一門學(xué)科。9/21/20231.4基本概念和術(shù)語1．?dāng)?shù)據(jù)

數(shù)據(jù)是人們利用文字符號、數(shù)字符號以及其他規(guī)定的符號對現(xiàn)實(shí)世界的事物及其活動所做的描述。在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)的含義非常廣泛，我們把一切能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的信息，包括文字、表格、圖象等，都稱為數(shù)據(jù)。例如，一個個人書庫管理程序所要處理的數(shù)據(jù)可能是一張如表1-1所示的表格。9/21/2023

表1-1個人書庫9/21/20232．結(jié)點(diǎn)結(jié)點(diǎn)也叫數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單位。在程序中通常把結(jié)點(diǎn)作為一個整體進(jìn)行考慮和處理。例如，在表1-1所示的個人書庫中，為了便于處理，把其中的每一行（代表一本書）作為一個基本單位來考慮，故該數(shù)據(jù)由10個結(jié)點(diǎn)構(gòu)成。一般情況下，一個結(jié)點(diǎn)中含有若干個字段（也叫數(shù)據(jù)項(xiàng)）。例如，在表1-1所示的表格數(shù)據(jù)中，每個結(jié)點(diǎn)都有登錄號、書號、書名、作者、出版社和價(jià)格等六個字段構(gòu)成。字段是構(gòu)成數(shù)據(jù)的最小單位。9/21/20233．邏輯結(jié)構(gòu)結(jié)點(diǎn)和結(jié)點(diǎn)之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。在表1-1所示的表格數(shù)據(jù)中，各結(jié)點(diǎn)之間在邏輯上有一種線性關(guān)系，它指出了10個結(jié)點(diǎn)在表中的排列順序。根據(jù)這種線性關(guān)系，可以看出表中第一本書是什么書，第二本書是什么書，等等。4．存儲結(jié)構(gòu)數(shù)據(jù)在計(jì)算機(jī)中的存儲表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。在表1-1所示的表格數(shù)據(jù)在計(jì)算機(jī)中可以有多種存儲表示，例如，可以表示成數(shù)組，存放在內(nèi)存中；也可以表示成文件，存放在磁盤上，等等。9/21/20235．?dāng)?shù)據(jù)處理數(shù)據(jù)處理是指對數(shù)據(jù)進(jìn)行查找、插入、刪除、合并、排序、統(tǒng)計(jì)以及簡單計(jì)算等的操作過程。在早期，計(jì)算機(jī)主要用于科學(xué)和工程計(jì)算，進(jìn)入八十年代以后，計(jì)算機(jī)主要用于數(shù)據(jù)處理。據(jù)有關(guān)統(tǒng)計(jì)資料表明，現(xiàn)在計(jì)算機(jī)用于數(shù)據(jù)處理的時間比例達(dá)到80%以上，隨著時間的推移和計(jì)算機(jī)應(yīng)用的進(jìn)一步普及，計(jì)算機(jī)用于數(shù)據(jù)處理的時間比例必將進(jìn)一步增大。9/21/20236．?dāng)?shù)據(jù)結(jié)構(gòu)（DataStructure）數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素（DataElement）之間抽象化的相互關(guān)系和這種關(guān)系在計(jì)算機(jī)中的存儲表示（即所謂數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)），并對這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。為了敘述上的方便和避免產(chǎn)生混淆，通常我們把數(shù)據(jù)的邏輯結(jié)構(gòu)統(tǒng)稱為數(shù)據(jù)結(jié)構(gòu)，把數(shù)據(jù)的物理結(jié)構(gòu)統(tǒng)稱為存儲結(jié)構(gòu)（StorageStructure）。9/21/2023四種基本數(shù)據(jù)結(jié)構(gòu)：（1）集合：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個集合”的關(guān)系外，別無其他關(guān)系。（2）線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個對一個的關(guān)系。如：圖書館的書目檢索系統(tǒng)（3）樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在一個對多個的關(guān)系。如：計(jì)算機(jī)和人對奕問題工廠的組織管理（4）圖狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在多個對多個的關(guān)系。如：多叉路口的交通燈管理問題最短路徑問題

同一個邏輯結(jié)構(gòu)可以有不同的內(nèi)部存儲結(jié)構(gòu)；反之，數(shù)據(jù)的存儲結(jié)構(gòu)一定要映像數(shù)據(jù)之間的邏輯關(guān)系。數(shù)據(jù)結(jié)構(gòu)的形式定義：數(shù)據(jù)結(jié)構(gòu)是一個二元組data_structure=(D,S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。

9/21/2023例1一種結(jié)構(gòu)lineority=(K,R）K={k1,k2,k3,k4,k5,k6,k7}R={r}r={<k3,k1>,<k1,k5>,<k5,k6>,<k6,k4>,<k4,k2>,<k2,k7>}則有：k3->k1->k5->k6->k4->k2->k7一種線性結(jié)構(gòu)例2tree=(K,R)K={01,02,03,04,05,06,07,08}R={r}r={<01,02>,<01,03>,<02,04>,<02,05>,<03,06>,<03,07>,<07,08>}樹形結(jié)構(gòu)

9/21/2023例3graph=(K,R)K={01,02,03,04,05,06}R={r}r={<01,02>,<02,01>,<01,04>,<04,01>,<02,03>,<02,06>,<06,02>,<05,03>,<03,04>,<04,03>}圖形結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)分類：數(shù)據(jù)的邏輯結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)線性表樹形結(jié)構(gòu)圖一般線性表特殊線性表線性表推廣樹二叉樹有向圖無向圖線性表?xiàng)ｊ?duì)列串?dāng)?shù)組廣義表

9/21/2023數(shù)據(jù)的物理結(jié)構(gòu)方面二種類型：順序存儲結(jié)構(gòu)和非順序存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)：邏輯上相鄰的數(shù)據(jù)元素存儲在物理位置上相比鄰的存儲單元里，其關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)（向量、數(shù)組）。

非順序存儲結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)任意位置上存放，其關(guān)系用指針來鏈接，稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)-鏈表。按指針個數(shù)分為：單鏈表、雙向鏈表、多重鏈表

索引存儲結(jié)構(gòu)：按（地址關(guān)鍵字）的偶對集合，關(guān)鍵字是唯一標(biāo)識結(jié)點(diǎn)；地址指出該結(jié)點(diǎn)的存儲地址。

散列存儲結(jié)構(gòu)：根據(jù)結(jié)點(diǎn)關(guān)鍵字來直接算出該結(jié)點(diǎn)的存儲地址。9/21/20237．?dāng)?shù)據(jù)類型數(shù)據(jù)類型是一個值的集合和定義在這個值上的一組操作的總稱。數(shù)據(jù)類型是高級程序設(shè)計(jì)語言中的一個基本概念，它和數(shù)據(jù)結(jié)構(gòu)的概念密切相關(guān)。一方面，在程序設(shè)計(jì)語言中，每一個數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲方式以及允許進(jìn)行的運(yùn)算。可以認(rèn)為，數(shù)據(jù)類型是在程序設(shè)計(jì)中已經(jīng)實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。另一方面，在程序設(shè)計(jì)過程中，當(dāng)需要引入某種新的數(shù)據(jù)結(jié)構(gòu)時，總是借助編程語言所提供的數(shù)據(jù)類型來描述數(shù)據(jù)的存儲結(jié)構(gòu)。9/21/2023三元組表示(DSP)抽象數(shù)據(jù)類型（AbstractDataType,ADT)一個數(shù)學(xué)模型以及定義在該模型上的一組操作，它僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)。數(shù)據(jù)對象D上的關(guān)系集對D的基本操作集9/21/2023兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名其中，數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述，基本操作的定義格式為：基本操作名（參數(shù)表）初始條件：<初始條件描述>操作結(jié)果：<操作結(jié)果描述>9/21/2023ADTTriplet{數(shù)據(jù)對象：D={e1,e2,e3|e1,e2,e3屬于Elemset}數(shù)據(jù)關(guān)系：R1={<e1,e2>,<e2,e3>}基本操作：InitTriplet(&T,v1,v2,v3)操作結(jié)果：構(gòu)造了三元組T,元素e1,e2,和e3分別被賦以參數(shù)v1,v2和v3的值。DestroyTriplet(&T)操作結(jié)果：三元組T被銷毀。Get（T,I,&e)初始條件：三元組T已存在，1<=i<=3操作結(jié)果：用e返回T的第i元的值。}例抽象數(shù)據(jù)類型三元組的定義：9/21/2023簡單地說就是解決特定問題的方法.數(shù)值算法解決數(shù)值問題的算法如求解數(shù)值積分，求解線性方程組、求解代數(shù)方程、求解微分方程等。非數(shù)值算法解決非數(shù)值問題的算法如排序算法、查找算法、插入算法、刪除算法、遍歷算法等。數(shù)值算法和非數(shù)值算法并沒有嚴(yán)格的區(qū)別。遞歸算法和非遞歸算法8．算法從理論上講，任何遞歸算法都可以通過循環(huán)，堆棧等技術(shù)轉(zhuǎn)化為非遞歸算法。9/21/20231.5算法和算法的描述本書中“算法”和“程序”是通用的。1.5.1算法算法是執(zhí)行特定計(jì)算的有窮過程。特點(diǎn)動態(tài)有窮確定性輸入輸出可行性算法和程序的區(qū)別9/21/2023

1.5.2算法的描述

一個算法可以用自然語言、數(shù)字語言或約定的符號來描述，也可以用計(jì)算機(jī)高級程序語言來描述，如Pascal語言、C語言或偽代碼等。本書選用C語言作為描述算法的工具?，F(xiàn)簡單說明C語言的語法結(jié)構(gòu)如下：9/21/20231．預(yù)定義常量和類型：#defineTRUE1；#defineFALSE-1；#defineERRORNULL；1.5.2算法的描述

本書選用C語言作為描述算法的工具?，F(xiàn)簡單說明C語言的語法結(jié)構(gòu)如下：9/21/20232．函數(shù)的形式[數(shù)據(jù)類型]函數(shù)名（[形式參數(shù)]）[形式參數(shù)說明；]{內(nèi)部數(shù)據(jù)說明；執(zhí)行語句組；}/*函數(shù)名*/9/21/20233．賦值語句