數(shù)據(jù)結(jié)構(gòu)3第四章串

第四章 串和數(shù)組4.1串的定義及運(yùn)算4.2

串的存儲(chǔ)結(jié)構(gòu)4.3

串的運(yùn)算的實(shí)現(xiàn)結(jié)束放演4.1

串及其操作4.1.1

基本概念串的定義串(string)是由零個(gè)或多個(gè)字符組成的有限序列，記作s=“a0a1…an-1”，其中s為串的名字，用成對(duì)的雙引號(hào)括起來(lái)的字符序列為串的值，但兩邊的引號(hào)不算串值，不包含在串中。ai(0≤i≤n-1)可以是字母、數(shù)字或其它字符。n為串中字符的個(gè)數(shù)，稱(chēng)為串的長(zhǎng)度?？沾缓魏巫址拇Q(chēng)為空串，它的長(zhǎng)度n=0，記為s=“”。通常用￠表示3．空格串含有一個(gè)或多個(gè)空格的串，稱(chēng)為空格串，它的長(zhǎng)度是空格的個(gè)數(shù)，記為s=“”。子串、主串若一個(gè)串是另一個(gè)串中連續(xù)的一段，則這個(gè)串稱(chēng)為另一個(gè)串的子串，而另一個(gè)串相對(duì)于該串稱(chēng)為主串。例如,串s1=“abcdefg”，s2=“fabcdefghxyz”，則s1為s2的子串，s2相對(duì)于s1為主串。子串的位置子串的第一個(gè)字符在主串中的序號(hào)。例如，a=“guo”d=zhong

guo

guo

a是b的子串，a在b中的位置是7特別地，空串是任意串的子串，任意串是其自身的子串。4.1.2

串的運(yùn)算1.

復(fù)制

strcopy(s,t)將串t的值復(fù)制到s串中例如：strcpy(s3,s1);

//s3=“dirtreeformat”2.

求串長(zhǎng)度

strlen(s)求串中字符的個(gè)數(shù)。例如：printf(“%d”,strlen(s1));

輸出13char

s1[20]=“dirtreeformat”,s2[20]=“file.mem”;char

s3[30],*p;int

result;3

聯(lián)接

strcat(s,t)表示將s串和t串聯(lián)接起來(lái)，使t串接入s串的后面。例如：strcat(s3,”/”)；strcat(s3,s2);

//s3=“dirtreeformat/file.mem”4

串比較（compare)int

strcmp(chars1,char

s2);該函數(shù)比較串s1和串s2的大小，當(dāng)返回值小于0，等于0或大于0時(shí)分別表示s1<s2\s1=s2或s1>s2例如：result=strcmp(“baker”,”Baker”)

result>0result=strcmp(“12”,”12”);

result=0result=strcmp(“Joe”,”Joseph”);

result<0substr(s,start,len)5.

子串表示截取s串中從第start個(gè)字符開(kāi)始連續(xù)len個(gè)字符。求子串位置

index(s,t)求t子串在s主串中首次出現(xiàn)的位置，若t串不是s串的子串，則位置為零。串替換

replace

(s,t,v)將s串中所有的子串t用串v代替。串插入

insert

(s,i,t)在S串的第i個(gè)位置插入t串。串刪除

delete(s,i,j)刪除串S中從第i個(gè)字符開(kāi)始連續(xù)j個(gè)字符。4.2串的存儲(chǔ)結(jié)構(gòu)4.2.1

順序存儲(chǔ)串的順序存儲(chǔ)結(jié)構(gòu)，也稱(chēng)為順序串，與第二章介紹的順序表類(lèi)似。但由于串中元素全部為字符,故存放形式與順序表有所區(qū)別。一．串的非緊縮存儲(chǔ)一個(gè)存儲(chǔ)單元中只存儲(chǔ)一個(gè)字符，和順序表中一個(gè)元素占用一個(gè)存儲(chǔ)單元類(lèi)似。具體形式見(jiàn)圖4-1,設(shè)串S=“How

do

youdo”。二．串的緊縮存儲(chǔ)根據(jù)各機(jī)器字的長(zhǎng)度，盡可能將多個(gè)字符存放在一個(gè)字中。假設(shè)一個(gè)字可存儲(chǔ)4個(gè)字符，則緊縮存儲(chǔ)具體形式見(jiàn)圖4-2。Howdoyoudo圖4-1S

串的非緊縮存儲(chǔ)Howdoyoudo圖4-2S

串的緊縮存儲(chǔ)三．順序串的數(shù)據(jù)類(lèi)型描述在C語(yǔ)言中只有緊縮格式?jīng)]有非緊縮格式。其形式定義為：maxlen 200

/*串允許的最大字符個(gè)數(shù)*/struct#definetypedef{charintstring

[maxlen]；len；/*串的長(zhǎng)度*/}orderstring如圖4.1所示的串s=“abcdef”。abcdef\0下標(biāo)：

0

1

2

3

4

5圖4.1 串的順序表示算法4.1

實(shí)現(xiàn)兩個(gè)串的聯(lián)接orderstring Concat（orderstring

s1，orderstring

s2）/*將串s1和s2聯(lián)接成新串，放到s中由s返回*/{orderstring

s；if（（s1.len+s2.len）>＝maxlen）printf（”聯(lián)接后的串太長(zhǎng)”）；else{for

（i=0；i<s1.len；i++）s.string[i]=s1.string

[i]；for（i=0；i<s2.len；i++）{s.string[s1.len+i]=s2.string[i]；s.len=s1.len+s2.len；s.string[s.len]=‘\0’；}return

（s）；}算法4.2

求一個(gè)串的子串orderstring Substring（orderstring

s，int

i，intlen）/*從串s中把第i個(gè)字符開(kāi)始的連續(xù)len個(gè)字符組成的子串賦給

sub

*/{

orderstring

sub；{if（（i+len-1）>s.len

）printf（“超界！”）else{

for（k=0；k<len；k++）sub.string[k]=s.string[i+k-1]；sub.len=len；sub.string[len]=‘\0’}return（sub）}注意：在串的靜態(tài)存儲(chǔ)結(jié)構(gòu)中必須預(yù)先定義允許存放的最大字符個(gè)數(shù)，這容易造成系統(tǒng)空間浪費(fèi)或運(yùn)行錯(cuò)誤。在C語(yǔ)言中有這樣一個(gè)規(guī)定，程序員使用串的長(zhǎng)度一旦超過(guò)允許存放串的最大字符數(shù)，系統(tǒng)將自動(dòng)減去超出字符。4.2.2堆分配存儲(chǔ)表示這種存儲(chǔ)表示的特點(diǎn)是，仍以一組地址連續(xù)的存儲(chǔ)單元存放串值字符序列，但它們的存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得。所以也稱(chēng)為動(dòng)態(tài)存儲(chǔ)分配的順序表。在C語(yǔ)言中，利用動(dòng)態(tài)存儲(chǔ)管理函數(shù)，來(lái)根據(jù)實(shí)際需要?jiǎng)討B(tài)分配和釋放字符數(shù)組空間。這樣定義的順序串類(lèi)型也有兩種形式堆式存儲(chǔ)結(jié)構(gòu)的形式定義為：typedef

struct{char

*str；int

len；}heapstring；下面給出字符串在堆式存儲(chǔ)時(shí)，串的基本操作的實(shí)現(xiàn)方法。算法4.3heapstring實(shí)現(xiàn)兩個(gè)串的聯(lián)接*Concat（heapsting

*s1，heapstring*s2）/*將串s1和s2聯(lián)接成新串，放到s中由s返回*/{ heapstring

*s；n=s1->len+s2->len；if（！（s->str=（char*）malloc（n*sizeof

（char））））printf

（“可分配空間不足！”）；else{ strcpy（s->str，s1->str）；

/* C語(yǔ)言中的串拷貝命令*/C語(yǔ)言中的串聯(lián)接命令*/strcat（s->str，s2->str）；

/*s->len=n；free（s1->str）；free（s2->str）；return

（s）}}4.2.2

鏈?zhǔn)酱鎯?chǔ)順序串上的插入和刪除操作不方便，需要移動(dòng)大量的字符。因此，我們可用單鏈表方式來(lái)存儲(chǔ)串值，串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱(chēng)為鏈串。一．結(jié)點(diǎn)大小為1的鏈?zhǔn)酱鎯?chǔ)和前面介紹到的單鏈表一樣，每個(gè)結(jié)點(diǎn)為一個(gè)字符，鏈表也可以帶頭結(jié)點(diǎn)。S=‘a(chǎn)bcdef’的存儲(chǔ)結(jié)構(gòu)具體形式見(jiàn)圖4-3。aSbcdef

^圖4-3S

串的鏈?zhǔn)酱鎯?chǔ)示意圖typedef

struct

node{char

data;struct

node

*next;}lstring;一個(gè)鏈串由頭指針唯一確定。這種結(jié)構(gòu)便于進(jìn)行插入和刪除運(yùn)算，但存儲(chǔ)空間利用率太低。二．結(jié)點(diǎn)大小為K的鏈?zhǔn)酱鎯?chǔ)為了提高存儲(chǔ)密度，可使每個(gè)結(jié)點(diǎn)存放多個(gè)字符。通常將結(jié)點(diǎn)數(shù)據(jù)域存放的字符個(gè)數(shù)定義為結(jié)點(diǎn)的大小，顯然，當(dāng)結(jié)點(diǎn)大小大于1時(shí)，串的長(zhǎng)度不一定正好是結(jié)點(diǎn)的整數(shù)倍，因此要用特殊字符來(lái)填充最后一個(gè)結(jié)點(diǎn)，以表示串的終結(jié)。對(duì)于結(jié)點(diǎn)大小不為1的鏈串，其類(lèi)型定為義只需對(duì)上述的結(jié)點(diǎn)類(lèi)型做簡(jiǎn)單的修改即可。a

b

c

d

e

f

\0

\0

^S頭結(jié)點(diǎn)圖

4-4 S

串的結(jié)點(diǎn)大小為

4

的鏈?zhǔn)酱鎯?chǔ)串的塊鏈?zhǔn)酱鎯?chǔ)形式定義如下：blocksize

10/*用戶自定義塊的大小*/struct

Blocknode#definetypedef{

charstructch[blocksize]；Blocknode

*next；}Blocknode；typedef

struct{

Blocknode

*head；/*串的頭指針*//*串的當(dāng)前長(zhǎng)度*/int

curlen；}Blstring；下面給出字符串在鏈?zhǔn)酱鎯?chǔ)時(shí)，串的基本操作的實(shí)現(xiàn)方法。算法4.4

實(shí)現(xiàn)兩個(gè)串的聯(lián)接。Blstring *concat

（Blstring*s1，Blstring*s2）{Blstring

*p，*q；p=s1->head

；while（!p->next）p=p->next；q=s2->head；p->next=q；free（s2->head）；free（s2->tail）；return（s1）；}四、子串定位順序串上的子串定位運(yùn)算index(S，T)子串的定位運(yùn)算通常稱(chēng)為串的模式匹配，是串處理中最重要的運(yùn)算之一。設(shè)串s=‘a(chǎn)1a2…an’，串T=‘b1b2…bm’(m≤n)，子串定位是要在主串S中找出一個(gè)與子串T相同的子串。通常把主串S稱(chēng)為目標(biāo)，把子串T稱(chēng)為模式，把從目標(biāo)S中查找模式為T(mén)的子串的過(guò)程稱(chēng)為“模式匹配”。匹配有兩種結(jié)果出現(xiàn)：若S中有模式為T(mén)的子串，就返回該子串在S中的位置，當(dāng)S中有多個(gè)模式為T(mén)的子串，通常只要找出第一個(gè)子串即可，這種情況稱(chēng)為匹配成功，若S中無(wú)模式為T(mén)的子串，返回值為零，稱(chēng)為匹配失敗。模式匹配過(guò)程如圖4-10所示，假設(shè)S=“abababac”，T=“abac”。a

b

a

b

a

b

a

ca

b

a

c(

a

)

第

一

趟a

b

a

b

a

b

a

ca

b

a

b

a

b

a

ca

b

a

c(

b

)

第

二

趟

匹

配a

b

a

b

a

b

a

c匹

配

s

4

?

t

4s

2

?

t1a

b

a

c(c)

第a

b

a

c(

d

)

第

四

趟

匹

配

s

4

?

t1三

趟

匹

配

s

6

?

t

4a

b

a

b

a

b

a

ca

b

a

c(

e

)

第

五

趟

匹

配

成

功圖

4

-

1

0

模

式

匹

配

過(guò)

程int Index（orderstring

s，orderstring

t，int

p）/*在主串s中尋找在第p個(gè)字符后模式串t第一次出現(xiàn)的位置*/{

int

i=p

，j=0；while

（（i<s.len）&&（j<t.len））{if

（s.string[i]=t.string[j]{

i++；j++；}else{i=i-j+1；j=0；}if

（j=

=t.len）return（i-t.len）；return（-1）；}}4.4

數(shù)組的定義及基本操作一、數(shù)組的定義數(shù)組是一種“同構(gòu)”的數(shù)據(jù)元素的集合，它的每個(gè)數(shù)據(jù)元素類(lèi)型相同，結(jié)構(gòu)一致。而且存儲(chǔ)在一塊地址連續(xù)的存儲(chǔ)單元中。它是線性表在維數(shù)上的擴(kuò)張，也就是線性表中的元素又是一個(gè)線性表。例如，二維數(shù)組：可看成一個(gè)線性表A=（a0，a1，……，ap）（p=m-1或n-1）a00

a01

…a10

a11

……

…

…am-1,0

am-1,1

…a0,n-1a1,n-1…am-1,n-1Amn=4.4

數(shù)組的定義及基本操作二、數(shù)組的基本操作數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷(xiāo)毀之外，數(shù)組只有存取元素和修改元素值的操作，通常數(shù)組的運(yùn)算不包括插入和刪除這樣的操作。4.5

數(shù)組的順序存儲(chǔ)結(jié)構(gòu)由于計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來(lái)表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個(gè)線性序列存放在存儲(chǔ)器中。通常有兩種順序存儲(chǔ)方式：⑴行優(yōu)先順序——將數(shù)組元素按行排列，第i+1個(gè)行向量緊接在第i個(gè)行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲(chǔ)的線性序列為：a00,a01,…,a0,n-1,a10,a11,…a1,n-1,……,am-1,0,

…,am-1,n-1在PASCAL、C語(yǔ)言中，數(shù)組就是按行優(yōu)先順序存儲(chǔ)的。⑵列優(yōu)先順序——將數(shù)組元素按列向量排列，第j+1個(gè)列向量緊接在第j個(gè)列向量之后，A的m*n個(gè)元素按列優(yōu)先順序存儲(chǔ)的線性序列為：a00,a10,…,am-1,0,a01,a11,…am-1,1,……,am-1,1,

…,an-1,m-1在FORTRAN語(yǔ)言中，數(shù)組就是按列優(yōu)先順序存儲(chǔ)的。在以行序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)中，設(shè)每個(gè)數(shù)組元素占L個(gè)單元，元素a的地址用

loc（a）表示。設(shè)數(shù)組元素的起始地址為base：二維數(shù)組的地址計(jì)算公式：loc（aij）=base+（i×n+j）×L4.6

矩陣的壓縮存儲(chǔ)在科學(xué)與工程計(jì)算問(wèn)題中，矩陣是一種常用的數(shù)學(xué)對(duì)象，在高級(jí)語(yǔ)言編制程序時(shí)，簡(jiǎn)單而又自然的方法，就是將一個(gè)矩陣描述為一個(gè)二維數(shù)組。矩陣在這種存儲(chǔ)表示之下，可以對(duì)其元素進(jìn)行隨機(jī)存取，各種矩陣運(yùn)算也非常簡(jiǎn)單，并且存儲(chǔ)的密度為1。但是在矩陣中非零元素呈某種

規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，看起來(lái)存儲(chǔ)密度仍為1，但實(shí)際上占用了許多單元去存儲(chǔ)重復(fù)的非零元素或零元素，這對(duì)高階矩陣會(huì)造成極大的浪費(fèi)，為了節(jié)省存儲(chǔ)空間，我們可以對(duì)這類(lèi)矩陣進(jìn)行壓縮存儲(chǔ)：即為多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。4.6

矩陣的壓縮存儲(chǔ)一、特殊矩陣的壓縮存儲(chǔ)1、對(duì)稱(chēng)矩陣若n階矩陣A中的數(shù)據(jù)元素滿足下述性質(zhì)aij=aji

（0≤i，j≤n-1）則稱(chēng)A為n階對(duì)稱(chēng)稱(chēng)矩陣；因aij與aji相等，二者只需分配一個(gè)存儲(chǔ)單元。這樣，可將n*n個(gè)存儲(chǔ)單元壓縮到n（n+1）/2個(gè)單元。a0,n-1a1,n-1…an-1,0a00

a01a10

a11…

…an-1,1…………an-1,n-1Amn=說(shuō)明：按行序?yàn)橹餍颍篴00a10a11a20a21…...an-1,0…...an-1,n-1n(n+1)/2-1

k=0

1

2

3

4

i(i

+1)/2

+j，i

?

jk

=

j(j

+1)/2

+i,i

<

j若i≧j，則ai

j在下三角形中。ai

j之前的i行（從第0行到第i-1行）一共有1+2+…+i=i(i+1)/2個(gè)元素，在第i行上，ai

j之前恰有j個(gè)元素，因此有：k=i*(i+1)/2+j若i<j，則aij是在上三角矩陣中。因?yàn)閍ij=aji，所以只要交換上述對(duì)應(yīng)關(guān)系式中的i和j即可得到：k=j*(j+1)/2+i4.6

矩陣的壓縮存儲(chǔ)一、特殊矩陣的壓縮存儲(chǔ)2、對(duì)角矩陣如果矩陣中的所有的非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域則稱(chēng)為對(duì)角矩陣，即除了主對(duì)角線和主對(duì)角線相鄰兩側(cè)的若干條對(duì)角線上的元素之外，其余元素皆為零。如常見(jiàn)的三對(duì)角矩陣。a00

a01

0a10

a11

a120

…

an-2,n-3

an-2,n-200

0

…an-2,n-1an-1,n-1…an-1,n-20a21

a22

a230

……………………

.

00

……………

00……………說(shuō)明：a00a01a10a11a12…...…...an-1,n-13(n-1)按行序?yàn)橹餍颍悍橇阍貎H出現(xiàn)在主對(duì)角(aii,0≦i≦n-1）上，以及緊鄰主對(duì)角線上面的那條對(duì)角線上(ai,i+1,0≦i≦n-2)和緊鄰主對(duì)角線下面的那條對(duì)角線上

(ai+1,

i,0≦i≦n-2)。顯然，當(dāng)∣i-j∣>1時(shí)，元素aij=0。k=0

1

2

3

43i-1

當(dāng)i=j+1時(shí)k=

3i

當(dāng)i=j時(shí)3i+1

當(dāng)i=j-1時(shí)4.6

矩陣的壓縮存儲(chǔ)素的三元，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)(即s的存儲(chǔ)方法；省存儲(chǔ)單元，很自然地想到使用壓般是沒(méi)有規(guī)律的，因此在存儲(chǔ)非零行和列的位置（i,j）。一個(gè)三元組(因此，稀疏矩陣可由表示非零元二、稀疏矩陣的壓縮存儲(chǔ)設(shè)矩陣Amn中有s個(gè)非零元素，則稱(chēng)A為稀疏矩陣。下面討論它（1）三元組表示法在存儲(chǔ)稀疏矩陣時(shí)，為了節(jié)方法。但由于非零元素的分布一同時(shí)，還必須同時(shí)記下它所在的一確定了矩陣A的一個(gè)非零元素。組及其行列數(shù)唯一確定。

i,j,aij)唯

0

0

元素的

2

00

縮存儲(chǔ)

00

0

<<m×n)

0

00

800400000000500070000000609000

0

M

=

M由{(0,1,8),

(0,4,4),

(2,3,5),

(3,2,7),(4,0,2), (4,5,6),

(5,2,9))

}

和矩陣維數(shù)（6,7）唯一確定

0

0

2

00

00

0

0

00

800400000000500070000000609000

0

M

=

018044235327402456529i

jv0123456三元組表三元組表示法描述三元組表表示描述較為簡(jiǎn)單，但這類(lèi)順序存儲(chǔ)方式對(duì)于非零元的位置或個(gè)數(shù)經(jīng)常發(fā)生變化的矩陣運(yùn)算就顯得不太適合。比如在執(zhí)行將矩陣B相加到矩陣A上的運(yùn)算時(shí)，某位置上的結(jié)果可能會(huì)由非零元變?yōu)榱阍?，但也可能由零元變?yōu)榉橇阍?，這就會(huì)引起在A的三元組表中進(jìn)行刪除和插人操作，從而導(dǎo)致大量結(jié)點(diǎn)的移動(dòng)。三元組表存儲(chǔ)的定義：#

define

maxsize256/*

最大非零元素個(gè)數(shù)*/typedef

struct/*

三元組類(lèi)型*/{

int

i，j；/*

該非零元素的行下標(biāo)和列下標(biāo)*/datatype

v；}

triple；typedef

struct{

triple

data[maxsize+1]；int

mu，nu，tu；}

Tsmatrix；/*

三元組表類(lèi)型*//*

三元組表存儲(chǔ)空間*//*

矩陣的行數(shù)，列數(shù)和非零元素個(gè)數(shù)*/一個(gè)m×n的矩陣A，它的轉(zhuǎn)置B是一個(gè)n×m的矩陣，那么a[i][j]=b[j][i]，0≦i≦m-1，0≦j≦n-1，即A的行是B的列，A的列是B的行。將A轉(zhuǎn)置為B，就是將A的三元組表a.data置換為表B的三元組表b.data，假設(shè)A是按行優(yōu)先順序存儲(chǔ)，如果只是簡(jiǎn)單地交換a.data中i和j的內(nèi)容，那么得到的b.data將是一個(gè)按列優(yōu)先順序存儲(chǔ)的稀疏矩陣B，要得到按行優(yōu)先順序存儲(chǔ)的b.data，就必須重新排列三元組的順序。由于A的列是B的行，因此，按a.data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b.data必定是按行優(yōu)先存放的。方法一：按列序轉(zhuǎn)置由于A的列是B的行，因此，按a.data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b.data必定是按行優(yōu)先存放的。按這種方法設(shè)計(jì)的算法，其基本思想是：對(duì)A中的每一列col(0≤col≤a->n-1)，通過(guò)從頭至尾掃描三元組表A，找出所有列號(hào)等于col的那些三元組，將它們的行號(hào)和列號(hào)互換后依次放人B中，即可得到B的按行優(yōu)先的壓縮存貯表示。矩陣的轉(zhuǎn)置：矩陣的轉(zhuǎn)置：方法二：快速轉(zhuǎn)置即按ma中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果放入mb中恰當(dāng)位置，此法關(guān)鍵是要預(yù)先確定M中每一列第一個(gè)非零元在mb中位置，為確定這些位置，轉(zhuǎn)置前應(yīng)先求得M的每一列中非零元個(gè)數(shù)。實(shí)現(xiàn)：設(shè)兩個(gè)數(shù)組num[col]：表示矩陣M中第col列中非零元個(gè)數(shù)

pos[col]：指示M中第col列第一個(gè)非零元在mb中位置顯然有：pos[0]=1;pos[col]=pos[col-1]+num[col-1]; (1￡col

￡a.nu-1)8

0

0

4

0

0

0

0

0

0

0

0

col0123456num[col]1121110cpot[col]1235678作業(yè)：P81第一、二題直接填在課本中

P81第三題3，4寫(xiě)在作業(yè)本上通常有兩種順序存儲(chǔ)方式：⑴行優(yōu)先順序——將數(shù)組元素按行排列，第i+1個(gè)行向量緊接在第i個(gè)行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲(chǔ)的線性序列為：

a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn在PASCAL、C語(yǔ)言中，數(shù)組就是按行優(yōu)先順序存儲(chǔ)的。⑵列優(yōu)先順序——將數(shù)組元素按列向量排列，第j+1個(gè)列向量緊接在第j個(gè)列向量之后，A的m*n個(gè)元素按列優(yōu)先順序存儲(chǔ)的線性序列為：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm在FORTRAN語(yǔ)言中，數(shù)組就是按列優(yōu)先順序存儲(chǔ)的。以上規(guī)則可以推廣到多維數(shù)組的情況：優(yōu)先順序可規(guī)定為先排最右的下標(biāo)，從右到左，最后排最左下標(biāo)：列優(yōu)先順序與此相反，

先排最左下標(biāo)，從左向右，最后排最右下

標(biāo)。按上述兩種方式順序存儲(chǔ)的序組，只要知道開(kāi)始結(jié)點(diǎn)的存放地址（即基地址），維數(shù)和每維的上、下界，以及每個(gè)數(shù)組元

素所占用的單元數(shù)，就可以將數(shù)組元素的

存放地址表示為其下標(biāo)的線性函數(shù)。因此，數(shù)組中的任一元素可以在相同的時(shí)間內(nèi)存

取，即順序存儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)

構(gòu)。例如，二維數(shù)組Amn按“行優(yōu)先順序”存儲(chǔ)在內(nèi)存中，假設(shè)每個(gè)元素占用d個(gè)存儲(chǔ)單元。元素aij的存儲(chǔ)地址應(yīng)是數(shù)組的基地址加上排在aij前面的元素所占用的單元數(shù)。因?yàn)閍ij位于第i行、第j列，前面i-1行一共有(i-1)×n個(gè)元素，第i行上aij前面又有j-1個(gè)元素，故它前面一共有(i-1)×n+j-1個(gè)元素，因此，aij的地址計(jì)算函數(shù)為：LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d同樣，三維數(shù)組Aijk按“行優(yōu)先順序”存儲(chǔ)，其地址計(jì)算函數(shù)為：LOC(aijk)=LOC(a111)+[(i-1)*n*p+(

j-1)*p+(k-1)]*d上述討論均是假設(shè)數(shù)組各維的下界是不是1，更一般的二維數(shù)組是A[c1..d1,c2..d2]，這里

c1,c2不一定是1。aij前一共有i-c1行，二維數(shù)組一共有d2-c2+1列，故這i-c1行共有(i-c1)*(d2-c2+1)個(gè)元素，第i行上aij前一共有j-c2個(gè)元素，因此，aij的地址計(jì)算函數(shù)為：LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*d例如，在C語(yǔ)言中，數(shù)組各維下標(biāo)的下界是0，因此在C語(yǔ)言中，二維數(shù)組的地址計(jì)算公式為：LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d5.3矩陣的壓縮存儲(chǔ)在科學(xué)與工程計(jì)算問(wèn)題中，矩陣是一種常用的數(shù)學(xué)對(duì)象，在高級(jí)語(yǔ)言編制程序時(shí)，簡(jiǎn)單而又自然的方法，就是將一個(gè)矩陣描述為一個(gè)二維數(shù)組。矩陣在這種存儲(chǔ)表示之下，可以對(duì)其元素進(jìn)行隨機(jī)存取，各種矩陣運(yùn)算也非常簡(jiǎn)單，并且存儲(chǔ)的密度為1。但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，看起來(lái)存儲(chǔ)密度仍為1，但實(shí)際上占用了許多單元去存儲(chǔ)重復(fù)的非零元素或零元素，這對(duì)高階矩陣會(huì)造成極大的浪費(fèi)，為了節(jié)省存儲(chǔ)空間，我們可以對(duì)這類(lèi)矩陣進(jìn)行壓縮存儲(chǔ)：即為多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。5.3.1特殊矩陣所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣，下面我們討論幾種特殊矩陣的壓縮存儲(chǔ)。1、對(duì)稱(chēng)矩陣在一個(gè)n階方陣A中，若元素滿足下述性質(zhì)：aij=aji0≦i,j≦n-1則稱(chēng)A為對(duì)稱(chēng)矩陣。如圖5.1便是一個(gè)5階對(duì)稱(chēng)矩陣。對(duì)稱(chēng)矩陣中的元素關(guān)于主對(duì)角線對(duì)稱(chēng)，故只要存儲(chǔ)矩陣中上三角或下三角中的元素，讓每?jī)蓚€(gè)對(duì)稱(chēng)的元素共享一個(gè)存儲(chǔ)空間，這樣，能節(jié)約近一半的存儲(chǔ)空間。不失一般性，我們按“行優(yōu)先順序”存儲(chǔ)主對(duì)角線（包括對(duì)角線）以下的元素，其存儲(chǔ)形式如圖所示：1513750800189263025170613a00a10

a

11a20

a21

a23………………..an-1

0

a

n-11

a

n-12

…a

n-1n-1圖5.1對(duì)稱(chēng)矩陣在這個(gè)下三角矩陣中，第i行恰有i+1個(gè)元素，元素總數(shù)為：(i+1)=n(n+1)/2因此，我們可以按圖中箭頭所指的次序?qū)⑦@些元素存放在一個(gè)向量sa[0..n(n+1)/2-1]中。為了便于訪問(wèn)對(duì)稱(chēng)矩陣A中的元素，我們必須在aij和sa[k]之間找一個(gè)對(duì)應(yīng)關(guān)系。若i≧j，則aij在下三角形中。aij之前的i行（從第0行到第i-1行）一共有1+2+…+i=i(i+1)/2個(gè)元素，在第i行上，aij之前恰有j個(gè)元素（即ai0,ai1,ai2,…,aij-1），因此有：k=i*(i+1)/2+j

0≦k<n(n+1)/2若i<j，則aij是在上三角矩陣中。因?yàn)閍ij=aji，所以只要交換上述對(duì)應(yīng)關(guān)系式中的i和j即可得到：k=j*(j+1)/2+i 0≦

k<n(n+1)/2令I(lǐng)=max(i,j)，J=min(i,j)，則k和i,j的對(duì)應(yīng)關(guān)系可統(tǒng)一為：k=I*(I+1)/2+J 0≦

k<n(n+1)/2因此，aij的地址可用下列式計(jì)算：LOC(aij)=LOC(sa[k])=LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d有了上述的下標(biāo)交換關(guān)系，對(duì)于任意給定一組下標(biāo)(i，j)，均可在sa[k]中找到矩陣元素aij，反之，對(duì)所有的k=0,1,2,…n(n-1)/2-1，都能確定sa[k]中的元素在矩陣中的位置(i,j)。由此，稱(chēng)sa[n(n+1)/2]為階對(duì)稱(chēng)矩陣A的壓縮存儲(chǔ)，見(jiàn)下圖：例如a21和a12均存儲(chǔ)在sa[4]中，這是因?yàn)?/p>

k=I*(I+1)/2+J=2*(2+1)/2+1=4a00k=0a101a112a203……an-1

0n(n-1)/2……an-1,n-1n(n-1)/2-12、三角矩陣以主對(duì)角線劃分，三角矩陣有上三角和下三角兩種上三角矩陣如圖所示，它的下三角（不包括主對(duì)角線）中的元素均為常數(shù)。下三角矩陣正好相反，它的主對(duì)

角線上方均為常數(shù)，如圖所示。在大多數(shù)情況下，三角矩陣常數(shù)為零。a00

a01

… a

0

n-1c

a11

… a

1

n-1a00a10c

…

ca11

…

c…..……………..an-1

0

an-11

… an-1

n-1c

c…

a

n-1

n-1(a)上三角矩陣圖5.2三角矩陣(b)下三角矩陣三角矩陣中的重復(fù)元素c可共享一個(gè)存儲(chǔ)空間，其余的元素正好有n(n+1)/2個(gè)，因此，三角矩陣可壓縮存儲(chǔ)到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一個(gè)分量中，上三角矩陣中，主對(duì)角線之上的第p行(0≦p<n)恰有n-p個(gè)元素，按行優(yōu)先順序存放上三角矩陣中的元素aij時(shí)，aij之前的i行一共有(n-p)=i(2n-i+1)/2個(gè)元素，在第i行上，aij前恰好有j-i個(gè)元素：

aij,aij+1,…aij-1。因此，sa[k]和aij的對(duì)應(yīng)關(guān)系是：i(2n-i+1)/2+j-i 當(dāng)i≦jn(n+1)/2 當(dāng)i>jk=下三角矩陣的存儲(chǔ)和對(duì)稱(chēng)矩陣類(lèi)似，sa[k]和aij對(duì)應(yīng)關(guān)系是：i(i+1)/2+j

i≧jk=n(n+1)/2

i>j3、對(duì)角矩陣對(duì)角矩陣中，所有的非零元素集中在以主對(duì)角線為了中心的帶狀區(qū)域中，即除了主對(duì)角線和主對(duì)角線相鄰兩側(cè)的若干條對(duì)角線上的元素之外，其余元素皆為零。下圖給出了一個(gè)三對(duì)角矩陣，a00

a01a10

a11

a12a21

a22

a23….…..….

圖5.3

對(duì)角矩陣an-2

n-3

an-2

n-2

an-2

n-1an-1

n-2

an-1

n-1非零元素僅出現(xiàn)在主對(duì)角(aii,0≦i≦n-1上，緊鄰主對(duì)角線上面的那條對(duì)角線上

(aii+1,0≦i≦n-2)和緊鄰主對(duì)角線下面的那條對(duì)角線上(ai+1

i,0≦i≦n-2)。顯然，當(dāng)∣i-j∣>1時(shí)，元素aij=0。由此可知，一個(gè)k對(duì)角矩陣(k為奇數(shù))A是滿足下述條件的矩陣：若∣i-j∣>(k-1)/2，則元素aij=0。對(duì)角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲(chǔ)到一個(gè)向量中，并且也能找到每個(gè)非零元素和向量下標(biāo)的對(duì)應(yīng)關(guān)系。在三對(duì)角矩陣?yán)锔綕M足條件i=0，j=0、1，或

i=n-1j=n-2、n-1或1<i<n-1,j=i-1、i、i+1的元素aij外，其余元素都是零。對(duì)這種矩陣，我們也可按行優(yōu)序?yàn)橹餍騺?lái)存儲(chǔ)。除第0行和第n-1行是2個(gè)元素外，每行的非零元

素都要是3個(gè)，因此，需存儲(chǔ)的元素個(gè)數(shù)為3n-2。a00a01a10a11a12a21……a

n-1n-2a

n-1n-1K=0

1

2

3

4

5

…

… 3n-2 3n-1數(shù)組sa中的元素sa[k]與三對(duì)角帶狀矩陣中的元素aij存在一一對(duì)應(yīng)關(guān)系，在aij之前有i行,共有3*i-1個(gè)非零元素，在第i行，有j-i+1個(gè)非零元素，這樣，非零元素aij的地址為：LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d=LOC(0,0)+(2i+j)*d上例中，a34對(duì)應(yīng)著sa[10]。k=2*i+j=2*3+4=10a21對(duì)應(yīng)著sa[5]k=2*2+1=5由此，我們稱(chēng)sa[0..3*n-2]是階三對(duì)角帶狀矩陣A的壓縮存儲(chǔ)表示。上述的各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲(chǔ)到一個(gè)向量中，并且一般都能找到矩陣中的元素與該向量的對(duì)應(yīng)關(guān)系，通過(guò)這個(gè)關(guān)系，仍能對(duì)矩陣的元素進(jìn)行隨機(jī)存取。5.3.2稀疏矩陣什么是稀疏矩陣？簡(jiǎn)單說(shuō)，設(shè)矩陣A中有

s個(gè)非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的

總數(shù)（即s≦m×n），則稱(chēng)A為稀疏矩陣。精確點(diǎn)，設(shè)在的矩陣A中，有s個(gè)非零元素。令e=s/(m*n)，稱(chēng)e為矩陣的稀疏因子。通常認(rèn)為e≦0.05時(shí)稱(chēng)之為稀疏矩陣。在

存儲(chǔ)稀疏矩陣時(shí)，為了節(jié)省存儲(chǔ)單元，很自然地想到使用壓縮存儲(chǔ)方法。但由于非零元素的分布一般是沒(méi)有規(guī)律的，因此在存儲(chǔ)非零元素的同時(shí)，還必須同時(shí)記下它所在的行和列的位置（i,j)。反之，一個(gè)三元組(i,j,aij)唯一確定了矩陣A的一個(gè)非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。例如，下列三元組表((1,2,12)(1,3,9),(3,1,-

3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))加上(6,7)這一對(duì)行、列值便可作為下列矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲(chǔ)方法。0 12

9 0

0

0

00

0

0 0

0

0

00 0

-30 0

1512

0

0

0 18

09 0

0 24

0

00

0 24

0

0

0

00 18

0 0

0

0

015

0 0

–7

0

0

00 0

14

0

0

00 0

0

0

0

00 0

0

0

0

0圖5.4稀疏矩陣M和TM=-3

0

0 0

0

14

00 0

0T0=0

–7一、三元組順序表假設(shè)以順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組表，則可得到稀疏矩陣的一種壓縮存儲(chǔ)方法——三元順序表。#define

maxsize

10000typedef

int

datatype;typedef

struct{int

i,j;datatype

v;}triple;typedef

struct{triple

data[maxsize];int

m,n,t;}tripletable;設(shè)A為tripletable型的結(jié)構(gòu)變量，圖5.4中所示的稀疏矩陣的三元組的表示如下：i

jv121213931-3361443245218611564-7下面以矩陣的轉(zhuǎn)置為例，說(shuō)明在這種壓縮存儲(chǔ)結(jié)構(gòu)上如何實(shí)現(xiàn)矩陣的運(yùn)算。一個(gè)m×n的矩陣A，它的轉(zhuǎn)置B是一個(gè)n×m的矩陣，且a[i][

j]=b[

j][i]，0≦i≦m，0≦j≦n，即A的行是B的列，A的列是B的行。將A轉(zhuǎn)置為B，就是將A的三元組表a.data置換為表B的三元組表b.data，如果只是簡(jiǎn)單地交換

a.data中i和j的內(nèi)容，那么得到的b.data將是一個(gè)按列優(yōu)先順序存儲(chǔ)的稀疏矩陣B，要得到按行優(yōu)先順序存儲(chǔ)的b.data，就必須重新排列三元組的順序。由于A的列是B的行，因此，按a.data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b.data必定是按行優(yōu)先存放的。按這種方法設(shè)計(jì)的算法，其基本思想是：對(duì)A中的每一列col(0≦col≦n-1)，通過(guò)從頭至尾掃描三元表a.data，找出所有列號(hào)等于col的那些三元組，將它們的行號(hào)和列號(hào)互換后依次放入

b.data中，即可得到B的按行優(yōu)先的壓縮存儲(chǔ)表示。ijv13-3161521122518319342446-76314Void

transmatrix(tripletable

a,tripletable

b){intp

qcol;b.m=a.n;b.n=a.m;b.t=a.t;if(b.t<=0)printf(“A=0\n”);q=0;for(col=1;col<=a.n;col++)for(p=0;p<=a.t;p++)if(a.data[p].j==col){b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].v=a.data[p].v;q++;}}分析這個(gè)算法，主要的工作是在p和col的兩個(gè)循環(huán)中完成的，故算法的時(shí)間復(fù)雜度為

O(n*t)，即矩陣的列數(shù)和非零元的個(gè)數(shù)的乘積成正比。而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法為：for(col=0;col<=n-1;++col)for(row=0;row<=m;++row)t[col][row]=m[row][col];其時(shí)間復(fù)雜度為O(n*m)。當(dāng)非零元素的個(gè)數(shù)

t和m*n同數(shù)量級(jí)時(shí)，算法transmatrix的時(shí)間復(fù)雜度為O(n*n2)。三元組順序表雖然節(jié)省了存儲(chǔ)空間，但時(shí)間復(fù)雜度比一般矩陣轉(zhuǎn)置的算法還要復(fù)雜，同時(shí)還有可能增加算是法的難度。因此，此算法僅適用于t<=m*n的情況。下面給出另外一種稱(chēng)之為快速轉(zhuǎn)置的算法，其算法思想為：對(duì)A掃描一次，按A第二列提供的列號(hào)一次確定位置裝入B的一個(gè)三元組。具體實(shí)施如下：一遍掃描先確

定三元組的位置關(guān)系，二次掃描由位置

關(guān)系裝入三元組?？梢?jiàn)，位置關(guān)系是此

種算法的關(guān)鍵。為了預(yù)先確定矩陣M中的每一列的第一個(gè)非零元素在數(shù)組B中應(yīng)有的位置，需要先求得矩陣M中的每一列中非零元素的個(gè)數(shù)。因?yàn)椋壕仃嘙中第一列的第一個(gè)非零元素在數(shù)組B中應(yīng)有的位置等于前一列第一個(gè)非零元素的位置加上前列非零元素的個(gè)數(shù)。為此，需要設(shè)置兩個(gè)一維數(shù)組

num[0..n]和cpot[0..n]num[0..n]：統(tǒng)計(jì)M中每列非零元素的個(gè)數(shù)，

num[col]的值可以由A的第二列求得。ccpot[0..n]：由遞推關(guān)系得出M中的每列第一個(gè)非零元素在B中的位置。算法通過(guò)cpot數(shù)組建立位置對(duì)應(yīng)關(guān)系：

cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]2<=cpl<=a.n例如：圖5.4中的矩陣M和相應(yīng)的三元組A可以求得num[col]和cpot[col]的值如下：col1234567num[col]2221010pot[col]

135788912vq…A

i

j

v第一列元素個(gè)數(shù)第二列元素個(gè)數(shù)第三列元素個(gè)數(shù)pnumcpotq=cpot[col]p21v快速轉(zhuǎn)置算法如下：void

fasttranstri(tritupletable

b,tritupletable

a){int

p,q,col,k;int

num[0..a.n],copt[0..a.n];b.m=a.n;

b.n=a.m;

b.t=a.t;if(b.t<=0)printf(“a=0”\n);for(col=1;col<=a.u;++col)num[col]=0;for(k=1;k<=a.t;++k)++num[a.data[k].j];cpot[0]=1;for(col=2;col<=a.t;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=a.t;++p){col=a.data[p].j;

q=cpot[col];b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].v=a.data[p].v;

++cpot[col];}}}二、帶行表的三元組有時(shí)為了方便某些矩陣運(yùn)算，我們?cè)诎葱袃?yōu)先存儲(chǔ)的三元組中，加入一個(gè)行表來(lái)記錄稀疏矩陣中每行的非零元素在三元組表中的起始位置。當(dāng)將行表作為三元組表的一個(gè)新增屬性加以描述時(shí)，我們就得到了稀疏矩陣