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

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

3、 S S串中任意串中任意m m （mnmn）個(gè)連續(xù)字符構(gòu)成的串稱(chēng)為）個(gè)連續(xù)字符構(gòu)成的串稱(chēng)為S S的子串。的子串。 相對(duì)地，相對(duì)地，S S稱(chēng)為主串。稱(chēng)為主串。 2. 子串關(guān)系子串關(guān)系1. 相等關(guān)系相等關(guān)系精確相等關(guān)系 左對(duì)齊相等關(guān)系 兩串有相同的長(zhǎng)度，且自左至右逐對(duì)對(duì)應(yīng)字符相等時(shí)兩串才為相等 不要求兩串有相同的長(zhǎng)度自最左的第1個(gè)字符開(kāi)始逐個(gè)對(duì)應(yīng)字符比較當(dāng)不等時(shí)，如何判斷大小關(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子串子串空串是任意串的子串，任意串是其自身的子串空串是任意串的子串，任意串是其自身的子串字符在序列中的序號(hào)。字符在序列中的序號(hào)。子串的子串的首字符首字符在主串中的位置。在主串中的位置。 在在S S中的位置：中的位置：8 8 非串非串 S 中的中的連續(xù)連續(xù)字符所字符所組組成成4.1.3串的基本操作串的基本操作1u 串賦值串賦值2u 串精確相等串精確相等3u 串左對(duì)齊相等串左對(duì)齊相等4u 求串長(zhǎng)度求串長(zhǎng)度5u 取子串取子串6u 串匹配串匹配7u 并串并串8u 串置換串置換9u 串插入串插入10u 串刪除串刪除4.1.4串的存儲(chǔ)結(jié)構(gòu)串的存儲(chǔ)結(jié)構(gòu)串的存儲(chǔ)結(jié)構(gòu)串的

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

6、int len ； HSTR ；串的實(shí)際長(zhǎng)度可在這個(gè)預(yù)定義長(zhǎng)度范圍內(nèi)隨意設(shè)定，超出則被截?cái)嘁砸粋€(gè)特殊的字符作為字符串的結(jié)束標(biāo)志，串長(zhǎng)是一個(gè)隱含值3.1.5關(guān)于串的幾個(gè)算法關(guān)于串的幾個(gè)算法串的基本操作和線性表有很大差別串的基本操作和線性表有很大差別線性表：線性表：大多以大多以“單個(gè)元素單個(gè)元素”作為操作對(duì)象作為操作對(duì)象串：串：通常以通常以“串的整體串的整體”作為操作對(duì)象作為操作對(duì)象如：在線性表中查找某個(gè)元素、求取某個(gè)元素、在某個(gè)位置上插入一個(gè)元素和刪除一個(gè)元素等；如：在串中查找某個(gè)子串、求取一個(gè)子串、在串的某個(gè)位置上插入一個(gè)子串以及刪除一個(gè)子串等。3.1.5關(guān)于串的幾個(gè)算法關(guān)于串的幾個(gè)算法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)于串的幾個(gè)算法關(guān)于串的幾個(gè)算法2.取子串取子串 SUBSTR（S,pos,len）求子串的過(guò)程：為復(fù)

8、制字符序列的過(guò)程將串 S中的第 pos 個(gè)字符開(kāi)始的長(zhǎng)度為 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)于串的幾個(gè)算法關(guān)于串的幾個(gè)算法3. 串匹配串匹配 MATCH(S,T)就是在主串中找出子串出現(xiàn)的位置就是在主串中找出子串出現(xiàn)的位置如果在主串 S 中能夠找到子串 T， 則稱(chēng)匹配成功，返回第一個(gè)和子串 T 中第一個(gè)字符相等的字符在主串S 中的序號(hào)；否則，稱(chēng)匹配失敗，返回 0。簡(jiǎn)單匹配算法或樸素匹配算法簡(jiǎn)單匹配算法或樸

9、素匹配算法匹配過(guò)程是一個(gè)字符比較的過(guò)程 cdcbabbaacdbai 匹配j不匹配jcdbai 匹配j不匹配jicdba不匹配jicdba不匹配jicdba 匹配j 匹配j 匹配j 匹配jcdbai=i-j+2 返回此元素序號(hào)返回此元素序號(hào)3.1.5關(guān)于串的幾個(gè)算法關(guān)于串的幾個(gè)算法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)順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)在串的靜態(tài)順

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

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

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

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

14、某個(gè)元素的地址就是它前面所有行所占的單元加上它所在行前面所有列元素所占的單元數(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，每個(gè)元，每個(gè)元 素素占占 2 個(gè)存儲(chǔ)單元，順序存儲(chǔ)，則元素個(gè)存儲(chǔ)單元，順序存儲(chǔ)，則元素A31, 57 的存儲(chǔ)地的存儲(chǔ)地址為址為 。 解：解：= = =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ù)組存儲(chǔ)特殊矩陣的數(shù)組存儲(chǔ)矩陣的常規(guī)存儲(chǔ)的特點(diǎn)：矩陣的常規(guī)存儲(chǔ)的特點(diǎn)： 可以對(duì)其元素進(jìn)行隨機(jī)存取；可以對(duì)其元素進(jìn)行隨機(jī)存?。?矩陣運(yùn)算非常簡(jiǎn)單；存儲(chǔ)的密度為矩陣運(yùn)算非常簡(jiǎn)單；存儲(chǔ)的密度為 1 1。 不適宜常規(guī)存儲(chǔ)的矩陣：不適宜常規(guī)存儲(chǔ)的矩陣：值相同的元素很多且呈某種值相同的元素很多且呈某種 規(guī)律分布；零元素多。規(guī)律分布；零元素多。 矩陣的壓縮存儲(chǔ)：矩陣的壓縮存儲(chǔ)：為多個(gè)相同的非零元素只分

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

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

18、陣三角矩陣的存儲(chǔ)：三角矩陣的存儲(chǔ)：存儲(chǔ)主對(duì)角線和上（存儲(chǔ)主對(duì)角線和上（下下）三）三 角中的元素。角中的元素。用一維數(shù)組用一維數(shù)組sjxszM存儲(chǔ)存儲(chǔ) ，其中其中 M= n(1+n)/2 對(duì)稱(chēng)矩陣上下三角中的元素?cái)?shù)均為：對(duì)稱(chēng)矩陣上下三角中的元素?cái)?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存儲(chǔ)下三角矩陣存儲(chǔ)下三角矩陣存儲(chǔ)地址計(jì)算公式存儲(chǔ)地址計(jì)算公式 = = = = = 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對(duì)稱(chēng)矩陣的數(shù)組表示對(duì)稱(chēng)矩陣的數(shù)組表示數(shù)據(jù)元素值以主對(duì)角線為對(duì)稱(chēng)軸對(duì)應(yīng)相等數(shù)據(jù)元素值以主對(duì)角線為對(duì)稱(chēng)軸對(duì)應(yīng)相等 nnnnnnaaaaaaaaa212222111211存儲(chǔ)對(duì)稱(chēng)矩陣存儲(chǔ)對(duì)稱(chēng)矩陣忽略主對(duì)角線上方的所有數(shù)據(jù)元素忽略主對(duì)角線上方的所有數(shù)據(jù)元素或忽略主對(duì)角線下方的所有數(shù)據(jù)元素或忽略主對(duì)角線下方的所有數(shù)據(jù)元素 下三角形矩陣下三角形矩陣 上三角形矩陣上三角形矩陣 滿足滿足a aijij=a=ajiji 對(duì)稱(chēng)矩陣上下三角中的元素?cái)?shù)均為：對(duì)稱(chēng)矩

20、陣上下三角中的元素?cái)?shù)均為：n(n + 1)/2 4.3.4稀疏矩陣的數(shù)組表示稀疏矩陣的數(shù)組表示稀疏矩陣是稀疏矩陣是0 0元素較多，且出現(xiàn)位置無(wú)固定規(guī)律的矩陣元素較多，且出現(xiàn)位置無(wú)固定規(guī)律的矩陣 060000900000004007200010003005M壓縮存儲(chǔ)原則：存各非零元的值、行列位置和矩陣的行列數(shù)壓縮存儲(chǔ)原則：存各非零元的值、行列位置和矩陣的行列數(shù) 例如：例如：5 56 6的稀疏矩陣，只有的稀疏矩陣，只有8 8個(gè)非個(gè)非0 0元素元素用形如（行號(hào)用形如（行號(hào), ,列號(hào)列號(hào), ,元素值）的三元組表示之元素值）的三元組表示之, ,一般表示為（一般表示為（i,j,vi,j,v） ijv該非零元素的值該非零元素的列號(hào)該非零元素的行號(hào)三元組表結(jié)點(diǎn)：三元組表結(jié)點(diǎn)：用三元組線性表表示：用三元組線性表表示： 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)示意