等級考試三級數(shù)據(jù)庫考點(diǎn)分析：數(shù)據(jù)結(jié)構(gòu)與算法

考點(diǎn)6　棧

　　棧又稱為堆棧，它是一種運(yùn)算受限的特殊的線性表，僅允許在表的一端進(jìn)行插人和刪除運(yùn)算，可進(jìn)行運(yùn)算的一端為棧頂( top)，另一端為棧底( bottom)。表中無任何元素的棧稱為空棧。由于棧的插人和刪除運(yùn)算僅在棧頂進(jìn)行，后進(jìn)棧的元素必定先被刪除，所以又把棧稱為“后進(jìn)先出”（LIFO）表。
　　棧的基本操作有：
　�。�1） push(S,X)。往棧S中插人（或稱推人）一個新的棧頂元素x，即進(jìn)棧。
　�。�2）pop（S）。從棧S中刪除（或稱彈出）棧頂元素，即出棧。
　　（3）lop(S，X)：把棧S的棧頂元素讀到變量x中，棧保持不變。
　�。ǎ矗〆mpty（S）。判斷棧S是否為空棧，是則返回值為真。
　　（5）makempty。（S）將棧S設(shè)置為空。
　　棧既然是一種線性表，所以線性表的存儲結(jié)構(gòu)同樣也適用于棧。棧通常用順序存儲方式來存儲，分配一塊連續(xù)的存儲區(qū)域存放棧中元素，用一個變量來指向當(dāng)前棧頂。

考點(diǎn)7　隊(duì)列
　　隊(duì)列簡稱為隊(duì)，它也是一種運(yùn)算受限的線性表，隊(duì)列的限定是僅允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。進(jìn)行刪除操作的一端稱做隊(duì)列的頭，進(jìn)行插人操作的一端稱為隊(duì)列的尾.
　　隊(duì)列的基本操作有：
    （1) enq（Q, X)。往隊(duì)列口中插人一個新的隊(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ì)列的存儲方式也有順序存儲和鏈?zhǔn)酱鎯�兩種。順序隊(duì)列在進(jìn)行人隊(duì)操作時，會產(chǎn)生假溢出現(xiàn)象解決的辦法是讓隊(duì)列首尾相連，構(gòu)成一個循環(huán)隊(duì)列。

考點(diǎn)8　串

　　串（或字符串）是由零個或多個字符組成的有限序列。零個字符的串是空串。串中字符的個數(shù)就是串的長度串中的字符可以是字母、數(shù)字或其他字符。
　　串的存儲同樣也有順序存儲和鏈?zhǔn)酱鎯�兩種。順序存儲時，既可以采用非緊縮方式，也可以采用緊縮方式。
　　串的基本運(yùn)算有連接、賦值、求長度、全等比較、求子串、找子串位置及替換等，其中找子串位置（或稱模式匹配）比較重要。

   2.3多維數(shù)組、稀疏矩陣和廣義表
考點(diǎn)9　多維數(shù)組的順序存儲

　　多維數(shù)組是一維數(shù)組的推廣。多維數(shù)組的所有元素并未排在一個線性序列里，要順序存儲多維數(shù)組就需要按一定次序把所有的元素排在一個線性序列里。常用的排列次序有行優(yōu)先順序和列優(yōu)先順序兩種。
考點(diǎn)10　稀疏矩陣的存儲

　　稀疏矩陣是指矩陣中含有大量的0元素。對稀疏矩陣可進(jìn)行壓縮存儲，即只存儲其中的非0元素。若非0元素分布是有規(guī)律的，可用順序方法存儲非0元素。對于一般的稀疏矩陣，常見的存儲方法還有不元組法和十字鏈表法，這里就不再介紹了。
 考點(diǎn)11　廣義表的定義和存儲

　　 廣義表（又稱列表）是線性表的另一種推廣，是由零個或多個單元素或子表所組成的有限序列。它與線性表的區(qū)別在于：線性表中的元素都是結(jié)構(gòu)上不可分的單元素，而廣義表中的元素既可以是單元素，又可以是有結(jié)構(gòu)的表廣義表與線性表相比，具有如下3個方面的特征。
　　（１）廣義表的元素可以是子表，而子表的元素還可以是子表。
　�。ǎ玻�廣義表可被其他廣義表引用二
　　（３）廣義表可以是遞歸的表，即廣義表也可以是自身的一個子表。