? 作为抽象数据类型的数组
? 顺序表
? 稀疏矩阵
? 字符串
作为抽象数据类型的数组
? 一维数组
? 一维数组的示例
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 element[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 ( j,k ) =
= a + ( j * m + k ) * l
? 三维数组
?各维元素个数为 m1,m2,m3
?下标为 i1,i2,i3的数组元素的存储地址：
（按页 /行 /列存放）
LOC ( i1,i2,i3 ) = a +
( i1* m2 * m3 + i2* m3 + i3 ) * l
前 i1页总
元素个数
第 i1页的
前 i2行 总
元素个数
? 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 是表长度。
? 遍历 逐项访问：
从前向后 从后向前
线性表的特点
? 除第一个元素外，其他每一个元素
有一个且仅有一个 直接前驱 。
? 除最后一个元素外，其他每一个元
素有一个且仅有一个 直接后继 。
顺序表 (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 = 1; 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中删除它 }
}
顺序表的应用,集合的“交”运算
00002800
00000091
03900000
0006000
017000110
150022000
A
76
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
稀疏矩阵 (Sparse Matrix)
非零元素个数 远远少于矩阵元素个数
稀疏矩阵的抽象数据类型
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); //相乘
}
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;
}
快速转置算法
? 建立辅助数组 rowSize 和 rowStart，
记录矩阵转置后 各行非零元素个数 和
各行元素在转置三元组表中开始存放
位置 。
? 扫描矩阵三元组表，根据某项的列号，
确定它转置后的行号，查 rowStart 表，
按查到的位置直接将该项存入转置三
元组表中。
[0] [1] [2] [3] [4] [5] [6]
row Siz e 1 1 1 2 0 2 1
矩阵 A 各列非零元素个数
row Sta rt 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];
[0] [1] [2] [3] [4] [5] [6]
r ow Siz e 1 1 1 2 0 2 1
r ow Star t 0 1 2 3 5 5 7
稀疏矩阵的快速转置
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 {
//穷举的模式匹配
for ( int i = 0; i <= curLen-pat.curLen; i++ )
{ //逐趟比较
int j = 0; //从 ch[i]与模式 pat.ch比较
while ( j < pat.curLen )
if ( ch[i+j] == pat.ch[j] ) j++;
else break;
if ( j == pat.curLen ) return i;
//pat扫描完,匹配成功
}
? 顺序表
? 稀疏矩阵
? 字符串
作为抽象数据类型的数组
? 一维数组
? 一维数组的示例
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 element[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 ( j,k ) =
= a + ( j * m + k ) * l
? 三维数组
?各维元素个数为 m1,m2,m3
?下标为 i1,i2,i3的数组元素的存储地址：
（按页 /行 /列存放）
LOC ( i1,i2,i3 ) = a +
( i1* m2 * m3 + i2* m3 + i3 ) * l
前 i1页总
元素个数
第 i1页的
前 i2行 总
元素个数
? 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 是表长度。
? 遍历 逐项访问：
从前向后 从后向前
线性表的特点
? 除第一个元素外，其他每一个元素
有一个且仅有一个 直接前驱 。
? 除最后一个元素外，其他每一个元
素有一个且仅有一个 直接后继 。
顺序表 (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 = 1; 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中删除它 }
}
顺序表的应用,集合的“交”运算
00002800
00000091
03900000
0006000
017000110
150022000
A
76
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
稀疏矩阵 (Sparse Matrix)
非零元素个数 远远少于矩阵元素个数
稀疏矩阵的抽象数据类型
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); //相乘
}
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;
}
快速转置算法
? 建立辅助数组 rowSize 和 rowStart，
记录矩阵转置后 各行非零元素个数 和
各行元素在转置三元组表中开始存放
位置 。
? 扫描矩阵三元组表，根据某项的列号，
确定它转置后的行号，查 rowStart 表，
按查到的位置直接将该项存入转置三
元组表中。
[0] [1] [2] [3] [4] [5] [6]
row Siz e 1 1 1 2 0 2 1
矩阵 A 各列非零元素个数
row Sta rt 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];
[0] [1] [2] [3] [4] [5] [6]
r ow Siz e 1 1 1 2 0 2 1
r ow Star t 0 1 2 3 5 5 7
稀疏矩阵的快速转置
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 {
//穷举的模式匹配
for ( int i = 0; i <= curLen-pat.curLen; i++ )
{ //逐趟比较
int j = 0; //从 ch[i]与模式 pat.ch比较
while ( j < pat.curLen )
if ( ch[i+j] == pat.ch[j] ) j++;
else break;
if ( j == pat.curLen ) return i;
//pat扫描完,匹配成功
}
