数据结构教学课件-7 string.pptVIP

作业(5月20日交) P.134 3.29 (算法思路以及伪码) P.183 4.1 P.183 4.2 (注意下标是从1开始的） * * 清华大学数据结构教研组 * Lecture-7 09/05 字符串 C++中包含的C的基本字符串操作 字符串类 字符串的匹配 * * 字符串是 n ( ? 0 ) 个字符的有限序列， 记作 S : “c1c2c3…cn” 其中，S 是串名字 “c1c2c3…cn”是串值 ci 是串中字符 n 是串的长度，n = 0 称为空串。 例如, S = “Tsinghua University”。 注意：空串和空白串不同，例如 “ ” 和 “” 分别表示长度为1的空白串和长度为0的空串。 字符串 (String) * 串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。 通常将子串在主串中首次出现时，该子串首字符对应的主串中的序号，定义为子串在主串中的位置。例如，设A和B分别为 A = “This is a string” B = “is” 则 B 是 A 的子串，A 为主串。B 在 A 中出现了两次，首次出现所对应的主串位置是2（从0开始）。因此，称 B 在 A 中的位置为2。 特别地，空串是任意串的子串，任意串是其自身的子串。 * #ifndef ASTRING_H //定义在文件“Astring.h”中 #define ASTRING_H #define defaultSize = 128; //字符串的最大长度 class AString { //对象: 零个或多个字符的一个有限序列。 private: char *ch; //串存放数组 int curLength; //串的实际长度 int maxSize; //存放串的最大长度 public: 字符串的类定义 * AString(int sz = defaultSize); //构造函数 创建一个空串 AString(const char *init ); //构造函数从已有字符数组*init复制 AString(const AString ob); //复制构造函数从已有串ob复制 ～AString() {delete [ ]ch; } //析构函数 int Length() const { return curLength; } //求长度 Astring operator() (int pos, int len); //求子串 bool operator == (AString ob) const { return strcmp (ch, ob.ch) == 0; } //判串相等. 若串相等, 则函数返回true bool operator != (AString ob) const { return strcmp (ch, ob.ch) != 0; } //判串不等. 若串不相等, 则函数返回true * bool operator ! () const { return curLength == 0; } //判串空否。若串空, 则函数返回true AString operator = (AString ob); //串赋值 AString operator += (AString ob); //串连接 char operator [ ] (int i); //取第 i 个字符 int Find (AString pat, int k) const; //串匹配 }; 在此定义下ch[0]至ch[curLenghth-1]中存放的是当前字符串，ch[curLenghth]=‘\0’ 序 号 重载操作 操作 使用示例 (设使用操作的当前串为S：‘tsinghua’) 1 ( ) (int pos, int len) 取子串 S1 = S(3, 2), //S1结果为 ‘ng’ 2 == (const AString ob) 判两串 相等 S == S1 , //若S与S1相等, 结果为true，否则为false 3 != (const AString ob) 判两串 不等 S != S1 , //若S与S1不等， 结果为tr