数据结构与C++算法设计案例教程课件

模块五数组、串和广义表数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件书名：数据结构与C++算法设计案例教程作者：赖俊峰ISBN：978-7-111-31755-5出版社：机械工业出版社数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件教材详情：点击查阅机械工业出版社教材服务网任务一数组任务二串

任务三广义表

数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件任务一数组子任务1数组的定义子任务2数组的基本操作

子任务3特殊矩阵的压缩存储

数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件子任务1数组的定义在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。数组作为一种数据结构，其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，以此类推。如图5-1表示一个m行n列的二维数组。数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件图5-1中的A数组可看成是由m个行向量或者n个列向量组成的线性表。对于上述二维数组A，这里可以将A看成是下述线性表A'=(d1,d2,…,dn)

其中每一个数据元素dj本身也是一个线性表dj=(d1j,d2j,…,dmj)1≤j≤n。该线性表是二维数组A的第j个列向量。同样，也可将二维数组A看成线性表A‘’=(s1,s2,…,sm),其中每个si本身也是一个线性表si=(si1,si2,…,sin)1≤i≤m，si是二维数组A的第i个行向量。类似地，一个三维数组可以看成是数据元素为二维数组的线性表。一般地，一个n维数组可视为其数据元素为n-1维数组的线性表。Am×n=a21a22。。。。。。a2nam1am2。。。。。。

amna11a12。。。。。。a1n。。。。。。。。。。。。。。。图5-1数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件二维数组中每个元素ai,j均属于两个向量，第i行的行向量和第j列的列向量。因此，除边界外，每个元素ai,j都恰好有两个直接前趋和直接后继：行向量上的直接前趋ai,j-1和直接后继ai,j+1，列向量上的直接前趋ai-1,j和直接后继ai+1,j；二维数组中有且仅有一个开始结点a11，它没有直接前趋；有且仅有一个终端结点amn，它没有直接后继；边界上的结点(开始结点和终端结点除外)只有一个直接前趋或者只有一个直接后继。即除开始结点a11外，第一行和第一列上的结点a1j(j=2,...,n),ai1(i=2,...,m)都只有一个直接前趋；除终端结点amn外，第m行和第n列上的结点amj(j=1,...,n-1),ain(i=1,...,m-1)都只有一个直接后继。数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。数组通常只有两种基本运算——读和写。①读：给定一组下标，读取相应的数据元素。②写：给定一组下标，修改相应的数据元素。数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件数组上的基本操作有：(1)数组的输入：ArInput()

初始条件：数组存在。操作结果：向数组元素中输入元素。(2)求数组的长度：ArLength()

初始条件：数组存在。操作结果：显示数组中有效元素的个数。(3)取数组元素：ArGetElem(intn)

初始条件：数组存在。操作结果：显示数组指定元素，如果没有则显示空。(4)按值查找：ArLocateElem(intm)，m是给定的一个数据元素初始条件：数组存在。操作结果：显示m所在的位置，如果没有则显示空。数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件(5)地址操作：ArAddress(inti)

初始条件：数组存在。操作结果：显示第i号元素的地址(6)插入操作：ArInsertElem(inti,intj,intk,char*e)

初始条件：数组存在。操作结果：在第i个的第j个的第k个位置插入元素e。(7)删除操作：voidArDeleteElem(inti,intj,intk)

初始条件：数组存在。操作结果：在第i个的第j个的第k个位置插入元素。数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件二维数组的两种存储方式一种是以列序为主序的存储方式一种是以行序为主序的存储方式数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件(a)列序为主序：

a11a21．．．am1a12a22．．．Am2

．．．

a1na2n．．．amn(b)行序为主序：

a11a12．．．a1na21a22．．．A2n

．．．

am1am2．．．amn以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件按上述两种方式顺序存储的数组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件举例二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用d个存储单元。元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有(i-1)×n个元素，第i行上aij前面又有j-1个元素，故它前面一共有

(i-1)×n+j-1个元素，因此，aij的地址计算函数为：LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件三维数组Aijk按“行优先顺序”存储，其地址计算函数为：LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p+(k-1)]*d上述讨论均是假设数组各维的下上界是1的情况，更一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是1。aij前一共有i-c1行，二维数组一共有d2-c2+1列，故这i-c1行共有(i-c1)*(d2-c2+1)个元素，第i行上aij前一共有j-c2个元素，因此，aij的地址计算函数为：LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*d数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件在C++语言中，数组各维下标的下界是0，因此在C语言中，二维数组的地址计算公式为：LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件子任务2数组的基本操作数组的主要基本操作包括：1、向数组元素中输入元素2、显示数组中有效元素的个数3、插入元素4、删除元素数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件【案例】对学生宿舍楼（包括层数，每层宿舍数，每宿舍学生数）管理创建一个三维数组#include<iostream>usingnamespacestd;classDormArray//宿舍楼数组类{private:intcnt;//当前有效元素的个数

char*Dormitory[6][30][6]; //学生宿舍数组，每座宿舍楼有6层，每层有30个宿舍，每个宿舍住6个学生public: voidArInput();//向数组元素中输入元素，

voidArLength();//显示数组中有效元素的个数

voidArInsertElem(inti,intj,intk,char*e);//在第i号楼、第j号宿舍、k号床位插入元素e voidArDeleteElem(inti,intj,intk);//在第i号楼、第j号宿舍、k号床位删除元素e};数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件1、向数组元素中输入元素voidDormArray::ArInput(){inti,j,k; for(i=0;i<6;i++) for(j=0;j<30;j++) for(k=0;k<6;k++) Dormitory[i][j][k]=NULL;//将指针数组都置为空

cnt=0; cout<<"以-1结束"<<endl; while(1) {cout<<"请你依次输入所在楼层号、宿舍号、床位号："<<endl; cin>>i; if(i==-1)break; cin>>j; cin>>k; cout<<"请你输入学生姓名"<<endl; char*name=newchar[10]; cin>>name; Dormitory[i-1][j-1][k-1]=name; cout<<name<<endl; cnt++;//计数器累加

cout<<endl; }}数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件本程序完成初始化学生宿舍数组Dormitory的功能。首先，清空Dormitory数组（将指针数组都置为空）；然后，逐个向学生宿舍数组中输入元素，输入内容包括学生所在楼层号、宿舍号、床位号与学生姓名，程序会根据楼层号、宿舍号、床位号确定学生所在Dormitoory数组的位置，元素内容为学生姓名。在输入每个学生信息时，当前有效元素个数cnt，自动累加。最后，在提示“请你依次输入所在楼层号、宿舍号、床位号：”后输入－1完成学生录入。数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件2、显示数组中有效元素的个数voidDormArray::ArLength(){cout<<"宿舍楼中一共有"<<cnt<<"个学生"<<endl;}数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件本函数的功能是显示学生宿舍数组Dormitory中有效元素（非空元素的个数）。实现方法：只需输出记录当前Dormitory数组有效元素的个数的变量cnt即可。数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件3、插入元素voidDormArray::ArInsertElem(inti,intj,intk,char*e)//在第i号楼、第j号宿舍、k号床位插入元素e{inti1,j1,k1; if(Dormitory[i-1][j-1][k-1]!=NULL)cout<<"本位置已经被其他同学占用了！"<<endl; else {cnt++; Dormitory[i-1][j-1][k-1]=e; for(i1=0;i1<6;i1++) for(j1=0;j1<30;j1++) for(k1=0;k1<6;k1++) if(Dormitory[i1][j1][k1]!=NULL) {cout<<"第"<<i1+1<<"层、第";cout<<j1+1<<"号宿舍、第";cout<<k1+1<<"号床位是：";cout<<Dormitory[i1][j1][k1]<<endl; } }}数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件上面的函数完成安排学生住宿的功能，即判断在第i号楼、第j号宿舍、k号床位插入元素e。首先，判断要插入的位置是否已被占用，如果已被占用，输出“本位置已经被其他同学占用了！”提示信息，结束程序运行；否则，将元素e插入相应位置；然后，将当前有效元素的个数（cnt）加1；最后，输出所有学生信息（数组中的所有非空的元素）。数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件4、删除元素voidDormArray::ArDeleteElem(inti,intj,intk)//在第i号楼、第j号宿舍、k号床位删除元素e{ inti1,j1,k1; if(Dormitory[i-1][j-1][k-1]==NULL)cout<<"本位置为空！"<<endl; else { cnt--; Dormitory[i-1][j-1][k-1]=NULL; for(i1=0;i1<6;i1++) for(j1=0;j1<30;j1++) for(k1=0;k1<6;k1++) if(Dormitory[i1][j1][k1]!=NULL) cout<<"第"<<i1+1<<"层、第";cout<<j1+1<<"号宿舍、第";cout<<k1+1<<"号床位是：";cout<<Dormitory[i1][j1][k1]<<endl; }}数据结构与C++算法设计案例教程赖俊峰978-7-111-31755-5高职高专ppt课件本函数完成学生搬离宿舍，即：在第i号楼、第j号宿舍、k号床位删除元素e的工作。首先，判断该位置是否存在学生，若不存在，结束程序运行；否则，将学生宿舍数组Dormitory中相应元素设为NULL；然后，将当前有效元素的个数（cnt）减1；最后，输出所有学生信息（数组中的所有非空的元素）。子任务3特殊矩阵的压缩存储矩阵在计算机中是以二维数组的方式来存储的，对于一些特殊的矩阵，为了节省存储空间，采用压缩存储的方式来保存矩阵。本子任务主要讨论如下矩阵：1、对称矩阵2、三角矩阵3、稀疏矩阵1．对称矩阵在一个n阶方阵A中，若元素满足下述性质：

aij=aji0≦i,j≦n-1则称A为对称矩阵。如图5-2（a）便是一个5阶对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。如果按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式图5-2（b）所示。A=50800302511513718926图5-2（a）对称矩阵30251A=a10a11a20a21a23a33a00a20a21a23图5-2（b）存储形式图a20a21a23a34a44在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：(n+1)/2。因此，可以按从上到下、从左到右将这些元素存放在一个向量M[0..n(n+1)/2-1]中。展开后即为下面的格式：a00a10a11a20a21a23…an-10an-11an-12…an-1n-1为了便于访问对称矩阵A中的元素，就必须在aij和M[k]之间找一个对应关系。若i>=j，则aij在下三角形中。aij之前的i行（从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上，aij之前恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有关系式：

k=i*(i+1)/2+j0<=k<n(n+1)/2若i<j，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到：

k=j*(j+1)/2+i0<=k<n(n+1)/2对于给定矩阵A中的一个元素aij，根据它的下标(i,j)，就能由上述公式确定其在数组M中的位置k。而aij在内存的存储地址可用下列公式求出(假设每个数据元素占用L个存储单元)：

LOC(aij)=LOC(M[k])=LOC(M[0])+k*L注：上述的推导公式与二维的逻辑结构的起始下标以及存储的起始小标有关。2．三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。所谓上(下)三角矩阵是指矩阵的下(上)三角(不包括对角线)中元素均为常数C或零的n阶矩阵.如图5-3所示。(a)上三角矩阵A=ca11…a1n-1…..a00a01…a0n-1…..cc…an-1n-1(b)下三角矩阵A=a10a11…c…..a00c…c…..an-10an-11…an-1n-1图5-3三角矩阵因此，三角矩阵可压缩存储到数组M[1..n*(n+1)/2+1]中，其中c若非0，则存放到数组的最后一个下标变量中。在三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量M[0..n(n+1)/2]中，其中c存放在M[n(n-1)/2]中。上三角矩阵中，主对角线之上的第i行(0≦i<n)恰有n-i个元素，按行优先顺序存放上三角矩阵中的元素aij时，aij之前的i行一共有i(2n-i+1)/2个元素，在第i行上，aij前恰好有j-i个元素：aii,aii+1,…aij-1。因此，M[k]和aij的对应关系是：

i(2n-i+1)/2+j-i当i≦jn(n+1)/2当i>j下三角矩阵的存储和对称矩阵类似sa[k]和aij对应关系是：

i(i+1)/2+ji≧jn(n+1)/2i<j3．稀疏矩阵设m*n矩阵中有s个非零元素，若s远远小于矩阵元素的总数（即s<<m×n），这样的矩阵称为稀疏矩阵。确切的说，令e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e≦0.05时称之为稀疏矩阵。稀疏矩阵的压缩存储方法是只存储非零元素，但由于非零元素的分布一般是没有规律的，在存储非零元素的同时，还必须同时记下它所在的行和列的位置(i,j)。对每个非零元素aij，可以用一个三元组(i,j,aij)唯一确定，其中aij表示该非零元素的值，i,j为该元素在原矩阵中的行号和列号。然后将所有非零元素的三元组按一定次序排列在一起构成三元组表。图5-4为稀疏矩阵和对应的三元组表表示，对于一个稀疏矩阵，可以按行序为主搜索其非零元素，并以此放入三元组表中，在三元组表的最下一行表示稀疏矩阵的行数和列数和非零元素的个数，只有这样的三元组表才能还原出原来的稀疏矩阵。图5-4稀疏矩阵和对应的三元组表表示A=00060070010000120005050030000000009000000000(a)稀疏矩阵(b)三元组表序 行 列 值 1 1 2 12 2 1 6 5 3 2 4 6 4 3 2 5 5 3 5 3 6 4 1 7 7 4 4 10 8 6 3 9 9 7 6 8 任务二串子任务1串的概念子任务2串的存储子任务3串的模式匹配算法

子任务1串的概念下面介绍另一种具有线性结构的数据结构——串，它也是一种顺序表，本子任务内容主要有：1、串的定义。2、串的相关术语。3、串的基本操作。1．串的概念串是零个或多个字符组成的有限序列。一般记作S=‘’a1a2a3…an‘’，其中S是串名，双引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符。2．串的相关术语（1）串长度：串中所包含的字符个数称为该串的长度。（2）空串：长度为零的串称为空串，它不包含任何字符。（3）空白串：仅由一个或多个空格组成的串称为空白串。空串和空白串的不同，例如''''和''''分别表示长度为1的空白串和长度为0的空串。（4）子串：串中任意个连续字符组成的子序列称为该串的子串。空串是任意串的子串，任意串是其自身的子串。（5）主串：包含子串的串被称为主串。（6）子串在主串中的位置：子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为

A=''Thisisastring''B=''is''

则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3。串的基本操作有：(1)StrInput(charstr[])

初始条件：串str[]存在。操作结果：向任意一个str[]赋值。(2)StrDisplay(charstr[]);

初始条件：串str[]存在。操作结果：显示一个str[]赋值。(3)StrClear(charstr[])

初始条件：串str[]存在。操作结果：清空一个str[]的值。(4)StrCopy(charstr1[],charstr2[]);

初始条件：串str1[]和str2[]存在。操作结果：把str1[]的内容拷贝到str2[]中。(5) StrCompare(charstr1[],charstr2[]);

初始条件：串str1[]和str2[]存在。操作结果：比较str1[]中的内容与str2[]的内容是否相同,显示结果(6)StrSubstring(charstr[],intp,intlength);

初始条件：串str[]存在。操作结果：显示一个str[]中p位置开始长度为length的子串。(7)voidStrConcat(charstr1[],charstr2[],charstr3[]);

初始条件：串str1[]和str2[]存在。操作结果：把str2[]和str3[]的内容进行连接,存入str1[]中。(8)StrIndex(charstr1[],charstr2[]);

初始条件：串str1[]和str2[]存在。操作结果：在str1[]中寻找与str2[]一样的字符串,显示所在的位置,没有则显示"无此串",用简单模式匹配算法实现。(9)voidStrKMP(charstr1[],charstr2[]);

初始条件：串str1[]和str2[]存在。操作结果：在str1[]中寻找与str2[]一样的字符串,显示所在的位置,没有则显示"无此串",用KMP算法实现(重要)子任务2串的存储串的存储方式主要有三种，本子任务主要讲解：1、定长顺序存储表示2、堆分配存储表示3、串的链式存储结构1．定长顺序存储表示定长顺序存储表示是用一组连续的存储单元来存放串中的字符序列，可直接使用定长的字符数组来定义，数组的上界预先给出：

#definemaxstrlen256typedefcharsstring[maxstrlen];sstrings;//s是一个可容纳255个字符的顺序串。

例如，在C++语言中使用一个不会出现在串中的特殊字符‘\0’在串值的尾部来表示串的结束。所以串空间最大值maxstrlen虽然为256，但最多只能存放255个字符，必须留一个字节来存放‘\0’字符。若不设终结符，可用一个整数来表示串的长度，那么该长度减1的位置就是串值的最后一个字符的位置。此时顺序串的类型定义和顺序表类似：

classsstring{public：

charch[maxstrlen];intlength;};//其优点是涉及到串长操作时速度快。2．堆分配存储表示在这种存储表示下，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。在C++语言中，利用动态存储管理函数，来根据实际需要动态分配和释放字符数组空间。这样定义的顺序串类型如下：

classhsring{char*ch;intlength;};

3．串的链式存储结构在顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，这里可用单链表方式来存储串值，串的这种链式存储结构简称为链串。

classlstring{chardata;lstring*next;};这种结构便于进行插入和删除运算，但存储空间利用率太低。为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。其类型定为：

#definenodesize80classlstring{chardata[nodesize];lstring*next;};子任务3串的模式匹配算法串的操作包括：1、串的基本操作2、串的模式匹配算法3、改进的模式匹配算法（KMP算法）1、串的基本操作对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。在C++语言中，常用的串运算有串的赋值运算、求串的长度运算、串连接运算、串比较运算和求子串运算，上述串的操作是最基本的，故称为串运算的最小子集。串的其余操作可由这些基本操作组合而成。2．模式匹配算法子串定位运算又称为模式匹配或串匹配，就是在主串中取从第i个字符起、长度和串T相等的子串和T比较，若相等，则求得函数值为i，否则值增1直至S中不存在和串T相等的子串为止。在串匹配中，一般将主串称为目标串，子串称之为模式串。设S为目标串，T为模式串，且不妨设：

S="s0s1s2…sn-1"T="t0t1…tm-1"串的匹配实际上是对于合法的位置0<=i<=n-m依次将目标串中的子串s[i..i+m-1]和模式串t[0..m-1]进行比较，若s[i..i+m-1]=t[0..m-1]，则称从位置i开始的匹配成功，亦称模式t在目标s中出现；若s[i..i+m-1]≠t[0..m-1]，则称从位置i开始的匹配失败。上述的位置i又称为位移，当s[i..i+m-1]=t[0..m-1]时，i称为有效位移；当s[i..i+m-1]≠t[0..m-1]时，i称为无效位移。这样,串匹配问题可简化为是找出某给定模式T在一给定目标T中首次出现的有效位移。串匹配的算法很多，这里先讨论一种最简单的称为朴素的串匹配算法。其基本思想是用一个循环来依次检查n-m+1个合法的位移i(0≦i≦n-m)是否为有效位移，例如：

for(i=0;i<=n-m;i++){if(S[i..i+m-1]=T[0..m-1])returni;

｝下面以定长的顺序串类型作为存储结构，给出具体的串匹配算法。intindex(sstrings,sstringt,intpos){inti,j,k;intm=s.length;intn=t.length;for(i=0;i<=n-m;i++){j=0;k=i;while(j<m&&s.ch[k]==t.ch[j]{k++;j++;}if(j==m)returni;}return–1;}显然，该算法在最坏情况下的时间复杂度为O((n-m)m)。3、改进的模式匹配算法（KMP算法）这个算法是D.E.Knuth与V.R.Pratt和J.H.Morris三个人同时发现的，因此人们称它为克努特---莫里斯—普拉特操作，简称为KMP算法。此算法可以在O（n+m）的时间数量及上完成串的模式匹配操作。其改进在于每当在一趟匹配过程中出现对应位置的字符不相等时，其字符指针并不回退，而是利用已经得到的“部分匹配”的结果将模式向右滑动尽可能远的一旦距离后，继续进行比较。例如有主串S="ababcabcacba"和子串T="abcac"，按简单的匹配算法进行时，其匹配过程如图5-5：S='ababcabcacbab'j=3-〉1i=3--〉2T='abcac'图5-5(a)S='ababcabcacbab'j=5-〉1i=7--〉4T='abcac'图5-5(b)图5-5简单的模式匹配仔细观察在图5-5（b）比较不成功时，因为模式串中第一个字符是a，故不需要和i=4、i=5、和i=6进行比较，而仅需将模式向右滑动三个字符的位置继续比较i=7和j=2的字符是否相等即可。同理在第一次比较失败（图5-5（a））后，只需将模式串的指针j修改为j=1，而主串继续加1（i=3）即可，由此可得在整个匹配过程中，i的指针没有回退，这就是KMP的主要思想。现在讨论一般情况，假设主串''S1…Sn'',模式串''P1…Pm'',KMP算法需解决下述问题，当匹配过程产生失败（Si不等于Pj）时，指针j需要向右滑动多大的距离，而使得i不回退继续进行下一次的比较。假设此时应与模式串中第k（k<j）个字符，则模式串中的前k-1个字符的子串必须满足下列的关系，且不可能存在大于k的其它值满足此关系。

'P1…Pk-1'='Si-(k-1)…Si-1'(5-1)式已经得到的部分匹配可知如下的关系式成立：'Pj-k+1…Pj-1'='Si-(k-1)…Si-1'(5-2)式由4-1式和4-2式可得以下结果'P1…Pk-1'='Sj-(k-1)…Sj-1'(5-3)式反之，若模式串中存在满足5-3式的两个子串，则当匹配过程中，主串的第i个字符与模式串的第j个字符比较不等时，仅需将模式向右滑动到模式串中第k个字符与主串的第i个字符对齐即可继续比较。现在的问题是求解子串的第j个字符比较失败是如何求解下一个比较位置，用next[j]数组来表示第j个字符比较失败时下一个比较位置。由上面的5-3式可以得到图5-6的关系：一旦失配，应从模式串T中第next[j]个字符开始与S的失配点i重新匹配。next[j]＝0当j＝1时max{k|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)

…Tj-1’}1其他情况图5-6next[j]的求解推算模式串“abaabcac”的next函数值如下：j=1时,next[j]≡0；因为属于“j=1”;j=2时,next[j]≡1；因为属于“其他情况”；j=3时,k={2}，只需查看‘T1’=‘T2’；j=4时,k={2，3}，要查看‘T1’=‘T3’和‘T1T2’=‘T2T3’j=5时,k={2，3，4}，要查看‘T1’=‘T4’、‘T1T2’=‘T3T4’和‘T1T2T3’=‘T2T3T4’由上面的求解可得到如下的next的求解值。可能失配位j：12345678模式串T：abaabcac新匹配位

next[j]:01122312KMP算法在形式上与简单模式匹配算法极为相似，不同之处仅在于当匹配过程产生失败时，指针i不变，指针j退回到next[j]所指示的位置上重新进行比较，并且当指针j退回到0时，指针i和指针j需要同时增1。下面给出串的最基本几个算法

charstr1[100],str2[100];voidAdressString::StrIndex(charstr1[],charstr2[]) //在str1[]中寻找与str2[]一样的字符串,显示所在的位置,没有则显示"无此串",//用简单模式匹配算法实现(重要){ inti=0,j=0; while(i<strlen(str1)&&j<strlen(str2)) //用while循环进行匹配

{ if(str1[i]==str2[j]) //如果当前字符相同,则继续惊醒比较

{ i++; j++; } else //否则,则从开始位置的下一位置进行比较

{ i=i-j+1; j=0; } } if(j==strlen(str2)) //j==strlen(str2)匹配成功

{ cout<<"str1中包含str2!"<<endl; cout<<"位置为(从0开始):"<<i-j<<endl<<endl; } elsecout<<"str1中不包含str2!"<<endl<<endl; //j<strlen(str2,)匹配不成功}用简单模式匹配算法实现在str1[]中寻找与str2[]一样的字符串并显示所在的位置,没有则显示“无此串”。首先，定义两个初始值为0的变量i、j，分别标记str1与str2的下标。然后，从两个字符串的开始位置，逐个匹配。若匹配成功，则i和j同时加1，否则，i赋值为开始匹配成功字符的下一个字符，j重新赋值为0。直到循环条件不成立为止。最后，判断变量j的值，若j==strlen(str2)说明匹配成功了str2中的所有字符，所在位置为i－j。voidAdressString::StrKMP(charstr1[],charstr2[]) //在str1[]中寻找与str2[]一样的字符串,显示所在的位置,没有则显示"无此串",//用KMP算法实现(重要){ inti=0,j=0,next[100]; while(i<strlen(str1)&&j<strlen(str2)) { if(str1[i]==str2[j]) //如果当前字符相同,则继续进行比较

{ i++; j++; } else j=getnext(next);

} cout<<"i="<<i<<endl; if(j==strlen(str2))//j==strlen(str2)匹配成功

{ StrIndex(str1,str2); } elsecout<<"str1中不包含str2!"<<endl<<endl; //j<strlen(str2),匹配不成功}用KMP算法实现在str1[]中寻找与str2[]一样的字符串并显示所在的位置,没有则显示"无此串"。首先，定义两个初始值为0的变量i、j，分别标记str1与str2的下标。然后，从两个字符串的开始位置，逐个匹配。若匹配成功，则i和j同时加1，否则，i值不变，j使用函数getnext(next)重新赋值。直到循环条件不成立为止。最后，判断变量j的值，若j==strlen(str2)说明匹配成功了str2中的所有字符，调用函数StrIndex(str1,str2)输出相应成功信息。intAdressString::getnext(intnext[]){ inti=0,j=0; next[0]=0; while(j<strlen(str2)) { if(j==0||str2[i]==str2[j]) { i++; j++; next[i]=j; } elsej=next[j];

} returnj;}该函数完成的功能是，根据str1自身的性质，求出如果遇到不匹配字符时在指向str1的下标不变的情况下，指向str2的下标需要回溯的距离。任务三广义表广义表也是一种线性表，本任务内容围绕以下几个方面展开：1、广义表的定义2、广义表的存储结构3、广义表的构造及其算法1．广义表的定义广义表是n(n>=0)个元素d1，d2，……dn的有限序列，其中di或者是原子项，或者是一个广义表。通常记作LS=(d1，d2，……dn)。LS是广义表的名字，n为它的长度。若di是广义表，则称它为LS的子表，为了区别原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。广义表具有如下的结构特点:（1）广义表中的数据元素有相对次序。（2）广义表的长度定义为最外层包含的元素个数。（3）