数据结构----串

2/22/2017来源:ASP.NET技巧人气:302

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

1、串的三种表示方式

定长顺序存储表示 堆分配表示(比较倾向使用这种) 链式存储表示

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;//返回输出流 }

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

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++写个程序,统计里面出现不同单词的总数和各个单词出现的频率。