《数据结构与算法》第4章 串.pptVIP

* * * * * * * * * 串的应用——文本编辑 行号 起始地址 长度 200 301 8 201 309 13 202 322 21 203 343 9 204 352 14 205 366 2 串的应用——文本编辑 下面讨论3种文本编辑的操作。 （1）插入。把新插入的行存到文本的末尾，并按行号的次序把新行的行号、起始位置及该行字符串的长度信息插入到行表的合适位置。 （2）删除。把被删除行的行号、起始位置及该行字符串的长度信息从行表中删去（若存储空间较紧张，则应同时从内存中删去该行）。若被删除的行是所在页的起始行，则还要修改页表中相应页的起始行号（修改为下一行的行号）。 （3）修改。①若新行长小于等于原行长，则把新行字符串仍存于原行字符串的位置，并修改行表中该行子串的长度信息即可；②若新行长大于等于原行长，则把新行字符串存于文本末尾，即为该行重新分配存储空间（并可删去文本中的原行），并修改行表中该行的起始位置及行长信息。 本 章 总 结 学习要点 本章主要介绍串的基本概念、基本运算、静态存储结构与动态存储结构，以及基本操作的实现方法，串操作的综合应用程序设计。主要学习要点如下：① 串的逻辑结构定义和串的连接、求子串、定位、置换、插入、删除等基本运算的功能；② 串的静态存储和动态存储的基本思想和实现方法；③ 串操作在文本编辑、文本格式化处理中的应用。 本 章 总 结 基本要求 （1）深入领会串运算的定义和基本算法以及综合应用程序设计； （2）知道（字符）串的有关术语、逻辑结构、特点以及与线性表的区别； （3）弄清串的连接，求子串、模式匹配、置换等基本运算的功能，并能灵活应用串的这些基本运算； （4）弄清顺序串和链串紧缩格式的主要优缺点，非紧缩格式的优缺点； （5）了解串及其运算在文本编辑及文本格式化中的应用。 本 章 总 结 重点与难点 重点是：求子串、定位、置换基本运算（操作）的实现算法。难点是：串的综合应用程序设计。 * * * * * * * * * * * * * * * * * * * * * * * * * * * 数据结构与算法（C++语言版） 第4章 串 现实世界中的实体有多种形式，如数值、文字符号序列、图形、图像、声音等，其中文字（符号）序列称为字符串，简称串。串是一种常用的数据结构，用于描述非数值的简单信息，它在现实世界中屡见不鲜，如人名、产品名、事物名称、车牌号、文献、源程序等。从数据元素间的逻辑关系看，串是线性表，但从操作方式与种类看，它与线性表有许多不同。在计算机中，串被认为是一种特殊的线性表——元素为文字符号的线性表。由于现实问题中经常使用串，所以对串应选择合适的存储结构，并提供灵活多样的基本操作。 串的逻辑结构 基本概念 串（string）是由零个或多个字符构成的有限序列，一般记为s=‘s1s2…sn’（n≥0）。其中，s是串名，用单引号括起来的字符序列是串的值，但单引号本身并不属于串，si（1≤i≤n）为一个字符，字符是计算机可识别的任意符号（字母、数字或其他符号）。 串的长度：串中字符的数目n。 空串：零个字符的串，其长度为零。 空白串：由一个或多个空格组成的串，其长度为串中空格字符的个数。 子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串相应地称为主串。 串的逻辑结构 字符在串中的位置：字符在序列中的序号。 串相等：当且仅当这两个串的值相等，即两个串的长度相等，并且各个对应位置的字符都相等。 通常，在程序中使用的串可分为两类：串变量和串常量。串变量和其他类型的变量一样，其取值是可改变的。串常量和常数一样，在程序中只能被引用但不能改变其值，即只能读不能写。 例4-1 假设a、b、c、d为如下的4个串：a=‘Guang’，b=‘Zhou’，c=‘GuangZhou’，d=‘Guang Zhou’。它们的长度分别为5、4、9、10；并且a和b都是c和d的子串，a在c和d中的位置都是1，而b在c中的位置是6，在d中的位置是7；a、b、c、d彼此都不相等。 显然，若某串的长度为n，则在该串中，长度为1的子串的个数为n，长度为2的子串的个数为n?1，……，长度为i的子串的个数为n?(i?1)，所以长度为n的串中子串总数（包括空串与自身）为1+ =1+ 。串的抽象数据类型定义见以下ADT 。 例4-1 例4-1 例4-1 串的逻辑结构 串的大小比较 字符的大小 在计