第二章 數(shù)據(jù)結(jié)構(gòu)算法
2.1基本概率
考點(diǎn)1數(shù)據(jù)結(jié)構(gòu)的基本概念
1.數(shù)據(jù)
在計(jì)算機(jī)系統(tǒng)中，數(shù)據(jù)不僅包含了通常的數(shù)值概念，還有更廣泛的含義我們把采用計(jì)算機(jī)對(duì)客觀事物進(jìn)行識(shí)別、存儲(chǔ)和加工所做的描述，統(tǒng)稱為數(shù)據(jù)。簡(jiǎn)言之，數(shù)據(jù)就是計(jì)算機(jī)化的信息
數(shù)據(jù)的基本單位是數(shù)據(jù)元素。數(shù)據(jù)元素可由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位，又稱為關(guān)鍵碼，其值能夠確定一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。
2.數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)包括3個(gè)方面的內(nèi)容：數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式，以及在這些數(shù)據(jù)上定義的運(yùn)算的集合。
(l)數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式無(wú)關(guān)，它用來(lái)抽象地反映數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。最常見(jiàn)的線性結(jié)構(gòu)是線性表，最典型的非線性結(jié)構(gòu)是樹型結(jié)構(gòu)。
(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)了數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)的存儲(chǔ)問(wèn)題，存儲(chǔ)結(jié)構(gòu)又稱為物理結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)分為順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
(3)數(shù)據(jù)的運(yùn)算。數(shù)據(jù)的各種邏輯結(jié)構(gòu)都有相對(duì)應(yīng)的運(yùn)算，每一種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。數(shù)據(jù)運(yùn)算主要包括查找(檢索)、排序、插人、更新及刪除等。
考點(diǎn)2主要的數(shù)據(jù)存儲(chǔ)方式
實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)到計(jì)算機(jī)存儲(chǔ)器的映像有多種不同的方式。順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是兩種最主要的存儲(chǔ)方式。
1.順序存儲(chǔ)結(jié)構(gòu)
順序存儲(chǔ)結(jié)構(gòu)是將邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里，節(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的相鄰關(guān)系來(lái)決定，它主要用于存儲(chǔ)線性結(jié)構(gòu)的數(shù)據(jù)。順序存儲(chǔ)結(jié)構(gòu)的主要特點(diǎn)如下。
(1)由于節(jié)點(diǎn)之間的關(guān)系由物理上的相鄰關(guān)系決定，所以節(jié)點(diǎn)中沒(méi)有鏈接信息域，只有自身的信息域，存儲(chǔ)密度大，空間利用率高。
(2)數(shù)據(jù)結(jié)構(gòu)中第i個(gè)節(jié)點(diǎn)的存儲(chǔ)地址乙可由下述公式計(jì)算求得：
L¬i＝L¬0＋(i－1)×K
L¬0為第一個(gè)節(jié)點(diǎn)存儲(chǔ)地址，左為每個(gè)節(jié)點(diǎn)所占的存儲(chǔ)單元數(shù)。
(3)插人、刪除運(yùn)算會(huì)引起相應(yīng)節(jié)點(diǎn)的大量移動(dòng)各節(jié)點(diǎn)的物理地址是相鄰的，每一次插人、刪除運(yùn)算會(huì)引起相應(yīng)節(jié)點(diǎn)物理地址的重新排列。
2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)打破了計(jì)算機(jī)存儲(chǔ)單元的連續(xù)性，可以將邏輯上相鄰的兩個(gè)數(shù)據(jù)元素存放在物理上不相鄰的存儲(chǔ)單元中鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的每個(gè)節(jié)點(diǎn)中至少有一個(gè)節(jié)點(diǎn)域，來(lái)體現(xiàn)數(shù)據(jù)之間邏輯上的聯(lián)系。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要特點(diǎn)包括以下幾個(gè)方面。
(1)節(jié)點(diǎn)中除自身信自、外，還有表示鏈接信息的指針域，因此比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小，存儲(chǔ)空間利用率低。
(2)：羅輯上相鄰的節(jié)點(diǎn)物理上不一定相鄰，可用于線性表、樹、圖等多種邏輯結(jié)構(gòu)的存儲(chǔ)表示。
(3)插人、刪除等操作靈活方便，不需要大量移動(dòng)節(jié)點(diǎn)，只需將節(jié)點(diǎn)的指針值修改即可。
考點(diǎn)3算法設(shè)計(jì)與分析
在計(jì)算機(jī)領(lǐng)域，一個(gè)算法實(shí)質(zhì)上是針對(duì)所處理問(wèn)題的需要，在數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上施加的一種運(yùn)算，它是解決特定問(wèn)題的方法。一個(gè)算法所占用的計(jì)算機(jī)資源包括時(shí)間代價(jià)和空間代價(jià)兩個(gè)方面
時(shí)間代價(jià)的含義是：當(dāng)問(wèn)題的規(guī)模以某種單位由1增至n時(shí)，解決該問(wèn)題的算法運(yùn)行時(shí)所耗費(fèi)的時(shí)間也以某種單位由f( 1)增至f(n)，則稱該算法的時(shí)間代價(jià)為f(n)。
空間代價(jià)的含義是：當(dāng)問(wèn)題的規(guī)模以某種單位由1增至n時(shí)，解決該問(wèn)題的算法實(shí)現(xiàn)時(shí)所占用的空間也以某種單位由到g(1)增至g(n)，則稱該算法的空間代價(jià)為g(n)。
2.2線性表
線性表的邏輯結(jié)構(gòu)是由n個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列。線性表中所包含元素的個(gè)數(shù)叫線性表的長(zhǎng)度．它是可變的．可同線性表中增加或刪除元素。線性表包括順序表、鏈表、散列表和串等。
線性表的基本運(yùn)算有：置表空、求表長(zhǎng)、讀表元素、插人、刪除及檢索等操作。
考點(diǎn)4順序表和一維數(shù)組
線性表的順序存儲(chǔ)是線性表的一種最簡(jiǎn)單的存儲(chǔ)結(jié)構(gòu)。其存儲(chǔ)方法是：在內(nèi)存中為線性表開辟一塊連續(xù)的存儲(chǔ)空間，該存儲(chǔ)空間所包含的存儲(chǔ)單元數(shù)要大于或等于線性表的長(zhǎng)度，讓線性表的第一個(gè)元素存儲(chǔ)在這個(gè)存儲(chǔ)空間的第一個(gè)單元中，第二個(gè)元素存儲(chǔ)在第二個(gè)單元中，其他元素依次類推。一般情況下，若長(zhǎng)度為n的順序表，在任何位置土插入或刪除的概率相等，元素移動(dòng)的平均次數(shù)均為n/2。
2.1基本概率
考點(diǎn)1數(shù)據(jù)結(jié)構(gòu)的基本概念
1.數(shù)據(jù)
在計(jì)算機(jī)系統(tǒng)中，數(shù)據(jù)不僅包含了通常的數(shù)值概念，還有更廣泛的含義我們把采用計(jì)算機(jī)對(duì)客觀事物進(jìn)行識(shí)別、存儲(chǔ)和加工所做的描述，統(tǒng)稱為數(shù)據(jù)。簡(jiǎn)言之，數(shù)據(jù)就是計(jì)算機(jī)化的信息
數(shù)據(jù)的基本單位是數(shù)據(jù)元素。數(shù)據(jù)元素可由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位，又稱為關(guān)鍵碼，其值能夠確定一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。
2.數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)包括3個(gè)方面的內(nèi)容：數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式，以及在這些數(shù)據(jù)上定義的運(yùn)算的集合。
(l)數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式無(wú)關(guān)，它用來(lái)抽象地反映數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。最常見(jiàn)的線性結(jié)構(gòu)是線性表，最典型的非線性結(jié)構(gòu)是樹型結(jié)構(gòu)。
(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)了數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)的存儲(chǔ)問(wèn)題，存儲(chǔ)結(jié)構(gòu)又稱為物理結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)分為順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
(3)數(shù)據(jù)的運(yùn)算。數(shù)據(jù)的各種邏輯結(jié)構(gòu)都有相對(duì)應(yīng)的運(yùn)算，每一種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。數(shù)據(jù)運(yùn)算主要包括查找(檢索)、排序、插人、更新及刪除等。
考點(diǎn)2主要的數(shù)據(jù)存儲(chǔ)方式
實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)到計(jì)算機(jī)存儲(chǔ)器的映像有多種不同的方式。順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是兩種最主要的存儲(chǔ)方式。
1.順序存儲(chǔ)結(jié)構(gòu)
順序存儲(chǔ)結(jié)構(gòu)是將邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里，節(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的相鄰關(guān)系來(lái)決定，它主要用于存儲(chǔ)線性結(jié)構(gòu)的數(shù)據(jù)。順序存儲(chǔ)結(jié)構(gòu)的主要特點(diǎn)如下。
(1)由于節(jié)點(diǎn)之間的關(guān)系由物理上的相鄰關(guān)系決定，所以節(jié)點(diǎn)中沒(méi)有鏈接信息域，只有自身的信息域，存儲(chǔ)密度大，空間利用率高。
(2)數(shù)據(jù)結(jié)構(gòu)中第i個(gè)節(jié)點(diǎn)的存儲(chǔ)地址乙可由下述公式計(jì)算求得：
L¬i＝L¬0＋(i－1)×K
L¬0為第一個(gè)節(jié)點(diǎn)存儲(chǔ)地址，左為每個(gè)節(jié)點(diǎn)所占的存儲(chǔ)單元數(shù)。
(3)插人、刪除運(yùn)算會(huì)引起相應(yīng)節(jié)點(diǎn)的大量移動(dòng)各節(jié)點(diǎn)的物理地址是相鄰的，每一次插人、刪除運(yùn)算會(huì)引起相應(yīng)節(jié)點(diǎn)物理地址的重新排列。
2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)打破了計(jì)算機(jī)存儲(chǔ)單元的連續(xù)性，可以將邏輯上相鄰的兩個(gè)數(shù)據(jù)元素存放在物理上不相鄰的存儲(chǔ)單元中鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的每個(gè)節(jié)點(diǎn)中至少有一個(gè)節(jié)點(diǎn)域，來(lái)體現(xiàn)數(shù)據(jù)之間邏輯上的聯(lián)系。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要特點(diǎn)包括以下幾個(gè)方面。
(1)節(jié)點(diǎn)中除自身信自、外，還有表示鏈接信息的指針域，因此比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小，存儲(chǔ)空間利用率低。
(2)：羅輯上相鄰的節(jié)點(diǎn)物理上不一定相鄰，可用于線性表、樹、圖等多種邏輯結(jié)構(gòu)的存儲(chǔ)表示。
(3)插人、刪除等操作靈活方便，不需要大量移動(dòng)節(jié)點(diǎn)，只需將節(jié)點(diǎn)的指針值修改即可。
考點(diǎn)3算法設(shè)計(jì)與分析
在計(jì)算機(jī)領(lǐng)域，一個(gè)算法實(shí)質(zhì)上是針對(duì)所處理問(wèn)題的需要，在數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上施加的一種運(yùn)算，它是解決特定問(wèn)題的方法。一個(gè)算法所占用的計(jì)算機(jī)資源包括時(shí)間代價(jià)和空間代價(jià)兩個(gè)方面
時(shí)間代價(jià)的含義是：當(dāng)問(wèn)題的規(guī)模以某種單位由1增至n時(shí)，解決該問(wèn)題的算法運(yùn)行時(shí)所耗費(fèi)的時(shí)間也以某種單位由f( 1)增至f(n)，則稱該算法的時(shí)間代價(jià)為f(n)。
空間代價(jià)的含義是：當(dāng)問(wèn)題的規(guī)模以某種單位由1增至n時(shí)，解決該問(wèn)題的算法實(shí)現(xiàn)時(shí)所占用的空間也以某種單位由到g(1)增至g(n)，則稱該算法的空間代價(jià)為g(n)。
2.2線性表
線性表的邏輯結(jié)構(gòu)是由n個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列。線性表中所包含元素的個(gè)數(shù)叫線性表的長(zhǎng)度．它是可變的．可同線性表中增加或刪除元素。線性表包括順序表、鏈表、散列表和串等。
線性表的基本運(yùn)算有：置表空、求表長(zhǎng)、讀表元素、插人、刪除及檢索等操作。
考點(diǎn)4順序表和一維數(shù)組
線性表的順序存儲(chǔ)是線性表的一種最簡(jiǎn)單的存儲(chǔ)結(jié)構(gòu)。其存儲(chǔ)方法是：在內(nèi)存中為線性表開辟一塊連續(xù)的存儲(chǔ)空間，該存儲(chǔ)空間所包含的存儲(chǔ)單元數(shù)要大于或等于線性表的長(zhǎng)度，讓線性表的第一個(gè)元素存儲(chǔ)在這個(gè)存儲(chǔ)空間的第一個(gè)單元中，第二個(gè)元素存儲(chǔ)在第二個(gè)單元中，其他元素依次類推。一般情況下，若長(zhǎng)度為n的順序表，在任何位置土插入或刪除的概率相等，元素移動(dòng)的平均次數(shù)均為n/2。