第二章 数组 作为抽象数据类型的数组 顺序表 多项式抽象数据类型 稀疏矩阵 字符串 小结

作为抽象数据类型的数组 一维数组 一维数组的示例

一维数组的特点 连续存储的线性聚集（别名 向量） 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。

数组的定义和初始化 #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 ); //取元素值 Type* operator ( ) const //指针转换 { return elements; } int Length ( ) const //取数组长度 { return ArraySize; } void ReSize ( int sz ); //扩充数组 }

一维数组公共操作的实现 template <class Type> void Array<Type>::getArray ( ) { //私有函数：创建数组存储空间 elements = new Type[ArraySize]; if ( elements == 0 ) { arraySize = 0; cerr << "Memory Allocation Error" << 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 ( const Array<Type> & x ) { //复制构造函数 int n = ArraySize = x.ArraySize; elements = new Type[n]; if ( elements == 0 ) { arraySize = 0; cerr << “存储分配错” << endl; return; } Type *srcptr = x.elements; Type *destptr = elements; while ( n-- ) * destptr++ = * srcptr++;

Pos = Position[i -1] + Number[i -1] 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 == 0 ) { 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 二维数组 三维数组 行向量 下标 i 页向量 下标 i 列向量 下标 j 行向量 下标 j 列向量 下标 k

数组的连续存储方式 一维数组 LOC ( i ) = LOC ( i -1 ) + l =α+ i*l

二维数组 行优先 LOC ( j, k ) = = a + ( j * m + k ) * l

n维数组 + ……+ in-1*mn + in ) * l 各维元素个数为 m1, m2, m3, …, mn 下标为 i1, i2, i3, …, in 的数组元素的存储地址： LOC ( i1, i2, …, in ) = a + ( i1*m2*m3*…*mn + i2*m3*m4*…*mn+ + ……+ in-1*mn + in ) * l

顺序表 (Sequential List) 定义 n（  0）个表项的有限序列 顺序表的定义和特点 （a1, a2, …, an） ai是表项，n是表长度。 特点 顺序存取 遍历 逐项访问 从前向后 从后向前 从两端向中间

顺序表(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 IsIn ( Type & x ); 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; }

顺序搜索图示 x = 48 x = 50

搜索成功 若搜索概率相等，则 搜索不成功 数据比较 n 次

表项的插入

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; //插入成功 }

表项的删除

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

template <class Type> 顺序表的应用：集合的“并”运算 template <class Type> void Union ( SeqList<Type> & LA, SeqList<Type> & LB ) { int n = LA.Length ( ); int m = LB.Length ( ); for ( int i = 1; i <= m; i++ ) { Type x = LB.Get(i); //在LB中取一元素 int k = LA.Find (x); //在LA中搜索它 if ( k == -1 ) //若未找到插入它 { LA.Insert (n+1, x); n++; } }

template <class Type> 顺序表的应用：集合的“交”运算 template <class Type> void Intersection ( SeqList<Type> & LA, SeqList<Type> & LB ) { int n = LA.Length ( ); int m = LB.Length ( ); int i = 0; while ( i < n ) { Type x = LA.Get (i); //在LA中取一元素 int k = LB.Find (x); //在LB中搜索它 if ( k == -1 ) { LA.Remove (i); n--; } else i++; //未找到在LA中删除它 }

多项式 (Polynomial) n阶多项式 Pn(x) 有 n+1 项。 系数 a0, a1, a2, …, an

多项式(Polynomial)的抽象数据类型 class Polynomial { public: Polynomial ( ); //构造函数 int operator ! ( ); //判是否零多项式 float Coef ( int e); int LeadExp ( ); //返回最大指数 Polynomial Add (Polynomial poly); Polynomial Mult (Polynomial poly); float Eval ( float x); //求值 }

#include <iostream.h> 创建power类，计算x的幂 #include <iostream.h> class power { double x; int e; double mul; public: power (double val, int exp); //构造函数 double get_power ( ) { return mul; } //取幂值 };

power::power (double val, int exp) { 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

Polynomial::Polynomial (int sz) { 第二种：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; //指数 };

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中

两个多项式的相加 结果多项式另存 扫描两个相加多项式，若都未检测完： 若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。 若当前被检测项指数相等，系数相加。若未变成 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未检测完时

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++;

稀疏矩阵 (Sparse Matrix) 行数m = 6, 列数n = 7, 非零元素个数t = 6

稀疏矩阵(SparseMatrix)的抽象数据类型 template <class Type> class SparseMatrix { int Rows, Cols, Terms; //行/列/非零元素数 Trituple<Type> smArray[MaxTerms]; public: //三元组表 SparseMatrix ( int MaxRow, int Maxcol ); SparseMatrix<Type> Transpose ( ); //转置 SparseMatrix<Type> //相加 Add ( SparseMatrix<Type> b ); SparseMatrix<Type> //相乘 Multiply ( SparseMatrix<Type> b ); }

template<class Type> class SparseMatrix<Type>; 三元组 (Trituple) 类的定义 template<class Type> class SparseMatrix<Type>; template<class Type> class Trituple { friend class SparseMatrix <Type> private: int row, col; //非零元素所在行号/列号 Type value; //非零元素的值 }

稀疏矩阵 转置矩阵

用三元组表表示的稀疏矩阵及其转置

稀疏矩阵转置算法思想 设矩阵列数为 Cols，对矩阵三元组表扫描Cols 次。第 k 次检测列号为 k 的项。 设矩阵三元组表总共有 Terms 项，其时间代价为 O ( Cols* Terms )。 若矩阵有 200 行，200 列，10,000 个非零元素，总共有 2,000,000 次处理。

template <class Type> 稀疏矩阵的转置 template <class Type> SparseMatrix<Type> SparseMatrix<Type>:: Transpose ( ) { SparseMatrix<Type> b ( Cols, Rows ); b.Rows = Cols; b.Cols = Rows; b.Terms = Terms; //转置矩阵的列数,行数和非零元素个数 if ( Terms > 0 ) { int CurrentB = 0; //转置三元组表存放指针

for ( int k = 0; k < Cols; k++ ) for ( int i = 0; i < Terms; i++ ) if ( smArray[i].col == k ) { b.smArray[CurrentB].row = k; b.smArray[CurrentB].col = smArray[i].row; b.smArray[CurrentB].value= smArray[i].value; CurrentB++; } return b;

快速转置算法 建立辅助数组 rowSize 和 rowStart，记录矩阵转置后各行非零元素个数和各行元素在转置三元组表中开始存放位置。 转置时间代价为 O(max(Terms, Cols))。若矩阵有 200 列，10000 个非零元素，总共需要10000 次处理。

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 < Cols; i++ ) rowStart[i] = rowStart[i-1]+rowSize[i-1];

稀疏矩阵的快速转置 template <class Type> SparseMatrix<Type> SparseMatrix<Type>::FastTranspos ( ) { int *rowSize = new int[Cols]; int *rowStart = new int[Cols]; SparseMatrix<Type> b ( Cols, Rows ); b.Rows = Cols; b.Cols = Rows; b.Terms = Terms; if ( 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 < Cols; i++ ) rowStart[i] = rowStart[i-1]+rowSize[i-1]; for ( i = 0; i < Terms; i++ ) { int j = rowStart[smArray[i].col]; b.smArray[j].row = smArray[i].col; b.smArray[j].col = smArray[i].row; b.smArray[j].value = smArray[i].value; rowStart[smArray[i].col]++; } delete [ ] rowSize; delete [ ] rowStart; return b;

字符串 (String) 字符串是 n (  0 ) 个字符的有限序列， 记作 S : “c1c2c3…cn” 其中，S 是串名字 ci 是串中字符 n 是串的长度。

字符串抽象数据类型和类定义 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; }

String &operator ( ) ( int pos, int len ); int operator == ( const String &ob ) const { return strcmp (ch, ob.ch) == 0; } int operator != ( const String &ob ) const { return strcmp (ch, ob.ch) != 0; } int operator ! ( ) const { return curLen == 0; } String &operator = ( const String &ob ); String &operator += ( const String &ob ); char &operator [ ] ( int i ); int Find ( String& pat ) const; }

字符串部分操作的实现 //复制构造函数：从已有串ob复制 ch = new char[maxLen+1]; if ( !ch ) { String::String ( const String &ob ) { //复制构造函数：从已有串ob复制 ch = new char[maxLen+1]; if ( !ch ) { cerr << “存储分配错 \n”; exit(1); } curLen = ob.curLen; strcpy ( ch, ob.ch );

String::String ( const char *init ) { ch = new char[maxLen+1]; if ( !ch ){ cerr << “存储分配错 \n”; exit(1); } curLen = strlen ( init ); strcpy ( ch, init );

String::String ( ) { //构造函数：创建一个空串 ch = new char[maxLen+1]; if ( !ch ) { cerr << “存储分配错\n”; exit(1); } curLen = 0; ch[0] = ‘\0’;

提取子串的算法示例 pos+len -1 pos+len -1  curLen-1  curLen

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; //子串长度

例：串 st = “university”, pos = 3, len = 4 使用示例 subSt = st (3, 4) 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 = ( const String &ob ) { if ( &ob != this ) { delete [ ] ch; ch = new char [maxLen+1]; //重新分配 if ( ! ch ) { cerr << “内存不足!\n ”; exit (1); } curLen = ob.curLen; //串复制 strcpy ( ch, ob.ch ); else cout << “字符串自身赋值出错! \n”; return *this;

使用示例 newSt = st；newChar = st[1]; 数组赋值 newSt = “university” 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 += ( const String &ob ) { //串连接 char * temp =ch; //暂存原串数组 curLen += ob.curLen; //串长度累加 ch = new char [maxLen+1]; if ( ! ch ) { 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; }

改进的模式匹配     模式 pat p0 p1 p2 …… pm-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 下一趟必不匹配

‖ ‖ ‖ pj-k pj-k+1 … pj 同样，若 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 示例 ：确定失效函数 f (j)

第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 运用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 ]]

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; }

小结：需要复习的知识点 作为抽象数据类型的数组 数组的定义和初始化； 作为抽象数据类型的数组； 对称矩阵按上三角或下三角压缩存储时的地址转换公式 顺序表 顺序表的定义和特点

在顺序表中插入及删除时计算平均移动元素个数 使用顺序表的事例 稀疏矩阵 顺序表的类定义 顺序表的查找、插入和删除算法 在顺序表中插入及删除时计算平均移动元素个数 使用顺序表的事例 稀疏矩阵 稀疏矩阵的三元组表表示； 稀疏矩阵的转置算法；

字符串 字符串的抽象数据类型； 字符串常用操作的实现； 字符串模式匹配方法(不要求算法)