考點(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)算的集合。
(1)數(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é)構(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ǔ)問題，存儲(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)中沒有鏈接信息域，只有自身的信息域，存儲(chǔ)密度大，空間利用率高。
(2)數(shù)據(jù)結(jié)構(gòu)中第i個(gè)節(jié)點(diǎn)的存儲(chǔ)地址乙可由下述公式計(jì)算求得：
Li＝L0＋（i－1）×K
L0為第一個(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)的指針值修改即可?？键c(diǎn)3 算法設(shè)計(jì)與分析
在計(jì)算機(jī)領(lǐng)域，一個(gè)算法實(shí)質(zhì)上是針對(duì)所處理問題的需要，在數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上施加的一種運(yùn)算，它是解決特定問題的方法。一個(gè)算法所占用的計(jì)算機(jī)資源包括時(shí)間代價(jià)和空間代價(jià)兩個(gè)方面時(shí)間代價(jià)的含義是：當(dāng)問題的規(guī)模以某種單位由1增至n時(shí)，解決該問題的算法運(yùn)行時(shí)所耗費(fèi)的時(shí)間也以某種單位由f( 1)增至f(n)，則稱該算法的時(shí)間代價(jià)為f(n)。
空間代價(jià)的含義是：當(dāng)問題的規(guī)模以某種單位由1增至n時(shí)，解決該問題的算法實(shí)現(xiàn)時(shí)所占用的空間也以某種單位由到g（1）增至g（n），則稱該算法的空間代價(jià)為g（n）。
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。
考點(diǎn)5 鏈表
鏈表分為線性鏈表和非線性鏈表二線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)表示，非線性鏈表是非線性數(shù)據(jù)結(jié)構(gòu)樹和圖的鏈?zhǔn)酱鎯?chǔ)表示。
1、線性鏈表
線性鏈表也稱為單鏈表，其每個(gè)一節(jié)點(diǎn)中只包含一個(gè)指針域。對(duì)鏈表進(jìn)行插人、刪除運(yùn)算時(shí)只需改變節(jié)點(diǎn)中指針域的值。
（1）在指針一P后插人指針9的關(guān)鍵運(yùn)算步驟：
q ↑. link：＝P↑．link：
p ↑. link：＝q；
（2）刪除指針P后繼節(jié)點(diǎn)q的關(guān)鍵運(yùn)算步驟：
q：＝p↑ . link；
p↑. link：＝q↑．link；
（3）在第一個(gè)節(jié)點(diǎn)（或稱頭節(jié)點(diǎn)）前插人一個(gè)指針P的關(guān)鍵運(yùn)算步驟：
p↑. link：＝head；
head：二P；
（4）刪除表中頭節(jié)點(diǎn)的關(guān)鍵運(yùn)算步驟：
head：＝head↑ . link：
2、雙鏈表
在雙鏈表中，每個(gè)節(jié)點(diǎn)中設(shè)置有兩個(gè)指針域，分別用以指向其前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)。rlink指向節(jié)點(diǎn)的后繼，llink指向節(jié)點(diǎn)的前驅(qū)，這樣的結(jié)構(gòu)方便向后和向前查找。
（l）若要在雙鏈表中刪除指針P所指的節(jié)點(diǎn)時(shí)，只需修改其前驅(qū)的rlink字段和后繼的Mink字段，步驟如下：
p↑ . llink↑. rlink：＝p↑. rlink；
P↑T．rlink↑. llink：＝P↑．llink；
(2)如果要在指針P后面插人指針q所指的新節(jié)點(diǎn)，只需修改P指針?biāo)腹?jié)點(diǎn)的rlink字段和原來(lái)后繼均Ilink字段，并重新設(shè)置q所指節(jié)點(diǎn)的Mink和rlink值，步驟如下：
q ↑. Mink：＝P：
q↑．rlink：＝P↑．rlink;
P↑．rlink r. Rink：＝q；
p↑．rlink：＝q;
3、可利用空間表
可利用空間表的作用是管理可用于鏈表插人和刪除的節(jié)點(diǎn)，當(dāng)鏈表插人需要一個(gè)新節(jié)點(diǎn)時(shí)，就從可利用空間表中刪除第一個(gè)節(jié)點(diǎn)，用這個(gè)節(jié)點(diǎn)去做鏈表插人；當(dāng)從鏈表中刪除一個(gè)節(jié)點(diǎn)時(shí)，就把這個(gè)節(jié)點(diǎn)插人到可利用空間表的第一個(gè)節(jié)點(diǎn)前面。
考點(diǎn)6 棧
棧又稱為堆棧，它是一種運(yùn)算受限的特殊的線性表，僅允許在表的一端進(jìn)行插人和刪除運(yùn)算，可進(jìn)行運(yùn)算的一端為棧頂( top)，另一端為棧底( bottom)。表中無(wú)任何元素的棧稱為空棧。由于棧的插人和刪除運(yùn)算僅在棧頂進(jìn)行，后進(jìn)棧的元素必定先被刪除，所以又把棧稱為“后進(jìn)先出”（LIFO）表。
棧的基本操作有：
（1）push(S,X)。往棧S中插人（或稱推人）一個(gè)新的棧頂元素x，即進(jìn)棧。
（2）pop（S）。從棧S中刪除（或稱彈出）棧頂元素，即出棧。
（3）lop(S，X)：把棧S的棧頂元素讀到變量x中，棧保持不變。
（4）empty（S）。判斷棧S是否為空棧，是則返回值為真。
（5）makempty。（S）將棧S設(shè)置為空。
棧既然是一種線性表，所以線性表的存儲(chǔ)結(jié)構(gòu)同樣也適用于棧。棧通常用順序存儲(chǔ)方式來(lái)存儲(chǔ)，分配一塊連續(xù)的存儲(chǔ)區(qū)域存放棧中元素，用一個(gè)變量來(lái)指向當(dāng)前棧頂。
考點(diǎn)7 隊(duì)列
隊(duì)列簡(jiǎn)稱為隊(duì)，它也是一種運(yùn)算受限的線性表，隊(duì)列的限定是僅允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。進(jìn)行刪除操作的一端稱做隊(duì)列的頭，進(jìn)行插人操作的一端稱為隊(duì)列的尾.
隊(duì)列的基本操作有：
（1) enq（Q, X)。往隊(duì)列口中插人一個(gè)新的隊(duì)尾元素x，即人隊(duì)。
（2）deq（口）從隊(duì)列Q中刪除隊(duì)頭元素，即出隊(duì)。
（3）front口,x)將隊(duì)列口的隊(duì)頭元素值讀到變量x中，隊(duì)列保持不變。
（4）empty ( Q )．判斷隊(duì)歹，l口是否為空，是則返回值為真。
（5）makempty（口）將隊(duì)列口置為空隊(duì)列。
和線性表一樣、隊(duì)列的存儲(chǔ)方式也有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種。順序隊(duì)列在進(jìn)行人隊(duì)操作時(shí)，會(huì)產(chǎn)生假溢出現(xiàn)象解決的辦法是讓隊(duì)列首尾相連，構(gòu)成一個(gè)循環(huán)隊(duì)列。
考點(diǎn)8 串
串（或字符串）是由零個(gè)或多個(gè)字符組成的有限序列。零個(gè)字符的串是空串。串中字符的個(gè)數(shù)就是串的長(zhǎng)度串中的字符可以是字母、數(shù)字或其他字符。
串的存儲(chǔ)同樣也有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種。順序存儲(chǔ)時(shí)，既可以采用非緊縮方式，也可以采用緊縮方式。
串的基本運(yùn)算有連接、賦值、求長(zhǎng)度、全等比較、求子串、找子串位置及替換等，其中找子串位置（或稱模式匹配）比較重要。
3. 多維數(shù)組、稀疏矩陣和廣義表
考點(diǎn)9 多維數(shù)組的順序存儲(chǔ)
多維數(shù)組是一維數(shù)組的推廣。多維數(shù)組的所有元素并未排在一個(gè)線性序列里，要順序存儲(chǔ)多維數(shù)組就需要按一定次序把所有的元素排在一個(gè)線性序列里。常用的排列次序有行優(yōu)先順序和列優(yōu)先順序兩種。
考點(diǎn)10 稀疏矩陣的存儲(chǔ)
稀疏矩陣是指矩陣中含有大量的0元素。對(duì)稀疏矩陣可進(jìn)行壓縮存儲(chǔ)，即只存儲(chǔ)其中的非0元素。若非0元素分布是有規(guī)律的，可用順序方法存儲(chǔ)非0元素。對(duì)于一般的稀疏矩陣，常見的存儲(chǔ)方法還有不元組法和十字鏈表法，這里就不再介紹了。
考點(diǎn)11 廣義表的定義和存儲(chǔ)
廣義表（又稱列表）是線性表的另一種推廣，是由零個(gè)或多個(gè)單元素或子表所組成的有限序列。它與線性表的區(qū)別在于：線性表中的元素都是結(jié)構(gòu)上不可分的單元素，而廣義表中的元素既可以是單元素，又可以是有結(jié)構(gòu)的表廣義表與線性表相比，具有如下3個(gè)方面的特征。
（１）廣義表的元素可以是子表，而子表的元素還可以是子表。
（２）廣義表可被其他廣義表引用二
（３）廣義表可以是遞歸的表，即廣義表也可以是自身的一個(gè)子表。