數(shù)據(jù)結(jié)構(gòu)-04串和數(shù)組

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第四章 串和數(shù)組數(shù)組 第四章 串和數(shù)組數(shù)組主要內(nèi)容主要內(nèi)容串的相關(guān)知識串的相關(guān)知識1數(shù)組的定義數(shù)組的定義2特殊矩陣的數(shù)組存儲特殊矩陣的數(shù)組存儲3數(shù)組和串的應(yīng)用數(shù)組和串的應(yīng)用4教學(xué)要求教學(xué)要求教學(xué)重點教學(xué)難點目標(biāo)要求1理解串的基本操作的定義；2. 熟練掌握在串的順序存儲結(jié)構(gòu)上實現(xiàn)串的各種操作的方法3.掌握樸素的模式匹配算法。4.了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組的地址計算方法；5.了解稀疏矩陣的特點和壓縮存儲方法1.樸素的模式匹配運算2.掌握數(shù)組的存儲方式，順序存儲的地址計算公式1.串的匹配運算算法2.稀疏矩陣壓縮存儲表示下實現(xiàn)的算法4.1串串4.1.1 4.1.1 串的定

2、義串的定義串的串的 串的串的 串的串的 是由是由 計算機字符組成的有限序列計算機字符組成的有限序列。 通常記為：通常記為：s = c1 c2 c3 ci cn ( ( n n0 )0 )。字母、數(shù)字或其他字符字母、數(shù)字或其他字符 必須有！必須有！ 但不屬于串！但不屬于串！ 作用：避免作用：避免與與變量名變量名或或數(shù)的常量數(shù)的常量混淆?；煜?。 例例：x = 123 x = 123 test =test 不含任何字符的串，長度不含任何字符的串，長度 n= 0n= 0，用，用表示為表示為表示為表示為S =S =。 僅由一個或多個空格組成的串。僅由一個或多個空格組成的串。 4.1.2 串間關(guān)系串間關(guān)系

3、 S S串中任意串中任意m m （mnmn）個連續(xù)字符構(gòu)成的串稱為）個連續(xù)字符構(gòu)成的串稱為S S的子串。的子串。 相對地，相對地，S S稱為主串。稱為主串。 2. 子串關(guān)系子串關(guān)系1. 相等關(guān)系相等關(guān)系精確相等關(guān)系 左對齊相等關(guān)系 兩串有相同的長度，且自左至右逐對對應(yīng)字符相等時兩串才為相等 不要求兩串有相同的長度自最左的第1個字符開始逐個對應(yīng)字符比較當(dāng)不等時，如何判斷大小關(guān)系包含關(guān)系例：例：S=NanJing S1=Nan Jing S3=“NanJing” S S1 S S2 例：例：S7 =“I am a student now.”，S8 =“student”，S9 =“student.”

4、S7主串主串S8S7子串子串S9非非S7子串子串空串是任意串的子串，任意串是其自身的子串空串是任意串的子串，任意串是其自身的子串字符在序列中的序號。字符在序列中的序號。子串的子串的首字符首字符在主串中的位置。在主串中的位置。 在在S S中的位置：中的位置：8 8 非串非串 S 中的中的連續(xù)連續(xù)字符所字符所組組成成4.1.3串的基本操作串的基本操作1u 串賦值串賦值2u 串精確相等串精確相等3u 串左對齊相等串左對齊相等4u 求串長度求串長度5u 取子串取子串6u 串匹配串匹配7u 并串并串8u 串置換串置換9u 串插入串插入10u 串刪除串刪除4.1.4串的存儲結(jié)構(gòu)串的存儲結(jié)構(gòu)串的存儲結(jié)構(gòu)串的

5、存儲結(jié)構(gòu)與線性表的存儲結(jié)構(gòu)十分相似與線性表的存儲結(jié)構(gòu)十分相似。 區(qū)別是：串的數(shù)據(jù)元素在任何情況下僅是一個區(qū)別是：串的數(shù)據(jù)元素在任何情況下僅是一個單個字符單個字符 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)靜態(tài)順序存儲結(jié)構(gòu)（靜態(tài)順序存儲結(jié)構(gòu)（順序串順序串）動態(tài)順序存儲結(jié)構(gòu)動態(tài)順序存儲結(jié)構(gòu)一次性為串分配好足夠的存儲單元一次性為串分配好足夠的存儲單元塊鏈?zhǔn)酱鎯Y(jié)構(gòu)塊鏈?zhǔn)酱鎯Y(jié)構(gòu)堆存儲結(jié)構(gòu)（堆存儲結(jié)構(gòu)（堆串堆串）隨時擴充和釋放空間隨時擴充和釋放空間 順序串順序串#define M 100typedef structchar chM ； int n ；SSTR ；堆串堆串typedef structchar *ch ；

6、int len ； HSTR ；串的實際長度可在這個預(yù)定義長度范圍內(nèi)隨意設(shè)定，超出則被截斷以一個特殊的字符作為字符串的結(jié)束標(biāo)志，串長是一個隱含值3.1.5關(guān)于串的幾個算法關(guān)于串的幾個算法串的基本操作和線性表有很大差別串的基本操作和線性表有很大差別線性表：線性表：大多以大多以“單個元素單個元素”作為操作對象作為操作對象串：串：通常以通常以“串的整體串的整體”作為操作對象作為操作對象如：在線性表中查找某個元素、求取某個元素、在某個位置上插入一個元素和刪除一個元素等；如：在串中查找某個子串、求取一個子串、在串的某個位置上插入一個子串以及刪除一個子串等。3.1.5關(guān)于串的幾個算法關(guān)于串的幾個算法1.判

7、串精確相等判串精確相等 EQUAL（S，Q）串串S：串串Q：s t u d e n t . s t u d u n t , S.nQ.nint EQUAL(SSTR S,SSTR Q) int i; if(S.n!=Q.n) return 0; elsefor(i=0;S.chi=Q.chi;i+); if(i=S.n-1) return(1); else return(0); i=0i=0 i=1i=1i=2i=2i=3i=3i=4i=4字符字符不等不等返返回回i與與S.n比較比較3.1.5關(guān)于串的幾個算法關(guān)于串的幾個算法2.取子串取子串 SUBSTR（S,pos,len）求子串的過程：為復(fù)

8、制字符序列的過程將串 S中的第 pos 個字符開始的長度為 len 的字符串復(fù)制到串 Sub 中。 d a t a s t r u c t u r e主串主串S：子串子串Q：posalenkkksktkrkukci=0i=70可能出現(xiàn)“參數(shù)非法”的情況，應(yīng)返回 ERROR3.1.5關(guān)于串的幾個算法關(guān)于串的幾個算法3. 串匹配串匹配 MATCH(S,T)就是在主串中找出子串出現(xiàn)的位置就是在主串中找出子串出現(xiàn)的位置如果在主串 S 中能夠找到子串 T， 則稱匹配成功，返回第一個和子串 T 中第一個字符相等的字符在主串S 中的序號；否則，稱匹配失敗，返回 0。簡單匹配算法或樸素匹配算法簡單匹配算法或樸

9、素匹配算法匹配過程是一個字符比較的過程 cdcbabbaacdbai 匹配j不匹配jcdbai 匹配j不匹配jicdba不匹配jicdba不匹配jicdba 匹配j 匹配j 匹配j 匹配jcdbai=i-j+2 返回此元素序號返回此元素序號3.1.5關(guān)于串的幾個算法關(guān)于串的幾個算法4. 并串并串串串S S值值 Q.len+T.len Q.len+T.len MAXSTRLEN MAXSTRLEN Q.len Q.len MAXSTRLEN Q.len+T.len MAXSTRLEN Q.len Q.len = = MAXSTRLEN MAXSTRLEN 在串的靜態(tài)順序存儲結(jié)構(gòu)上實現(xiàn)在串的靜態(tài)順

10、序存儲結(jié)構(gòu)上實現(xiàn)CONCAT(S,Q,T)CONCAT(S,Q,T)，需考慮可能出現(xiàn)的三種情況：需考慮可能出現(xiàn)的三種情況：采用串的堆存儲結(jié)構(gòu)上實現(xiàn)采用串的堆存儲結(jié)構(gòu)上實現(xiàn)CONCAT(S,Q,T)CONCAT(S,Q,T)，不存在串連接時被截斷的問題，不存在串連接時被截斷的問題4.2 數(shù)組數(shù)組數(shù)組是數(shù)組是同類數(shù)據(jù)同類數(shù)據(jù)元素的有序排列。元素的有序排列。4.2.1 數(shù)組的定義數(shù)組的定義相同數(shù)據(jù)類型、相同的存儲空間大小 數(shù)組元素：組成數(shù)組的數(shù)據(jù)元素數(shù)組元素：組成數(shù)組的數(shù)據(jù)元素指數(shù)據(jù)元素的存儲和排列有固定的規(guī)則 一維數(shù)組一維數(shù)組二維數(shù)組二維數(shù)組三維數(shù)組三維數(shù)組.多維數(shù)組多維數(shù)組 int szM= 0

11、，1，2，3，4; M為最多數(shù)組元素個數(shù) sz為數(shù)組名數(shù)組類型為整數(shù)注意：注意：C C語言規(guī)定數(shù)組元素號從語言規(guī)定數(shù)組元素號從0 0起始，到起始，到M-M-1 1為止為止( (一般從一般從1 1數(shù)數(shù)到數(shù)數(shù)到M)M) 數(shù)組元素4.2.2一維數(shù)組一維數(shù)組又稱向量，是一個順序表結(jié)構(gòu)又稱向量，是一個順序表結(jié)構(gòu) 數(shù)組元素即是順序表的數(shù)據(jù)元素或結(jié)點數(shù)組元素即是順序表的數(shù)據(jù)元素或結(jié)點 聲明格式：聲明格式： 數(shù)據(jù)類型數(shù)據(jù)類型 變量名稱變量名稱長度長度；例如：例如： int szM =0，1，2，3，4; 存儲位置地址存儲位置地址( 表示為表示為的形式的形式 )計算公式為計算公式為 = A + ib 數(shù)組存儲空

12、間起始地址 第i號數(shù)組元素元素存儲為b個字節(jié)若一維數(shù)組中的數(shù)據(jù)元素又是一維數(shù)組結(jié)構(gòu)若一維數(shù)組中的數(shù)據(jù)元素又是一維數(shù)組結(jié)構(gòu)二維數(shù)組二維數(shù)組三要素便可隨時求出任一元素的地址：三要素便可隨時求出任一元素的地址：開始結(jié)點的存放地址（即基地址）維數(shù)和每維的上、下界；每個數(shù)組元素所占用的單元數(shù)4.2.3二維數(shù)組二維數(shù)組又稱矩陣，是在橫豎兩個方向上排列數(shù)組元素構(gòu)成的數(shù)組又稱矩陣，是在橫豎兩個方向上排列數(shù)組元素構(gòu)成的數(shù)組聲明格式：聲明格式： 數(shù)據(jù)類型數(shù)據(jù)類型 變量名稱變量名稱長度長度長度長度；例如：例如： int ewszNM （N為行數(shù)，為行數(shù)，M為列數(shù)）為列數(shù)）行行列列二維數(shù)組看成一個一維數(shù)組二維數(shù)組看成

13、一個一維數(shù)組例如：例如：sz4=sz0，sz1，sz2，sz3; wsz45e191817161514131211109876543210sz0sz1sz2sz3szi =(a0j,a1j,am-1,j) 0jN-1 二維數(shù)組順序存儲位置地址二維數(shù)組順序存儲位置地址( 表示為表示為的形式的形式 )計算公式為計算公式為數(shù)組存儲空間起始地址 第i號數(shù)組元素每行M個元素元素存儲為b個字節(jié)根據(jù)一維數(shù)組地址公式根據(jù)一維數(shù)組地址公式 = A + i（Mb） =(A + i（Mb）) + jb = A + iMb + jb = A +（ iM + j）b 某個元素的地址就是它前面所有行所占的單元加上它所在行

14、某個元素的地址就是它前面所有行所占的單元加上它所在行前面所有列元素所占的單元數(shù)之和前面所有列元素所占的單元數(shù)之和 . a1, n-1 . a11 a10 a0, n-1 . a01 a0001n -1m*n -1na00 a01 . a0, n-1a10 a11 . a1, n-1 .例如：例如： 設(shè)數(shù)組設(shè)數(shù)組 A059, 069 的基地址為的基地址為 2048，每個元，每個元 素素占占 2 個存儲單元，順序存儲，則元素個存儲單元，順序存儲，則元素A31, 57 的存儲地的存儲地址為址為 。 解：解：= = =A =A（ i iM + jM + j）b b = 2048 + (31 = 204

15、8 + (3170705757 ) )2 2 = 6502 = 6502 a00 a01 a0, 69 a10 a11 a1, 69 a59, 0 a59, 1 a59, 69 a31, 57 4.3特殊矩陣的數(shù)組存儲特殊矩陣的數(shù)組存儲矩陣的常規(guī)存儲的特點：矩陣的常規(guī)存儲的特點： 可以對其元素進行隨機存??；可以對其元素進行隨機存?。?矩陣運算非常簡單；存儲的密度為矩陣運算非常簡單；存儲的密度為 1 1。 不適宜常規(guī)存儲的矩陣：不適宜常規(guī)存儲的矩陣：值相同的元素很多且呈某種值相同的元素很多且呈某種 規(guī)律分布；零元素多。規(guī)律分布；零元素多。 矩陣的壓縮存儲：矩陣的壓縮存儲：為多個相同的非零元素只分

16、配一個存儲空間；對零元素不為多個相同的非零元素只分配一個存儲空間；對零元素不分配空間。分配空間。 特殊矩陣特殊矩陣稀疏矩陣稀疏矩陣三角形矩陣三角形矩陣對角線矩陣對角線矩陣對稱矩陣對稱矩陣4.3.1對角線矩陣的數(shù)組表示對角線矩陣的數(shù)組表示對角線矩陣是除矩陣主對角線上的元素外，其余所有元素的值都是對角線矩陣是除矩陣主對角線上的元素外，其余所有元素的值都是0 0的矩陣。的矩陣。 nn2211a0a0a將其壓縮存儲到一維數(shù)組中，且能找到將其壓縮存儲到一維數(shù)組中，且能找到每個非零元素和向量下標(biāo)的對應(yīng)關(guān)系每個非零元素和向量下標(biāo)的對應(yīng)關(guān)系定義為定義為int djxszn 當(dāng)當(dāng)i = j時，時，djx(i,j

17、)=djxszi 當(dāng)當(dāng)ij時，時，djx(i,j)= 0。第第i i個元素的存儲地址的計算公式是：個元素的存儲地址的計算公式是：djx = A + i= A + ib b 各參數(shù)含義同前面4.3.2三角形矩陣的數(shù)組表示三角形矩陣的數(shù)組表示以主對角線劃分，三角矩陣有上（以主對角線劃分，三角矩陣有上（下下）三角兩種。）三角兩種。上（上（下下）三角矩陣的下（）三角矩陣的下（上上）三角（不含主對角線）中的元素均為常數(shù)）三角（不含主對角線）中的元素均為常數(shù)( (通常為通常為0)0)。nnn222n11211a00aa0aaann2n1n222111aaa0aa00a上三角矩陣上三角矩陣下三角矩陣下三角矩

18、陣三角矩陣的存儲：三角矩陣的存儲：存儲主對角線和上（存儲主對角線和上（下下）三）三 角中的元素。角中的元素。用一維數(shù)組用一維數(shù)組sjxszM存儲存儲 ，其中其中 M= n(1+n)/2 對稱矩陣上下三角中的元素數(shù)均為：對稱矩陣上下三角中的元素數(shù)均為： 1 + 2 + + n = n(1+n)/2 =n(n + 1)/2 k = 0 1 2 3 n(n-1)/2 n(n+1)/21 a11a21a22a31a32 an1ann如：一維數(shù)組如：一維數(shù)組 sjxszM存儲下三角矩陣存儲下三角矩陣存儲地址計算公式存儲地址計算公式 = = = = = A + (i(i-1)/2+j-1)b= A + (

19、i(i-1)/2+j-1)b 各參數(shù)含義同前面k = 1 + 2 + + (i - 1) = (1+(i-1)(i-1)/2 = i(i-1)/24.3.3對稱矩陣的數(shù)組表示對稱矩陣的數(shù)組表示數(shù)據(jù)元素值以主對角線為對稱軸對應(yīng)相等數(shù)據(jù)元素值以主對角線為對稱軸對應(yīng)相等 nnnnnnaaaaaaaaa212222111211存儲對稱矩陣存儲對稱矩陣忽略主對角線上方的所有數(shù)據(jù)元素忽略主對角線上方的所有數(shù)據(jù)元素或忽略主對角線下方的所有數(shù)據(jù)元素或忽略主對角線下方的所有數(shù)據(jù)元素 下三角形矩陣下三角形矩陣 上三角形矩陣上三角形矩陣 滿足滿足a aijij=a=ajiji 對稱矩陣上下三角中的元素數(shù)均為：對稱矩

20、陣上下三角中的元素數(shù)均為：n(n + 1)/2 4.3.4稀疏矩陣的數(shù)組表示稀疏矩陣的數(shù)組表示稀疏矩陣是稀疏矩陣是0 0元素較多，且出現(xiàn)位置無固定規(guī)律的矩陣元素較多，且出現(xiàn)位置無固定規(guī)律的矩陣 060000900000004007200010003005M壓縮存儲原則：存各非零元的值、行列位置和矩陣的行列數(shù)壓縮存儲原則：存各非零元的值、行列位置和矩陣的行列數(shù) 例如：例如：5 56 6的稀疏矩陣，只有的稀疏矩陣，只有8 8個非個非0 0元素元素用形如（行號用形如（行號, ,列號列號, ,元素值）的三元組表示之元素值）的三元組表示之, ,一般表示為（一般表示為（i,j,vi,j,v） ijv該非零元素的值該非零元素的列號該非零元素的行號三元組表結(jié)點：三元組表結(jié)點：用三元組線性表表示：用三元組線性表表示： 1,1,5,1,4,3,2,2,1,3,1,7, 2,6,23,4,4,4,6,9,5,5,6三元組線性表結(jié)構(gòu)示意