其他线性数据结构

其他线性数据结构第一页，共五十页，2022年，8月28日本章要点串、多维数组、特殊矩阵及稀疏矩阵的定义串、多维数组、特殊矩阵及稀疏矩阵的存储方式串、稀疏矩阵的基本操作第二页，共五十页，2022年，8月28日本章难点多维数组的顺序存储特殊矩阵的压缩存储稀疏矩阵的基本操作学习目标掌握串操作掌握多维数组的顺序存储掌握特殊矩阵的压缩存储掌握稀疏矩阵的基本操作第三页，共五十页，2022年，8月28日4.1串串是一种特殊的线性结构，它的数据元素仅由字符组成。第四页，共五十页，2022年，8月28日4.1.1串的定义和基本操作1.串的相关概念串(String)

串是由零个或多个字符组成的有限序列。一般记为S=“a1a2

…an”

(n≥0)。其中，S是串名，用单引号或双引号括起来的字符序列是串的值，ai(1≤i≤n)可以是字母、数字或其他字符。值得注意的是，引号本身不属于串。串的长度

串中字符的数目n。空串

长度为0的串。空格串

由一个或多个空格组成的串。需要注意的是，空格串不是空串，空格串的长度由其中空格的数目决定，而空串的长度为0。第五页，共五十页，2022年，8月28日4.1.1串的定义和基本操作串的子串、主串串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。空串是任意串的子串，任意串是其自身的子串。字符在串中的位置

字符在序列中的序号。子串在主串中的位置

以子串的第一个字符在主串中的位置来表示。两串相等当两个串的长度相等，并且各个对应位置上的字符都相等时，称这两个串相等。例如上例中的C、D看起来相似，但不相等。

第六页，共五十页，2022年，8月28日4.1.1串的定义和基本操作2.串的基本操作

（1）=赋值操作赋值号左边必须是串变量，右边可以是串变量、串常量或运算值是串值的表达式。（2判两串是否相等的函数。若S和T相等，则返回函数值“true”或1；否则返回函数值“false”或0。S和T可以是空串，也可以是非空串。（3）求串的长度的函数。函数值为串S中字符的个数。（4）联接操作。设S，T1，T2都是串变量，联接操作就是将串T1和串T2放入S中。S串中的前一段和串T1相等，S串中的后一段和串T2相等。CONCAT(S,T1,T2)与CONCAT(S,T2,T1)的结果不一样。联接操作还可推广至n个串变量。（5）SUBSTR(S,i,j)求子串函数。当1≤i≤STRLEN(S)且0≤j≤STRLEN(S)-i+1，返回函数值是S的一个子串，即从串S中第i个字符起，长度为j的字符序列。否则返回一个特殊的值。（6）INDEX(S,T)定位函数。若在主串S中存在和T相等的子串，则函数值返回在S中出现的第一个和T相等的子串在S中的位置，否则函数值为零。注意T不能是空串。第七页，共五十页，2022年，8月28日4.1.1串的定义和基本操作（7）置换操作。操作结果是以串V替换所有在串S中出现的和串T相等的不重叠的子串。（8）插入操作。当1≤pos≤STRLEN(S)+1时，在串S的第pos个字符之前插入串T。（9）删除操作。当1≤pos≤STRLEN(S)且0≤len≤STRLEN(S)-pos+1时，从串S中删去第pos字符起、长度为len的子串。（10）串复制（11）输出串第八页，共五十页，2022年，8月28日1、串赋值运算voidAssign(SqString&s,chart[]) { inti=0; while(t[i]!='\0') {s.ch[i]=t[i];i++; } s.len=i;}2、串复制运算voidStrCopy(SqString&s,SqStringt) { inti; for(i=0;i<t.len;i++) s.ch[i]=t.ch[i]; s.len=t.len;}第九页，共五十页，2022年，8月28日3、求串长运算intStrLength(SqStrings) { return(s.len);}4、判断串相等运算intStrEqual(SqStrings,SqStringt) { inti=0; if(s.len!=t.len) /*串长不同时返回0*/ return(0); else {for(i=0;i<s.len;i++) if(s.ch[i]!=t.ch[i])/*有一个对应字符不同时返回0*/ return(0); return(1); }}第十页，共五十页，2022年，8月28日5、串连接运算SqStringConcat(SqStrings,SqStringt) { SqStringr; inti,j; for(i=0;i<s.len;i++) /*将s复制到r*/ r.ch[i]=s.ch[i]; for(j=0;j<t.len;j++) /*将t复制到r*/ r.ch[s.len+j]=t.ch[j]; r.len=i+j; return(r); /*返回r*/}第十一页，共五十页，2022年，8月28日6、求子串运算SqStringSubStr(SqStrings,inti,intj) { SqStringt; intk; if(i<1||i>s.len||j<1||i+j>s.len+1) t.len=0; /*参数错误时返回空串*/ else { for(k=i-1;k<i+j;k++) t.ch[k-i+1]=s.ch[k]; t.len=j; } return(t);}第十二页，共五十页，2022年，8月28日7、查找子串位置运算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])/*对应字符相同时,继续比较下一对字符*/ { i++;j++; } else *否则,主子串指针回溯重新开始下一次匹配*/ { i=i-j+1;j=0; } } if(j>=t.len) k=i-t.len+1;/*求出第一个字符的位置*/ else k=-1; /*置特殊值-1*/ return(k);}第十三页，共五十页，2022年，8月28日8、子串插入运算intInsStr(SqString&s,inti,SqStringt) { intj; if(i>s.len+1) return(0); /*位置参数值错误*/ 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个位置*/ for(j=0;j<t.len;j++) s.ch[i+j-1]=t.ch[j]; s.len=s.len+t.len; /*修改s串长度*/ return(1); }}第十四页，共五十页，2022年，8月28日9、子串删除运算intDelStr(SqString&s,inti,intj) { intk; if(i<1||i>s.len||j<1||i+j>s.len+1) return(0); /*位置参数值错误*/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的长度*/ return(1); }}第十五页，共五十页，2022年，8月28日10、子串替换运算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、输出串运算voidDispStr(SqStrings) { inti; for(i=0;i<s.len;i++) printf("%c",s.ch[i]); printf("\n");}第十六页，共五十页，2022年，8月28日串的链式存储及基本运算串的定义：typedefstructnode{ chardata; /*存放字符*/ structnode*next; /*指针域*/}LinkString;第十七页，共五十页，2022年，8月28日1、串赋值运算voidAssign(LinkString*&s,chart[]){ inti=0; LinkString*q,*tc; s=(LinkString*)malloc(sizeof(LinkString));/*建立头结点*/ s->next=NULL; tc=s; /*tc指向s串的尾结点*/ while(t[i]!='\0') { q=(LinkString*)malloc(sizeof(LinkString)); q->data=t[i]; tc->next=q;tc=q; i++; } tc->next=NULL; /*终端结点的next置NULL*/}第十八页，共五十页，2022年，8月28日2、串复制运算voidStrCopy(LinkString*&s,LinkString*t) /*t=>s*/{ LinkString*p=t->next,*q,*tc; s=(LinkString*)malloc(sizeof(LinkString));/*建立头结点*/ s->next=NULL; tc=s; /*tc指向s串的尾结点*/ while(p!=NULL) /*复制t的所有结点*/ { q=(LinkString*)malloc(sizeof(LinkString)); q->data=p->data; tc->next=q;tc=q; p=p->next;} tc->next=NULL; /*终端结点的next置NULL*/}第十九页，共五十页，2022年，8月28日3、求串长运算intStrLength(LinkString*s){ intn=0; LinkString*p=s->next; while(p!=NULL) /*扫描串s的所有结点*/ { n++;p=p->next; }return(n);}第二十页，共五十页，2022年，8月28日4、判断串相等运算intStrEqual(LinkString*s,LinkString*t){ LinkString*p=s->next,*q=t->next; while(p!=NULL&&q!=NULL)/*比较两串的当前结点*/ {if(p->data!=q->data)/*data域不等时返回0*/ return(0);p=p->next;q=q->next; } if(p!=NULL||q!=NULL) /*两串长度不等时返回0*/ return(0); return(1);}第二十一页，共五十页，2022年，8月28日5、串连接运算LinkString*Concat(LinkString*s,LinkString*t){ LinkString*p=s->next,*q,*tc,*str;str=(LinkString*)malloc(sizeof(LinkString));/*建立头结点*/ str->next=NULL; tc=str; /*tc总是指向新链表的尾结点*/ while(p!=NULL) /*将s串复制给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串复制给str*/ { q=(LinkString*)malloc(sizeof(LinkString)); q->data=p->data; tc->next=q;tc=q; p=p->next;}tc->next=NULL;return(str);}第二十二页，共五十页，2022年，8月28日6、求子串运算LinkString*SubStr(LinkString*s,inti,intj){ intk=1; LinkString*p=s->next,*q,*tc,*str;str=(LinkString*)malloc(sizeof(LinkString));/*建立头结点*/ str->next=NULL; tc=str; /*tc总是指向新链表的尾结点*/ while(k<i&&p!=NULL) { p=p->next;k++; } if(p!=NULL) { k=1; while(k<=j&&p!=NULL) /*复制j个结点*/ { q=(LinkString*)malloc(sizeof(LinkString)); q->data=p->data; tc->next=q;tc=q; p=p->next; k++;} tc->next=NULL; } return(str);}第二十三页，共五十页，2022年，8月28日7、查找子串运算intIndex(LinkString*s,LinkString*t){ LinkString*p=s->next,*p1,*q,*q1; inti=0; while(p!=NULL) /*循环扫描s的每个结点*/ {q=t->next; /*子串总是从第一个字符开始比较*/if(p->data==q->data)/*判定两串当前字符相等*/{/*若首字符相同,则判定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*/}第二十四页，共五十页，2022年，8月28日8、子串插入运算intInsStr(LinkString*&s,inti,LinkString*t){ intk; LinkString*q=s->next,*p,*str; StrCopy(str,t); /*将t复制到str*/ p=str;str=str->next; free(p); /*删除str的头结点*/ for(k=1;k<i;k++) /*在s中找到第i-1个结点,由p指向它,q指向下一个结点*/ {if(q==NULL) /*位置参数i错误*/ return(0); p=q; q=q->next; } p->next=str; /*将str链表链接到*p之后*/ while(str->next!=NULL) /*由str指向尾结点*/ str=str->next; str->next=q; /*将*q链接到*str之后*/ return(1);}第二十五页，共五十页，2022年，8月28日9、子串删除运算intDelStr(LinkString*&s,inti,intj){ intk; LinkString*q=s->next,*p,*t; for(k=1;k<i;k++) /*在s中找到第i-1个结点,由p指向它,q指向下一个结点*/ {if(q==NULL) /*位置参数i错误*/ return(0);p=q;q=q->next; }for(k=1;k<=j;k++) /*删除*p之后的j个结点,并由q指向下一个结点*/ { if(q==NULL) /*长度参数j错误*/return(0); t=q; q=q->next; free(t); } p->next=q; return(1);}第二十六页，共五十页，2022年，8月28日10、子串替换运算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);}第二十七页，共五十页，2022年，8月28日11、输出子串运算voidDispStr(LinkString*s){ LinkString*p=s->next; while(p!=NULL) {printf("%c",p->data);p=p->next; } printf("\n");}第二十八页，共五十页，2022年，8月28日4.2多维数组4.2.1多维数组的定义及存储结构1.多维数组的定义数组是由下标和值组成的序对的集合。在数组中，一旦给定下标，都存在一个与其相对应的值，这个值就称为数组元素。数组可以看作是广义的线性表，即多维数组对应的线性表中的数据元素本身又是一个线性表。数组一旦被定义，它的维数和维界就不再改变。因此，数组的运算通常只有两种基本运算：（1）取值操作：给定一组下标，存取相应的数据元素。（2）赋值操作：给定一组下标，存储/修改相应数据元素。第二十九页，共五十页，2022年，8月28日4.2.1多维数组的定义及存储结构

2.多维数组的存储结构数组一般不做插入和删除操作，也就是说，数组一旦建立，其结构中的元素个数和元素之间的关系就不再发生变化，因此数组可以采用向量(顺序)存储结构来存放。在进行顺序存储时存放次序有两种规则：

（1）先行后列顺序，或者称为行优先顺序，其分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。

（2）先列后行顺序，或者称为列优先顺序，其分配的规律是：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。第三十页，共五十页，2022年，8月28日4.2.1多维数组的定义及存储结构对于数组，一旦确定了它的维数和各维的长度，便可以为它分配存储空间。反之，若已知一组下标也可求出对应数据元素的存储位置。例如，假设，一个二维数组A(m×n)按行优先顺序存储在向量中，其第一个元素的序号为0，且已知某个数据元素的下标i,j(0≤i≤m-1，0≤j≤n-1)，则可用下列公式计算该数据元素在向量中的序号index(ai,j)：

index(ai,j)=n×i+j+1若已知数组A(m×n)中第一个元素的存储地址LOC(a0,0)，并已知某个数据元素的下标i,j(0≤i≤m-1，0≤j≤n-1)，及每个数据元素占用的存储单元数为b，则该数据元素的存储地址：

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

第三十一页，共五十页，2022年，8月28日4.2.2稀疏矩阵及压缩1.稀疏矩阵的压缩存储若一个矩阵中非零元素的个数远远小于矩阵元素的总数，则称为稀疏矩阵。对于稀疏矩阵，只须考虑非零元素的存储。每一个非零元素aij，可以用一个三元组(i,j,v)来惟一确定。其中，i，j是非零元素在矩阵中对应的行号和列号，v是非零元素的值。将稀疏矩阵中的非零元素的三元组按行优先的顺序排列则得到一个元素类型是三元组的线性表，称为三元组表。三元组表是稀疏矩阵的一种顺序存储结构。以下的讨论中均假定三元组是按行优先的顺序排列的。稀疏矩阵的三元组存储的数据类型描述如下：第三十二页，共五十页，2022年，8月28日4.2.2稀疏矩阵及压缩#defineMAXLEN40#defineDATATYPE1inttypedefstruct{inti,j;/*非零元素的行号和列号*/DATATYPE1v;/*非零元素的值*/}NODE;typedefstruct{intm,n,t;/*稀疏矩阵的行数和列数及非零元素的个数*/

NODEdata［MAXLEN］;/*三元组线性表*/}SPMATRIX;

三元组存储结构因以行优先存放，存在以下的规律：元组中的第一列按行号的顺序由小到大排列，元组中的第二列是列号，列号在行号相同时也是由小到大排列。第三十三页，共五十页，2022年，8月28日4.2.2稀疏矩阵及压缩2.稀疏矩阵的转置存储矩阵转置就是把矩阵元素的行和列对换，一个m行n列的矩阵转置以后变成一个n行m列的矩阵。例如，矩阵M转置后得到矩阵N，在矩阵M中位于i,j上的元素，转置后对应于矩阵N中j,i上的元素，即Mi,j=Nj,i，其中0≤i≤m-1，0≤j≤n-1。以下给出的转置算法都是在矩阵的三元组存储结构上实现的（1）一般插入算法算法的思路是：对a.data扫描一遍，扫描过程中依次取出a.data中的每一个三元组元素，将对应的行号和列号对换，放入b.data中。为保证b.data具有三元组存放元素的规律，需和前面的元素按行及列比较之后，才可插在对应位置上。此算法在移动元素上花去了大量的时间。第三十四页，共五十页，2022年，8月28日4.2.2稀疏矩阵及压缩（2）transpose算法该算法的思路是：考虑到b.data中的行就是a.data中的列，要想得到b.data中行号为x的三元组元素，可对a.data扫描一遍，找出a.data中列号为x的元素即可。以下就是中文描述的transpose算法。①对a.data扫描第1遍，得到a.data[p].j=1(0≤p≤a.t-1)的元素，它们应该就是b.data中行号为1的元素，而且根据规律，依次得到的这些元素的行号一定是从小到大排好序的，所以把这些三元组元素的i,j对换放到b.data中，b.data行号为1的元素就放到位了。②对a.data扫描第2遍，得到a.data［p］.j=2(1≤p≤a.t)的元素，把这些三元组元素的i,j对换放到b.data中，b.data行号为2的元素就放到位了。③重复①、②的方法，对a.data扫描a.n遍，数组转置完成。

第三十五页，共五十页，2022年，8月28日4.2.2稀疏矩阵及压缩voidtranspose(SPMATRIXb,SPMATRIXa){intp,q,col;b.m=a.n;/*行列数互换*/b.n=a.m;b.t=a.t;/*非零元素个数不变*/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++;}}}

第三十六页，共五十页，2022年，8月28日4.2.3特殊矩阵的压缩1.对称矩阵的压缩存储对称矩阵的特点是：在一个n阶方阵中，有aij=aji

，其中0≤i,j≤n-1，如图4-8所示。对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可，比如，我们只存储下三角中的元素aij，其特点是j≤i且0≤i≤n-1，对于上三角中的元素aij

，它和对应的aji相等，因此当访问的元素在上三角时，直接去访问和它对应的下三角元素即可，这样，原来需要n*n个存储单元，现在只需要n*(n+1)/2个存储单元了。第三十七页，共五十页，2022年，8月28日4.2.3特殊矩阵的压缩对下三角部分以行为主序顺序存储到一个向量中去，在下三角中共有n*(n+1)/2个元素，设存储到向量SA[n(n+1)/2]中，这样，原矩阵下三角中的某一个元素aij则具体对应一个sak，下面的问题是要找到k与i、j之间的关系。

图4-8对称矩阵

第三十八页，共五十页，2022年，8月28日4.2.3特殊矩阵的压缩若i<j，则aij是上三角中的元素，因为aij=aji

，这样，访问上三角中的元素aij时则去访问和它对应的下三角中的aji即可，因此将上式中的行列下标交换就是上三角中的元素在SA中的对应关系：k=j*(j+1)/2+i(０≤k<n*(n+1)/2)综上所述，对于对称矩阵中的任意元素aij，若令I=max(i,j)，J=min(i,j)，则将上面两个式子综合起来得到：第三十九页，共五十页，2022年，8月28日4.2.3特殊矩阵的压缩2.三角矩阵的压缩存储形如图4-10的矩阵称为三角矩阵，其中c为某个常数。其中(a)为上三角矩阵：主对角线以下均为同一个常数；(b)为下三角矩阵：主对角线以上均为同一个常数。三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)/2个，共存储了n×(n+1)/2+1个元素，因此，三角矩阵可压缩存储到一维数组sa[n(n+1)/2+1]中，其中c存放在向量的最后一个分量中。（a）

上三角矩阵

（b）

下三角矩阵

第四十页，共五十页，2022年，8月28日4.2.3特殊矩阵的压缩（1）上三角矩阵的压缩对于上三角矩阵，以行优先顺序存储上三角部分，最后存储对角线下方的常量。第i行上，aij之前恰有j-i+1个元素(即aii，ai,i+1，…，ai,j-1)；所以，它是上三角存储顺序中的第

i×(2n-i+1)/2+j-i+1个元素，因此它在向量sa中的下标为：k=i×(2n-i+1)/2+j-i。故aij(0≤i,j≤n-1)对应存储向量sa中的下标k(0≤k≤n(n+1)/2)：第四十一页，共五十页，2022年，8月28日4.2.3特殊矩阵的压缩与上三角矩阵类似，按行优先顺序存储。

sak(0≤k≤n(n+1)/2)与aij(0≤i，j≤n-1)的对应关系为：

第四十二页，共五十页，2022年，8月28日4.2.3特殊矩阵的压缩3.对角矩阵的压缩存储所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零的矩阵为对角矩阵。对角矩阵又称为带状矩阵。图4-13是一个三对角矩阵示意图。

图4-13对角矩阵示意图

第四十三页，共五十页，2022年，8月28日4.2.3特殊矩阵的压缩若以行为主序将三对角矩阵存储到一个一维数组中，则需要3*n-2个存储空间。假设存储到向量SA[3*n-2]中，存储顺序如图4-14所示。向量中的元素sak(0≤k≤3n-1)与aij(0≤i，j≤n-1)的对应关系为：

图4-14三对角矩阵压缩存储

第四十四页，共五十页，2022年，8月28日4.4应用举例分析例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。

第四十五页，共五十页，2022年，8月28日4.4应用举例分析例4.2

已知一个二维数组A，行下标1≤i≤7，列下标1≤j≤9，每个元素的长度为2字节，从首地址200开始连续存放在内存中，该数组元素按行优先存放，问：