数据结构课件老师chapter

1、 第2章 数组1. 数组及其抽象数据类型 1)一维数组 2) 一维数组的抽象数据类型的类声明 3)二维数组（矩阵） 4)特殊矩阵2.顺序表(sequential List) 1)顺序表定义和特点 2) 顺序表的类定义 3)顺序表的查找 插入 删除 4) 使用顺序表的例子(用抽象数据类型）3.多项式抽象数据类型 1)如何表达多项式：系数，阶数 2)多项式相加 4. 稀疏矩阵 5.字符串（String） 1) 字符串（简称串）的定义以及一些术语 2)串的基本操作 3)串的类定义以及串操作的实现 4)字符串的模式匹配（pattern matching） 朴素的匹配算法 改进的模式匹配算法：KMP第2

2、章 数组数组：具有相同数据类型的数据元素的集合。 一般存储于一个连续存储空间中。 通过数组元素的下标来存取该元素。1. 数组及其抽象数据类型 1)一维数组：具有相同数据类型的n（n=0）个元素的有限序列。例如： 0 1 2 3 4 5 6 7 8 9 a： i 下标i为数组元素到数组开始的偏移量 Loc(ai)=loc(a0)+i*l35274918605477834102 2 ) 一维数组的抽象数据类型的类声明 对数组的操作主要有：对数组元素的存与取。 3 ) 二维数组（矩阵） 由n个行向量和m个列向量所组成的向量 a00 a01 a02 a0,m-1 Anm = a10 a11 a12 a

3、 1,m-1 an-1,0an-1,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 同理

4、对三维数组am1m2m3 其下标元素aijk Loc(i, j, k)=Loc(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+(

5、n-1)+(n-i+2)+j-i*L =loc(1,1)+(n-k+1)+j-i*L K=1i-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） 顺序表的类定义顺序表的实现：用数组。 datalast 0 1 2 MaxSize-1 有三个量来表示数组： data-存放数组 MaxSize-顺序表的最大项数 last-当前已存项数的下标 这三个向量都是封装在私有域中 顺序表的操作常用的操作是:查找，插入，删除。 下面是顺序表的类声明：templateclass SeqList public: SeqList(int MaxSize=defaultSize); SeqLis

7、t( )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 ilast? NULL:datai;

8、private: Type * data; int MaxSize; int last; 构造函数 templateSeqlist:Seqlist(int sz) if(sz0) Maxsize=sz; 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，

9、否则返回0 算法分析：插入运算主要在移动元素的时间上 如果有n个元素，在每个位置上插入元素的概率相等，则datalast 0 1 2 n-1 MaxSize-1 0位置，1位置,n位置,一共有n+1情况 AMN=(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中取一个元素

10、， 在LA中查找这一元素，如果未 找到则插入到LA中。templatevoid union(seglist&LA,seglist&LB) int n=LA.length( ); int m=LB.length( ); for (int i=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

11、(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 17 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分析：首先把非零元素表示出来，一般用三元组（稀疏矩阵 的压缩表示）：行号，列号，值。如上例 稀疏矩阵的抽象数据类型SmArray01234567rowcolValue03220615111

12、1151723-6353940915228*对于稀疏矩阵应该有哪些数据成员？ （1）矩阵行数（Rows） （2）列数（Cols） （3）非零元素个数（Terms） （4）非零元素的三元组（SmArray）*对于稀疏矩阵的操作 （1）实现转置矩阵 （2）行数、列数相同的两个稀疏矩阵a与b相加 （3）稀疏矩阵a与b相乘 template class SparseMatrix;template class Trituplefriend class SparseMatrixprivate: int row,col; Type value;template class SparseMatrixpubli

13、c: SparseMatrix(int MaxRow,int MaxCol);/构造函数 SparseMatrix Transpose(); SparseMatrix Add (SparseMatrix b); SparseMatrix Multiply (SparseMatrix b);Private: int Rows,Cols,Terms; Trituple SmArray MaxTerms; 5.字符串（String）1) 字符串（简称串）的定义以及一些术语 *串：是n（n=0）个字符的一个有限序列，开头结尾用单 引号 或双引号“ ”括起来。 例如： B=“structure” （B为

14、串名） *串的长度：串中所包含的字符个数n（不包括分界符，也不 包括串的结束符0） *空串：长度为0的串。或者说只包含串结束符0的串。 注意 0 不等于 0 , 空串不等于空白串 *子串：串中任一连续子序列 例子：B=peking 则 空串、ki、peking都是B的 子串但pk不是B的子串2)串的基本操作： *构造一个空串；*求串长；*两个串的连接（并置）； *取子串；*求一个子串在串中第一次出现的位置等。3)串的类定义以及串操作的实现： (1)串的类定义： 0 1 2 3 4 curlen-1 ch D a t a S t r . maxlen作为类外全局变量说明 const int ma

15、xlen=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 len); int operator = =(const String & ob) const return strcmp(ch, ob.ch)= =0; int operator !=(const String &ob) cons

16、t 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; char * ch; (2)部分串操作的实现： maxlen-1 *取子串： 0 1 2 3 4 5 String B: ch: P e

17、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模式 pattern:ABC找模式（子串）ABC在目标串KxABDABCEFABC中第一次出现的起始位置，称为模式匹配。 (1

18、)朴素的匹配算法*思想：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:abcad 为什么：从模式P出发。因为ba,而b与T中b已匹配，所以T中的b与

19、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: T0 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 b c a