【正文】 rlo(蒙特卡羅 )算法的思想是：對于目標(biāo)串 S，求出其S(j)=S[j]S[j+1]? S[j+m1](從 S第 j位開始、長度與 P一樣的子串)的指紋 Ip(S(j))，與 P的指紋 Ip(P)，如果它們相等則認(rèn)為 P是 S的子串，并且得到位置 j；否則比較 S(j+1)與 P的指紋，一直比較 nm+1次，如果沒有一個 S(j)與 P的指紋相等，則認(rèn)為 P不是 S的子串。 Las Vegas(拉斯維加斯 )算法的思想是：它與 Monte Carlo算法相似，只是在 Ip(P)=Ip(S(j))時，不直接返回匹配成功，而是轉(zhuǎn)去比較 P與 S(j)是否真的相等。因此，采用 Las Vegas算法得出 P是 S的子串的結(jié)果總是正確的。 第 5章 數(shù)組及廣義表 本章主要內(nèi)容 數(shù)組的定義 數(shù)組的順序存儲 矩陣的壓縮存儲 廣義表 數(shù)組的定義 數(shù)組的基本概念 數(shù)組的抽象數(shù)據(jù)類型 數(shù)組的基本概念 ? 一維數(shù)組：是存儲于計算機(jī)的連續(xù)存儲空間中的多個具有統(tǒng)一類型的數(shù)據(jù)元素。它們定義的一般格式為 類型標(biāo)識符 數(shù)組名 [常量表達(dá)式 ]。 ? 二維數(shù)組：存放的是有規(guī)律地按行、列排列的同一類型數(shù)據(jù)。二維數(shù)組定義的一般格式為 類型標(biāo)識符 數(shù)組名 [常量表達(dá)式 1][常量表達(dá)式 2]。 數(shù)組的抽象數(shù)據(jù)類型 將二維數(shù)組 Amn看成一個線性表 A=(A1, A2, ?, An) 其中每一個元素都是一個行向量或列向量的線性表，以行向量為例， Ai又可以表示為 A1=(ai1, ai2, ?, ain) 將上面的分析推廣到多維數(shù)組，它的每個元素可以表示為一個 (n1)維的向量。 根據(jù)前面的分析，可以將數(shù)組的抽象數(shù)據(jù)類型定義如下： ADT ARRAY{ 數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系： R={R1, R2, ?, Rn} ?? 1 2 nj , j , , j i i i iD a n 0 , j i , 1 j b b i稱 為 數(shù) 組 的 維 數(shù) 是 數(shù) 組 第 維 的 下 標(biāo) ≤ ≤ ， 是 數(shù) 組 第 維 的 長 度 。??1 2 nj j ja E l e m e n t s e t2{ , , , , ,? ? ? ? ? ? ? ???? ? ? ? ? ?2 1 n 2 1 n 2 1 n2 1 ni j j j j j 2 j k x i i j j jj j jR a a 1 j b 1 k n k i j b 1 a a D≤ ≤ ≤ ≤ 且 ,1 ≤ ≤}?i 2 , ,n ,n 2≥? 多維數(shù)組一般不進(jìn)行插入和刪除操作，數(shù)組一旦給定以后，每個元素之間的關(guān)系就不會發(fā)生變化了。因此數(shù)組的操作主要有兩個。 (1)取數(shù)組元素的值 (Value(A， amp。e， index1， ? ， indexn))。 (2)修改數(shù)組元素的值 (Assign(amp。A， e， index1， ? ， indexn))。 數(shù)組的順序存儲 數(shù)組的順序存儲方式 數(shù)組的順序存儲的基本操作 數(shù)組的順序存儲方式 ? 因?yàn)槎嗑S數(shù)組主要執(zhí)行的是取值和修改元素的操作，因此宜采用順序存儲的方式。 ? 為了便于查找，人們規(guī)定二維數(shù)組以行序?yàn)橹鬟M(jìn)行存儲或以列序?yàn)橹鬟M(jìn)行存儲。 數(shù)組的順序存儲的基本操作 ? 下面給出了數(shù)組的順序存儲的類型聲明 struct Array { ElemType *base。 //數(shù)組的元素基址，也就是第一個元素的存儲位置 int dim。 //數(shù)組的維數(shù) int *bounds。 //數(shù)組中的每一維的大小 int *constants。 //數(shù)組的映像函數(shù)的常量的基址，即 c0的存儲位置 }。 typedef struct Array Array。 ? 1. Locate操作 Locate操作就是根據(jù)下標(biāo)值求出元素在數(shù)組中的存儲相對地址。 ? 2. Value操作 Value操作就是根據(jù)下標(biāo)取出數(shù)組中元素的值。 矩陣的壓縮存儲 特殊矩陣 稀疏矩陣 特殊矩陣 特殊矩陣是指矩陣中元素的存儲具有一定的規(guī)律。 1．對稱矩陣 在一個 n個方陣中，如果元素滿足下述的性質(zhì) aij=aji 0≤ i， j≤ n1 則稱方陣 A為對稱矩陣。 2．三角矩陣 以主對角線進(jìn)行劃分，三角矩陣可以分為上三角矩陣和下三角矩陣兩種。上三角矩陣的下三角 (不包括主對角線 )中的元素均為常數(shù) c(c一般為 0)，下三角矩陣與上三角矩陣正好相反，它的主對角線上方的元素均為常數(shù) c。 3．對角矩陣 對角矩陣中所有的非零元素集中在以主對角線為中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零的矩陣為對角矩陣。 稀疏矩陣 ? 設(shè)矩陣 Amn中有 s個非零元素，若 s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)，則稱 A為稀疏矩陣。為了能更確切地描述遠(yuǎn)遠(yuǎn)小于這一情況，人們引入了稀疏因子。假設(shè)在 m n的矩陣中，有 t個元素不為零，令 ，則稱為矩陣的稀疏因子。通常認(rèn)為 時稱為稀疏矩陣。 ? 稀疏矩陣的抽象數(shù)據(jù)類型如下 (只列出了一些基本的矩陣運(yùn)算 )。 ADT SparseMatrix{ ? 數(shù)據(jù)對象： D={aij|i=0,?,m 1， i=0,?,n 1， aij ∈elementset ， m,n分別為矩陣的行數(shù)和列數(shù) } ? 數(shù)據(jù)關(guān)系： R={Row, Col} Row={ aij,aij+1 ｜ 0≤i≤n 1， 0≤j≤n 2} Col={ aij,ai+1j ｜ 0≤i≤m 2， 0≤j≤n 1} /t m n? ??? ≤ ? 1．三元組表 用線性表來存儲三元組的方式稱為三元組表。 1) 轉(zhuǎn)置操作 矩陣的轉(zhuǎn)置操作是將一個矩陣由 m n的矩陣變換為 n m的矩陣，并且原矩陣的第 i行變?yōu)樾戮仃嚨牡?j列。 2) 快速轉(zhuǎn)置操作 稀疏矩陣的快速轉(zhuǎn)置操作的主要思想是：在掃描矩陣 M的三元組表的過程中，每遇到一個三元組，就將它的行值和列值交換，并放在矩陣T的三元組表的正確位置上。 3) 相乘操作 兩個矩陣相乘是矩陣的一個常用操作，其計算方法如下。 設(shè)矩陣 M是 m1 n1階的矩陣， N是 n1 n2階的矩陣，則 M與 N相乘得到矩陣 Q是一個 m1 n2階的矩陣，它的元素與 M和 N的關(guān)系如下： Q[i][j]= 0≤ im1， 0≤ jn2 Q[i][j]= 10[ ][ ] [ ][ ]nkM i k N k j???? 在稀疏矩陣相乘的算法中有以下幾點(diǎn)需要注意。 (1)因?yàn)?rpos[i]表示 N中第 i1行第 1個非零元素在 置，因此 rpos[i+1]1就表示第 i1行最后一個非零元素在。 (2)矩陣相乘的基本思想是：在 [p].e，找到滿足 [p].nu=[q].mu的所有 q，然后將[p].e與 [q].e的乘積添加到適當(dāng)?shù)那罄塾嫼偷膕um中。 (3)兩個稀疏矩陣相乘的結(jié)果不一定是稀疏矩陣，相乘的兩個分量 M[i][k] N[k][j]不為零，但累加的結(jié)果可能為零。 ? 2．十字鏈表 十字鏈表與單鏈表相比，其指針域比單鏈表多了一個指向矩陣中下一列的 downf域，其結(jié)點(diǎn)的結(jié)構(gòu)如圖 。 在結(jié)點(diǎn)中 row和 col分別表示非零元素的行號和列號， e表示非零元素的取值， down域指向此非零元素的下一行的非零元素，如沒有非零元素，則為 NULL。 right指向本行中下一個非零元素，如果沒有則為 NULL。 圖 十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)示意圖 廣 義 表 廣義表的定義 廣義表的存儲 廣義表的基本操作 廣義表的定義 廣義表一般記為 GL=(d1， d2， ? ， dn) 其中， GL為廣義表的名稱； n是廣義表的長度； di可以是單個元素也可以是廣義表，如果 di為單個元素則稱其為原子，如果 di為廣義表則稱其為 GL的子表。 對于廣義表的定義需要注意以下幾點(diǎn)。 (1)通常情況下，廣義表用圓括號括起來，用逗號分隔其中的元素。 (2)習(xí)慣上，采用大寫字母表示廣義表的名稱，小寫字母表示廣義表的原子。 (3)若廣義表 GL非空，則 d1為 GL的表頭 (head)，其余元素 (d2， d3， ? ， dn)組成廣義表的表尾 (tail)。 (4)一個廣義表展開后所含括號的層數(shù)稱為廣義表的深度。 廣義表的抽象數(shù)據(jù)類型定義如下： ADT GList{ 數(shù)據(jù)類型： D={ei | i=1,2,?,n。 n≥0, ei∈AtomSet 或 ei∈GList, AtomSet 為某個數(shù)據(jù)對象 } 數(shù)據(jù)關(guān)系： R={ei1,ei | ei1,ei∈D, 2≤i≤n} 廣義表的存儲 因?yàn)閺V義表的元素可以是原子也可以是子表，因此不宜采用順序表。通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)來存儲廣義表。表中的每個元素可以用一個結(jié)點(diǎn)來表示。由于廣義表中的元素可以是原子也可以是子表，因此要為廣義表設(shè)置兩類結(jié)點(diǎn)，一類為原子結(jié)點(diǎn)，另一類為子表結(jié)點(diǎn)。圖 。 圖 廣義表的結(jié)點(diǎn)示意圖 廣義表的基本操作 1. 廣義表的創(chuàng)建 廣義表的創(chuàng)建是根據(jù)字符串 s建立相應(yīng)廣義表。廣義表可以通過下面的遞歸方式進(jìn)行定義。 基本項 歸納項：假設(shè) subs為 s去掉最外層括號對的串，記作“ s1, s2, ?, sn” ，其中 si(i=1, ?, n)為非空字符串。對每個 si建立表結(jié)點(diǎn)，并令其 hp域的指針為由 si建立的子表的頭指針，除最后建立的表結(jié)點(diǎn)的尾指針為 NULL外，其余表結(jié)點(diǎn)的尾指針均指向在它之后建立的表結(jié)點(diǎn)。也就是說，因?yàn)?si是一個字符串，首先為這個字符串建立一個表結(jié)點(diǎn)，表結(jié)點(diǎn)的指針域指向 si中的元素，它的 tp域指向下一次建立的 si+1，而 sn的 tp域?yàn)榭铡? ss???廣 義 表 為 空 表 ， 當(dāng) 為 空 時廣 義 表 為 原 子 結(jié) 點(diǎn) ， 當(dāng) 為 單 字 符 串 時2. 廣義表的打印 廣義表打印的算法思想是：先打印一個左括號“ (” ，若遇到 tag=ATOM，則打印該結(jié)點(diǎn)的值，如果此結(jié)點(diǎn)后面有后繼結(jié)點(diǎn)，則再打印一個“，”。如果 tag=LIST，說明是一個子表，則遞歸調(diào)用函數(shù)，打印這個子表，打印完所有的結(jié)點(diǎn)以后，最后打印一個“ )” 。 3. 求廣義表表頭和表尾 廣義表的結(jié)點(diǎn)定義中 hp用來指向廣義表的表頭結(jié)點(diǎn)， tp用來指向廣義表的表尾結(jié)點(diǎn)，因此很容易得到廣義表的求表頭和表尾算法。