数据结构（Java语言描述）第四章 串、矩阵和广义表.pptx

第四章 串、矩阵和广义表;目录;总体要求;4.1 串及其运算;4.1.2 串的基本操作;子串：由串中任意个连续的字符组成的子序列。 ;串复制：将某个串复制给当前串 串连接：将串S1和S2联接而成一个新串 串替换：用子串x替换当前串中的子串y 插入子串：将子串插到当前串中的某个位置 删除子串：从当前串中删除指定子串 大写转小写：将串中的大写字母转化为对应小写字符 小写转大写：将串中的小写字母转化为对应大写字符 串压缩：将当前串中首部和尾部的所有空格删除;4.2 串的顺序存储与实现;4.2.2 串的实现;;【算法4-2】串比较;【算法4-3】串连接;【算法4-4】求子串;【算法4-5】复制串; 4.3.2 模式匹配;又如当前串S = “ababcabcacbab”，子串t = “abcac”，则串的模式匹配操作如下图所示：;【算法4-６】串的模式匹配算法;最好情况：不成功的匹配都发生在串t的第一个字符;最坏情况:不成功的匹配都发生在串t的最后一个字符;为什么简单匹配算法时间性能低？ 在每趟匹配不成功时存在大量回溯，没有利用已经部分匹配的结果。 如何在匹配不成功时主串不回溯？ 主串不回溯，模式就需要向右滑动一段距离。 如何确定模式的滑动距离？;KMP算法;4.3 矩阵;可将n2个元素压缩存储到n×(n+1)/2个元素的空间中。按行优先存储到数组SA[k]中，此时，A11存入SA0，A21存入SA1，A22存入SA2，……，Aij存入SAk。SAK与Aij的对应关系为：;;;4.3.2 稀疏矩阵;稀疏矩阵的压缩存储;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 value; } };class SparseMatrix //定义稀疏矩阵 { public Triple[] datas; //三元组表 public SparseMatrix(int rows,int cols, int length) { if(length1){ datas = new Triple[1]; datas[0] = new Triple(0,0,0); } else{ datas = new Triple[length+1]; datas[0] = new Triple(rows,cols,length); } } };4.4 广义表;(1) A=( ) ;广义表的性质 ;广义表可以为其他广义表共享；如：广义表 D 就共享表 A、B、C。在 D中不必列出 A、B、C的值，而是通过名称来引用。 ;广义表是多层次??构，广义表的元素可以是单元素， 也可以是子表，而子表的元素还可以是子表，…。 可以用图形象地表示。 ;4.4.2 广义表的存储结构及实现;如 LS=(a,(x,y),((z)))，其存储结构如下图所示：;4.5 串的应用：文本编辑;把页、段和行看作文本的子串并建立页表和段表来辅助各子串的操作，从而实现文本处理。;class Paragraph { public int 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.end = start; this.length=0; } };class Text { public string contents; //由字符序列组成的串 public int length; //文本的总长度 public int pages; //页数 public int paras;