第3讲堆栈、队列和字符串要点.ppt

void get_nextval(SString T, int nextval[]) { i = 1; nextval[1] = 0; j = 0; while (i T[0]) { if (j = 0 || T[i] == T[j]) { ++i; ++j; if (T[i] != T[j]) nextval[i] = j; else nextval[i] = nextval[j]; } else j = nextval[j]; } } // get_nextval 串C++实现 class String { public: // methods of the string ADT String(); ~String(); String (const String copy); // copy constructor String (const char * copy); // conversion from C-string String (Listchar copy); // conversion from List void operator =(const String copy); const char *c_str() const; // conversion to C-style string protected: char *entries; int length; }; 串比较运算符重载 bool operator ==(const String first, const String second); bool operator (const String first, const String second); bool operator (const String first, const String second); bool operator =(const String first, const String second); bool operator =(const String first, const String second); bool operator !=(const String first, const String second); 串构造函数(1) String::String (const char *in_string) { length = strlen (in_string); entries = new char[length + 1]; strcpy (entries, in_string); } 串构造函数 String::String (Listchar in_list) { length = in_list.size(); entries = new char[length + 1]; for (int i = 0; i length; i++) in_list.retrieve(i,entries[i]); entries[length] = \0; } 将C++串转换为C语言串 const char*String::c_str() const /* Post: A pointer to a legal C-string object matching the String is returned. */ { return (const char *) entries; } 串比较实现 bool operator ==(const String first, const String second) { return strcmp(first.c_str(), second.c_str()) == 0; } bool operator (const String first, const String second) { return strcmp(first.c_str(), second.c_str()) 0; } 进一步串操作示例(1) void strcat(String add_to, const String add_on) { const char *cfirst = add_to.c_str(); c