第5章 数组和串 5.1 数 组   5.2 间接地址 5.3 特殊矩阵的压缩存储 5.4 稀疏矩阵的压缩存储 5.5 串.

Presentation on theme: "第5章 数组和串 5.1 数 组   5.2 间接地址 5.3 特殊矩阵的压缩存储 5.4 稀疏矩阵的压缩存储 5.5 串."— Presentation transcript:

1 第5章 数组和串 5.1 数 组   5.2 间接地址 5.3 特殊矩阵的压缩存储 5.4 稀疏矩阵的压缩存储 5.5 串

2 5.1 数 组   C++的数组 我们首先讨论C++中提供的支持基本数组的方法和实现机理。前面我们已讲述过，C++中的数组有静态数组和动态数组两种。在定义静态数组时必须给出数组个数，系统在编译时为用户分配存储空间。

3 在定义动态数组时也必须给出数组个数，系统在用户使用new函数申请时为用户分配存储空间。无论是静态数组还是动态数组，系统都是分配一块地址连续的存储空间给用户。C++中的数组下标均从0开始。
C++提供的数组的操作主要有存储和提取。当数组操作符［］处于赋值号左边时表示数组的存储操作，当它处于赋值号右边时表示数组的提取操作。例如， 我们定义有一个数组a，a［i］ = a［i+1］就表示把数组元素a［i+1］中的数值提取出来并存储到数组元素a［i］中。

4 对一个有n个数据元素的一维数组，设a0是下标为0的数组元素，Loc(a0)是a0的存储地址，k是每个数据元素所需的存储单元，则数组中任一数据元素ai的存储地址Loc(ai)可由下边公式求出：
Loc(ai) = Loc(a0) + i * k (0≤i<n) (5―1) 对一个m行n列的二维数组，由于计算机的存储单元都是一维的，就有一个二维向一维的映射问题，用计算机的术语叫做行主序还是列主序存放的问题。

5 C++中的数组元素是行主序的存放方法，即一行存完后再存放下一行。设a00是行列下标均为0的数组元素，Loc(a00)是a00的存储地址，k是每个数据元素所需的存储单元，则数组中任一数据元素aij的存储地址Loc(aij)可由下边公式求出： Loc(aij) = Loc(a00) + (i * n + j) * k (0≤i<m, 0≤j<n) (5―2)

6 式(5―2)可按如下思路理解：数组是从基地址Loc(a00)开始存放的；数组元素aij前已存放了i行，即已存放了i. n个数据元素，占用了i
式(5―2)可按如下思路理解：数组是从基地址Loc(a00)开始存放的；数组元素aij前已存放了i行，即已存放了i * n个数据元素，占用了i * n * k个存储单元；数组元素aij前已存放了j列，即已存放了j个数据元素，占用了j * k个存储单元，所以数组元素aij的存储地址Loc(aij)为上述三部分之和。

7 安全数组类的定义和实现 C++提供的数组方法能满足大多数应用程序的设计需求，但C++提供的数组方法有两个缺点： (1) C++提供的静态数组方法需要预先给出数组元素个数，数组大小在编译时就已确定，且在运行时无法修改。 (2) C++提供的数组方法不进行数组下标越界判断，当数组下标越界时程序照常运行。

8 本节我们利用C++提供的动态数组方法设计一个一维安全数组类。一维安全数组类在基本数组功能的基础上考虑了数组下标越界问题，且可以重新定义数组元素个数。一维安全数组类的定义和实现如下：
＃include <iostream.h> ＃include <stdlib.h> //定义enum类型的错误类型。 注意, 其顺序和错误信息数组的顺序相同 enum Error Type{InvalidArraySize, MemoryAllocationError, IndexOutOfRange}; //定义错误信息数组并赋值

9 char *errorMsg［］ ={"Invalid Array Size", "Memory Allocation Error",
"Index Out Of Range"};  template <class T> class Array //Array类定义 { private: T* arr; //数组指针 int size; //数组个数 //错误处理 void Error(ErrorType , int badIndex = 0) const;  

10 public: Array(int sz = 100); //一般构造函数 Array(const Array<T>& a); //拷贝构造函数 ~Array(void); //析构函数  Array<T>& operator=(const Array<T>& a); //赋值操作符重载 T& operator［］(int i); //下标操作符重载 int ArraySize(void)const; //返回数组个数 void ReSize(int sz); //重新定义数组大小 };

11 //错误处理，打印出errorComm所对应的错误信息
template <class T> void Array<T>::Error(ErrorType errorComm, int badIndex)const { if(badIndex == 0) cout << errorMsg［errorComm］ << endl; else cout << errorMsg［errorComm］ << ": " << badIndex << endl; } //构造函数，申请sz个元素空间给arr

12 template <class T>
Array<T>::Array(int sz) { if(sz <= 0) Error(Invalid ArraySize, sz); size = sz; arr = new T［size］; if(arr == NULL) Error(Memory AllocationError); } //析构函数，释放数组arr的内存空间

13 template <class T> 
Array<T>::~Array(void) { delete ［］arr; }  //构造函数，申请a.size个元素空间给arr， 并拷贝a.arr ［i］到arr［i］ template <class T> Array<T>::Array(const Array<T>& a) int n = a.size;

14 size = n; arr = new T［size］; if(arr == NULL) Error(Memory AllocationError); T* soucePtr = a.arr; T* destPtr = arr; while(n--) *destPtr++ = *soucePtr++; }

15 //赋值操作符重载，申请a.size个元素空间给arr，并拷贝a.arr ［i］到arr［i］
template <class T>  Array<T>& Array<T>::operator=(const Array<T>& a) { int n = a.size; size = n; arr = new T［size］; if(arr == NULL) Error(Memory AllocationError);

16 T* soucePtr = a.arr; T* destPtr = arr; while(n--) *destPtr++ = *soucePtr++; } //下标操作符重载，返回arr［i］ template <class T>  T& Array<T>:: operator［］(int i) { if(i < 0 || i > size-1) Error(IndexOutOfRange, i);

17 return arr［i］; } //返回数组个数 template <class T>  int Array<T>::ArraySize(void)const { return size; }  //重新定义数组大小，方法是申请sz个元素空间给新数组newArray， //拷贝原数组元素arr［i］到新数组元素newArray ［i］，

18 //释放原数组arr空间，arr为newArray
template <class T> void Array<T>::ReSize(int sz) { if(sz <= 0) Error(InvalidArraySize, sz); if(sz == size) return; T* newArray = new T［sz］; if(newArray == NULL) Error(MemoryAllocationError); int n = (sz <= size) ? sz: size; //n为sz和size中的较小者  

19 T* soucePtr = arr; T* destPtr = newArray; while(n--) *destPtr++ = *soucePtr++;  delete ［］arr; arr = newArray; size = sz; }

20 上述一维安全数组类的定义和实现放在文件Array.h中。
下面给出一个简单例子， 讨论C++中提供的数组方法与这里重新设计的一维安全数组类有何不同。

21 ＃include "Array.h"  void main(void) { Array<int> a(10); //定义Array<int>类型对象a，数组个数为10  cout << "ArraySize = " << a.ArraySize() << endl; for(int i = 0; i < 10; i++) a［i］ = i; //a［20］ = 20; //若包括此语句， 则显示数组下标越界错误信息  a.Resize(30); //重新定义a的数组个数为30

22 a［21］ = 21; cout << "a［21］ = " << a［21］ << endl; cout << "ArraySize of Resize = " << a.ArraySize() << endl;} 上述程序的运行结果如下： ArraySize = 10 a［21］ = 21 ArraySize of Resize = 30若包括a［20］ = 20语句，由于该语句数组下标越界，因此程序的运行结果如下： Index Out Of Range：20

23 5.2 间接地址   3.1节讨论的顺序存储结构和4.1节讨论的链式存储结构是计算机中两种最主要的存储结构，除此之外，间接地址也是一种很常用的数据存储结构。间接地址是存储的数据元素为某个数据元素的地址（或称指针）。间接地址有单数据和数组两种情况。单数据的间接地址就是通常C++中的指针的指针；数组的间接地址通常称作指针数组。

24 指针数组在数据结构的存储结构中较为常用。指针数组中的数据元素或者可以是一个数组的首地址，或者可以是一个链表的头指针，可见，指针数组是两种存储结构的结合。这里我们讨论指针数据元素为数组首地址的情况，指针数据元素为链表头指针的情况将在5.4.3节讨论。

25 template <class T>
void Make2DArray(T** &a, int row, int col) //定义二维动态数组a，其行数为row, 列数为col { a = new T*［row］; //a为有row个指针的指针数组  for(int i = 0; i < row; i++) a［i］ = new T［col］; //每个指针指向一个有col个元素空间的数组 }

26 函数参数a定义为指针的指针类型，因此函数中首先为a申请row个元素空间，使a为有row个指针的指针数组；然后， 为每个指针申请col个元素空间，使每个指针指向一个有col个元素空间的数组。设行数row为3，列数col为4，则所构造的二维动态数组的结构如图5-1所示。

27 注意，如图5―1所示，由于二维动态数组的全部存储空间不是一次申请的，所以二维动态数组的每一维数组在物理上是连续的;而全部二维动态数组在物理上不一定是连续的；二维动态数组逻辑上的次序关系靠图5―1左边所示的指针数组实现。此外还要指出的是，实现m行n列二维动态数组实际需要的数据元素存储空间超过m*n个，额外的m个用于存储指针数组，如图5―1左边所示的3个数据元素(a［0］、a［１］和a［2］)用于存储3个指针元素。

28 图5―1 一个3行4列动态数组的结构

29 一个int类型的二维动态数组使用方法示例的主函数如下：
＃include <iostream.h> （Make2Darray()函数同上，此处省略） void main(void) { int **a; Make2DArray<int>(a, 3, 4); for(int i = 0; i < 3; i++) for(int j = 0; j < 4; j++)

30 { a［i］［j］ = i + j; cout << a［i］［j］ << " "; } cout << endl; } 程序运行输出为：

31 5.3 特殊矩阵的压缩存储 矩阵运算是许多科学和工程计算问题中经常遇到的问题，通常在编写求解矩阵问题的应用程序时都用二维数组来存储矩阵数据元素。在编写求解矩阵问题的应用程序时，我们也经常会遇到这样一些矩阵，其中有许多值相同的元素或有许多零元素，且值相同的元素或零元素的分布有一定的规律。我们称这种分布有一定规律的矩阵为特殊矩阵。当程序的空间复杂度需要认真考虑时，我们可以对这些特殊矩阵进行压缩存储，方法是只存储其中数值不相同的数据元素部分。

32 矩阵的定义和操作 为方便下面的叙述，我们在此首先讨论矩阵的定义和操作。一个m×n的矩阵是一个有m行n列的表，表中的数据元素称作矩阵元素，矩阵元素共有m*n个，m和n称作矩阵的维数。 当m等于n时也称n为矩阵的阶。下面是一个4行4列矩阵的示例。

33 矩阵最常用的操作有矩阵加、矩阵减、矩阵乘和矩阵转置。设A，B，C为三个m×n的矩阵，aij，bij，cij为矩阵元素，则矩阵加的定义为C = A + B，即有：
cij=aij+bij (0≤i<m, 0≤j<n) (5―3) 注意，为与C++中数组元素从0开始一致，我们这里定义的矩阵运算也从0开始。矩阵减的定义为C = A - B，即有：  cij = aij - bij (0≤i<m, 0≤j<n) (5―4) 矩阵乘的定义为C = A * B，即有： (0≤i<m, 0≤j<n) (5―5)

34 矩阵转置的定义为B = A，即有：  bij = aji (0≤i<m, 0≤j<n) (5―6) 除此之外，矩阵操作还有矩阵求逆、矩阵行列式等，在此我们不再作深入的讨论，有兴趣的读者可参阅相关文献。我们下面设计的矩阵类的成员函数也不包括矩阵求逆、矩阵行列式等。在实际的软件系统中， 若需要这些操作， 可在矩阵类中增加相应的成员函数。

35 对称矩阵的压缩存储 若一个n阶矩阵A中的数据元素满足  aij = aji (0 ≤ i, j ≤ n-1) (5―7) 则称其为n阶对称矩阵。 由于对称矩阵中的数据元素以主对角线为中线对称，因此在存储时可只存储对称矩阵中上三角或下三角的数据元素，即让对称的数据元素共享一个存储空间，这样就可将n2个数据元素压缩存储到n(n+1)/2个数据元素空间中。不失一般性，我们这里讨论的算法所存储的是对称矩阵的下三角（包括对角线）的数据元素。

36 假设以有n(n+1)/2个数据元素的一维数组sa作为n阶对称矩阵A的存储结构，我们可做一个数学映射，使得n阶对称矩阵A中的所有下三角（包括对角线）的数据元素对应不同的存储单元，所有上三角（不包括对角线）的数据元素对应下三角的相应存储单元。设aij为n阶对称矩阵中i行j列的数据元素，k为一维数组sa的下标序号，我们可做如下数学映射： 当i≥j时 (5―8) 当i<j时

37 所谓n阶下三角矩阵就是行列数均为n的矩阵的上三角（不包括对角线）中的数据元素均为0，此时我们可以只存储n阶下三角矩阵的下三角（包括对角线）中的数据元素。设aij为n阶下三角矩阵中i行j列的数据元素，k为一维数组sa的下标序号， 我们有如下数学映射公式： 当i≥j时 (5―9) 当i<j时 空

38 当n阶下三角矩阵的上三角（不包括对角线）中的数据元素为一不为0的常数时，上述式(5―9)也可更改为如下的式(5―10)。
当i≥j时 (5―10) 当i<j时

39 上三角矩阵压缩存储类 从4.8节讨论的应用问题的面向对象程序设计方法可知，对上三角矩阵的压缩存储，我们可将其设计为一个类，这样应用程序就可通过定义上三角矩阵压缩存储类的对象而方便地进行应用程序设计。 一个四阶的上三角矩阵不为0的数据元素排列情况如下所示。可以推知，对于一个n阶的上三角矩阵的数据元素aij，当i>j时aij=0，当i≤j时aij≠0。

40 我们首先给出上三角矩阵的数学性质, 以方便上三角矩阵压缩存储类的设计。上三角矩阵具有如下性质：
(1) 两个上三角矩阵之和是上三角矩阵； (2) 两个上三角矩阵之差是上三角矩阵； (3) 两个上三角矩阵之积是上三角矩阵。 上述三条性质说明，上三角矩阵关于加、减和乘运算是封闭的。  

41 不同于5.3.1节的下三角矩阵映射公式，我们这里给出把上三角矩阵中的数据元素变换到一维数组中的一种递推公式。设上三角矩阵的非零元素存储在一维数组arr中， 主对角线以下的数据元素（全为0）不存储，我们用一维数组row Table来记录上三角矩阵的每一行的第一个非零元素在数组arr中的位置，有： row Table［0］ = 0 row Table［1］ = n row Table［2］ = n + n -1  … row Table［i］ =

42 这样，上三角矩阵数据元素aij 在一维数组arr中的存储位置为：
(5―11) i≤j

43 最后我们再来分析一下矩阵运算要具有的操作。对于矩阵类来说，除前面讨论过的矩阵加、矩阵减和矩阵乘操作外，矩阵数据元素的存储和提取是必须的，矩阵数据元素的输入和屏幕显示是必须的，读当前矩阵的维数也是必须的，因此，设计的上三角矩阵压缩存储类应包括这些操作。 模板形式的上三角矩阵类的定义和实现如下：

44 ＃include <iostream.h>
＃include <iomanip.h> ＃include <stdlib.h> const int RowLimit = 50; //最大行数，也即最大维数 const int EleLimit = 1275; //相应的最大元素个数，等于50*51/2 template <class T> class TriMat //模板形式的类TriMat {

45 private: T arr［EleLimit］; //一维数组，用于存储矩阵元素 int rowTable［RowLimit］; //矩阵每行第一个非零元素在arr中的下标 int n; //矩阵的阶数 public: TriMat(int matSize); //构造函数，矩阵阶数为matSize ～TriMat(void){}; //析构函数， 为空 void PutEle(T item, int i, int j); //存储元素item到i行j列 T GetEle(int i, int j)const; //提取i行j列的元素返回

46 TriMat<T> operator+ (const TriMat<T>& a)const;
//矩阵加 TriMat<T> operator- (const TriMat<T>& a)const; //矩阵减 TriMat<T> operator* (const TriMat<T>& a)const; //矩阵乘 void ReadMat(void);//矩阵元素输入 void WriteMat(void)const; //矩阵元素屏幕输出 int GetDim(void)const //取矩阵的阶数返回 {return n;};

47 }; template <class T> TriMat<T>::TriMat(int matSize) //构造函数，矩阵阶数为matSize { int storedEles = 0; //第0行第一个非零元素在arr中的下标为零 if(matSize > RowLimit) cerr << "矩阵的阶数超过了上限: " << RowLimit << endl; exit(1);

48 }  n = matSize;  //递推求出第i行第一个非零元素在arr中的下标并存于rowTable［i］中 for(int i = 0; i < n; i++) { rowTable［i］ = storedEles; storedEles += n-i; }

49 template <class T>
void TriMat<T>::PutEle(T item, int i, int j) //存储元素item到i行j列 { if((i < 0 || i >= n) || (j < 0 || j >= n)) cerr << "数组下标越界超过了范围0到" << n-1 << endl; exit(1); } if(j >= i) arr［rowTable［i］+j-i］ = item; //只存对角线上的元素}

50 template <class T>
T TriMat<T>::GetEle(int i, int j)const //提取i行j列的元素返回 { if((i < 0 || i >= n) || (j < 0 || j >= n)) cerr << "数组下标越界超过了范围0到" << n-1 << endl; exit(1); }  if(j >= i) return arr［rowTable［i］+j-i］; //返回对角线上的元素 else return 0; //对角线下的元素为0 }

51 template <class T>
TriMat<T> TriMat<T>::operator+ (const TriMat<T>& a)const //矩阵加 { T itemCurr, itemA; TriMat<T> b(a.n); for(int i = 0; i < n; i++) for(int j = i; j < n; j++)

52 itemCurr = GetEle(i, j); //取当前对象的i行j列元素
itemA = a.GetEle(i, j); //取矩阵a的i行j列元素 b.PutEle(itemCurr+itemA, i, j); //元素相加后存于b的i行j列 } return b; //返回b } template <class T> TriMat<T> TriMat<T>::operator- (const TriMat<T>& a)const //矩阵减

53 { T itemCurr, itemA; TriMat<T> b(a.n); for(int i = 0; i < n; i++) { for(int j = i; j < n; j++) itemCurr = GetEle(i, j); //取当前对象的i行j列元素 itemA = a.GetEle(i, j); //取矩阵a的i行j列元素 b.PutEle(itemCurr-itemA, i, j); //元素相减后存于b的i行j列

54 } return b; //返回b template <class T> TriMat<T> TriMat<T>::operator* (const TriMat<T>& a)const //矩阵乘 { T itemCurr, itemA, itemB; TriMat<T> b(a.n);  for(int i = 0; i < n; i++)

55 { for(int j = i; j < n; j++) itemB = 0; //初值为0 for(int k = i; k <= j; k++) //求出i行j列的乘积值存于itemB   itemCurr = GetEle(i, k); itemA = a.GetEle(k, j); itemB += itemCurr * itemA; } b.PutEle(itemB, i, j); //把求出的乘积存于b的i行j列

56 } return b; template <class T> void TriMat<T>::ReadMat(void) //矩阵元素输入 { T item; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)

57 cin >> item; PutEle(item, i, j); //输入元素存于i行j列 } } template <class T> void TriMat<T>::WriteMat(void)const //矩阵元素屏幕输出 { for(int i = 0; i < n; i++)

58 for(int j = 0; j < n; j++)
cout << setw(7) << GetEle(i, j); //提取i行j列元素输出 cout << endl; } } 上述模板形式的上三角矩阵类TriMat的定义和实现放在文件TriMat.h中。下面的测试程序既演示了TriMat类的I/O操作以及矩阵乘操作，也演示了TriMat类的程序使用方法。

59 ＃include "TriMat.cpp" void main(void) { int n; cout << "输入矩阵维数: "; cin >> n;  TriMat<int> a(n), b(n), c(n); //定义三个n阶上三角矩阵a,b,c

60 cout << "输入矩阵a的元素(包括0): " << endl;
a.ReadMat(); //输入a cout << "输入矩阵b的元素(包括0): " << endl; b.ReadMat(); //输入b c = a * b; //a*b存于c cout << "A * B 为: " << endl; c.WriteMat(); //输出c }

61 程序的一次运行如下： 输入矩阵维数：4 输入矩阵a的元素(包括0): 输入矩阵b的元素(包括0):

62 A * B 为:

63 5.4 稀疏矩阵的压缩存储 稀疏矩阵的三元组表 稀疏矩阵中每个非零元素和它对应的行下标和列下标构成一个三元组，稀疏矩阵中所有这样的三元组构成一个三元组表。图5―2（a）是一个稀疏矩阵，图5―2（b）是对应的三元组表。

64 图5―2 稀疏矩阵和对应的三元组表 （a） 稀疏矩阵； (b） 三元组表

65 三元组表可用第3章讨论的顺序表存储，也可用第4章讨论的链表存储。用顺序表存储的三元组表称作三元组顺序表，用链表存储的三元组表称作三元组链表。下面我们分别讨论稀疏矩阵的三元组顺序表存储类的设计和稀疏矩阵的三元组链表的设计。

66 稀疏矩阵的三元组顺序表存储类 稀疏矩阵的三元组顺序表存储类的成员函数除了构造函数和析构函数外， 主要是矩阵的转置运算，前面已讨论过，稀疏矩阵不能有矩阵加、矩阵减和矩阵乘运算，因为这些运算将使稀疏矩阵变为稠密矩阵。 此外，我们下面设计的类中把稀疏矩阵的输入和输出设计成了输入流和输出流操作符重载，由于这些重载的操作符是输入流类和输出流类的成员函数，所以要定义为稀疏矩阵的三元组顺序表存储类的友元。稀疏矩阵的三元组顺序表存储类的定义和实现如下：

67 ＃include <iostream.h>
＃include <stdlib.h> template <class T> struct Term { int row; int col; T value; }; template <class T> class SeqSpaMat

68 { //定义为友元的输出流操作符重载 friend ostream& operator<< (ostream& out, const SeqSpaMat<T>& a); //定义为友元的输入流操作符重载 friend istream& operator>> (istream& in, SeqSpaMat<T>& a); private: int rows; //矩阵行数   int cols; //矩阵列数

69 Term<T> *arr; //三元组动态数组指针
int size; //非零元个数 int MaxSize; //三 元组动态数组个数 public: SeqSpaMat(int maxTerm = 100); //构造函数 ~SeqSpaMat(void) //析构函数 {delete ［］arr;}; //把当前对象的三元组数组转置存储到对象a

70 void Transpose(SeqSpaMat<T>& a);
};  template <class T> SeqSpaMat<T>::SeqSpaMat(int maxTerm) //构造函数 { if(maxTerm < 1) cout << "初始化值错!" << endl; exit(1); }

71 MaxSize = maxTerm; arr = new Term<T>［MaxSize］; size = rows = cols = 0; }  //把当前对象的三元组数组转置存储到对象a Template <class T> void SeqSpaMat<T>::Transpose(SeqSpaMat<T>& a) { int j; if(size > a.MaxSize)  

72 { cout << "空间不够无法转置!" << endl; exit(1); } a.cols = rows; a.rows = cols; a.size = size; int *colSize, *rowNext;

73 colSize = new int［cols］;
//为矩阵每列非零元个数计数器  rowNext = new int［rows］; //为每行第一个非零元存储序号  //初始化列非零元个数计数器为0 for(int i = 0; i < cols; i++) colSize［i］ = 0;  //计数每列的非零元个数 for(i = 0; i < size; i++) colSize［arr［i］.col］++;

74 rowNext［0］ = 0; //第0行第一个非零元存储序号为0 //第i行第一个非零元存储序号=第i-1行第一个非零元存储序号+列非零元个数   for(i = 1; i < cols; i++) rowNext［i］ = rowNext［i-1］ + colSize［i-1］; //递推求值   for(i = 0; i < size; i++) {

75 //计算转置存储非零元三元组的下标序号 // rowNext［arr［i］.col］加1后就变为该列下一个非零元三元组的下标序号 j = rowNext［arr［i］.col］++;   //转置存储非零元三元组到a.arr［j］ a.arr［j］.row =arr［i］.col; a.arr［j］.col =arr［i］.row; a.arr［j］.value = arr［i］.value;

76 } delete ［］colSize; delete ［］rowNext; template <class T> ostream& operator<< (ostream& out, const SeqSpaMat<T>& a){ out << "矩阵行数为：" << a.rows << endl; out << "矩阵列数为：" << a.cols << endl; out << "矩阵非零元个数为：" << a.size <<endl;  

77 cout << "矩阵非零元三元组为：" << endl;
for(int i = 0; i < a.size; i++) out << "a(" << a.arr［i］.row << ',' << a.arr［i］.col << ") = " << a.arr［i］.value << endl;  return out;  } template <class T> istream& operator>> (istream& in, SeqSpaMat<T>& a)

78 { cout << "输入行数、列数和非零元个数：" ; in >> a.rows >> a.cols >> a.size; if(a.size > a.MaxSize) cout << "非零元个数超过了定义的最大值!" << endl; exit(1); }  for(int i = 0; i < a.size; i++)

79 cout << "输入行号、列号和元素值：";
in >> a.arr［i］.row >> a.arr［i］.col >> a.arr［i］ .value; } return in;

80 上述稀疏矩阵的三元组顺序表存储类的定义和实现放在文件SeqSpaMat. h中。一般稀疏矩阵的转置算法的时间复杂度为O（n
上述稀疏矩阵的三元组顺序表存储类的定义和实现放在文件SeqSpaMat.h中。一般稀疏矩阵的转置算法的时间复杂度为O（n*t）, n为稀疏矩阵的行数, t为稀疏矩阵的非零元个数；上述稀疏矩阵的转置算法由于用递推方法首先求出了第i行第一个非零元存储的下标序号， 所以该算法的时间复杂度为O（n）和O（t）的较大者。   一个测试程序如下： ＃include "SeqSpaMat.h"  void main(void)

81 { SeqSpaMat<int> matricA; SeqSpaMat<int> matricB; cin >> matricA; cout << "原矩阵为：" << endl; cout << matricA; matricA.Transpose(matricB); cout << "转置后的矩阵为：" << endl; cout << matricB; }

82 程序的一次运行如下： 输入行数、列数和非零元个数：2 2 2 输入行号、列号和元素值：0 0 1 输入行号、列号和元素值：0 1 2 原矩阵为： 矩阵行数为：2 矩阵列数为：2 矩阵非零元个数为：2 a(0,0) = 1 a(0,1) = 2

83 转置后的矩阵为： 矩阵行数为：2 矩阵列数为：2 矩阵非零元个数为：2 a(0,0) = 1 a(1,0) = 2

84 稀疏矩阵的三元组链表 稀疏矩阵的三元组也可采用链表存储。用链指针依次把稀疏矩阵中非零元的三元组链接起来就构成了最简单的三元组链表。图5― 2（a）的带头结点的三元组链表结构如图5―3所示，其中头结点的行号域存储了稀疏矩阵的行数，列号域存储了稀疏矩阵的列数。

85 图5―3 带头结点的三元组链表结构

86 这种三元组链表的缺点是算法的时间复杂度高，因为要访问某行某列中的一个元素时，必须从头指针进入后逐个结点查找。为降低时间复杂度，我们可以给三元组链表的每一行设计一个头指针，这些头指针构成一个指针数组，指针数组中的每一行的指针指向该行的三元组链表。 由于链表中每一行的行下标均相同，所以此时也可以去掉三元组中的行下标，我们称这种结构的三元组链表为行指针数组结构的三元组链表。图5―2（a）的行指针数组结构的三元组链表如图5―4所示。由于每行的行域值均相同，所以行指针数组结构的三元组链表中可省略行域，统一放在指针数组的行号域中。

87 图5―4 行指针数组结构的三元组链表

88 行指针数组结构的三元组链表对于从某行进入后找某列元素的操作比较容易实现，但对于从某列进入后找某行元素的操作就不容易实现，为此可再仿造行指针数组构造相同结构的列指针数组，这样的链表结构称作十字链表存储结构。8.4.2节较详细地讨论了十字链表存储结构。

89 5.5 串 串的定义、存储结构和操作 串（String），也称作字符串，是由 n（n≥0）个字符组成的有限序列。一般记作s="s0, s1,… sn-1"。其中, s称作串名;n称作串的长度;双引号括起来的字符序列称作串的值;每个字符si（0≤i<n）可以是任意的ASCII码字符，一般是字母、数字、标点符号等可屏幕显示的字符。

90 虽然串是由字符组成的，但串和字符是两个不同的概念，即使是长度为1的串也和字符不同。例如， 串"a"和字符′a′（字符通常用单引号括起来）就是两个不同的概念。长度为1的串和字符的不同主要是两者的存储结构不同。由于串是由n（n≥0）个字符组成的有限序列，是一种线性结构，且每个字符占空间很小，　只占8个字节。若用链式结构存储时存储效率太低；而用顺序存储结构存储时既有高的存储效率，又方便串的通常连续若干个字符序列操作的实现；所以， 串通常采用顺序存储结构存储。

91 当串采用顺序存储结构存储时，存储串的数组名指出了串在内存中的首地址，为表示串的长度，可有两种解决方法：(1) 在存储串的数组末尾添加一个结束标识符；（2）用一个单独的长度参数。计算机高级语言系统一般采用第一种方法表示串的长度。从字符串和字符的存储结构不同，我们就可以回答为什么串"a"和字符′a′是两个不同的概念。对一个采用第一种方法表示串长度的串来说，当串的长度为1时，内存中存储了一个字符和一个结束标识符，而一个字符在内存中只存储了一个字符。

92 下面我们要讨论串的操作，为方便下面讨论中的示例，我们先定义如下几个串：
s1 =″I am a student" s2 ="teacher" s3 ="student" 串的操作主要有： (1) 求串的长度。s1的长度为14，s2的长度为7。 (2) 把一个串的值拷贝给另一个串。若有s4 = s3，则有s4 =″student"。 (3) 把两个串连接形成一个长度为两个串长度之和的新串。

93 (4) 比较两个串的ASCII码值的大小。设str1和str2为两个串，按下述规则得到两个串的比较结果。
(6) 在一个串中查找是否存在一个字符。 (7) 截取子串形成一个新串。设str为要截取的串，pos为要截取的起始位，length为要截取的长度，则形成的新串长度为length。 (8) 在一个串中插入另一个串。 (9) 从一个串中删除一个子串。

94 (10) 从键盘输入一个字符序列。 (11) 在屏幕上显示一个字符序列。

95 C++的串 C++的串解决串的长度的方法是在存储串的数组末尾添加一个ASCII值为0的空字符（标识符为NULL）作为结束标识符。下面的语句定义了一个字符数组并赋初值"Data Structure":   Char str［］ = “Data Structure"; 字符串"Data Structure"在内存中的存储形式如下：  

96 C++的串库（string.h）中提供了许多实现上述字符串操作的字符串函数，但C++的串库中提供的实现字符串操作的函数功能和我们在前面讨论的字符串的基本操作功能不完全相同。几个常用的C++字符串函数及其使用方法如下（各次示例都从定义语句开始）：假设我们已有如下定义语句： char s1［］ ="I am a student"; char s2［］ ="teacher"; char s3［］ ="student"; int result; char s4［20］, *p;

97 (1) 串长度 int strlen(char *str):
cout << strlen(s1) << endl; //输出14 cout << strlen(s2) << endl; //输 出7(2) 串拷贝 char *strcpy(char *str1, char *str2): strcpy(s4, s2); //s4 ="teacher" (3) 串连接 char * strcat(char *str1, char *str2): strcat(s2, s3); //s2 ="teacherstudent"

98 (4) 串比较 int strcmp(char *str1, char *str2):
result = strcmp(s2, s3); // r esult > 0 result = strcmp(s2, s2); // r esult = 0 result = strcmp(s3, s2); // r esult < 0 (5) 串定位 char *strchr(char *str, char ch); p = strchr(s1, ′s′); //p指在s1中字符′s′的位置 strcpy(p, s2); //s1 ="I am a teacher"

99 C++的流库（iostream.h）为字符输入流cin（键盘）和字符输出流cout（屏幕）提供I/O操作，使用方法如下：
(1) 读串 StreamVariable >> str cin >> s4;//若输入"Hello!", 则s4 =“Hello!" (2) 写串 StreamVariable << str cout << s4; //输出"Hello!"

100 例5―1 名和姓的对换问题。英国和美国人的姓名是名在前姓在后，但在有些情况下，需要把姓名写成姓在前名在后中间加一个逗号的形式。编写一个程序实现把名在前姓在后的姓名表示法转换成姓在前名在后中间加一个逗号的姓名表示法。   程序如下： ＃include <string.h> ＃include <iostream.h>  void ReverseName(char *name, char *newName) { char *p;  p = strchr(name, ′ ′); //p指在空格′ ′位置

101 *p = NULL; //把空格换为NULL，因此na
me的长度只包括名 strcpy(newName, p+1); //p+1是name的姓，因此newName等 于name的姓 strcat(newName, ","); // newName等于姓加逗号 strcat(newName, name); // newName等于姓加逗号加名   *p = ′ ′; //恢复name为开始时的状态 } void main(void)

102 { char name［30］, new Name［30］; cin.getline(name, 30, ′＼n′); Reverse Name(name, new Name); cout << "Reverse Name: " << new Name << endl; } 程序运行如下： William Topp //键盘输入 Topp,William //屏幕输出

103 读者只要按照C++的字符串内存表示法自动在字符串末尾处添加结束标识符NULL就可理解函数Reverse Name( )的执行过程。方法是按照程序首先把输入名姓的空格改写为NULL(注意， 此时的NULL后边，即指针p+1指示的是原字符串name的姓部分；此时的name表示的是原name的名部分），再把原name的姓、逗号和名逐步添加到new Name中，最后再恢复name为开始时的状态。

104 方便用户使用的串类的定义和实现 丰富的串库函数是实现高效的串操作的得心应手的工具包，但对大多数程序员，甚至是一些虽经验丰富但不经常使用C++编程的程序员来说，C++提供的串库函数的技术性太强（与上节很简单的举例比较），使用起来不很方便。在一些高级程序设计语言中，比如BASIC语言，支持“+” 运算符表示的连接运算，支持“=” 运算符表示的赋值运算，并支持“<”等运算符表示的比较运算，等等。借鉴这些做法，并根据面向对象程序设计的思想，本节我们讨论一个方便用户使用的串类的定义和实现。

105 下面设计的串类String的成员函数有字符串的个数size和存储字符串的字符数组str，为与C++字符串兼容，我们也在字符串末尾添加结束标记符NULL。在下述设计的串类String中，我们不仅设计了前面讨论过的串操作要求的成员函数，还设计了类似BASIC的字符串操作运算符。由于所设计的串类还要兼容C++字符串， 所以每个重载的操作符都要考虑串类和C++字符串操作的各种情况。例如，对逻辑等于操作符（==）重载，有String串类和String串类、String串类和C++字符串，以及C++字符串和String串类等三种逻辑等于情况。

106 方便用户使用的串类的定义如下： ＃include <string.h> ＃include <iostream.h> ＃include <stdlib.h> enum ErrorType{out Of Memory, indexError}; char *strErrorMsg［］ = {"Out Of Memory", "Invalid Index"}; class String {

107 private: char *str; //存储字符串的字符数组 int size; //字符串的个数 public: String(char *s= ""); //C++构造函数 String(const String &s); //构造函数 ~String(void); //析构函数

108 void Error(int ErrorType, int badIndex = 0);
//出错处理 String SubStr(int pos, int length); //取子串返回 void Insert(const String& s, int pos); //插入子串 void Delete(int pos, int length); //删除子串 int Find(char c, int start)const; //查找字符 int Length(void)const; //取字符串长度返回

109 int IsEmpty(void)const; //字符串空否
void Clear(void); //清除字符串空间  int FindSubstr(const String& t, int start); //查找子串  //字符串输出流和输入流重载 friend ostream& operator<< (ostream& ostr, const String& s); friend istream& operator>> (istream& istr, String& s);   char& operator［］(int n)

110 //下标运算符重载 //String串类和C++字符串赋值操作符重载 String& operator= (const String& s); //String串类 String& operator= (char *s); //C++字符串   //String串类和String串类、String串类和C++字 符串 //C++字符串和String串类逻辑相等操作符重载

111 int operator== (const String& s)const;
//String串类和String串类 int operator== (char *s)const; // S tring串类和C[HT6]++字符串 ///C++字符串和String串类 friend int operator== (char *strL, const String& strR);  //逻辑不相等操作符重载 int operator!= (const String& s)const; int operator!= (char *s)const;

112 friend int operator!= (char *strL, const String& strR);
  //逻辑小于操作符重载 int operator< (const String& s)const; int operator< (char *s)const; friend int operator< (char *strL, const String& strR);   //逻辑小于等于操作符重载 int operator<= (const String& s)const; int operator<= (char *s)const; friend int operator<= (char *strL, const String& strR);

113 //逻辑大于操作符重载 int operator> (const String& s)const; int operator> (char *s)const; friend int operator> (char *strL, const String& strR); //逻辑大于等于操作符重载 int operator>= (const String& s)const; int operator>= (char *s)const; friend int operator>= (char *strL, const String& strR);  

114 //字符串连接操作符重载 String operator+ (const String& s) const; String operator+ (char *s) const; friend String operator+ (char *str1, const String& str2);   //字符串连接赋值操作符重载 void operator+= (const String& s); void operator+= (char *s); };

115 1. 构造函数、析构函数和出错处理函数 String::String(char *s) //C++构造函数 { size = strlen(s) + 1; str = new char［size］; if(str == NULL) Error(outOfMemory); strcpy(str, s); } String::String(const String &s) //构造函数

116 size = s.size; str = new char［size］; if(str == NULL) Error(out Of Memory); for(int i = 0; i < size; i++) str［i］ = s.str［i］; } String::~String(void) //析构函数 { delete ［］str; } void String::Error(int ErrorType, int badIndex) //出错处理函数

117 { cout << strErrorMsg［ErrorType］ << endl; exit(1); } 2. 截取从pos开始、长度为length的子串返回函数 String String::SubStr(int pos, int length) int charsLeft = size-pos-1; String temp; //注意默认参数使temp 为空串 char *p, *q;

118 if(pos >= size-1) return temp; //返回空串
 if(length > charsLeft) length = charsLeft; //长度不能越出范围  delete ［］temp.str; //删除默认参数分配的空串空间 temp.str = new char［length+1］; //重新分配空间 if(temp.str == NULL) Error(out Of Memory);

119 //拷贝字符串 p = temp.str; q = &str［pos］; for(int i = 0; i < length; i++) *p++ = *q++; *p = NULL; //在字符串末尾添加结 束标记符NULL temp.size = length + 1; return temp; }

120 3. 字符串输入流和输出流操作符重载函数 ostream& operator<< (ostream& ostr, const String& s) //输出流操作符重载 { cout << s.size << endl; for(int i = 0; i < s.size; i++) cout << s.str［i］; cout << endl; return ostr; }

121 s.size++; return istr; } 4. String串类和C++ 字符串赋值操作符重载函数 String& String::operator= (const String& s)//参数为String串类赋值操作符重载 if(size != s.size) { delete ［］str; str = new char［s.size］;

122 if(str == NULL) Error(out Of Memory);
size = s.size; } for(int i = 0; i < size; i++) str［i］ = s.str［i］; return *this; String& String::operator= (char *s) //参数为C[HT6]++字符串赋值操作符重载 { int length = strlen(s);

123 if(size != length) { delete ［］str; str = new char［length+1］; if(str == NULL) Error(out Of Memory); size = length+1; }  strcpy(str, s); return *this; 

124 5. 三种逻辑等于操作符重载函数 String串类和String串类、String串类和C++字符串，以及C++字符串和String串类逻辑相等操作符重载函数。相等时函数返回1；不等时返回0。 int String::operator== (const String& s)const // String串类和String串类 { return (strcmp(str, s.str) == 0);  } int String::operator== (char *s)const // String串类和C++字符串

125 { return (strcmp(str, s) == 0);  } int operator== (char *strL, const String& strR) //C++字符串和S tring串类{ return (strcmp(strL, strR.str) == 0);  } 上述String类的定义和实现放在文件String.h中。 下面给出一个测试上述String类的简单程序。

126 ＃include "String.h" void main(void) { String str1("Data Strstrure"), str2("Structure"); //测试有值构 造函数 String str3, str4; //测试默认值构造函数  str3 = str1.SubStr(5, 9); //测试SubStr()函数和赋值操作符重载 str4 = str1.SubStr(5, 9);

127 cout << "str3 = " << str3 ;
//测试输出流操作符重载 cout << "str4 = " << str4 ;  //测试String串类和String串类逻辑相等操作符重载 if(str3 == str4) cout << "String == String" << endl;  //测试String串类和C++字符串逻辑相等操作符重载 if(str2 == "Structure") cout << "String == C++ string" << endl;

128 //测试C++字符串和String串类逻辑相等操作符重载
if("Structure" == str2) cout << "C++ string == String" << endl;} 程序的运行结果如下： str3 = 10 Structure Str4 = 10 String == String String == C++ string C++ string == String

129 模式匹配的BruteForce算法 成员函数Find Substr(t, start)称作模式匹配。模式匹配的具体含义是在当前对象串（也称作主串）中从start开始查找一个与串t（也称作模式串）相同的子串。如在主串中查找到一个与模式串t相同的子串，则函数返回模式串t的第一个字符在主串中的下标；如在主串中未查找到一个与模式串t相同的子串，则函数返回-1。

130 BruteForce算法实现模式匹配的思想是：从主串s="s0s1…sn-1"的第一个字符开始与模式串t="t0t1…tm-1"的第一个字符比较: 若相等, 则继续比较后续字符; 否则, 从目标串s的第二个字符开始重新与模式串t的第一个字符比较。如此不断继续，若存在模式串中的每个字符依次和主串中的一个连续字符序列相等，则匹配成功，函数返回模式串t的第一个字符在主串中的下标；否则， 匹配失败，函数返回-1。

131 为便于理解举例说明如下。设主串s="cddcdc"，模式串t="cdc"，s的长度为n=6， t的长度为m=3，用变量i指示主串s的当前比较字符的下标，用变量 j指示模式串t的当前比较字符的下标。模式匹配过程如图5―5所示。

132 图5―5 模式匹配过程

133 由此我们可以推知两点： (1) 若在前k-1次比较中未匹配成功，则第k次比较是从s中的第k个字符sk-1开始与t中的第1个字符t0比较。 (2) 设某一次匹配有si≠tj，其中0≤i<n，0≤j<m，i≥j，则应有si-1=tj-1，…， si-j+1=t1，si-j=t0 。再由（1）知，下一次比较主串的字符si-j+1和模式串的第一个字符t0 。

134 图5―6 模式匹配的一般性过程

135 根据上面的分析，成员函数Find Substr(t, start)可设计如下：  
int String::Find Substr(const String& t, int start) { int i = start, j = 0, v;   while(i < size-1 && j < t.size-1) if(str［i］ == t.str［j］)

136 i++; j++; } else { i = i-j+1; j = 0;

137 if(j >= t.size-1) v = i-t.size+1;
else v = -1; return v; } 这个算法简单和易于理解，但有些情况下时间效率不高。主要原因是主串下标i在若干个字符序列比较相等后， 只要有一个字符比较不相等， 便需要把下标i的值回退。该算法在最好情况下的时间复杂度为O(m)，即主串的前m个字符刚好就等于模式串的m个字符，该算法在最坏情况下的时间复杂度为O(n*m)。

138 算法的最坏情况可分析如下：当模式串的前m-1个字符序列与主串的相应字符序列比较总是相等，但模式串的第m个字符与主串的相应字符比较总是不等。此时，模式串的m个字符序列必须与主串的相应字符序列块一共比较n-m+1次，每次比较m个字符，所以总共需比较m*(n-m+1)次，因此其时间复杂度为O(n*m)。如s="aaaaaaaa"，t="aab"，n=8，m=3，t的前2个字符序列与s的相应字符序列比较总是相等， t的第3个字符与s的相应字符比较总是不等，t的3个字符序列与s的相应字符序列块一共比较了n-m+1=6次，每次比较了3个字符，总共比较了m*( n-m+1)=18次。

139 模式匹配的KMP算法 KMP算法是在BruteForce算法的基础上的模式匹配的改进算法。KMP算法的特点主要是消除了BruteForce算法的如下缺点： 主串下标i在若干个字符序列比较相等后， 只要有一个字符比较不相等便需要把下标i的值回退。分析BruteForce算法的匹配过程可以发现，算法中的主串下标i值的回退并非一定必要。这可分两种情况讨论。

140 第一种情况是模式串中无真子串（关于模式串中的真子串将在下面讨论)， 如图5―5的主串s="cddcdc"、模式串t="cdc"的模式匹配过程。当s0=t0，s1=t1，s2≠t2时，算法中取i=1,j=0，使主串下标i值回退，然后比较s1和t0。但是因t1≠t0，所以一定有s1≠t0，实际上接下来就可直接比较s2和t0。 第二种情况是模式串中有真子串。设主串s="abacabab"、模式串t="abab"。 第一次匹配过程如图5―7所示。此时, 因t0≠t1，s1=t1，必有s1≠t0；又因t0=t2，s2=t2，必有s2=t2， 因此接下来可直接比较s3和t1。

141 图5―7 模式匹配的一个例子

142 总结以上两种情况可以发现，一旦si和tj比较不相等，主串s的下标值都可不必回退，主串的si（或si+1）可直接与模式串的tk（0≤k<j）比较，k的确定与主串s并无关系，而只与模式串t本身的构成有关，即从模式串本身就可求出k的值。   现在我们讨论一般情况。设s="s0s1...sn-1"，t="t0t1...tm-1"，当si≠tj（0≤i<n,0≤j<m）时，存在 "si-jsi-j+1…si-1" = "t0t1…tj-1" (5―12) 此时若模式串中存在可相互重叠的真子串，满足 "t0t1...tk-1" = "tj-ktj-k+1…tj-1" （0<k<j） (5―13)

143 则说明模式串中的子串"t0t1…tk-1"已和主串"si-ksi-k+1…si-1"匹配。下一次可直接比较si和tk；此时若模式串中不存在可相互重叠的真子串，则说明在模式串"t0t1…tj-1"中不存在任何以t0为首字符的字符串与"si-jsi-j+1…si-1"中以si-1为末字符的字符串匹配，下一次可直接比较si和t0。 现在我们讨论关于模式串中的真子串问题。我们把模式串中从第一个字符开始到任一个字符为止的模式串中的真子串定义为next［j］函数，则next［j］函数定义为

144 当此集合非空时 其他情况 (5―14) 当j=0 若模式串t中存在真子串"t0t1…tk-1" = "tj-ktj-k+1…tj-1"且满足0<k<j，则next［j］表示当模式串t中的tj与主串s的si比较不相等时，模式串t中需重新与主串s的si比较的字符下标为k，即下一次开始比较si和tk； 若模式串t中不存在如上所说的真子串，有next［j］=0，则下一次开始比较si和t0；当j=0时令next［j］=-1， 此处-1为一标记，表示下一次开始比较si+1和t0 。

145 上述匹配过程如图5―8所示。当模式串t中存在真子串"t0t1…tk-1" = "tj-ktj-k+1…tj-1"时，若模式串t中的tj与主串s的si比较不相等，我们此时可将模式串t按照next［j］的值右滑。模式串t右滑后若仍有si≠tk,则模式串t按照next［j］的值右滑的过程可一直进行下去，直到next［j］=-1时模式串t不再右滑，下一次开始比较si+1和t0 。简而言之，KMP算法对BruteForce算法的改进就是利用已经得到的部分匹配结果将模式串t右滑一段距离再继续比较，从而无需回退主串s的下标值。  

146 图5―8 模式串t的右滑

147 例5―2 计算t="aba"的next［j］。 当j=0时，next［0］=-1； 当j=1时，next［1］=0；
当j=2时，t0≠t1，next［2］=0。 即有 模式 a b c j 1 2 Next[j] -1

148 例5―3 计算t="abcabcaaa"的next［j］。
当j=0时，next［0］=-1； 当j=1时，next［1］=0； 当j=2时，t0≠t1，next［2］=0； 当j=3时，t0≠t2，next［3］=0； 当j=4时，t0＝t3＝′a′, next［4］=1； 当j=5时，t0t1＝t3t4＝′ab′, next［5］=2；  

149 当j=6时，t0t1t2＝t3t4t5＝′abc′, next［6］=3；
当j=7时，t0t1t2t3≠t3t4t5t6, t0＝t6＝′a′, next［7］=1； 当j=8时，t0t1≠t6t7, t0＝t7＝′a′, next［8］=1；即有 模式 a b c j 1 2 3 4 5 6 7 8 Next[j] -1

150 KMP算法的思想是：设s为主串，t为模式串;设i为主串s当前比较字符的下标，j为模式串t当前比较字符的下标，令i和j的初值为0。当si=tj时，i和j分别增1再继续比较；否则，i不变，j改变为等于next［j］，再继续比较。依此类推， 直到下列两种情况之一：一种是j退回到某个j=next［j］时有si=tj，则i和j分别增1再继续比较；另一种是j退回到j=-1，此时令主串和模式串的下标各增1，再继续比较。

151 在已知next［j］函数的情况下，Find Substr（）函数可设计如下：int Find Substr(const String& s, const String& t, int start, int next［］) //查找主串s从start开始的模式串t, 找到返回t在s中的开始字符下标; 否则返回-1 //数组next［］中存放有模式串t的next［j］值 { int i = start, j = 0, v;

152 while(i < s.size-1 && j < t.size-1)
{ if(j == -1 || s.str［i］ == t.str［j］) i++; j++; } else j = next［j］;  } if(j >= t.size-1) v = i-t.size+1; else v = -1;

153 return v; } 我们再来讨论求next［j］的算法问题。从前面我们给出的计算next［j］值的例子可以看出，next［j］值的计算问题是一个递推计算问题。设有next［j］=k，即在模式串t中存在″t0t1…tk-1″ = "tj-ktj-k+1…tj-1"（0<k<j），其中k为满足等式的最大值，则计算next［j+1］的值有两种情况：

154 (1) 若tk=tj，则表明在模式串t中有“t0t1…tk” = “tj-ktj-k+1…tj”，且不可能存在任何一个k′>k满足上式，因此有：
next［j+1］ = next［j］ + 1 = k + 1 (2) 若tk≠tj，则可把计算next［j+1］值的问题看成是一个如图 5 ― 9 的模式匹配问题，即把模式串t′，向右滑动至k′=next［k］（0<k′<k<j），若tk′＝tj，则表明在模式串t中有"t0t1…tk′" = "tj-k′tj-k′+1…tj"（0<k′<k<j），因此有： next［j+1］ = k′ + 1 = next［k］ + 1

155 若tk′≠tj，则将模式串t′继续右滑到k"= next［k′］。依此类推，直到某次匹配成功或匹配失败，最后一次匹配失败为：
next［j+1］ = next［0］ + 1 = = 0 图5―9 求next［j+1的模式匹配

156 因此，可有如下类同于求子串FindSubstr(s, t, start, next ［］)的方法求next［j］的函数GetNext(t, next［］)：
void Get Next(const String& t, int next［］) //求模式串t的next［j］值存于next［］中 { int j = 0, k = -1;   next［0］ = -1; while(j < t.size-1)

157 if(k == -1 || t.str［j］ == t.str［k］)
{ j++; k++; next［j］ = k; } else k = next［k］; }