kl800.com省心范文网

第4章 其他线性数据结构_图文

本章要点
? ?

?

串、多维数组、特殊矩阵及稀疏矩阵的定义 串、多维数组、特殊矩阵及稀疏矩阵的存储方 式 串、稀疏矩阵的基本操作

本章难点
? ? ?

多维数组的顺序存储 特殊矩阵的压缩存储 稀疏矩阵的基本操作

学习目标
?

?
? ?

掌握串操作 掌握多维数组的顺序存储 掌握特殊矩阵的压缩存储 掌握稀疏矩阵的基本操作

4.1 串
?

串是一种特殊的线性结构,它的数据元素仅由 字符组成。

4.1.1 串的定义和基本操作
1. 串的相关概念
?

? ? ?

串(String) 串是由零个或多个字符组成的有限序 列。一般记为S = “a1 a2 …an” (n ≥ 0)。其中,S 是串名,用单引号或双引号括起来的字符序列是串 的值,ai (1 ≤ i ≤ n)可以是字母、数字或其他字 符。值得注意的是,引号本身不属于串。 串的长度 串中字符的数目n。 空串 长度为0的串。 空格串 由一个或多个空格组成的串。需要注意的 是,空格串不是空串,空格串的长度由其中空格的 数目决定,而空串的长度为0。

4.1.1 串的定义和基本操作
?

? ?

?

串的子串、主串 串中任意个连续的字符组成的子 序列称为该串的子串,包含子串的串相应地称为主 串。空串是任意串的子串,任意串是其自身的子串。 字符在串中的位置 字符在序列中的序号。 子串在主串中的位置 以子串的第一个字符在主串 中的位置来表示。 两串相等 当两个串的长度相等,并且各个对应位 置上的字符都相等时,称这两个串相等。例如上例 中的C、D看起来相似,但不相等。

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不能是空串。

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)输出串

?
? ? ?

?
? ? ? ? ? ? ? ? ? ? ? ?

?
?

1、串赋值运算 void Assign(SqString &s,char t[]) { int i=0; while (t[i]!='\0') { s.ch[i]=t[i]; i++; } s.len=i; } 2、串复制运算 void StrCopy(SqString &s,SqString t) { int i; for (i=0;i<t.len;i++) s.ch[i]=t.ch[i]; s.len=t.len; }

?
? ? ? ? ? ? ? ? ? ? ? ?

?
? ?

?
? ?

3、求串长运算 int StrLength(SqString s) { return(s.len); } 4、判断串相等运算 int StrEqual(SqString s,SqString t) { int i=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); } }

? ? ? ? ? ? ? ? ? ? ?

?

5、串连接运算 SqString Concat(SqString s,SqString t) { SqString r; int i,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*/ }

? ?

?
? ? ?

?
? ? ?

?
? ? ? ?

6、求子串运算 SqString SubStr(SqString s,int i,int j) { SqString t; int k; 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); }

?
? ? ? ? ? ? ? ?

?
? ? ? ?

?
? ? ? ? ? ?

7、查找子串位置运算 int Index(SqString s,SqString t) { int i=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); }

?
? ? ?

?
? ? ?

?
? ? ? ? ? ? ?

8、子串插入运算 int InsStr(SqString &s,int i,SqString t) { int j; 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); } }

?
? ? ? ? ? ?

?
? ? ? ? ?

?

9、子串删除运算 int DelStr(SqString &s,int i,int j) { int k; 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); } }

?
? ? ?

?
? ? ? ? ? ? ? ? ? ? ? ?

?
?

10、子串替换运算 SqString RepStrAll(SqString s,SqString s1,SqString s2) { int i; i=Index(s,s1); while (i>=0) { DelStr(s,i,s1.len); /*删除*/ InsStr(s,i,s2); /*插入*/ i=Index(s,s1); } return(s); } 11、输出串运算 void DispStr(SqString s) { int i; for (i=0;i<s.len;i++) printf("%c",s.ch[i]); printf("\n");}

4.1.3串的链式存储及基本运算
? ? ? ? ? ?

串的定义: typedef struct node { char data; struct node *next; } LinkString;

/*存放字符*/ /*指针域*/

? ? ? ? ? ? ? ? ? ? ? ? ?

?
? ? ?

1、串赋值运算 void Assign(LinkString *&s,char t[]) { int i=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*/ }

?
? ? ?

?
? ? ? ? ? ? ? ? ? ? ?

2、串复制运算 void StrCopy(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*/ }

?
? ? ? ?

?
? ? ? ? ?

3、求串长运算 int StrLength(LinkString *s) { int n=0; LinkString *p=s->next; while (p!=NULL) /*扫描串s的所有结点*/ { n++;p=p->next; } return(n); }

?
? ? ? ? ? ? ? ? ? ? ? ?

4、判断串相等运算 int StrEqual(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); }

?
? ? ? ? ? ? ? ? ? ? ? ?

?
? ? ?

?
? ?

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);}

? ?

?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

6、求子串运算 LinkString *SubStr(LinkString *s,int i,int j) { int k=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);}

?
? ? ?

?
? ? ?

?
? ? ? ? ? ? ? ?

7、查找子串运算 int Index(LinkString *s,LinkString *t) { LinkString *p=s->next,*p1,*q,*q1; int i=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*/ }

? ?

?
? ? ?

?
? ? ? ? ? ? ? ? ? ? ?

8、子串插入运算 int InsStr(LinkString *&s,int i,LinkString *t) { int k; 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); }

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

?
? ? ? ?

9、子串删除运算 int DelStr(LinkString *&s,int i,int j) { int k; 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); }

? ? ? ?

?
? ?

?
? ? ? ? ?

10、子串替换运算 LinkString *RepStrAll(LinkString *s,LinkString *s1,LinkString *s2) { int i; 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); }

? ? ? ? ? ? ?

?
? ?

?

11、输出子串运算 void DispStr(LinkString *s) { LinkString *p=s->next; while (p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n"); }

4.2 多维数组
4.2.1 多维数组的定义及存储结构
1. 多维数组的定义
?

? ?

数组是由下标和值组成的序对的集合。在数组中,一旦 给定下标,都存在一个与其相对应的值,这个值就称为 数组元素。 数组可以看作是广义的线性表,即多维数组对应的线性 表中的数据元素本身又是一个线性表。 数组一旦被定义,它的维数和维界就不再改变。因此, 数组的运算通常只有两种基本运算:

(1)取值操作:给定一组下标,存取相应的数据元素。 (2)赋值操作:给定一组下标,存储/修改相应数据元素。

4.2.1 多维数组的定义及存储结构
2. 多维数组的存储结构
?

?

数组一般不做插入和删除操作,也就是说,数组一旦建立, 其结构中的元素个数和元素之间的关系就不再发生变化,因 此数组可以采用向量(顺序)存储结构来存放。 在进行顺序存储时存放次序有两种规则: (1)先行后列顺序,或者称为行优先顺序,其分配规律是: 最右边的下标先变化,即最右下标从小到大,循环一遍后, 右边第二个下标再变,…,从右向左,最后是左下标。 ( 2 )先列后行顺序,或者称为列优先顺序,其分配的规律 是:最左边的下标先变化,即最左下标从小到大,循环一遍 后,左边第二个下标再变,…,从左向右,最后是右下标。

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

4.2.2 稀疏矩阵及压缩
1. 稀疏矩阵的压缩存储
?

?

若一个矩阵中非零元素的个数远远小于矩阵元素的总数,则 称为稀疏矩阵。对于稀疏矩阵,只须考虑非零元素的存储。 每一个非零元素 aij,可以用一个三元组 (i,j,v) 来惟一确定。 其中, i , j 是非零元素在矩阵中对应的行号和列号, v 是非 零元素的值。 将稀疏矩阵中的非零元素的三元组按行优先的顺序排列则得 到一个元素类型是三元组的线性表,称为三元组表。三元组 表是稀疏矩阵的一种顺序存储结构。以下的讨论中均假定三 元组是按行优先的顺序排列的。稀疏矩阵的三元组存储的数 据类型描述如下:

4.2.2 稀疏矩阵及压缩
#define MAXLEN 40 #define DATATYPE1 int typedef struct { int i, j; /* 非零元素的行号和列号*/ DATATYPE1 v; /* 非零元素的值*/ }NODE; typedef struct { int m, n, t; /*稀疏矩阵的行数和列数及非零元素的个数*/ NODE data[MAXLEN]; /*三元组线性表*/ }SPMATRIX;

?

三元组存储结构因以行优先存放,存在以下的规律: 元组中的第一列按行号的顺序由小到大排列,元组中 的第二列是列号,列号在行号相同时也是由小到大排 列。

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具有三元组存放元素的规律, 需和前面的元素按行及列比较之后,才可插在对应位置上。 此算法在移动元素上花去了大量的时间。
?

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遍,数组转置完成。

4.2.2 稀疏矩阵及压缩
void transpose(SPMATRIX b, SPMATRIX a) { int p, 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++; } } }

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个存储 单元了。

4.2.3 特殊矩阵的压缩
?

对下三角部分以行为主序顺序存储到一个向量中去, 在下三角中共有n*(n+1)/2个元素,设存储到向量 SA[n(n+1)/2]中,这样,原矩阵下三角中的某一个元 素aij则具体对应一个sak,下面的问题是要找到k与i、j 之间的关系。
? a 00 ? a ? 10 ? a 20 ? ? ? ?a n ?1, 0 ? a10 a11 a 21 ? a n ?1,1 a 20 a 21 a 22 ? a n ?1, 2 a n ?1, 0 ? ? a n ?1,1 ? ? ? a n ?1, 2 ? ? ? ? ? ? a n ?1,n ?1 ? ? ?

图4-8 对称矩阵

4.2.3 特殊矩阵的压缩
?

?

若i<j,则aij是上三角中的元素,因为aij=aji ,这样, 访问上三角中的元素aij时则去访问和它对应的下三角 中的aji即可,因此将上式中的行列下标交换就是上三 角 中 的 元 素 在 SA 中 的 对 应 关 系 : k=j*(j+1)/2+i (0≤k<n*(n+1)/2 ) 综 上 所 述 , 对 于 对 称 矩 阵 中 的 任 意 元 素 aij , 若 令 I=max(i,j),J=min(i,j),则将上面两个式子综合起 来得到:
k ? I ? ( I ? 1) / 2 ? J I ? max( i, j ), J ? min(i, j )

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 00 ? c ? ? c ? ? ? ? c ? a01 a11 c ? c a 02 ? a 0,n ? 2 a 12 ? a1,n ? 2 a 22 ? a 2,n ? 2 ? c ? c ? c a 0,n ?1 ? a1,n ?1 ? ? a 2,n ?1 ? ? ? ? a n ?1,n ?1 ? ? ? a00 ? a ? 10 ? a 20 ? ? ? ?a n ?1, 0 ? c a11 a 21 ? a n ?1,1 c c a 22 ? ? ? ? ? c c c ? ? c ? ? c ? ? ? ? a n ?1,n ?1 ? ? c

a n ?1, 2 ? a n ?1,n ?2

(a) 上三角矩阵

(b) 下三角矩阵

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):
? i ? (2n - i ? 1)/2 ? j - i k ?? ? n ? (n ? 1)/2 当i ? j 当i ? j

4.2.3 特殊矩阵的压缩
?

与上三角矩阵类似,按行优先顺序存储。 sa k(0≤k≤n (n+1)/2) 与aij (0≤i,j≤n-1)的对应关系为:
? i ? (i ? 1)/2 ? j k?? ? n ? (n ? 1)/2 当i ? j 当i ? j

4.2.3 特殊矩阵的压缩
3. 对角矩阵的压缩存储
?

所有的非零元素集中在以主对角线为中心的带状区域中, 即除了主对角线和主对角线相邻两侧的若干条对角线上的 元素之外,其余元素皆为零的矩阵为对角矩阵。对角矩阵 又称为带状矩阵。图4-13是一个三对角矩阵示意图。
?a 00 ? ?a 10 ? ? ? ? ? ? ? ? a 01 a11 a 21 a12 a 22 ? a 23 ? a n ? 2 , n ?3 ? a n ? 2,n ? 2 a n ?1,n ? 2

0

0

? ? ? ? ? ? ? a n ? 2,n ?1 ? ? a n ?1,n ?1 ? ?

图4-13 对角矩阵示意图

4.2.3 特殊矩阵的压缩
?

?

若以行为主序将三对角矩阵存储到一个一维数组中,则需 要3*n-2个存储空间。假设存储到向量SA[3*n-2]中,存储 顺序如图4-14所示。 向量中的元素sa k(0≤k≤3n-1) 与aij (0≤i,j≤n-1)的 对应关系为:
?2 ? i ? j k ?? ?0 | i ? j |? 1 其它情况

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

4.4 应用举例分析
?

例 4.1 已知字符串: A=“an apple”,B=“other hero” ,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)的返回值为“another hero”。 (2)substr(A,5,1)的返回值为“p”,故 replace(A,substr(A,5,1),C)的返回值为“an aherherle”。 (3)index(A,C)的返回值为0,index(B,C)的返回值为3。

4.4 应用举例分析
?

?

例 4.2 已知一个二维数组 A ,行下标 1≤i≤7 ,列下标 1≤j≤9 ,每个元素的长度为 2 字节,从首地址 200 开始 连续存放在内存中,该数组元素按行优先存放,问: 元素a54的存储地址是多少? 解:该二维数组是用顺序存储结构存放元素。A数组 共有7行,9列。元素的下标从1开始。对于aij (1≤i≤m,1≤j≤n)而言,其在向量中的存储序号为, index(ai,j)=(i-1)×n+j,则其LOC(ai,j)= LOC(a11) + (index(ai,j) – 1)×2= LOC(a11)+ ((i-1)×n+j-1)×2,套用 此公式,求得结果:LOC(a54)=200 + (4×9+4-1)×2= 278。

4.4 应用举例分析
?

?

例4.3 已知n阶下三角矩阵A,按照压缩存储的思想,可 以将其主对角线以下所有元素(包括主对角线上元素)依 次存放于一维数组B中。请写出从第一列开始以列序为主 序分配方式时在B中确定元素aij(0≤i≤n-1,0≤j≤n-1)的存 放位置的公式。 解:如果aij按列存储,则其第0列需要存储n个元素,第1 列需要存储n-1个,…,第j列需要存储(n-j)个元素。n个 元素那么它的前面有j列,共有元素: (n-0)+(n-1)+(n-2)+…+(n-j+1)=j×(2n-j+1)/2 而它又是所在列的第i行,因此在它前的元素个数还得加 上i+1。因此它在一维数组B中的存储顺序为: j × (2n-j+1)/2 + i + 1

本章小结
1.串是由零个或多个字符组成的有限序列。串的基本操作有
以下九种:赋值操作=、判两串是否相等操作EQUAL(S,T)、 求串的长度STRLEN(S)、联接操作CONCAT(S,T1,T2)、求子 串操作SUBSTR(S, i , j )、定位操作INDEX(S,T)、置换 操作REPLACE(S,T,V)、插入操作INSERT(S,pos,T)、删除 操作DELETE(S,pos,len)。串的存储方式有两种:顺序存 储结构和串的堆分配存储结构。两种存储方式上实现各个 操作的方法不同。

本章小结
2. 数组是由下标和值组成的序对的集合。数组只有两种基 本运算:取值操作和赋值操作。由于数组采用顺序存储方 式,故一旦确定了它的维数和各维的长度,便可以为它分 配存储空间。反之,若已知一组下标也可求出对应数据元 素的存储位置。不过采用行优先次序和列优先次序的计算 公式是不同的。 多维数组有一些特殊形式的数组,如稀疏矩阵、三角矩阵、 对角矩阵等。这些数组阶数很高且含有许多零元素或值相 同的元素,为了节省存储空间,可以对这类矩阵进行压缩 存储,即对零元素可以不分配空间,而对多个相同值的元 素只分配一个存储空间。稀疏矩阵采用了三元组进行压缩 存储;而对称矩阵、三角矩阵、对角矩阵等特殊矩阵则根 据自身形式的特点进行压缩存储。另外在三元组上实现稀 疏矩阵的转置也是很重要的知识点。

本章小结
3.广义表是n(n≥0)个数据元素的有序序列,是线形表的
推广。广义表有取头操作、取尾操作、求表的长度和求表 的深度共四个基本操作。由于广义表中的数据元素可以具 有不同的结构,故通常都采用链式的存储结构来存储广义 表。按结点形式的不同,广义表的链式存储结构又可以分 为不同的两种存储方式。一种称为头尾表示法,另一种称 为孩子兄弟表示法。


第4章 其他线性数据结构.pdf

第4章 其他线性数据结构 - 第四章 其他线性数据结构 一、串 1、串的概念及基

第4章 数据结构_图文.ppt

第4章 数据结构 - 第4章 数据结构 10 65 1.1 基本数据结构与算法 1.2 线性表 865 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 内部排序 姓名 学号 ...

第四章 数据结构_图文.ppt

数据结构 合肥工业大学 数据结构课程的基本结构: 目 录 第1章 绪论 第2章 线性表 第3章 栈和队列 第 4章 串第5章 数组和广义表 第6章 树和二叉树 第 ...

第4章 数据结构-广义线性表._图文.ppt

第4章 数据结构-广义线性表. - 清华大学出版社 数据结构(C++版) 第四章 广义线性表 本章的基本内容是: 数组的逻辑结构特征 数组的存储方式及寻址方法 特殊...

第4章 算法与数据结构_图文.ppt

第4章 算法与数据结构 - 第4章 算法与数据结构 本章简介 ? 在编写计算机程

四章节数据结构_图文.ppt

四章节数据结构 - 第四章 数据结构 主要内容 4.1 基本数据结构与算法 4.2 线性表 4.3 栈和队列 4.4 树和二叉树 4.5 查找 4.6 内部排序 4.1 基本数据结构与算...

大学计算机基础第4章数据结构资料_图文.ppt

大学计算机基础第4章数据结构资料 - 第4章 数据结构 HEU 主要内容 数据结构概述 线性表及其操作 树与二叉树 数据结构 数据结构概述 例1 : 080611825196101...

数据结构(严蔚敏)课件第4章_图文.ppt

数据结构(严蔚敏)课件第4章 - 第四章 串 【课前思考】 课前思考】 1. 串就是线性表 的结论是否正确? 串就是线性表的结论是否正确 串就是线性表 的结论...

大学计算机基础--第4章 数据结构基础1_图文.ppt

大学计算机基础--第4章 数据结构基础1 - 软件工程基础___软件的生命期 软

数据结构与算法分析课件第4章_图文.ppt

数据结构与算法分析课件第4章 - 数据结构与算法分析 A Practical I

四章节数据结构-PPT课件_图文.ppt

四章节数据结构-PPT课件 - 第四章 数据结构 主要内容 4.1 基本数据结构与算法 4.2 线性表 4.3 栈和队列 4.4 树和二叉树 4.5 查找 4.6 内部排序 4.1 基本...

第4章计算机专业基础知识(7数据结构)_图文.ppt

第4章计算机专业基础知识(7数据结构) - 数据结构 1 概述 2 线性表 3 堆栈 4 队列 5 树 6 图 数据结构 1 概述 1 数据结构概述 ? 数据结构...

计算机辅助设计技术-第4章_常用数据结构_图文.ppt

计算机辅助设计技术-第4章_常用数据结构 - 第四章 机械CAD中常用的数据结构 第一节 基本概念 第二节 线性表 第三节 栈 第四节 树 第五节 二叉树 第四章...

第4章 CAD中常用的数据结构_图文.ppt

第4章 CAD中常用的数据结构 - 第四章 CAD中常用的数据结构 ?学习内容: ?CAD中数据结构 ?线性表 ?栈 ?树 ?二叉树 1 4.1 数据结构的概念 车床 床身及导轨...

第四章 算法与数据结构基础_图文.ppt

第四章 算法与数据结构基础_数学_自然科学_专业资料。第四章 算法与数据结构...关,数据的逻辑结构分为线性结构、树形结构和网状结构,如图45,4-6,4-7所示。...

数据结构第4章_图文.ppt

数据结构第4章 - 2 第4章 串 学习目标与要求: 了解串的基本概念和基本运算

数据结构 第4章_图文.ppt

数据结构 第4章 - 数据结构 广东工业大学 计算机学院 第4章 哈希表 第4章 哈希表 ? ? 4.1 哈希表的概念 4.2 哈希函数的构造方法 ? ? ? ? ? 4.2.1 ...

数据结构第四章资料_图文.ppt

数据结构第四章资料 - 第4章 串、数组和广义表 ? 第2章 线性表 ? 第3章 栈和队列 ? 第4章 串、数组和广义表 线性结构 可表示为:(a1 , a2 , ……,...

数据结构第4章_图文.ppt

数据结构第4章_数学_自然科学_专业资料。第 4章 串 4.1 应用实例 4.2 串...字符串是一种特殊的线性第4章 串 4.1 应用实例 4.2 串及其运算 4.3 串...

数据结构 第4章 广义线性表(g)_图文.ppt

数据结构 第4章 广义线性表(g) - 广东海洋大学 谢仕义 数据结构(C++版) 第四章 广义线性表 本章的基本内容是: 数组的逻辑结构特征 数组的存储方式及寻址方法...