其他線(xiàn)性數(shù)據(jù)結(jié)構(gòu)

其他線(xiàn)性數(shù)據(jù)結(jié)構(gòu)第一頁(yè)，共五十頁(yè)，2022年，8月28日本章要點(diǎn)串、多維數(shù)組、特殊矩陣及稀疏矩陣的定義串、多維數(shù)組、特殊矩陣及稀疏矩陣的存儲(chǔ)方式串、稀疏矩陣的基本操作第二頁(yè)，共五十頁(yè)，2022年，8月28日本章難點(diǎn)多維數(shù)組的順序存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)稀疏矩陣的基本操作學(xué)習(xí)目標(biāo)掌握串操作掌握多維數(shù)組的順序存儲(chǔ)掌握特殊矩陣的壓縮存儲(chǔ)掌握稀疏矩陣的基本操作第三頁(yè)，共五十頁(yè)，2022年，8月28日4.1串串是一種特殊的線(xiàn)性結(jié)構(gòu)，它的數(shù)據(jù)元素僅由字符組成。第四頁(yè)，共五十頁(yè)，2022年，8月28日4.1.1串的定義和基本操作1.串的相關(guān)概念串(String)

串是由零個(gè)或多個(gè)字符組成的有限序列。一般記為S=“a1a2

…an”

(n≥0)。其中，S是串名，用單引號(hào)或雙引號(hào)括起來(lái)的字符序列是串的值，ai(1≤i≤n)可以是字母、數(shù)字或其他字符。值得注意的是，引號(hào)本身不屬于串。串的長(zhǎng)度

串中字符的數(shù)目n?？沾?/p>

長(zhǎng)度為0的串。空格串

由一個(gè)或多個(gè)空格組成的串。需要注意的是，空格串不是空串，空格串的長(zhǎng)度由其中空格的數(shù)目決定，而空串的長(zhǎng)度為0。第五頁(yè)，共五十頁(yè)，2022年，8月28日4.1.1串的定義和基本操作串的子串、主串串中任意個(gè)連續(xù)的字符組成的子序列稱(chēng)為該串的子串，包含子串的串相應(yīng)地稱(chēng)為主串?？沾侨我獯淖哟?，任意串是其自身的子串。字符在串中的位置

字符在序列中的序號(hào)。子串在主串中的位置

以子串的第一個(gè)字符在主串中的位置來(lái)表示。兩串相等當(dāng)兩個(gè)串的長(zhǎng)度相等，并且各個(gè)對(duì)應(yīng)位置上的字符都相等時(shí)，稱(chēng)這兩個(gè)串相等。例如上例中的C、D看起來(lái)相似，但不相等。

第六頁(yè)，共五十頁(yè)，2022年，8月28日4.1.1串的定義和基本操作2.串的基本操作

（1）=賦值操作賦值號(hào)左邊必須是串變量，右邊可以是串變量、串常量或運(yùn)算值是串值的表達(dá)式。（2判兩串是否相等的函數(shù)。若S和T相等，則返回函數(shù)值“true”或1；否則返回函數(shù)值“false”或0。S和T可以是空串，也可以是非空串。（3）求串的長(zhǎng)度的函數(shù)。函數(shù)值為串S中字符的個(gè)數(shù)。（4）聯(lián)接操作。設(shè)S，T1，T2都是串變量，聯(lián)接操作就是將串T1和串T2放入S中。S串中的前一段和串T1相等，S串中的后一段和串T2相等。CONCAT(S,T1,T2)與CONCAT(S,T2,T1)的結(jié)果不一樣。聯(lián)接操作還可推廣至n個(gè)串變量。（5）SUBSTR(S,i,j)求子串函數(shù)。當(dāng)1≤i≤STRLEN(S)且0≤j≤STRLEN(S)-i+1，返回函數(shù)值是S的一個(gè)子串，即從串S中第i個(gè)字符起，長(zhǎng)度為j的字符序列。否則返回一個(gè)特殊的值。（6）INDEX(S,T)定位函數(shù)。若在主串S中存在和T相等的子串，則函數(shù)值返回在S中出現(xiàn)的第一個(gè)和T相等的子串在S中的位置，否則函數(shù)值為零。注意T不能是空串。第七頁(yè)，共五十頁(yè)，2022年，8月28日4.1.1串的定義和基本操作（7）置換操作。操作結(jié)果是以串V替換所有在串S中出現(xiàn)的和串T相等的不重疊的子串。（8）插入操作。當(dāng)1≤pos≤STRLEN(S)+1時(shí)，在串S的第pos個(gè)字符之前插入串T。（9）刪除操作。當(dāng)1≤pos≤STRLEN(S)且0≤len≤STRLEN(S)-pos+1時(shí)，從串S中刪去第pos字符起、長(zhǎng)度為len的子串。（10）串復(fù)制（11）輸出串第八頁(yè)，共五十頁(yè)，2022年，8月28日1、串賦值運(yùn)算voidAssign(SqString&s,chart[]) { inti=0; while(t[i]!='\0') {s.ch[i]=t[i];i++; } s.len=i;}2、串復(fù)制運(yùn)算voidStrCopy(SqString&s,SqStringt) { inti; for(i=0;i<t.len;i++) s.ch[i]=t.ch[i]; s.len=t.len;}第九頁(yè)，共五十頁(yè)，2022年，8月28日3、求串長(zhǎng)運(yùn)算intStrLength(SqStrings) { return(s.len);}4、判斷串相等運(yùn)算intStrEqual(SqStrings,SqStringt) { inti=0; if(s.len!=t.len) /*串長(zhǎng)不同時(shí)返回0*/ return(0); else {for(i=0;i<s.len;i++) if(s.ch[i]!=t.ch[i])/*有一個(gè)對(duì)應(yīng)字符不同時(shí)返回0*/ return(0); return(1); }}第十頁(yè)，共五十頁(yè)，2022年，8月28日5、串連接運(yùn)算SqStringConcat(SqStrings,SqStringt) { SqStringr; inti,j; for(i=0;i<s.len;i++) /*將s復(fù)制到r*/ r.ch[i]=s.ch[i]; for(j=0;j<t.len;j++) /*將t復(fù)制到r*/ r.ch[s.len+j]=t.ch[j]; r.len=i+j; return(r); /*返回r*/}第十一頁(yè)，共五十頁(yè)，2022年，8月28日6、求子串運(yùn)算SqStringSubStr(SqStrings,inti,intj) { SqStringt; intk; if(i<1||i>s.len||j<1||i+j>s.len+1) t.len=0; /*參數(shù)錯(cuò)誤時(shí)返回空串*/ else { for(k=i-1;k<i+j;k++) t.ch[k-i+1]=s.ch[k]; t.len=j; } return(t);}第十二頁(yè)，共五十頁(yè)，2022年，8月28日7、查找子串位置運(yùn)算intIndex(SqStrings,SqStringt) { inti=0,j=0,k; /*i和j分別掃描主串s和子串t*/ while(i<s.len&&j<t.len) { if(s.ch[i]==t.ch[j])/*對(duì)應(yīng)字符相同時(shí),繼續(xù)比較下一對(duì)字符*/ { i++;j++; } else *否則,主子串指針回溯重新開(kāi)始下一次匹配*/ { i=i-j+1;j=0; } } if(j>=t.len) k=i-t.len+1;/*求出第一個(gè)字符的位置*/ else k=-1; /*置特殊值-1*/ return(k);}第十三頁(yè)，共五十頁(yè)，2022年，8月28日8、子串插入運(yùn)算intInsStr(SqString&s,inti,SqStringt) { intj; if(i>s.len+1) return(0); /*位置參數(shù)值錯(cuò)誤*/ else { for(j=s.len;j>=i-1;j--) /*將s.ch[i-1]-s.ch[s.len-1]*/ s.ch[j+t.len]=s.ch[j]; /*后移t.len個(gè)位置*/ for(j=0;j<t.len;j++) s.ch[i+j-1]=t.ch[j]; s.len=s.len+t.len; /*修改s串長(zhǎng)度*/ return(1); }}第十四頁(yè)，共五十頁(yè)，2022年，8月28日9、子串刪除運(yùn)算intDelStr(SqString&s,inti,intj) { intk; if(i<1||i>s.len||j<1||i+j>s.len+1) return(0); /*位置參數(shù)值錯(cuò)誤*/else { for(k=i+j-1;k<s.len;k++)/*將s的第i+j位置之后的字符前移j位*/ s.ch[k-j]=s.ch[k]; s.len=s.len-j; /*修改s的長(zhǎng)度*/ return(1); }}第十五頁(yè)，共五十頁(yè)，2022年，8月28日10、子串替換運(yùn)算SqStringRepStrAll(SqStrings,SqStrings1,SqStrings2) { inti; i=Index(s,s1); while(i>=0) { DelStr(s,i,s1.len); /*刪除*/ InsStr(s,i,s2); /*插入*/ i=Index(s,s1); } return(s);}11、輸出串運(yùn)算voidDispStr(SqStrings) { inti; for(i=0;i<s.len;i++) printf("%c",s.ch[i]); printf("\n");}第十六頁(yè)，共五十頁(yè)，2022年，8月28日串的鏈?zhǔn)酱鎯?chǔ)及基本運(yùn)算串的定義：typedefstructnode{ chardata; /*存放字符*/ structnode*next; /*指針域*/}LinkString;第十七頁(yè)，共五十頁(yè)，2022年，8月28日1、串賦值運(yùn)算voidAssign(LinkString*&s,chart[]){ inti=0; LinkString*q,*tc; s=(LinkString*)malloc(sizeof(LinkString));/*建立頭結(jié)點(diǎn)*/ s->next=NULL; tc=s; /*tc指向s串的尾結(jié)點(diǎn)*/ while(t[i]!='\0') { q=(LinkString*)malloc(sizeof(LinkString)); q->data=t[i]; tc->next=q;tc=q; i++; } tc->next=NULL; /*終端結(jié)點(diǎn)的next置NULL*/}第十八頁(yè)，共五十頁(yè)，2022年，8月28日2、串復(fù)制運(yùn)算voidStrCopy(LinkString*&s,LinkString*t) /*t=>s*/{ LinkString*p=t->next,*q,*tc; s=(LinkString*)malloc(sizeof(LinkString));/*建立頭結(jié)點(diǎn)*/ s->next=NULL; tc=s; /*tc指向s串的尾結(jié)點(diǎn)*/ while(p!=NULL) /*復(fù)制t的所有結(jié)點(diǎn)*/ { q=(LinkString*)malloc(sizeof(LinkString)); q->data=p->data; tc->next=q;tc=q; p=p->next;} tc->next=NULL; /*終端結(jié)點(diǎn)的next置NULL*/}第十九頁(yè)，共五十頁(yè)，2022年，8月28日3、求串長(zhǎng)運(yùn)算intStrLength(LinkString*s){ intn=0; LinkString*p=s->next; while(p!=NULL) /*掃描串s的所有結(jié)點(diǎn)*/ { n++;p=p->next; }return(n);}第二十頁(yè)，共五十頁(yè)，2022年，8月28日4、判斷串相等運(yùn)算intStrEqual(LinkString*s,LinkString*t){ LinkString*p=s->next,*q=t->next; while(p!=NULL&&q!=NULL)/*比較兩串的當(dāng)前結(jié)點(diǎn)*/ {if(p->data!=q->data)/*data域不等時(shí)返回0*/ return(0);p=p->next;q=q->next; } if(p!=NULL||q!=NULL) /*兩串長(zhǎng)度不等時(shí)返回0*/ return(0); return(1);}第二十一頁(yè)，共五十頁(yè)，2022年，8月28日5、串連接運(yùn)算LinkString*Concat(LinkString*s,LinkString*t){ LinkString*p=s->next,*q,*tc,*str;str=(LinkString*)malloc(sizeof(LinkString));/*建立頭結(jié)點(diǎn)*/ str->next=NULL; tc=str; /*tc總是指向新鏈表的尾結(jié)點(diǎn)*/ while(p!=NULL) /*將s串復(fù)制給str*/ { q=(LinkString*)malloc(sizeof(LinkString)); q->data=p->data; tc->next=q;tc=q; p=p->next;} p=t->next; while(p!=NULL) /*將t串復(fù)制給str*/ { q=(LinkString*)malloc(sizeof(LinkString)); q->data=p->data; tc->next=q;tc=q; p=p->next;}tc->next=NULL;return(str);}第二十二頁(yè)，共五十頁(yè)，2022年，8月28日6、求子串運(yùn)算LinkString*SubStr(LinkString*s,inti,intj){ intk=1; LinkString*p=s->next,*q,*tc,*str;str=(LinkString*)malloc(sizeof(LinkString));/*建立頭結(jié)點(diǎn)*/ str->next=NULL; tc=str; /*tc總是指向新鏈表的尾結(jié)點(diǎn)*/ while(k<i&&p!=NULL) { p=p->next;k++; } if(p!=NULL) { k=1; while(k<=j&&p!=NULL) /*復(fù)制j個(gè)結(jié)點(diǎn)*/ { q=(LinkString*)malloc(sizeof(LinkString)); q->data=p->data; tc->next=q;tc=q; p=p->next; k++;} tc->next=NULL; } return(str);}第二十三頁(yè)，共五十頁(yè)，2022年，8月28日7、查找子串運(yùn)算intIndex(LinkString*s,LinkString*t){ LinkString*p=s->next,*p1,*q,*q1; inti=0; while(p!=NULL) /*循環(huán)掃描s的每個(gè)結(jié)點(diǎn)*/ {q=t->next; /*子串總是從第一個(gè)字符開(kāi)始比較*/if(p->data==q->data)/*判定兩串當(dāng)前字符相等*/{/*若首字符相同,則判定s其后字符是否與t的依次相同*/ p1=p->next;q1=q->next; while(p1!=NULL&&q1!=NULL&&p1->data==q1->data) { p1=p1->next; q1=q1->next; } if(q1==NULL) /*若都相同,返回相同的子串的起始位置*/ return(i);}p=p->next;i++; } return(-1); /*若不是子串,返回-1*/}第二十四頁(yè)，共五十頁(yè)，2022年，8月28日8、子串插入運(yùn)算intInsStr(LinkString*&s,inti,LinkString*t){ intk; LinkString*q=s->next,*p,*str; StrCopy(str,t); /*將t復(fù)制到str*/ p=str;str=str->next; free(p); /*刪除str的頭結(jié)點(diǎn)*/ for(k=1;k<i;k++) /*在s中找到第i-1個(gè)結(jié)點(diǎn),由p指向它,q指向下一個(gè)結(jié)點(diǎn)*/ {if(q==NULL) /*位置參數(shù)i錯(cuò)誤*/ return(0); p=q; q=q->next; } p->next=str; /*將str鏈表鏈接到*p之后*/ while(str->next!=NULL) /*由str指向尾結(jié)點(diǎn)*/ str=str->next; str->next=q; /*將*q鏈接到*str之后*/ return(1);}第二十五頁(yè)，共五十頁(yè)，2022年，8月28日9、子串刪除運(yùn)算intDelStr(LinkString*&s,inti,intj){ intk; LinkString*q=s->next,*p,*t; for(k=1;k<i;k++) /*在s中找到第i-1個(gè)結(jié)點(diǎn),由p指向它,q指向下一個(gè)結(jié)點(diǎn)*/ {if(q==NULL) /*位置參數(shù)i錯(cuò)誤*/ return(0);p=q;q=q->next; }for(k=1;k<=j;k++) /*刪除*p之后的j個(gè)結(jié)點(diǎn),并由q指向下一個(gè)結(jié)點(diǎn)*/ { if(q==NULL) /*長(zhǎng)度參數(shù)j錯(cuò)誤*/return(0); t=q; q=q->next; free(t); } p->next=q; return(1);}第二十六頁(yè)，共五十頁(yè)，2022年，8月28日10、子串替換運(yùn)算LinkString*RepStrAll(LinkString*s,LinkString*s1,LinkString*s2){ inti; i=Index(s,s1); while(i>=0) { DelStr(s,i+1,StrLength(s1));/*刪除串s1*/ InsStr(s,i+1,s2); /*插入串s2*/ i=Index(s,s1); } return(s);}第二十七頁(yè)，共五十頁(yè)，2022年，8月28日11、輸出子串運(yùn)算voidDispStr(LinkString*s){ LinkString*p=s->next; while(p!=NULL) {printf("%c",p->data);p=p->next; } printf("\n");}第二十八頁(yè)，共五十頁(yè)，2022年，8月28日4.2多維數(shù)組4.2.1多維數(shù)組的定義及存儲(chǔ)結(jié)構(gòu)1.多維數(shù)組的定義數(shù)組是由下標(biāo)和值組成的序?qū)Φ募?。在?shù)組中，一旦給定下標(biāo)，都存在一個(gè)與其相對(duì)應(yīng)的值，這個(gè)值就稱(chēng)為數(shù)組元素。數(shù)組可以看作是廣義的線(xiàn)性表，即多維數(shù)組對(duì)應(yīng)的線(xiàn)性表中的數(shù)據(jù)元素本身又是一個(gè)線(xiàn)性表。數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，數(shù)組的運(yùn)算通常只有兩種基本運(yùn)算：（1）取值操作：給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素。（2）賦值操作：給定一組下標(biāo)，存儲(chǔ)/修改相應(yīng)數(shù)據(jù)元素。第二十九頁(yè)，共五十頁(yè)，2022年，8月28日4.2.1多維數(shù)組的定義及存儲(chǔ)結(jié)構(gòu)

2.多維數(shù)組的存儲(chǔ)結(jié)構(gòu)數(shù)組一般不做插入和刪除操作，也就是說(shuō)，數(shù)組一旦建立，其結(jié)構(gòu)中的元素個(gè)數(shù)和元素之間的關(guān)系就不再發(fā)生變化，因此數(shù)組可以采用向量(順序)存儲(chǔ)結(jié)構(gòu)來(lái)存放。在進(jìn)行順序存儲(chǔ)時(shí)存放次序有兩種規(guī)則：

（1）先行后列順序，或者稱(chēng)為行優(yōu)先順序，其分配規(guī)律是：最右邊的下標(biāo)先變化，即最右下標(biāo)從小到大，循環(huán)一遍后，右邊第二個(gè)下標(biāo)再變，…，從右向左，最后是左下標(biāo)。

（2）先列后行順序，或者稱(chēng)為列優(yōu)先順序，其分配的規(guī)律是：最左邊的下標(biāo)先變化，即最左下標(biāo)從小到大，循環(huán)一遍后，左邊第二個(gè)下標(biāo)再變，…，從左向右，最后是右下標(biāo)。第三十頁(yè)，共五十頁(yè)，2022年，8月28日4.2.1多維數(shù)組的定義及存儲(chǔ)結(jié)構(gòu)對(duì)于數(shù)組，一旦確定了它的維數(shù)和各維的長(zhǎng)度，便可以為它分配存儲(chǔ)空間。反之，若已知一組下標(biāo)也可求出對(duì)應(yīng)數(shù)據(jù)元素的存儲(chǔ)位置。例如，假設(shè)，一個(gè)二維數(shù)組A(m×n)按行優(yōu)先順序存儲(chǔ)在向量中，其第一個(gè)元素的序號(hào)為0，且已知某個(gè)數(shù)據(jù)元素的下標(biāo)i,j(0≤i≤m-1，0≤j≤n-1)，則可用下列公式計(jì)算該數(shù)據(jù)元素在向量中的序號(hào)index(ai,j)：

index(ai,j)=n×i+j+1若已知數(shù)組A(m×n)中第一個(gè)元素的存儲(chǔ)地址LOC(a0,0)，并已知某個(gè)數(shù)據(jù)元素的下標(biāo)i,j(0≤i≤m-1，0≤j≤n-1)，及每個(gè)數(shù)據(jù)元素占用的存儲(chǔ)單元數(shù)為b，則該數(shù)據(jù)元素的存儲(chǔ)地址：

LOC(ai,j)=LOC(a0,0)+(index(ai,j)–1)×b=LOC(a0,0)+(n×i+j)×b

第三十一頁(yè)，共五十頁(yè)，2022年，8月28日4.2.2稀疏矩陣及壓縮1.稀疏矩陣的壓縮存儲(chǔ)若一個(gè)矩陣中非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)，則稱(chēng)為稀疏矩陣。對(duì)于稀疏矩陣，只須考慮非零元素的存儲(chǔ)。每一個(gè)非零元素aij，可以用一個(gè)三元組(i,j,v)來(lái)惟一確定。其中，i，j是非零元素在矩陣中對(duì)應(yīng)的行號(hào)和列號(hào)，v是非零元素的值。將稀疏矩陣中的非零元素的三元組按行優(yōu)先的順序排列則得到一個(gè)元素類(lèi)型是三元組的線(xiàn)性表，稱(chēng)為三元組表。三元組表是稀疏矩陣的一種順序存儲(chǔ)結(jié)構(gòu)。以下的討論中均假定三元組是按行優(yōu)先的順序排列的。稀疏矩陣的三元組存儲(chǔ)的數(shù)據(jù)類(lèi)型描述如下：第三十二頁(yè)，共五十頁(yè)，2022年，8月28日4.2.2稀疏矩陣及壓縮#defineMAXLEN40#defineDATATYPE1inttypedefstruct{inti,j;/*非零元素的行號(hào)和列號(hào)*/DATATYPE1v;/*非零元素的值*/}NODE;typedefstruct{intm,n,t;/*稀疏矩陣的行數(shù)和列數(shù)及非零元素的個(gè)數(shù)*/

NODEdata［MAXLEN］;/*三元組線(xiàn)性表*/}SPMATRIX;

三元組存儲(chǔ)結(jié)構(gòu)因以行優(yōu)先存放，存在以下的規(guī)律：元組中的第一列按行號(hào)的順序由小到大排列，元組中的第二列是列號(hào)，列號(hào)在行號(hào)相同時(shí)也是由小到大排列。第三十三頁(yè)，共五十頁(yè)，2022年，8月28日4.2.2稀疏矩陣及壓縮2.稀疏矩陣的轉(zhuǎn)置存儲(chǔ)矩陣轉(zhuǎn)置就是把矩陣元素的行和列對(duì)換，一個(gè)m行n列的矩陣轉(zhuǎn)置以后變成一個(gè)n行m列的矩陣。例如，矩陣M轉(zhuǎn)置后得到矩陣N，在矩陣M中位于i,j上的元素，轉(zhuǎn)置后對(duì)應(yīng)于矩陣N中j,i上的元素，即Mi,j=Nj,i，其中0≤i≤m-1，0≤j≤n-1。以下給出的轉(zhuǎn)置算法都是在矩陣的三元組存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的（1）一般插入算法算法的思路是：對(duì)a.data掃描一遍，掃描過(guò)程中依次取出a.data中的每一個(gè)三元組元素，將對(duì)應(yīng)的行號(hào)和列號(hào)對(duì)換，放入b.data中。為保證b.data具有三元組存放元素的規(guī)律，需和前面的元素按行及列比較之后，才可插在對(duì)應(yīng)位置上。此算法在移動(dòng)元素上花去了大量的時(shí)間。第三十四頁(yè)，共五十頁(yè)，2022年，8月28日4.2.2稀疏矩陣及壓縮（2）transpose算法該算法的思路是：考慮到b.data中的行就是a.data中的列，要想得到b.data中行號(hào)為x的三元組元素，可對(duì)a.data掃描一遍，找出a.data中列號(hào)為x的元素即可。以下就是中文描述的transpose算法。①對(duì)a.data掃描第1遍，得到a.data[p].j=1(0≤p≤a.t-1)的元素，它們應(yīng)該就是b.data中行號(hào)為1的元素，而且根據(jù)規(guī)律，依次得到的這些元素的行號(hào)一定是從小到大排好序的，所以把這些三元組元素的i,j對(duì)換放到b.data中，b.data行號(hào)為1的元素就放到位了。②對(duì)a.data掃描第2遍，得到a.data［p］.j=2(1≤p≤a.t)的元素，把這些三元組元素的i,j對(duì)換放到b.data中，b.data行號(hào)為2的元素就放到位了。③重復(fù)①、②的方法，對(duì)a.data掃描a.n遍，數(shù)組轉(zhuǎn)置完成。

第三十五頁(yè)，共五十頁(yè)，2022年，8月28日4.2.2稀疏矩陣及壓縮voidtranspose(SPMATRIXb,SPMATRIXa){intp,q,col;b.m=a.n;/*行列數(shù)互換*/b.n=a.m;b.t=a.t;/*非零元素個(gè)數(shù)不變*/if(a.t!=0){q=0;for(col=0;col<=a.n-1;col++)for(p=0;p<=a.t-1;p++)if(a.data［p］.j==col){b.data［q］.j=a.data［p］.i;b.data［q］.i=a.data［p］.j;b.data［q］.v=a.data［p］.v;q++;}}}

第三十六頁(yè)，共五十頁(yè)，2022年，8月28日4.2.3特殊矩陣的壓縮1.對(duì)稱(chēng)矩陣的壓縮存儲(chǔ)對(duì)稱(chēng)矩陣的特點(diǎn)是：在一個(gè)n階方陣中，有aij=aji

，其中0≤i,j≤n-1，如圖4-8所示。對(duì)稱(chēng)矩陣關(guān)于主對(duì)角線(xiàn)對(duì)稱(chēng)，因此只需存儲(chǔ)上三角或下三角部分即可，比如，我們只存儲(chǔ)下三角中的元素aij，其特點(diǎn)是j≤i且0≤i≤n-1，對(duì)于上三角中的元素aij

，它和對(duì)應(yīng)的aji相等，因此當(dāng)訪(fǎng)問(wèn)的元素在上三角時(shí)，直接去訪(fǎng)問(wèn)和它對(duì)應(yīng)的下三角元素即可，這樣，原來(lái)需要n*n個(gè)存儲(chǔ)單元，現(xiàn)在只需要n*(n+1)/2個(gè)存儲(chǔ)單元了。第三十七頁(yè)，共五十頁(yè)，2022年，8月28日4.2.3特殊矩陣的壓縮對(duì)下三角部分以行為主序順序存儲(chǔ)到一個(gè)向量中去，在下三角中共有n*(n+1)/2個(gè)元素，設(shè)存儲(chǔ)到向量SA[n(n+1)/2]中，這樣，原矩陣下三角中的某一個(gè)元素aij則具體對(duì)應(yīng)一個(gè)sak，下面的問(wèn)題是要找到k與i、j之間的關(guān)系。

圖4-8對(duì)稱(chēng)矩陣

第三十八頁(yè)，共五十頁(yè)，2022年，8月28日4.2.3特殊矩陣的壓縮若i<j，則aij是上三角中的元素，因?yàn)閍ij=aji

，這樣，訪(fǎng)問(wèn)上三角中的元素aij時(shí)則去訪(fǎng)問(wèn)和它對(duì)應(yīng)的下三角中的aji即可，因此將上式中的行列下標(biāo)交換就是上三角中的元素在SA中的對(duì)應(yīng)關(guān)系：k=j*(j+1)/2+i(０≤k<n*(n+1)/2)綜上所述，對(duì)于對(duì)稱(chēng)矩陣中的任意元素aij，若令I(lǐng)=max(i,j)，J=min(i,j)，則將上面兩個(gè)式子綜合起來(lái)得到：第三十九頁(yè)，共五十頁(yè)，2022年，8月28日4.2.3特殊矩陣的壓縮2.三角矩陣的壓縮存儲(chǔ)形如圖4-10的矩陣稱(chēng)為三角矩陣，其中c為某個(gè)常數(shù)。其中(a)為上三角矩陣：主對(duì)角線(xiàn)以下均為同一個(gè)常數(shù)；(b)為下三角矩陣：主對(duì)角線(xiàn)以上均為同一個(gè)常數(shù)。三角矩陣中的重復(fù)元素c可共享一個(gè)存儲(chǔ)空間，其余的元素正好有n×(n+1)/2個(gè)，共存儲(chǔ)了n×(n+1)/2+1個(gè)元素，因此，三角矩陣可壓縮存儲(chǔ)到一維數(shù)組sa[n(n+1)/2+1]中，其中c存放在向量的最后一個(gè)分量中。（a）

上三角矩陣

（b）

下三角矩陣

第四十頁(yè)，共五十頁(yè)，2022年，8月28日4.2.3特殊矩陣的壓縮（1）上三角矩陣的壓縮對(duì)于上三角矩陣，以行優(yōu)先順序存儲(chǔ)上三角部分，最后存儲(chǔ)對(duì)角線(xiàn)下方的常量。第i行上，aij之前恰有j-i+1個(gè)元素(即aii，ai,i+1，…，ai,j-1)；所以，它是上三角存儲(chǔ)順序中的第

i×(2n-i+1)/2+j-i+1個(gè)元素，因此它在向量sa中的下標(biāo)為：k=i×(2n-i+1)/2+j-i。故aij(0≤i,j≤n-1)對(duì)應(yīng)存儲(chǔ)向量sa中的下標(biāo)k(0≤k≤n(n+1)/2)：第四十一頁(yè)，共五十頁(yè)，2022年，8月28日4.2.3特殊矩陣的壓縮與上三角矩陣類(lèi)似，按行優(yōu)先順序存儲(chǔ)。

sak(0≤k≤n(n+1)/2)與aij(0≤i，j≤n-1)的對(duì)應(yīng)關(guān)系為：

第四十二頁(yè)，共五十頁(yè)，2022年，8月28日4.2.3特殊矩陣的壓縮3.對(duì)角矩陣的壓縮存儲(chǔ)所有的非零元素集中在以主對(duì)角線(xiàn)為中心的帶狀區(qū)域中，即除了主對(duì)角線(xiàn)和主對(duì)角線(xiàn)相鄰兩側(cè)的若干條對(duì)角線(xiàn)上的元素之外，其余元素皆為零的矩陣為對(duì)角矩陣。對(duì)角矩陣又稱(chēng)為帶狀矩陣。圖4-13是一個(gè)三對(duì)角矩陣示意圖。

圖4-13對(duì)角矩陣示意圖

第四十三頁(yè)，共五十頁(yè)，2022年，8月28日4.2.3特殊矩陣的壓縮若以行為主序?qū)⑷龑?duì)角矩陣存儲(chǔ)到一個(gè)一維數(shù)組中，則需要3*n-2個(gè)存儲(chǔ)空間。假設(shè)存儲(chǔ)到向量SA[3*n-2]中，存儲(chǔ)順序如圖4-14所示。向量中的元素sak(0≤k≤3n-1)與aij(0≤i，j≤n-1)的對(duì)應(yīng)關(guān)系為：

圖4-14三對(duì)角矩陣壓縮存儲(chǔ)

第四十四頁(yè)，共五十頁(yè)，2022年，8月28日4.4應(yīng)用舉例分析例4.1

已知字符串：A=“anapple”，B=“otherhero”，C=“her”，求：

（1）concat(substr(A,1,2),B)。

（2）replace(A,substr(A,5,1),C)。

（3）index(A,C)和index(B,C)。解：

（1）substr(A,1,2)的返回值為”an”，故concat(substr(A,1,2),B)的返回值為“anotherhero”。

（2）substr(A,5,1)的返回值為“p”，故replace(A,substr(A,5,1),C)的返回值為“anaherherle”。

（3）index(A,C)的返回值為0，index(B,C)的返回值為3。

第四十五頁(yè)，共五十頁(yè)，2022年，8月28日4.4應(yīng)用舉例分析例4.2

已知一個(gè)二維數(shù)組A，行下標(biāo)1≤i≤7，列下標(biāo)1≤j≤9，每個(gè)元素的長(zhǎng)度為2字節(jié)，從首地址200開(kāi)始連續(xù)存放在內(nèi)存中，該數(shù)組元素按行優(yōu)先存放，問(wèn)：