符”的“字节”即是该字符的编码。 根据要表示的字符集的大小和用途,字符有多种编码方式。常用的编码包括英文的 ASCⅡ编码,中文的GB2312-80编码,繁体中文的BIG5编码,以及通用文字符号编码标准 UNICODE 授课时需强调字符编码方式的不同取决于具体的应用需要。字符串是一种元素为字符的 特殊的线性表,字符编码的不同仅仅表示组成线性表的元素不同,并不改变字符串概念和操 作的本质。 (2)字符串类 class String的存储结构 字符串的一个显著且难以回避的特点是其长度动态变化,选择串的存储结构时需要考虑 串的变长特点。静态长度的顺序存储很难适应诸如串的拼接、查找、置换等运算所导致的串 长度的改变 Class String类采用一种动态变长的存储结构来存储字符串,根据运算的需要动态地改 变字符串的长度,使得编程人员摆脱自己维护静态定长数组的重任。 讲授时宜采用字符串赋值或拼接等运算为例来介绍 class string类的存储机制。 (3)朴素字符串模式匹配算法 本课程中所涉及的字符串模式匹配仅限于精确匹配中的单选情况:给定一个由字符或符 号组成的字符串目标对象T和一个字符串模式P,模式匹配的目的是在目标字符串T中搜索 与模式P完全相同的子串,并返回T和P匹配的第一个子串的首字符位置。 模式匹配的一个简单方法就是把模式P的字符依次与目标T的相应字符进行比较。从 首字符开始,依次将两个串对应位置上的字符进行比较。当某次比较失败时,则把模式P 相对于T右移一个字符位置,重新开始下一趟匹配。如此不断重复,直到某趟配串成功返 回;或是比较到目标串的结束也没有出现“配串”的情况,则匹配失败。 授课时需引导学生分析朴素匹配算法的时间代价,并找出其最佳、最差、及平均情况下 的开销,同时引导学生分析和总结朴素算法之所以时间代价较大的症结所在,最好辅以实际 的匹配例子来说明,能够采用动画的话更好 (4)KMP算法中特征向量的含义与计算 朴素模式匹配算法存在的一个问题是,一旦某趟匹配中发生失配,无论模式的具体情况 如何,都采用模式右移一位的方式开始下一趟的匹配,这可能导致很多冗余的比较。 Knuth、 Morris、Prat!等人发现在模式匹配失配后,模式P相对于目标T应该右移的位数存在且与 目标串无关,仅依赖于模式本身,他们对朴素的模式匹配算法进行了改进得到了KMP算法 其基本思想为:预先处理模式本身,分析其字符分布状况,并为模式中的每一个字符计算失 配时应该右移的位数,这即为字符串的特征向量。 授课时须强调特征向量的计算过程本身即是一个模式匹配的过程,采用相同的匹配方 法。另外,应该着重介绍一下计算特征向量时的优化考虑,以帮助学生了解算法设计的精微 之处。建议采用图示或动画来辅助说明特征向量的计算。 6.课后练习和实习 作为教学的重要一环,课后练习和上机实习帮助学生巩固课堂所学理论知识,训练学生 创新思维能力训练、工程实践能力。 字符串部分可以安排4道书面作业,可酌情布置有关字符串的综合训练,以帮助学生充 分巩固课堂所学知识,课程网站上字符串综合训练题目如下: http://www.jpkpku.edu.cn/pkujpk/course/sug/report/hwtest/2007proj/plEdline/pl.doc符”的“字节”即是该字符的编码。 根据要表示的字符集的大小和用途，字符有多种编码方式。常用的编码包括英文的 ASCII 编码，中文的 GB2312-80 编码，繁体中文的 BIG5 编码，以及通用文字符号编码标准 UNICODE。 授课时需强调字符编码方式的不同取决于具体的应用需要。字符串是一种元素为字符的 特殊的线性表，字符编码的不同仅仅表示组成线性表的元素不同，并不改变字符串概念和操 作的本质。 （2）字符串类 class String 的存储结构 字符串的一个显著且难以回避的特点是其长度动态变化，选择串的存储结构时需要考虑 串的变长特点。静态长度的顺序存储很难适应诸如串的拼接、查找、置换等运算所导致的串 长度的改变。 Class String 类采用一种动态变长的存储结构来存储字符串，根据运算的需要动态地改 变字符串的长度，使得编程人员摆脱自己维护静态定长数组的重任。 讲授时宜采用字符串赋值或拼接等运算为例来介绍 class String 类的存储机制。 （3）朴素字符串模式匹配算法 本课程中所涉及的字符串模式匹配仅限于精确匹配中的单选情况：给定一个由字符或符 号组成的字符串目标对象 T 和一个字符串模式 P，模式匹配的目的是在目标字符串 T 中搜索 与模式 P 完全相同的子串，并返回 T 和 P 匹配的第一个子串的首字符位置。 模式匹配的一个简单方法就是把模式 P 的字符依次与目标 T 的相应字符进行比较。从 首字符开始，依次将两个串对应位置上的字符进行比较。当某次比较失败时，则把模式 P 相对于 T 右移一个字符位置，重新开始下一趟匹配。如此不断重复，直到某趟配串成功返 回；或是比较到目标串的结束也没有出现“配串”的情况，则匹配失败。 授课时需引导学生分析朴素匹配算法的时间代价，并找出其最佳、最差、及平均情况下 的开销，同时引导学生分析和总结朴素算法之所以时间代价较大的症结所在，最好辅以实际 的匹配例子来说明，能够采用动画的话更好。 （4）KMP 算法中特征向量的含义与计算 朴素模式匹配算法存在的一个问题是，一旦某趟匹配中发生失配，无论模式的具体情况 如何，都采用模式右移一位的方式开始下一趟的匹配，这可能导致很多冗余的比较。Knuth、 Morris、Pratt等人发现在模式匹配失配后，模式 P 相对于目标 T应该右移的位数存在且与 目标串无关，仅依赖于模式本身，他们对朴素的模式匹配算法进行了改进得到了KMP算法， 其基本思想为：预先处理模式本身，分析其字符分布状况，并为模式中的每一个字符计算失 配时应该右移的位数，这即为字符串的特征向量。 授课时须强调特征向量的计算过程本身即是一个模式匹配的过程，采用相同的匹配方 法。另外，应该着重介绍一下计算特征向量时的优化考虑，以帮助学生了解算法设计的精微 之处。建议采用图示或动画来辅助说明特征向量的计算。 6．课后练习和实习 作为教学的重要一环，课后练习和上机实习帮助学生巩固课堂所学理论知识，训练学生 创新思维能力训练、工程实践能力。 字符串部分可以安排 4 道书面作业，可酌情布置有关字符串的综合训练，以帮助学生充 分巩固课堂所学知识，课程网站上字符串综合训练题目如下： http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/report/HWTest/2007Proj/P1_Edline/P1.doc