? 一维数组
多维数组
线性表
顺序表
多项式
稀疏矩阵
字符串一维数组
定义相同类型的数据元素的集合。
一维数组的示例
与顺序表的不同在于数组可以按元素的下标直接存储和访问数组元素。
35 27 49 18 60 54 77 83 41 02
0 1 2 3 4 5 6 7 8 9
数组的定义和初始化
#include <iostream.h>
class szcl {
int e;
public:
szcl ( ) { e = 0; }
szcl ( int value ) { e = value; }
int get_value ( ) { return e; }
}
main ( ) {
szcl a1[3] = { 3,5,7 },*elem;
for ( int i = 0; i < 3; i++ )
cout << a1[i].get_value ( ) <<,\n”; //静态
elem = a1;
for ( int i = 0; i < 3; i++ ) {
cout << elem->get_value( ) <<,\n”; //动态
elem++;
}
return 0;
}
一维数组 (Array)类的定义
#include <iostream.h>
#include <stdlib.h>
template <class Type>
class Array {
Type *elements; //数组存放空间
int ArraySize; //当前长度
void getArray ( ); //建立数组空间
public:
Array( int Size=DefaultSize );
Array( const Array<Type>& x );
~Array( ) { delete [ ]elements;}
Array<Type> & operator = //数组复制
( const Array<Type> & A );
Type& operator [ ] ( int i ); //取元素值
int Length ( ) const { return ArraySize; }
//取数组长度
void ReSize ( int sz ); //扩充数组
}
template <class Type>
void Array<Type>,,getArray ( ) {
//私有函数：创建数组存储空间
elements = new Type[ArraySize];
if ( elements == NULL ) {
arraySize = 0;
cerr <<,存储分配错 ！ " << endl;
return;
}
}
一维数组公共操作的实现
template <class Type>
Array<Type>,,Array ( int sz ) {
//构造函数
if ( sz <= 0 ) {
arraySize = 0;
cerr <<,非法数组大小,<< endl;
return;
}
ArraySize = sz;
getArray ( );
}
template <class Type> Array<Type>,:
Array ( Array<Type> & x ) { //复制构造函数
int n = ArraySize = x.ArraySize;
elements = new Type[n];
if ( elements == NULL ) {
arraySize = 0;
cerr <<,存储分配错,<< endl;
return;
}
Type *srcptr = x.elements;
Type *destptr = elements;
while ( n-- ) * destptr++ = * srcptr++;
}
template <class Type>
Type& Array<Type>,,operator [ ] ( int i ) {
//按数组名及下标 i,取数组元素的值
if ( i < 0 || i > ArraySize-1 ) {
cerr <<,数组下标超界,<< endl;
return NULL;
}
return elements[i];
}
使用该函数于赋值语句
Pos = Position[i -1] + Number[i -1]
template <class Type>
void Array<Type>,,Resize ( int sz ) {
if ( sz >= 0 && sz != ArraySize ) {
Type * newarray = new Type[sz];
//创建新数组
if ( newarray == NULL ) {
cerr <<,存储分配错,<< endl;
return;
}
int n = ( sz <= ArraySize )? sz,ArraySize;
//按新的大小确定传送元素个数
Type *srcptr = elements; //源数组指针
Type *destptr = newarray; //目标数组指针
while ( n-- ) * destptr++ = * srcptr++;
//从源数组向目标数组传送
delete [ ] elements;
elements = newarray;
ArraySize = sz;
}
}
多维数组
多维数组是一维数组的推广
多维数组是一种非线性结构。其特点是 每一个数据元素可以有多个直接前驱和多个直接后继 。
数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性结构简单。
二维数组 三维数组行向量 下标 i 页向量 下标 i
列向量 下标 j 行向量 下标 j
列向量 下标 k
数组的连续存储方式
一维数组
35 27 49 18 60 54 77 83 41 02
0 1 2 3 4 5 6 7 8 9
l l l l l l l l l l
LOC(i) = LOC(i-1)+l = a+i*l
LOC(i) = LOC(i-1)+l = a+i*l,i > 0a,i = 0
a+i*l
a
二维数组
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
111101
121202
111101
101000
mnanana
maaa
maaa
maaa
a
行优先存放：
设数组开始存放位置 LOC( 0,0 ) = a,每个元素占用 d 个存储单元
LOC ( j,k ) = a + ( j * m + k ) * d
二维数组
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
111101
121202
111101
101000
mnanana
maaa
maaa
maaa
a
列优先存放：
设数组开始存放位置 LOC( 0,0 ) = a,每个元素占用 d 个存储单元
LOC ( j,k ) = a + ( k * n + j ) * d
三维数组
各维元素个数为 m1,m2,m3
下标为 i1,i2,i3的数组元素的存储地址：
（按页 /行 /列存放）
LOC ( i1,i2,i3 ) = a +
( i1* m2 * m3 + i2* m3 + i3 ) * l
前 i1页总元素个数第 i1页的前 i2行 总元素个数第 i2 行前 i3
列 元素个数
n 维数组
各维元素个数为 m1,m2,m3,…,m n
下标为 i1,i2,i3,…,i n 的数组元素的存储地址：
limia
n
j
n
jk
nkj *
1
1 1
LOC ( i1,i2,…,i n ) = a +
( i1*m2*m3*…*m n + i2*m3*m4*…*m n+
+ ……+ i n-1*mn + in ) * l
线性表 (Linear List)
线性表的定义和特点
定义 n（? 0） 个数据元素的有限序列，记作
（ a1,a2,…,an）
ai 是表中数据元素,n 是表长度。
遍历 逐项访问：
从前向后 从后向前线性表的特点
除第一个元素外，其他每一个元素有一个且仅有一个 直接前驱 。
除最后一个元素外，其他每一个元素有一个且仅有一个 直接后继 。
a1 a2 a3 a4 a5 a6
顺序表 (Sequential List)
顺序表的定义和特点
定义 将线性表中的元素相继存放在一个连续的存储空间中。
可利用 一维数组 描述 存储结构
特点 线性表的顺序存储方式
遍历 顺序 访问
25 34 57 16 48 09
0 1 2 3 4 5
data
顺序表 (SeqList)类的定义
template <class Type> class SeqList {
Type *data; //顺序表存储数组
int MaxSize; //最大允许长度
int last; //当前最后元素下标
public:
SeqList ( int MaxSize = defaultSize );
~SeqList ( ) { delete [ ] data; }
int Length ( ) const { return last+1; }
int Find ( Type& x ) const; //查找
int Locate ( int i ) const; //定位
int Insert ( Type & x,int i ); //插入
int Remove ( Type & x ); //删除
int Next ( Type & x ) ; //后继
int Prior ( Type & x ) ; //前驱
int IsEmpty ( ) { return last ==-1; }
int IsFull ( ) { return last == MaxSize-1; }
Type Get ( int i ) { //提取
return i < 0 || i > last？ NULL,data[i];
}
}
顺序表部分公共操作的实现
template <class Type> //构造函数
SeqList<Type>,,SeqList ( int sz ) {
if ( sz > 0 ) {
MaxSize = sz; last = -1;
data = new Type[MaxSize];
if ( data == NULL ) {
MaxSize = 0; last = -1;
return;
}
}
}
template <class Type>
int SeqList<Type>,,Find ( Type & x ) const {
//搜索函数,在顺序表中从头查找结点值等于
//给定值 x的结点
int i = 0;
while ( i <= last && data[i] != x )
i++;
if ( i > last ) return -1;
else return i;
}
顺序搜索图示
25 34 57 16 48 09
0 1 2 3 4 5
data
搜索 16 i
25 34 57 16 48 09
i
25 34 57 16 48 09
i
25 34 57 16 48 09
i 搜索成功
25 34 57 16 48
0 1 2 3 4
data
搜索 50 i
25 34 57 16 48
i
25 34 57 16 48
i
25 34 57 16 48
i
25 34 57 16 48
i 搜索失败搜索成功 的平均比较次数若搜索概率相等，则搜索不成功 数据比较 n 次
i
n
i
i cp
1
0
=A C N
2
1
2
)(11
)2(1
1
1)(
1
=
1
0
nnn
n
n
n
i
n
n
i
A C N?
22
1)(
1)(
1
0)1(
1
1
)(
1
1
=
0
nnn
n
n
n
in
n
n
i
A M N
表项的插入
25 34 57 16 48 09 63
0 1 2 3 4 5 6 7
data
50插入 x
25 34 57 50 16 48 09 63
0 1 2 3 4 5 6 7
data 50
i
template <class Type>
int SeqList<Type>,,Insert (Type& x,int i ) {
//在表中第 i 个位置插入新元素 x
if ( i < 0 || i > last+1 || last == MaxSize-1 )
return 0; //插入不成功
else {
last++;
for ( int j = last; j > i; j-- )
data[j] = data[j -1];
data[i] = x; return 1; //插入成功
}
}
表项的删除
1
0 2
1
2
1)(11)(1= n
i
nnn
n
in
n
A M N
25 34 57 50 16 48 09 63
0 1 2 3 4 5 6 7
data 16
删除 x
25 34 57 50 48 09 63
0 1 2 3 4 5 6 7
data
template <class Type>
int SeqList<Type>,,Remove ( Type& x ) {
//在表中删除已有元素 x
int i = Find (x); //在表中搜索 x
if ( i >= 0 ) {
last-- ;
for ( int j = i; j <= last; j++ )
data[j] = data[j+1];
return 1; //成功删除
}
return 0; //表中没有 x
}
顺序表的应用,集合的“并”运算
void Union ( SeqList<int> & A,
SeqList<int> & B ) {
int n = A.Length ( );
int m = B.Length ( );
for ( int i = 0; i < m; i++ ) {
int x = B.Get(i); //在 B中取一元素
int k = A.Find (x); //在 A中搜索它
if ( k == -1 ) //若未找到插入它
{ A.Insert (n,x); n++; }
}
}
void Intersection ( SeqList<int> & A,
SeqList<int> & B ) {
int n = A.Length ( );
int m = B.Length ( ); int i = 0;
while ( i < n ) {
int x = A.Get (i); //在 A中取一元素
int k = B.Find (x); //在 B中搜索它
if ( k == -1 ) { A.Remove (i); n--; }
else i++; //未找到在 A中删除它
}
}
顺序表的应用,集合的“交”运算
i
n
i
i
n
nn
xa
xaxaxaaxP
0
2
210
)(?
多项式 (Polynomial)
n阶多项式 Pn(x) 有 n+1 项 。
系数 a0,a1,a2,…,an
指数 0,1,2,…,n。按升幂排列
class Polynomial {
public,
Polynomial ( ); //构造函数
int operator ! ( ); //判是否零多项式
float Coef ( int e);
int LeadExp ( ); //返回最大指数
Polynomial Add (Polynomial poly);
Polynomial Mult (Polynomial poly);
float Eval ( float x); //求值
}
多项式 (Polynomial)的抽象数据类型
#include <iostream.h>
class power {
double x;
int e;
double mul;
public:
power (double val,int exp); //构造函数
double get_power ( ) { return mul; } //取幂值
};
创建 power类，计算 x的幂
power,,power (double val,int exp) {
//按 val值计算乘幂
x = val; e = exp; mul = 1.0;
if ( exp == 0 ) return;
for ( ; exp > 0; exp--) mul = mul * x;
}
main ( ) {
power pwr ( 1.5,2 );
cout << pwr.get_power ( ) <<,\n”;
}
多项式的存储表示第一种,private,
(静态数 int degree;
组表示 ) float coef [maxDegree+1];
Pn(x)可以表示为,
pl.degree = n
pl.coef[i] = ai,0? i? n
a0 a1 a2 …… an ………
0 1 2 degree maxDegree-1
coef
n
第二种,private:
(动态数 int degree;
组表示 ) float * coef;
Polynomial,,Polynomial (int sz) {
degree = sz;
coef = new float [degree + 1];
}
以上两种存储表示适用于指数连续排列的多项式。但对于指数不全的多项式如 P101(x) = 3 + 5x50 - 14x101,不经济。
第三种,
class Polynomial;
class term { //多项式的项定义
friend Polynomial;
private,
float coef; //系数
int exp; //指数
};
a0 a1 a2 …… ai …… am
e0 e1 e2 …… ei …… em
coef
exp
0 1 2 i m
class Polynomial { //多项式定义
public:
……
private:
static term termArray[MaxTerms]; //项数组
static int free; //当前空闲位置指针
// term Polynomial::termArray[MaxTerms];
// int Polynomial::free = 0;
int start,finish; //多项式始末位置
}
A(x) = 2.0x1000+1.8
B(x) = 1.2 + 51.3x50 + 3.7x101
两个多项式存放在 termArray中
A.start A.finish B.start B.finish free
coef
exp
1.8 2.0 1.2 51.3 3.7 ……
0 1000 0 50 101 ……
maxTerms
两个多项式的相加
结果多项式另存
扫描两个相加多项式，若都未检测完：
若当前被检测项 指数相等,系数相加。若未变成 0，则将结果加到结果多项式。
若当前被检测项 指数不等,将指数小者加到结果多项式。
若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。
Polynomial Polynomial,:
operator + ( Polynomial B ) {
Polynomial C;
int a = start; int b = B.start; C.start = free;
float c;
while ( a <= finish && b <= B.finish )
Switch ( compare ( termArray[a].exp,
termArray[b].exp) ) { //比较对应项指数
case?=?,//指数相等
c = termArray[a].coef + //系数相加
termArray[b].coef;
if ( c ) NewTerm ( c,termArray[a].exp );
a++; b++; break;
case?>?,//b指数小,建立新项
NewTerm ( termArray[b].coef,
termArray[b].exp );
b++; break;
case '<',//a指数小,建立新项
NewTerm ( termArray[a].coef,
termArray[a].exp );
a++;
}
for ( ; a <= finish; a++ ) //a未检测完时
NewTerm ( termArray[a].coef,
termArray[a].exp );
for ( ; b <= B.finish; b++ ) //b未检测完时
NewTerm ( termArray[b].coef,
termArray[b].exp );
C.finish = free-1;
return C;
}
在多项式中加入新的项
void Polynomial,,NewTerm ( float c,int e ) {
//把一个新的项加到多项式 C(x)中
if ( free >= maxTerms ) {
cout << "Too many terms in polynomials”
<< endl;
return;
}
termArray[free].coef = c;
termArray[free].exp = e;
free++;
}
00002800
00000091
03900000
0006000
017000110
150022000
A
76
稀疏矩阵 (Sparse Matrix)
非零元素个数 远远少于矩阵元素个数稀疏矩阵的定义
设矩阵 Am?n 中有 t 个非零元素，若 t 远远小于矩阵元素的总数 m?n，则称矩阵
A 为稀疏矩阵。
为节省存储空间，应只存储非零元素。
非零元素的分布一般没有规律，应在存储非零元素时，同时存储该非零元素的行下标 row、列下标 col、值 value。
每一个非零元素由一个三元组唯一确定：
( 行号 row,列号 col,值 value )
稀疏矩阵的抽象数据类型
template<class Type> class SparseMatrix;
template<class Type> class Trituple { //三元组
friend class SparseMatrix <Type>
private:
int row,col; //非零元素行号 /列号
Type value; //非零元素的值
}
template <class Type> class SparseMatrix {
//稀疏矩阵类定义
int Rows,Cols,Terms; //行 /列 /非零元素数
Trituple<Type> smArray[MaxTerms];
public,//三元组表
SparseMatrix (int MaxRow,int Maxcol);
SparseMatrix<Type>& Transpose
(SparseMatrix<Type>&); //转置
SparseMatrix<Type>&Add (SparseMatrix
<Type> a,SparseMatrix<Type> b); //相加
SparseMatrix<Type>& Multiply(SparseMatrix
<Type> a,SparseMatrix<Type> b); //相乘
}
稀疏矩阵的转置
一个 m?n 的矩阵 A，它的转置矩阵 B 是一个 n?m 的矩阵，且 A[i][j] = B[j][i]。 即矩阵 A 的行成为矩阵 B 的列，矩阵 A 的列成为矩阵 B 的行。
在稀疏矩阵的三元组表中，非零矩阵元素按行存放。当行号相同时，按列号递增的顺序存放。
稀疏矩阵的转置运算要转化为对应三元组表的转置。
00002800
00000091
03900000
0006000
017000110
150022000
稀疏矩阵行行
(( rr oo w ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
[0] 00 33 22 22
[1] 00 66 11 55
[2] 11 11 11 11
[3] 11 55 11 77
[4] 22 33 -- 66
[5] 33 55 33 99
[6] 44 00 99 11
[7] 55 22 22 88
0000015
00390170
000000
0006022
2800000
0000110
0910000
转置矩阵行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
[0] 00 44 99 11
[1] 11 11 11 11
[2] 22 55 22 88
[3] 33 00 22 22
[4] 33 22 -- 66
[5] 55 11 11 77
[6] 55 33 33 99
[7] 66 00 11 66
用三元组表表示的稀疏矩阵及其转置行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
[0] 00 33 22 22 [0] 00 44 99 11
[1] 00 66 11 55 [1] 11 11 11 11
[2] 11 11 11 11 [2] 22 55 22 88
[3] 11 55 11 77 [3] 33 00 22 22
[4] 22 33 -- 66 [4] 33 22 -- 66
[5] 33 55 33 99 [5] 55 11 11 77
[6] 44 00 99 11 [6] 55 33 33 99
[7] 55 22 22 88 [7] 66 00 11 66
稀疏矩阵转置算法思想
设矩阵列数为 Cols，对矩阵三元组表扫描 Cols 次。第 k 次检测列号为 k
的项。
第 k 次扫描找寻所有列号为 k 的项，
将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。
稀疏矩阵的转置
template <class Type> SparseMatrix<Type>&
SparseMatrix<Type>,,Transpose
(SparseMatrix<Type>& a) {
SparseMatrix<Type> b (a.Cols,a.Rows);
b.Rows = a.Cols; b.Cols = a.Rows;
b.Terms = a.Terms;
//转置矩阵的列数,行数和非零元素个数
if ( a.Terms > 0 ) {
int CurrentB = 0;
//转置三元组表存放指针
for ( int k = 0; k < a.Cols; k++ )
//对所有列号处理一遍
for ( int i = 0; i < a.Terms; i++ )
if ( a.smArray[i].col == k ) {
b.smArray[CurrentB].row = k;
b.smArray[CurrentB].col =
a.smArray[i].row;
b.smArray[CurrentB].value=
a.smArray[i].value;
CurrentB++;
}
}
return b;
}
快速转置算法
设矩阵三元组表总共有 t 项，上述算法的时间代价为 O ( n* t )。
若矩阵有 200 行,200 列,10,000 个非零元素，总共有 2,000,000 次处理。
为加速转置速度，建立辅助数组 rowSize
和 rowStart，记录 矩阵转置后各行非零元素个数 和各 行元素在转置三元组表中开始存放位置 。
扫描矩阵三元组表，根据某项列号，确定它转置后的行号,查 rowStart 表,按查到的位置直接将该项存入转置三元组表中
[0] [1] [2] [3] [4] [5] [6] 语 义
row Siz e 1 1 1 2 0 2 1 矩阵 A 各列非零元素个数
row Start 0 1 2 3 5 5 7 矩阵 B 各行开始存放位置
for ( int i = 0; i < a.Cols; i++ ) rowSize[i] = 0;
for ( i = 0; i < a.Terms; i++ )
rowSize[a.smArray[i].col]++;
rowStart[0] = 0;
for ( i = 1; i < Cols; i++ )
rowStart[i] = rowStart[i-1]+rowSize[i-1];
稀疏矩阵的快速转置
template <class Type> SparseMatrix<Type>&
SparseMatrix<Type>,,FastTranspos
(SparseMatrix<Type>& a) {
int *rowSize = new int[a.Cols];
int *rowStart = new int[a.Cols];
SparseMatrix<Type> b ( a.Cols,a.Rows );
b.Rows = a.Cols; b.Cols = a.Rows;
b.Terms = a.Terms;
if ( a.Terms > 0 ) {
for (int i = 0; i < Cols; i++) rowSize[i] = 0;
for ( i = 0; i < Terms; i++ )
rowSize[smArray[i].col]++;
rowStart[0] = 0;
for ( i = 1; i < a.Cols; i++ )
rowStart[i] = rowStart[i-1]+rowSize[i-1];
for ( i = 0; i < a.Terms; i++ ) {
int j = rowStart[a.smArray[i].col];
b.smArray[j].row = a.smArray[i].col;
b.smArray[j].col = a.smArray[i].row;
b.smArray[j].value = a.smArray[i].value;
rowStart[a.smArray[i].col]++;
}
}
delete [ ] rowSize; delete [ ] rowStart;
return b;
}
字符串 (String)
字符串是 n (? 0 ) 个字符的有限序列，
记作 S,,c1c2c3…c n”
其中,S 是串名字
,c1c2c3…c n”是串值
ci 是串中字符
n 是串的长度。
例如,S =,Tsinghua University”
const int maxLen = 128;
class String {
int curLen; //串的当前长度
char *ch; //串的存储数组
public:
String ( const String& ob );
String ( const char * init );
String ( );
~String ( ) { delete [ ] ch; }
字符串抽象数据类型和类定义
int Length ( ) const { return curLen; }
//求当前串 *this的实际长度
String &operator ( ) ( int pos,int len );
//取 *this从 pos开始 len个字符组成的子串
int operator == ( const String &ob )
{ return strcmp (ch,ob.ch) == 0; }
//判当前串 *this与对象串 ob是否相等
int operator != ( const String &ob )
const { return strcmp (ch,ob.ch) != 0; }
//判当前串 *this与对象串 ob是否不等
int operator ! ( )
const { return curLen == 0; }
//判当前串 *this是否空串
String &operator = (String &ob);
//将串 ob赋给当前串 *this
String &operator += (String &ob);
//将串 ob连接到当前串 *this之后
char &operator [ ] ( int i );
//取当前串 *this的第 i 个字符
int Find ( String& pat ) const;
}
String,,String ( const String& ob ) {
//复制构造函数：从已有串 ob复制
ch = new char[maxLen+1]; //创建串数组
if ( ch == NULL ) {
cerr <<,存储分配错 ! \n”;
exit(1);
}
curLen = ob.curLen; //复制串长度
strcpy ( ch,ob.ch ); //复制串值
}
字符串部分操作的实现
String,,String ( const char *init ) {
//复制构造函数,从已有字符数组 *init复制
ch = new char[maxLen+1]; //创建串数组
if ( ch == NULL ){
cerr <<,存储分配错 ! \n”;
exit(1);
}
curLen = strlen ( init ); //复制串长度
strcpy ( ch,init ); //复制串值
}
String,,String ( ) {
//构造函数：创建一个空串
ch = new char[maxLen+1]; //创建串数组
if ( ch == NULL ) {
cerr <<,存储分配错 !\n”;
exit(1);
}
curLen = 0;
ch[0] =?\0?;
}
提取子串的算法示例
pos+len -1 pos+len -1
curLen-1? curLen
i n f i n i t y i n f i n i t y
pos = 2,len = 3 pos = 5,len = 4
f i n i t y
超出
String& String,,operator ( ) (int pos,int len) {
//从串中第 pos 个位置起连续提取 len 个字符
//形成子串返回
String * temp = new String; //动态分配
if (pos<0 || pos+len-1 >= maxLen || len<0) {
temp->curLen = 0; //返回空串
temp->ch[0] = '\0';
}
else { //提取子串
if ( pos+len -1 >= curLen )
len = curLen - pos;
temp->curLen = len; //子串长度
for ( int i = 0,j = pos; i < len; i++,j++ )
temp->ch[i] = ch[j]; //传送串数组
temp->ch[len] =?\0?; //子串结束
}
return * temp;
}
例：串 st =,university”,pos = 3,len = 4
使用示例 subSt = st (3,4)
提取子串 subSt =,vers”
String& String,,operator = ( String& ob ) {
//串赋值：从已有串 ob复制
if ( &ob != this ) {
delete [ ] ch;
ch = new char [maxLen+1]; //重新分配
if ( ch == NULL )
{ cerr <<,内存不足 !\n”; exit (1);}
curLen = ob.curLen; //串复制
strcpy ( ch,ob.ch );
}
else cout <<,字符串自身赋值出错 ! \n”;
return *this;
}
char& String,,operator [ ] ( int i ) {
//按串名提取串中第 i 个字符
if ( i < 0 && i >= curLen )
{ cout <<,串下标超界 !\n,; exit (1); }
return ch[i];
}
例：串 st =,university”,
使用示例 newSt = st； newChar = st[1];
数组赋值 newSt =,university”
提取字符 newChar =?n?
String& String,,operator += ( String& ob ) {
//串连接
char * temp = ch; //暂存原串数组
curLen += ob.curLen; //串长度累加
ch = new char [maxLen+1];
if ( ch == NULL )
{ cerr <<,存储分配错 !\n,; exit (1); }
strcpy ( ch,temp ); //拷贝原串数组
strcat ( ch,ob.ch ); //连接 ob串数组
delete [ ] temp; return *this;
}
例：串 st1 =,beijing,,
st2 =,university”,
使用示例 st1 += st2;
连接结果 st1 =,beijing university”
st2 =,university”
串的模式匹配
定义 在串中寻找子串（第一个字符）在串中的位置
词汇 在模式匹配中，子串称为 模式,串称为 目标 。
示例 目标 T,,Beijing”
模式 P,,jin”
匹配结果 = 3
第 1趟 T a b b a b a 穷举的模式
P a b a 匹配过程第 2趟 T a b b a b a
P a b a
第 3趟 T a b b a b a
P a b a
第 4趟 T a b b a b a
P a b a
int String,,Find ( String &pat ) const {
//穷举的模式匹配
char * p = pat.ch,* s = ch; int i = 0;
if ( *p && *s ) //当两串未检测完
while ( i <= curLen - pat.curLen )
if ( *p++ == *s++ ) //比较串字符
if ( !*p ) return i; //相等
else { i++; s = ch + i; p = pat.ch; }
//对应字符不相等，对齐目标的
//下一位置，继续比较
return -1;
}
目标 T t0 t1 t2 …… tm-1 … tn-1
模式 pat p0 p1 p2 …… pm-1
目标 T t0 t1 t2 …… tm-1 tm … tn-1
模式 pat p0 p1 …… pm-2 pm-1
目标 T t0 t1 …… ti ti+1…… ti+m-2 ti+m-1… tn-1
‖ ‖ ‖ ‖
模式 pat p0 p1 …… pm-2 pm-1
改进的模式匹配
穷举的模式匹配算法时间代价：
最坏情况比较 n-m+1趟，每 趟比较 m次，总比较次数达 (n-m+1)*m
原因在于 每趟重新比较时，目标串的检测指针要回退。改进的模式匹配算法可使目标串的检测指针每趟不回退。
改进的模式匹配 (KMP)算法的时间代价：
若每趟第一个不匹配，比较 n-m+1趟,总比较次数最坏达 (n-m)+m = n
若每趟第 m个不匹配，总比较次数最坏亦达到 n
T t0 t1 … ts-1 ts ts+1 ts+2 … ts+j-1 ts+j ts+j+1 … tn-1
‖ ‖ ‖ ‖ ‖?
P p0 p1 p2 … pj-1 pj pj+1
则有 ts ts+1 ts+2 … ts+j = p0 p1 p2 … pj (1)
为使模式 P 与目标 T 匹配，必须满足
p0 p1 p2 … pj-1 … pm-1 = ts+1 ts+2 ts+3 … ts+j … ts+m
如果 p0 p1 … pj-1? p1 p2 … pj (2)
则立刻可以断定
p0 p1 … pj-1? ts+1 ts+2 … ts+j
下一趟必不匹配同样，若 p0 p1 … pj-2? p2 p3 … pj
则再下一趟也不匹配，因为有
p0 p1 … pj-2? ts+2 ts+3 … ts+j
直到对于某一个,k”值，使得
p0 p1 … pk+1? pj-k-1 pj-k… pj
且 p0 p1 … pk = pj-k pj-k+1 … pj
则 p0 p1 … pk = ts+j-k ts+j-k+1 … ts+j
‖ ‖ ‖
pj-k pj-k+1 … pj
k 的确定方法当比较到模式第 j 个字符失配时,k 的 值 与模式的前 j 个字符有关，与目标无关。
利用失效函数 f (j)可描述。
利用失效函数 f (j) 的匹配处理如果 j = 0，则目标指针加 1，模式指针回到 p0。
如果 j > 0，则目标指针不变，模式指针回到 pf ( j-1)+1。
若设 模式 P = p0 p1… pm-2 pm-1
1,-
,
,<0
,
=)(
1
10
.其它情况的最大整数且使得当
jkjkj
k
ppp
pppjk
k
jf?
j 0 1 2 3 4 5 6 7
PP a b a a b c a c
ff (( jj )) -- 11 -- 11 00 00 11 -- 11 00 -- 11示例,确定失效函数 f (j)
运用 KMP算法的匹配过程第 1趟 目标 a c a b a a b a a b c a c a a b c
模式 a b a a b c a c
j = 1? j = f (j-1)+1 = 0
第 2趟 目标 a c a b a a b a a b c a c a a b c
模式 a b a a b c a c
j = 0 目标指针加 1
第 3趟 目标 a c a b a a b a a b c a c a a b c
模式 a b a a b c a c
j = 5
j = f (j-1)+1 = 2
第 4趟 目标 a c a b a a b a a b c a c a a b c
模式 (a b) a a b c a c?
int String,,fastFind ( String pat ) const {
//带失效函数的 KMP匹配算法
int posP = 0,posT = 0;
int lengthP = pat.curLen,lengthT = curLen;
while ( posP < lengthP && posT < lengthT )
if ( pat.ch[p osP] == ch[posT] ) {
posP++; posT++; //相等继续比较
}
else if ( posP == 0 ) posT++; //不相等
else posP = pat.f [posP-1]+1;
if ( posP < lengthP ) return -1;
else return posT - lengthP;
}
计算失效函数 f [ j ] 的方法首先确定 f [0] = -1，再利用 f [ j]求 f [ j+1]。
其中,f (1)[ j ] = f [ j ],
f (m)[ j ] = f [f (m -1)[ j ]]
,
,][
][
01
1
1
1][)(
j
k
pp
jf
jf
j
( k)
jfm
否则或的最小正整数可找到令
void String,,fail ( ) {
//计算失效函数
int lengthP = curLen;
f [0] = -1; //直接赋值
for ( int j = 1; j < lengthP; j++ ) { //依次求 f [j]
int i = f [j-1];
while ( *(ch+j) != *(ch+i+1) && i >= 0 )
i = f [i]; //递推
if ( *(ch+j) == *(ch+i+1) ) f [j] = i+1;
else f [j] = -1;
}
}
多维数组
线性表
顺序表
多项式
稀疏矩阵
字符串一维数组
定义相同类型的数据元素的集合。
一维数组的示例
与顺序表的不同在于数组可以按元素的下标直接存储和访问数组元素。
35 27 49 18 60 54 77 83 41 02
0 1 2 3 4 5 6 7 8 9
数组的定义和初始化
#include <iostream.h>
class szcl {
int e;
public:
szcl ( ) { e = 0; }
szcl ( int value ) { e = value; }
int get_value ( ) { return e; }
}
main ( ) {
szcl a1[3] = { 3,5,7 },*elem;
for ( int i = 0; i < 3; i++ )
cout << a1[i].get_value ( ) <<,\n”; //静态
elem = a1;
for ( int i = 0; i < 3; i++ ) {
cout << elem->get_value( ) <<,\n”; //动态
elem++;
}
return 0;
}
一维数组 (Array)类的定义
#include <iostream.h>
#include <stdlib.h>
template <class Type>
class Array {
Type *elements; //数组存放空间
int ArraySize; //当前长度
void getArray ( ); //建立数组空间
public:
Array( int Size=DefaultSize );
Array( const Array<Type>& x );
~Array( ) { delete [ ]elements;}
Array<Type> & operator = //数组复制
( const Array<Type> & A );
Type& operator [ ] ( int i ); //取元素值
int Length ( ) const { return ArraySize; }
//取数组长度
void ReSize ( int sz ); //扩充数组
}
template <class Type>
void Array<Type>,,getArray ( ) {
//私有函数：创建数组存储空间
elements = new Type[ArraySize];
if ( elements == NULL ) {
arraySize = 0;
cerr <<,存储分配错 ！ " << endl;
return;
}
}
一维数组公共操作的实现
template <class Type>
Array<Type>,,Array ( int sz ) {
//构造函数
if ( sz <= 0 ) {
arraySize = 0;
cerr <<,非法数组大小,<< endl;
return;
}
ArraySize = sz;
getArray ( );
}
template <class Type> Array<Type>,:
Array ( Array<Type> & x ) { //复制构造函数
int n = ArraySize = x.ArraySize;
elements = new Type[n];
if ( elements == NULL ) {
arraySize = 0;
cerr <<,存储分配错,<< endl;
return;
}
Type *srcptr = x.elements;
Type *destptr = elements;
while ( n-- ) * destptr++ = * srcptr++;
}
template <class Type>
Type& Array<Type>,,operator [ ] ( int i ) {
//按数组名及下标 i,取数组元素的值
if ( i < 0 || i > ArraySize-1 ) {
cerr <<,数组下标超界,<< endl;
return NULL;
}
return elements[i];
}
使用该函数于赋值语句
Pos = Position[i -1] + Number[i -1]
template <class Type>
void Array<Type>,,Resize ( int sz ) {
if ( sz >= 0 && sz != ArraySize ) {
Type * newarray = new Type[sz];
//创建新数组
if ( newarray == NULL ) {
cerr <<,存储分配错,<< endl;
return;
}
int n = ( sz <= ArraySize )? sz,ArraySize;
//按新的大小确定传送元素个数
Type *srcptr = elements; //源数组指针
Type *destptr = newarray; //目标数组指针
while ( n-- ) * destptr++ = * srcptr++;
//从源数组向目标数组传送
delete [ ] elements;
elements = newarray;
ArraySize = sz;
}
}
多维数组
多维数组是一维数组的推广
多维数组是一种非线性结构。其特点是 每一个数据元素可以有多个直接前驱和多个直接后继 。
数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性结构简单。
二维数组 三维数组行向量 下标 i 页向量 下标 i
列向量 下标 j 行向量 下标 j
列向量 下标 k
数组的连续存储方式
一维数组
35 27 49 18 60 54 77 83 41 02
0 1 2 3 4 5 6 7 8 9
l l l l l l l l l l
LOC(i) = LOC(i-1)+l = a+i*l
LOC(i) = LOC(i-1)+l = a+i*l,i > 0a,i = 0
a+i*l
a
二维数组
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
111101
121202
111101
101000
mnanana
maaa
maaa
maaa
a
行优先存放：
设数组开始存放位置 LOC( 0,0 ) = a,每个元素占用 d 个存储单元
LOC ( j,k ) = a + ( j * m + k ) * d
二维数组
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
111101
121202
111101
101000
mnanana
maaa
maaa
maaa
a
列优先存放：
设数组开始存放位置 LOC( 0,0 ) = a,每个元素占用 d 个存储单元
LOC ( j,k ) = a + ( k * n + j ) * d
三维数组
各维元素个数为 m1,m2,m3
下标为 i1,i2,i3的数组元素的存储地址：
（按页 /行 /列存放）
LOC ( i1,i2,i3 ) = a +
( i1* m2 * m3 + i2* m3 + i3 ) * l
前 i1页总元素个数第 i1页的前 i2行 总元素个数第 i2 行前 i3
列 元素个数
n 维数组
各维元素个数为 m1,m2,m3,…,m n
下标为 i1,i2,i3,…,i n 的数组元素的存储地址：
limia
n
j
n
jk
nkj *
1
1 1
LOC ( i1,i2,…,i n ) = a +
( i1*m2*m3*…*m n + i2*m3*m4*…*m n+
+ ……+ i n-1*mn + in ) * l
线性表 (Linear List)
线性表的定义和特点
定义 n（? 0） 个数据元素的有限序列，记作
（ a1,a2,…,an）
ai 是表中数据元素,n 是表长度。
遍历 逐项访问：
从前向后 从后向前线性表的特点
除第一个元素外，其他每一个元素有一个且仅有一个 直接前驱 。
除最后一个元素外，其他每一个元素有一个且仅有一个 直接后继 。
a1 a2 a3 a4 a5 a6
顺序表 (Sequential List)
顺序表的定义和特点
定义 将线性表中的元素相继存放在一个连续的存储空间中。
可利用 一维数组 描述 存储结构
特点 线性表的顺序存储方式
遍历 顺序 访问
25 34 57 16 48 09
0 1 2 3 4 5
data
顺序表 (SeqList)类的定义
template <class Type> class SeqList {
Type *data; //顺序表存储数组
int MaxSize; //最大允许长度
int last; //当前最后元素下标
public:
SeqList ( int MaxSize = defaultSize );
~SeqList ( ) { delete [ ] data; }
int Length ( ) const { return last+1; }
int Find ( Type& x ) const; //查找
int Locate ( int i ) const; //定位
int Insert ( Type & x,int i ); //插入
int Remove ( Type & x ); //删除
int Next ( Type & x ) ; //后继
int Prior ( Type & x ) ; //前驱
int IsEmpty ( ) { return last ==-1; }
int IsFull ( ) { return last == MaxSize-1; }
Type Get ( int i ) { //提取
return i < 0 || i > last？ NULL,data[i];
}
}
顺序表部分公共操作的实现
template <class Type> //构造函数
SeqList<Type>,,SeqList ( int sz ) {
if ( sz > 0 ) {
MaxSize = sz; last = -1;
data = new Type[MaxSize];
if ( data == NULL ) {
MaxSize = 0; last = -1;
return;
}
}
}
template <class Type>
int SeqList<Type>,,Find ( Type & x ) const {
//搜索函数,在顺序表中从头查找结点值等于
//给定值 x的结点
int i = 0;
while ( i <= last && data[i] != x )
i++;
if ( i > last ) return -1;
else return i;
}
顺序搜索图示
25 34 57 16 48 09
0 1 2 3 4 5
data
搜索 16 i
25 34 57 16 48 09
i
25 34 57 16 48 09
i
25 34 57 16 48 09
i 搜索成功
25 34 57 16 48
0 1 2 3 4
data
搜索 50 i
25 34 57 16 48
i
25 34 57 16 48
i
25 34 57 16 48
i
25 34 57 16 48
i 搜索失败搜索成功 的平均比较次数若搜索概率相等，则搜索不成功 数据比较 n 次
i
n
i
i cp
1
0
=A C N
2
1
2
)(11
)2(1
1
1)(
1
=
1
0
nnn
n
n
n
i
n
n
i
A C N?
22
1)(
1)(
1
0)1(
1
1
)(
1
1
=
0
nnn
n
n
n
in
n
n
i
A M N
表项的插入
25 34 57 16 48 09 63
0 1 2 3 4 5 6 7
data
50插入 x
25 34 57 50 16 48 09 63
0 1 2 3 4 5 6 7
data 50
i
template <class Type>
int SeqList<Type>,,Insert (Type& x,int i ) {
//在表中第 i 个位置插入新元素 x
if ( i < 0 || i > last+1 || last == MaxSize-1 )
return 0; //插入不成功
else {
last++;
for ( int j = last; j > i; j-- )
data[j] = data[j -1];
data[i] = x; return 1; //插入成功
}
}
表项的删除
1
0 2
1
2
1)(11)(1= n
i
nnn
n
in
n
A M N
25 34 57 50 16 48 09 63
0 1 2 3 4 5 6 7
data 16
删除 x
25 34 57 50 48 09 63
0 1 2 3 4 5 6 7
data
template <class Type>
int SeqList<Type>,,Remove ( Type& x ) {
//在表中删除已有元素 x
int i = Find (x); //在表中搜索 x
if ( i >= 0 ) {
last-- ;
for ( int j = i; j <= last; j++ )
data[j] = data[j+1];
return 1; //成功删除
}
return 0; //表中没有 x
}
顺序表的应用,集合的“并”运算
void Union ( SeqList<int> & A,
SeqList<int> & B ) {
int n = A.Length ( );
int m = B.Length ( );
for ( int i = 0; i < m; i++ ) {
int x = B.Get(i); //在 B中取一元素
int k = A.Find (x); //在 A中搜索它
if ( k == -1 ) //若未找到插入它
{ A.Insert (n,x); n++; }
}
}
void Intersection ( SeqList<int> & A,
SeqList<int> & B ) {
int n = A.Length ( );
int m = B.Length ( ); int i = 0;
while ( i < n ) {
int x = A.Get (i); //在 A中取一元素
int k = B.Find (x); //在 B中搜索它
if ( k == -1 ) { A.Remove (i); n--; }
else i++; //未找到在 A中删除它
}
}
顺序表的应用,集合的“交”运算
i
n
i
i
n
nn
xa
xaxaxaaxP
0
2
210
)(?
多项式 (Polynomial)
n阶多项式 Pn(x) 有 n+1 项 。
系数 a0,a1,a2,…,an
指数 0,1,2,…,n。按升幂排列
class Polynomial {
public,
Polynomial ( ); //构造函数
int operator ! ( ); //判是否零多项式
float Coef ( int e);
int LeadExp ( ); //返回最大指数
Polynomial Add (Polynomial poly);
Polynomial Mult (Polynomial poly);
float Eval ( float x); //求值
}
多项式 (Polynomial)的抽象数据类型
#include <iostream.h>
class power {
double x;
int e;
double mul;
public:
power (double val,int exp); //构造函数
double get_power ( ) { return mul; } //取幂值
};
创建 power类，计算 x的幂
power,,power (double val,int exp) {
//按 val值计算乘幂
x = val; e = exp; mul = 1.0;
if ( exp == 0 ) return;
for ( ; exp > 0; exp--) mul = mul * x;
}
main ( ) {
power pwr ( 1.5,2 );
cout << pwr.get_power ( ) <<,\n”;
}
多项式的存储表示第一种,private,
(静态数 int degree;
组表示 ) float coef [maxDegree+1];
Pn(x)可以表示为,
pl.degree = n
pl.coef[i] = ai,0? i? n
a0 a1 a2 …… an ………
0 1 2 degree maxDegree-1
coef
n
第二种,private:
(动态数 int degree;
组表示 ) float * coef;
Polynomial,,Polynomial (int sz) {
degree = sz;
coef = new float [degree + 1];
}
以上两种存储表示适用于指数连续排列的多项式。但对于指数不全的多项式如 P101(x) = 3 + 5x50 - 14x101,不经济。
第三种,
class Polynomial;
class term { //多项式的项定义
friend Polynomial;
private,
float coef; //系数
int exp; //指数
};
a0 a1 a2 …… ai …… am
e0 e1 e2 …… ei …… em
coef
exp
0 1 2 i m
class Polynomial { //多项式定义
public:
……
private:
static term termArray[MaxTerms]; //项数组
static int free; //当前空闲位置指针
// term Polynomial::termArray[MaxTerms];
// int Polynomial::free = 0;
int start,finish; //多项式始末位置
}
A(x) = 2.0x1000+1.8
B(x) = 1.2 + 51.3x50 + 3.7x101
两个多项式存放在 termArray中
A.start A.finish B.start B.finish free
coef
exp
1.8 2.0 1.2 51.3 3.7 ……
0 1000 0 50 101 ……
maxTerms
两个多项式的相加
结果多项式另存
扫描两个相加多项式，若都未检测完：
若当前被检测项 指数相等,系数相加。若未变成 0，则将结果加到结果多项式。
若当前被检测项 指数不等,将指数小者加到结果多项式。
若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。
Polynomial Polynomial,:
operator + ( Polynomial B ) {
Polynomial C;
int a = start; int b = B.start; C.start = free;
float c;
while ( a <= finish && b <= B.finish )
Switch ( compare ( termArray[a].exp,
termArray[b].exp) ) { //比较对应项指数
case?=?,//指数相等
c = termArray[a].coef + //系数相加
termArray[b].coef;
if ( c ) NewTerm ( c,termArray[a].exp );
a++; b++; break;
case?>?,//b指数小,建立新项
NewTerm ( termArray[b].coef,
termArray[b].exp );
b++; break;
case '<',//a指数小,建立新项
NewTerm ( termArray[a].coef,
termArray[a].exp );
a++;
}
for ( ; a <= finish; a++ ) //a未检测完时
NewTerm ( termArray[a].coef,
termArray[a].exp );
for ( ; b <= B.finish; b++ ) //b未检测完时
NewTerm ( termArray[b].coef,
termArray[b].exp );
C.finish = free-1;
return C;
}
在多项式中加入新的项
void Polynomial,,NewTerm ( float c,int e ) {
//把一个新的项加到多项式 C(x)中
if ( free >= maxTerms ) {
cout << "Too many terms in polynomials”
<< endl;
return;
}
termArray[free].coef = c;
termArray[free].exp = e;
free++;
}
00002800
00000091
03900000
0006000
017000110
150022000
A
76
稀疏矩阵 (Sparse Matrix)
非零元素个数 远远少于矩阵元素个数稀疏矩阵的定义
设矩阵 Am?n 中有 t 个非零元素，若 t 远远小于矩阵元素的总数 m?n，则称矩阵
A 为稀疏矩阵。
为节省存储空间，应只存储非零元素。
非零元素的分布一般没有规律，应在存储非零元素时，同时存储该非零元素的行下标 row、列下标 col、值 value。
每一个非零元素由一个三元组唯一确定：
( 行号 row,列号 col,值 value )
稀疏矩阵的抽象数据类型
template<class Type> class SparseMatrix;
template<class Type> class Trituple { //三元组
friend class SparseMatrix <Type>
private:
int row,col; //非零元素行号 /列号
Type value; //非零元素的值
}
template <class Type> class SparseMatrix {
//稀疏矩阵类定义
int Rows,Cols,Terms; //行 /列 /非零元素数
Trituple<Type> smArray[MaxTerms];
public,//三元组表
SparseMatrix (int MaxRow,int Maxcol);
SparseMatrix<Type>& Transpose
(SparseMatrix<Type>&); //转置
SparseMatrix<Type>&Add (SparseMatrix
<Type> a,SparseMatrix<Type> b); //相加
SparseMatrix<Type>& Multiply(SparseMatrix
<Type> a,SparseMatrix<Type> b); //相乘
}
稀疏矩阵的转置
一个 m?n 的矩阵 A，它的转置矩阵 B 是一个 n?m 的矩阵，且 A[i][j] = B[j][i]。 即矩阵 A 的行成为矩阵 B 的列，矩阵 A 的列成为矩阵 B 的行。
在稀疏矩阵的三元组表中，非零矩阵元素按行存放。当行号相同时，按列号递增的顺序存放。
稀疏矩阵的转置运算要转化为对应三元组表的转置。
00002800
00000091
03900000
0006000
017000110
150022000
稀疏矩阵行行
(( rr oo w ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
[0] 00 33 22 22
[1] 00 66 11 55
[2] 11 11 11 11
[3] 11 55 11 77
[4] 22 33 -- 66
[5] 33 55 33 99
[6] 44 00 99 11
[7] 55 22 22 88
0000015
00390170
000000
0006022
2800000
0000110
0910000
转置矩阵行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
[0] 00 44 99 11
[1] 11 11 11 11
[2] 22 55 22 88
[3] 33 00 22 22
[4] 33 22 -- 66
[5] 55 11 11 77
[6] 55 33 33 99
[7] 66 00 11 66
用三元组表表示的稀疏矩阵及其转置行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
[0] 00 33 22 22 [0] 00 44 99 11
[1] 00 66 11 55 [1] 11 11 11 11
[2] 11 11 11 11 [2] 22 55 22 88
[3] 11 55 11 77 [3] 33 00 22 22
[4] 22 33 -- 66 [4] 33 22 -- 66
[5] 33 55 33 99 [5] 55 11 11 77
[6] 44 00 99 11 [6] 55 33 33 99
[7] 55 22 22 88 [7] 66 00 11 66
稀疏矩阵转置算法思想
设矩阵列数为 Cols，对矩阵三元组表扫描 Cols 次。第 k 次检测列号为 k
的项。
第 k 次扫描找寻所有列号为 k 的项，
将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。
稀疏矩阵的转置
template <class Type> SparseMatrix<Type>&
SparseMatrix<Type>,,Transpose
(SparseMatrix<Type>& a) {
SparseMatrix<Type> b (a.Cols,a.Rows);
b.Rows = a.Cols; b.Cols = a.Rows;
b.Terms = a.Terms;
//转置矩阵的列数,行数和非零元素个数
if ( a.Terms > 0 ) {
int CurrentB = 0;
//转置三元组表存放指针
for ( int k = 0; k < a.Cols; k++ )
//对所有列号处理一遍
for ( int i = 0; i < a.Terms; i++ )
if ( a.smArray[i].col == k ) {
b.smArray[CurrentB].row = k;
b.smArray[CurrentB].col =
a.smArray[i].row;
b.smArray[CurrentB].value=
a.smArray[i].value;
CurrentB++;
}
}
return b;
}
快速转置算法
设矩阵三元组表总共有 t 项，上述算法的时间代价为 O ( n* t )。
若矩阵有 200 行,200 列,10,000 个非零元素，总共有 2,000,000 次处理。
为加速转置速度，建立辅助数组 rowSize
和 rowStart，记录 矩阵转置后各行非零元素个数 和各 行元素在转置三元组表中开始存放位置 。
扫描矩阵三元组表，根据某项列号，确定它转置后的行号,查 rowStart 表,按查到的位置直接将该项存入转置三元组表中
[0] [1] [2] [3] [4] [5] [6] 语 义
row Siz e 1 1 1 2 0 2 1 矩阵 A 各列非零元素个数
row Start 0 1 2 3 5 5 7 矩阵 B 各行开始存放位置
for ( int i = 0; i < a.Cols; i++ ) rowSize[i] = 0;
for ( i = 0; i < a.Terms; i++ )
rowSize[a.smArray[i].col]++;
rowStart[0] = 0;
for ( i = 1; i < Cols; i++ )
rowStart[i] = rowStart[i-1]+rowSize[i-1];
稀疏矩阵的快速转置
template <class Type> SparseMatrix<Type>&
SparseMatrix<Type>,,FastTranspos
(SparseMatrix<Type>& a) {
int *rowSize = new int[a.Cols];
int *rowStart = new int[a.Cols];
SparseMatrix<Type> b ( a.Cols,a.Rows );
b.Rows = a.Cols; b.Cols = a.Rows;
b.Terms = a.Terms;
if ( a.Terms > 0 ) {
for (int i = 0; i < Cols; i++) rowSize[i] = 0;
for ( i = 0; i < Terms; i++ )
rowSize[smArray[i].col]++;
rowStart[0] = 0;
for ( i = 1; i < a.Cols; i++ )
rowStart[i] = rowStart[i-1]+rowSize[i-1];
for ( i = 0; i < a.Terms; i++ ) {
int j = rowStart[a.smArray[i].col];
b.smArray[j].row = a.smArray[i].col;
b.smArray[j].col = a.smArray[i].row;
b.smArray[j].value = a.smArray[i].value;
rowStart[a.smArray[i].col]++;
}
}
delete [ ] rowSize; delete [ ] rowStart;
return b;
}
字符串 (String)
字符串是 n (? 0 ) 个字符的有限序列，
记作 S,,c1c2c3…c n”
其中,S 是串名字
,c1c2c3…c n”是串值
ci 是串中字符
n 是串的长度。
例如,S =,Tsinghua University”
const int maxLen = 128;
class String {
int curLen; //串的当前长度
char *ch; //串的存储数组
public:
String ( const String& ob );
String ( const char * init );
String ( );
~String ( ) { delete [ ] ch; }
字符串抽象数据类型和类定义
int Length ( ) const { return curLen; }
//求当前串 *this的实际长度
String &operator ( ) ( int pos,int len );
//取 *this从 pos开始 len个字符组成的子串
int operator == ( const String &ob )
{ return strcmp (ch,ob.ch) == 0; }
//判当前串 *this与对象串 ob是否相等
int operator != ( const String &ob )
const { return strcmp (ch,ob.ch) != 0; }
//判当前串 *this与对象串 ob是否不等
int operator ! ( )
const { return curLen == 0; }
//判当前串 *this是否空串
String &operator = (String &ob);
//将串 ob赋给当前串 *this
String &operator += (String &ob);
//将串 ob连接到当前串 *this之后
char &operator [ ] ( int i );
//取当前串 *this的第 i 个字符
int Find ( String& pat ) const;
}
String,,String ( const String& ob ) {
//复制构造函数：从已有串 ob复制
ch = new char[maxLen+1]; //创建串数组
if ( ch == NULL ) {
cerr <<,存储分配错 ! \n”;
exit(1);
}
curLen = ob.curLen; //复制串长度
strcpy ( ch,ob.ch ); //复制串值
}
字符串部分操作的实现
String,,String ( const char *init ) {
//复制构造函数,从已有字符数组 *init复制
ch = new char[maxLen+1]; //创建串数组
if ( ch == NULL ){
cerr <<,存储分配错 ! \n”;
exit(1);
}
curLen = strlen ( init ); //复制串长度
strcpy ( ch,init ); //复制串值
}
String,,String ( ) {
//构造函数：创建一个空串
ch = new char[maxLen+1]; //创建串数组
if ( ch == NULL ) {
cerr <<,存储分配错 !\n”;
exit(1);
}
curLen = 0;
ch[0] =?\0?;
}
提取子串的算法示例
pos+len -1 pos+len -1
curLen-1? curLen
i n f i n i t y i n f i n i t y
pos = 2,len = 3 pos = 5,len = 4
f i n i t y
超出
String& String,,operator ( ) (int pos,int len) {
//从串中第 pos 个位置起连续提取 len 个字符
//形成子串返回
String * temp = new String; //动态分配
if (pos<0 || pos+len-1 >= maxLen || len<0) {
temp->curLen = 0; //返回空串
temp->ch[0] = '\0';
}
else { //提取子串
if ( pos+len -1 >= curLen )
len = curLen - pos;
temp->curLen = len; //子串长度
for ( int i = 0,j = pos; i < len; i++,j++ )
temp->ch[i] = ch[j]; //传送串数组
temp->ch[len] =?\0?; //子串结束
}
return * temp;
}
例：串 st =,university”,pos = 3,len = 4
使用示例 subSt = st (3,4)
提取子串 subSt =,vers”
String& String,,operator = ( String& ob ) {
//串赋值：从已有串 ob复制
if ( &ob != this ) {
delete [ ] ch;
ch = new char [maxLen+1]; //重新分配
if ( ch == NULL )
{ cerr <<,内存不足 !\n”; exit (1);}
curLen = ob.curLen; //串复制
strcpy ( ch,ob.ch );
}
else cout <<,字符串自身赋值出错 ! \n”;
return *this;
}
char& String,,operator [ ] ( int i ) {
//按串名提取串中第 i 个字符
if ( i < 0 && i >= curLen )
{ cout <<,串下标超界 !\n,; exit (1); }
return ch[i];
}
例：串 st =,university”,
使用示例 newSt = st； newChar = st[1];
数组赋值 newSt =,university”
提取字符 newChar =?n?
String& String,,operator += ( String& ob ) {
//串连接
char * temp = ch; //暂存原串数组
curLen += ob.curLen; //串长度累加
ch = new char [maxLen+1];
if ( ch == NULL )
{ cerr <<,存储分配错 !\n,; exit (1); }
strcpy ( ch,temp ); //拷贝原串数组
strcat ( ch,ob.ch ); //连接 ob串数组
delete [ ] temp; return *this;
}
例：串 st1 =,beijing,,
st2 =,university”,
使用示例 st1 += st2;
连接结果 st1 =,beijing university”
st2 =,university”
串的模式匹配
定义 在串中寻找子串（第一个字符）在串中的位置
词汇 在模式匹配中，子串称为 模式,串称为 目标 。
示例 目标 T,,Beijing”
模式 P,,jin”
匹配结果 = 3
第 1趟 T a b b a b a 穷举的模式
P a b a 匹配过程第 2趟 T a b b a b a
P a b a
第 3趟 T a b b a b a
P a b a
第 4趟 T a b b a b a
P a b a
int String,,Find ( String &pat ) const {
//穷举的模式匹配
char * p = pat.ch,* s = ch; int i = 0;
if ( *p && *s ) //当两串未检测完
while ( i <= curLen - pat.curLen )
if ( *p++ == *s++ ) //比较串字符
if ( !*p ) return i; //相等
else { i++; s = ch + i; p = pat.ch; }
//对应字符不相等，对齐目标的
//下一位置，继续比较
return -1;
}
目标 T t0 t1 t2 …… tm-1 … tn-1
模式 pat p0 p1 p2 …… pm-1
目标 T t0 t1 t2 …… tm-1 tm … tn-1
模式 pat p0 p1 …… pm-2 pm-1
目标 T t0 t1 …… ti ti+1…… ti+m-2 ti+m-1… tn-1
‖ ‖ ‖ ‖
模式 pat p0 p1 …… pm-2 pm-1
改进的模式匹配
穷举的模式匹配算法时间代价：
最坏情况比较 n-m+1趟，每 趟比较 m次，总比较次数达 (n-m+1)*m
原因在于 每趟重新比较时，目标串的检测指针要回退。改进的模式匹配算法可使目标串的检测指针每趟不回退。
改进的模式匹配 (KMP)算法的时间代价：
若每趟第一个不匹配，比较 n-m+1趟,总比较次数最坏达 (n-m)+m = n
若每趟第 m个不匹配，总比较次数最坏亦达到 n
T t0 t1 … ts-1 ts ts+1 ts+2 … ts+j-1 ts+j ts+j+1 … tn-1
‖ ‖ ‖ ‖ ‖?
P p0 p1 p2 … pj-1 pj pj+1
则有 ts ts+1 ts+2 … ts+j = p0 p1 p2 … pj (1)
为使模式 P 与目标 T 匹配，必须满足
p0 p1 p2 … pj-1 … pm-1 = ts+1 ts+2 ts+3 … ts+j … ts+m
如果 p0 p1 … pj-1? p1 p2 … pj (2)
则立刻可以断定
p0 p1 … pj-1? ts+1 ts+2 … ts+j
下一趟必不匹配同样，若 p0 p1 … pj-2? p2 p3 … pj
则再下一趟也不匹配，因为有
p0 p1 … pj-2? ts+2 ts+3 … ts+j
直到对于某一个,k”值，使得
p0 p1 … pk+1? pj-k-1 pj-k… pj
且 p0 p1 … pk = pj-k pj-k+1 … pj
则 p0 p1 … pk = ts+j-k ts+j-k+1 … ts+j
‖ ‖ ‖
pj-k pj-k+1 … pj
k 的确定方法当比较到模式第 j 个字符失配时,k 的 值 与模式的前 j 个字符有关，与目标无关。
利用失效函数 f (j)可描述。
利用失效函数 f (j) 的匹配处理如果 j = 0，则目标指针加 1，模式指针回到 p0。
如果 j > 0，则目标指针不变，模式指针回到 pf ( j-1)+1。
若设 模式 P = p0 p1… pm-2 pm-1
1,-
,
,<0
,
=)(
1
10
.其它情况的最大整数且使得当
jkjkj
k
ppp
pppjk
k
jf?
j 0 1 2 3 4 5 6 7
PP a b a a b c a c
ff (( jj )) -- 11 -- 11 00 00 11 -- 11 00 -- 11示例,确定失效函数 f (j)
运用 KMP算法的匹配过程第 1趟 目标 a c a b a a b a a b c a c a a b c
模式 a b a a b c a c
j = 1? j = f (j-1)+1 = 0
第 2趟 目标 a c a b a a b a a b c a c a a b c
模式 a b a a b c a c
j = 0 目标指针加 1
第 3趟 目标 a c a b a a b a a b c a c a a b c
模式 a b a a b c a c
j = 5
j = f (j-1)+1 = 2
第 4趟 目标 a c a b a a b a a b c a c a a b c
模式 (a b) a a b c a c?
int String,,fastFind ( String pat ) const {
//带失效函数的 KMP匹配算法
int posP = 0,posT = 0;
int lengthP = pat.curLen,lengthT = curLen;
while ( posP < lengthP && posT < lengthT )
if ( pat.ch[p osP] == ch[posT] ) {
posP++; posT++; //相等继续比较
}
else if ( posP == 0 ) posT++; //不相等
else posP = pat.f [posP-1]+1;
if ( posP < lengthP ) return -1;
else return posT - lengthP;
}
计算失效函数 f [ j ] 的方法首先确定 f [0] = -1，再利用 f [ j]求 f [ j+1]。
其中,f (1)[ j ] = f [ j ],
f (m)[ j ] = f [f (m -1)[ j ]]
,
,][
][
01
1
1
1][)(
j
k
pp
jf
jf
j
( k)
jfm
否则或的最小正整数可找到令
void String,,fail ( ) {
//计算失效函数
int lengthP = curLen;
f [0] = -1; //直接赋值
for ( int j = 1; j < lengthP; j++ ) { //依次求 f [j]
int i = f [j-1];
while ( *(ch+j) != *(ch+i+1) && i >= 0 )
i = f [i]; //递推
if ( *(ch+j) == *(ch+i+1) ) f [j] = i+1;
else f [j] = -1;
}
}
