1、 第2章 数组1.数组及其抽象数据类型 1)一维数组 2)一维数组的抽象数据类型的类声明n 3)二维数组（矩阵）n 4)特殊矩阵2.顺序表(sequential List)1)顺序表定义和特点 2)顺序表的类定义n 3)顺序表的查找 插入 删除 4)使用顺序表的例子(用抽象数据类型）3.多项式抽象数据类型 1)如何表达多项式：系数，阶数 2)多项式相加 4.稀疏矩阵 5.字符串（String）1)字符串（简称串）的定义以及一些术语 2)串的基本操作 3)串的类定义以及串操作的实现 4)字符串的模式匹配（pattern matching）朴素的匹配算法n 改进的模式匹配算法：KMP第2章 数组数
2、组：具有相同数据类型的数据元素的集合。一般存储于一个连续存储空间中。通过数组元素的下标来存取该元素。1.数组及其抽象数据类型 1)一维数组：具有相同数据类型的n（n=0）个元素的有限序列。例如：0 1 2 3 4 5 6 7 8 9 a：i 02418377546018492735下标i为数组元素到数组开始的偏移量 Loc(ai)=loc(a0)+i*l 2)一维数组的抽象数据类型的类声明 对数组的操作主要有：对数组元素的存与取。3)二维数组（矩阵）由n个行向量和m个列向量所组成的向量 a00 a01 a02 a0,m-1 Anm=a10 a11 a12 a 1,m-1 an-1,0an-1,
3、1an-1,2an-1,m-1a00a01a0m-1a10a11a1m-1对二维数组的顺序存储：1）按行优先顺序存放 a00,a01,a02,a0m-1,a10 如ALGOL,PASCAL,C+,BASIC,Ada等都是按行优先顺序存放的。2)按列优先顺序存放 a00,a10,a20,a n-10 ,a01 如Fortran语言 如果按行优先存放，其下标元素的映射公式为：Loc(i,j)=Loc(0,0)+i*m+j*L 如果按列优先存放，其下标元素的映射公式为：Loc(i,j)=Loc(0,0)+j*n+i*L 同理对三维数组am1m2m3 其下标元素aijk Loc(i,j,k)=Loc(
4、0,0,0)+i*m2*m3+j*m3+k 0120m2-1m1-1 4)特殊矩阵(1)下三角矩阵（对于对称矩阵的压缩存储）a11a21 a22a31 a32 a33an1 an2 ann 按行序存放a11a21a22 Loc(i,j)=Loc(1,1)+(1+2+3+i-1)+j-1*L =Loc(1,1)+(i*(i-1)/2+j-1)*L 上三角矩阵 a11 a12 a1n a11 a22 a2n 按行序存放 a12 a33 a1n a22 .ann .Loc(i,j)=Loc(1,1)+(n+(n-1)+(n-i+2)+j-i*L =loc(1,1)+(n-k+1)+j-i*L K=1
5、i-1(2)三对角线矩阵 a11a12 a21a22a23 a32a33a34 按行序存放 an-1,n-2an-1,n-1an-1,n an,n-1 an,n Loc(i,j)=Loc(1,1)+(i-1)*3-1+(j-i+1)*La11a12a21a22a232.顺序表(sequential List)1)顺序表定义和特点 定义：是一个顺序存储的n（n=0）个表项的序列。n=0叫做空表。每个表项是单个对象，其数据类型 相同。表长度因随插入，删除而改变。线性表（a0,a1,a2,an-1)可以线性存储，也可拉链存储 特点：查找某一表项，必须从表的第一个表项开始查找，直到找到为止。数组可以方
6、便的随机存取，但不可任意插，删元 素。a0a1an-12）顺序表的类定义n顺序表的实现：用数组。datalast 0 1 2 MaxSize-1 有三个量来表示数组：data-存放数组 MaxSize-顺序表的最大项数 last-当前已存项数的下标 这三个向量都是封装在私有域中 顺序表的操作常用的操作是:查找，插入，删除。下面是顺序表的类声明：templateclass SeqList public:SeqList(int MaxSize=defaultSize);SeqList()delete data;int Length()const return last+1;int Find(Typ
7、e&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 ilast?NULL:datai;private:Type*data;int MaxSize;int last;构造函数 templateSeqlist:Seqlist(int sz)if(sz0)Maxsize=sz;
8、last=-1;data=new TypeMaxsize;3)顺序表的查找 插入 删除(1)查找：i从0号位置开始找，找到则返回x在data数组中的位 置，否则返回-1 算法分析：假设表中有n项 ACN=(1+2+n)/n 等概率 =(1+n)*n/2n=(n+1)/2 不成功的比较次数为n次 (2）插入 把x插入到i位置,则必须把i到n-1的表项成块向后移一个位置 插入成功返回1，否则返回0 算法分析：插入运算主要在移动元素的时间上 如果有n个元素，在每个位置上插入元素的概率相等，则datalast 0 1 2 n-1 MaxSize-1 0位置，1位置,n位置,一共有n+1情况 AMN=(
9、n-i)/(n+1)=(n+n-1+1+0)/(n+1)=n/2 ni=0（3）删除 01ilast(i+1至last 向前移动)n-1算法分析 AMN=(n-i-1)/n=(n-1+n-2+1+0)/n=(n-1)/2i=04)使用顺序表的例子(用抽象数据类型）(1)将两个顺序表LA,LB当集合来使用,实现并的运算。即两表中如有相同元素只保留一个。算法：从LB中取一个元素，在LA中查找这一元素，如果未 找到则插入到LA中。templatevoid union(seglist&LA,seglist&LB)int n=LA.length();int m=LB.length();for(int i
10、=0;i=m-1;i+)type x=LB.get(i);int k=LA.find(x);if(k=-1)LA.insert(x,n);n+;(2)实现两个顺序表la和lb的交的运算 即求两个表的公共元素。以表la为基准，每取表la中一个元素，看是否在lb中出现，如果没有出现则在la中删除Templatevoid intersection(seglist&la,seglisttype&lb)int n=la.length();int m=lb.length();int i=0;while(i非零元素个数且非零元素是无规则 分佈的。例子：0 0 0 22 0 0 15 0 11 0 0 0 1
11、7 0 0 0 0 6 0 0 0 A6x7=0 0 0 0 0 39 0 91 0 0 0 0 0 0 0 0 28 0 0 0 0分析：首先把非零元素表示出来，一般用三元组（稀疏矩阵 的压缩表示）：行号，列号，值。如上例 稀疏矩阵的抽象数据类型282591043953-6321751111115602230ValuecolrowSmArray01234567*对于稀疏矩阵应该有哪些数据成员？（1）矩阵行数（Rows）（2）列数（Cols）（3）非零元素个数（Terms）（4）非零元素的三元组（SmArray）*对于稀疏矩阵的操作 （1）实现转置矩阵 （2）行数、列数相同的两个稀疏矩阵a与b
12、相加 （3）稀疏矩阵a与b相乘 template class SparseMatrix;template class Trituplefriend class SparseMatrixprivate:int row,col;Type value;template class SparseMatrixpublic:SparseMatrix(int MaxRow,int MaxCol);/构造函数 SparseMatrix Transpose();SparseMatrix Add(SparseMatrix b);SparseMatrix Multiply(SparseMatrix b);Priva
13、te:int Rows,Cols,Terms;Trituple SmArray MaxTerms;5.字符串（String）1)字符串（简称串）的定义以及一些术语 *串：是n（n=0）个字符的一个有限序列，开头结尾用单 引号 或双引号“”括起来。例如：B=“structure”（B为串名）*串的长度：串中所包含的字符个数n（不包括分界符，也不 包括串的结束符0）*空串：长度为0的串。或者说只包含串结束符0的串。注意 0 不等于 0,空串不等于空白串 *子串：串中任一连续子序列 例子：B=peking 则 空串、ki、peking都是B的 子串但pk不是B的子串2)串的基本操作：*构造一个空串；
14、*求串长；*两个串的连接（并置）；*取子串；*求一个子串在串中第一次出现的位置等。3)串的类定义以及串操作的实现：(1)串的类定义：0 1 2 3 4 curlen-1 ch D a t a S t r .maxlen作为类外全局变量说明 const int maxlen=128;class String public:String(const String&ob);String(const char*init);String();String()delete ch;int Length()const return curlen;String&operator()(int pos,int le
15、n);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;private:int curLen
16、;char*ch;(2)部分串操作的实现：maxlen-1 *取子串：0 1 2 3 4 5 String B:ch:P e k i n g curlen-1*串赋值：String a(),b();.a=b;1、如果对赋值号“=”不重载，则实现浅拷贝.2、只有对“=”重载了，才能实现深拷贝.具体赋值过程：（1）先删除原a中的ch数组 （2）为对象a再重分配ch数组 （3）再把b.ch复制到a.ch中achbch *连接操作 String a(),b();.;a+=b;4)字符串的模式匹配（pattern matching）问题：目标串 Target:KxABDABCEFABC模式 patter
17、n:ABC找模式（子串）ABC在目标串KxABDABCEFABC中第一次出现的起始位置，称为模式匹配。(1)朴素的匹配算法*思想：T:a b b a b a P:a b a从头开始比，若对应字符相等，则继续下一对字符，一旦不等，则T从刚刚开始比的下一个字符，P从第 一个字符再开始一轮比较。要么匹配成功，要么没有。*算法：*算法分析：该算法是带有回溯的，在最坏情况下，假设每 趟的比较都在最后出现不等，则比较趟数 n-m+1，每趟比较次数为m,所以总次数=m*(n-m+1)O(m*n)(2)改进的模式匹配算法：KMP(Knuth等人)O(m+n)*目的：克服不必要的回溯例子：T:.abcaxc.P
18、:abcad 为什么：从模式P出发。因为ba,而b与T中b已匹配，所以T中的b与P的第一个a肯定不匹配，不必比较，同理c不等于a，所以T中的c也不必与P中的a相比，.。*问题：当前面i-1个字符匹配，而PiTj，为使j不回退，Tj应与P?比 较.假设Tj应与Pk比，即 Text:“.Tj-i+1.Tj-k+1.Tj-1Tj.”pattern:“P1.Pk-1 Pk.Pi-k+1.Pi-1 Pi.”称：P1P2.Pk-1 =Pi-k+1.Pi-1 前缀子串 后缀子串 注意：pattern：前缀子串与后缀子串可能重复（真子串）例如：aaaab(3）书中的模式匹配改进算法：用的是失效函数Text:T
19、0 T1.Ti.Tn-1 Pattern:P0 P1.Pj Pj+1.Pm-1失效函数f(j)=k text:t0 t1 t2.ti ti+1.pattern:p0 p1 pk pk+1pj-k pj-k+1pj pj+1.pm-1 kF(j)=k-为pj+1匹配失效时用的，当pj+1!=ti+1时t的指针不动，p以pf(j)+1=pk+1作为回退位置*失效函数的定义：P=P0 P1.Pm-2 Pm-1 f(j)=k 当0=k0（即除第1位外）则目标串指针不动，模式P的 开始位置为P f(j-1)+1例如：T:a c a b a a b a a b c a c a a b cP:a b a a
20、 b c a c -1-1 0 0 1-1 0-1 *失效函数的求法：递推法：1.从f0=-1开始，逐个向后求f1,f2,.,fm-12.求fj时，利用在求fj-1所得到的最大相同前后缀子串，然后扩 充一个字符。1）当Pk+1=Pj则fj=k+12）当Pk+1 Pj则前面求出的k长度无用，但可能Pj-1前的更小的串与P0起的更小的串相等。这种串长度由fk给出。此时再看PjP fk+1，以此类推。例：0 1 2 3 4 5 6 7 8 P:ch:a b a a b c a b a f:-1 1 0 0 1 0 0 1 2 时间复杂度的分析：总共m次 外循环：j+:1m-1次 内循环：i的值不断减
21、，次数也不会多于m-1次 复杂度为：O(n+m)其中n=lengthT,m=lengthP考题1.在字符串匹配的KMP算法中，模式p=p0p1p2 pm-2pm-1的失效函数定义为:k 当0=kj 且使得p0p1p2pk=pj-kpj-k+1pj的最大整数最大整数 -1 其他情况 举例说明为什么要特别指出为最大整数最大整数 答：K为最大整数是为了不失去可能的匹配。例如：T：“a a a a b b b“P：“a a a b”如果fail2取0，则当P3!=T3时，T中的下标i不变,P中下j回到fail2+1=1的位置，则失去可能的匹配。如果fail2取1，则当P3!=T3时，T中的下标i不变,P中下j回到fail2+1=2的位置，则匹配成功。f(j)=2.习题2-93.习题2-16
