List类的实现.doc

/list#include#include#include#include#includeusing namespace std;class i_stringprivate: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 &str0;char* end() return &strlen;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 &); 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 );public: /特殊运算符friend istream & operator ( istream &is , i_string &ch ) isch.str;ch.len=strlen(ch.str); return is; friend ostream & operator (ostream &os , i_string &ch ) osch.str; return os; char* operator + (int i)return &stri;char &operator (int i) constreturn stri;/ 构造函数 /i_string:i_string()str=new char1;len=0;str0=NULL;i_string:i_string() delete str;i_string:i_string(char *s) len=strlen(s); str=new charlen+1; strcpy(str,s); strlen=NULL;i_string:i_string(char c,int n) len=n;str=new charlen+1;for(int i=0;ilen;i+) stri=c;strlen=NULL;i_string:i_string(char c)len=1;str=new char2;str0=c;str1=NULL;i_string:i_string(int n) len=n;str=new charlen+1;for(int i=0;in;i+) stri=0;strlen=NULL;i_string:i_string(i_string &i_str)len=i_str.len;str=new charlen+1;strcpy(str,i_str.str);strlen=NULL;i_string:i_string(char *s,int n)int k=strlen(s);len=n*k;str=new charlen+1; for(int i=0;ik;i+) for(int j=0;jn;j+) strj*k+i=si;strlen=NULL;i_string:i_string(i_string& ch,int n)len=n*ch.len;str=new charlen+1; for(int i=0;ich.len;i+) for(int j=0;jn;j+) strj*ch.len+i=ch.stri;strlen=NULL;/输出函数/void i_string:Sci_out(int w) i_string i_str(*this); i_str.reset(); if(w=0) coutOutput error=len) couti_str.str; else int op=0; if(i_str.str0=-) op=1,w+; i_string s(i_str.substring(w); if(i_str.strw5) couts.str0; if(s.str0=-) cout1+op) cout.; couts.str+(1+op)*e0?s.sub(1):s.add(1); if(ks.len) i_str.len+; s.remove(s.len); couts.str0; if(s.str0=-) cout1+op) cout.; couts.str+(1+op)*eSci_out(w);coutSci_out(1);void i_string:Sci_outln()this-Sci_out(1);coutendl;/ 运算符重载 /i_string& i_string:operator =(i_string &ch)if(this!=&ch) str=new charch.len+1; strcpy(str,ch.str); len=ch.len; strlen=NULL;return *this;i_string& i_string:operator =(char *ch) str=new charstrlen(ch)+1; strcpy(str,ch); len=strlen(ch); strlen=NULL; return *this;i_string& i_string:operator =(char c) str=new char2; str0=c;len=1; strlen=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;ik2;i+) strk1+i=ch.stri;len=k1+k2;strlen=NULL; void i_string:operator += (char *ch) int k1=len,k2=strlen(ch); str=(char*)realloc(str,(k2+k1+1)*sizeof(char);for(int i=0;ik2;i+) strk1+i=chi;len=k1+k2;strlen=NULL;i_string i_string:operator + (char *ch) int k1=len,k2=strlen(ch),i;i_string STR(k1+k2);for(i=0;ik1;i+) STRi=stri; for(i=k1;ik2+k1;i+) STRi=chi-k1;return STR;i_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);strlen+=ch;strlen=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(c0) coutRuntime error0) 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 char2; c0=ch;c1=NULL; return *this+c;i_string i_string:operator(int n) if(n0)coutInput errorendl;exit(0) ; i_string STR(n+len);for(int i=0;i(int n) if(lenn) coutInsufficient memoryendl;exit(0) ; i_string STR(len-n);for(int i=0;ilen-n;i+) STR.stri=stri;return STR;bool i_string:operator Figure()&ch.Figure() i_string i_str1(*this),i_str2(ch); i_str1=i_str1.sub(i_str2); if(i_str10=-) return true; return false;if(strcmp(str,ch.str) (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_str10=-) 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_str10=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_str10=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_str10=0) return true; return false;if(strcmp(str,ch.str)=0) return true;return false;bool i_string:operator Figure()&ch.Figure() i_string i_str1(*this),i_str2(ch); i_str1=i_str1.sub(i_str2); if(i_str10=0) return true; return false;if(strcmp(str,ch.str)len)coutYou cant insert int the outside!pos;i-) stri=stri-1; strpos=c;len+; strlen=NULL;void i_string:insert(int pos,char *ch) if(poslen) coutYou cant insert outside!pos+k-1;i-) stri=stri-k; for(;i=pos;i-) stri=ch-k; strlen=NULL;void i_string:insert(int pos,i_string& ch) if(poslen)coutYou cant insert outside!insert(pos,ch.str);void i_string:swap(int p1,int p2) if(p11|p2len|p2len) coutSwap should inside!endl; exit(0); char tem=strp1-1; strp1-1=strp2-1; strp2-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;iLen/2;i+) swap(chi,chLen-i-1);void i_string:reserve(int p1,int p2) /第p1个到第p2个字符倒置 if(p2p1) swap(p1,p2); if(p1len) coutReserve should inside!endl; exit(0); for(int i=p1-1;iswap(i+1,p1+p2-1-i);_int64 i_string:valueof()if(len19) coutToo large value!endl;exit(0);_int64 sum=0;for(int i=0;ilen;i+)if(0=stri&stri=9) sum=10*sum+stri-0;else coutTransform error19) coutToo large value!endl;exit(0);_int64 sum=0;for(int i=0;ik;i+)if(0=chi&chi=9) sum=10*sum+chi-0;else coutTransform error9|c0) coutTransform errorp2) swap(p1,p2); ans=1; if(p1len) coutGet value should inside!18) coutToo large value!endl;exit(0);_int64 sum=0;int i;for(i=p1-1;ip2;i+)if(0=stri&stri=9) sum=10*sum+stri-0;else coutTransform error0) _int64 M=sum;sum=0;while(i=p1)sum=10*sum+M%10;M/=10;i-;return sum; bool i_string:empty()if(str0!=NULL) return false;return true;i_string i_string:substring(int p1,int p2) int ans=0; if(p1p2) swap(p1,p2);ans=1; if(p1len) coutGet substring should inside!endl; exit(0); int Len=p2-p1+1; i_string STR(Len);for(int i=0;iLen;i+)STRi=strp1-1+i;STR.len=Len;STR.strLen=NULL;if(ans) STR.reserve();return STR;i_string i_string:substring(int p2) if(p2=-len) return this-substring(len,len+p2+1); if(p2len|p2-len) coutGet substring should inside!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;ip2) swap(p1,p2); if(p1len) coutRemove should inside!endl; exit(0); int k,i;for(k=i=p1-1;ilen;i+) if(stri!=c) strk+=stri;str=(char*)realloc(str,(p1+k+1)*sizeof(char); len=k;strlen=NULL; void i_string:remove(int fig) if(fig=0) return; if(figlen) coutRemove should inside!endl; exit(0); for(int i=fig-1;ip2) swap(p1,p2); if(p1=p2) return; if(p1=0) p1=1; if(p1len) coutRemove should inside!endl; exit(0); for(int i=p2-1;ilen;i+) strp1+i-p2=stri+1; str=(char*)realloc(str,(len-p2+p1)*sizeof(char); len=len-p2+p1-1; strlen=NULL; void i_string:erase(int fig) if(fig=0) return; if(figlen) coutErase should inside!remove(1,fig); void get_next(char *T,int *next) / 外部辅助函数 next0=-1; int k=-1,j=0; while(Tj) if(k!=-1&Tk!=Tj) k=nextk; j+;k+; if(Tk=Tj) nextj=nextk; else nextj=k; void i_string:remove(int p1,int p2,char *T) /KMP求匹配 if(p1p2) swap(p1,p2); if(p1len) coutRemove should inside!endl; exit(0); int Len=strlen(T); if(p2-p1Len-1) return; int *next=new intLen+1; get_next(T,next); int i=p1-1,j=0; while(ip2) if(stri= Tj) i+;j+; if(j=Len) j=0; for(int k=1;k=Len;k+) stri-k=#; else if(nextj!=-1) j=nextj; else j=0;i+; delete next; for(j=i=p1-1;iremove(1,len,T);bool i_string:Figure()if(str0=-|(str0=0&str0=9)for(int i=1;ilen;i+)if(stri9) return false ;return true;return false;bool figure(char *ch)if(ch0=-|(ch0=0&ch0=9)for(int i=1;chi!=0;i+) if(chi9) return false ;return true;return false;void i_string:reset()int i;if(len=1) return;if(str0=-) for(i=1;ierase(i-1);if(str1=0) this-remove(1);return;for(i=0;ierase(i);void Reset(char *ch) int i,k,Len=strlen(ch);for(i=0;iLen-1;i+) if(chi!=0) break;for(k=i;kFigure()|!figure(s) coutCalculation must between digitalsendl;exit(0);int op1=0,op2=0;if(s0=-) op2=1;i_string c