数据结构----串

灰太狼 2022-07-12 08:16 183阅读 0赞

*前言*  
Try my best to do want i want to do.  
Time:2017/1/18  
name:Willam

**1、串的三种表示方式**

1.  定长顺序存储表示
2.  堆分配表示（比较倾向使用这种）
3.  链式存储表示

**2、完成实现串的基本操作的代码框架的构建（采用第二种表示方式来实现）**

class Mystring
    {
    private:
        char * data;
        int MAX_SIZE;
        int length;
        int step;
    public:
        Mystring();//无参构造函数
        Mystring(char *);//有参构造函数
        Mystring(const Mystring &);//拷贝构造函数
        void strassign(char *);//赋值函数，将之前的值全部删除，替换为新的值
        int strlength() const;//返回串的长度
        char * getdata() const;//返回串的内容
        int strcompare(const Mystring);//比较两个串的长度
        void clear();//释放内存，清空串的内容
        void concat(const  Mystring);//连接两个串的内容
        char * substring(int,int);//返回一个子串
        friend ostream & operator <<(ostream &,const Mystring &);////重载“<<
    };

**3、操作函数的实现**  
①Mystring()函数的实现：

Mystring::Mystring(){
        data=NULL;
        MAX_SIZE=1000;
        length=0;
        step=100;
    }

②Mystring（char \*）函数的实现

Mystring::Mystring(char * temp){
            //初始化MAX_SIZE和step
        MAX_SIZE=1000;
        step=100;
        int i=0;
        //得到temp字符串的长度（拖底程序效率的一个地方，写完尝试优化）
        while(temp[i++]!='\0');
        //如果串的长度，大于我们设定的最大的长度，那么就要对MAX_SIZE做一些修改        
        length=i-1;
        if(length>=MAX_SIZE){
            MAX_SIZE=length+step;
        }
            //为data开辟空间
        data=new char[MAX_SIZE];
            //为data赋值
        //data=temp;这种方法是错误的，虽然它可以很快捷的完成初始化，但是它只不过又重新为data定义了一个新的空间，这个空间就是temp开辟的空间
        for(i=0;i<=length;i++)
            data[i]=temp[i];
    
    }

③Mystring(const Mystring &)函数的实现

Mystring::Mystring(const Mystring & s)
    {
        //字符指指针的原理是：比如我们的data是指向存放那个串的第一个字符的内存地址，因为我们的串是存放的连续的内存地址的，并且是以“\0”结尾的，所以我们可以直接通过data来操作整个字符串，同时包括赋值。
        data=s.data;
        length=s.length;
        MAX_SIZE=s.MAX_SIZE;
        step=s.step;
    }

④void strassign(char \*)函数的实现

void Mystring::strassign(char * temp)
    {
        //对于这个函数，我们首先是要先把我们串之前的内容给清空，然后我们再为它重新赋值
        data=NULL;
        length=0;
        //同样是先得到temp串的长度
        int i=0;
        while(temp[i++]!='\0');
        length=i-1;
        if(length>=MAX_SIZE)
            MAX_SIZE=length+step;
        //为data开辟新的空间
        data=new char[MAX_SIZE];
         //为data赋值
        for(i=0;i<=length;i++)
            data[i]=temp[i];
    
    
    }

⑤int strlength() const;函数的实现  
*这里我首先解释一下const的含义：1、const函数不能修改其数据成员，2、const的成员 不能访问非const的函数，所以对于后面的strcompare函数，如果它的const形参需要访问这个函数，就要把这个函数声明为const函数*

//const是必须添加的，因为这个是STL的一个机制的问题，如果我们不添加const，在strcompare函数将会报错
    int Mystring::strlength()const
    {
        return length;
    }

⑥char \* getdata() const函数的实现

char * Mystring::getdata()const
    {
        return data;
    }

⑦int strcompare(const Mystring)函数的实现

int Mystring::strcompare(const Mystring s)
    {
        //如果比s的data大，则返回大于0，两者相等则返回0，小于则返回小于0的数
        char *d=s.getdata();
        int l=s.strlength();
        int i;
        for(i=0;i<length && i<l;i++)
            if(data[i]!=d[i])
                return data[i]-d[i];
        return data[i]-d[i];
    }

⑧void clear();函数的实现

void Mystring::clear(){
        length=0;
        delete data;
        data=NULL;
    }

⑨void concat(const Mystring);函数的实现

void Mystring::concat(const Mystring s){
        int total=length+s.strlength();
        int l=s.strlength();
        int i=0;
        //如果data的空间不足以存放两个串的内容，所以我们需要为它重新开辟一个更大的空间
        if(MAX_SIZE<(total+1))
        {
            char *temp=data;
            MAX_SIZE=total+step;
            data=new char[MAX_SIZE];
            for(i=0;i<=length;i++)
            {
                data[i]=temp[i];
            }
            delete temp;
            temp=NULL;
        }
        else{
            i=length;//尾巴添加串的位置
        }
    
    
        //把s的串接在data的尾部
        char * t=s.getdata();
        for(int j=0;j<=l;j++){
            data[i++]=t[j];
        }
    }

⑩char \* substring(int,int);函数的实现

//假设下标从1开始，start为想要的字串开始的为位置，而l为其长度
    char * Mystring::substring(int start,int l)
    {
        char * temp;
        //判断你想要的子串的起点是否合法
        if(start<1 || start>length)
        {
            cout<<"你输入的起始位置不合法"<<endl;
            return NULL;
        }
        //为我们的临时字符串数组开辟足够大的空间
        temp=new char[l+1];
        //j为temp的下标，i为data的下标
        int j=0;
        int i=start-1;
        //为temp赋值
        for(j=0;j<l && i<length;j++,i++)
        {
            temp[j]=data[i];
        }
        //为temp字符数组添加一个结尾符号
        temp[j]='\0';
        return temp;
    }

⑪friend ostream & operator <<(ostream &,const Mystring &);函数的实现

//重载了“<<”这个运算符，而且是通过友元函数的方式来重载的，所以在使用是可以直接：cout<<类对象名，通过这种格式来输出串的内容。
    ostream & operator << (ostream & out,const Mystring & s)
    {
        out<<s.data<<endl;
        return out;//返回输出流
    }

在运算符重载的中，有两种重载方式：友元函数重载和成员函数重载，但是一般我们都是使用友元函数重载，除了几个必须要使用成员函数重载的。具体可以看我之前的博客：[运算符重载介绍][Link 1]

**3、代码整合与总结**  
我是在Linux下跑我的代码的，所以我采用的新建一个工程的方式来实现我的代码，它包括了四个文件：string.h、string.c、main.c、makefile;

**string.h文件的内容**

#ifndef STR_H
    #define STR_H
    
    #include<iostream>
    using namespace  std;
    class Mystring
    {
    private:
            char * data;
        int MAX_SIZE;
        int length;
        int step;
     public:
        Mystring();//无参构造函数
        Mystring(char *);//有参构造函数
        Mystring(const Mystring &);//拷贝构造函数
        void strassign(char *);//赋值函数，将之前的值全部删除，替换为新的值
        int strlength() const;//返回串的长度
            char * getdata() const;
        int strcompare(const Mystring);//比较两个串的长度
        void clear();//释放内存，清空串的内容
        void concat(const  Mystring);//连接两个串的内容
        char *  substring(int,int);//返回一个子串
        friend ostream & operator << (ostream &,const Mystring &);//重载“<<”
    };
    #endif

**string.c文件的内容**

#include "string.h"
    
    
    Mystring::Mystring(){
        data=NULL;
        MAX_SIZE=1000;
        length=0;
        step=100;
    }
    
    Mystring::Mystring(char * temp){
            //初始化MAX_SIZE和step
        MAX_SIZE=1000;
        step=100;
        int i=0;
        //得到temp字符串的长度（拖底程序效率的一个地方，写完尝试优化）
        while(temp[i++]!='\0');
        //如果串的长度，大于我们设定的最大的长度，那么就要对MAX_SIZE做一些修改        
        length=i-1;
        if(length>=MAX_SIZE){
            MAX_SIZE=length+step;
        }
            //为data开辟空间
    
        data=new char[MAX_SIZE];
            //为data赋值
        //data=temp;这种方法是错误的，虽然它可以很快捷的完成初始化，但是它只不过又重新为data定义了一个新的空间，这个空间就是temp开辟的空间
        for(i=0;i<=length;i++)
            data[i]=temp[i];
    
    }
    
    Mystring::Mystring(const Mystring & s)
    {
        //字符指指针的原理是：比如我们的data是指向存放那个串的第一个字符的内存地址，因为我们的串是存放的连续的内存地址的，并且是以“\0”结尾的，所以我们可以直接通过data来操作整个字符串，同时包括赋值。
        data=s.data;
        length=s.length;
        MAX_SIZE=s.MAX_SIZE;
        step=s.step;
    }
    
    void Mystring::strassign(char * temp)
    {
        //对于这个函数，我们首先是要先把我们串之前的内容给清空，然后我们再为它重新赋值
        data=NULL;
        length=0;
        //同样是先得到temp串的长度
        int i=0;
        while(temp[i++]!='\0');
        length=i-1;
        if(length>=MAX_SIZE)
            MAX_SIZE=length+step;
        //为data开辟新的空间
        data=new char[MAX_SIZE];
         //为data赋值
        for(i=0;i<=length;i++)
            data[i]=temp[i];
    
    
    }
    
    //const是必须添加的，因为这个是STL的一个机制的问题，如果我们不添加const，在strcompare函数将会报错
    int Mystring::strlength()const
    {
        return length;
    }
    
    char * Mystring::getdata()const
    {
        return data;
    }
    
    int Mystring::strcompare(const Mystring s)
    {
        //如果比s的data大，则返回大于0，两者相等则返回0，小于则返回小于0的数
        char *d=s.getdata();
        int l=s.strlength();
        int i;
        for(i=0;i<length && i<l;i++)
            if(data[i]!=d[i])
                return data[i]-d[i];
        return data[i]-d[i];
    }
    
    void Mystring::clear(){
        length=0;
        delete data;
        data=NULL;
    }
    
    void Mystring::concat(const Mystring s){
        int total=length+s.strlength();
        int l=s.strlength();
        int i=0;
        //如果data的空间不足以存放两个串的内容，所以我们需要为它重新开辟一个更大的空间
        if(MAX_SIZE<(total+1))
        {
            char *temp=data;
            MAX_SIZE=total+step;
            data=new char[MAX_SIZE];
            for(i=0;i<=length;i++)
            {
                data[i]=temp[i];
            }
            delete temp;
            temp=NULL;
        }
        else{
            i=length;//尾巴添加串的位置
        }
    
    
        //把s的串接在data的尾部
        char * t=s.getdata();
        for(int j=0;j<=l;j++){
            data[i++]=t[j];
        }
    }
    
    //假设下标从1开始，start为想要的字串开始的为位置，而l为其长度
    char * Mystring::substring(int start,int l)
    {
        char * temp;
    
        if(start<1 || start>length)
        {
            cout<<"你输入的起始位置不合法"<<endl;
            return NULL;
        }
        temp=new char[l];
        int j=0;
        int i=start-1;
        for(j=0;j<l && i<length;j++,i++)
        {
            temp[j]=data[i];
        }
        temp[j]='\0';
        cout<<j<<endl;
        return temp;
    }
    //重载了“<<”这个运算符，而且是通过友元函数的方式来重载的，所以在使用是可以直接：cout<<类对象名，通过这种格式来输出串的内容。
    ostream & operator << (ostream & out,const Mystring & s)
    {
        out<<s.data<<endl;
        return out;//返回输出流
    }

**main.c文件的内容**  
这里面的代码主要是一些测试的内容，所以基本没有写什么

#include "string.h"
    #include<iostream>
    using namespace std;
    
    int main()
    {
        char * str;
        str=new char[100];
        cin>>str;
        Mystring test(str);
    
        cout<<test<<endl;   
        return 0;
    }

**makefile文件的内容**  
makefile是一个告诉系统如何执行这个程序的一个文件，如果你有了这个文件，只需要在该目录下打开命令行，输入make就可以执行程序了，具体可以去百度看看

out:main.o string.o
        g++ -o out main.o string.o
    
    main.o:main.c string.h
        g++ -c main.c
    string.o:string.c string.h
        g++ -c string.c
    clean:
        rm out main.o string.o

**总结**

首先这次有光串的基础知识的学习，其实你会发现，你现在做的这些内容，STL中的string类都已经帮你做好了，所以我们在这里只是去学习一下string内部实现的一些方式，另外，学习了串的基本操作后，我想写一个小小的程序：*给你一篇英文的文章，你用c++写个程序，统计里面出现不同单词的总数和各个单词出现的频率。*

[Link 1]: http://blog.csdn.net/qq_35644234/article/details/52963325