串、數(shù)組和廣義表的概念和基本操作

1、串、數(shù)組和廣義表的概念和基本操作學(xué)習(xí)目標(biāo)：1.掌握串、空串、空格串、子串、主串、位置、兩串相等的概念；了解串有哪些基本操作。 2.掌握數(shù)組的概念；理解數(shù)組的順序存儲(chǔ)的含義，掌握順序存儲(chǔ)的定位公式。3.掌握廣義表的概念及其結(jié)構(gòu)特點(diǎn)，了解廣義表的遞歸算法。重點(diǎn)難點(diǎn)：串的概念，串的表示，矩陣的壓縮存儲(chǔ)。4.1 串類型的定義4.2 串的表示和實(shí)現(xiàn)5.1 數(shù)組的定義5.2 數(shù)組的順序表示和實(shí)現(xiàn)5.3 矩陣的壓縮存儲(chǔ) 教學(xué)內(nèi)容內(nèi)容回顧棧的特點(diǎn)及其表示實(shí)現(xiàn)隊(duì)列的特點(diǎn)及其表示實(shí)現(xiàn)串和基本概念串(String):零個(gè)或多個(gè)字符組成的有限序列.如：S=a1a2a3an(n0),其中，S是串的名，單引號(hào)括起來(lái)的字符

2、序列是串的值；ai（1in）可以是字母、數(shù)字或其它字符，單引號(hào)本身不屬于串,它的作用只是為了避免與變量名或數(shù)的常量混淆。串長(zhǎng)(string length)：串中所包含的字符個(gè)數(shù)。 strLength(s)=n第四章 串空串(Empty String):0個(gè)字符的串，串的長(zhǎng)度為零，它不包含任何字符,一個(gè)空串用 表示?？崭翊?Blank String)：由一個(gè)或多個(gè)空格組成的串。注意：空串和空格串的不同，例如 和分別表示長(zhǎng)度為1的空格串和長(zhǎng)度為0的空串。子串:串中任意個(gè)連續(xù)字符組成的子序列。主串:包含子串的串。如求 S=abc的子串？一個(gè)長(zhǎng)度為n的串有多少個(gè)子串？子串在主串中的位置:以子串的第一個(gè)

3、字符在主串中的位置來(lái)表示.如：a,b,c,d分別為: a=BEI, b=JING, c=BEIJING, d=BEI JING, 長(zhǎng)度分別為？子串？主串？子串在主串中的位置？稱兩個(gè)串是相等的，當(dāng)且僅當(dāng)這兩個(gè)串的值相等，即只有當(dāng)兩個(gè)串的長(zhǎng)度相等，并且各個(gè)對(duì)應(yīng)位置的字符相等時(shí)才相等。注意：空串是任意串的子串，任意串是其自身的子串。串常量：和整常數(shù)、實(shí)常數(shù)一樣，在程序中只能被引用但不能改變其值，即只能讀不能寫。如：const char ch=“hello”，串變量：其取值是可以改變的。2.串的抽象數(shù)據(jù)類型的定義ADT String 數(shù)據(jù)對(duì)象：D ai |aiCharacterSet, i=1,2,.

4、,n, n0 數(shù)據(jù)關(guān)系：R1 | ai-1, ai D, i=2,.,n 串是有限長(zhǎng)的字符序列，由一對(duì)單引號(hào)相括，如: a string 基本操作 StrAssign (&T, chars) StrCopy (&T, S) DestroyString(&S) StrEmpty (S) StrCompare (S, T) StrLength(S) Concat (&T, S1, S2)SubString (&Sub, S, pos, len) Index (S, T, pos) Replace (&S, T, V)StrInsert (&S, pos, T) StrDelete (&S, pos

5、, len) ClearString (&S) ADT String SubString (&Sub, S, pos, len)初始條件： 串 S 存在，1posStrLength(S) 且0lenStrLength(S)-pos+1。操作結(jié)果： 用 Sub 返回串 S 的第 pos 個(gè)字符起 長(zhǎng)度為 len 的子串。 基本操作例1： SubString( sub, commander, 4, 3) 求得 sub = man ； SubString( sub, commander, 1, 9)求得 sub = commander； SubString( sub, commander, 9, 1

6、)求得 sub = r；子串為“串”中的一個(gè)字符子序列SubString(sub, commander, 4, 7) sub = ? SubString(sub, beijing, 7, 2) = ? sub = ?SubString(sub，student, 5, 0) = 起始位置和子串長(zhǎng)度之間存在約束關(guān)系0lenStrLength(S)-pos+1長(zhǎng)度為 0 的子串為“合法”串Index (S, T, pos)初始條件：串S和T存在，T是非空串， 1posStrLength(S)。操作結(jié)果： 若主串 S 中存在和串 T 值相同 的子串, 則返回它在主串 S 中第pos個(gè) 字符之后第一次出

7、現(xiàn)的位置； 否則函數(shù)值為0。 例2： S = abcaabcaaabc, T = bca Index(S, T, 1) = 2；Index(S, T, 3) = 6；Index(S, T, 8) = 0； “子串在主串中的位置”意指子串中的第一個(gè)字符在主串中的位序。 Replace (&S, T, V) 初始條件：串S, T和 V 均已存在，且 T 是非空串。 操作結(jié)果：用V替換主串S中出現(xiàn)的所有與（模式串）T相等的不重疊的子串。 例3：假設(shè) S = abcaabcaaabca，T =bca若 V = x， 則經(jīng)置換后得到 S = axaxaax若 V = bc，則經(jīng)置換后得到 S = abc

8、abcaabc StrInsert (&S, pos, T)初始條件：串S和T存在， 1posStrLength(S)1。操作結(jié)果：在串S的第pos個(gè)字符之前 插入串T。例4：S = chater，T = rac， 則執(zhí)行 StrInsert(S, 4, T)之后得到 S = character 對(duì)于串的基本操作集可以有不同的定義方法，在使用高級(jí)程序設(shè)計(jì)語(yǔ)言中的串類型時(shí)，應(yīng)以該語(yǔ)言的參考手冊(cè)為準(zhǔn)。 gets(str) 輸入一個(gè)串； puts(str) 輸出一個(gè)串； strcat(str1, str2) 串聯(lián)接函數(shù)； strcpy(str1, str2, k) 串復(fù)制函數(shù)； strcmp(str

9、1, str2) 串比較函數(shù)； strlen(str) 求串長(zhǎng)函數(shù)；例如：C語(yǔ)言函數(shù)庫(kù)中提供下列串處理函數(shù)： 在上述抽象數(shù)據(jù)類型定義的13種操作中， 串賦值StrAssign、串比較StrCompare、 求串長(zhǎng)StrLength、串聯(lián)接Concat、 求子串SubString 等五種操作構(gòu)成串類型的最小操作子集。 即：這些操作不可能利用其他串操作來(lái)實(shí)現(xiàn)，反之，其他串操作（除串清空ClearString和串銷DestroyString 外）可在這個(gè)最小操作子集上實(shí)現(xiàn)。 串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對(duì)象約束為字符集。 串的基本操作和線性表有很大差別。 在線性表的基本操作中，大

10、多以“單個(gè)元素”作為操作對(duì)象； 在串的基本操作中，通常以“串的整體”作為操作對(duì)象。 在程序設(shè)計(jì)語(yǔ)言中，串只是作為輸入或輸出的常量出現(xiàn)，則只需存儲(chǔ)此串的串值，即字符序列即可。但在多數(shù)非數(shù)值處理的程序中，串也以變量的形式出現(xiàn)。3. 串的表示和實(shí)現(xiàn) 按這種串的表示方法實(shí)現(xiàn)串的運(yùn)算時(shí)，其基本操作為 “字符序列的復(fù)制”。 用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序 列，即按照預(yù)定義大小，為每一個(gè)定義的串變量分配一個(gè)固定長(zhǎng)度的存儲(chǔ)區(qū)。串的實(shí)際長(zhǎng)度可在這個(gè)預(yù)定義長(zhǎng)度的范圍內(nèi)隨意設(shè)定，超過(guò)預(yù)定義長(zhǎng)度的串值則被舍去，稱之為“截?cái)唷?。串的定長(zhǎng)順序存儲(chǔ)表示導(dǎo)入 線性表、棧、隊(duì)列、串：要求數(shù)據(jù)結(jié)構(gòu)中的元素必須有相同的

11、屬性，即數(shù)據(jù)類型；其中元素的數(shù)據(jù)類型只要相同即可，當(dāng)然也可以就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。第五章 數(shù)組和廣義表1、數(shù)組的定義數(shù)組：它是n（n1)個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,an-1構(gòu)成的占用一塊地址連續(xù)的內(nèi)存單元的有限序列。注意：（1）C語(yǔ)言的數(shù)組定義下標(biāo)從0開(kāi)始。（2）數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。（3）一個(gè)二維數(shù)組可以看作每個(gè)數(shù)據(jù)元素是一個(gè)一維數(shù)組的一維數(shù)組。二維數(shù)組是兩維的，內(nèi)存單元是一維的，存在向內(nèi)存存儲(chǔ)時(shí)二維數(shù)組中數(shù)據(jù)元素的存儲(chǔ)方法問(wèn)題，C語(yǔ)言采用以行序?yàn)橹餍虻姆椒ù鎯?chǔ)。 數(shù)組邏輯上是線性結(jié)構(gòu)的推廣； 數(shù)組是以線性表為元素的線性

12、結(jié) 構(gòu)，而且元素的結(jié)構(gòu)相同； 數(shù)組可以看作是下標(biāo)和值的偶對(duì)的集合； 數(shù)組是一種邏輯結(jié)構(gòu)。 例1 高級(jí)語(yǔ)言中的數(shù)組int a10; a0 a1 a2 a3 a10-1char B45 B00 B01 B02 B03 B05-1B10 B11B15-1B20 B21B25-1二維數(shù)組int a23; 兩個(gè)變量組成的一個(gè)數(shù)組，其中每一個(gè)變量都是數(shù)組。其中a0，a1都是數(shù)組的名字，也就是地址。一個(gè)mn的二維數(shù)組可以看成是m行的一維數(shù)組，或者n列的一維數(shù)組。 a01a00a12a11a10a022.數(shù)組的抽象數(shù)據(jù)類型ADT Array 數(shù)據(jù)對(duì)象：ji=0,bi-1,i=1,2,n, D= aj1j2,j

13、n| n(0)稱為數(shù)組的維數(shù)，bi是數(shù)組第i維 的長(zhǎng)度, ji 是第i維的下標(biāo), aj1j2,jn| ElemSet 數(shù)據(jù)關(guān)系： 1jkbk,1kn且ki,1jibi-1 基本操作： InitArray(&A,n bound1,boundn) DestroyArray(&A) Value(A,index1,indexn) Assign(A,e,index1,indexn) ADT Array 數(shù)組一旦被定義，它的維數(shù)和維界就不再改變，因此除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取元素和修改元素值的操作。3.數(shù)組的順序表示和實(shí)現(xiàn) 數(shù)組一般不做插入和刪除操作 ,因此采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)組是自然的事

14、了，數(shù)組順序存儲(chǔ)時(shí)，必須確定按行序或列序存儲(chǔ)： （1） PASCAL、C 以行序?yàn)橹鞔鎯?chǔ) （2）FORTRAN 以列序?yàn)橹鞔鎯?chǔ)a11 a12 a1n a21 a22 a2n am1 am2 amn a11 a21 am1 a12 a22 am2 a1n a2n amn 以行為主序 以列為主序例如： 稱為基地址或基址。以“行序?yàn)橹餍颉钡拇鎯?chǔ)映象二維數(shù)組A中任一元素ai,j 的存儲(chǔ)位置 LOC(i,j) = LOC(0,0) + (b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L 例2：設(shè)數(shù)組a67的基地址為2000，每個(gè)元素占2個(gè)存

15、儲(chǔ)單元，若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a5,6的存儲(chǔ)地址為 。答：根據(jù)行優(yōu)先公式 LOC(aij)=LOC(a00)+(i*n+j)*k (0im，0jn)得：LOC(a5,6)=2000+(5*7+6)*22082注：只要知道以下三要素便可隨時(shí)求出任一元素的地址（意義：數(shù)組中的任一元素可隨機(jī)存?。╅_(kāi)始結(jié)點(diǎn)的存放地址（即基地址）；維數(shù)和每維的上、下界；每個(gè)數(shù)組元素所占用的單元數(shù)例3 一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是 個(gè)字節(jié)。288答：Volume=m*n*L=(6-1+1)*(7- 0 +1)

16、*6 =48*6=2884.矩陣的壓縮存儲(chǔ)當(dāng)矩陣的階數(shù)較高，而且矩陣中的一些元素有特殊的性質(zhì)時(shí)，可以采用節(jié)省空間的存儲(chǔ)辦法（壓縮存儲(chǔ)） 兩類矩陣： 特殊矩陣：值相同的元素或非零元素分布有一定的規(guī)律； 稀疏矩陣：非零元素少且分布無(wú)規(guī)律；特殊矩陣對(duì)稱矩陣 若n階矩陣A中的元素滿足下述性質(zhì) aij=aji 1i , jn 則稱A為n階對(duì)稱矩陣 a11 a21 a22 a31 an1 ann k= 0 1 2 3 n2個(gè)元素可以壓縮到n(n+1)/2個(gè)空間中；以行序?yàn)橹餍驅(qū)⑵湎氯牵ò▽?duì)角線）中的元素存儲(chǔ)到一個(gè)向量Bn(n+1)/2中: 向量Bk和矩陣中的元素aij之間存在著一一對(duì)應(yīng)關(guān)系： 下面按下

17、標(biāo)從0開(kāi)始討論。 特殊矩陣（對(duì)稱矩陣）向量Bk和矩陣中的元素aij之間的關(guān)系：由i和j推導(dǎo)k：特殊矩陣（三角矩陣 ）三角矩陣 : 下(上)三角矩陣是指矩陣的上（下）三角（不包括對(duì)角線）中的元素均為常數(shù)c或零的n階矩陣 下（上）三角矩陣的存儲(chǔ)公式除了和對(duì)稱矩陣一樣，只存儲(chǔ)其下（上）三角中元之外，再加上一個(gè)存儲(chǔ)常數(shù)c的存儲(chǔ)空間即可。 注意：上（下）三角矩陣的下（上）三角部分，可以全是0，也可以全是常數(shù)c.對(duì)角矩陣 :所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中。即除了主對(duì)角線上和直接在對(duì)角線上、下方若干條對(duì)角線上的元素之外，所有其它的元素均為零。 特殊矩陣（對(duì)角矩陣 ）b條對(duì)角線n行n列(a)

18、a11 a12 a21 a22 a23 an-1,n an,n an,n-1 OO(b)三對(duì)角矩陣a00 a01 a10 a11 a12 an-1,n an,n an,n-1 OO 三對(duì)角矩陣:共3(n+1)-2個(gè)非零元素，存入B3n+1中,元素在一維數(shù)組B中的下標(biāo)k和元素在矩陣中的下標(biāo)i和j的對(duì)應(yīng)關(guān)系為： k = 3i-1 (主對(duì)角線左下角，即i=j+1) k = 3i (主對(duì)角線，即i=j) k = 3i+1(主對(duì)角線右上角，即i=j-1) 由以上三式，得 k=2i+j (0i,jn; 0k3n) 稀疏矩陣非零元素較少，分布無(wú)規(guī)律 假設(shè) m 行 n 列的矩陣含 t 個(gè)非零元素，稀疏因子：

19、= t/(m*n) = 0.05 存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)三元組表（行，列，值）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)十字鏈表 ije 1 2 6 1 6 -2 3 4 -8 4 2 3 4 6 7 5 1 -12 5 3 9 例子：三元組表示稀疏矩陣: 十字鏈表十字鏈表中非零元結(jié)點(diǎn)的結(jié)構(gòu) :row col e down right 0 0 next down right row col next 元素結(jié)點(diǎn)行列表頭總表頭結(jié)點(diǎn)十字鏈表的結(jié)構(gòu)類型typedef struct OLNode int i , j; ElemType e; struct OLNode *down, *right; OLNode;*OLink; ty

20、pedef struct OLink *rhead, *chead ; /行、列鏈表頭指針 int mu, nu , tu ; CrossList;3 0 0 50 -1 0 02 0 0 011314522-1312思考：數(shù)組與線性表的區(qū)別與聯(lián)系相同之處：它們都是若干個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,，an-1構(gòu)成的有限序列。不同之處：(1)數(shù)組要求其元素占用一塊地址連續(xù)的內(nèi)存單元空間，而線性表無(wú)此要求；(2)線性表的元素是邏輯意義上不可再分的元素，而數(shù)組中的每個(gè)元素還可以是一個(gè)數(shù)組；(3)數(shù)組的操作主要是向某個(gè)下標(biāo)的數(shù)組元素中存放數(shù)據(jù)和取某個(gè)下標(biāo)的數(shù)組元素，這與線性表的插入和刪除操

21、作不同。廣義表的定義廣義表是由零個(gè)或多個(gè)原子或子表組成的有限序列，是線性表的推廣 廣義表的概念廣義表般記作： LS(d1，d2，dn) LS是廣義表(d1，d2，dn)的名稱，n是它的長(zhǎng)度。di可以是單個(gè)元素，也可以是廣義表，分別稱為廣義表LS的原子和子表。 用大寫字母表示廣義表的名稱，用小寫字母表示原子 當(dāng)廣義表LS非空時(shí)，稱第一個(gè)元素d1為L(zhǎng)S的表頭(Head)，稱其余元素組成的子表(d2，dn)是LS的表尾(Tail) 非空廣義表可唯一分解成表頭和表尾；反過(guò)來(lái)，由表頭和表尾可唯一組成一個(gè)廣義表 廣義表括號(hào)的層數(shù)定義為廣義表的深度。廣義表舉例A=( ) A是一個(gè)空表，它的長(zhǎng)度為零 B=(e

22、,f) B有兩個(gè)原子e,f，B的長(zhǎng)度為2 C=(a,(b,c) C有一個(gè)原子a和一個(gè)子表(b,c)，C的長(zhǎng)度為2 D=(B,A,C) D有三個(gè)子表B、A、C，D的長(zhǎng)度為3 E=(a,E) E是一個(gè)遞歸的表，E的長(zhǎng)度為2，E相當(dāng)于一個(gè)無(wú)限的表(a,(a,(a,) 廣義表是一個(gè)多層次的線性結(jié)構(gòu)例如：D=(E, F)其中: E=(a, (b, c) F=(d, (e)DEFa( )d( )bce廣義表 LS = ( 1, 2, , n )的結(jié)構(gòu)特點(diǎn):1) 廣義表中的數(shù)據(jù)元素有相對(duì)次序；2) 廣義表的長(zhǎng)度定義為最外層包含元素個(gè)數(shù)；3) 廣義表的深度定義為所含括弧的重?cái)?shù)； 注意：“原子”的深度為 0 “

23、空表”的深度為 1 4) 廣義表可以共享；5) 廣義表可以是一個(gè)遞歸的表。 遞歸表的深度是無(wú)窮值，長(zhǎng)度是有限值。6) 任何一個(gè)非空廣義表 LS = ( 1, 2, , n) 均可分解為 表頭 Head(LS) = 1 和 表尾 Tail(LS) = ( 2, , n) 兩部分。例如: D = ( E, F ) = (a, (b, c)，F(xiàn) )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( )求下列廣義表操作的結(jié)果 GetHead( (a,b,c)