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

數(shù)據(jù)結(jié)構(gòu)討論的是數(shù)據(jù)的邏輯結(jié)構(gòu)第一頁，共二十一頁，編輯于2023年，星期三1.1數(shù)據(jù)結(jié)構(gòu)

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

冬5700123瑤湖大道198700004王

三5700567瑤湖大道200800005江

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

將用戶信息表中的所有結(jié)點(diǎn)存入計(jì)算機(jī)時(shí)，就必須考慮存儲(chǔ)結(jié)構(gòu)，使用C語言進(jìn)行設(shè)計(jì)時(shí)，常見的方式是用一個(gè)結(jié)構(gòu)數(shù)組來存儲(chǔ)整個(gè)用戶信息表，每一個(gè)數(shù)組元素是一個(gè)結(jié)構(gòu)，它對(duì)應(yīng)于用戶信息表中的一個(gè)結(jié)點(diǎn)。數(shù)據(jù)在計(jì)算機(jī)的存儲(chǔ)方式稱為存儲(chǔ)結(jié)構(gòu)。第四頁，共二十一頁，編輯于2023年，星期三3數(shù)據(jù)的運(yùn)算集合

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

數(shù)據(jù)結(jié)構(gòu)就是指按一定的邏輯結(jié)構(gòu)組成的一批數(shù)據(jù)，使用某種存儲(chǔ)結(jié)構(gòu)將這批數(shù)據(jù)存儲(chǔ)于計(jì)算機(jī)中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算集合。第五頁，共二十一頁，編輯于2023年，星期三1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)

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

所示。若ki∈K，kj∈R，<ki,kj>∈r，則稱ki是kj的相對(duì)于關(guān)系r的前驅(qū)結(jié)點(diǎn)，kj是ki的相對(duì)于關(guān)系r的后繼結(jié)點(diǎn)，因?yàn)橐话阒挥懻摼哂幸环N關(guān)系的邏輯結(jié)構(gòu)，即R={r}，所以簡(jiǎn)稱ki是kj前驅(qū)，kj是ki的后繼。如果某個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，稱之為開始結(jié)點(diǎn)；如果某個(gè)結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，稱之為終端結(jié)點(diǎn)；既不是開始結(jié)點(diǎn)也不是終端結(jié)點(diǎn)的結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn)。第七頁，共二十一頁，編輯于2023年，星期三1.1.3數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是獨(dú)立于計(jì)算機(jī)的，它與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)無關(guān)，要對(duì)數(shù)據(jù)進(jìn)行處理，就必須將數(shù)據(jù)存儲(chǔ)在計(jì)算機(jī)中。如果將數(shù)據(jù)在計(jì)算機(jī)中無規(guī)律地存儲(chǔ)，那么在處理時(shí)是非常糟的，是沒有用的。試想一下，如果一本英漢字典中的單詞是隨意編排的，這本字典誰會(huì)用！對(duì)于一個(gè)數(shù)據(jù)結(jié)構(gòu)B=（K，R），必須建立從結(jié)點(diǎn)集合到計(jì)算機(jī)某個(gè)存儲(chǔ)區(qū)域M的一個(gè)映象，這個(gè)映象要直接或間接地表達(dá)結(jié)點(diǎn)之間的關(guān)系R。數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有4種。第八頁，共二十一頁，編輯于2023年，星期三數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有4種。1順序存儲(chǔ)順序存儲(chǔ)通常用于存儲(chǔ)具有線性結(jié)構(gòu)的數(shù)據(jù)。將邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在連續(xù)存儲(chǔ)區(qū)域M的相鄰的存儲(chǔ)單元中，使得邏輯相鄰的結(jié)點(diǎn)一定是物理位置相鄰。對(duì)于一個(gè)數(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>}它的順序存儲(chǔ)方式如圖所示第九頁，共二十一頁，編輯于2023年，星期三2鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)方式是給每個(gè)結(jié)點(diǎn)附加一個(gè)指針段，一個(gè)結(jié)點(diǎn)的指針?biāo)傅氖窃摻Y(jié)點(diǎn)的后繼的存儲(chǔ)地址，因?yàn)橐粋€(gè)結(jié)點(diǎn)可能有多個(gè)后繼，所以指針段可以是一個(gè)指針，也可以是一個(gè)多個(gè)指針。例，數(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>}這是一個(gè)線性結(jié)構(gòu)，它的鏈?zhǔn)酱鎯?chǔ)如圖所示。第十頁，共二十一頁，編輯于2023年，星期三3索引存儲(chǔ)在線性結(jié)構(gòu)中，設(shè)開始結(jié)點(diǎn)的索引號(hào)為1，其它結(jié)點(diǎn)的索引號(hào)等于其前繼結(jié)點(diǎn)的索引號(hào)加1，則每一個(gè)結(jié)點(diǎn)都有唯一的索引號(hào)，索引號(hào)就是根據(jù)結(jié)點(diǎn)的索引號(hào)確定該結(jié)點(diǎn)的存儲(chǔ)地址。4散列存儲(chǔ)散列存儲(chǔ)的思想是構(gòu)造一個(gè)從集合K到存儲(chǔ)區(qū)域M的一個(gè)函數(shù)h，該函數(shù)的定義域?yàn)镵，值域?yàn)镸，K中的每個(gè)結(jié)點(diǎn)ki在計(jì)算機(jī)中的存儲(chǔ)地址由h(ki)確定。第十一頁，共二十一頁，編輯于2023年，星期三1.1.4數(shù)據(jù)的運(yùn)算集合

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

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

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

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

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

……

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

……

操作集合：操作名1：

…………

操作名n：}ADT抽象數(shù)據(jù)類型名稱第十六頁，共二十一頁，編輯于2023年，星期三1.3算法和算法分析

1.3.1算法

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

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

算法可以有0個(gè)或多個(gè)輸入。④輸出，

算法一定有輸出結(jié)果⑤可行性，算法中的運(yùn)算都必須是可以實(shí)現(xiàn)的。算法具有有窮性，程序不需要具備有窮性。一般的程序都會(huì)在有限時(shí)間內(nèi)終止，但有的程序卻可以不在有限時(shí)間內(nèi)終止，如一個(gè)操作系統(tǒng)在正常情況下是永遠(yuǎn)都不會(huì)終止的。第十八頁，共二十一頁，編輯于2023年，星期三1.3.2算法的時(shí)間和空間復(fù)雜性

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