線性結(jié)構(gòu)（線性表、棧、隊、串、數(shù)組）數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)物理（存儲）結(jié)構(gòu)數(shù)據(jù)運(yùn)算非線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)插入運(yùn)算刪除運(yùn)算修改運(yùn)算查找運(yùn)算排序運(yùn)算數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容2.3串2.3.1串及其基本運(yùn)算

1.串的基本概念

2.串的基本運(yùn)算2.3.2串的定長順序存儲及基本運(yùn)算

1.串的定長順序存儲

2.定長順序串的基本運(yùn)算2.3.1串及其基本運(yùn)算:串的基本概念

S=“a1,a2,……..,an”(n≥0)

串名串值（用“”括起來，引號不是串值。）串（String）是由零個或多個任意字符（含空格）組成的有限序列。記作:S=“a1a2…an”S是串的名字“a1a2…an”是串的值，必須用引號括起來ai是串中的字符，可以是字母、數(shù)字或其他字符n是串的長度2.3.1串及其基本運(yùn)算:串的基本概念子串：串S中任意個連續(xù)的字符組成的子序列。包含子串的串S稱為主串。子串（在主串中）的位置：子串的第一個字符在主串中的位置。兩個串相等：兩個串長度相等且每個對應(yīng)位置上字符相等。字符位置：字符在串中的序號。串長：串中字符個數(shù)（n≥0），n=0時稱為空串

。2.3.1串及其基本運(yùn)算:串的基本概念區(qū)分空串和空格串：空串：n（串的長度）＝0時的串空格串：由一個或多個空格組成的串空串的長度一定為0；空格串的長度一定大于0，但具體值由空格的個數(shù)決定示例串A＝“ChinaNanjing”，

B＝“Nanjing”，C＝“China”，D＝“inaN”，E＝“iij”,F＝“iij”問：1）其中，B、C、D、E、F中哪些是A的子串，哪些不是？

2）如果是A的子串，則在A中的位置分別是多少？

3）D、E、F的長度分別是多少？E是否與F相等？B、C、D是A的子串，E、F不是A的子串。字串B的位置為7，字串C的位置為1，字串D的位置為3。D、E、F的長度分別是5、3、4。字串E與字串F不相等。2串的基本運(yùn)算1)求串長StrLength(s)操作條件：串s存在操作結(jié)果：求出串s的長度。2)串賦值StrAssign(s1,s2)操作條件：s1是一個串變量，s2或者是一個串常量，或者是一個串變量。操作結(jié)果：將s2的串值賦值給s1，s1原來的值被覆蓋掉。2串的基本運(yùn)算3)串的連接(concatenation

)操作：StrConcat(s1,s2,s)或StrConcat(s1,s2)操作條件：串s1,s2存在。操作結(jié)果：兩個串的連接就是將一個串的串值緊接著放在另一個串的后面，連接成一個串。4)求子串SubStr(s,i,len)：操作條件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作結(jié)果：返回從串s的第i個字符開始的長度為len的子串。len=0得到的是空串。例如：SubStr(“abcdefghi”,3,4)=“cdef”2串的基本運(yùn)算5)串比較StrCmp(s1,s2)操作條件：串s1,s2存在。操作結(jié)果：若s1==s2，操作返回值為0；若s1<s2,返回值<0；若s1>s2,返回值>0。6)子串定位StrIndex(s,t)：找子串t在主串s中首次出現(xiàn)的位置操作條件：串s,t存在。操作結(jié)果：若t∈s，則操作返回t在s中首次出現(xiàn)的位置，否則返回值為-1。例如：StrIndex(“abcdebda”,“bc”)=2StrIndex(“abcdebda”,“ba”)=-1給定兩個串s1=“a1a2…an”,s2=“b1b2…bm”，s1<s2表示兩個串中第一個不匹配的字符ai和bj，有ai<bj。2串的基本運(yùn)算7)串插入StrInsert(s,i,t)操作條件：串s,t存在，且1≤i≤StrLength(s)+1。操作結(jié)果：將串t插入到串s的第i個字符位置上，s的串值發(fā)生改變。例如：s=“Thisabook”,t=“is” StrInsert(s,6,t)=“Thisisabook”8)串刪除StrDelete(s,i,len)操作條件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作結(jié)果：刪除串s中從第i個字符開始的長度為len的子串，s的串值改變。例如：s=“Thisabook”

StrDelete(s,6,2)=“Thisbook”2串的基本運(yùn)算9)串替換StrRep(s,t,r)操作條件：串s,t,r存在，t不為空。操作結(jié)果：用串r替換串s中出現(xiàn)的所有與串t相等的不重疊的子串，s的串值改變。例如：s=“Heisastudent”,t=“He”,r=“She” StrRep(s,t,r)=“Sheisastudent”設(shè)s

=“IAMASTUDENT”,t

=“GOOD”,q=“WORKER”。求：練習(xí)：(1)StrLength(s)=

(2)StrLength(t)=(3)SubString(s,8,7)=(4)SubString(t,2,1)=(5)StrIndex(s,“A”)=(6)StrIndex(s,t

)=(7)StrRep(s,“STUDENT”,q)=144“STUDENT”“O”3-1（s中沒有t?。癐AMAWORKER”2.3.2串的定長順序存儲及基本運(yùn)算強(qiáng)調(diào)：串與線性表的運(yùn)算有所不同，是以“串的整體”作為操作對象，例如查找某子串，在主串某位置上插入一個子串等。串存儲方法有：

定長順序存儲結(jié)構(gòu)、塊鏈?zhǔn)酱鎯Y(jié)構(gòu)等。2.3.2串的定長順序存儲及基本運(yùn)算1.串的定長順序存儲定長順序存儲表示——用一組地址連續(xù)的存儲單元存儲串值中的字符序列。定長是指按預(yù)定義的大小，為每一個串變量分配一個固定長度的存儲區(qū)。例如：#defineMAXSIZE256 chars[MAXSIZE];

則串的最大長度不能超過256。問題：如何標(biāo)識實(shí)際長度？

2.3.2串的定長順序存儲及基本運(yùn)算1.串的定長順序存儲如何標(biāo)識實(shí)際長度：方法1：專用變量，指向最后一個字符的指針方法2：在串尾存儲特殊字符作為串的終結(jié)符方法3：用s[0]存放串的實(shí)際長度方法1.

用一個指示變量來指向最后一個字符。這樣表示的串描述如下：typedefstruct{chardata[MAXSIZE];intstrlen;}SeqString;…s.strlen=10012345678910...

MAXSIZE-1abcdefghijk

2.3.2串的定長順序存儲及基本運(yùn)算例如：SeqStrings;這種存儲方式可以直接得到串的長度=(s.strlen+1)。如圖所示:方法2.

在串尾存儲一個不會在串中出現(xiàn)的特殊字符作為串的終結(jié)符，以此表示串的結(jié)尾。\0012345678910...

MAXSIZE-1abcdefghijk

…

2.3.2串的定長順序存儲及基本運(yùn)算比如C語言用’\0’(ascii碼值為0的NULL字符)來表示串的結(jié)束。這種存儲方法不能直接得到串的長度，是用判斷當(dāng)前字符是否是’\0’來確定串是否結(jié)束，從而求得串的長度。

chars[MAXSIZE];注意：字符‘\0’標(biāo)識串的結(jié)束，不在串長計算范圍之內(nèi)。

方法3.設(shè)定長串存儲空間：chars[MAXSIZE+1];用s[0]存放串的實(shí)際長度，串值存放在s[1]~s[MAXSIZE]。2.3.2串的定長順序存儲及基本運(yùn)算串的定長順序存儲（串的定長順序存儲）缺點(diǎn)：

1)需要預(yù)先定義一個串允許的最大字符個數(shù)，當(dāng)估計過大時存儲效率就降低。

2)插入與刪除操作需要移動字符。2.定長順序串的基本運(yùn)算

(1)串的聯(lián)接

(2)求子串

(3)串比較其他：串的塊鏈?zhǔn)酱鎯Y(jié)構(gòu)小結(jié)

串是零個或多個字符組成的有限序列，是一種特殊的線性表。它的每個結(jié)點(diǎn)元素僅由一個字符組成。另外，串上的操作主要針對串的整體或串的某一部分子串進(jìn)行，不同于一般線性表是針對表中某一結(jié)點(diǎn)元素進(jìn)行的。數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容線性結(jié)構(gòu)（線性表、棧、隊、串、數(shù)組）邏輯結(jié)構(gòu)唯一存儲結(jié)構(gòu)不唯一運(yùn)算的實(shí)現(xiàn)依賴于存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)物理（存儲）結(jié)構(gòu)數(shù)據(jù)運(yùn)算非線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)插入運(yùn)算刪除運(yùn)算修改運(yùn)算查找運(yùn)算排序運(yùn)算第2章2.4數(shù)組、特殊矩陣2.4.1多維數(shù)組

1.數(shù)組的邏緝結(jié)構(gòu)

2.數(shù)組的內(nèi)存映象2.4.2特殊矩陣的壓縮存儲*

1.對稱矩陣

2.三角矩陣

3.稀疏矩陣數(shù)組可以看作線性表的推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)其特點(diǎn)是數(shù)據(jù)元素本身可以是一個數(shù)據(jù)結(jié)構(gòu)（具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型）。數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個數(shù)據(jù)元素有唯一的一組下標(biāo)來標(biāo)識。在數(shù)組上不能做插入、刪除數(shù)據(jù)元素的操作。在數(shù)組中通常做下面兩種操作：(1)取值操作：給定一組下標(biāo)，讀取對應(yīng)的數(shù)據(jù)元素(2)賦值操作：給定一組下標(biāo)，修改與其相對應(yīng)的數(shù)據(jù)元素第2章2.4數(shù)組、特殊矩陣2.4.1多維數(shù)組1.數(shù)組的邏輯結(jié)構(gòu)注意：

數(shù)據(jù)結(jié)構(gòu)中數(shù)組與高級語言中數(shù)組的區(qū)別：高級語言中的數(shù)組是順序結(jié)構(gòu)；而數(shù)據(jù)結(jié)構(gòu)中的數(shù)組既可以是順序的，也可以是鏈?zhǔn)浇Y(jié)構(gòu)，用戶可根據(jù)需要選擇。數(shù)組是n(n≥0)個相同數(shù)據(jù)類型數(shù)據(jù)元素構(gòu)成的有限序列。一維數(shù)組是一個線性表。二維數(shù)組的任何一行/列都是一個線性表。a11a12…a1n

a21a22…a2n

…………

am1am2…amn

Amn=一維數(shù)組的特點(diǎn)：定長線性表（別名向量）除第一個元素外，其他每一個元素有一個且僅有一個直接前驅(qū)。除最后一個元素外，其他每一個元素有一個且僅有一個直接后繼。

數(shù)組的邏輯結(jié)構(gòu)a1a11a12……..a1n

a2a21a22……..a2n

amam1am2……..amn

….ai=(ai1,ai2,……..,ain)(1<=i<=m)——行向量數(shù)組是線性表的推廣二維數(shù)組的定義:數(shù)據(jù)元素是一維數(shù)組的一維數(shù)組。

數(shù)組的邏輯結(jié)構(gòu)?i=(?1i,

?2i,

……..

,

?mi)(1<=i<=n)——列向量?1a11a21……am1?2a12a22……am2?na1na2n……amn…………………………

數(shù)組的邏輯結(jié)構(gòu)二維數(shù)組的定義:數(shù)據(jù)元素是一維數(shù)組的一維數(shù)組。

二維數(shù)組三維數(shù)組行向量下標(biāo)

i頁向量下標(biāo)

i列向量下標(biāo)

j行向量下標(biāo)

j

列向量下標(biāo)

k

數(shù)組的邏輯結(jié)構(gòu)討論：“數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡單”，對嗎？答：對的。因?yàn)椋孩贁?shù)組中各元素具有統(tǒng)一的數(shù)據(jù)類型；②數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。③數(shù)組的基本操作比較簡單，除了結(jié)構(gòu)的初始化和銷毀之外，只有讀取元素（取值）和賦值的操作。2.數(shù)組的順序表示（數(shù)組的內(nèi)存映象）數(shù)組建立后，數(shù)據(jù)元素個數(shù)和元素之間的關(guān)系就不再發(fā)生變動，因而非常適合采用順序存儲結(jié)構(gòu)。問題：內(nèi)存的地址空間是一維的，對應(yīng)一維數(shù)組（向量）；數(shù)組可以是多維的；兩者之間的對應(yīng)關(guān)系： 通過映象函數(shù)實(shí)現(xiàn)，根據(jù)數(shù)組元素的下標(biāo)得到它的存儲地址。2.數(shù)組的內(nèi)存映象一維數(shù)組的特點(diǎn)：二維數(shù)組的特點(diǎn)：2個下標(biāo)，每個元素ai,j受到兩個關(guān)系（行關(guān)系和列關(guān)系）的約束：一個m×n的二維數(shù)組可以看成是m行的一維數(shù)組（向量），或者n列的一維數(shù)組（向量）。N維數(shù)組的特點(diǎn)：

n個下標(biāo)，每個元素受到n個關(guān)系約束一個n維數(shù)組可以看成是由若干個n－1維數(shù)組組成的線性表。1個下標(biāo)，ai是ai+1的直接前驅(qū)數(shù)組的順序存儲表示和實(shí)現(xiàn)問題：計算機(jī)的存儲結(jié)構(gòu)是一維的，而數(shù)組一般是多維的，怎樣存放？解決辦法：事先約定按某種次序?qū)?shù)組元素排成一個線性序列（向量），然后將這個線性序列存入存儲器中。例如：在二維數(shù)組中，我們既可以規(guī)定按行存儲，也可以規(guī)定按列存儲。注意：若規(guī)定好了次序，則數(shù)組中任意一個元素的存放地址便有規(guī)律可尋，可形成地址計算公式；約定的次序不同，則計算元素地址的公式也有所不同；⑴行優(yōu)先順序——將數(shù)組元素按行排列，第i+1個行向量緊接在第i個行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲的線性序列為：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn

通常有兩種順序存儲方式：amn……..

am2am1……….a2n……..

a22a21a1n

…….a12

a11

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….任意元素aij的存儲位置：loc(aij)=loc(a11)+[]×LL為每個元素的存儲大小

按行優(yōu)先順序存放(i-1)×n+(j-1)⑵列優(yōu)先順序——將數(shù)組元素按列向量排列，第j+1個列向量緊接在第j個列向量之后，二維數(shù)組A的m*n個元素按列優(yōu)先順序存儲的線性序列為：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anmamn……..

a2na1n……….am2……..

a22a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a