數(shù)據(jù)結(jié)構(gòu)討論的是數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)討論的是數(shù)據(jù)的邏輯結(jié)構(gòu)第1頁，共21頁，2023年，2月20日，星期六1.1數(shù)據(jù)結(jié)構(gòu)

1.1.1數(shù)據(jù)結(jié)構(gòu)隨著計算機軟、硬件的發(fā)展，計算機的應(yīng)用范圍在不斷擴大，計算機所處理的數(shù)據(jù)的數(shù)量也在不斷擴大，計算機所處理的數(shù)據(jù)已不再是單純的數(shù)值數(shù)據(jù)，而更多的是非數(shù)值數(shù)據(jù)。需要處理的數(shù)據(jù)并不是雜亂無章的，它們一定有內(nèi)在的聯(lián)系，只有弄清楚它們之間的本質(zhì)的聯(lián)系，才能使用計算機對大量的數(shù)據(jù)進行有效的處理。第2頁，共21頁，2023年，2月20日，星期六某電信公司的市話用戶信息表格如下圖所示：序號用戶名電話號碼用戶住址街道名門牌號00001萬方林3800235北京西路165900002吳金平3800667北京西路209900003王

冬5700123瑤湖大道198700004王

三5700567瑤湖大道200800005江

凡8800129學(xué)府大道5035這里序號、用戶名、電話號碼等項稱為基本項，它是有獨立意義的最小標識單位，而用戶住址稱為組合項，組合項是由一個或多個基本項或組合項組成，是有獨立意義的標識單位，每一行稱為一個結(jié)點，每一個組合項稱為一個字段。使用計算機處理用戶信息表中的數(shù)據(jù)時，必須弄清楚下面3個問題：第3頁，共21頁，2023年，2月20日，星期六1數(shù)據(jù)的邏輯結(jié)構(gòu)這些數(shù)據(jù)之間有什么樣的內(nèi)在聯(lián)系？除最前和最后兩個結(jié)點之外，表中所有其它的結(jié)點都有且僅有一個和它相鄰位于它之前的一個結(jié)點，也有且僅有一個和它相鄰位于它之后的一個結(jié)點，這些就是用戶信息表的邏輯結(jié)構(gòu)。2數(shù)據(jù)的存儲結(jié)構(gòu)

將用戶信息表中的所有結(jié)點存入計算機時，就必須考慮存儲結(jié)構(gòu)，使用C語言進行設(shè)計時，常見的方式是用一個結(jié)構(gòu)數(shù)組來存儲整個用戶信息表，每一個數(shù)組元素是一個結(jié)構(gòu)，它對應(yīng)于用戶信息表中的一個結(jié)點。數(shù)據(jù)在計算機的存儲方式稱為存儲結(jié)構(gòu)。第4頁，共21頁，2023年，2月20日，星期六3數(shù)據(jù)的運算集合

數(shù)據(jù)處理必涉及到相關(guān)的運算，在上述用戶信息表中，可以有刪除一個用戶、增加一個用戶和查找某個用戶等操作。應(yīng)該明確指明這些操作的含義。比如刪除操作，是刪除序號為5的用戶還是刪除用戶名為王三的用戶是應(yīng)該明確定義的，如果需要可以定義兩個不同的刪除操作，為一批數(shù)據(jù)定義的所有運算（或稱操作）構(gòu)成一個運算（操作）集合。對待處理的數(shù)據(jù)，只有分析清楚上面3個方面的問題，才能進行有效的處理！

數(shù)據(jù)結(jié)構(gòu)就是指按一定的邏輯結(jié)構(gòu)組成的一批數(shù)據(jù)，使用某種存儲結(jié)構(gòu)將這批數(shù)據(jù)存儲于計算機中，并在這些數(shù)據(jù)上定義了一個運算集合。第5頁，共21頁，2023年，2月20日，星期六1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)和數(shù)據(jù)之間所存在的邏輯關(guān)系，它可以用一個二元組B=（K，R）來表示，其中K是數(shù)據(jù)、即結(jié)點的有限集合；R是集合K上關(guān)系的有限集合，這里的關(guān)系是從集合K到集合K的關(guān)系，這里一般只涉及到一個關(guān)系的邏輯結(jié)構(gòu)。例如，有5個人，分別記為a,b,c,d,e,其中a是b的父親，b是c的父親，c是d的父親,d是e的父親，如果只討論他們之間所存在的父子關(guān)系，則可以用下面的二元組形式化地予以表達。B=（K，R）其中：K={a,b,c,d,e}R={r}r={<a,b>,<b,c>,<c,d>,<d,e>}第6頁，共21頁，2023年，2月20日，星期六邏輯結(jié)構(gòu)的圖形表示方式，對K中的每個結(jié)點ki用一個方框表示，而結(jié)點之間的關(guān)系用帶箭頭的線段表示，這5人之間的邏輯結(jié)構(gòu)用圖形的方式表達如下圖

所示。若ki∈K，kj∈R，<ki,kj>∈r，則稱ki是kj的相對于關(guān)系r的前驅(qū)結(jié)點，kj是ki的相對于關(guān)系r的后繼結(jié)點，因為一般只討論具有一種關(guān)系的邏輯結(jié)構(gòu)，即R={r}，所以簡稱ki是kj前驅(qū)，kj是ki的后繼。如果某個結(jié)點沒有前驅(qū)結(jié)點，稱之為開始結(jié)點；如果某個結(jié)點沒有后繼結(jié)點，稱之為終端結(jié)點；既不是開始結(jié)點也不是終端結(jié)點的結(jié)點稱為內(nèi)部結(jié)點。第7頁，共21頁，2023年，2月20日，星期六1.1.3數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是獨立于計算機的，它與數(shù)據(jù)在計算機中的存儲無關(guān)，要對數(shù)據(jù)進行處理，就必須將數(shù)據(jù)存儲在計算機中。如果將數(shù)據(jù)在計算機中無規(guī)律地存儲，那么在處理時是非常糟的，是沒有用的。試想一下，如果一本英漢字典中的單詞是隨意編排的，這本字典誰會用！對于一個數(shù)據(jù)結(jié)構(gòu)B=（K，R），必須建立從結(jié)點集合到計算機某個存儲區(qū)域M的一個映象，這個映象要直接或間接地表達結(jié)點之間的關(guān)系R。數(shù)據(jù)在計算機中的存儲方式稱為數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)主要有4種。第8頁，共21頁，2023年，2月20日，星期六數(shù)據(jù)的存儲結(jié)構(gòu)主要有4種。1順序存儲順序存儲通常用于存儲具有線性結(jié)構(gòu)的數(shù)據(jù)。將邏輯上相鄰的結(jié)點存儲在連續(xù)存儲區(qū)域M的相鄰的存儲單元中，使得邏輯相鄰的結(jié)點一定是物理位置相鄰。對于一個數(shù)據(jù)結(jié)構(gòu)B=（K，R）其中K={k1,k2,k3,k4,k5,k6,k7,k8,k9}R={r}r={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>,<k5,k6>,<k6,k7>,<k7,k8>,<k8,k9>}它的順序存儲方式如圖所示第9頁，共21頁，2023年，2月20日，星期六2鏈式存儲鏈式存儲方式是給每個結(jié)點附加一個指針段，一個結(jié)點的指針所指的是該結(jié)點的后繼的存儲地址，因為一個結(jié)點可能有多個后繼，所以指針段可以是一個指針，也可以是一個多個指針。例，數(shù)據(jù)的邏輯結(jié)構(gòu)B=（K，R）

其中

K={k1,k2,k3,k4,k5}R={r}R={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>}這是一個線性結(jié)構(gòu)，它的鏈式存儲如圖所示。第10頁，共21頁，2023年，2月20日，星期六3索引存儲在線性結(jié)構(gòu)中，設(shè)開始結(jié)點的索引號為1，其它結(jié)點的索引號等于其前繼結(jié)點的索引號加1，則每一個結(jié)點都有唯一的索引號，索引號就是根據(jù)結(jié)點的索引號確定該結(jié)點的存儲地址。4散列存儲散列存儲的思想是構(gòu)造一個從集合K到存儲區(qū)域M的一個函數(shù)h，該函數(shù)的定義域為K，值域為M，K中的每個結(jié)點ki在計算機中的存儲地址由h(ki)確定。第11頁，共21頁，2023年，2月20日，星期六1.1.4數(shù)據(jù)的運算集合

對于一批數(shù)據(jù)，數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上的，而運算的具體實現(xiàn)就依賴于數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)的運算集合要視情況而定，一般而言，數(shù)據(jù)的運算包括插入、刪除、檢索、輸出、排序等。插入：在一個結(jié)構(gòu)中增加一個新的結(jié)點。刪除：在一個結(jié)構(gòu)刪除一個結(jié)點。檢索：在一個結(jié)構(gòu)中查找滿足條件的結(jié)點。輸出：將一個結(jié)構(gòu)中所有結(jié)點的值打印、輸出。排序：將一個結(jié)構(gòu)中所有結(jié)點按某種順序重新排列。第12頁，共21頁，2023年，2月20日，星期六在程序設(shè)計中，數(shù)據(jù)和運算是兩個不可缺少的因素。所有的程序設(shè)計活動都是圍繞著數(shù)據(jù)和其上的相關(guān)運算而進行的。從機器指令、匯編語言中的數(shù)據(jù)沒有類型的概念，到現(xiàn)在的面向?qū)ο蟪绦蛟O(shè)計語言中抽象數(shù)據(jù)類型概念的出現(xiàn)，程序設(shè)計中的數(shù)據(jù)經(jīng)歷了一次次抽象，數(shù)據(jù)的抽象經(jīng)歷了三個發(fā)展階段。1.2數(shù)據(jù)類型和抽象數(shù)據(jù)類型從無類型的二進制數(shù)到基本數(shù)據(jù)類型的產(chǎn)生從基本數(shù)據(jù)類型到用戶自定義類型的產(chǎn)生從用戶自定義類型到抽象數(shù)據(jù)類型的出現(xiàn)第13頁，共21頁，2023年，2月20日，星期六1.2.1數(shù)據(jù)類型數(shù)據(jù)類型（或簡稱類型）反映了數(shù)據(jù)的取值范圍以及對這類數(shù)據(jù)可以施加的運算。1.2.2數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是計算機科學(xué)中廣泛使用的一個術(shù)語，在計算機科學(xué)中具有非常重要的作用。數(shù)據(jù)結(jié)構(gòu)包括三個方面的內(nèi)容：一組數(shù)據(jù)中各數(shù)據(jù)之間的邏輯關(guān)系；這組數(shù)據(jù)在計算機中的存儲方式；對這組數(shù)據(jù)所能施加的運算的集合。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。所有的數(shù)據(jù)都是按照數(shù)據(jù)結(jié)構(gòu)進行分類的。簡單數(shù)據(jù)類型對應(yīng)于簡單的數(shù)據(jù)結(jié)構(gòu)；構(gòu)造數(shù)據(jù)類型對應(yīng)于復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。第14頁，共21頁，2023年，2月20日，星期六1.2.3抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型是與表示無關(guān)的數(shù)據(jù)類型，是一個數(shù)據(jù)模型及定義在該模型上的一組運算。對一個抽象數(shù)據(jù)類型進行定義時，必須給出它的名字及各運算的運算符名，即函數(shù)名，并且規(guī)定這些函數(shù)的參數(shù)性質(zhì)。一旦定義了一個抽象數(shù)據(jù)類型及具體實現(xiàn)，程序設(shè)計中就可以像使用基本數(shù)據(jù)類型那樣，十分方便地使用抽象數(shù)據(jù)類型。1.2.4抽象數(shù)據(jù)類型的描述和實現(xiàn)

抽象數(shù)據(jù)類型的描述包括給出抽象數(shù)據(jù)類型的名稱、數(shù)據(jù)的集合、數(shù)據(jù)之間的關(guān)系和操作的集合等方面的描述。抽象數(shù)據(jù)類型的設(shè)計者根據(jù)這些描述給出操作的具體實現(xiàn)，抽象數(shù)據(jù)類型的使用者依據(jù)這些描述使用抽象數(shù)據(jù)類型。第15頁，共21頁，2023年，2月20日，星期六抽象數(shù)據(jù)類型描述的一般形式如下：ADT抽象數(shù)據(jù)類型名稱{

數(shù)據(jù)對象：

……

數(shù)據(jù)關(guān)系：

……

操作集合：操作名1：

…………

操作名n：}ADT抽象數(shù)據(jù)類型名稱第16頁，共21頁，2023年，2月20日，星期六1.3算法和算法分析

1.3.1算法

為了求解某問題，必須給出一系列的運算規(guī)則，這一系列的運算規(guī)則是有限的，表達了求解問題方法和步驟，這就是一個算法。

一個算法可以用自然語言描述，也可以用高級程序設(shè)計語言描述，也可以用偽代碼描述。本書采用C語言對算法進行描述。第17頁，共21頁，2023年，2月20日，星期六算法具有五個基本特征：①有窮性，算法的執(zhí)行必須在有限步內(nèi)結(jié)束。②確定性，算法的每一個步驟必須是確定的無二義性的。③輸入，

算法可以有0個或多個輸入。④輸出，

算法一定有輸出結(jié)果⑤可行性，算法中的運算都必須是可以實現(xiàn)的。算法具有有窮性，程序不需要具備有窮性。一般的程序都會在有限時間內(nèi)終止，但有的程序卻可以不在有限時間內(nèi)終止，如一個操作系統(tǒng)在正常情況下是永遠都不會終止的。第18頁，共21頁，2023年，2月20日，星期六1.3.2算法的時間和空間復(fù)雜性

一個算法的優(yōu)劣主要從算法的執(zhí)行時間和所需要占用的存儲空間兩個方面衡量，算法執(zhí)行時間的度量不是采用算法執(zhí)行的絕對時間來計算的，因為一個算法在不同的機器上執(zhí)行所花的時間不一樣，在不同時刻也會由于計算機資源占用情況的不同，使得算法在同一臺計算機上執(zhí)行的時間也不一樣，所以對于算法的時間復(fù)雜性，采用算法執(zhí)行過程中其基本操作的執(zhí)行次數(shù)，稱為計算量來度量。算法中基本操作的執(zhí)行次數(shù)一般是與問題規(guī)模有關(guān)的，對于結(jié)點個數(shù)為n的數(shù)據(jù)處理問題，用T(n)表示算法基本操作的執(zhí)行次數(shù)。第19頁，共21頁，2023年，2月20日，星期六在評價算法的時間復(fù)雜性時，不考慮兩算法執(zhí)行次數(shù)之間的細小區(qū)別，而只關(guān)心算法的本質(zhì)差別。為此，引入一個所謂的O()記號，則T1(n)=2n=O(n),T2(n)=n+1=O(n)。一個函數(shù)f(n)是O(g(n))的，則一定存在正常數(shù)c和m，使對所有的n>m，都滿足f(n)<c*g(n)。下面的表格給出了一些具體函數(shù)的O()的表示，如圖所示。f(n)O(g(n))量級35O(1)常數(shù)階2n+7