第 5章 串与数组
【 课前思考 】
为什么顺序表以及其它线性结构的顺序存储结构都可以用 "一维数组 "来描述？
因为在高级编程语言中实现的一维数组正是用的这种顺序存储的映象方式。
从数据结构的观点来说,串是一种特殊的线性表 ;但就数据类型而言,串不是线性表 。
"串就是线性表 "的结论是否正确？
5.1 串类型的定义
5.2 串的表示和实现
5.3 串的模式匹配算法
5.4 串操作应用举例
5.5 数组的定义
5.6 数组顺序存储的表示和实现
5.7 矩阵的压缩存储
【 学习目标 】
1.理解 串 类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。
理解串类型的各种存储表示方法。
理解串匹配的各种算法。
2.理解数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在 以行为主 的存储表示中的地址计算方法；
3.掌握特殊矩阵的存储压缩表示方法；
4.理解稀疏矩阵的两类存储压缩方法的特点及其适用范围,掌握以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法 ；
【 重点和难点 】
1.重点了解串类型定义以及串的实现方法 —串的匹配,
学会利用这些基本操作来实现串的其它操作；
掌握 随机稀疏矩阵的压缩存储表示方法和运算实现串、串的匹配、数组、特殊矩阵、稀疏矩阵、三元组、
十字链表。
【 知识点 】
课后练习题,5.1,5.2,5.3,5.4,5.6,5.11,5.12
记为,s = ―a0 a1 ….,a n-1‖ (n≥0 )
串名 串值 (用 双引号 括起来）
串中字符个数 (n≥0),n=0 时称为空串? 。
由一个或多个空格符组成的串。
串 s中任意个连续的字符序列叫 s的子串 ; S叫 主串 。
子串的第一个字符的序号。
字符在串中的序号。
串长度相等，且对应位置上字符相等。
串 即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。
若干术语：
串长：
空白串：
子串：
子串位置：
字符位置：
串相等：
隐含结束符‘ /0‘,
即 ASCII码 NUL
5.1 串的定义和操作
串 （ string）,由 0个或多个字符组成的有限序列,
也称字符串 。 记为,s=―a0a1a2…… an-1‖ (n≥ 0),
其 中 s 是 串 的 名,a0a1a2…… an-1 是 串 的 值,
ai(0≤ i≤ n-1)可以是字母,数字或其它字符 。
串长度,串中字符的数目 n。
空串,不含任何字符的串,串长度 =0
空格串,仅由一个或多个空格组成的串
子串,由串中任意个连续的字符组成的子序列
主串,包含子串的串。
串相等的条件,当两个串的长度相等且各个对应位置的字符都相等时才相等。
注意,(1) 串值必须用一对单引号括起来
(2) 串值大小是按 词典 次序进行比较的
StrCompare(?data‘,‘Stru‘)<0
StrCompare(?cat‘,‘case‘)>0
显然,只有在两个串的长度相等且每个字符一一对等的情况下称两个串相等 。
练 1,串是由 字符组成的序列，一般记为 。
练 2,现有以下 4个字符串：
a =?BEI‘ b =?JING‘ c =?BEIJING‘ d =?BEI JING‘
问：① 他们各自的长度？
② a是哪个串的子串？在主串中的位置是多少？
a =3,b =4,c = 7,d=8
a是 c和 d的子串，在 c和 d中的位置都是 1
练 3,空串和空白串有无区别？
答,有区别。 空串 (Null String)是指长度为零的串；而空白串 (Blank String),是指包含一个或多个空白字符
‘ ’ (空格键 )的字符串。
0个或多个
S=‘a1a2……a n‘
1.串的数据对象约束为字符集。
2,线性表的基本操作大多以?单个元素?为操作对象，而串的基本操作通常以?串的整体?作为操作对象。
串的逻辑结构和线性表的区别,
补充,C语言中常用的串运算串比较,int strcmp(chars1,char s2); //StrCompare(S,T)
求串长,int strlen(char s); //StrLength(S)
串连接,char strcat(char *to,char *from) //Concat(&T,S1,S2)
子串定位,char strchr(char *s,char *c); //Index(S,T,pos)
……
注：用 C处理字符串时，要调用标准库函数 #include<string.h>
gets( char *s ) 输入一个串；
puts( char *s ) 输出一个串；
strcat(char *s1,char *s2 ) 串联接函数；
strcpy( char *s1,char *s2 ) 串复制函数；
strcmp( char *s1,char *s2 ) 串比较函数；
strlen( char *s ) 求串长函数；
表示空串，空串的长度为零。
StrAssign (&T,chars)
初始条件,chars是字符串常量。
操作结果,把 chars赋为 T的值。
StrCopy (&T,S)
初始条件,串 S 存在。
操作结果,由串 S复制得串 T。
DestroyString (&S)
初始条件,串 S存在。
操作结果,串 S被销毁。
StrEmpty (S)
初始条件,串 S存在。
操作结果,若 S为空串,则返回 true,否则返回 false.
串的基本操作
StrCompare (S,T)
初始条件,串 S 和 T 存在。
操作结果,若 S?T，则返回值?0;
若 S?T，则返回值?0;
若 S?T，则返回值?0.
StrLength (S)
初始条件,串 S存在。
操作结果,返回 S的元素个数,称为串的长度,
Concat (&T,S1,S2)
初始条件,串 S1和 S2存在。
操作结果,用 T返回由 S1和 S2联接而成的新串。
SubString (&Sub,S,pos,len)
初始条件：
操作结果,用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。
串 S 存在,1≤pos≤StrLength(S) 且 0≤len≤StrLength(S)-pos+1。
例如,Concate( T,?man?,?kind?),
求得 T =?mankind?
例如,StrCompare(?data?,?state?)<0
StrCompare(?cat?,?case?)>0
例如,SubString( sub,?commander?,4,3 )
子串为“串”中的一个字符子序列求得 sub =?man? ;
SubString( sub,?commander?,1,9 )
SubString( sub,?commander?,9,1 ) 求得 sub =?r?
求得 sub =?commander?
SubString( sub,?commander?,4,7 )
sub =?
SubString( sub,?beijing?,7,2 ) =?
sub =?
SubString(?student?,5,0 ) =起始位置和子串长度之间存在约束关系长度为 0 的子串为“合法”串
Index( S,T,pos )
初始 条件：串 S和 T存在,T是非空串,1≤pos≤StrLength(S)。
操作结果,若主串 S 中存在和串 T 值相同的子串,则返回它在主串 S 中第 pos个字符之后第一次出现的位置 ; 否则函数值为 0。
假设 S =?abcaabcaaabc?,T =?bca?
Index(S,T,1) = 2;
Index(S,T,3) = 6;
Index(S,T,8) = 0;
―子串在主串中的位置”意指子串中的第一个字符在主串中的位序。
Replace (&S,T,V)
初始条件,串 S,T和 V 均已存在，且 T 是非空串。
操作结果,用 V 替换主串 S 中出现的所有与（模式串） T相等的不重叠 的子串。
例如,假设 S =?abcaabcaaabca?,T =?bca?
若 V =?x?,则经置换后得到 S =?axaxaax?
若 V =?bc?,则经置换后得到 S =?abcabcaabc?
b a b a b
例：假设 S="abcacabcaca",T="abca"和 V="x"，则置换之后的
S="xcxca"。
注意定义中 "不重叠 "三个字，若上例中的 V="ab"时，则置换后的结果应该是
S=" abcabca"，而不是 "abbca"。
串赋值 StrAssign、串复制 Strcopy、
串比较 StrCompare、求串长 StrLength、
串联接 Concat以及求子串 SubString
等六种操作构成串类型的最小操作子集。
在上述抽象数据类型定义的 13种操作中，
即：这些操作不可能利用其他串操作来实现，
反之，其他串操作（除串清除 ClearString和串销毁 DestroyString外）可在这个最小操作子集上实现。
例如，可利用 串比较,求串长和求子串等操作实现定位函数 Index( S,T,pos )。
StrCompare(SubString(S,i,StrLength(T)),T )
S串
T串 T串
i
pos n-m+1
算法的基本思想为：
0
int Index (String S,String T,int pos) {
// T为非空串。若主串 S中第 pos个字符之后存在与 T相等的子串，
// 则返回第一个这样的子串在 S中的 位置，否则返回 0
if (pos > 0) {
}
return 0; //S中不存在与 T相等的子串
}
n = StrLength(S); m = StrLength(T); i = pos;
while ( i <= n-m+1) {
} // while
SubString (sub,S,i,m);
if (StrCompare(sub,T) != 0) ++i ;
else return i ;
串的置换函数：
S串
T串 V串
V串
pos pos
sub
i
news 串
sub
= i+m pos
n-pos+1
void replace(String& S,String T,String V) {
}
while ( pos <= n-m+1 && i) {
i=Index(S,T,pos);
if (i!=0) {
SubString(sub,S,pos,i-pos); // 不置换子串
Concat(news,sub,V);
pos = i+m;
}
}
SubString(sub,S,pos,n-pos+1); // 剩余串
Concat( S,news,sub );
n=StrLength(S); m=StrLength(T); pos = 1;
StrAssign(news,NullStr); i=1;
串 的逻辑结构和 线性表 极为相似,区别 仅在于 串的数据对象约束为字符集 。
串的基本操作和线性表有很大差别。
在线性表的基本操作中，大多以 单个元素 作为操作对象；
在串的基本操作中，通常以 串的整体 作为操作对象。
串的 整体操作
– 赋值 StrAssign(S,―Data Structure‖)
– 复制 StrCopy(T,S) // T<=S,T为? Data Structure‖
– 比较 StrCompare(S,T)
– 连接 Concat(T,―Data‖,―Structure‖) //T为? DataStructure‖
– 取子串 SubString(sub,S,2,5) // sub为? ata S‖
– 子串在主串中的定位 Index(S,―a‖,3) // 4
– 子串置换 Replace(S,―a‖,―b‖) // S为? Dbtb Structure‖
– 子串插入 StrInsert(S,3,―aha‖) // ―Daahata Structure‖
– 子串删除 StrDelete(S,3,5) // ―Daructure‖
设 s =‘I AM A STUDENT‘,t =‘GOOD‘,
q=‘WORKER‘ 。求：
练习：
StrLength(s) ＝
StrLength(t) ＝
SubString(s,8,7)=
SubString(t,2,1)=
Index(s,?A‘)=
Index(s,t)=
Replace(s,?STUDENT‘,q)=
14
4
STUDENT‘
O‘
3
0 （ s中没有 t！）
’ I AM A WORKER‘
再问,Concat(SubString(s,6,2),Concat(t,SubString(s,7,8))) ＝？
一、串的定长顺序存储表示二、串的堆分配存储表示三、串的块链存储表示
5.2 串的表示和实现
5.2串的表示和实现
定长顺序存储表示 ——用一组地址连续的存储单元存储串值的字符序列
堆分配存储表示 ——用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。
串的块链存储表示 ——链式方式存储首先强调,串与线性表的运算有所不同，是以? 串的整体? 作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。
串有三种机内表示方法：
顺序存储链式存储定长顺序存储特点,用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的 上界预先给出,故称为静态存储分配。
例如,#define Maxstrlen 255 //用户可用的最大串长
typedef unsigned char SString[Maxstrlen+1];
SString s; //s是一个可容纳 255个字符的顺序串。
注：
一般用 SString[0]来存放串长信息；
C语言约定在串尾加结束符 ‘ \0?，以利操作加速，但不计入串长；
若字符串超过 Maxstrlen 则自动截断（因为静态数组存不 进去）。
讨论,想存放 超长 字符串怎么办？ ——静态数组有缺陷！
实现方式,两串连接和 求子串改用 动态 分配的一维数组 —— ―堆”！
5.2.1 串的定长顺序存储表示
void Concat_Sq( char S1[ ],char S2[ ],char T[ ]) {
j=0; k=0;
while ( S1[j] != '\0' ) T[k++] = S1[j++]; //复制串 S1
j = 0;
while ( S2[j] != '\0' ) T[k++] = S2[j++]; //接着复制串 S2
T[k] = '\0';
} // Concat
#define MAXSTRLEN 255 //串长度最大为 255
char SString[MAXSTRLEN];
void SubString_Sq( char Sub[ ],char S,int pos,int len) {
// 用 Sub返回串 S的第 pos个字符起长度为 len的子串。
// 其中,0≤pos<StrLength(S) 且 0≤len≤StrLength(S)-pos。
slen=StrLength_Sq(S); //求取顺序存储表示的字符串 S的串长度
if ( pos<0||pos>slen-1||len<0||len>slen-pos ) ERROR( "参数不合法 ");
for ( j = 0; j < len; j++ ) Sub[ j ] = S[ pos + j ];
Sub[len] = '\0';
} // SubString
将串 S中从第 pos个字符开始长度为 len的字符序列复制到串 Sub中 （注：串 Sub的预留长度与 S一样）
typedef struct {
char *ch; // 若是非空串,则按串实用长度分配存储区,否则 ch 为 NULL
int length; // 串长度
} HString;
5.2.2 串的堆分配存储表示通常,C/C++语言中提供的串类型就是以这种存储方式实现的。
系统利用函数 malloc( ) /new和 free( )/delete 进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为 堆 。
C语言中的串以一个空字符为结束符，串长是一个隐含值。
这类串操作 实现的算法 为,先为新生成的串分配一个存储空间，然后进行串值的复制。
void StrInsert_ HSq (char *S,int pos,char *T)
{ //1≤pos≤StrLength(S)+1。在串 S的第 pos个字符 之前 插入串 T
slen=StrLength_HSq (S); tlen=StrLength_HSq (T);
char S1[slen +1] ; // S1作为辅助串空间用于暂存 S
if ( pos<1 || pos>slen+1 ) ERROR(" 插入位置不合法 ");
if ( tlen>0 ) {
i=0;
while ( (S1[i]=S[i])!='\0' ) i++; // 暂存串 S
S = new char[slen+tlen+1]; // 为 S重新分配空间
for ( i=0,k=0; i<pos-1; i++ ) S[k++] = S1[i];
j = 0;
while ( T[j]!= '\0' ) S[k++] = T[j++]; // 插入 T
while ( S1[i]!= '\0? ) S[k++] = S1[i++]; 串
S[k] = '\0'; // 置串 S的结束标志
}
}
void StrInsert ( char *S,int pos,char *T ) {
char *S1,*Sub;
slen = strlen(S); tlen = strlen(T);
if ( pos<1 || pos>slen+1 ) ERROR(,插入位置不合法” );
if ( tlen>0 ) {
S1 = strdup(S);
S = new char[slen+tlen+1];
Sub = s1+pos-1;
strncpy( S,S1,pos-1 );
s[pos-1] =?\0];
strcat( S,T );
strcat( S,Sub );
}
}
例：用堆实现串插入操作
5.2.3 串的块链存储表示也可用链表来存储串值，由于串的数据元素是一个字符，它只有 8 位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。
存储密度 = 数据元素所占存储位 实际分配的存储位
#define CHUNKSIZE 80 // 可由用户定义的块大小
typedef struct Chunk { // 结点结构
char ch[CUNKSIZE];
struct Chunk *next;
} Chunk;
typedef struct { // 串的链表结构
Chunk *head,*tail; // 串的 头和尾指针
int curlen; // 串的 当前长度
} LString;
S.head
S.crulen
S.tail
T h i s a s t
r i n g ^
i s
例如,在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即,同一行的串用定长结构
(80个字符 ),行和行之间用指针相联接。
实际应用时，可以根据问题所需来设置结点的大小。
讨论,法 1存储密度为 ；法 2存储密度为 ；
显然，若 数据元素很多，用法 2存储更优 —称为 块链结构链式存储特点,用链表存储串值，易插入和删除。
法 1,链表结点（数据域）大小取 1
法 2,链表结点（数据域）大小取 n(例如 n=4)
1/2 9/15=3/5
A? B? C? I NULLhead
head A B C D? E F G H? I # # # NULL
模式匹配 (Pattern Matching) 即 子串定位运算 (Index函数 ).
初始条件,串 S和 T存在,T是非空串,1≤pos≤StrLength(s)
操作结果,若主串 S中存在和串 T值相同的子串，则返回它在主串
S中第 pos个字符之后 第一次 出现的位置；否则函数值为 0。
注,S称为 被匹配的串,T称为 模式串 。若 S包含串 T，则称 匹配成功 。否则称 匹配不成功 。
算法目的,确定主串中所含子串第一次出现的位置（ 定位 ）
——即如何实现 Index(S,T,pos)函数
5.3 串的模式匹配算法
BF算法 (又称古典的、经典的、朴素的、穷举的 )
KMP算法 (特点：速度快 )
Index(S,T,pos)函数
S串
T串 T串
i
pos n-m+1
S串
T 串 T串
i
j j>m
i
j
i
j
i>n
j
T串
i
jBF算法设计思想：
将主串的第 pos个字符和模式的第 1个字符比较，
若 相等,继续逐个比较后续字符；
若 不等,从主串的下一字符（ pos+1）起，重新与第一个字符比较。
直到主串的一个连续子串字符序列与模式相等 。返回值为 S中与 T匹配的子序列 第一个字符的序号,即匹配成功。
否则，匹配失败，返回值 0,
S=?a b a b c a b c a c b a b‘T=?a b c a c‘
pos=5
int Index( char char S[],char T[],int pos ) {
I = pos; j = 1;
Slen = strlen(S); Tlen = strlen(T);
while ( i<=Slen && j<=Tlen ) {
if ( S[i]==T[j] ) { ++i,++j } //继续比较后续字符
else { i=i-j+2; j=1; } //指针回溯到 下一首位，重新开始匹配
}
if ( j>Tlen ) return i-j+1; //子串结束，说明匹配成功
else return 0;
} //Index
BF算法的实现 —即 Index()操作的实现
S=?a b a b c a b c a c b a b‘
T=?a b c a c‘
pos=5
相当于子串向右滑动一个字符位置匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。
i
j
S a b b b a a
T
朴素的模式匹配过程
a b aa b a b aa b a
模式匹配的最简单的做法是,用 T中的字符依次与 S中的字符比较：
如果 S0 = T0,S1 = T1,…,Sm-1 = Tm-1,则匹配成功,调用求子串的操作 subString(S,1,m)即是找到的子串 。 否则必有某个 i（ 0≤i≤m-1）,
使得 Si ≠Ti,这时可将 T右移一个字符,用 T中字符从头开始与 S中字符依次比较；如此反复执行,直到下面两种情况之一：或者到达某步时,Si = T0,Si+1 = T1,…,Si+m-1 = Tm-1,匹配成功,
subString(S,i+1,m)即是找到的 （ 第一个 ） 与模式 T相同的子串；或者一直将 T移到无法与 S继续比较为止,则匹配失败 。
a
第一趟匹配 a b a b c a b c a c b a b
i=3
a b c
j=3
第二趟匹配 a b a b c a b c a c b a b
i=2
a
j=1
第三趟匹配 a b a b c a b c a c b a b
i=7
a b c a c
j=5
S[2]!=t[2],该趟匹配失败 i=i- j+1,j=0
进入下趟匹配算法
i=0
i=1
S[1]!=t[0],该趟匹配失败 i=i- j+1,j=0
进入下趟
i=2
S[6]!=t[4],该趟匹配失败 i=i- j+1,j=0
进入下趟串的模式匹配算法第四趟匹配 a b a b c a b c a c b a b
i=4
a
j=1
第五趟匹配 a b a b c a b c a c b a bi=5
a
j=1
第六趟匹配 a b a b c a b c a c b a b
i=11
a b c a c
j=6
匹配成功匹配算法 2
S[3]!=t[0],该趟匹配失败 i=i- j+1,j=0
进入下趟
S[4]!=t[0],该趟匹配失败 i=i- j+1,j=0
进入下趟
j 等于 t 的串长,该趟匹配成功,返回 i=i-n
i=4
i=3
i=5
串的模式匹配算法
int Index_BF ( char S [ ],char T [ ],int pos ) {
i = pos; j = 0;
while ( S[i+j] != '\0' && T[j] != '\0' )
if ( S[i+j] == T[j] ) j ++; // 继续比较后一字符
else { i ++; j = 0; } // 重新开始新的一轮比较
if ( T[j] == '\0' ) return i; else return -1;
}
BF算法的时间复杂度讨论,若 n为主串长度,m为子串长度，则串的 BF匹配算法最坏的情况下需要比较字符的总次数为,(n-m+1)*m＝ O(n*m)
最恶劣情况是,主串前面 n-m个位置都 部分匹配 到子串的最后一位，
即这 n-m位各比较了 m次，再加上最后 m位也各比较了 1次，所以总次数为,(n-m)*m+m＝ (n-m+1)*m
一般的情况是,O(n+m) 要从最好到最坏情况统计总的比较次数,
然后取平均。
最好的情况是,一配就中！
5.4 正文编辑 —串操作应用举例文本编辑,实质是修改字符数据的形式或格式,
包括串的查找,插入,删除等基本操作 。
思路,可以利用换行符和换页符将文本划分成若干页，每页包含若干行。 页是文本串的子串，行是页的子串 。在编辑程序中，先为文本串建立相应的页表和行表，即建立各子串的存储映象，在程序中设立页指针、行指针和字符指针，分别指向当前操作的页、行和字符。进行文本编辑的过程，就是一个对行表、页表进行查找、插入或删除的过程。
假设有下列一段 C的源程序
main() {
float a,b,max;
scanf(―%f,%f‖,&a,&b);
if a>b max=a;
else max=b;
};
将此源程序看成是一个正文串,输入 内存后如图所示,
图中,↙,为换行符。
m a i n ( ) { ↙ f l o a t a,b,
m a x ; ↙ s c a n f ( " % f,% f "
,& a,& b ) ; ↙ i f a > b m
a x = a ; ↙ e l s e m a x = b ;
↙ } ; ↙
如果在某行内插入或删除若干字符,则要修改行表中该行的长度,若该行长度因插入而超出了原分配给它的存储空间,
则要为该行重新分配存储空间,并修改该行的起始位置。
例如,对上述源程序进行编辑后,其中的 105行修改成：
If (a>b) max=a;
108行修改成：
}
修改后的行表如图所示。
行号 起始地址 长度
100 200 8
102 208 17
104 225 24
105 284 19
106 266 15
108 281 2
行号 起始地址 长度
100 200 8
102 208 17
104 225 24
105 249 17
106 266 15
108 281 3
5.5 数组数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表
mnmm
n
n
nm
aaa
aaa
aaa
A
......
...............
......
......
21
22221
11211
– 数组特点
数组结构固定
数据元素同构
– 数组运算
给定一组下标，存取相应的数据元素
给定一组下标，修改数据元素的值
( )
( )
( )
( )
(
)
(
)
(
)
(
)
(
)
5.5.1 数组的定义和特点一、定义
5.5.1 数组的定义和操作
定义特殊的线性表,一个数组中，数据元素的类型是一样的；
数据元素的类型可能 是非结构的原子类型,也可能是 定长线性表 。 数组一旦被定义，它的维数和维界就不再改变。
数组 (数据结构 ) vs 数组类型 (程序设计语言中 )
数组 (数据结构 ) 反映数据元素之间的特殊逻辑关系可以用数组类型表示，也可以用链表示数组类型 体现物理表示，如 C中规定按行优先存储
ADT Array
初始化、注销、存取元素值 ----无插入、删除操作
二维数组
a00 a01 … a0,n-1
a10 a11 … a1,n-1
… … … …
am-1,0 am-1,1 … am-1,n-1
将二维数组看成是一个定长线性表，即
A = ( a0,a1,.,,,ap ) p=m-1或 n -1
其中每个数据元素也是一个定长线性表，即
aj = ( a0j,a1j,.,,,am-1,j ) 0≤j ≤ n -1 aj是 列向量 形式的线性表
ai = ( ai0,ai1,.,,,ai,n-1 ) 0≤i ≤ m -1 ai是 行向量 形式的线性表
Am× n =
5.5.1 数组的定义和操作数组,由一组名字相同、下标不同的变量构成注意,本章所讨论的数组与高级语言中的数组有所区别：
高级语言中的数组是顺序结构；
本章的数组既可以是顺序的，也可以是链式结构。
答,对的 。因为：
① 数组中各元素具有 统一的类型 ；
② 数组元素的下标一般具有 固定的上界和下界,即数组一旦被定义，它的维数和维界就不再改变。
③数组的 基本操作比较简单,除了结构的初始化和销毁之外,只有存取元素和修改元素值的操作 。
讨论：“数组的处理比其它复杂的结构要简单”，对吗？
5.5.1 数组的定义和操作二维数组的特点：
一维数组的特点,1个下标,ai 是 ai+1的直接前驱
2个下标,每个元素 ai,j受到两个关系
（行关系和列关系）的约束：
一个 m× n的二维数组可以看成是 m行的一维数组，或者 n列的一维数组。
N维数组的特点,n个下标,每个元素受到 n个关系约束一个 n维数组可以看成是 由若干个 n－ 1维数组组成的线性表。
a11 a12 … a 1n
a21 a22 … a 2n
… … … …
am1 am2 … a mn
Amn=
5.5.1 数组的定义和操作
5.5.2 数组的顺序存储表示和实现问题,计算机的存储结构是一维的，而数组一般是多维的，
怎样存放？
解决办法,事先约定按某种次序将数组元素排成一列序列，
然后将这个线性序列存入存储器中。
例如,在二维数组中，我们既可以规定按 行 存储，也可以规定按 列 存储 。
注意：
若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；
约定的次序不同，则计算元素地址的公式也有所不同；
C和 PASCAL中一般采用行优先顺序； FORTRAN采用列优先。
通常有两种顺序存储方式：
以行序为主序
以列序为主序
a11 a12 …….,a 1n
a21 a22 …….,a 2n
am1 am2 …….,a mn
………………….
Loc( aij)=Loc(a11)+[(i-1)n+(j-1)]*l
按行序为主序存放
amn
…….,
am2
am1
……….
a2n
…….,
a22
a21
a1n
…….
a12
a110
1
n-1
m*n-1
n
按列序为主序存放
0
1
m-1
*n-1
m
amn
…….,
a2n
a n
……….
am2
…….,
a22
a12
am1
…….
a21
a11
a11 a12 …….,a1n
a21 a22 …….,a2n
am1 am2 …….,amn
………………….
Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l
补充：计算二维数组元素地址的通式设一般的二维数组是 A[c1..d1,c2..d2],这里 c1,c2不一定是 0。
无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（ 这样数组中的任一元素便可以随机存取！ ）,
二维数组 列优先 存储的通式为：
LOC(aij)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L
ac1,c2 … a c1,d2
… aij …
ad1,c2 … a d1,d2
Amn=
单个元素长度aij之前的行数数组基址 总列数，即第 2维长度
aij本行前面的元素个数
① 开始结点的存放地址（即基地址）
②维数和每维的上、下界；
③每个数组元素所占用的单元数则 行优先 存储时的地址公式为：
LOC(aij)=LOC(ac1,c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L
Loc(j1,j2,… jn)=LOC(0,0,… 0)＋
若是 N维数组，其中任一元素的地址该如何计算？
n
i
ii
1
jC
其中 Cn=L,Ci-1=bi× Ci,1<i≤n
一个元素长度数组基址前面若干元素占用的地址字节总数第 i维长度 与所存元素个数有关的系数，可用递推法求出例如：
称为基地址或基址。
以“行序为主序”的存储映象二维数组 A中任一元素 ai,j的存储位置
LOC(i,j) = LOC(0,0) + (b2× i＋ j)×
a0,1a0,0 a0,2
a1,0 a1,1 a1,2
a0,1a0,0 a0,2 a1,0 a1,1 a1,2
L
L
在 C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，
typedef elemtype array2[m][n];
等价于：
typedef elemtype array1[n];
typedef array1 array2[m];
数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。
5.5.2 数组的顺序表示和实现例,已知二维数组 Am,m按行存储的元素地址公式是：
Loc(aij)= Loc(a11)+[(i-1)*m+(j-1)]*K,按列存储的公式是？
Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K （尽管是方阵，但公式仍不同）
例,一个二维数组 A，行下标的范围是 1到 6，列下标的范围是 0
到 7，每个数组元素用相邻的 6个字节存储，存储器按字节编址。那么，这个数组的体积是 个字节。288
例,设数组 a[1…60,1…70]的基地址为 2048，每个元素占 2个存储单元，若以列序为主序顺序存储，则元素 a[32,58]的存储地址为 。8950
LOC(aij)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L
得,LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1)]*2＝ 8950
答,请注意审题！ 利用列优先通式：
答,Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288
5.5.3 数组的应用利用数组降低算法的复杂度。
例：寻求两个字符串中的最大公共子串。
设 string1 =,sgabacbadfgbacst”,
string2 =“gabadfgab”
最长公共子串为 badfg。
算法的复杂度：
时间复杂度,O(m*n)
空间复杂度,O(m*n)
1
1 1 1 1
1
1
1
11
1
1 1
1
1
1
1
1
1
1
1
1
1
1
g
a
b
a
d
f
g
a
b
s g a b a c b a d f g b a c s t
串的对应矩阵子串集,Gab,3 a,1 b,1 a,1
最大长度,3,位置序号,1最大长度,0,位置序号,-
a,1 gaba,4 a/b,1
最大长度,4,位置序号：
badfg,5 a,1
最大长度,5,位置序号,6
a,1 ba,2 g,1 a,1位置数,6号，长度,5
子串,badfg
程序
void diagmaxl( int mat[ ][ ],int
&maxlen,int jpos )
{
maxlen = 0; jpos = -1;
istart = 0;
for ( k=-(m-1); k<=n-1; k++ ) {
i = istart; j = i-k;
diagscan(i,j);
if (k>=0) istart++;
}
}
void diagscan( int I,int j )
{
eg = 0; len = 0;
while ( i<n && j<m ) {
if ( mat[i][j]==1 ) {
len++;
if ( !eg ) { sj = j; eg = 1; }
}
else if ( eg ) {
if ( len>maxlen ) { maxlen = len; jpos = sj; }
eg = 0; len = 0;
}
i++; j++;
}
}
int maxsamesubstring ( char *string1,char *string2,char *&sub )
{ p1 = string2; p2 = string1;
for ( i=0; i<n; i++ )
for ( j=0; j<m; j++ )
if ( *(p1+i)==*(p2+j) ) mat[i][j] = 1; else mat[i][j] = 0;
diagmaxl( mat,maxlen,jpos );
if ( maxlen==0 ) *sun =?\0?; else subString( sub,string1,jpos,
maxlen );
return maxlen;
}
void SubString( char *&sub,char *str,int s,int len )
{ char *p;
int k;
sub = new char[len+1];
p = str+s-1; k=len;
while ( k ) { *sub++ = *p++; k--; }
*sub =?\0?;
sub = sub-len;
}
在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，
就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为 1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为 1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，我们可以对这类矩阵进行 压缩存储,即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。
5.6 矩阵的压缩存储以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题,
1) 零值元素占了很大空间 ;
2) 计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零 ;
1) 尽可能少存或不存零值元素 ;
解决问题的原则,
2) 尽可能减少没有实际意义的运算 ;
3) 操作方便 ; 即,能尽可能快地找到与下标值 (i,j) 对应的元素 ;
能尽可能快地找到同一行或同一列的非零值元 ;
5.6 矩阵的压缩存储讨论：
1,什么是压缩存储？
若多个数据元素的 值都相同,则只分配一个元素值的存储空间，且零元素不占存储空间。
2,所有二维数组（矩阵）都能压缩吗？
未必，要看矩阵是否具备以上压缩条件。
3,什么样的矩阵具备以上压缩条件？
一些特殊矩阵，
如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。
4,什么叫稀疏矩阵？
矩阵中非零元素的个数较少（一般小于 5%）
重点介绍稀疏矩阵的压缩和相应的操作。
在一个 n阶方阵 A中，若元素满足下述性质：
aij=aji 0≦i,j≦n -1
则称 A为对称矩阵。
对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。
5.6.1 特殊形状矩阵的存储表示所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。
1、对称矩阵
5.3 矩阵的压缩存储
对称矩阵
– 为每一对对称元分配一个存储空间,n2?n(n+1)/2
– 以行序为主序存储下三角中的元 ——下三角矩阵
a11
a21 a22
… … …
an1 an2 … ann?
jii
jj
jij
ii
k
当当
1
2
)1(
1
2
)1(
a11 a21 a22 a31 … an1 … ann
k = 0 1 2 3 n(n-1)/2 n(n+1)/2-1
对称矩阵定义,n阶矩阵 A中的元满足 aij= aji ( 1≤ i,j≤n)
a00 a01 … a 0 n-1 a00 0 … 0
0 a11 … a 1 n-1 a10 a11 … 0
………………….,……………..
0 0 … a n-1 n-1 an-1 0 an-1 1 … a n-1 n-1
(a)上三角矩阵 (b)下三角矩阵
2、三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。
上三角矩阵,它的下三角 (除主对角线 )中的元素均为常数。
下三角矩阵,它的主对角线上方均为常数。
三角矩阵常数为零
2、三角矩阵
a11 0 0…….,0
a21 a22 0…….,0
an1 an2 an3…….,ann
…………………,0
Loc(aij)=Loc(a11)+[( +(j-1)]*li(i-1)2
按行序为主序,a11 a21 a22 a31 a32 an1 ann…..,…...
k = 0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
1、若 i≧ j，则 ai j在 下三角形 中。
ai j之前的 i行 (从第 0 行到第 i-1行 )一共有,
1+2+…+i=i(i+1)/2个元素，
在第 i行上,ai j之前恰有 j个元素
（即 ai0,ai1,ai2,…,aij-1），
因此有,k=i*(i+1)/2+j 0≦ k<n(n+1)/2
2、若 i<j，则 aij是在 上三角 矩阵中。
因为 aij=aji，
所以只要交换上述对应关系式中的 i和 j即可得到：
k=j*(j+1)/2+i 0≦ k<n(n+1)/2
3、对角矩阵
a11 a12 0 ……………,0
a21 a22 a23 0…………… 0
0 0… an-1,n-2 an-1,n-1 an-1,n
0 0 … … an,n-1 ann.
0 a32 a33 a34 0……… 0
……………………………
Loc(aij)=Loc(a11)+2(i-1)+(j-1) |i-j|<=1
按行序为主序,a11 a12 a21 a22 … an-1,n an,n-1 ann
k = 1 2 3 4 3n-2
假设 m 行 n 列 的矩阵含 t 个非零元素,
则称为 稀疏因子通常认为 0.05 的矩阵为稀疏矩阵
nm t
5.6.2 稀疏矩阵的压缩存储何谓稀疏矩阵？
7600070015
00000180
00002400
01400003
0000000
00009120
M
M由 { (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)唯一确定稀疏矩阵
定义,非零元较零元少，且分布没有一定规律的矩阵
压缩存储原则,只存矩阵的行列维数和每个非零元的行列下标及其值一、稀疏矩阵的压缩存储问题：
如果只存储 稀疏矩阵中的非零元素，那这些元素的 位置信息 该如何表示？
解决思路：
对每个非零元素 增开 若干存储单元，例如存放其所在的行号和列号，便可准确反映该元素所在位置。
实现方法：
将每个非零元素用一个三元组 （ i,j,aij）来表示，
则每个 稀疏矩阵可用一个 三元组表 来表示。
二、稀疏矩阵的操作
1、三元组顺序表随机稀疏矩阵的压缩存储方法
稀疏矩阵的三元组顺序表表示
– 存储非零元,记录值、位置 (行下标和列下标 )——
三元组
– 三元组的排列次序,这里以行序为主序，也可选择以列序为主序 ——有序表
– 稀疏矩阵的规模,行数、列数以及非零元的个数
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0
6 7 8
1 2 12
1 3 9
3 1 –3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
1、三元组顺序表
#define MAXSIZE 125000 //设非零元素最大个数 125000
typedef struct {
int i; //元素行号
int j; //元素列号
ElemType e; //元素值
} Triple;
typedef struct {
Triple data[MAXSIZE+1]; //三元组表，以行为主序存入一维向量 data[ ]中
int mu; //矩阵总行数
int nu; //矩阵总列数
int tu; //矩阵中非零元素总个数
} TsMatrix;
三元组表的顺序存储表示稀疏矩阵的压缩存储方法
–顺序存储结构三元组表
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
ma
i j v
行列下标 非零元值
7600070015
00000180
00002400
01400003
0000000
00009120
M
#define M 20
typedef struct node
{ int i,j;
int v;
} Node;
Node ma[M];
三元组表所需存储单元个数为 3(t+1)
其中 t为非零元个数
0
1
2
3
4
5
6
7
8
ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数链式存储结构 -- 带行指针向量的单链表表示
每行的非零元用一个单链表存放
设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空
表头结点与单链表结点类型定义 0
typedef struct node
{ int col;
int val;
struct node *link;
} Node;
typedef struct Node *TD;
02000
00000
00021
00100
70003
A
^
1 3 5 7
3 -1
1 -1 2 -2
4 2 ^
^
^
^
需存储单元个数为 3t+m
例：三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的,和 。行下标 列下标 元素值例,写出右图所示稀疏矩阵的压缩存储形式。
0 12 9 0 0 0
0 0 0 0 0 0
-3 0 0 0 14 0
0 0 24 0 0 0
0 18 0 0 0 0
15 0 0 -7 0 0
(( 1,2,12),(1,3,9),(3,1,-3),(3,5,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))
法 1,用线性表表示
9 0 0 0
3 0 0 0 14 0
0 24 0 0 0
18 0 0 0 0
0 7 0 0
法 2,用三元组矩阵表示：
0 12 9 0 0 0
0 0 0 0 0 0
-3 0 0 0 14 0
0 0 24 0 0 0
0 18 0 0 0 0
15 0 0 -7 0 0
1 2 12
1 3 9
3 1 -3
3 5 14
4 3 24
5 2 18
6 1 15
6 4 -7
注意,为更可靠描述，
通常再加一行总体信息：
总行数、总列数、非零元素总个数
6 6 8
i j value
稀疏矩阵压缩存储的 缺点：将失去随机存取功能
0
1
2
3
4
5
6
7
8
法 3,用 带辅助向量 的三元组表示。
方法,增加 2个辅助向量：
① 记录每行非 0元素个数,用 NUM(i)表示 ;
② 记录稀疏矩阵中每行第一个非 0元素在三元组中的行号,用 POS(i)表示。
76531
211202NUM( i)
6543
POS( i )
21i
0 12 9 0 0 0
0 0 0 0 0 0
-3 0 0 0 14 0
0 0 24 0 0 0
0 18 0 0 0 0
15 0 0 -7 0 0
-746
1516
1825
2434
1453
-313
931
1221
866
vji
0
1
2
3
4
5
6
7
8
3
用途,通过三元组 高效访问稀疏矩阵 中任一非零元素。
规律,POS(1)＝ 1
POS(i)＝ POS(i-1)+NUM(i-1)
稀疏矩阵的操作
0 12 9 0 0 0
0 0 0 0 0 0
-3 0 0 0 14 0
0 0 24 0 0 0
0 18 0 0 0 0
15 0 0 -7 0 0
0 0 –3 0 0 15
12 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 14 0 0 0
0 0 0 0 0 0
(1,2,12)
(1,3,9 )
(3,1,-3)
(3,5,14)
(4,3,24)
(5,2,18)
(6,1,15)
(6,4,-7)
(1,3,-3)
(1,6,15)
(2,1,12)
(2,5,18)
(3,1,9)
(3,4,24)
(4,6,-7)
(5,3,14)
三元组表
a.data
三元组表
b.data
转置后M T
（以转置运算为例）
目的：
转置如何求转置矩阵？
0280036
00070
500140
005
2800
000
0714
3600
用常规的二维数组表示时的算法其时间复杂度为,O(mu× nu)
for (col=1; col<=nu; ++col)
for (row=1; row<=mu; ++row)
T[col][row] = M[row][col];
用三元组表示时如何实现？
1 2 14
1 5 -5
2 2 -7
3 1 36
3 4 28
2 1 14
5 1 -5
2 2 -7
1 3 36
4 3 28
7600070015
00000180
00002400
01400003
0000000
00009120
M
67000000
0001400
000000
700000
0024009
01800012
1500300
N
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
m
a
i j v
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
m
b
0
1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
8
答,肯定不正确！
除了,(1) 每个元素的行下标和列下标互换 (即三元组中的 i和 j互换 );
还应该 (2) T的总行数 mu和总列数 nu与 M值不同（ 互换）；
(3) 重排 三元组内元素顺序,使转置后的三元组也按行 (或列 )
为主序有规律的排列。
上述（ 1）和（ 2）容易实现，难点在 （ 3） 。
若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算，这种说法正确吗？
有两种实现方法压缩转置
(压缩 )快速转置提问：
方法 1,压缩转置思路,反复扫描 a.data中的 列序,从小到大依次进行转置。
三元组表
a.data
三元组表
b.data
①
(1,3,-3)
②
(1,6,15)
③
(2,1,12)
④
(2,5,18)
⑤
(3,1,9)⑥
(3,4,24)
⑦
(4,6,-7)
⑧
(5,3,14)
(1,2,12)
(1,3,9 )
(3,1,-3)
(3,5,14)
(4,3,24)
(5,2,18)
(6,1,15)
(6,4,-7)
1
1
2
col q
1
2
3
4
p
1
2
3
4
解决思路,只要做到
将矩阵行、列维数互换
将每个三元组中的 i和 j相互调换
重排三元组次序，使 mb中元素以 N的行 (M的列 )为主序方法一,按 M的列序转置,即按 mb中三元组次序依次在 ma中找到相应的三元组进行转置。
为找到 M中每一列所有非零元素，需对其三元组表 ma从第一行起扫描一遍。由于 ma中以 M行序为主序,所以由此得到的恰是
mb中应有的顺序
算法分析,T(n)=O(M的列数 n?非零元个数 t)
若 t 与 m?n同数量级，则 )()(
2nmOnT
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
ma
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
i j v
mb
kp
p
p
p
p
p
p
p
k
k
k
k
p
p
p
p
p
p
p
p
col=1 col=2
0
1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
8
bool TransPoseSMatrix(TSMatrix M,TSMatrix &T)
{
T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
if ( T.tu ) {
q=1;
for ( col=1; col<=M.nu; col++ ) {
for ( p=1; p<=M.tu; p++ ) {
if (M.data[p].j==col) {
T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;
T.data[q].value=M.data[p].value; q++;
}
}
}
}
return OK;
}
压缩转置算法描述,
1,主要时间消耗在 查找 M.data[p].j=col的元素,由两重循环完成,
for(col=1; col<=M.nu; col++) 循环次数＝ nu
{ for(p=1; p<=M.tu; p++) 循环次数＝ tu
所以该算法的时间复杂度为 O(nu*tu)
----即 M的列数与 M中非零元素的个数之 积最恶劣情况,M中全是非零元素，此时 tu=mu*nu，
时间复杂度为 O(nu2*mu )
注,若 M中基本上是非零元素时，即使用非压缩传统转置算法的时间复杂度也不过是 O(nu*mu)
结论,压缩转置算法不能滥用。
前提,仅适用于非零元素个数很少（即 tu<<mu*nu）的情况。
压缩转置算法的效率分析,
三元组表
a.data
三元组表
b.data
③
(1,3,-3)①
(2,1,12)
⑥
(2,5,18)
②
(3,1,9)
⑧
(4,6,-7)
④
(5,3,14)
⑦
(1,6,15)
⑤
(3,4,24)
(1,2,12)
(1,3,9 )
(3,1,-3)
(3,5,14)
(4,3,24)
(5,2,18)
(6,1,15)
(6,4,-7)
思路,依次 把 a.data中的元素直接送入 b.data的恰当位置上（ 即 M三元组的 p指针不回溯 ）。
关键,怎样寻找 b.data的,恰当,位置？
p
1
2
3
4
q
3
5
方法 2,快速 转置如果能 预知 M矩阵 每一列 (即 T的每一行 )的 非零元素个数,又能预知 第一个非零元素 在 b.data中的 位置,则扫描 a.data时便可以将每个元素准确定位（ 因为已知若干参考点 ）。
技巧,利用 带辅助向量 的三元组表，它正好携带每行（或列）
的非零元素个数 NUM(i)以及每行（或列）的第一个非零元素在三元组表中的位置 POS(i)等信息。
设计思路：
i 1 2 3 4 5 6
NUM(i) 2 0 2 1 1 2
POS( i ) 1 3 3 5 6 7
需要的是 按列生成的 M矩阵的辅助向量。
规律,POS(1)＝ 1
POS(i)＝ POS(i-1)+NUM(i-1)
请注意 a.data特征：每列首个非零元素必定先被扫描到。
令,M中的列变量用 col表示；
num[ col ],存放 M中第 col 列中非 0元素个数，
cpot[ col ],存放 M中第 col列的第一个非 0元素的位置，
（即 b.data中待计算的“恰当”位置所需参考点）
讨论,按列优先 的辅助向量求出后，下一步该如何操作？
由 a.data中每个元素的 列 信息，即可直接查出 b.data中的重要参考点之位置，进而可确定当前元素之位置！
col 1 2 3 4 5 6
num[col] 2 2 2 1 1 0
cpot[col] 1
规律,cpot(1)＝ 1
cpot[col] ＝ cpot[col-1] + num[col-1]
0 12 9 0 0 0
0 0 0 0 0 0
-3 0 0 0 14 0
0 0 24 0 0 0
0 18 0 0 0 0
15 0 0 -7 0 0
M
3 5 7 8 8
col 1 2 3 4 5 6
cpot[1] = 1;
for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col-1] + num[col-1];
快速转置,即按 ma中三元组次序转置，转置结果放入 b中恰当位置,此法关键是要预先确定 M中每一列第一个非零元在 mb中位置，
为确定这些位置，转置前应先求得 M的每一列中非零元个数实现,设两个数组
num[col]：表示矩阵 M中第 col列中非零元个数
cpot[col],指示 M中第 col列第一个非零元在 mb中位置显然有,cpot[1]=1;
cpot[col]=cpot[col-1]+num[col-1]; (2?col?ma[0].j)
1 3 5 7 8 8 9
col
num[col]
cpot[col]
1
2
2
2
3
2
4
1
5
0
6
1
7
0
7600070015
00000180
00002400
01400003
0000000
00009120
M
算法分析,T(n)=O(M的列数 n+非零元个数 t)
若 t 与 m?n同数量级，则 T(n)=O(m?n)
方法 2,快速 转置
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
ma
i j v
mb
col
num[col]
cpot[col]
1
1
2
2
3
2
3
5
2
4
7
1
5
8
0
6
8
1
7
9
0
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
p
p
p
p
p
p
p
p
4 62 9
753
0
1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
8
7600070015
00000180
00002400
01400003
0000000
00009120
M
Status FastTransposeSMatrix（ TSMatirx M,TSMatirx &T）
{ T.mu = M.nu ;T,nu = M.mu ; T.tu = M.tu ;
if ( T.tu ) {
creatpos( M );
for ( p =1; p <=M.tu ; p++ ) { //p指向 a.data，循环次数为非 0元素总个数 tu
col =M.data[ p ],j ; q =cpos [ col ]; //查辅助向量表得 q，即 T中位置
T.data[q].i = M.data[p],j; T.data[q].j = M.data[p],i;
T.data[q],value = M.data[p],value;
++cpos[col] ; //重要语句！ 修改列坐标值,供 同一列 下一非零元素定位 !
}
}
return OK;
}
快速转置算法描述,
void creatpos( TSMatrix M )
{ for (col = 1; col <=M.nu; col++ ) num[col] =0;
for ( i = 1; i <=M.tu; i ++ ) ++num [M.data[t].j] ;
rpos[ 1 ] =1;
for ( col = 2; col <=M.nu; col++ ) rpos[col ] = rpos[col-1]+num [col-1 ] ;
}
const MAXMN = 100
int num[],rpos[];
1,与常规算法相比，附加了 生成辅助向量表 的工作。增开了 2
个长度为列长的数组 (num[ ]和 cpos[ ]）。
传统转置,O(mu*nu) 压缩转置,O(mu*tu)
压缩快速转置,O(nu+tu)——牺牲空间效率换时间效率。
快速转置算法的效率分析,
2,从时间上，此算法用了 4个并列的单循环，而且其中前 3个单循环都是用来产生辅助向量表的。
for(col = 1; col <=M.nu; col++) 循环次数＝ nu;
for( i = 1; i <=M.tu; i ++) 循环次数＝ tu;
for(col = 2; col <=M.nu; col++) 循环次数＝ nu;
for( p=1; p<=M.tu ; p++ ) 循环次数＝ tu;
该算法的时间复杂度＝ (nu*2)+(tu*2)=O(nu+tu）
讨论,最恶劣情况是 tu=nu*mu(即矩阵中全部是非零元素），
而此时的时间复杂度也只是 O(mu*nu)，并未超过传统转置算法的时间复杂度。
小结：
三元组顺序表又称 有序的双下标法,它的特点是，非零元在表中按行序有序存储，因此 便于进行依行顺序处理的矩阵运算 。然而，若需 随机 存取某一行中的非零元，则需从头开始进行查找。
行逻辑联接的顺序表修改前述的稀疏矩阵的结构定义，增加一个数据成员 rpos,其值在稀疏矩阵的初始化函数中确定。
#define MAXMN 500
typedef struct {
Triple data[MAXSIZE + 1];
int rpos[MAXMN + 1];
int mu,nu,tu;
} RLSMatrix; // 行逻辑链接顺序表类型例如：给定一组下标，求矩阵的元素值
ElemType value(RLSMatrix M,int r,int c)
{
p = M.rpos[r];
while (M.data[p].i==r &&M.data[p].j < c)
p++;
if (M.data[p].i==r && M.data[p].j==c)
return M.data[p].e;
else return 0;
}
结点,非零元的信息 (三元组 )、所在行和列的后继链域十字,每一个非零元结点既是某行链表中的一个结点，
又是某列链表中的一个结点。
稀疏矩阵的规模,行数、列数以及非零元的个数
3 0 0 5
0 -1 0 0
2 0 0 0
1 1 3 1 4 5
2 2 -1
3 1 2
^ ^
^ ^
^ ^3 4 4
^
2、十字链表稀疏矩阵的十字链表表示用 十字链表 表示用途,方便稀疏矩阵的加减运算；
方法,每个非 0元素占用 5个域 。
rightdown
vji
同一列中下一非零元素的指针 同一行中下一非零元素的指针十字链表的特点：
① 每行非零元素链接 成带表头结点的循环链表；
② 每列非零元素也链接 成带表头结点的循环链表。
则每个非零元素既是行循环链表中的一个结点；又是列循环链表中的一个结点，即 呈十字链状。
以稀疏矩阵为例：
1221311H
1
941
-1223 12 0 5
0 -1 0 0
2 0 0 0
2、十字链表
M,c h e a d
M,rh e a d
3 0 0 5
0 -1 0 0
2 0 0 0
1 1 3 1 4 5
2 2 -1
3 1 2
^
^^
^ ^
^ ^
十字链表,设行指针数组和列指针数组，分别指向每行、
列第一个非零元
typedef struct node
{ int row,col,val;
struct node *down,*right;
} Node;
row col val
down right
34008
000
450
003
A
1 1 3
4 1 8
2 2 5 2 3 4
^
^ ^
^
^ ^ ^
结点定义
3 4
7
0 0 3 0 3 0 3 0
0 0 1 1 4 3 4 2
0 0 2 2 2 2 3 9
0 0
0 0 3 1 4 3 2 6 3 4 -5
0 0 0
1
HEAD
4 0 0 2
0 2 9 0
4 6 0 -5
从键盘接收信息建立十字链表算法算法分析,T(n)=o(t?s)
其中,t——非零元个数
s= max(m,n)
令 q=NULL,p=rh[r-1],
(1) 寻找插入位置,当 p!=NULL且 c>p->col时,p和 q右移
(2) 插入：
a、若 p==NULL且 q==NULL，即本行空,则 rh[r-1]==s;
b,若 p==NULL,q!=NULL,即走到行末，则 q->right=s
c,若 c==p->col,则修改 p->val
d,若 c<p->col且 q==NULL,则在 p之前插入 s,即 s是行链表中第一个结点，令 rh[r-1]=s; s->right=p;
e,若 c<p->col且 q!=NULL,则在 p之前插入 s，
即 s->right=p; q->right=s;
4 1 8
^ ^
2 3 4
^ ^
m=4,n=3
1,1,3
2,2,5
2,3,4
4,1,8
2,1,7
1 1 3
^^
2 1 7
^ ^
2 2 5
^ ^
typedef struct OLNode {
int i,j; // 行下标和列下标
ElemType e; // 非零元的值
struct OLNode*right,*down; // 该非零元所在行表和列表的后继链域
} OLNode,*OLink;
typedef struct {
OLink *rhead,*chead; // 行和列链表头指针
int mu,nu,tu; // 行数、列数和非零元个数
} CrossList;
查找算法
void CrossSearch( CrossList &M,ElemType x )
{ i = 0;
p = *(M.rhead+i);
while ( i<M.mu ) {
if ( !p ) { i++; p = *(M.rhead+i); }
else {
if ( p.e==x ) cout <<?(? << p->i <<?,? << p->j <<?)? << endl;
p = p->rnext;
}
}
}
1.熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。
2.熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。
3.了解串的堆存储结构以及在其上实现串操作的基本方法。
4.理解串匹配的 KMP算法，熟悉 NEXT函数的定义，学会手工计算给定模式串的 NEXT函数值和改进的 NEXT函数值。
5.了解串操作的应用方法和特点。
6.了解数组的两种存储表示方法,并掌握数组在以行为主的存储结构中的地址计算方法 。
7.掌握对特殊矩阵进行压缩存储时的下标变换公式 。
8.了解稀疏矩阵的两类压缩存储方法的特点和适用范围,领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法 。
本章总结
!
问答题实验五 停车场管理设停车场内只有一个可停放几辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满几辆汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，
由于停车场是狭长的通道，在它之后开入停车场的车辆必须先退出车场为它让路，待该辆车开出大门外后，为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走。试设计一个停车管理程序。
…入口 出口 …
大门北便道 停车场分析,汽车在停车场内进出是按照栈的运算方式来实现的，
先到的先进停车场；停车场的汽车离开停车场时，车场内其他汽车为该辆汽车让路，也是按栈的方式进行；汽车在便道上等候是按队列的方式进行的。因此，将停车场设计成一个栈，汽车让路也需要另一个栈来协助完成，汽车进出便道用队列来实现。
算法描述：
1、接受命令（ A:入,D:出）和车号，若是汽车要进停车场，
先判断停车场栈是否满，若不满，则汽车入栈，否则汽车入便道队列等候。
2、若是汽车要离开停车场，为该汽车让路，将停车场栈上若干辆汽车入临时栈，等这辆汽车出停车场后，临时栈中的汽车出栈，再回到停车场栈，然后看便道队列是否为空，若不空，
则说明有汽车等候，从队头取出汽车号，让该车入停车场栈。
3、重复 1,2直到为退出命令（车号为 0或负数）。
【 课前思考 】
为什么顺序表以及其它线性结构的顺序存储结构都可以用 "一维数组 "来描述？
因为在高级编程语言中实现的一维数组正是用的这种顺序存储的映象方式。
从数据结构的观点来说,串是一种特殊的线性表 ;但就数据类型而言,串不是线性表 。
"串就是线性表 "的结论是否正确？
5.1 串类型的定义
5.2 串的表示和实现
5.3 串的模式匹配算法
5.4 串操作应用举例
5.5 数组的定义
5.6 数组顺序存储的表示和实现
5.7 矩阵的压缩存储
【 学习目标 】
1.理解 串 类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。
理解串类型的各种存储表示方法。
理解串匹配的各种算法。
2.理解数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在 以行为主 的存储表示中的地址计算方法；
3.掌握特殊矩阵的存储压缩表示方法；
4.理解稀疏矩阵的两类存储压缩方法的特点及其适用范围,掌握以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法 ；
【 重点和难点 】
1.重点了解串类型定义以及串的实现方法 —串的匹配,
学会利用这些基本操作来实现串的其它操作；
掌握 随机稀疏矩阵的压缩存储表示方法和运算实现串、串的匹配、数组、特殊矩阵、稀疏矩阵、三元组、
十字链表。
【 知识点 】
课后练习题,5.1,5.2,5.3,5.4,5.6,5.11,5.12
记为,s = ―a0 a1 ….,a n-1‖ (n≥0 )
串名 串值 (用 双引号 括起来）
串中字符个数 (n≥0),n=0 时称为空串? 。
由一个或多个空格符组成的串。
串 s中任意个连续的字符序列叫 s的子串 ; S叫 主串 。
子串的第一个字符的序号。
字符在串中的序号。
串长度相等，且对应位置上字符相等。
串 即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。
若干术语：
串长：
空白串：
子串：
子串位置：
字符位置：
串相等：
隐含结束符‘ /0‘,
即 ASCII码 NUL
5.1 串的定义和操作
串 （ string）,由 0个或多个字符组成的有限序列,
也称字符串 。 记为,s=―a0a1a2…… an-1‖ (n≥ 0),
其 中 s 是 串 的 名,a0a1a2…… an-1 是 串 的 值,
ai(0≤ i≤ n-1)可以是字母,数字或其它字符 。
串长度,串中字符的数目 n。
空串,不含任何字符的串,串长度 =0
空格串,仅由一个或多个空格组成的串
子串,由串中任意个连续的字符组成的子序列
主串,包含子串的串。
串相等的条件,当两个串的长度相等且各个对应位置的字符都相等时才相等。
注意,(1) 串值必须用一对单引号括起来
(2) 串值大小是按 词典 次序进行比较的
StrCompare(?data‘,‘Stru‘)<0
StrCompare(?cat‘,‘case‘)>0
显然,只有在两个串的长度相等且每个字符一一对等的情况下称两个串相等 。
练 1,串是由 字符组成的序列，一般记为 。
练 2,现有以下 4个字符串：
a =?BEI‘ b =?JING‘ c =?BEIJING‘ d =?BEI JING‘
问：① 他们各自的长度？
② a是哪个串的子串？在主串中的位置是多少？
a =3,b =4,c = 7,d=8
a是 c和 d的子串，在 c和 d中的位置都是 1
练 3,空串和空白串有无区别？
答,有区别。 空串 (Null String)是指长度为零的串；而空白串 (Blank String),是指包含一个或多个空白字符
‘ ’ (空格键 )的字符串。
0个或多个
S=‘a1a2……a n‘
1.串的数据对象约束为字符集。
2,线性表的基本操作大多以?单个元素?为操作对象，而串的基本操作通常以?串的整体?作为操作对象。
串的逻辑结构和线性表的区别,
补充,C语言中常用的串运算串比较,int strcmp(chars1,char s2); //StrCompare(S,T)
求串长,int strlen(char s); //StrLength(S)
串连接,char strcat(char *to,char *from) //Concat(&T,S1,S2)
子串定位,char strchr(char *s,char *c); //Index(S,T,pos)
……
注：用 C处理字符串时，要调用标准库函数 #include<string.h>
gets( char *s ) 输入一个串；
puts( char *s ) 输出一个串；
strcat(char *s1,char *s2 ) 串联接函数；
strcpy( char *s1,char *s2 ) 串复制函数；
strcmp( char *s1,char *s2 ) 串比较函数；
strlen( char *s ) 求串长函数；
表示空串，空串的长度为零。
StrAssign (&T,chars)
初始条件,chars是字符串常量。
操作结果,把 chars赋为 T的值。
StrCopy (&T,S)
初始条件,串 S 存在。
操作结果,由串 S复制得串 T。
DestroyString (&S)
初始条件,串 S存在。
操作结果,串 S被销毁。
StrEmpty (S)
初始条件,串 S存在。
操作结果,若 S为空串,则返回 true,否则返回 false.
串的基本操作
StrCompare (S,T)
初始条件,串 S 和 T 存在。
操作结果,若 S?T，则返回值?0;
若 S?T，则返回值?0;
若 S?T，则返回值?0.
StrLength (S)
初始条件,串 S存在。
操作结果,返回 S的元素个数,称为串的长度,
Concat (&T,S1,S2)
初始条件,串 S1和 S2存在。
操作结果,用 T返回由 S1和 S2联接而成的新串。
SubString (&Sub,S,pos,len)
初始条件：
操作结果,用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。
串 S 存在,1≤pos≤StrLength(S) 且 0≤len≤StrLength(S)-pos+1。
例如,Concate( T,?man?,?kind?),
求得 T =?mankind?
例如,StrCompare(?data?,?state?)<0
StrCompare(?cat?,?case?)>0
例如,SubString( sub,?commander?,4,3 )
子串为“串”中的一个字符子序列求得 sub =?man? ;
SubString( sub,?commander?,1,9 )
SubString( sub,?commander?,9,1 ) 求得 sub =?r?
求得 sub =?commander?
SubString( sub,?commander?,4,7 )
sub =?
SubString( sub,?beijing?,7,2 ) =?
sub =?
SubString(?student?,5,0 ) =起始位置和子串长度之间存在约束关系长度为 0 的子串为“合法”串
Index( S,T,pos )
初始 条件：串 S和 T存在,T是非空串,1≤pos≤StrLength(S)。
操作结果,若主串 S 中存在和串 T 值相同的子串,则返回它在主串 S 中第 pos个字符之后第一次出现的位置 ; 否则函数值为 0。
假设 S =?abcaabcaaabc?,T =?bca?
Index(S,T,1) = 2;
Index(S,T,3) = 6;
Index(S,T,8) = 0;
―子串在主串中的位置”意指子串中的第一个字符在主串中的位序。
Replace (&S,T,V)
初始条件,串 S,T和 V 均已存在，且 T 是非空串。
操作结果,用 V 替换主串 S 中出现的所有与（模式串） T相等的不重叠 的子串。
例如,假设 S =?abcaabcaaabca?,T =?bca?
若 V =?x?,则经置换后得到 S =?axaxaax?
若 V =?bc?,则经置换后得到 S =?abcabcaabc?
b a b a b
例：假设 S="abcacabcaca",T="abca"和 V="x"，则置换之后的
S="xcxca"。
注意定义中 "不重叠 "三个字，若上例中的 V="ab"时，则置换后的结果应该是
S=" abcabca"，而不是 "abbca"。
串赋值 StrAssign、串复制 Strcopy、
串比较 StrCompare、求串长 StrLength、
串联接 Concat以及求子串 SubString
等六种操作构成串类型的最小操作子集。
在上述抽象数据类型定义的 13种操作中，
即：这些操作不可能利用其他串操作来实现，
反之，其他串操作（除串清除 ClearString和串销毁 DestroyString外）可在这个最小操作子集上实现。
例如，可利用 串比较,求串长和求子串等操作实现定位函数 Index( S,T,pos )。
StrCompare(SubString(S,i,StrLength(T)),T )
S串
T串 T串
i
pos n-m+1
算法的基本思想为：
0
int Index (String S,String T,int pos) {
// T为非空串。若主串 S中第 pos个字符之后存在与 T相等的子串，
// 则返回第一个这样的子串在 S中的 位置，否则返回 0
if (pos > 0) {
}
return 0; //S中不存在与 T相等的子串
}
n = StrLength(S); m = StrLength(T); i = pos;
while ( i <= n-m+1) {
} // while
SubString (sub,S,i,m);
if (StrCompare(sub,T) != 0) ++i ;
else return i ;
串的置换函数：
S串
T串 V串
V串
pos pos
sub
i
news 串
sub
= i+m pos
n-pos+1
void replace(String& S,String T,String V) {
}
while ( pos <= n-m+1 && i) {
i=Index(S,T,pos);
if (i!=0) {
SubString(sub,S,pos,i-pos); // 不置换子串
Concat(news,sub,V);
pos = i+m;
}
}
SubString(sub,S,pos,n-pos+1); // 剩余串
Concat( S,news,sub );
n=StrLength(S); m=StrLength(T); pos = 1;
StrAssign(news,NullStr); i=1;
串 的逻辑结构和 线性表 极为相似,区别 仅在于 串的数据对象约束为字符集 。
串的基本操作和线性表有很大差别。
在线性表的基本操作中，大多以 单个元素 作为操作对象；
在串的基本操作中，通常以 串的整体 作为操作对象。
串的 整体操作
– 赋值 StrAssign(S,―Data Structure‖)
– 复制 StrCopy(T,S) // T<=S,T为? Data Structure‖
– 比较 StrCompare(S,T)
– 连接 Concat(T,―Data‖,―Structure‖) //T为? DataStructure‖
– 取子串 SubString(sub,S,2,5) // sub为? ata S‖
– 子串在主串中的定位 Index(S,―a‖,3) // 4
– 子串置换 Replace(S,―a‖,―b‖) // S为? Dbtb Structure‖
– 子串插入 StrInsert(S,3,―aha‖) // ―Daahata Structure‖
– 子串删除 StrDelete(S,3,5) // ―Daructure‖
设 s =‘I AM A STUDENT‘,t =‘GOOD‘,
q=‘WORKER‘ 。求：
练习：
StrLength(s) ＝
StrLength(t) ＝
SubString(s,8,7)=
SubString(t,2,1)=
Index(s,?A‘)=
Index(s,t)=
Replace(s,?STUDENT‘,q)=
14
4
STUDENT‘
O‘
3
0 （ s中没有 t！）
’ I AM A WORKER‘
再问,Concat(SubString(s,6,2),Concat(t,SubString(s,7,8))) ＝？
一、串的定长顺序存储表示二、串的堆分配存储表示三、串的块链存储表示
5.2 串的表示和实现
5.2串的表示和实现
定长顺序存储表示 ——用一组地址连续的存储单元存储串值的字符序列
堆分配存储表示 ——用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。
串的块链存储表示 ——链式方式存储首先强调,串与线性表的运算有所不同，是以? 串的整体? 作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。
串有三种机内表示方法：
顺序存储链式存储定长顺序存储特点,用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的 上界预先给出,故称为静态存储分配。
例如,#define Maxstrlen 255 //用户可用的最大串长
typedef unsigned char SString[Maxstrlen+1];
SString s; //s是一个可容纳 255个字符的顺序串。
注：
一般用 SString[0]来存放串长信息；
C语言约定在串尾加结束符 ‘ \0?，以利操作加速，但不计入串长；
若字符串超过 Maxstrlen 则自动截断（因为静态数组存不 进去）。
讨论,想存放 超长 字符串怎么办？ ——静态数组有缺陷！
实现方式,两串连接和 求子串改用 动态 分配的一维数组 —— ―堆”！
5.2.1 串的定长顺序存储表示
void Concat_Sq( char S1[ ],char S2[ ],char T[ ]) {
j=0; k=0;
while ( S1[j] != '\0' ) T[k++] = S1[j++]; //复制串 S1
j = 0;
while ( S2[j] != '\0' ) T[k++] = S2[j++]; //接着复制串 S2
T[k] = '\0';
} // Concat
#define MAXSTRLEN 255 //串长度最大为 255
char SString[MAXSTRLEN];
void SubString_Sq( char Sub[ ],char S,int pos,int len) {
// 用 Sub返回串 S的第 pos个字符起长度为 len的子串。
// 其中,0≤pos<StrLength(S) 且 0≤len≤StrLength(S)-pos。
slen=StrLength_Sq(S); //求取顺序存储表示的字符串 S的串长度
if ( pos<0||pos>slen-1||len<0||len>slen-pos ) ERROR( "参数不合法 ");
for ( j = 0; j < len; j++ ) Sub[ j ] = S[ pos + j ];
Sub[len] = '\0';
} // SubString
将串 S中从第 pos个字符开始长度为 len的字符序列复制到串 Sub中 （注：串 Sub的预留长度与 S一样）
typedef struct {
char *ch; // 若是非空串,则按串实用长度分配存储区,否则 ch 为 NULL
int length; // 串长度
} HString;
5.2.2 串的堆分配存储表示通常,C/C++语言中提供的串类型就是以这种存储方式实现的。
系统利用函数 malloc( ) /new和 free( )/delete 进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为 堆 。
C语言中的串以一个空字符为结束符，串长是一个隐含值。
这类串操作 实现的算法 为,先为新生成的串分配一个存储空间，然后进行串值的复制。
void StrInsert_ HSq (char *S,int pos,char *T)
{ //1≤pos≤StrLength(S)+1。在串 S的第 pos个字符 之前 插入串 T
slen=StrLength_HSq (S); tlen=StrLength_HSq (T);
char S1[slen +1] ; // S1作为辅助串空间用于暂存 S
if ( pos<1 || pos>slen+1 ) ERROR(" 插入位置不合法 ");
if ( tlen>0 ) {
i=0;
while ( (S1[i]=S[i])!='\0' ) i++; // 暂存串 S
S = new char[slen+tlen+1]; // 为 S重新分配空间
for ( i=0,k=0; i<pos-1; i++ ) S[k++] = S1[i];
j = 0;
while ( T[j]!= '\0' ) S[k++] = T[j++]; // 插入 T
while ( S1[i]!= '\0? ) S[k++] = S1[i++]; 串
S[k] = '\0'; // 置串 S的结束标志
}
}
void StrInsert ( char *S,int pos,char *T ) {
char *S1,*Sub;
slen = strlen(S); tlen = strlen(T);
if ( pos<1 || pos>slen+1 ) ERROR(,插入位置不合法” );
if ( tlen>0 ) {
S1 = strdup(S);
S = new char[slen+tlen+1];
Sub = s1+pos-1;
strncpy( S,S1,pos-1 );
s[pos-1] =?\0];
strcat( S,T );
strcat( S,Sub );
}
}
例：用堆实现串插入操作
5.2.3 串的块链存储表示也可用链表来存储串值，由于串的数据元素是一个字符，它只有 8 位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。
存储密度 = 数据元素所占存储位 实际分配的存储位
#define CHUNKSIZE 80 // 可由用户定义的块大小
typedef struct Chunk { // 结点结构
char ch[CUNKSIZE];
struct Chunk *next;
} Chunk;
typedef struct { // 串的链表结构
Chunk *head,*tail; // 串的 头和尾指针
int curlen; // 串的 当前长度
} LString;
S.head
S.crulen
S.tail
T h i s a s t
r i n g ^
i s
例如,在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即,同一行的串用定长结构
(80个字符 ),行和行之间用指针相联接。
实际应用时，可以根据问题所需来设置结点的大小。
讨论,法 1存储密度为 ；法 2存储密度为 ；
显然，若 数据元素很多，用法 2存储更优 —称为 块链结构链式存储特点,用链表存储串值，易插入和删除。
法 1,链表结点（数据域）大小取 1
法 2,链表结点（数据域）大小取 n(例如 n=4)
1/2 9/15=3/5
A? B? C? I NULLhead
head A B C D? E F G H? I # # # NULL
模式匹配 (Pattern Matching) 即 子串定位运算 (Index函数 ).
初始条件,串 S和 T存在,T是非空串,1≤pos≤StrLength(s)
操作结果,若主串 S中存在和串 T值相同的子串，则返回它在主串
S中第 pos个字符之后 第一次 出现的位置；否则函数值为 0。
注,S称为 被匹配的串,T称为 模式串 。若 S包含串 T，则称 匹配成功 。否则称 匹配不成功 。
算法目的,确定主串中所含子串第一次出现的位置（ 定位 ）
——即如何实现 Index(S,T,pos)函数
5.3 串的模式匹配算法
BF算法 (又称古典的、经典的、朴素的、穷举的 )
KMP算法 (特点：速度快 )
Index(S,T,pos)函数
S串
T串 T串
i
pos n-m+1
S串
T 串 T串
i
j j>m
i
j
i
j
i>n
j
T串
i
jBF算法设计思想：
将主串的第 pos个字符和模式的第 1个字符比较，
若 相等,继续逐个比较后续字符；
若 不等,从主串的下一字符（ pos+1）起，重新与第一个字符比较。
直到主串的一个连续子串字符序列与模式相等 。返回值为 S中与 T匹配的子序列 第一个字符的序号,即匹配成功。
否则，匹配失败，返回值 0,
S=?a b a b c a b c a c b a b‘T=?a b c a c‘
pos=5
int Index( char char S[],char T[],int pos ) {
I = pos; j = 1;
Slen = strlen(S); Tlen = strlen(T);
while ( i<=Slen && j<=Tlen ) {
if ( S[i]==T[j] ) { ++i,++j } //继续比较后续字符
else { i=i-j+2; j=1; } //指针回溯到 下一首位，重新开始匹配
}
if ( j>Tlen ) return i-j+1; //子串结束，说明匹配成功
else return 0;
} //Index
BF算法的实现 —即 Index()操作的实现
S=?a b a b c a b c a c b a b‘
T=?a b c a c‘
pos=5
相当于子串向右滑动一个字符位置匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。
i
j
S a b b b a a
T
朴素的模式匹配过程
a b aa b a b aa b a
模式匹配的最简单的做法是,用 T中的字符依次与 S中的字符比较：
如果 S0 = T0,S1 = T1,…,Sm-1 = Tm-1,则匹配成功,调用求子串的操作 subString(S,1,m)即是找到的子串 。 否则必有某个 i（ 0≤i≤m-1）,
使得 Si ≠Ti,这时可将 T右移一个字符,用 T中字符从头开始与 S中字符依次比较；如此反复执行,直到下面两种情况之一：或者到达某步时,Si = T0,Si+1 = T1,…,Si+m-1 = Tm-1,匹配成功,
subString(S,i+1,m)即是找到的 （ 第一个 ） 与模式 T相同的子串；或者一直将 T移到无法与 S继续比较为止,则匹配失败 。
a
第一趟匹配 a b a b c a b c a c b a b
i=3
a b c
j=3
第二趟匹配 a b a b c a b c a c b a b
i=2
a
j=1
第三趟匹配 a b a b c a b c a c b a b
i=7
a b c a c
j=5
S[2]!=t[2],该趟匹配失败 i=i- j+1,j=0
进入下趟匹配算法
i=0
i=1
S[1]!=t[0],该趟匹配失败 i=i- j+1,j=0
进入下趟
i=2
S[6]!=t[4],该趟匹配失败 i=i- j+1,j=0
进入下趟串的模式匹配算法第四趟匹配 a b a b c a b c a c b a b
i=4
a
j=1
第五趟匹配 a b a b c a b c a c b a bi=5
a
j=1
第六趟匹配 a b a b c a b c a c b a b
i=11
a b c a c
j=6
匹配成功匹配算法 2
S[3]!=t[0],该趟匹配失败 i=i- j+1,j=0
进入下趟
S[4]!=t[0],该趟匹配失败 i=i- j+1,j=0
进入下趟
j 等于 t 的串长,该趟匹配成功,返回 i=i-n
i=4
i=3
i=5
串的模式匹配算法
int Index_BF ( char S [ ],char T [ ],int pos ) {
i = pos; j = 0;
while ( S[i+j] != '\0' && T[j] != '\0' )
if ( S[i+j] == T[j] ) j ++; // 继续比较后一字符
else { i ++; j = 0; } // 重新开始新的一轮比较
if ( T[j] == '\0' ) return i; else return -1;
}
BF算法的时间复杂度讨论,若 n为主串长度,m为子串长度，则串的 BF匹配算法最坏的情况下需要比较字符的总次数为,(n-m+1)*m＝ O(n*m)
最恶劣情况是,主串前面 n-m个位置都 部分匹配 到子串的最后一位，
即这 n-m位各比较了 m次，再加上最后 m位也各比较了 1次，所以总次数为,(n-m)*m+m＝ (n-m+1)*m
一般的情况是,O(n+m) 要从最好到最坏情况统计总的比较次数,
然后取平均。
最好的情况是,一配就中！
5.4 正文编辑 —串操作应用举例文本编辑,实质是修改字符数据的形式或格式,
包括串的查找,插入,删除等基本操作 。
思路,可以利用换行符和换页符将文本划分成若干页，每页包含若干行。 页是文本串的子串，行是页的子串 。在编辑程序中，先为文本串建立相应的页表和行表，即建立各子串的存储映象，在程序中设立页指针、行指针和字符指针，分别指向当前操作的页、行和字符。进行文本编辑的过程，就是一个对行表、页表进行查找、插入或删除的过程。
假设有下列一段 C的源程序
main() {
float a,b,max;
scanf(―%f,%f‖,&a,&b);
if a>b max=a;
else max=b;
};
将此源程序看成是一个正文串,输入 内存后如图所示,
图中,↙,为换行符。
m a i n ( ) { ↙ f l o a t a,b,
m a x ; ↙ s c a n f ( " % f,% f "
,& a,& b ) ; ↙ i f a > b m
a x = a ; ↙ e l s e m a x = b ;
↙ } ; ↙
如果在某行内插入或删除若干字符,则要修改行表中该行的长度,若该行长度因插入而超出了原分配给它的存储空间,
则要为该行重新分配存储空间,并修改该行的起始位置。
例如,对上述源程序进行编辑后,其中的 105行修改成：
If (a>b) max=a;
108行修改成：
}
修改后的行表如图所示。
行号 起始地址 长度
100 200 8
102 208 17
104 225 24
105 284 19
106 266 15
108 281 2
行号 起始地址 长度
100 200 8
102 208 17
104 225 24
105 249 17
106 266 15
108 281 3
5.5 数组数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表
mnmm
n
n
nm
aaa
aaa
aaa
A
......
...............
......
......
21
22221
11211
– 数组特点
数组结构固定
数据元素同构
– 数组运算
给定一组下标，存取相应的数据元素
给定一组下标，修改数据元素的值
( )
( )
( )
( )
(
)
(
)
(
)
(
)
(
)
5.5.1 数组的定义和特点一、定义
5.5.1 数组的定义和操作
定义特殊的线性表,一个数组中，数据元素的类型是一样的；
数据元素的类型可能 是非结构的原子类型,也可能是 定长线性表 。 数组一旦被定义，它的维数和维界就不再改变。
数组 (数据结构 ) vs 数组类型 (程序设计语言中 )
数组 (数据结构 ) 反映数据元素之间的特殊逻辑关系可以用数组类型表示，也可以用链表示数组类型 体现物理表示，如 C中规定按行优先存储
ADT Array
初始化、注销、存取元素值 ----无插入、删除操作
二维数组
a00 a01 … a0,n-1
a10 a11 … a1,n-1
… … … …
am-1,0 am-1,1 … am-1,n-1
将二维数组看成是一个定长线性表，即
A = ( a0,a1,.,,,ap ) p=m-1或 n -1
其中每个数据元素也是一个定长线性表，即
aj = ( a0j,a1j,.,,,am-1,j ) 0≤j ≤ n -1 aj是 列向量 形式的线性表
ai = ( ai0,ai1,.,,,ai,n-1 ) 0≤i ≤ m -1 ai是 行向量 形式的线性表
Am× n =
5.5.1 数组的定义和操作数组,由一组名字相同、下标不同的变量构成注意,本章所讨论的数组与高级语言中的数组有所区别：
高级语言中的数组是顺序结构；
本章的数组既可以是顺序的，也可以是链式结构。
答,对的 。因为：
① 数组中各元素具有 统一的类型 ；
② 数组元素的下标一般具有 固定的上界和下界,即数组一旦被定义，它的维数和维界就不再改变。
③数组的 基本操作比较简单,除了结构的初始化和销毁之外,只有存取元素和修改元素值的操作 。
讨论：“数组的处理比其它复杂的结构要简单”，对吗？
5.5.1 数组的定义和操作二维数组的特点：
一维数组的特点,1个下标,ai 是 ai+1的直接前驱
2个下标,每个元素 ai,j受到两个关系
（行关系和列关系）的约束：
一个 m× n的二维数组可以看成是 m行的一维数组，或者 n列的一维数组。
N维数组的特点,n个下标,每个元素受到 n个关系约束一个 n维数组可以看成是 由若干个 n－ 1维数组组成的线性表。
a11 a12 … a 1n
a21 a22 … a 2n
… … … …
am1 am2 … a mn
Amn=
5.5.1 数组的定义和操作
5.5.2 数组的顺序存储表示和实现问题,计算机的存储结构是一维的，而数组一般是多维的，
怎样存放？
解决办法,事先约定按某种次序将数组元素排成一列序列，
然后将这个线性序列存入存储器中。
例如,在二维数组中，我们既可以规定按 行 存储，也可以规定按 列 存储 。
注意：
若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；
约定的次序不同，则计算元素地址的公式也有所不同；
C和 PASCAL中一般采用行优先顺序； FORTRAN采用列优先。
通常有两种顺序存储方式：
以行序为主序
以列序为主序
a11 a12 …….,a 1n
a21 a22 …….,a 2n
am1 am2 …….,a mn
………………….
Loc( aij)=Loc(a11)+[(i-1)n+(j-1)]*l
按行序为主序存放
amn
…….,
am2
am1
……….
a2n
…….,
a22
a21
a1n
…….
a12
a110
1
n-1
m*n-1
n
按列序为主序存放
0
1
m-1
*n-1
m
amn
…….,
a2n
a n
……….
am2
…….,
a22
a12
am1
…….
a21
a11
a11 a12 …….,a1n
a21 a22 …….,a2n
am1 am2 …….,amn
………………….
Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l
补充：计算二维数组元素地址的通式设一般的二维数组是 A[c1..d1,c2..d2],这里 c1,c2不一定是 0。
无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（ 这样数组中的任一元素便可以随机存取！ ）,
二维数组 列优先 存储的通式为：
LOC(aij)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L
ac1,c2 … a c1,d2
… aij …
ad1,c2 … a d1,d2
Amn=
单个元素长度aij之前的行数数组基址 总列数，即第 2维长度
aij本行前面的元素个数
① 开始结点的存放地址（即基地址）
②维数和每维的上、下界；
③每个数组元素所占用的单元数则 行优先 存储时的地址公式为：
LOC(aij)=LOC(ac1,c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L
Loc(j1,j2,… jn)=LOC(0,0,… 0)＋
若是 N维数组，其中任一元素的地址该如何计算？
n
i
ii
1
jC
其中 Cn=L,Ci-1=bi× Ci,1<i≤n
一个元素长度数组基址前面若干元素占用的地址字节总数第 i维长度 与所存元素个数有关的系数，可用递推法求出例如：
称为基地址或基址。
以“行序为主序”的存储映象二维数组 A中任一元素 ai,j的存储位置
LOC(i,j) = LOC(0,0) + (b2× i＋ j)×
a0,1a0,0 a0,2
a1,0 a1,1 a1,2
a0,1a0,0 a0,2 a1,0 a1,1 a1,2
L
L
在 C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，
typedef elemtype array2[m][n];
等价于：
typedef elemtype array1[n];
typedef array1 array2[m];
数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。
5.5.2 数组的顺序表示和实现例,已知二维数组 Am,m按行存储的元素地址公式是：
Loc(aij)= Loc(a11)+[(i-1)*m+(j-1)]*K,按列存储的公式是？
Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K （尽管是方阵，但公式仍不同）
例,一个二维数组 A，行下标的范围是 1到 6，列下标的范围是 0
到 7，每个数组元素用相邻的 6个字节存储，存储器按字节编址。那么，这个数组的体积是 个字节。288
例,设数组 a[1…60,1…70]的基地址为 2048，每个元素占 2个存储单元，若以列序为主序顺序存储，则元素 a[32,58]的存储地址为 。8950
LOC(aij)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L
得,LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1)]*2＝ 8950
答,请注意审题！ 利用列优先通式：
答,Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288
5.5.3 数组的应用利用数组降低算法的复杂度。
例：寻求两个字符串中的最大公共子串。
设 string1 =,sgabacbadfgbacst”,
string2 =“gabadfgab”
最长公共子串为 badfg。
算法的复杂度：
时间复杂度,O(m*n)
空间复杂度,O(m*n)
1
1 1 1 1
1
1
1
11
1
1 1
1
1
1
1
1
1
1
1
1
1
1
g
a
b
a
d
f
g
a
b
s g a b a c b a d f g b a c s t
串的对应矩阵子串集,Gab,3 a,1 b,1 a,1
最大长度,3,位置序号,1最大长度,0,位置序号,-
a,1 gaba,4 a/b,1
最大长度,4,位置序号：
badfg,5 a,1
最大长度,5,位置序号,6
a,1 ba,2 g,1 a,1位置数,6号，长度,5
子串,badfg
程序
void diagmaxl( int mat[ ][ ],int
&maxlen,int jpos )
{
maxlen = 0; jpos = -1;
istart = 0;
for ( k=-(m-1); k<=n-1; k++ ) {
i = istart; j = i-k;
diagscan(i,j);
if (k>=0) istart++;
}
}
void diagscan( int I,int j )
{
eg = 0; len = 0;
while ( i<n && j<m ) {
if ( mat[i][j]==1 ) {
len++;
if ( !eg ) { sj = j; eg = 1; }
}
else if ( eg ) {
if ( len>maxlen ) { maxlen = len; jpos = sj; }
eg = 0; len = 0;
}
i++; j++;
}
}
int maxsamesubstring ( char *string1,char *string2,char *&sub )
{ p1 = string2; p2 = string1;
for ( i=0; i<n; i++ )
for ( j=0; j<m; j++ )
if ( *(p1+i)==*(p2+j) ) mat[i][j] = 1; else mat[i][j] = 0;
diagmaxl( mat,maxlen,jpos );
if ( maxlen==0 ) *sun =?\0?; else subString( sub,string1,jpos,
maxlen );
return maxlen;
}
void SubString( char *&sub,char *str,int s,int len )
{ char *p;
int k;
sub = new char[len+1];
p = str+s-1; k=len;
while ( k ) { *sub++ = *p++; k--; }
*sub =?\0?;
sub = sub-len;
}
在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，
就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为 1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为 1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，我们可以对这类矩阵进行 压缩存储,即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。
5.6 矩阵的压缩存储以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题,
1) 零值元素占了很大空间 ;
2) 计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零 ;
1) 尽可能少存或不存零值元素 ;
解决问题的原则,
2) 尽可能减少没有实际意义的运算 ;
3) 操作方便 ; 即,能尽可能快地找到与下标值 (i,j) 对应的元素 ;
能尽可能快地找到同一行或同一列的非零值元 ;
5.6 矩阵的压缩存储讨论：
1,什么是压缩存储？
若多个数据元素的 值都相同,则只分配一个元素值的存储空间，且零元素不占存储空间。
2,所有二维数组（矩阵）都能压缩吗？
未必，要看矩阵是否具备以上压缩条件。
3,什么样的矩阵具备以上压缩条件？
一些特殊矩阵，
如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。
4,什么叫稀疏矩阵？
矩阵中非零元素的个数较少（一般小于 5%）
重点介绍稀疏矩阵的压缩和相应的操作。
在一个 n阶方阵 A中，若元素满足下述性质：
aij=aji 0≦i,j≦n -1
则称 A为对称矩阵。
对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。
5.6.1 特殊形状矩阵的存储表示所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。
1、对称矩阵
5.3 矩阵的压缩存储
对称矩阵
– 为每一对对称元分配一个存储空间,n2?n(n+1)/2
– 以行序为主序存储下三角中的元 ——下三角矩阵
a11
a21 a22
… … …
an1 an2 … ann?
jii
jj
jij
ii
k
当当
1
2
)1(
1
2
)1(
a11 a21 a22 a31 … an1 … ann
k = 0 1 2 3 n(n-1)/2 n(n+1)/2-1
对称矩阵定义,n阶矩阵 A中的元满足 aij= aji ( 1≤ i,j≤n)
a00 a01 … a 0 n-1 a00 0 … 0
0 a11 … a 1 n-1 a10 a11 … 0
………………….,……………..
0 0 … a n-1 n-1 an-1 0 an-1 1 … a n-1 n-1
(a)上三角矩阵 (b)下三角矩阵
2、三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。
上三角矩阵,它的下三角 (除主对角线 )中的元素均为常数。
下三角矩阵,它的主对角线上方均为常数。
三角矩阵常数为零
2、三角矩阵
a11 0 0…….,0
a21 a22 0…….,0
an1 an2 an3…….,ann
…………………,0
Loc(aij)=Loc(a11)+[( +(j-1)]*li(i-1)2
按行序为主序,a11 a21 a22 a31 a32 an1 ann…..,…...
k = 0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
1、若 i≧ j，则 ai j在 下三角形 中。
ai j之前的 i行 (从第 0 行到第 i-1行 )一共有,
1+2+…+i=i(i+1)/2个元素，
在第 i行上,ai j之前恰有 j个元素
（即 ai0,ai1,ai2,…,aij-1），
因此有,k=i*(i+1)/2+j 0≦ k<n(n+1)/2
2、若 i<j，则 aij是在 上三角 矩阵中。
因为 aij=aji，
所以只要交换上述对应关系式中的 i和 j即可得到：
k=j*(j+1)/2+i 0≦ k<n(n+1)/2
3、对角矩阵
a11 a12 0 ……………,0
a21 a22 a23 0…………… 0
0 0… an-1,n-2 an-1,n-1 an-1,n
0 0 … … an,n-1 ann.
0 a32 a33 a34 0……… 0
……………………………
Loc(aij)=Loc(a11)+2(i-1)+(j-1) |i-j|<=1
按行序为主序,a11 a12 a21 a22 … an-1,n an,n-1 ann
k = 1 2 3 4 3n-2
假设 m 行 n 列 的矩阵含 t 个非零元素,
则称为 稀疏因子通常认为 0.05 的矩阵为稀疏矩阵
nm t
5.6.2 稀疏矩阵的压缩存储何谓稀疏矩阵？
7600070015
00000180
00002400
01400003
0000000
00009120
M
M由 { (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)唯一确定稀疏矩阵
定义,非零元较零元少，且分布没有一定规律的矩阵
压缩存储原则,只存矩阵的行列维数和每个非零元的行列下标及其值一、稀疏矩阵的压缩存储问题：
如果只存储 稀疏矩阵中的非零元素，那这些元素的 位置信息 该如何表示？
解决思路：
对每个非零元素 增开 若干存储单元，例如存放其所在的行号和列号，便可准确反映该元素所在位置。
实现方法：
将每个非零元素用一个三元组 （ i,j,aij）来表示，
则每个 稀疏矩阵可用一个 三元组表 来表示。
二、稀疏矩阵的操作
1、三元组顺序表随机稀疏矩阵的压缩存储方法
稀疏矩阵的三元组顺序表表示
– 存储非零元,记录值、位置 (行下标和列下标 )——
三元组
– 三元组的排列次序,这里以行序为主序，也可选择以列序为主序 ——有序表
– 稀疏矩阵的规模,行数、列数以及非零元的个数
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0
6 7 8
1 2 12
1 3 9
3 1 –3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
1、三元组顺序表
#define MAXSIZE 125000 //设非零元素最大个数 125000
typedef struct {
int i; //元素行号
int j; //元素列号
ElemType e; //元素值
} Triple;
typedef struct {
Triple data[MAXSIZE+1]; //三元组表，以行为主序存入一维向量 data[ ]中
int mu; //矩阵总行数
int nu; //矩阵总列数
int tu; //矩阵中非零元素总个数
} TsMatrix;
三元组表的顺序存储表示稀疏矩阵的压缩存储方法
–顺序存储结构三元组表
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
ma
i j v
行列下标 非零元值
7600070015
00000180
00002400
01400003
0000000
00009120
M
#define M 20
typedef struct node
{ int i,j;
int v;
} Node;
Node ma[M];
三元组表所需存储单元个数为 3(t+1)
其中 t为非零元个数
0
1
2
3
4
5
6
7
8
ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数链式存储结构 -- 带行指针向量的单链表表示
每行的非零元用一个单链表存放
设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空
表头结点与单链表结点类型定义 0
typedef struct node
{ int col;
int val;
struct node *link;
} Node;
typedef struct Node *TD;
02000
00000
00021
00100
70003
A
^
1 3 5 7
3 -1
1 -1 2 -2
4 2 ^
^
^
^
需存储单元个数为 3t+m
例：三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的,和 。行下标 列下标 元素值例,写出右图所示稀疏矩阵的压缩存储形式。
0 12 9 0 0 0
0 0 0 0 0 0
-3 0 0 0 14 0
0 0 24 0 0 0
0 18 0 0 0 0
15 0 0 -7 0 0
(( 1,2,12),(1,3,9),(3,1,-3),(3,5,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))
法 1,用线性表表示
9 0 0 0
3 0 0 0 14 0
0 24 0 0 0
18 0 0 0 0
0 7 0 0
法 2,用三元组矩阵表示：
0 12 9 0 0 0
0 0 0 0 0 0
-3 0 0 0 14 0
0 0 24 0 0 0
0 18 0 0 0 0
15 0 0 -7 0 0
1 2 12
1 3 9
3 1 -3
3 5 14
4 3 24
5 2 18
6 1 15
6 4 -7
注意,为更可靠描述，
通常再加一行总体信息：
总行数、总列数、非零元素总个数
6 6 8
i j value
稀疏矩阵压缩存储的 缺点：将失去随机存取功能
0
1
2
3
4
5
6
7
8
法 3,用 带辅助向量 的三元组表示。
方法,增加 2个辅助向量：
① 记录每行非 0元素个数,用 NUM(i)表示 ;
② 记录稀疏矩阵中每行第一个非 0元素在三元组中的行号,用 POS(i)表示。
76531
211202NUM( i)
6543
POS( i )
21i
0 12 9 0 0 0
0 0 0 0 0 0
-3 0 0 0 14 0
0 0 24 0 0 0
0 18 0 0 0 0
15 0 0 -7 0 0
-746
1516
1825
2434
1453
-313
931
1221
866
vji
0
1
2
3
4
5
6
7
8
3
用途,通过三元组 高效访问稀疏矩阵 中任一非零元素。
规律,POS(1)＝ 1
POS(i)＝ POS(i-1)+NUM(i-1)
稀疏矩阵的操作
0 12 9 0 0 0
0 0 0 0 0 0
-3 0 0 0 14 0
0 0 24 0 0 0
0 18 0 0 0 0
15 0 0 -7 0 0
0 0 –3 0 0 15
12 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 14 0 0 0
0 0 0 0 0 0
(1,2,12)
(1,3,9 )
(3,1,-3)
(3,5,14)
(4,3,24)
(5,2,18)
(6,1,15)
(6,4,-7)
(1,3,-3)
(1,6,15)
(2,1,12)
(2,5,18)
(3,1,9)
(3,4,24)
(4,6,-7)
(5,3,14)
三元组表
a.data
三元组表
b.data
转置后M T
（以转置运算为例）
目的：
转置如何求转置矩阵？
0280036
00070
500140
005
2800
000
0714
3600
用常规的二维数组表示时的算法其时间复杂度为,O(mu× nu)
for (col=1; col<=nu; ++col)
for (row=1; row<=mu; ++row)
T[col][row] = M[row][col];
用三元组表示时如何实现？
1 2 14
1 5 -5
2 2 -7
3 1 36
3 4 28
2 1 14
5 1 -5
2 2 -7
1 3 36
4 3 28
7600070015
00000180
00002400
01400003
0000000
00009120
M
67000000
0001400
000000
700000
0024009
01800012
1500300
N
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
m
a
i j v
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
m
b
0
1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
8
答,肯定不正确！
除了,(1) 每个元素的行下标和列下标互换 (即三元组中的 i和 j互换 );
还应该 (2) T的总行数 mu和总列数 nu与 M值不同（ 互换）；
(3) 重排 三元组内元素顺序,使转置后的三元组也按行 (或列 )
为主序有规律的排列。
上述（ 1）和（ 2）容易实现，难点在 （ 3） 。
若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算，这种说法正确吗？
有两种实现方法压缩转置
(压缩 )快速转置提问：
方法 1,压缩转置思路,反复扫描 a.data中的 列序,从小到大依次进行转置。
三元组表
a.data
三元组表
b.data
①
(1,3,-3)
②
(1,6,15)
③
(2,1,12)
④
(2,5,18)
⑤
(3,1,9)⑥
(3,4,24)
⑦
(4,6,-7)
⑧
(5,3,14)
(1,2,12)
(1,3,9 )
(3,1,-3)
(3,5,14)
(4,3,24)
(5,2,18)
(6,1,15)
(6,4,-7)
1
1
2
col q
1
2
3
4
p
1
2
3
4
解决思路,只要做到
将矩阵行、列维数互换
将每个三元组中的 i和 j相互调换
重排三元组次序，使 mb中元素以 N的行 (M的列 )为主序方法一,按 M的列序转置,即按 mb中三元组次序依次在 ma中找到相应的三元组进行转置。
为找到 M中每一列所有非零元素，需对其三元组表 ma从第一行起扫描一遍。由于 ma中以 M行序为主序,所以由此得到的恰是
mb中应有的顺序
算法分析,T(n)=O(M的列数 n?非零元个数 t)
若 t 与 m?n同数量级，则 )()(
2nmOnT
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
ma
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
i j v
mb
kp
p
p
p
p
p
p
p
k
k
k
k
p
p
p
p
p
p
p
p
col=1 col=2
0
1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
8
bool TransPoseSMatrix(TSMatrix M,TSMatrix &T)
{
T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
if ( T.tu ) {
q=1;
for ( col=1; col<=M.nu; col++ ) {
for ( p=1; p<=M.tu; p++ ) {
if (M.data[p].j==col) {
T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;
T.data[q].value=M.data[p].value; q++;
}
}
}
}
return OK;
}
压缩转置算法描述,
1,主要时间消耗在 查找 M.data[p].j=col的元素,由两重循环完成,
for(col=1; col<=M.nu; col++) 循环次数＝ nu
{ for(p=1; p<=M.tu; p++) 循环次数＝ tu
所以该算法的时间复杂度为 O(nu*tu)
----即 M的列数与 M中非零元素的个数之 积最恶劣情况,M中全是非零元素，此时 tu=mu*nu，
时间复杂度为 O(nu2*mu )
注,若 M中基本上是非零元素时，即使用非压缩传统转置算法的时间复杂度也不过是 O(nu*mu)
结论,压缩转置算法不能滥用。
前提,仅适用于非零元素个数很少（即 tu<<mu*nu）的情况。
压缩转置算法的效率分析,
三元组表
a.data
三元组表
b.data
③
(1,3,-3)①
(2,1,12)
⑥
(2,5,18)
②
(3,1,9)
⑧
(4,6,-7)
④
(5,3,14)
⑦
(1,6,15)
⑤
(3,4,24)
(1,2,12)
(1,3,9 )
(3,1,-3)
(3,5,14)
(4,3,24)
(5,2,18)
(6,1,15)
(6,4,-7)
思路,依次 把 a.data中的元素直接送入 b.data的恰当位置上（ 即 M三元组的 p指针不回溯 ）。
关键,怎样寻找 b.data的,恰当,位置？
p
1
2
3
4
q
3
5
方法 2,快速 转置如果能 预知 M矩阵 每一列 (即 T的每一行 )的 非零元素个数,又能预知 第一个非零元素 在 b.data中的 位置,则扫描 a.data时便可以将每个元素准确定位（ 因为已知若干参考点 ）。
技巧,利用 带辅助向量 的三元组表，它正好携带每行（或列）
的非零元素个数 NUM(i)以及每行（或列）的第一个非零元素在三元组表中的位置 POS(i)等信息。
设计思路：
i 1 2 3 4 5 6
NUM(i) 2 0 2 1 1 2
POS( i ) 1 3 3 5 6 7
需要的是 按列生成的 M矩阵的辅助向量。
规律,POS(1)＝ 1
POS(i)＝ POS(i-1)+NUM(i-1)
请注意 a.data特征：每列首个非零元素必定先被扫描到。
令,M中的列变量用 col表示；
num[ col ],存放 M中第 col 列中非 0元素个数，
cpot[ col ],存放 M中第 col列的第一个非 0元素的位置，
（即 b.data中待计算的“恰当”位置所需参考点）
讨论,按列优先 的辅助向量求出后，下一步该如何操作？
由 a.data中每个元素的 列 信息，即可直接查出 b.data中的重要参考点之位置，进而可确定当前元素之位置！
col 1 2 3 4 5 6
num[col] 2 2 2 1 1 0
cpot[col] 1
规律,cpot(1)＝ 1
cpot[col] ＝ cpot[col-1] + num[col-1]
0 12 9 0 0 0
0 0 0 0 0 0
-3 0 0 0 14 0
0 0 24 0 0 0
0 18 0 0 0 0
15 0 0 -7 0 0
M
3 5 7 8 8
col 1 2 3 4 5 6
cpot[1] = 1;
for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col-1] + num[col-1];
快速转置,即按 ma中三元组次序转置，转置结果放入 b中恰当位置,此法关键是要预先确定 M中每一列第一个非零元在 mb中位置，
为确定这些位置，转置前应先求得 M的每一列中非零元个数实现,设两个数组
num[col]：表示矩阵 M中第 col列中非零元个数
cpot[col],指示 M中第 col列第一个非零元在 mb中位置显然有,cpot[1]=1;
cpot[col]=cpot[col-1]+num[col-1]; (2?col?ma[0].j)
1 3 5 7 8 8 9
col
num[col]
cpot[col]
1
2
2
2
3
2
4
1
5
0
6
1
7
0
7600070015
00000180
00002400
01400003
0000000
00009120
M
算法分析,T(n)=O(M的列数 n+非零元个数 t)
若 t 与 m?n同数量级，则 T(n)=O(m?n)
方法 2,快速 转置
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
ma
i j v
mb
col
num[col]
cpot[col]
1
1
2
2
3
2
3
5
2
4
7
1
5
8
0
6
8
1
7
9
0
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
p
p
p
p
p
p
p
p
4 62 9
753
0
1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
8
7600070015
00000180
00002400
01400003
0000000
00009120
M
Status FastTransposeSMatrix（ TSMatirx M,TSMatirx &T）
{ T.mu = M.nu ;T,nu = M.mu ; T.tu = M.tu ;
if ( T.tu ) {
creatpos( M );
for ( p =1; p <=M.tu ; p++ ) { //p指向 a.data，循环次数为非 0元素总个数 tu
col =M.data[ p ],j ; q =cpos [ col ]; //查辅助向量表得 q，即 T中位置
T.data[q].i = M.data[p],j; T.data[q].j = M.data[p],i;
T.data[q],value = M.data[p],value;
++cpos[col] ; //重要语句！ 修改列坐标值,供 同一列 下一非零元素定位 !
}
}
return OK;
}
快速转置算法描述,
void creatpos( TSMatrix M )
{ for (col = 1; col <=M.nu; col++ ) num[col] =0;
for ( i = 1; i <=M.tu; i ++ ) ++num [M.data[t].j] ;
rpos[ 1 ] =1;
for ( col = 2; col <=M.nu; col++ ) rpos[col ] = rpos[col-1]+num [col-1 ] ;
}
const MAXMN = 100
int num[],rpos[];
1,与常规算法相比，附加了 生成辅助向量表 的工作。增开了 2
个长度为列长的数组 (num[ ]和 cpos[ ]）。
传统转置,O(mu*nu) 压缩转置,O(mu*tu)
压缩快速转置,O(nu+tu)——牺牲空间效率换时间效率。
快速转置算法的效率分析,
2,从时间上，此算法用了 4个并列的单循环，而且其中前 3个单循环都是用来产生辅助向量表的。
for(col = 1; col <=M.nu; col++) 循环次数＝ nu;
for( i = 1; i <=M.tu; i ++) 循环次数＝ tu;
for(col = 2; col <=M.nu; col++) 循环次数＝ nu;
for( p=1; p<=M.tu ; p++ ) 循环次数＝ tu;
该算法的时间复杂度＝ (nu*2)+(tu*2)=O(nu+tu）
讨论,最恶劣情况是 tu=nu*mu(即矩阵中全部是非零元素），
而此时的时间复杂度也只是 O(mu*nu)，并未超过传统转置算法的时间复杂度。
小结：
三元组顺序表又称 有序的双下标法,它的特点是，非零元在表中按行序有序存储，因此 便于进行依行顺序处理的矩阵运算 。然而，若需 随机 存取某一行中的非零元，则需从头开始进行查找。
行逻辑联接的顺序表修改前述的稀疏矩阵的结构定义，增加一个数据成员 rpos,其值在稀疏矩阵的初始化函数中确定。
#define MAXMN 500
typedef struct {
Triple data[MAXSIZE + 1];
int rpos[MAXMN + 1];
int mu,nu,tu;
} RLSMatrix; // 行逻辑链接顺序表类型例如：给定一组下标，求矩阵的元素值
ElemType value(RLSMatrix M,int r,int c)
{
p = M.rpos[r];
while (M.data[p].i==r &&M.data[p].j < c)
p++;
if (M.data[p].i==r && M.data[p].j==c)
return M.data[p].e;
else return 0;
}
结点,非零元的信息 (三元组 )、所在行和列的后继链域十字,每一个非零元结点既是某行链表中的一个结点，
又是某列链表中的一个结点。
稀疏矩阵的规模,行数、列数以及非零元的个数
3 0 0 5
0 -1 0 0
2 0 0 0
1 1 3 1 4 5
2 2 -1
3 1 2
^ ^
^ ^
^ ^3 4 4
^
2、十字链表稀疏矩阵的十字链表表示用 十字链表 表示用途,方便稀疏矩阵的加减运算；
方法,每个非 0元素占用 5个域 。
rightdown
vji
同一列中下一非零元素的指针 同一行中下一非零元素的指针十字链表的特点：
① 每行非零元素链接 成带表头结点的循环链表；
② 每列非零元素也链接 成带表头结点的循环链表。
则每个非零元素既是行循环链表中的一个结点；又是列循环链表中的一个结点，即 呈十字链状。
以稀疏矩阵为例：
1221311H
1
941
-1223 12 0 5
0 -1 0 0
2 0 0 0
2、十字链表
M,c h e a d
M,rh e a d
3 0 0 5
0 -1 0 0
2 0 0 0
1 1 3 1 4 5
2 2 -1
3 1 2
^
^^
^ ^
^ ^
十字链表,设行指针数组和列指针数组，分别指向每行、
列第一个非零元
typedef struct node
{ int row,col,val;
struct node *down,*right;
} Node;
row col val
down right
34008
000
450
003
A
1 1 3
4 1 8
2 2 5 2 3 4
^
^ ^
^
^ ^ ^
结点定义
3 4
7
0 0 3 0 3 0 3 0
0 0 1 1 4 3 4 2
0 0 2 2 2 2 3 9
0 0
0 0 3 1 4 3 2 6 3 4 -5
0 0 0
1
HEAD
4 0 0 2
0 2 9 0
4 6 0 -5
从键盘接收信息建立十字链表算法算法分析,T(n)=o(t?s)
其中,t——非零元个数
s= max(m,n)
令 q=NULL,p=rh[r-1],
(1) 寻找插入位置,当 p!=NULL且 c>p->col时,p和 q右移
(2) 插入：
a、若 p==NULL且 q==NULL，即本行空,则 rh[r-1]==s;
b,若 p==NULL,q!=NULL,即走到行末，则 q->right=s
c,若 c==p->col,则修改 p->val
d,若 c<p->col且 q==NULL,则在 p之前插入 s,即 s是行链表中第一个结点，令 rh[r-1]=s; s->right=p;
e,若 c<p->col且 q!=NULL,则在 p之前插入 s，
即 s->right=p; q->right=s;
4 1 8
^ ^
2 3 4
^ ^
m=4,n=3
1,1,3
2,2,5
2,3,4
4,1,8
2,1,7
1 1 3
^^
2 1 7
^ ^
2 2 5
^ ^
typedef struct OLNode {
int i,j; // 行下标和列下标
ElemType e; // 非零元的值
struct OLNode*right,*down; // 该非零元所在行表和列表的后继链域
} OLNode,*OLink;
typedef struct {
OLink *rhead,*chead; // 行和列链表头指针
int mu,nu,tu; // 行数、列数和非零元个数
} CrossList;
查找算法
void CrossSearch( CrossList &M,ElemType x )
{ i = 0;
p = *(M.rhead+i);
while ( i<M.mu ) {
if ( !p ) { i++; p = *(M.rhead+i); }
else {
if ( p.e==x ) cout <<?(? << p->i <<?,? << p->j <<?)? << endl;
p = p->rnext;
}
}
}
1.熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。
2.熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。
3.了解串的堆存储结构以及在其上实现串操作的基本方法。
4.理解串匹配的 KMP算法，熟悉 NEXT函数的定义，学会手工计算给定模式串的 NEXT函数值和改进的 NEXT函数值。
5.了解串操作的应用方法和特点。
6.了解数组的两种存储表示方法,并掌握数组在以行为主的存储结构中的地址计算方法 。
7.掌握对特殊矩阵进行压缩存储时的下标变换公式 。
8.了解稀疏矩阵的两类压缩存储方法的特点和适用范围,领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法 。
本章总结
!
问答题实验五 停车场管理设停车场内只有一个可停放几辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满几辆汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，
由于停车场是狭长的通道，在它之后开入停车场的车辆必须先退出车场为它让路，待该辆车开出大门外后，为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走。试设计一个停车管理程序。
…入口 出口 …
大门北便道 停车场分析,汽车在停车场内进出是按照栈的运算方式来实现的，
先到的先进停车场；停车场的汽车离开停车场时，车场内其他汽车为该辆汽车让路，也是按栈的方式进行；汽车在便道上等候是按队列的方式进行的。因此，将停车场设计成一个栈，汽车让路也需要另一个栈来协助完成，汽车进出便道用队列来实现。
算法描述：
1、接受命令（ A:入,D:出）和车号，若是汽车要进停车场，
先判断停车场栈是否满，若不满，则汽车入栈，否则汽车入便道队列等候。
2、若是汽车要离开停车场，为该汽车让路，将停车场栈上若干辆汽车入临时栈，等这辆汽车出停车场后，临时栈中的汽车出栈，再回到停车场栈，然后看便道队列是否为空，若不空，
则说明有汽车等候，从队头取出汽车号，让该车入停车场栈。
3、重复 1,2直到为退出命令（车号为 0或负数）。
