數(shù)據(jù)結(jié)構(gòu)——串和數(shù)組.ppt

3.6 其他線性結(jié)構(gòu),串(String)是由零個或多個字符組成的有限序列。一般記為: S=a1 a2 . an (n0) 其中，S是串的名，用單引號括起來的字符序列是串的值；ai(1in)可以是字母、數(shù)字或其它字符，串中字符的數(shù)目n稱為串的長度。 n=0的串稱為空串(null string)。,3.6.1 串的定義和串的存儲方式概念,串中任意個連續(xù)的字符組成的子序列稱為該串的子串。 包含子串的串相應(yīng)地稱為主串。 通常稱字符在序列中的序號為該字符在串中的位置。 子串在主串中的位置則以子串的第一個字符在主串中的位置來表示。 當(dāng)兩個串的長度相等，并且各個對應(yīng)位置上的字符都相等時，稱兩個串相等。,3.6.1 串的定義和串的存儲方式概念,例：串名為A、B、C、D的四個串如下： A=very good； 長度為9，是D的主串； B= ； 長度為3； C=； 長度為0（空串）； D=good； 長度為4，是A的子串。 D在A中的位置是6。,3.6.1 串的定義和串的存儲方式概念,(1) 賦值操作：StrAssign(S，chars) 初始條件：chars是字符串常量； 操作結(jié)果：生成一個值等于chars的字符串S； (2) 插入操作：StrInsert(S，pos，T) 初始條件：字符串S、T存在， 1pos StrLength(S)+1； 操作結(jié)果：在字符串S的第pos個字符之前插入串T。,3.6.1 串的定義和串的存儲方式基本操作,(3) 刪除操作：StrDelete(S，pos，len) 初始條件：字符串S存在， 1pos StrLength(S)-len+1； 操作結(jié)果：從字符串S中刪除第pos個字符起長度為len的子串。 (4) 復(fù)制操作：StrCopy(S，T) 初始條件：字符串S存在； 操作結(jié)果：將字符串S的內(nèi)容復(fù)制到串T。,3.6.1 串的定義和串的存儲方式基本操作,(5) 判空操作：StrEmpty(S) 初始條件：字符串S存在； 操作結(jié)果：若S為空串，則返回TRUE，否則返回FALSE。 (6) 比較操作：StrCompare(S，T) 初始條件：字符串S、T存在； 操作結(jié)果：若ST，則返回值0；若S=T，則返回值=0；若ST，則返回值0 。,3.6.1 串的定義和串的存儲方式基本操作,(7) 求串長操作：StrLength(S) 初始條件：字符串S存在； 操作結(jié)果：返回字符串S的長度，即串S中字符的個數(shù)。 (8) 置空操作：StrClear(S) 初始條件：字符串S存在； 操作結(jié)果：將字符串S清為空串。,3.6.1 串的定義和串的存儲方式基本操作,(9) 聯(lián)接操作：StrCat(S，T) 初始條件：字符串S、T存在； 操作結(jié)果：將字符串T的值連接在S的后面。 (10) 求子串操作：SubString(Sub，S，pos，len) 初始條件：字符串S存在， 1posStrLength(S) 且1lenStrLength(S)-pos+1； 操作結(jié)果：用Sub返回字符串S的第pos個字符開始長度為len的子串。,3.6.1 串的定義和串的存儲方式基本操作,(11) 定位操作：StrIndex(S，pos，T) 初始條件：字符串S、T存在，T非空， 1posStrLength(S)； 操作結(jié)果：若字符串S中存在與T相等的子串，則返回它在字符串S中第pos個字符之后第一次出現(xiàn)的位置；否則返回0。 (7) 置換操作：StrReplace(S，T，V) 初始條件：字符串S、T、V存在，T非空； 操作結(jié)果：用V替換字符串S中出現(xiàn)的所有與T相等的不重疊的子串。,3.6.1 串的定義和串的存儲方式基本操作,(13) 釋放操作：StrDestroy(S) 初始條件：字符串S存在； 操作結(jié)果：銷毀字符串S。,3.6.1 串的定義和串的存儲方式基本操作,串的兩種基本存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。 定長順序串：當(dāng)串的長度基本固定時，主要考慮采用順序存儲結(jié)構(gòu)實現(xiàn)。其C語言描述如下： #define Maxlen 20 /串的最大長度 typedef struct /串的定義 char chMaxlen; int len; /串的長度 Sstring；,3.6.1 串的定義和串的存儲方式串的存儲結(jié)構(gòu),在進(jìn)行串的插入時： 插入位置pos將原字符串劃分為兩部分(分別假設(shè)為A和B，長度分別為LA和LB)； 待插入字符串假設(shè)為C，其長度為LC； 插入過程可能出現(xiàn)下列三種情況： 1) 插入后串的總長度為LA+LB+LC Maxlen； 2) 插入后串的總長度Maxlen，且pos+LCMaxlen，且pos+LCMaxlen；,3.6.2 定長順序串運(yùn)算插入算法分析,/* 在串s中序號為pos的字符之前插入串t */ int StrInsert(SString *s, int pos, SString t) int i; if(poss-len) return(0); /* 插入位置不合法 */ if(s-len+t.lenlen+t.len-1; i=t.len+pos; i-) s-chi=s-chi-t.len; for(i=0; ichi+pos=t.chi; s-len=s-len+t.len; ,3.6.2 定長順序串運(yùn)算插入算法實現(xiàn),else if(pos+t.lenMaxlen， 但串t的字符序列可以全部插入 */ for(i=Maxlen-1; i=t.len+pos; i-) s-chi=s-chi-t.len; for(i=0; ichi+pos=t.chi; s-len=Maxlen; else /* 串t的部分字符序列要舍棄 */ for(i=0; ichi+pos=t.chi; s-len=Maxlen; return(1); ,3.6.2 定長順序串運(yùn)算插入算法實現(xiàn),int StrDelete(SString *s, int pos, int len) if(pos(s-len-len) return(0); for(i=pos+len; ilen; i+) s-chi-len=s-chi; s-len=s-len-len; return(1); ,3.6.2 定長順序串運(yùn)算刪除算法實現(xiàn),在進(jìn)行串的連接時： 假設(shè)原字符串為A，長度為LA； 待連接串假設(shè)為B，其長度為LB； 連接過程可能出現(xiàn)下列三種情況： 1) 連接后串的總長度為LA+LB Maxlen； 2) 連接后串的總長度Maxlen，且LAMaxlen，LA=Maxlen；,3.6.2 定長順序串運(yùn)算連接算法分析,/* 將串t連接在串s的后面 */ int StrCat(SString *s, SString t) int i, flag; if(s-len+t.lenlen; ilen+t.len; i+) s-chi=t.chi-s-len; s-len=s-len+t.len; flag=1; ,3.6.2 定長順序串運(yùn)算連接算法實現(xiàn),else if(s-lenMaxlen， 但串s的長度len; ichi=t.chi-s-len; s-len=Maxlen; flag=0; else flag=0; /* 串s的長度=Maxlen，串t不被連接 */ return(flag); ,3.6.2 定長順序串運(yùn)算連接算法實現(xiàn),數(shù)組(array)可看成是線性表的推廣，是最常用的數(shù)據(jù)結(jié)構(gòu)之一。 數(shù)組是有限個數(shù)組元素的集合，元素數(shù)目固定； 數(shù)組的每個元素與一組下標(biāo)相對應(yīng)，數(shù)組元素的下標(biāo)關(guān)系具有上下界的約束且下標(biāo)有序； 數(shù)組中所有數(shù)組元素的數(shù)據(jù)類型必須一致； 數(shù)組的兩種基本運(yùn)算： 給定下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素； 給定下標(biāo)，修改相應(yīng)的數(shù)據(jù)元素。,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)和存儲方式定義,一個m行n列的二維數(shù)組(也稱為矩陣)，記作Am, n。,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)和存儲方式定義,A=,a11 a12 . a1n a21 a22 . a2n am1 am2 . amn,按行優(yōu)先順序存儲 對于上述二維數(shù)組A而言，可以將其看成是由m個行向量組成的向量，即： Amn =(a11，.，a1n)，(a21，.，a2n)，.，(am1，.，amn) 這種行向量表相當(dāng)于一個線性表。 行優(yōu)先順序存儲就是數(shù)組元素按行向量表次序進(jìn)行存儲，即第i+1個行表緊跟在第i個行表后面進(jìn)行存儲。,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)和存儲方式存儲結(jié)構(gòu),當(dāng)把n維數(shù)組的元素按行優(yōu)先順序地存放在存儲器里，則每個元素的存儲地址可以用公式計算出來。這個計算公式稱為“地址公式”。 假設(shè)每個數(shù)據(jù)元素占c個存儲單元，則上述二維數(shù)組Amn的地址公式為： Loc(aij)= Loc(a11)+ (i-1)* n +(j-1) * c (1im，1jn),3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)和存儲方式存儲結(jié)構(gòu),按列優(yōu)先順序存儲 對于上述二維數(shù)組A而言，也可以將其看成是由n個列向量組成的向量，即： Amn =(a11，.，am1)，(a12，.，am2)，.，(a1n，.，amn) 這種列向量表也相當(dāng)于一個線性表。 列優(yōu)先順序存儲就是數(shù)組元素按列向量表次序進(jìn)行存儲，即第i+1個列表緊跟在第i個列表后面進(jìn)行存儲。,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)和存儲方式存儲結(jié)構(gòu),當(dāng)把n維數(shù)組的元素按列優(yōu)先順序地存放在存儲器里，并假設(shè)每個數(shù)據(jù)元素占c個存儲單元，則上述二維數(shù)組Amn的地址公式為： Loc(aij)= Loc(a11)+ (j-1)* m +(i-1) * c (1im，1jn),3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)和存儲方式存儲結(jié)構(gòu),根據(jù)二維數(shù)組的特性可以推出：一個三維數(shù)組可以用其數(shù)據(jù)元素為二維數(shù)組的線性表來定義；依次類推，n維數(shù)組是由數(shù)據(jù)元素為n-1維數(shù)組的線性表構(gòu)成。 因此，對n維數(shù)組也有上述兩種不同順序分配的存儲結(jié)構(gòu)。當(dāng)把n維數(shù)組的元素這樣順序地存放在存儲器里，則每個元素的存儲地址都可以用“地址公式”計算出來。,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)和存儲方式存儲結(jié)構(gòu),在C語言中，可以把一個二維數(shù)組看作是一種特殊的一維數(shù)組，該一維數(shù)組的元素又是一個一維數(shù)組。例如定義： int a34； 其中，可以把a(bǔ)看作是一個一維數(shù)組，它有3個元素：a0、a1、a2，每個元素又是一個包含4個元素的一維數(shù)組。,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)和存儲方式示例,通常在實際計算中經(jīng)常出現(xiàn)一些階數(shù)很高的矩陣，且矩陣中有許多值相同的元素或者零元素。 為了節(jié)省存儲空間，可以對這類矩陣進(jìn)行壓縮存儲。 所謂壓縮存儲是指：為多個值相同的元素只分配一個存儲空間；對零元素不分配空間。,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,下三角矩陣的存儲方式： 設(shè)下三角矩陣為Ann，滿足：,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,A=,a11 0 0 a21 a22 0 an1 an2 ann,若將其中的非零元素按行優(yōu)先順序存放為： 則一維數(shù)組Sak和矩陣元素aij之間存在著一一對應(yīng)關(guān)系： (1ji n),3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,k=,+j,假設(shè)每個數(shù)據(jù)元素占用一個字節(jié)的存儲單元，則下三角矩陣的地址公式為：,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,Loc(aij) = Loc(a11)+ i(i1)/ 2 +(j1),三對角矩陣的存儲方式： 設(shè)三對角矩陣為Ann，滿足：,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,A=,a11 a12 0 0 a21 a22 a23 0 0 0 a32 a33 a34 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 0 an,n-1 ann,若將其中的非零元素按行優(yōu)先順序存放，假設(shè)每個數(shù)據(jù)元素占用一個字節(jié)的存儲單元，則三對角矩陣的地址公式為：,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,Loc(aij) = Loc(a11)+2(i1)+(j1) 其中：i=1, j=1, 2 或：i=n, j=n-1, n 或：1in, j=i-1, i, i+1,對稱矩陣的存儲方式： 解決方案類似于下三角矩陣的存儲。,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,稀疏矩陣： 如果一個矩陣中大多數(shù)元素為零，非零元素較少且分布無一定規(guī)律，則稱之為稀疏矩陣。 順序存儲： 三元組表：線性表中的每個結(jié)點(diǎn)由三個字段組成，分別是該非零元素的行下標(biāo)、列下標(biāo)和值。,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,稀疏矩陣的C語言表示： #define smax 16 /* 最大非零元素個數(shù) */ typedef int datatype; typedef struct int i, j; /* 行號，列號 */ datatype v; /* 元素值 */ node;,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,稀疏矩陣的C語言表示： typedef struct int m, n, t; /* 行數(shù)，列數(shù)，非零元素個數(shù) */ node datasmax; /* 三元組表 */ spmatrix; /* 稀疏矩陣類型 */,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,稀疏矩陣舉例：非零元素按行優(yōu)先順序存儲。,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,該稀疏矩陣共有20個元素，僅有6個非零元素。其三元組表如下圖所示。,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,偽地址表示法： 偽地址是指本元素在矩陣中按行優(yōu)先順序的相對位置，上述稀疏矩陣A中非零元素為： 5，8，1，3，-2，6 非零元素的偽地址=n*i+j，n為矩陣的列數(shù)。 因此，5的偽地址為1；1的偽地址為5；。,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,spmatrix TRANSMAT(spmatrix a) /* 返回稀疏矩陣A的轉(zhuǎn)置 */ int ano, bno, col; /* ano和bno分別指示a-data 和b-data中結(jié)點(diǎn)序號； col指示*a的列號，即*b的行號 */ pmatrix *b; /* 存放轉(zhuǎn)置后的矩陣 */ b=malloc(sizeof(spmatrix); b-m=a-n; b-n=a-m; /*行列數(shù)交換*/ b-t=a-t;,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,if (b-t0) /* 有非零元素，則轉(zhuǎn)置 */ bno=0; for(col=0; coln; col+) /*按*a的列序轉(zhuǎn)置*/ for(ano=0; anot; ano+) /* 掃描整個三元組表 */ if (a-dataano.j=col) /* 列號為col則進(jìn)行置換 */ b-databno.i=a-dataano.j; b-databno.j=a-dataano.i; b-databno.v=a-dataano.v;,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,bno+; /* b-data結(jié)點(diǎn)序號加1 */ return b; /* 返回轉(zhuǎn)置結(jié)果指針 */ /* TRANSMAT */,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,該算法的時間主要耗費(fèi)在col和ano的二重循環(huán)上，若A的列數(shù)為n，非零元素個數(shù)為t，則執(zhí)行時間為(nt)，即與的列數(shù)和非零元素個數(shù)的乘積成正比。 而通常用二維數(shù)組表示矩陣時，其轉(zhuǎn)置算法的執(zhí)行時間是(mn)。 由于非零元素個數(shù)一般遠(yuǎn)遠(yuǎn)大于行數(shù)，因此，上述稀疏矩陣轉(zhuǎn)置算法雖然節(jié)省了空間，但增加了轉(zhuǎn)置的時間。,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,鏈?zhǔn)酱鎯Y(jié)構(gòu)： 帶行指針向量的單鏈表表示。 行指針向量 列值 ,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,十字鏈表結(jié)構(gòu)：,3.6.3 二維數(shù)組的結(jié)構(gòu)特點(diǎn)特殊矩陣的存儲方式,設(shè)已知一個nn的上三角矩陣X，其上三角元素已按行序為主序連續(xù)存放在數(shù)組Y中。 請設(shè)計一個tran函數(shù)，將數(shù)組Y中元素按列為主序連續(xù)存放在數(shù)組Z中。,3.6.4 應(yīng)用實例問題描述,A=,1 2 3 4 5 0 6 7 8 9 0 0 10 11 12 0 0 0 13 14 0 0 0 0 15,根據(jù)已知條件： Y=(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) 期望得到的結(jié)果： Z=(1, 2, 6, 3, 7, 10, 4, 8, 11, 13, 5, 9, 12, 14, 15) 解題思路： 用i和j表示矩陣X中元素的行和列下標(biāo)。用k表示數(shù)組Y中元素的下標(biāo)。 初始值設(shè)為：i=1, j=1, k=1； 將yk=xi, j元素存放在zj*(j-1)/2+i中，且當(dāng)一行沒有結(jié)束時j+，否則i+并修改下一行元素的個數(shù)及i和j的值，直到k=n(n+1)/2為止。,3.6.4 應(yīng)用實例算法分析,#include #define N 5 void tran(int y, int n, int z) int k, step=n, count=0, i=0, j=0; for(k=0; kn*(n+1)/2; k+) count+; zj*(j-1)/2+i=yk; if(count=step) step-; count=0; i+; j=i; else j+; ,3.6.4 應(yīng)用實例算法實現(xiàn),main( ) int xNN, yN*(N+1)/2, zN*(N+1)/2; int i, j, k=0, n=N; for(i=0; in; i+) for(j=0; jn; j+) xij=0; printf(“please input non zero data of Matrix:n); for(i=0; in; i+) for(j=i; jn; j+) scanf(“%d”, ,3.6.4 應(yīng)用實例算法實現(xiàn),for(i=0; in; i+) for(j=0; jn; j+) printf(“%4d”,xij); printf(“n”); for(i=0; in; i+) for(j=i; jn; j+) yk=xij; k+; for(i=0; in*(n+1)/2; i+) printf(“%4d”, yi); printf(“n”); tran(y, n, z); for(i=0; in*(n+1)/2; i+) printf(“%4d”, zi); printf(“n”); ,3.6.4 應(yīng)用實例算法實現(xiàn),問題描述 輸入一個稀疏矩陣，要求： 將其轉(zhuǎn)化為三元組的表示形式； 在三元組存儲矩陣中查找值為x的結(jié)點(diǎn)，若x存在，則輸出其位置，否則輸出“不存在”提示信息。,3.6.5 稀疏矩陣壓縮存儲方式和簡單運(yùn)算實例,算法描述 稀疏矩陣用二維數(shù)組A進(jìn)行存儲； 三元組用結(jié)構(gòu)體B表示； 將數(shù)組A中的非零元素及它所在的行、列下標(biāo)按行優(yōu)先順序存在到B中； 在B中查找值為x的結(jié)點(diǎn)，若存在，則輸出其位置；否則輸出“不存在”提示信息。,3.6.5 稀疏矩陣壓縮存儲方式和簡單運(yùn)算實例,C語言源程序 #include #define Max 100 typedef int Elemtype; typedef struct int i, j; Elemtype v; Pnode;,3.6.5 稀疏矩陣壓縮存儲方式和簡單運(yùn)算實例,typedef struct int rows, cols, terms; Pnode dataMax+1; PMatrix; PMatrix B;,3.6.5 稀疏矩陣壓縮存儲方式和簡單運(yùn)算實例,void crt_matrix(int AMax, int m, int n) int i, j, k=1; for(i=1; i=m; i+) for(j=1; j=n; j+) if(Aij!=0) B.datak.i=i; B.datak.j=j; B.