c語言字符串數(shù)組和特殊矩陣

會計學1c語言字符串數(shù)組和特殊矩陣4.1字符串

4.1.1字符串的基本概念

字符串是由零個或多個字符構(gòu)成的有限序列，一般可表示成如下形式：

“c1c2c3….cn”(n≥0)

串中所含字符的個數(shù)n稱為字符串的長度；當n=0時，稱字符串為空串。

串中任意個連續(xù)的字符構(gòu)成的子序列稱為該串的子串，包含子串的串稱為主串。通常稱字符在字符串序列中的序號為該字符在串中的位置。子串在主串中的位置以子串的第一個字符在主串中的位置來表示。例如：T=“STUDENT”，S=“UDEN”,則S是T的子串，S在T中出現(xiàn)的位置為3。

第1頁/共65頁

兩個字符串相等，當且僅當兩個串的長度相等，并且各個對應位置的字符都相等。例如：

T1=“REDROSE”T2=“REDROSE”

由于T1和T2的長度不相等，因此T1≠T2。

若

T3=“STUDENT”T4=“STUDENS”

雖然T3和T4的長度相等，但兩者有些對應的字符不同，因而T3≠T4。

值得一提的是，若S=“

”，此時S由一個空格字符組成，其長度為1，它不等價于空串，因為空串的長度為0。

第2頁/共65頁4.1.2字符串類的定義

ADTstring{

數(shù)據(jù)對象D：由零個或多個字符型的數(shù)據(jù)元素構(gòu)成的有限集合；

數(shù)據(jù)關(guān)系R：{<ai,ai+1>|其中ai,ai+1D,

i=1,2,……n-1}

字符串的基本操作如下：

（1）

Strcreate(S)

（2）

Strassign(S,T)

（3）

Strlength(S)

（4）

Strempty(S)

第3頁/共65頁

（5）

Strclear(S)

（6）Strcompare(S1，S2)

（7）

Strconcat(S1，S2)

（8）

Substring(S,i,len)

（9）

Index(P,T)

（10）

Strinsert(S,i,T)

（11）

Strdelete(S,i,len)

（12）

Replace(S,T1,T2)

（13）

Strdestroy(S)

}ADTstring

第4頁/共65頁4.1.3字符串的存儲及其實現(xiàn)

1、串的順序存儲及其部分運算的實現(xiàn)

串的順序存儲使用數(shù)組存放，具體類型定義如下：

#defineMAXSIZE100

typedefstruct{

charstr[MAXSIZE];

intlength;

}seqstring;

第5頁/共65頁（1）插入運算strinsert(S,i,T)

voidstrinsert(seqstring*S,inti,seqstringT)

{intk;

if(i<1||i>S->length+1||S->length+T.length>MAXSIZE)

printf("connotinsert\n“);

else

{

for(k=S->length-1;k>=i-1;k--)

S->str[T.length+k]=S->str[k];

for(k=0;k<T.length;k++)

S->str[i-1+k]=T.str[k];

S->length=S->length+T.length;

S->str[S->length]=‘\0’;

}

}

第6頁/共65頁（2）刪除運算strdelete(S,i,len)

voidstrdelete(seqstring*S,inti,intlen)

{intk;

if(i<1||i>S->length||i+len-1>S->length)

printf(“cannotdelete\n”);

else

{

for(k=i-1+len;k<S->length;k++)

S->str[k-len]=S->str[k];

S->length=S->length-len;

S->str[S->length]=‘\0’;

}

}

第7頁/共65頁（3）連接運算strconcat(S1,S2)

seqstring*strconcat(seqstringS1,seqstringS2)

{inti;seqstring*r;

if(S1.length+S2.length>MAXSIZE)

{printf("cannotconcate");return(NULL);}

else

{r=(seqstring*)malloc(sizeof(seqstring));

for(i=0;i<S1.length;i++)r->str[i]=S1.str[i];

for(i=0;i<S2.length;i++)

r->str[S1.length+i]=S2.str[i];

r->length=S1.length+S2.length;

r->str[r->length]='\0';

}

return(r);

}

第8頁/共65頁（4）求子串運算substring(S,i,len)

seqstring*substring(seqstringS,inti,intlen)

{intk;seqstring*r;

if(i<1||i>S.length||i+len-1>S.length)

{printf(“error\n”);return(NULL);}

else

{r=(seqstring*)malloc(sizeof(seqstring));

for(k=0;k<len;k++)r->str[k]=S.str[i-1+k];

r->length=len;

r->str[r->length]='\0';

}

return(r);

}

第9頁/共65頁2串的鏈接存儲及其部分運算的實現(xiàn)

串的鏈接存儲采用單鏈表的形式實現(xiàn)，其中每個結(jié)點的定義如下：

typedefstructnode

{

chardata;

structnode*next;

}linkstrnode;

typedeflinkstrnode*linkstring;

例如，串S=“abcde”，其鏈接存儲結(jié)構(gòu)如下圖所示：

abcde∧

S第10頁/共65頁（1）創(chuàng)建字符串運算strcreate(S)

voidstrcreate(linkstring*S)

{charch;linkstrnode*p,*r;

*S=NULL;r=NULL;

while((ch=getchar())!=‘\n’)

{p=(linkstrnode*)malloc(sizeof(linkstrnode));

p->data=ch;

if(*S==NULL)*S=p;

elser->next=p;

r=p;/*r移向當前鏈接串的最后一個字符的位置*/

}

if(r!=NULL)r->next=NULL;/*處理表尾結(jié)點指針域*/

}

第11頁/共65頁（2）插入運算strinsert(S,i,T)

voidstrinsert(linkstring*S,inti,linkstringT)

{intk;linkstringp,q;

p=*S,k=1;

while(p&&k<i-1)

{p=p->next;k++;}

if(!p)printf("error\n");

else

{q=T;

while(q->next)q=q->next;

q->next=p->next;p->next=T;

}

}

第12頁/共65頁（3）刪除運算strdelete(S,i,len)

voidstrdelete(linkstring*S,inti,intlen)

{intk;linkstringp,q,r;

p=*S,q=null;k=1;

/*用p查找S的第i個元素，q始終跟蹤p的前驅(qū)*/

while(p&&k<i)

{q=p;p=p->next;k++;}

if(!p)printf("error1\n");

else

{k=1;

/*p從第i個元素開始查找長度為len子串的最后元素*/

while(k<len&&p)

{p=p->next;k++;}

if(!p)printf("error2\n");

第13頁/共65頁else

{if(!q){r=*S;*S=p->next;}

/*被刪除的子串位于S的最前面*/

else

{/*被刪除的子串位于Ｓ的中間或最后*/

r=q->next;q->next=p->next;

}

p->next=null;

while(r!=null)

{p=r;r=r->next;free(p);}

}

}

}

第14頁/共65頁（4）連接運算strconcat(S1,S2)

voidstrconcat(linkstring*S1,linkstringS2)

{

linkstringp;

if(!(*S1)){*S1=S2;return;}

else

if(S2)/*S1和S2均不為空串的情形*/

{

p=*S1;/*用p查找S1的最后一個字符的位置*/

while(p->next)p=p->next;

p->next=S2;/*將串S2連接到S1之后*/

}

}

第15頁/共65頁（5）求子串運算substring(S,i,len)

linkstringsubstring(linkstringS,inti,intlen)

{intk;linkstringp,q,r,t;

p=S,k=1;

/*用p查找S中的第i個字符*/

while(p&&k<i){p=p->next;k++;}

if(!p){printf("error1\n");return(null);}

else

{

r=(linkstring)malloc(sizeof(linkstrnode));

r->data=p->data;r->next=null;

第16頁/共65頁k=1;q=r;/*用q始終指向子串的最后一個字符的位置*/

while(p->next&&k<len)/*取長度為len的子串*/

{

p=p->next;k++;

t=(linkstring)malloc(sizeof(linkstrnode));

t->data=p->data;

q->next=t;q=t;

}

if(k<len){printf("error2\n");return(null);}

else

{q->next=null;return(r);}/*處理子串的尾部*/

}

}

第17頁/共65頁4.2字符串的模式匹配

尋找字符串p在字符串t中首次出現(xiàn)的起始位置稱為字符串的模式匹配，其中稱p為模式(pattern），t為正文(text)，t的長度遠遠大于p的長度。

4.2.1樸素的模式匹配算法

樸素模式匹配算法的基本思想是：用p中的每個字符去與t中的字符一一比較：

正文t：t1t2

……tm……tn

模式p：p1p2……pm

如果t1=p1,t2=p2,…..tm=pm，則模式匹配成功；否則

第18頁/共65頁將p向右移動一個字符的位置，重新用p中的字符從頭開始與t中相對應的字符依次比較，即：

t1t2t3……tmtm+1……tn

p1p2……pm-1pm

如此反復，直到匹配成功或者p已經(jīng)移到使t中剩下的字符個數(shù)小于p的長度的位置，此時意味著模式匹配失敗，表示t中沒有子串與模式p相等，我們約定返回-1代表匹配失敗。

樸素模式匹配算法的具體實現(xiàn)如下：

第19頁/共65頁intindex(seqstringp,seqstringt)

{inti,j,succ;

i=0;succ=0;/*succ為匹配成功的標志*/

while((i<t.length-p.length+1)&&(!succ))

{j=0;succ=1;/*用j掃描模式p*/

while((j<=p.length-1)&&succ)

if(p.str[j]==t.str[i+j])j++;

elsesucc=0;

++i;

}

if(succ)return(i-1);

elsereturn(-1);

}

第20頁/共65頁4.2.2快速模式匹配算法（KMP算法）

首先我們來分析下圖所示的情況：

t0t1t2

……tktk+1tk+2……tr-2tr-1tr…….

‖‖‖‖‖╫

p0p1p2……pi-2pi-1pi……….

（4-1）

t0t1t2

……tktk+1tk+2……tr-2tr-1tr…….

‖‖‖‖

p0p1……pi-2pi-1pi………

（4-2）

t0t1t2……tktk+1tk+2……tr-2tr-1tr…….

‖

‖

‖

p0………pi-3pi-2pi-1pi……

（4-3）

第21頁/共65頁(4-1)式表明此次匹配從p0與tk開始比較，當比較到pi與tr時出現(xiàn)不等情況，于是將模式右移一位，變成(4-2)所示的狀態(tài)，若此次比較成功，則必有p0=tk+1，p1=tk+2，……pi-2=tr-1，且pi-1≠pi；而根據(jù)(4-1)的比較結(jié)果有：p1=tk+1，p2=tk+2，……pi-1=tr-1，因此有：p0=p1，p1=p2，……pi-2=pi-1。這個性質(zhì)說明在模式p中pi之前存在一個從p0開始長度為i-1的連續(xù)序列p0p1

……pi-2

和以pi-1為結(jié)尾，長度同樣為i-1的連續(xù)序列p1p2……pi-1其值對應相等，即：

p0p1p2……pi-2pi-1pi……….

簡記為：

[p0—pi-2]=[p1—pi-1]

稱模式p中pi之前存在長度為i-1的真前綴和真后綴的匹配。

第22頁/共65頁

反之，若在(4-1)所示的狀態(tài)下，模式p中pi之前存在長度為i-1的真前綴和真后綴的匹配，即[p0—pi-2]=[p1—pi-1]且pi-1≠pi；當pi與tr出現(xiàn)不等時，根據(jù)前面已比較的結(jié)果p1=tk+1，p2=tk+2，……pi-1=tr-1，于是可得p0=tk+1，p1=tk+2，……pi-2=tr-1，因此接下來只需從pi-1與tr開始繼續(xù)后繼對應字符的比較即可。

再假設(shè)在(4-1)所示的狀態(tài)下，模式右移一位成為狀態(tài)(4-2)后，匹配仍然不成功，說明[p0—pi-2][p1—pi-1]或pi-1=pi，于是模式再右移一位，成為狀態(tài)(4-3)，若此次匹配成功，仿照上述分析，必有：

p0p1p2……pi-3pi-2pi-1pi……….

第23頁/共65頁即：

[p0—pi-3]=[p2—pi-1]

說明模式p中pi之前存在長度為i-2的真前綴和真后綴的匹配。由(4-3)表明，在(4-1)所示的狀態(tài)下，若模式p中pi之前最長真前綴和真后綴匹配的長度為i-2，當pi與tr出現(xiàn)不等時，接下來只需從pi-2與tr開始繼續(xù)后繼對應字符的比較。

考慮一般情況。在進行模式匹配時，若模式p中pi之前最長真前綴和真后綴匹配的長度為j，當pitr時，則下一步只需從pj與tr開始繼續(xù)后繼對應字符的比較,而不應該將模式一位一位地右移，也不應該反復從模式的開頭進行比較。這樣既不會失去任何匹配成功的機會，又極大地加快了匹配的速度。

第24頁/共65頁

根據(jù)上述分析，在模式匹配過程中，每當出現(xiàn)pitr時，下一次與tr進行比較的pj和模式p中pi之前最長真前綴和真后綴匹配的長度密切相關(guān)；而模式p中pi之前最長真前綴和真后綴匹配的長度只取決于模式p的組成，與正文無關(guān)。

于是我們可以針對模式p定義一個數(shù)組next[m]，其中next[i]表示當pitr時，下一次將從pnext[i]與tr開始繼續(xù)后繼對應字符的比較。顯然，next[i]的值與模式p中pi之前最長真前綴和真后綴匹配的長度密切相關(guān)。下面考慮如何根據(jù)模式p的組成求數(shù)組next的值。我們規(guī)定：

next[0]=-1

這表明當p0tr時，將從p-1與tr開始繼續(xù)后繼對應字符的比較；然而p-1是不存在的，我們可以將這種情況理解成下一步將從p0與tr+1開始繼續(xù)后繼對應字符的比較。

第25頁/共65頁

以下假設(shè)next[0]，next[1]，……，next[i]的值均已求出，現(xiàn)要求next[i+1]的值。由于在求解next[i]時已得到pi之前最長真前綴和真后綴匹配的長度，設(shè)其值為j，即：

p0p1p2……pi-j…….pj-1pj……pi-2pi-1pipi+1……

如果此時進一步有pj=pi，則pi+1之前最長真前綴和真后綴匹配的長度就為j+1，且next[i+1]=j+1;反之，若pj

pi，注意到，求pi+1之前最長真前綴和真后綴匹配問題本質(zhì)上仍然是一個模式匹配問題，只是在這里模式和正文都是同一個串p而已。因此當pjpi時，應該檢查pnext[j]與pi是否相等；若相等，則next[i+1]=next[j]+1；如仍然不相等，則再取pnext[next[j]]與pi進行比較，……直至要將p-1與pi進行比較為止，此時next[i+1]=0。

第26頁/共65頁以下給出了根據(jù)模式p的組成求數(shù)組next值的算法：

voidgetnext(seqstringp,intnext[])

{inti,j;

next[0]=-1;

i=0;j=-1;

while(i<p.length)

{

if(j==-1||p.str[i]==p.str[j])

{++i;++j;next[i]=j;}

else

j=next[j];

}

for(i=0;i<p.length;i++)

printf("%d",next[i]);

}

第27頁/共65頁試求以下串的next數(shù)組值：例1、abaabcacNext數(shù)組值：-10011201例2、ababaababNext數(shù)組值：-100123123第28頁/共65頁KMP算法基本思想如下：

假設(shè)以i和j分別指示正文t和模式p中正待比較的字符，令i、j的初值為0；若在匹配過程中ti=pj，則i與j分別加1；否則i不變，而j退到next[j]的位置繼續(xù)比較（即j=next[j]）；若相等，則指針各自增加1；否則j再退到下一個next[j]值的位置，依此類推，直至下列兩種可能:

(1)一種是j退到某個next（next[..[next[j]]…]））

時，ti與pj字符比較相等，則i、j指針各自增加1

后繼續(xù)進行比較；

(2)一種是j退到-1（即模式的第一個字符“失配”），

此時需將正文指針i向右滑動一個位置，即從正文

的下一個字符ti+1起和模式p重新從頭開始比較。

第29頁/共65頁KMP算法的具體實現(xiàn)如下：

intkmp(seqstringt,seqstringp,intnext[])

{inti,j;

i=0;j=0;

while(i<t.length&&j<p.length)

{

if(j==-1||t.str[i]==p.str[j])

{i++;j++;}

elsej=next[j];

}

if(j==p.length)return(i-p.length);

elsereturn(-1);

}

第30頁/共65頁4.3數(shù)組

4.3.1數(shù)組和數(shù)組元素

數(shù)組是線性表的一種存儲方式。其實，數(shù)組本身也可以看成是線性表的推廣，數(shù)組的每個元素由一個值和一組下標確定，在數(shù)組中，對于每組有定義的下標都存在一個與之相對應的值；而線性表是有限結(jié)點的有序集合，若將其每個結(jié)點的序號看成下標，線性表就是一維數(shù)組（向量）；當數(shù)組為多維數(shù)組時，其對應線性表中的每個元素又是一個數(shù)據(jù)結(jié)構(gòu)而已。

第31頁/共65頁

例如，對于一個mn的二維數(shù)組A[m][n]：

a00a01a02………a0(n-1)

a10a11a12………a1(n-1)

A=┋┋┋┋

┋┋┋┋

a(m-1)0a(m-1)1………a(m-1)(n-1)

當把二維數(shù)組看成是線性表時，它的每一個結(jié)點又是一個向量（一維數(shù)組）。例如，上述二維數(shù)組A可以看成是如下的線性表：

(A0，A1，A2，……Am-1)

即A中每一行成為線性表的一個元素，其中每個元素Ai(0≤i≤m-1)都是一個向量；

（ai0,ai1,ai2…….ai(n-1)）

第32頁/共65頁當然，也可以將上述二維數(shù)組A看成如下的線性表：

(A0’，A1’，A2’，……An-1’)

即A中每一列成為線性表的一個元素，其中每一個元素Ai’(0≤i≤n-1)都是一個向量:

（a0i,a1i,a2i，……a(m-1)i）

二維數(shù)組A中的每一個元素aij都同時屬于兩個向量，即：第i+1行的行向量和第j+1列的列向量，因此每個元素aij最多有兩個前驅(qū)結(jié)點a(i-1)j和ai(j-1)，也最多有兩個后繼結(jié)點a(i+1)j和ai(j+1)（只要這些結(jié)點存在）；特別地，a00沒有前驅(qū)結(jié)點，a(m-1)(n-1)沒有后繼結(jié)點，邊界上的結(jié)點均只有一個后繼結(jié)點或一個前驅(qū)結(jié)點。

對于m（m>2）維數(shù)組，可以依據(jù)上述規(guī)律類推。

第33頁/共65頁4.3.2數(shù)組類的定義

ADTarray{

數(shù)據(jù)對象D：具有相同類型的數(shù)據(jù)元素構(gòu)成的有序集合；

數(shù)據(jù)關(guān)系R：對于n維數(shù)組，其每一個元素均位于n個向量中，

每個元素最多具有n個前驅(qū)結(jié)點和n個后繼結(jié)點；

數(shù)組的基本操作如下：

（1）Initarray(A,n,index1,index2,……indexn)

（2）Destroyarray(A)

（3）Value(A,index1,index2,……indexn,x)

（4）Assign(A,e,index1,index2,……indexn)

}ADTarray

第34頁/共65頁4.3.3數(shù)組的順序存儲及實現(xiàn)

由于數(shù)組是由有限的元素構(gòu)成的有序集合，數(shù)組的大小和元素之間的關(guān)系一經(jīng)確定，就不再發(fā)生變化，因此數(shù)組均采用順序存儲結(jié)構(gòu)實現(xiàn)，它要求一片連續(xù)的存儲空間存儲。

多維數(shù)組數(shù)據(jù)元素的順序存儲有兩種方式：

按行優(yōu)先存儲

按列優(yōu)先存儲第35頁/共65頁例如：對于二維數(shù)組A[m][n]：

a00a01

……………a0(n-1)

a10a11

……………a1(n-1)

A=┋┋┋

┋┋┋

a(m-1)0a(m-1)1………a(m-1)(n-1)

若將A按行優(yōu)先存儲，其存儲順序為：a00，a01，……a0(n-1),a10,a11，…….a1(n-1)，……a(m-1)0，a(m-1)1，……a(m-1)(n-1)；而按列優(yōu)先存儲，其順序為：a00，a10，……a(m-1)0,a01,a11,…….a(m-1)1，……a0(n-1),..a1(n-1)，……a(m-1)(n-1)。

第36頁/共65頁

對于數(shù)組，一旦確定了它的維數(shù)和各維的長度，便可以為它分配存儲空間；當規(guī)定了數(shù)組元素的存儲次序后，便可根據(jù)給定的一組下標值求得相應數(shù)組元素的存儲位置。

現(xiàn)假設(shè)數(shù)組中每個元素占用L個存儲單元，若考慮按行優(yōu)先存儲方式，則上述A數(shù)組中任何一個元素aij的存儲位置可以按以下公式確定：

address（aij

）=address(a00)+(i×n+j)×L

若考慮按列優(yōu)先的存儲方式，數(shù)組中任何一個元素aij存儲位置的地址計算公式為：

address(aij)=address(a00)+(j×m+i)×L

第37頁/共65頁

多維數(shù)組的存儲也和二維數(shù)組一樣，存在兩種存儲方式：按行優(yōu)先和按列優(yōu)先。但由于多維數(shù)組中數(shù)據(jù)元素間的關(guān)系較二維數(shù)組復雜，因此數(shù)據(jù)元素的地址計算公式也相對復雜些，但兩者所采用的原理是相同的。

考慮n維數(shù)組的情形：

datatypeA[b1][b2]……[bn]；

其中b1、b2、……bn為數(shù)組每一維的長度。仍假設(shè)每個元素占用L個單元，則n維數(shù)組A中任何一個元素A[j1][j2]……[jn]在按行優(yōu)先存儲方式下的地址計算公式為：

address(A[j1][j2]……[jn])=address(A[0][0]…[0])+

(b2×b3×……bn×j1+b3×b4×……bn×j2+……bn×jn-1+jn)×L

上式可以簡寫為：

address((A[j1][j2]……[jn])=address(A[0][0]…[0])+

c1*j1+c2*j2+……cn*jn

其中cn=L,ci-1=bi×ci,1<i≤n。

第38頁/共65頁

以下以三維數(shù)組為例，給出三維數(shù)組的順序存儲表示及其部分運算的實現(xiàn)。

typedefintdatatype;

/*假設(shè)數(shù)組元素的值為整型*/

typedefstruct{

datatype*base;/*數(shù)組存儲區(qū)的首地址指針*/

intindex[3];/*存放三維數(shù)組各維的長度*/

intc[3]/*存放三維數(shù)組各維的ci值*/

}array；

第39頁/共65頁1、數(shù)組初始化運算initarray(A,b1,b2,b3)

intinitarray(array*A,intb1,intb2,intb3)

{

intelements;

if(b1<=0||b2<=0||b3<=0)return(0);

A->index[0]=b1;A->index[1]=b2;A->index[2]=b3;

elements=b1×b2×b3;

A->base=(datatype*)malloc(elements×sizeof(datatype));

if(!(A->base))return(0);

A->c[0]=b2×b3;A->c[1]=b3;A->c[2]=1;

return(1);

}

第40頁/共65頁2、

訪問數(shù)組元素值的運算value(A,i1,i2,i3,x)

intvalue(arrayA,inti1,inti2,inti3;datatype*x)

{

intoff;

if(i1<0||i1>=A.index[0]||i2<0||i2>=A.index[1]||

i3<0||i3>=A.index[2])

return(0);/*處理下標非法的情況*/

off=i1×A.c[0]+i2×A.c[1]+i3×A.c[2];

*x=*(A.base+off);/*賦值*/

return(1);

}

第41頁/共65頁3、數(shù)組元素的賦值運算assign(A,e,i1,i2,i3)

intassign(array*A,datatypee,inti1,inti2,inti3)

{

intoff;

if(i1<0||i1>=A->index[0]||i2<0||i2>=A->index[1]

||i3<0||i3>=A->index[2])

return(0);/*處理下標非法的情況*/

off=i1×A->c[0]+i2×A->c[1]+i3×A->c[2];

*(A->base+off)=e;/*賦值*/

return(1);

}

第42頁/共65頁4.4特殊矩陣

本節(jié)主要研究對稱矩陣、三角矩陣和帶狀矩陣的壓縮存儲。所謂壓縮存儲即為：多個相同值的結(jié)點只分配一個存儲空間，值為零的結(jié)點不分配空間。

4.4.1對稱矩陣的壓縮存儲

如果矩陣的行數(shù)和列數(shù)相等，則稱該矩陣為方陣。若n×n階的方陣A滿足：

aij=aji(0≤i≤n-1,0≤j≤n-1)

則稱矩陣A為對稱矩陣。在對稱矩陣中，幾乎有一半元素的值是對應相等的。如果將A中所有元素進行存儲，那將會造成空間的浪費，且n值越大，浪費將越嚴重。

第43頁/共65頁

對于對稱矩陣壓縮存儲時只需存儲對角線以上或?qū)蔷€以下的部分，未存儲的部分可以利用元素之間的對稱性來訪問。

現(xiàn)考慮只存儲對稱矩陣A對角線以下的部分（即下標滿足i≥j的數(shù)組元素aij）：

a00

a10a11

A=a20a21a22

┋┋┋

a(n-1)0………….a(n-1)(n-1)

若采用按行優(yōu)先的存儲方式，A進行壓縮存儲后任何一個元素aij的地址計算公式為：

address(a00)+(i*(i+1)/2+j)×L當i≥j

address(aij)=

address(a00)+(j*(j+1)/2+i)×L當i<j

第44頁/共65頁4.4.2三角矩陣的壓縮存儲

1、下三角矩陣

a0000………0

a10a110……….0

A=a20a21a22……….0

┋┋┋┋

a(n-1)0………………

a(n-1)(n-1)

仍考慮采用按行優(yōu)先方式，A中下三角部分的任何一個元素aij(i≥j)壓縮存儲后的地址計算公式為：

address(aij)=address(a00)+(i*(i+1)/2+j)×L當i≥j

與對稱矩陣不同的是，當i<j時，aij的值為0，其沒有對應的存儲單元。

第45頁/共65頁2、上三角矩陣

a00a01a02……a0(n-1)

0a11a12...….a1(n-1)

A=00a22.……a2(n-1)

┋

┋

┋

┋

000……a(n-1)(n-1)

對于上三角矩陣，只需考慮存儲對角線以上的部分，對角線以下為0的部分無需存儲。仍采用按行優(yōu)先存儲方式，矩陣A中被存儲元素aij(i≤j)在壓縮存儲方式下的地址計算公式為：

address(aij)=address(a00)+[(n+(n-1)+(n-2)+…..+(n-

(i-1)))+j-i]×L

=address(a00)+(i*n-(i-1)*i/2+j-i)*L

而當i>j時，aij的值為0，其沒有對應的存儲空間。

第46頁/共65頁4.4.3帶狀矩陣的壓縮存儲

對于n×n階方陣，若它的全部非零元素落在一個以主對角線為中心的帶狀區(qū)域中，這個帶狀區(qū)域包含主對角線下面及上面各b條對角線上的元素以及主對角線上的元素，那么稱該方陣為半帶寬為b的帶狀矩陣。帶狀矩陣的特點是：對于矩陣元素aij，若i-j>b或j-i>b，即|i-j|>b，則aij=0。

b條對角線

b條對角線主對角線

第47頁/共65頁例、

2037200014253045001114354250016202610280071583000291655第48頁/共65頁

帶狀矩陣進行壓縮存儲時，只存儲帶狀部分內(nèi)部的元素，對于帶狀區(qū)域以外的元素，即|i-j|>b的aij，均不分配存儲空間。為了方便起見，我們規(guī)定按如下方法進行存儲：除第一行和最后一行外，每行都分配2b+1個元素的空間，將帶狀區(qū)域中的元素存儲于（(2b+1)×n-2b）×L個存儲單元之中，其中L為每個元素占用空間的大小。仍考慮采用按行優(yōu)先的存儲方式，于是可以得到帶狀區(qū)域中任何一個元素aij的地址計算公式為：

address(aij)=address(a00)+((i×(2b+1)-b)+(j-i+b))×L

=address(a00)+(i×(2b+1)+j-i)×L

(當|i-j|≤b時)

address(a34)=1+（3×(2×2+1)+4-3)×1=17第49頁/共65頁4.5稀疏矩陣

如果一個矩陣中很多元素的值為零，即零元素的個數(shù)遠遠大于非零元素的個數(shù)時，稱該矩陣為稀疏矩陣。

4.5.1稀疏矩陣類的定義

ADTspmatrix{

數(shù)據(jù)對象D：具有相同類型的數(shù)據(jù)元素構(gòu)成的有限

集合；

數(shù)據(jù)關(guān)系R：D中的每個元素均位于2個向量中，每

個元素最多具有2個前驅(qū)結(jié)點和2個后繼結(jié)點，

且D中零元素的個數(shù)遠遠大于非零元素的個數(shù)；

稀疏矩陣的基本運算如下：

（1）Createspmatrix(A)

第50頁/共65頁

（2）compressmatrix(A,B)

（3）Destroyspmatrix(A)

（4）Printspmatrix(A)

（5）Copyspmatrix(A,B)

（6）Addspmatrix(A,B,C)

（7）Subspmatrix(A,B,C)

（8）Multspmatrix(A,B,C)

（9）Transpmatrix(B,C)

（10）locatespmatrix(A,x,rowx,colx)

}ADTspmatrix第51頁/共65頁4.5.2稀疏矩陣的順序存儲及其實現(xiàn)

稀疏矩陣的順序存儲方法包括：三元組表示法、帶輔助行向量的二元組表示法和偽地址表示法，其中以三元組表示法最常用，故在此主要介紹稀疏矩陣的三元組表示。

在三元組表示法中，稀疏矩陣的每個非零元素可以采用如下形式表示：

(i,j,value)

其中i表示非零元素所在的行號，j表示非零元素所在的列號，value表示非零元素的值。采用三元組表示法表示一個稀疏矩陣時，首先將它的每一個非零元素表示成上述的三元組形式，然后按行號遞增的次序、同一行的非零元素按列號遞增的次序?qū)⑺蟹橇阍氐娜M表示存放到一片連續(xù)的存儲單元中即可。

第52頁/共65頁以下是稀疏矩陣A7×6及其對應的三元組表示。

B012

0767

00–5010

102-5

0002002041

3000003132

0000004203

120000054012

0000046554

002100076221

稀疏矩陣AA的三元組表示

第53頁/共65頁

稀疏矩陣A及其對應的三元組表示矩陣B的數(shù)據(jù)類型定義如下:

typedefstruct{

intdata[100][100];/*存放稀疏矩陣的二

維數(shù)組*/

intm,n;/*分別存放稀疏矩陣

的行數(shù)和列數(shù)*/

}matrix;

typedefintspmatrix[100][3];

/*稀疏矩陣對應的三元組表示的類型*/第54頁/共65頁1、產(chǎn)生稀疏矩陣三元組表示的算法

voidcompressmatrix(matrixA,spmatrixB)

{inti,j,k=1;

for(i=0;i<A.m;i++)

for(j=0;j<A.n;j++)

if(A.data[i][j]!=0)

{B[k][0]=i;

B[k][1]=j;

B[k][2]=A.data[i][j];

k++;

}

B[0][0]=A.m;B[0][1]=A.n;

B[0][2]=k-1;

}

第55頁/共65頁2、求稀疏矩陣的轉(zhuǎn)置算法transpmatrix(B,C)

按照矩陣轉(zhuǎn)置的定義，要實現(xiàn)矩陣的轉(zhuǎn)置，只要將矩陣中以主對角線為對稱軸的元素aij和aji的值互換。但三元組的排列要求采用按行優(yōu)先方式，如果只是簡單地將非零元素的行號和列號交換，則新產(chǎn)生的三元組表示將不再滿足按行優(yōu)先的原則。

解決的辦法是：首先確定B中每一列非零元素的個數(shù)，也即將來C中每一行非零元素的個數(shù)，從而可計算出C中每一行非零元素三元組的起始位置，這樣便可實現(xiàn)將B中的非零元素交換行號和列號后逐一放到它們在C中的最終位置上了。為了求B中每一列非零元素的個數(shù)和C中每一行非零元素三元組的起始位置，可以設(shè)置兩個數(shù)組x和y來實現(xiàn)相應的功能。

第56頁/共65頁voidtranspmatrix(spmatrixB,spmatrixC)

{inti,j,t,m,n;

intx[100];/*用來存放B中每一列非零元素的個數(shù)*/

inty[100];/*存放C中每一行非零元素三元組的起始

位置*/

m=B[0][0];n=B[0][1];t=B[0][2];

C[0][0]=n;C[0][1]=m;C[0][2]=t;

if(t>0)

{

for(i=0;i<n;i++)x[i]=0;

for(i=1;i<=t;i++)x[B[i][1]]=x[B[i][1]]+1;

/*統(tǒng)計B中每一列非零元素的個數(shù)*/

/*求矩陣C中每一行非零元素三元組的起始位置*/

y[0]=1;

for(i=1;i<n;i++)y[i]=y[i-1]+x[i-1];

第57頁/共65頁for(i=1;i<=t;i++)

{/*將B中非零元素交換行號、列號后寫入C中