List类的实现

#include #include #include #include #include using namespace std;

class i_string {

private: char *str; int len;

public: //构造函数 ~i_string(); i_string();

i_string(i_string &); i_string(char *); i_string(char ); i_string(int ); i_string(char *,int ); i_string(char ,int ); i_string(i_string& ,int); public: //位数控制输出 void Sci_out(int ); void Sci_outln(int ); void Sci_out(); void Sci_outln(); public: //功能函数 int length(){ return len;} char* begin(){ return &str[0];} char* end(){ return &str[len];} char* Str(){ return str;} void insert(int ,char *); void insert(int ,char);

void insert(int ,i_string &); void reserve();

void reserve(int,int); void swap(int ,int); void remove(char);

void remove(int,int,char); void remove(char*);

void remove(int ,int, char*);

void remove(int ); void remove(int,int); void erase(char*); void erase(int );

i_string substring(int,int); i_string substring(int); _int64 valueof();

_int64 valueof(int,int); void reset(); friend void swap(char*,char*); friend void swap(char&,char&); friend void Reset(char*); friend void Reserve(char*); friend void get_next(char*,int*); friend _int64 valueof(i_string &); friend _int64 valueof(char *); friend int valueof(char ); bool empty(); bool Figure(); void clear();

public: //值运算函数 i_string add(i_string &); i_string add(char *); i_string add(char ); i_string add(int ); i_string add(_int64); i_string mul(i_string &); i_string mul(char *); i_string mul(char ); i_string mul(int ); i_string mul(_int64 ); i_string sub(i_string &); i_string sub(char *); i_string sub(char ); i_string sub(int ); i_string sub(_int64 ); public: //运算符重载

i_string &operator =(i_string &); i_string &operator =(char *); i_string &operator =(char ); bool operator < (i_string &); bool operator > (i_string &); bool operator <= (i_string &); bool operator >= (i_string &);

bool operator == (i_string &); bool operator != (i_string &); void operator += (i_string &); void operator += (char *); void operator += (char ); i_string operator * (int ); i_string operator ^ (int);

i_string operator + (i_string & ); i_string operator + (char *); i_string operator + (char ); i_string operator <<(int ); i_string operator >>(int ); public: //特殊运算符 friend istream & operator >> ( istream &is , i_string &ch ) { is>>ch.str; ch.len=strlen(ch.str); return is; } friend ostream & operator << (ostream &os , i_string &ch ) { os</////////////////////////////////////////////////////// ////////// 构造函数 //////////////// ////////////////////////////////////////////////////// i_string::i_string() { str=new char[1]; len=0; str[0]=NULL; }

i_string::~i_string() {

delete []str; }

i_string::i_string(char *s) {

len=strlen(s); str=new char[len+1]; strcpy(str,s); str[len]=NULL; }

i_string::i_string(char c,int n) { len=n; str=new char[len+1]; for(int i=0;ii_string::i_string(char c) { len=1; str=new char[2]; str[0]=c; str[1]=NULL; }

i_string::i_string(int n) { len=n; str=new char[len+1]; for(int i=0;ii_string::i_string(i_string &i_str) { len=i_str.len; str=new char[len+1]; strcpy(str,i_str.str); str[len]=NULL; }

i_string:: i_string(char *s,int n) { int k=strlen(s); len=n*k; str=new char[len+1]; for(int i=0;ifor(int j=0;ji_string:: i_string(i_string& ch,int n) { len=n*ch.len; str=new char[len+1]; for(int i=0;i////////////////////////////////////////////////////////////////// ///////////////////输出函数////////////////////////////// ////////////////////////////////////////////////////////////// void i_string::Sci_out(int w) { i_string i_str(*this); i_str.reset(); if(w<=0) { cout<<\"Output error\"<if(w>=len) cout<1+op) cout<<\".\"; cout<0?s.sub(\"1\"):s.add(\"1\"); if(k} cout<1+op) cout<<\".\"; cout<void i_string::Sci_outln(int w) {

this->Sci_out(w); cout<void i_string::Sci_out() { this->Sci_out(1); }

void i_string::Sci_outln() { this->Sci_out(1); cout<///////////////////////////////////////////////////////////// ///////////// 运算符重载 ////////////////////// ////////////////////////////////////////////////////////////// i_string& i_string::operator =(i_string &ch) { if(this!=&ch) { str=new char[ch.len+1]; strcpy(str,ch.str); len=ch.len; str[len]=NULL; } return *this; }

i_string& i_string::operator =(char *ch) { str=new char[strlen(ch)+1]; strcpy(str,ch); len=strlen(ch); str[len]=NULL; return *this; }

i_string& i_string::operator =(char c) { str=new char[2]; str[0]=c;len=1; str[len]=NULL; return *this; }

void i_string::operator +=(i_string &ch) {

int k1=len,k2=ch.len;

str=(char*)realloc(str,(k2+k1+1)*sizeof(char)); for(int i=0;ivoid i_string::operator += (char *ch) {

int k1=len,k2=strlen(ch);

str=(char*)realloc(str,(k2+k1+1)*sizeof(char)); for(int i=0;ii_string i_string::operator + (char *ch) {

int k1=len,k2=strlen(ch),i; i_string STR(k1+k2); for(i=0;ifor(i=k1;ii_string i_string::operator + (i_string &ch) {

return *this+ch.str; }

void i_string::operator += (char ch) {

str=(char*)realloc(str,(2+len)*sizeof(char)); str[len++]=ch; str[len]=NULL; }

i_string i_string::operator * (int c) { i_string STR(*this);

while(--c) STR+=*this; return STR; }

i_string i_string::operator ^(int c) { if(c<0) { cout<<\"Runtime error\"<0) { if(c%2) SUM=SUM.mul(A); A=A.mul(A); c/=2; } return SUM; }

i_string i_string::operator + (char ch) {

char *c=new char[2]; c[0]=ch;c[1]=NULL; return *this+c; }

i_string i_string::operator<<(int n) { if(n<0) { cout<<\"Input error\"<i_string STR(n+len); for(int i=0;ii_string i_string::operator >>(int n) {

if(lenbool i_string::operator < (i_string &ch) { if(this->Figure()&&ch.Figure()) {

i_string i_str1(*this),i_str2(ch); i_str1=i_str1.sub(i_str2); if(i_str1[0]=='-') return true; return false; } if(strcmp(str,ch.str)<0) return true; return false; }

bool i_string::operator > (i_string &ch) { if(this->Figure()&&ch.Figure()) {

i_string i_str1(*this),i_str2(ch); i_str1=i_str2.sub(i_str1); if(i_str1[0]=='-') return true; return false; } if(strcmp(str,ch.str)>0) return true; return false; }

bool i_string::operator == (i_string &ch) {

if(this->Figure()&&ch.Figure()) {

i_string i_str1(*this),i_str2(ch); i_str1=i_str1.sub(i_str2); if(i_str1[0]=='0') return true; return false; } if(strcmp(str,ch.str)==0) return true; return false;

}

bool i_string::operator != (i_string &ch) {

if(this->Figure()&&ch.Figure()) {

i_string i_str1(*this),i_str2(ch); i_str1=i_str1.sub(i_str2); if(i_str1[0]=='0') return false; return true; } if(strcmp(str,ch.str)!=0) return true; return false; }

bool i_string::operator >= (i_string &ch) {

if(this->Figure()&&ch.Figure()) {

i_string i_str1(*this),i_str2(ch); i_str1=i_str1.sub(i_str2); if(i_str1[0]>='0') return true; return false; } if(strcmp(str,ch.str)>=0) return true; return false; }

bool i_string::operator <= (i_string &ch) {

if(this->Figure()&&ch.Figure()) {

i_string i_str1(*this),i_str2(ch); i_str1=i_str1.sub(i_str2); if(i_str1[0]<='0') return true; return false; } if(strcmp(str,ch.str)<=0) return true; return false; }

/////////////////////////////////////////////////////////////// //////////////// 功能函数 //////////////////////// ////////////////////////////////////////////////////////////// void i_string::insert(int pos,char c) { if(pos>len) {

cout<<\"You can't insert int the outside!\"<str=(char*)realloc(str,(2+len)*sizeof(char)); for(int i=len;i>pos;i--) str[i]=str[i-1]; str[pos]=c;len++; str[len]=NULL; }

void i_string::insert(int pos,char *ch) {

if(pos>len) { cout<<\"You can't insert outside!\"<str=(char*)realloc(str,(k+len+1)*sizeof(char)); len=len+k;

for(i=len-1;i>pos+k-1;i--) str[i]=str[i-k]; for(;i>=pos;i--) str[i]=ch[--k]; str[len]=NULL; }

void i_string::insert(int pos,i_string& ch) {

if(pos>len) { cout<<\"You can't insert outside!\"<insert(pos,ch.str); }

void i_string::swap(int p1,int p2) { if(p1<1||p2<1||p1>len||p2>len) { cout<<\"Swap should inside!\"<char tem=str[p1-1]; str[p1-1]=str[p2-1]; str[p2-1]=tem; }

void swap(char *p1,char *p2) {

char tem=*p1; *p1=*p2; *p2=tem; }

void swap(char &p1,char &p2) { char tem=p1; p1=p2; p2=tem; }

void i_string::reserve() {

for(int i=1;iswap(i,len-i+1); }

void Reserve(char *ch) { int Len=strlen(ch);

for(int i=0;ivoid i_string::reserve(int p1,int p2) //第p1个到第p2个字符倒置 { if(p2len) { cout<<\"Reserve should inside!\"<for(int i=p1-1;i<(p1+p2-1)/2;i++) this->swap(i+1,p1+p2-1-i); }

_int64 i_string::valueof() { if(len>19) { cout<<\"Too large value!\"<cout<<\"Transform error\"<_int64 valueof(char *ch) { int k=strlen(ch); if(k>19) { cout<<\"Too large value!\"<_int64 valueof(i_string &ch) { return valueof(ch.str); }

int valueof(char c) {

if(c>'9'||c<'0') { cout<<\"Transform error\"<_int64 i_string::valueof(int p1,int p2) { int ans=0; if(p1>p2) { swap(p1,p2);

ans=1; }

if(p1<1||p2>len) { cout<<\"Get value should inside!\"<18) { cout<<\"Too large value!\"<0) { _int64 M=sum; sum=0; while(i>=p1) { sum=10*sum+M%10; M/=10;i--; } } return sum; }

bool i_string::empty() { if(str[0]!=NULL) return false; return true; }

i_string i_string::substring(int p1,int p2) { int ans=0; if(p1>p2) {

swap(p1,p2);ans=1; }

if(p1<1||p2>len) { cout<<\"Get substring should inside!\"<i_string i_string::substring(int p2) { if(p2<0&&p2>=-len) { return this->substring(len,len+p2+1); }

if(p2>len||p2<-len) { cout<<\"Get substring should inside!\"<return this->substring(1,p2); }

void i_string::erase(char *dz) { char *i=dz; for(;(i+1)!=this->end();i++) *i=*(i+1); str=(char*)realloc(str,len*sizeof(char)); *i=NULL; len=len-1; }

void i_string::remove(char c) { int k=0,i; for(i=0;ivoid i_string::remove(int p1,int p2,char c) { if(p1>p2) swap(p1,p2); if(p1<1||p2>len) { cout<<\"Remove should inside!\"<void i_string::remove(int fig) { if(fig==0) return; if(fig<0||fig>len) { cout<<\"Remove should inside!\"<str=(char*)realloc(str,len*sizeof(char)); len--; str[len]=NULL; }

void i_string::remove(int p1,int p2) { if(p1>p2) swap(p1,p2); if(p1==p2) return;

if(p1==0) p1=1; if(p1<1||p2>len) { cout<<\"Remove should inside!\"<for(int i=p2-1;istr=(char*)realloc(str,(len-p2+p1)*sizeof(char)); len=len-p2+p1-1; str[len]=NULL; }

void i_string::erase(int fig) { if(fig==0) return; if(fig<0||fig>len) { cout<<\"Erase should inside!\"<remove(1,fig); }

void get_next(char *T,int *next) // 外部辅助函数 {

next[0]=-1; int k=-1,j=0; while(T[j]) {

if(k!=-1&&T[k]!=T[j]) k=next[k]; j++;k++;

if(T[k]==T[j]) next[j]=next[k]; else next[j]=k; } }

void i_string::remove(int p1,int p2,char *T) { if(p1>p2) swap(p1,p2); if(p1<1||p2>len) { cout<<\"Remove should inside!\"<int Len=strlen(T);

if(p2-p1//KMP求匹配 int *next=new int[Len+1]; get_next(T,next); int i=p1-1,j=0; while(iif(next[j]!=-1) j=next[j]; else {j=0;i++;} } }

delete []next;

for(j=i=p1-1;ivoid i_string::remove(char* T) { this->remove(1,len,T); }

bool i_string::Figure() { if(str[0]=='-'||(str[0]>='0'&&str[0]<='9')) { for(int i=1;i'9') return false ; return true; } return false; }

bool figure(char *ch) { if(ch[0]=='-'||(ch[0]>='0'&&ch[0]<='9')) { for(int i=1;ch[i]!='\\0';i++)

str[i-k]='#'; if(ch[i]<'0'||ch[i]>'9') return false ; return true; } return false; }

void i_string::reset() { int i; if(len==1) return; if(str[0]=='-') { for(i=1;ithis->erase(i-1); if(str[1]=='0') this->remove(1); return; } for(i=0;ierase(i); }

void Reset(char *ch) {

int i,k,Len=strlen(ch); for(i=0;ivoid i_string::clear() { delete []str; len=0; str=new char[1]; str[0]=NULL; }

//////////////////////////////////////////////////////////////// ////////////// 值运算函数 ////////////////////////// ///////////////////////////////////////////////////////////////

i_string i_string::mul(char *s) 效率为O(mn/64); { if(!this->Figure()||!figure(s)) { cout<<\"Calculation must between digitals\"<// } int op1=0,op2=0; if(s[0]=='-') op2=1; i_string ch(s+op2),i_str(*this); ch.reset();i_str.reset(); if(i_str.str[0]=='-') op1=1; int r1=len-op1,r2=ch.len; int i,j,u=0;

_int64 *d=new _int64[r1+r2+1]; for(i=0;iif(j%8) for(i=0;i<(8-j%8);i++) {a[r1++]=0;u++;} j=r2;

if(j%8) for(i=0;i<(8-j%8);i++) {b[r2++]=0;u++;}

_int64 *a8=new _int64[r1/8+2]; _int64 *b8=new _int64[r2/8+2]; for(i=0;ifor(i=0;i=0;i--) { temp=0; for(j=r2/8-1;j>=0;j--) { d[i+j+1]+=a8[i]*b8[j]+temp; temp=d[i+j+1]/M; d[i+j+1]%=M; }

d[i]+=temp; } int sp[9], k=0; char *p=new char[r1+r2+1]; while(d[0]) { sp[k++]=d[0]%10; d[0]/=10; } for(j=0;k>0;k--) p[j++]=sp[k-1]+'0'; for(i=1;ii_string STR(j-u); if(op1) STR.str[0]='-'; for(i=op1;idelete []p;delete []d;delete []b8; delete []a;delete []b;delete []a8; return STR; }

i_string i_string::mul(i_string &ch) { return this->mul(ch.str); }

i_string i_string::mul(char c) { i_string ch(c); return this->mul(ch); }

i_string i_string::mul(_int64 fig) {

if(fig>0) { int k=(int)log10(fig*1.0)+1; char *ch=new char[k+1]; ch[k]=NULL; while(k--) { ch[k]=fig%10+'0'; fig/=10; } return this->mul(ch); } else if(fig<0) { fig=-fig;

int k=(int)log10(fig*1.0)+2; char *ch=new char[k+1]; ch[k]=NULL; while(k>1) { ch[--k]=fig%10+'0'; fig/=10; } ch[0]='-'; return this->mul(ch); }

i_string ZERO(1); return ZERO; }

i_string i_string::mul(int fig) { return this->mul((_int64) fig); }

i_string i_string::add(char *c) {

if(!this->Figure()||!figure(c)) { cout<<\"Calculation must between digitals\"<sub(c+1); if(str[0]=='-') { i_string STR(c);

return STR.sub(str+1); }

this->reserve(); int i,Len=strlen(c); char *ch=new char[Len+1]; for(i=0;iLen?len:Len; i_string STR(temp); temp=0; if(len>Len) { for(i=0;iSTR.str[i]=str[i]-'0'+temp; temp=STR.str[i]/10; STR.str[i]=STR.str[i]%10+'0'; } } else {

for(i=0;iSTR.str[i]=ch[i]-'0'+temp; temp= STR.str[i]/10; STR.str[i]= STR.str[i]%10+'0'; } } if(temp>0) { STR.str=(char*) realloc(STR.str,(STR.len+2)*sizeof(char));

STR.str[STR.len++]=temp+'0'; STR.str[STR.len]=NULL; }

delete []ch; this->reserve(); STR.reserve();STR.reset(); return STR; }

i_string i_string::add(i_string &ch) {

if(ch[0]=='-') return this->sub(ch.str+1); return this->add(ch.str); }

i_string i_string::add(char c) { char *ch=new char[2]; ch[0]=c;ch[1]=NULL; return this->add(ch); }

i_string i_string::add(_int64 c) { if(c>0) { int k=(int) log10(c*1.0)+1; char *ch=new char[k+1]; ch[k]='\\0'; while(k--) { ch[k]=c%10+'0'; c/=10; } if(str[0]=='-') { i_string STR(ch); return STR.sub(str+1); } return this->add(ch); }

if(c<0) return this->sub(-c); return *this; }

i_string i_string::add(int c) { if(c>0) return this->add((_int64)c); if(c<0) return this->sub((_int64)-c);

i_string i_str(*this); i_str.reset(); return i_str; }

i_string i_string::sub(char *s) {

if(!this->Figure()||!figure(s)) { cout<<\"Calculation must between digitals\"<char *ch=new char[strlen(s)+1]; strcpy(ch,s); ch[L]=NULL; i_string i_str(*this); if(s[0]=='-') return this->add(s+1); if(i_str.str[0]=='-') { return i_str.mul(\"-1\").add(s).mul(\"-1\"); } i_str.reset(); i_str.reserve(); Reset(ch); Reserve(ch); L=strlen(ch); int i,temp=i_str.len>L?i_str.len:L; i_string STR(temp);temp=0; if(i_str.len>L) {

for(i=0;i=0) { STR.str[i]=i_str.str[i]-ch[i]-temp+'0'; temp=0; } else { STR.str[i]=i_str.str[i]-ch[i]-temp+10+'0';

temp=1; } } for(;i=0) { STR.str[i]=i_str.str[i]-temp; temp=0; } else { STR.str[i]=i_str.str[i]-temp+10; temp=1; } } STR.reserve();STR.reset(); return STR; }

else if(i_str.len=0) { STR.str[i]=ch[i]-i_str.str[i]-temp+'0'; temp=0; } else { STR.str[i]=ch[i]-i_str.str[i]-temp+10+'0'; temp=1; } } for(;i=0) { STR.str[i]=ch[i]-temp; temp=0; } else { STR.str[i]=ch[i]-temp+10;

temp=1; } } STR.str=(char*)realloc(STR.str,(L+2)*sizeof(char)); STR.str[STR.len++]='-';STR.str[STR.len]=NULL; STR.reserve(); STR.reset(); return STR; } else { for(i=L-1;i>=0;i--) { if(i_str.str[i]!=ch[i]) break; } if(i<0) { i_string ZERO(1); return ZERO; } if(i_str.str[i]>ch[i]) {

for(i=0;i=0) { STR.str[i]=i_str.str[i]-ch[i]-temp+'0'; temp=0; } else { STR.str[i]=i_str.str[i]-ch[i]-temp+10+'0'; temp=1; } }

STR.reserve();STR.reset(); return STR; } else for(i=0;i=0) { STR.str[i]=ch[i]-i_str.str[i]-temp+'0'; temp=0;

} else { STR.str[i]=ch[i]-i_str.str[i]-temp+10+'0'; temp=1; } } STR.str=(char*)realloc(STR.str,(L+2)*sizeof(char)); STR[STR.len++]='-';STR[STR.len]=NULL; STR.reserve(); STR.reset(); return STR; } }

i_string i_string::sub(i_string &ch) { if(ch[0]=='-') return this->add(ch.str+1); return this->sub(ch.str); }

i_string i_string::sub(char c) { char *ch=new char[2]; ch[0]=c;ch[1]=NULL; return this->sub(ch); }

i_string i_string::sub(_int64 c) { if(c>0) { int k=(int) log10(c*1.0)+1; char *ch=new char[k+1]; ch[k]='\\0'; while(k--) { ch[k]=c%10+'0'; c/=10; } return this->sub(ch); }

if(c<0) return this->add(-c); return *this; }

i_string i_string::sub(int c) { if(c>0) return this->sub((_int64)c);

if(c<0) return this->add((_int64)-c); i_string i_str(*this); i_str.reset(); return i_str; }

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////main函数/////////////////////////////////////

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// int main() //////////////测试 { i_string s0,s1(\"-00999900\"),s2(\"-00123\"),s3('1',3),s4(\"123\ cout<<\"测试\"<>s0; cout<cout<<\"其他测试： 略\"<