顺序串
《数据结构C++描述》 清华大学出版社 任燕编著小弟改了程序中的一个bug，看来数据结构还是要自己来运行一下，不能光看不练啊
#include <iostream>
#include <assert.h>
using namespace std;
class SqString{
public:
//把顺序串置空
void clear();
//获取第i个字符
bool getChar(int i, char &c);
//求顺序串的长度
int getLength();
//求模式串的next数组
void get_next(int *next, int display = 1);
//串的朴素匹配(有回溯查找)
int index(SqString p, int pos);
//模式匹配(无回溯KMP查找)
int index_KMP(SqString p, int pos);
//在第i个字符前插入另一个字符串
bool insert(int i, SqString t);
//判断顺序串是否为空
bool isEmpty();
//重载赋值运算符 char类型字符串
SqString operator=(char *s);
//重载赋值运算符SqString类型顺序串
SqString operator=(SqString s);
//重载加法运算符 被加是char类型
SqString operator+(char* s);
//重载加法运算符 SqString类型顺序串
SqString operator+(SqString s);
//重载是否小于运算符SqString类型
bool operator <(SqString s);
//重载是否相等运算符char
int operator ==(char *s);
//重载是否相等运算符 SqString
int operator==(SqString s);
protected:
//把char类型的顺序串赋值给当前顺序串的赋值函数
void strAssign_aux(char *s);
public:
//删除第i个字符起的长度为len的子串
bool strDelete(int i, int len);
//取顺序串的子串
bool subString(SqString& sub, int i, int len);
SqString();
virtual ~SqString();
SqString(char* s);
SqString(SqString &s);
//重载输出函数
friend ostream& operator <<(ostream& out, SqString s);
protected:
int length;//顺序串长度
char *ch;//顺序串动态存储空间的首地址
};
void SqString::clear(){
if (ch){
delete[]ch;
ch = NULL;
length = 0;
}
}
bool SqString::getChar(int i, char &c){
if (i<1 || i>length){
return false;
}
c = ch;
return true;
}
int SqString::getLength(){
return length;
}
void SqString::get_next(int *next, int display){
int j = -1, i = 0;//前后字符指针，初始化为-1和0
int first_i;//当前组第一个元素的下标
char no = "[ i]";
//生成next数组每个元素的值
next = -1;//-1为终止标志
while (i < length){
if (j == -1 || ch == ch){
j++;
i++;
next = j;
}
else{
j = next;
}
}
if (display == 1){
cout << " 当前模式串的next[]数组为:" << endl;
first_i = 0;
while (first_i < length){
i = first_i;
cout << " ";
do{
//修正元素下标的字符表示
if (i < 10){
no = i + '0';//数组中元素的小标小于10
}
else{
no = i / 10 + '0';//数组中元素的下标大于等于10
no = i % 10 + '0';
}
//每个元素的序号显示占5个字符，不足以空格补齐，靠右对齐
cout.width(5);
cout.fill(' ');
cout.setf(ios::right, ios::adjustfield);
cout << no;
i++;
} while (i % 10 && i < length);
cout << endl;
cout << " ";//显示模式串中的字符
i = first_i;
do{
cout.width(5);
cout.fill(' ');
cout.setf(ios::right, ios::adjustfield);
cout << ch;
i++;
} while (i % 10 && i < length);
cout << endl;
//显示next[]数组中每个元素的值
cout << " ";
i = first_i;
do{
cout.width(5);
cout.fill(' ');
cout.setf(ios::right, ios::adjustfield);
cout << ch;
i++;
} while (i % 10 && i < length);
first_i = i;//下一组第一个元素的下标
cout << endl << endl;
}
}
}
//朴素查找
int SqString::index(SqString p, int pos){
int i = pos - 1;//指向第pos个字符的下标
int j = 0;
while (i < length && j < p.length){
if (ch == p.ch){
i++;
j++;
}
else{//下标的重置
i = i - j + 1;
j = 0;
}
}
if (j == p.length){
return i - p.length + 1;//找到了
}
else{
return 0;//没找到
}
}
//KMP查找
int SqString::index_KMP(SqString p, int pos){
int i = pos - 1;
int j = -1;//模式串当前字符，初始化为-1，就是没有指向
int *next;
next = new int;
assert(next != 0);
p.get_next(next, 0);//求模式串的next函数的数组
//从主串的第pos个字符开始，与模式串的对应字符逐一比较
while (i < length && j < p.length){
if (j == -1 || ch == p.ch){
i++;
j++;
}
else{
j = next;//重置，无回溯
}
}
if (j == p.length){
return i - p.length + 1;//找到了
}
else{
return 0;//没找到
}
}
bool SqString::insert(int i, SqString t){
char *temp;
if (i<1 || i>length || t.isEmpty()){
return false;
}
temp = new char;
assert(temp != 0);
//其实这里感觉用指针也是比较方便
int j;
for (j = 0; j < i - 1; j++){
temp = ch;
}
for (; j < i - 1 + t.length; j++){
temp = t.ch;
}
for (; j < length + t.length; j++){
temp = ch;
}
delete[]ch;
ch = temp;
length = length + t.length;
return true;
}
bool SqString::isEmpty(){
return length ? false : true;
}
SqString SqString::operator=(char *s){
strAssign_aux(s);//赋值辅助函数
return *this;
}
SqString SqString::operator =(SqString right){
if (this != &right){
clear();
ch = new char;
assert(ch != 0);
length = right.length;
for (int i = 0; i < right.length; i++){
ch = right.ch;
}
}
return *this;
}
SqString SqString::operator +(char* s){
insert(length + 1, s);//调用insert函数
return *this;
}
SqString SqString::operator +(SqString right){
insert(length + 1, right);
return *this;
}
bool SqString::operator <(SqString right){
int i;
for (i = 0; i < length && i < right.length; i++){
if (ch < right.ch){
return true;
}
}
if (i < right.length){
return true;
}
else{
return false;
}
}
int SqString::operator ==(char *s){
int s_length;//获取s的长度
for (int i = 0; s; i++){
s_length = i;
}
for (int i = 0; i < length&&i < s_length; i++){
if (ch != s){
return ch - s;
}
}
return length - s_length;
}
int SqString::operator ==(SqString right){
for (int i = 0; i < length&&i < right.length; i++){
if (ch != right.ch){
return ch - right.ch;
}
}
return length - right.length;
}
//赋值辅助函数
void SqString::strAssign_aux(char *s){
clear();
length = 0;
for (int i = 0; s; ++i){
length++;
}
cout << length << endl;
ch = new char;
assert(ch != 0);
for (int i = 0; i < length; i++){
ch = s;
}
}
//删除第i个字符起长度为len的字符串
bool SqString::strDelete(int i, int len){
char *temp;
if (i<1 || i>length + 1){
return false;
}
temp = new char;
assert(temp != 0);
for (int j = 0; j < i - 1; j++){//前半段
temp = ch;
}
for (int j = i - 1 + len; j < length; j++){//后半段
temp = ch;
}
delete[]ch;
ch = temp;
length -= len;
return true;
}
//取子串
bool SqString::subString(SqString &sub, int i, int len){
if (i<1 || i>length || len < 0 || len>length - i + 1){
return false;
}
sub.clear();
sub.ch = new char;
assert(sub.ch != 0);
for (int j = 0; j < len; j++){
sub.ch = ch;
}
sub.length = len;
return true;
}
//构造函数
SqString::SqString(){
ch = NULL;
length = 0;
}
SqString::~SqString(){
clear();
}
//拷贝构造函数char类型
SqString::SqString(char *s){
ch = NULL;
strAssign_aux(s);
}
//拷贝构造函数
SqString::SqString(SqString &other){
ch = new char;
assert(ch != 0);
length = other.length;
for (int i = 0; i < length; i++){
ch = other.ch;
}
}
ostream& operator<<(ostream& out, SqString s){
for (int i = 0; i < s.length; i++){
out << s.ch << "";
}
cout << endl;
return out;
}
int main(int argc, char* argv[]){
SqString s1("Hello World!");
cout << s1;
SqString s2("haha,welcome to the program world,Hello World!,enjoy it");
cout << s2;
cout << "回溯法查找:";
cout << s2.index(s1, 0) << endl;
cout << "KMP查找:";
cout << s2.index_KMP(s1, 0) << endl;
return 0;
}
页:
[1]