考點1 數(shù)據(jù)結構的基本概念
1、數(shù)據(jù)
在計算機系統(tǒng)中，數(shù)據(jù)不僅包含了通常的數(shù)值概念，還有更廣泛的含義我們把采用計算機對客觀事物進行識別、存儲和加工所做的描述，統(tǒng)稱為數(shù)據(jù)。簡言之，數(shù)據(jù)就是計算機化的信息。
數(shù)據(jù)的基本單位是數(shù)據(jù)元素。數(shù)據(jù)元素可由一個或多個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位，又稱為關鍵碼，其值能夠確定一個數(shù)據(jù)元素的數(shù)據(jù)項。
2、數(shù)據(jù)結構
數(shù)據(jù)結構包括3個方面的內(nèi)容：數(shù)據(jù)之間的邏輯關系、數(shù)據(jù)在計算機中的存儲方式，以及在這些數(shù)據(jù)上定義的運算的集合。
(1)數(shù)據(jù)的邏輯結構。數(shù)據(jù)的邏輯結構與數(shù)據(jù)在計算機中的存儲方式無關，它用來抽象地反映數(shù)據(jù)元素之間的邏輯關系。邏輯結構可分為線性結構和非線性結構。最常見的線性結構是線性表，最典型的非線性結構是樹型結構。
(2)數(shù)據(jù)的存儲結構。數(shù)據(jù)的存儲結構實現(xiàn)了數(shù)據(jù)的邏輯結構在計算機內(nèi)的存儲問題，存儲結構又稱為物理結構。存儲結構分為順序存儲結構與鏈式存儲結構。
(3)數(shù)據(jù)的運算。數(shù)據(jù)的各種邏輯結構都有相對應的運算，每一種邏輯結構都有一個運算的集合。數(shù)據(jù)運算主要包括查找（檢索）、排序、插人、更新及刪除等。
考點2 主要的數(shù)據(jù)存儲方式
實現(xiàn)數(shù)據(jù)的邏輯結構到計算機存儲器的映像有多種不同的方式。順序存儲結構和鏈式存儲結構是兩種最主要的存儲方式。
1、順序存儲結構
順序存儲結構是將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里，節(jié)點之間的關系由存儲單元的相鄰關系來決定，它主要用于存儲線性結構的數(shù)據(jù)。順序存儲結構的主要特點如下。
(1)由于節(jié)點之間的關系由物理上的相鄰關系決定，所以節(jié)點中沒有鏈接信息域，只有自身的信息域，存儲密度大，空間利用率高。
(2)數(shù)據(jù)結構中第i個節(jié)點的存儲地址乙可由下述公式計算求得：
Li＝L0＋（i－1）×K
L0為第一個節(jié)點存儲地址，左為每個節(jié)點所占的存儲單元數(shù)。
(3)插人、刪除運算會引起相應節(jié)點的大量移動各節(jié)點的物理地址是相鄰的，每一次插人、刪除運算會引起相應節(jié)點物理地址的重新排列。
2、鏈式存儲結構
鏈式存儲結構打破了計算機存儲單元的連續(xù)性，可以將邏輯上相鄰的兩個數(shù)據(jù)元素存放在物理上不相鄰的存儲單元中鏈式存儲結構的每個節(jié)點中至少有一個節(jié)點域，來體現(xiàn)數(shù)據(jù)之間邏輯上的聯(lián)系。
鏈式存儲結構的主要特點包括以下幾個方面。
(1) 節(jié)點中除自身信自、外，還有表示鏈接信息的指針域，因此比順序存儲結構的存儲密度小，存儲空間利用率低。
(2) 羅輯上相鄰的節(jié)點物理上不一定相鄰，可用于線性表、樹、圖等多種邏輯結構的存儲表示。
(3) 插人、刪除等操作靈活方便，不需要大量移動節(jié)點，只需將節(jié)點的指針值修改即可。考點3 算法設計與分析
在計算機領域，一個算法實質(zhì)上是針對所處理問題的需要，在數(shù)據(jù)的邏輯結構和存儲結構的基礎上施加的一種運算，它是解決特定問題的方法。一個算法所占用的計算機資源包括時間代價和空間代價兩個方面時間代價的含義是：當問題的規(guī)模以某種單位由1增至n時，解決該問題的算法運行時所耗費的時間也以某種單位由f( 1)增至f(n)，則稱該算法的時間代價為f(n)。
空間代價的含義是：當問題的規(guī)模以某種單位由1增至n時，解決該問題的算法實現(xiàn)時所占用的空間也以某種單位由到g（1）增至g（n），則稱該算法的空間代價為g（n）。
2. 線性表
線性表的邏輯結構是由n個數(shù)據(jù)元素組成的一個有限序列。線性表中所包含元素的個數(shù)叫線性表的長度．它是可變的．可同線性表中增加或刪除元素。線性表包括順序表、鏈表、散列表和串等。
線性表的基本運算有：置表空、求表長、讀表元素、插人、刪除及檢索等操作。
考點4 順序表和一維數(shù)組
線性表的順序存儲是線性表的一種最簡單的存儲結構。其存儲方法是：在內(nèi)存中為線性表開辟一塊連續(xù)的存儲空間，該存儲空間所包含的存儲單元數(shù)要大于或等于線性表的長度，讓線性表的第一個元素存儲在這個存儲空間的第一個單元中，第二個元素存儲在第二個單元中，其他元素依次類推。一般情況下，若長度為n的順序表，在任何位置土插入或刪除的概率相等，元素移動的平均次數(shù)均為n/2。
考點5 鏈表
鏈表分為線性鏈表和非線性鏈表二線性鏈表是線性表的鏈式存儲表示，非線性鏈表是非線性數(shù)據(jù)結構樹和圖的鏈式存儲表示。
1、線性鏈表
線性鏈表也稱為單鏈表，其每個一節(jié)點中只包含一個指針域。對鏈表進行插人、刪除運算時只需改變節(jié)點中指針域的值。
（1）在指針一P后插人指針9的關鍵運算步驟：
q ↑. link：＝P↑．link：
p ↑. link：＝q；
（2）刪除指針P后繼節(jié)點q的關鍵運算步驟：
q：＝p↑ . link；
p↑. link：＝q↑．link；
（3）在第一個節(jié)點（或稱頭節(jié)點）前插人一個指針P的關鍵運算步驟：
p↑. link：＝head；
head：二P；
（4）刪除表中頭節(jié)點的關鍵運算步驟：
head：＝head↑ . link：
2、雙鏈表
在雙鏈表中，每個節(jié)點中設置有兩個指針域，分別用以指向其前驅(qū)節(jié)點和后繼節(jié)點。rlink指向節(jié)點的后繼，llink指向節(jié)點的前驅(qū)，這樣的結構方便向后和向前查找。
（l）若要在雙鏈表中刪除指針P所指的節(jié)點時，只需修改其前驅(qū)的rlink字段和后繼的Mink字段，步驟如下：
p↑ . llink↑. rlink：＝p↑. rlink；
P↑T．rlink↑. llink：＝P↑．llink；
(2)如果要在指針P后面插人指針q所指的新節(jié)點，只需修改P指針所指節(jié)點的rlink字段和原來后繼均Ilink字段，并重新設置q所指節(jié)點的Mink和rlink值，步驟如下：
q ↑. Mink：＝P：
q↑．rlink：＝P↑．rlink;
P↑．rlink r. Rink：＝q；
p↑．rlink：＝q;
3、可利用空間表
可利用空間表的作用是管理可用于鏈表插人和刪除的節(jié)點，當鏈表插人需要一個新節(jié)點時，就從可利用空間表中刪除第一個節(jié)點，用這個節(jié)點去做鏈表插人；當從鏈表中刪除一個節(jié)點時，就把這個節(jié)點插人到可利用空間表的第一個節(jié)點前面。
考點6 棧
棧又稱為堆棧，它是一種運算受限的特殊的線性表，僅允許在表的一端進行插人和刪除運算，可進行運算的一端為棧頂( top)，另一端為棧底( bottom)。表中無任何元素的棧稱為空棧。由于棧的插人和刪除運算僅在棧頂進行，后進棧的元素必定先被刪除，所以又把棧稱為“后進先出”（LIFO）表。
棧的基本操作有：
（1）push(S,X)。往棧S中插人（或稱推人）一個新的棧頂元素x，即進棧。
（2）pop（S）。從棧S中刪除（或稱彈出）棧頂元素，即出棧。
（3）lop(S，X)：把棧S的棧頂元素讀到變量x中，棧保持不變。
（4）empty（S）。判斷棧S是否為空棧，是則返回值為真。
（5）makempty。（S）將棧S設置為空。
棧既然是一種線性表，所以線性表的存儲結構同樣也適用于棧。棧通常用順序存儲方式來存儲，分配一塊連續(xù)的存儲區(qū)域存放棧中元素，用一個變量來指向當前棧頂。
考點7 隊列
隊列簡稱為隊，它也是一種運算受限的線性表，隊列的限定是僅允許在表的一端進行插入，而在另一端進行刪除。進行刪除操作的一端稱做隊列的頭，進行插人操作的一端稱為隊列的尾.
隊列的基本操作有：
（1) enq（Q, X)。往隊列口中插人一個新的隊尾元素x，即人隊。
（2）deq（口）從隊列Q中刪除隊頭元素，即出隊。
（3）front口,x)將隊列口的隊頭元素值讀到變量x中，隊列保持不變。
（4）empty ( Q )．判斷隊歹，l口是否為空，是則返回值為真。
（5）makempty（口）將隊列口置為空隊列。
和線性表一樣、隊列的存儲方式也有順序存儲和鏈式存儲兩種。順序隊列在進行人隊操作時，會產(chǎn)生假溢出現(xiàn)象解決的辦法是讓隊列首尾相連，構成一個循環(huán)隊列。
考點8 串
串（或字符串）是由零個或多個字符組成的有限序列。零個字符的串是空串。串中字符的個數(shù)就是串的長度串中的字符可以是字母、數(shù)字或其他字符。
串的存儲同樣也有順序存儲和鏈式存儲兩種。順序存儲時，既可以采用非緊縮方式，也可以采用緊縮方式。
串的基本運算有連接、賦值、求長度、全等比較、求子串、找子串位置及替換等，其中找子串位置（或稱模式匹配）比較重要。
3. 多維數(shù)組、稀疏矩陣和廣義表
考點9 多維數(shù)組的順序存儲
多維數(shù)組是一維數(shù)組的推廣。多維數(shù)組的所有元素并未排在一個線性序列里，要順序存儲多維數(shù)組就需要按一定次序把所有的元素排在一個線性序列里。常用的排列次序有行優(yōu)先順序和列優(yōu)先順序兩種。
考點10 稀疏矩陣的存儲
稀疏矩陣是指矩陣中含有大量的0元素。對稀疏矩陣可進行壓縮存儲，即只存儲其中的非0元素。若非0元素分布是有規(guī)律的，可用順序方法存儲非0元素。對于一般的稀疏矩陣，常見的存儲方法還有不元組法和十字鏈表法，這里就不再介紹了。
考點11 廣義表的定義和存儲
廣義表（又稱列表）是線性表的另一種推廣，是由零個或多個單元素或子表所組成的有限序列。它與線性表的區(qū)別在于：線性表中的元素都是結構上不可分的單元素，而廣義表中的元素既可以是單元素，又可以是有結構的表廣義表與線性表相比，具有如下3個方面的特征。
（１）廣義表的元素可以是子表，而子表的元素還可以是子表。
（２）廣義表可被其他廣義表引用二
（３）廣義表可以是遞歸的表，即廣義表也可以是自身的一個子表。