数据结构5

5.1 串的定义和基本运算
• （4）串的连接StrCat(S,T)。 • 初始条件：串S和T存在。 • 操作结果：将串T的值连接在串S的后面。 • （5）求子串SubString(Sub,S,pos,len)。 • 初始条件：串S存在，1≤pos≤StrLength(S)且
1≤len≤StrLength(S)-pos+1。 • 操作结果：用Sub返回串S的第pos个字符起长度为len的
1≤len≤StrLength(S)-pos+1。 • 操作结果：从串S中删除第pos个字符起长度为len的子串。 • （9）串的替换StrReplace(S,T,V)。 • 初始条件：串S，T和V存在，且T是非空串。 • 操作结果：用V替换串S中出现的所有与T相等的不重叠子
串。 • （10）判断串空StrEmpty(S)。 • 初始条件：串S存在。 • 操作结果：若串S为空串，则返回1；否则返回0。
• （1）非紧凑存储。设串S="Hello boy"，计算机字长为32 位（4个Byte），用非紧凑格式一个地址只能存一个字符， 如图5-2所示。其优点是运算处理简单，但缺点是存储空 间十分浪费。
• （2）紧凑存储。同样存储S="Hello boy"，用紧凑格式一 个地址能存四个字符，如图5-3所示。紧凑存储的优点是 空间利用率高，缺点是对串中字符处理的效率低。
•}
5.3 串的基本运算的实现
• （3）求子串操作。求串S从第pos位置开始，长度为len的 子串，并将其存入到串Sub中。操作成功返回1，不成功 返回0。其算法描述如下：
• int SubString(String *S,String *Sub,int pos,int len)

else break; /* find the proper position */
}
H->Elements[ i ] = LastElement;
return MinElement;
}
11/15
4. Other Heap Operations:
§3 Binary Heap
Note: Finding any key except the minimum one will have to take a linear scan through the entire heap.
Note: Analogously, we can declare a max heap by changing the heap order property.
[1] 9 The largest key
[1] 10 The smallest key
[2] 6 [3] 3
[2] 20 [3] 83
[4] 5
return FatalError( "Out of space!!!" ); H->Capacity = MaxElements; H->Size = 0; H->Elements[ 0 ] = MinData; /* set the sentinel */ return H; }
6/15
2. Heap Order Property:
LastElement = H->Elements[ H->Size-- ]; /* take last and reset size */
for ( i = 1; i * 2 <= H->Size; i = Child ) { /* Find smaller child */

2012年11月1日 13
2．三角矩阵 （1）上三角矩阵 即矩阵上三角部分元素是随机的，而下三角部分元素全部 相同（为某常数C或全为0），具体形式见图5-2（a）。 （2）下三角矩阵 即矩阵的下三角部分元素是随机的，而上三角部分元素全 部相同（为某常数C或全为0），具体形式见图5-2（b）。
2012年11月1日
2012年11月1日
12
5.3.1 特殊矩阵
2 3 1 A＝ 5 4 2 4 6 3
图5-1 一个对称矩阵
1．对称矩阵 若一个n阶方阵A中元素满足下列条件： aij=aji 其中0≤i, j≤n-1，则称A为对称矩阵。 例如，如图5-1所示是一个3×3的对称矩阵。
0
1
2
3
4
5
6
7
……
n ( n +1 ) 2
-3
n ( n +1 ) 2
-2
n ( n +1 ) -1 2
a00 a01 a02 a03 a04 a05 a06 a07
……
an-2n-2
an-2n-1
an-1n-1
2012年11月1日
（b）上三角矩阵的压缩存储形式 图5-5 对称矩阵及用上三角压缩存储
第5章 多维数组和广义表
本章学习内容
5.1 多维数组
5.2 多维数组的存储结构
5.3 特殊矩阵及其压缩存储
5.4 稀疏矩阵
5.5 广义表
2012年11月1日 1
5.1 多维数组
5.1.1 多维数组的概念
1．一维数组
一维数组可以看成是一个线性表或一个向量（第2章中 已经介绍），它在计算机内是存放在一块连续的存储 单元中，适合于随机查找。

an-1,n-1
压缩存储方法：只需要存储下三角 （含对角线）上的元素。可节省一 半空间。
可以使用一维数组Sa[n(n+1)/2]作为n阶对称矩阵A的存 储结构，且约定以行序为主序存储各个元素，则在Sa[k]和矩
阵元素aij之间存在一一对应关系： （下标变换公式）
i(i+1)/2 + j 当i≥j k = j(j+1)/2 + i 当i<j
q = cpot[col];
T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].e = M.data[p].e; ++cpot[col]; }
分析算法FastTransposeSMatrix的时间 复杂度：
for (col=1; col<=M.nu; ++col) … … for (t=1; t<=M.tu; ++t) … … for (col=2; col<=M.nu; ++col) … … for (p=1; p<=M.tu; ++p) … …
//对当前行中每一个非零元
处
brow=M.data[p].j;
理
if (brow < N.nu ) t = N.rpos[brow+1];
M
else { t = N.tu+1 }
的
for (q=N.rpos[brow]; q< t; ++q) { ccol = N.data[q].j; // 乘积元素在Q中列号
一、三元组顺序表
对于稀疏矩阵，非零元可以用三元组表示， 整个稀疏矩阵可以表示为所有非零元的三元组所 构成的线性表。例如：