数据结构-串（字符串）

// my_string.h
#ifndef MY_STRING_H
#define MY_STRING_H

#include <iostream>

using namespace std;

const int MAXSIZE=100;

class MyString
{
public:
    MyString(const MyString& copy);
    MyString(const char *init);
    MyString();
    ~MyString()
    {
        delete[] m_pstr;
    }
    int Length() const
    {
        return m_ncurlen;
    }
    int Find(MyString part) const;
    char* GetBuffer() const;
public:
    MyString& operator()(int pos, int len);
    bool operator==(const MyString cmp_str) const;
    bool operator!=(const MyString cmp_str) const;
    bool operator<(const MyString cmp_str) const;
    bool operator>(const MyString cmp_str) const;
    bool operator!() const
    {
        return (m_ncurlen == 0);
    }
    MyString& operator=(const MyString &copy);
    MyString& operator+=(const MyString &add);
    char& operator[](int i);
    friend ostream& operator<<(ostream&, MyString&);
    friend istream& operator>>(istream&, MyString&);
private:
    void Next();
private:
    char *m_pstr;
    int m_ncurlen;
    int *m_pnext;
};

#endif // MY_STRING_H

// my_string.cpp
#include "my_string.h"
#include <cstring>
#include <iostream>

using std::cout;
using std::endl;

MyString::MyString()
{
    m_pstr = new char[MAXSIZE];
    if(!m_pstr)
    {
        cerr << "Allocation Error" << endl;
        exit(1);
    }
    this->m_ncurlen = 0;
    m_pstr[0] = '\0';
}

MyString::MyString(const char *init)
{
    m_pstr = new char[MAXSIZE+1];
    if(!m_pstr)
    {
        cerr << "Allocation Error" << endl;
        exit(1);
    }
    this->m_ncurlen = strlen(init);
    strcpy(m_pstr, init);
}

MyString::MyString(const MyString &copy)
{
    m_pstr = new char[MAXSIZE];
    if(!m_pstr)
    {
        cerr << "Allocation Error" << endl;
        exit(1);
    }
    this->m_ncurlen = copy.m_ncurlen;
    strcpy(m_pstr, copy.m_pstr);
}

int MyString::Find(MyString part) const
{
    int posP = 0, posT = 0;
    int lengthP = part.m_ncurlen, lengthT = this->m_ncurlen;

    part.Next();
    while(posP < lengthP && posT < lengthT)
    {
        if(part.m_pstr[posP] == this->m_pstr[posT])
        {
            posP++;
            posT++;
        }
        else
        {
            if(posP == 0)
            {
                posT++;
            }
            else
            {
                posP = part.m_pnext[posP-1];
            }
        }
    }

    delete[] part.m_pnext;
    if(posP < lengthP)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}

void MyString::Next()
{
    int length = this->m_ncurlen;
    this->m_pnext = new int[length];
    this->m_pnext[0] = 0;
    for(int i = 1; i < length; i++)
    {
        int j = this->m_pnext[i-1];
        while(*(this->m_pstr+1) != *(this->m_pstr+j) && j > 0)
        {
            j = this->m_pnext[j-1];
        }
        if(*(this->m_pstr+i) == *(this->m_pstr+j))
        {
            this->m_pnext[i] = j + 1;
        }
        else
        {
            this->m_pnext[i] = 0;
        }
    }
}

char *MyString::GetBuffer() const
{
    return this->m_pstr;
}

MyString& MyString::operator()(int pos, int len)
{
    MyString *temp = new MyString;
    if(pos < 0 || pos + len - 1 > MAXSIZE || len < 0)
    {
        temp->m_ncurlen = 0;
        temp->m_pstr[0] = '\0';
    }
    else
    {
        if(pos+len-1 >= m_ncurlen)
        {
            len = m_ncurlen - pos;
        }
        temp->m_ncurlen = len;
        for(int i = 0, j = pos; i < len; i++, j++)
        {
            temp->m_pstr[i] = m_pstr[j];
        }
        temp->m_pstr[len] = '\0';
    }
    return *temp;
}

bool MyString::operator==(const MyString cmp_str) const
{
    if(this->m_ncurlen != cmp_str.m_ncurlen)
    {
        return 0;
    }
    for(int i = 0; i < this->m_ncurlen; i++)
    {
        if(this->m_pstr[i] != cmp_str.m_pstr[i])
        {
            return 0;
        }
    }
    return 1;
}

bool MyString::operator!=(const MyString cmp_str) const
{
    if(*this == cmp_str)
    {
        return 0;
    }
    return 1;
}

bool MyString::operator<(const MyString cmp_str) const
{
    if(this->m_ncurlen != cmp_str.m_ncurlen)
    {
        return this->m_ncurlen < cmp_str.m_ncurlen;
    }
    for(int i = 0; i < this->m_ncurlen; i++)
    {
        if(this->m_pstr[i] != cmp_str.m_pstr[i])
        {
            return this->m_pnext[i] < cmp_str.m_pnext[i];
        }
    }
}

bool MyString::operator>(const MyString cmp_str) const
{
    if(*this < cmp_str || *this==cmp_str)
    {
        return 0;
    }
    return 1;
}

MyString& MyString::operator=(const MyString &copy)
{
    delete[] this->m_pstr;
    this->m_pstr = new char[copy.m_ncurlen];
    strcpy(this->m_pstr, copy.m_pstr);
    return (*this);
}

MyString& MyString::operator+=(const MyString &add)
{
    int length = this->m_ncurlen + add.m_ncurlen;
    int n = this->m_ncurlen;
    MyString temp(*this);
    delete[] this->m_pstr;
    this->m_pstr = new char[length+1];
    for(int i = 0; i < n; i++)
    {
        this->m_pstr[i] = temp[i];
    }
    for(int i = n; i < length; i++)
    {
        this->m_pstr[i] = add.m_pstr[i-n];
    }
    this->m_pstr[length] = '\0';
    return (*this);
}

char& MyString::operator[](int i)
{
    if(i<0 || i >= this->m_ncurlen)
    {
        cout << __FUNCTION__ << " error : out of boundary! " << endl;
        exit(1);
    }
    return this->m_pstr[i];
}

ostream& operator<<(ostream& os, MyString& str)
{
    os << str.m_pstr;
    return os;
}

istream& operator>>(istream& is, MyString& str)
{
    is >> str.m_pstr;
    return is;
}

// main.cpp
#include <iostream>
#include "my_string.h"

using namespace std;

int main(int argc, char *argv[])
{
    MyString test1("babc");
    MyString test2("abababcdefb");
    cout << test2.Find(test1) << endl;
    cout << test2(2, 3) << endl;
    if(test1 < test2)
    {
        cout << test1 << " < " << test2 << endl;
    }
    else
    {
        if(test1 == test2)
        {
            cout << test1 << " == " << test2 << endl;
        }
        else
        {
            if(test1 > test2)
            {
                cout << test1 << " > " << test2 << endl;
            }
        }
    }

    int length = test2.Length();
    for(int i = 0; i < length; i++)
    {
        cout << test2[i];
    }
    cout << endl;

    test1 += test2;
    cout << test1 << endl;

    test1 = test2;
    cout << test1 << endl;
    return 0;
}