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

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

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

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

4、,n, n0 數(shù)據(jù)關(guān)系：R1 | ai-1, ai D, i=2,.,n 串是有限長的字符序列，由一對單引號相括，如: 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 個字符起 長度為 len 的子串。 基本操作例1： SubString( sub, commander, 4, 3) 求得 sub = man ； SubString( sub, commander, 1, 9)求得 sub = commander； SubString( sub, commander, 9, 1

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

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； “子串在主串中的位置”意指子串中的第一個字符在主串中的位序。 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個字符之前 插入串T。例4：S = chater，T = rac， 則執(zhí)行 StrInsert(S, 4, T)之后得到 S = character 對于串的基本操作集可以有不同的定義方法，在使用高級程序設(shè)計語言中的串類型時，應以該語言的參考手冊為準。 gets(str) 輸入一個串； puts(str) 輸出一個串； strcat(str1, str2) 串聯(lián)接函數(shù)； strcpy(str1, str2, k) 串復制函數(shù)； strcmp(str

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

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

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

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

13、n| n(0)稱為數(shù)組的維數(shù)，bi是數(shù)組第i維 的長度, ji 是第i維的下標, 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ù)組的順序表示和實現(xiàn) 數(shù)組一般不做插入和刪除操作 ,因此采用順序存儲結(jié)構(gòu)表示數(shù)組是自然的事

14、了，數(shù)組順序存儲時，必須確定按行序或列序存儲： （1） PASCAL、C 以行序為主存儲 （2）FORTRAN 以列序為主存儲a11 a12 a1n a21 a22 a2n am1 am2 amn a11 a21 am1 a12 a22 am2 a1n a2n amn 以行為主序 以列為主序例如： 稱為基地址或基址。以“行序為主序”的存儲映象二維數(shù)組A中任一元素ai,j 的存儲位置 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，每個元素占2個存

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

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

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

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

19、= t/(m*n) = 0.05 存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu)三元組表（行，列，值）鏈式存儲結(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é)點的結(jié)構(gòu) :row col e down right 0 0 next down right row col next 元素結(jié)點行列表頭總表頭結(jié)點十字鏈表的結(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)系相同之處：它們都是若干個相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,，an-1構(gòu)成的有限序列。不同之處：(1)數(shù)組要求其元素占用一塊地址連續(xù)的內(nèi)存單元空間，而線性表無此要求；(2)線性表的元素是邏輯意義上不可再分的元素，而數(shù)組中的每個元素還可以是一個數(shù)組；(3)數(shù)組的操作主要是向某個下標的數(shù)組元素中存放數(shù)據(jù)和取某個下標的數(shù)組元素，這與線性表的插入和刪除操

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

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

23、空表”的深度為 1 4) 廣義表可以共享；5) 廣義表可以是一個遞歸的表。 遞歸表的深度是無窮值，長度是有限值。6) 任何一個非空廣義表 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)