《数据结构 第四章教学课件 .ppt》由会员分享，可在线阅读，更多相关《数据结构 第四章教学课件 .ppt（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构 第四章教学课件 第四章第四章 串、矩阵和广义表串、矩阵和广义表数据结构数据结构目目录录第四章第四章第四章第四章串、矩阵串、矩阵串、矩阵串、矩阵和广义表和广义表和广义表和广义表4 41 12 23 3 串及其运算串及其运算串的顺序存储与实现串的顺序存储与实现矩阵矩阵广义表广义表5 54.6 4.6 矩阵的应用矩阵的应用总总体要求体要求掌握串的特点、表示和实现；掌握串的特点、表示和实现；熟悉串的类型和作用；熟悉串的类型和作用；掌握稀疏矩阵掌握稀疏矩阵了解广义表的概念和相关操作了解广义表的概念和相关操作4.1 串及其运算串及其运算u4.1.1 串的基本概念串的基本概念串的串的值值值值 串的
2、串的长度长度长度长度 串的串的名字名字名字名字 串：串：串：串：是由是由 0 个或多个字符组成的有限序列。个或多个字符组成的有限序列。记为：记为：s=a1 a2 a3 ai an (n0)。字母、数字或其他字符字母、数字或其他字符 零个字符的串称为零个字符的串称为空串空串，通常用符号，通常用符号“”来来表示，它的长度为零。表示，它的长度为零。u4.1.2 串的基本操作串的基本操作串的逻辑结构：串的逻辑结构：串的逻辑结构：串的逻辑结构：和线性表极为相似和线性表极为相似。串的基本操作：串的基本操作：串的基本操作：串的基本操作：和线性表有很大差别。和线性表有很大差别。区别：区别：串的数据对象约定是字
3、符集。串的数据对象约定是字符集。线性表的基本操作：线性表的基本操作：以以“单个元素单个元素”为操作对象；为操作对象；串的基本操作：串的基本操作：以以“串的整体串的整体”作为操作对象。作为操作对象。例：例：在串中查找某个子串；在串中查找某个子串；在串的某个位置上插入一个子串；在串的某个位置上插入一个子串；删除一个子串等。删除一个子串等。子串：子串：由串中由串中任意任意个个连续连续的字符组成的子序列。的字符组成的子序列。主串：主串：包含子串的串。包含子串的串。字符位置：字符位置：字符在序列中的序号。字符在序列中的序号。子串位置：子串位置：子串的子串的首字符首字符在主串中的位置。在主串中的位置。例：
4、例：a=cheng，b=du，c=chengdu，d=cheng du只有当两个串的长度相等，并且各个对应位置的字符只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等都相等时才相等，故，故c d。串长分别为串长分别为5、2、7、8且且a、b都是都是c、d的子串。的子串。a在在c和和d中的位置都是中的位置都是1，而，而b在在c中的位置是中的位置是6，在，在d中的位中的位置则是置则是7。串复制串复制：将某个串复制给当前串：将某个串复制给当前串串连接串连接：将串：将串S1S1和和S2S2联接而成一个新串联接而成一个新串串替换串替换：用子串：用子串x x替换当前串中的子串替换当前串中的子串y
5、 y插入子串插入子串：将子串插到当前串中的某个位置：将子串插到当前串中的某个位置删除子串删除子串：从当前串中删除指定子串：从当前串中删除指定子串大写转小写大写转小写：将串中的大写字母转化为对应小写字符：将串中的大写字母转化为对应小写字符小写转大写小写转大写：将串中的小写字母转化为对应大写字符：将串中的小写字母转化为对应大写字符串压缩串压缩：将当前串中首部和尾部的所有空格删除：将当前串中首部和尾部的所有空格删除判空判空：判断当前串是否为空：判断当前串是否为空串比较串比较：判断当前串与指定串是否相等：判断当前串与指定串是否相等求串长：求串长：返回当前串的字符个数返回当前串的字符个数求子串求子串：返
6、回串的第：返回串的第i i个字符开始的长达个字符开始的长达k k个字符的子串个字符的子串子串定位子串定位：输出子串在当前串中首次出现的位置：输出子串在当前串中首次出现的位置引引用用型型加加工工型型 串的基本操作串的基本操作4.2 串的串的顺顺序存序存储储与与实现实现在串的顺序存储中，一般有三种方法表示串的长度：在串的顺序存储中，一般有三种方法表示串的长度：用一个变量来表示串的长度用一个变量来表示串的长度(2)在串尾存储一个特殊字符作为串的终结符在串尾存储一个特殊字符作为串的终结符(3)用数组的用数组的0号单元存放串的长度号单元存放串的长度4.2.2 串的实现串的实现public class s
7、tringprivate int maxSize=10;private char chars;private int length;public string()public string(int n)public void copy(string t)public boolean isEmpty()public int compare(string t)public int getLength()./此处省略部分成员方法此处省略部分成员方法 顺序存储结构顺序存储结构的串可以用的串可以用字符数组字符数组来存储字符数据来存储字符数据串中字符数组串中字符数组的初始长度的初始长度存储元素的数组对象存
8、储元素的数组对象保存串的当前长度保存串的当前长度【算法算法4-1】串初始化串初始化无参构造方法无参构造方法public string()/构造一个空串构造一个空串有参构造方法有参构造方法public string(int n)/构造一个能保存构造一个能保存n个字符的串个字符的串this.maxSize=n;this.chars=new charn;this.length=0;【算法算法4-2】串比较串比较public int compare(string t)int i=0;while(this.charsi=t.charsi&ithis.length&it.getLength()i+;if(
9、i=this.length&i=t.length)return 0;else if(i=t.getLength()&ithis.length)return 1;elsereturn-1;若当前串等于串若当前串等于串t t，则返回值，则返回值0 0若当前串大于串若当前串大于串t t，则返回值，则返回值1 1若当前串小于串若当前串小于串t t，则返回值，则返回值-1-1【算法算法4-3】串联接串联接public void concat(string t)if(this.maxSize this.length+t.getLength()/当前串容量不够，暂存到数组当前串容量不够，暂存到数组athis
10、.maxSize=this.length+t.getLength();this.chars=new charthis.maxSize;/恢复当前串的原始状态恢复当前串的原始状态 for(int i=0;it.getLength();i+)this.charsthis.length=t.charsi;this.length+;for(int i=0;ia.length;i+)this.charsi=ai;char a=new charthis.length;for(int i=0;i=this.length)return null;string a=new string(len);for(int
11、 i=0;ilen;i+)a.charsi=this.charspos+i;a.length+;return a;从位置从位置pospos开始不存开始不存在长度为在长度为lenlen的子串的子串【算法算法4-5】复制串复制串public void copy(string t)/将串将串t复制给当前串复制给当前串if(this.maxSizet.maxSize)this.maxSize=t.maxSize;this.chars=new charthis.maxSize;this.length=0;/初始化当前串的长度初始化当前串的长度for(int i=0;it.getLength();i+)t
12、his.charsi=t.charsi;this.length+;当前串无法容纳当前串无法容纳t t的的内容，需扩充容量内容，需扩充容量u 4.3.2 模式匹配模式匹配 在当前串中寻找某个子串的过程称为在当前串中寻找某个子串的过程称为模式匹配模式匹配，其中该子串称为其中该子串称为模式串模式串。朴素的模式匹配算法朴素的模式匹配算法 例如例如,设目标串设目标串s=“cddcdc”,模式串模式串t=“cdc”。s的长度的长度为为n(n=6),t的长度为的长度为m(m=3)。用指针。用指针i指示目标串指示目标串s的当的当前比较字符位置前比较字符位置,用指针用指针j指示模式串指示模式串t的当前比较字符的
13、当前比较字符位置，匹配过程如下所示：位置，匹配过程如下所示：又如当前串又如当前串S=“ababcabcacbab”，子串，子串t=“abcac”，则串的模式匹配操作如下图所示：，则串的模式匹配操作如下图所示：设串设串S长度为长度为n，串，串T长度为长度为m，在匹配成功的情况下，在匹配成功的情况下，考虑两种极端情况：考虑两种极端情况：在最好情况下在最好情况下，每趟不成功的匹配都发生在串，每趟不成功的匹配都发生在串T的的第一个字符。第一个字符。平均的比较次数是：平均的比较次数是：n+m即最好情况下的即最好情况下的时间复杂度是时间复杂度是O(n+m)。在最坏情况下在最坏情况下，每趟不成功的匹配都发生
14、在串，每趟不成功的匹配都发生在串T的的最后一个字符。最后一个字符。平均比较的次数是：平均比较的次数是：m（n-m+1）一般情况下，一般情况下，m n，因此最坏情况下的，因此最坏情况下的时间复杂度时间复杂度是是O(nm)。【算法算法4-】串的模式匹配算法串的模式匹配算法public int index(string t)if(this.length t.getLength()return-1;int a=-1;for(int i=0;i this.length;i+)int j=0;/在当前串中从位置在当前串中从位置i开始查找子串开始查找子串tif(j=t.getLength()a=i;brea
15、k;return a;while(jt.getLength()&this.charsi+j=t.charsj)if(this.charsi+j!=t.charsj)break;j+;4.3 矩矩阵阵u4.3.1 特殊矩阵特殊矩阵1对称矩阵对称矩阵若若n阶矩阵阶矩阵A中的元素满足下述性质：中的元素满足下述性质：aij=aji 1i,jn ，则称，则称A为为n阶对称矩阵。阶对称矩阵。图图4-5 4-5 一个一个5*55*5对称矩阵对称矩阵对称矩阵关于对称矩阵关于主对角线对称主对角线对称压缩存储压缩存储可将可将n2个元素压缩存储到个元素压缩存储到n(n+1)/2个元素的空间中。个元素的空间中。按行优
16、先存储到数组按行优先存储到数组SAk中，此时，中，此时，A11存入存入SA0，A21存入存入SA1，A22存入存入SA2，Aij存入存入SAk。sk与与aij的对应关系为：的对应关系为：0 1 2 3 40 1 2 3 4 2三角矩阵三角矩阵下三角矩阵下三角矩阵压缩存储压缩存储共存储了共存储了n(n+1)/2+1个元个元 素素,任一元素任一元素a aij在在SASA中的下标中的下标k k与与i i、j j的对应关系为：的对应关系为：主对角线以上主对角线以上均为常数均为常数c c2三角矩阵三角矩阵上三角矩阵上三角矩阵压缩存储压缩存储共存储了共存储了n(n+1)/2+1个元个元 素素,任一元素任一
17、元素a aij在在SASA中的下标中的下标k k与与i i、j j的对应关系为：的对应关系为：主对角线以下主对角线以下均为常数均为常数c cu4.3.2 稀疏矩阵稀疏矩阵假设假设m行行n列的矩阵含列的矩阵含t个非零元素，则非零元素的个非零元素，则非零元素的比例比例=t/(mn)称为称为稀疏因子稀疏因子，通常认为，通常认为0.05的的矩阵为矩阵为稀疏矩阵稀疏矩阵。含有大量零元素，非含有大量零元素，非零元素很少，且零元零元素很少，且零元素分布没有规律。素分布没有规律。l若以常规方法，即以二维数组表示，则若以常规方法，即以二维数组表示，则:1)1)零值元素占的空间很大零值元素占的空间很大;2)2)计
18、算中进行了很多和零值的运算计算中进行了很多和零值的运算;稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵稀疏矩阵三元组表三元组表行数行数列数列数元素值元素值按照行优先次序存放按照行优先次序存放class Triple /定义三元组定义三元组public int x;public int y;private double value;public Triple(int x,int y,double data)this.x=x;this.y=y;this.value=data;public double getData()return data;采用三元组表结构的稀疏矩阵用采用三元组表结构的稀疏矩阵用
19、JavaJava语言描述如下：语言描述如下：class SparseMatrix /定义稀疏矩阵定义稀疏矩阵 public Triple datas;/三元组表三元组表 public SparseMatrix(int rows,int cols,int length)if(length1)datas=new Triple1;datas0=new Triple(0,0,0);elsedatas=new Triplelength+1;datas0=new Triple(rows,cols,length);4.4 广广义义表表u4.4.1 广义表的逻辑结构广义表的逻辑结构广义表广义表广义表广义表是是
20、是是n1n1个元素个元素个元素个元素 a a1 1,a,a1 1,a,an n 的有限序列，其中的有限序列，其中的有限序列，其中的有限序列，其中每一个每一个每一个每一个a ai i 或者是或者是或者是或者是原子原子原子原子，或者是一个，或者是一个，或者是一个，或者是一个子表子表子表子表。单个元素单个元素 表头表头：若若 LS 非空非空(n1)，则，则第一个第一个元素元素 a1 就是表头。就是表头。记作记作 Head(LS)=a1。注：注：注：注：表头可是原子，也可是子表。表头可是原子，也可是子表。表尾表尾：除表头之外的除表头之外的其它元素其它元素组成的组成的表表。记作记作 Tail(LS)=(
21、a2,.,an)注：注：注：注：表尾不是最后一个元素，而是一个子表。表尾不是最后一个元素，而是一个子表。(1)A=()例例：空表，长度为空表，长度为 0，深度为，深度为1(2)B=(e)(3)C=(a,(b,c,d)长度为长度为 1，深度为，深度为1，表头为，表头为e、表尾为、表尾为()长长度度为为 2，深深度度为为2，由由原原子子 a 和和子子表表(b,c,d)构成，表头为构成，表头为 a；表尾为；表尾为(b,c,d)。(4)D=(A,B,C)长度为长度为 3，每一项都是子表。将子表代入，每一项都是子表。将子表代入D，即，即D=()，(e)，(a，(b，c，d)，深，深度为度为3，表头为，表
22、头为 A；表尾为；表尾为(B,C)。(5)E=(a,E)长度为长度为 2，这是一个递归的广义表。，这是一个递归的广义表。表头为表头为 a；表尾为；表尾为(E)。深度为无穷值。深度为无穷值 广义表的性质广义表的性质(1)广义表中的数据元素有相对广义表中的数据元素有相对次序次序次序次序；(2)广义表的广义表的长度长度长度长度定义为最外层所包含元素的个定义为最外层所包含元素的个数；如：数；如：C=(a,(b,c)是长度为是长度为 2 的广义表。的广义表。(3)广义表的广义表的深度深度深度深度定义为该广义表定义为该广义表展开后展开后所含所含括号括号的重数的重数；A=(b,c)的深度为的深度为 1，B=
23、(A,d)的深的深度为度为 2，C=(f,B,h)的深度为的深度为 3。注意注意注意注意:广义表广义表()和和()不同，前者为空表，长度为不同，前者为空表，长度为0；后者长度为后者长度为1，可分解得到表头和表尾均为空表，可分解得到表头和表尾均为空表()。(4)广义表可以为其他广义表广义表可以为其他广义表共享共享共享共享；如：广义表；如：广义表 D 就共享表就共享表 A、B、C。在。在 D中不必列出中不必列出 A、B、C的值，而是通过名称来引用。的值，而是通过名称来引用。(5)广义表可以是广义表可以是递归递归递归递归的表。的表。如：如：E=(a,E)=(a,(a,(a,)注意：注意：注意：注意：
24、递归表的深度是无穷值，长度是有限值递归表的深度是无穷值，长度是有限值。(6)广义表是广义表是多层次多层次多层次多层次结构，广义表的元素可以是单元素，结构，广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，也可以是子表，而子表的元素还可以是子表，。可以用图形象地表示。可以用图形象地表示。例：例：D=(E,F)其中其中：E=(a,(b,c)F=(d,(e)DadbceEFu4.4.2 广义表的存储结构及实现广义表的存储结构及实现由于广义表是递归定义的由于广义表是递归定义的 其元素可具有不同的结构其元素可具有不同的结构 （原子或列表）（原子或列表）用顺序存储结构表示用顺序存储结构表示
25、 采用链式存储结构采用链式存储结构 指向指向表头表头结结点的指针点的指针指向指向表尾表尾结结点的指针点的指针存放单元素存放单元素的数据域的数据域如如如如 LS=(a,(x,y),(z)LS=(a,(x,y),(z)，其存储结构如下图所示：，其存储结构如下图所示：，其存储结构如下图所示：，其存储结构如下图所示：图图4-12 广义表的存储结构示例广义表的存储结构示例4.5 串的串的应应用：文本用：文本编辑编辑文本格式示例，文本格式示例，“n”“n”为换行符为换行符把页、段和行看作文本的子串并建立页表和段表来辅把页、段和行看作文本的子串并建立页表和段表来辅助各子串的操作，从而实现文本处理。助各子串的
26、操作，从而实现文本处理。class Pagepublic int id;/页号页号public int start;/该页首字符在串中的编号该页首字符在串中的编号public int end;/该页末字符在串中的编号该页末字符在串中的编号public Page next;/下一页指针下一页指针public Page(int id,int start)this.id=id;this.start=start;this.end=start;this.next=null;页结点的存储结构用页结点的存储结构用JavaJava语言描述如下：语言描述如下：class Paragraphpublic int
27、id;/自然段编号自然段编号public int pageid;/该自然段所属页的编号该自然段所属页的编号public int start;/该段首字符在串中的编号该段首字符在串中的编号public int end;/该段末字符在串中的编号该段末字符在串中的编号public int length;/本自然段的字符个数本自然段的字符个数public Paragraph next;/下一自然段的指针下一自然段的指针public Paragraph(int id,int page,int start)this.id=id;this.pageid=page;this.start=start;this.
28、end=start;this.length=0;段结点的存储结构用段结点的存储结构用Java语言描述如下：语言描述如下：class Text public string contents;/由字符序列组成的串由字符序列组成的串public int length;/文本的总长度文本的总长度public int pages;/页数页数public int paras;/自然段总数自然段总数public Page pageTable;/页表，单向链表页表，单向链表public Paragraph paraTable;/自然段单向链表自然段单向链表public int currentPage;/当前页
29、的编号当前页的编号public int currentPara;/当前自然段的编号当前自然段的编号public int current;/当前字符在串中的编号当前字符在串中的编号public int rowsPerPage;/每页的字符行数每页的字符行数public int colsPerRow;/每行的字符数每行的字符数public Text(int maxSize)/省略部分代码省略部分代码完整的文本串的存储结构用完整的文本串的存储结构用Java语言描述如下：语言描述如下：文本编辑的基本操作是文本查找、添加、替换、删文本编辑的基本操作是文本查找、添加、替换、删除、复制、移动等。这些操作可直
30、接调用串的操作来完除、复制、移动等。这些操作可直接调用串的操作来完成。但文本编辑不是简单的串操作，文本添加与删除往成。但文本编辑不是简单的串操作，文本添加与删除往往会造成自然段的调整、页的调整。因此，文本编辑还往会造成自然段的调整、页的调整。因此，文本编辑还必须在串操作的基础之上增加以下操作：必须在串操作的基础之上增加以下操作：1、有关页的基本操作、有关页的基本操作 2、有关段的基本操作、有关段的基本操作建议读者先实现单行文本编辑操作，在具备有关串的建议读者先实现单行文本编辑操作，在具备有关串的基本编程能力之后实现多行文本编辑操作或分页和分基本编程能力之后实现多行文本编辑操作或分页和分段的文本
31、编辑。段的文本编辑。4.6 矩矩阵阵的的应应用：矩用：矩阵阵运算与运算与实现实现【实例实例4-1】u4.6.1 矩阵运算的意义矩阵运算的意义M*N每个季度的每个季度的原料总成本原料总成本每个季度的支付每个季度的支付工资总成本工资总成本每个季度的管理每个季度的管理及其他总成本及其他总成本u4.6.2 矩阵的加法矩阵的加法如果如果A A、B B是两个同型矩阵，它们具有是两个同型矩阵，它们具有相同的行数相同的行数和列数和列数，那么，那么A A和和B B可以相加，且可以相加，且A+BA+B的元素为的元素为A A 和和B B对应元素的和，即：对应元素的和，即：A+B=(aA+B=(aij ij+b+bi
32、j ij)。矩阵的加法满足下列运算律：矩阵的加法满足下列运算律：（1）交换律：）交换律：A+B=B+A；（2）结合律：）结合律：A+(B+C)=(A+B)+C；（3）存在零元：）存在零元：A+0=0+A=A；（4）存在负元：）存在负元：A+(-A)=(-A)+A=0。例如，普通矩阵的相加如下：例如，普通矩阵的相加如下：而对应的三元组表结构的相加如下图所示而对应的三元组表结构的相加如下图所示：两个三元组表结构的稀疏矩阵相加的算法如下：两个三元组表结构的稀疏矩阵相加的算法如下：（1）分别从矩阵）分别从矩阵A、B中取中取ak和和bk，如果两个，如果两个元素的元素的行、列位置相同行、列位置相同，执行，
33、执行k.value+bk.value同时在新矩阵中增加同时在新矩阵中增加1个新元素。个新元素。（2）否则，按）否则，按行优先的次序插入行优先的次序插入，若，若ak.ibk.i，则先插入，则先插入ak，否则先插入，否则先插入bk。（3）重复第（）重复第（1）和第（）和第（2）步，直到矩阵）步，直到矩阵A、B的的元素取完为止。元素取完为止。（4）新矩阵中新增加的元素总数就是稀疏矩阵）新矩阵中新增加的元素总数就是稀疏矩阵A+B之后的非零元素的个数。之后的非零元素的个数。u4.6.3 矩阵的乘法矩阵的乘法两个矩阵相乘，只有当两个矩阵相乘，只有当第一个矩阵的列数第一个矩阵的列数与与第二个第二个矩阵的行数
34、矩阵的行数相等相等时才有意义。时才有意义。矩阵的乘法满足下列运算律：矩阵的乘法满足下列运算律：（1）结合律：）结合律：（2）做分配律：）做分配律：（3）右分配律：）右分配律：（4）数与矩阵乘法的结合律：）数与矩阵乘法的结合律：（5）单位元的存在性：）单位元的存在性：例如：例如：一个一个2行行2列的矩阵乘以列的矩阵乘以2行行3列的矩阵，其列的矩阵，其结果是一个结果是一个2行行3列的矩阵。列的矩阵。其中，结果矩阵的第二行其中，结果矩阵的第二行(i)第二列第二列(j)的数字的数字4=2（第一个矩阵第二（第一个矩阵第二(i)行第一列）行第一列）2（第二个矩阵（第二个矩阵中第一行第二中第一行第二(j)列
35、）列）+0（第一个矩阵第二（第一个矩阵第二(i)行第二列）行第二列）1（第二个矩（第二个矩阵中第二行第二阵中第二行第二(j)列）。列）。u4.6.4 矩阵的转置矩阵的转置矩阵的转置运算满足下列运算律：矩阵的转置运算满足下列运算律：转置转置本章小结本章小结 3、在当前串中寻找某个子串的过程称为、在当前串中寻找某个子串的过程称为模式匹配模式匹配，其，其中该子串称为中该子串称为模式串模式串。1、串串的的逻辑结构和线性表很相似逻辑结构和线性表很相似，区别仅在于串的数，区别仅在于串的数据据对象约束为字符集对象约束为字符集，而线性表的数据对象则不限。，而线性表的数据对象则不限。2、串的基本操作串的基本操作
36、中，通常针中，通常针对某个子串进行操作对某个子串进行操作，例，例如查找某个子串、在串的某个位置插入一个子串或删除如查找某个子串、在串的某个位置插入一个子串或删除一个子串等等。一个子串等等。5、对称矩阵、三角矩阵采用、对称矩阵、三角矩阵采用压缩存储压缩存储的方式节约存储的方式节约存储空间。空间。7、广义表是一种特殊的有限序列，其数据元素可以是、广义表是一种特殊的有限序列，其数据元素可以是单个数据（单元素，又称原子），也可以是一个广义表单个数据（单元素，又称原子），也可以是一个广义表（子表）。（子表）。6、稀疏矩阵稀疏矩阵每个非零元素就可以表示为一个三元组（每个非零元素就可以表示为一个三元组（i，j，aij），将三元组按行或列优先的顺序，如按行优），将三元组按行或列优先的顺序，如按行优先，同一行中列号从小到大的规律排列成一个线性表，先，同一行中列号从小到大的规律排列成一个线性表，称为称为三元组表三元组表。