第6章主要算法的C++代碼順序串的基本操作：/*順序串的實現(xiàn)C++*/#include<iostream>usingnamespacestd;constintMAX_N=100;//定義數(shù)據(jù)類型classSqStr{public: chardata[MAX_N]; intlength;};//串classString{public: String(){} ~String(){} //生成串 voidStrAssign(charcstr[]){ inti; for(i=0;cstr[i]!='\0';i++){ S.data[i]=cstr[i]; } S.length=i; } //復(fù)制串 voidStrCopy(Stringt){ inti; //串賦值 for(i=0;i<t.GetS()->length;i++){ S.data[i]=t.GetS()->data[i]; } //串長度賦值 S.length=t.GetS()->length; } //是否相等 boolStrEqual(Stringt){ //長度不等 if(S.length!=t.GetS()->length){ returnfalse; } else{ inti; for(i=0;i<S.length;i++){ //內(nèi)容不等 if(S.data[i]!=t.GetS()->data[i]){ returnfalse; } } //否則相等 returntrue; } } //求長度 intSTrLength(){ returnS.length; } //串連接 SqStrConcat(Stringt){ SqStrstr; str.length=S.length+t.GetS()->length; inti; //賦值S for(i=0;i<S.length;i++){ str.data[i]=S.data[i]; } //賦值t for(i=S.length;i<S.length+t.GetS()->length;i++){ str.data[i]=t.GetS()->data[i-S.length]; } returnstr; } //求子串,返回從S串的位置i開始連續(xù)j個字符，返回新串，參數(shù)不正確時返回空串 SqStrSubStr(inti,intj){ SqStrstr; str.length=0; //下標與位置差1 if(i<=0||i>S.length||j<=0||i+j-1>S.length){ returnstr; } else{ intk; for(k=i-1;k<i+j-1;k++){ str.data[k-(i-1)]=S.data[k]; } str.length=j; returnstr; } } //插入串，將s1插入到S中的位置i開始，返回新串，參數(shù)不正確時返回空串 SqStrInsertStr(Strings1,inti){ SqStrstr; str.length=0; //i為位置，與數(shù)組下標差1 if(i<=0||i>S.length+1){ returnstr; } else{ intj; //插入S前i-1個字符 for(j=0;j<i-1;j++){ str.data[j]=S.data[j]; } //插入串s1 for(j=0;j<s1.GetS()->length;j++){ str.data[j+i-1]=s1.GetS()->data[j]; } //插入剩下的S串 for(j=i-1;j<S.length;j++){ str.data[(i-1)+s1.GetS()->length+(j-(i-1))]=S.data[j]; } str.length=S.length+s1.GetS()->length; returnstr; } } //刪除S串中位置i開始的連續(xù)j個字符，生成新串并返回，參數(shù)不正確時返回空串 SqStrDeleteStr(inti,intj){ SqStrstr; str.length=0; //j<0無意義，不刪除任何字符，j==0即刪除0個字符串，仍為空串 if(i<=0||i>S.length||j<=0||i+j-1>S.length){ returnstr; } else{ intk; //賦值S前i-1個字符 for(k=0;k<i-1;k++){ str.data[k]=S.data[k]; } //跳過j個字符，賦值剩下的字符 for(k=i-1+j;k<S.length;k++){ str.data[k-j]=S.data[k]; } str.length=S.length-j; returnstr; } } //替換串，將S中的位置i開始的j個字符替換成串t,生成新串并返回，參數(shù)不正確返回空串 SqStrReplaceStr(inti,intj,Stringt){ SqStrstr; str.length=0; //j<0沒有實際意義，j==0，即將i-1后的0個字符替換 if(i<=0||i>S.length||j<0||i+j-1>S.length){ returnstr; } else{ intk; //賦值S的前i-1個字符 for(k=0;k<i-1;k++){ str.data[k]=S.data[k]; } //插入t串 for(k=0;k<t.GetS()->length;k++){ str.data[i-1+k]=t.GetS()->data[k]; } //S串跳過j個字符后插入剩下所有 for(k=i-1+j;k<S.length;k++){ str.data[(i-1)+t.GetS()->length+(k-(i-1+j))]=S.data[k]; } str.length=S.length-j+t.GetS()->length; returnstr; } } //輸出串（不帶參數(shù)） voidDisplayStr(){ //空串處理 if(S.length==0){ cout<<"Empty."<<endl; } //否則輸出串 else{ inti; for(i=0;i<S.length;i++){ cout<<S.data[i]; } cout<<endl; } } //輸出串（帶參數(shù)） voidDisplayStr(SqStrstr){ if(str.length==0){ cout<<"Empty."<<endl; } else{ inti; for(i=0;i<str.length;i++){ cout<<str.data[i]; } cout<<endl; } }private: SqStrS; //獲取串首地址 SqStr*GetS(){ return&S; }};intmain(){ intn,i,locate,strlength; chara[MAX_N]; //生成串 cout<<"CreateString."<<endl; cout<<"Inputn:"; cin>>n; cout<<"Input"<<n<<"characters."<<endl; for(i=0;i<n;i++){ cin>>a[i]; } a[i]='\0'; Stringstr1; str1.StrAssign(a); //輸出串 cout<<"Dispalystring."<<endl; str1.DisplayStr(); //串長度 cout<<"StringLength."<<endl; cout<<str1.STrLength()<<endl; //拷貝串 cout<<"StringCopy."<<endl; cout<<"Inputn:"; cin>>n; cout<<"Input"<<n<<"characters."<<endl; for(i=0;i<n;i++){ cin>>a[i]; } a[i]='\0'; Stringstr2; str2.StrAssign(a); str1.StrCopy(str2); str1.DisplayStr(); //獲取子串 cout<<"GetSubStr."<<endl; cout<<"Inputlocate,stringlength:"; cin>>locate>>strlength; str1.DisplayStr(str1.SubStr(locate,strlength)); //插入串 cout<<"Insertstring."<<endl; cout<<"Inputn:"; cin>>n; cout<<"Input"<<n<<"characters."<<endl; for(i=0;i<n;i++){ cin>>a[i]; } a[i]='\0'; str2.StrAssign(a); cout<<"Inputlocate:"; cin>>locate; str1.DisplayStr(str1.InsertStr(str2,locate)); //連接串 cout<<"Concatstring."<<endl; cout<<"Inputn:"; cin>>n; cout<<"Input"<<n<<"characters."<<endl; for(i=0;i<n;i++){ cin>>a[i]; } a[i]='\0'; str2.StrAssign(a); str1.DisplayStr(str1.Concat(str2)); //是否相等 cout<<"IsEqual."<<endl; if(str1.StrEqual(str2)){ cout<<"YES."<<endl; } else{ cout<<"NO."<<endl; } //刪除串 cout<<"Delete."<<endl; cout<<"Inputlocate,stringlength:"; cin>>locate>>strlength; str1.DisplayStr(str1.DeleteStr(locate,strlength)); //替換串 cout<<"Repalce."<<endl; cout<<"Inputlocate,stringlength:"; cin>>locate>>strlength; str1.DisplayStr(str1.ReplaceStr(locate,strlength,str2)); return0;}稀疏矩陣的基本操作#include<iostream>usingnamespacestd;structTrituple{//自定義數(shù)據(jù)結(jié)構(gòu)：矩陣元素的行，列，值； introw,col; intvalue; Trituple&operator=(Trituple&x){//賦值運算符重載 row=x.row; col=x.col; value=x.value; return*this; }};#include"Trituple.h"#include<iostream>#include<assert.h>usingnamespacestd;constintDefaultSize=100;classSparseMatrix{//稀疏矩陣private: intRows,Cols,Terms;//行數(shù)，列數(shù)，非零元素的個數(shù) Trituple*smArray;//存非零元素的三元數(shù)組 intmaxTerms;//三元組最大可容納的元素個數(shù)public: SparseMatrix(intmaxSz=DefaultSize);//構(gòu)造函數(shù) SparseMatrix(SparseMatrix&SM);//賦值構(gòu)造函數(shù) ~SparseMatrix();//析構(gòu)函數(shù) SparseMatrix&operator=(SparseMatrix&SM);//賦值運算符重載 SparseMatrixTranspose();//矩陣轉(zhuǎn)置 SparseMatrixAdd(SparseMatrix&b);//矩陣的加法 SparseMatrixMultiply(SparseMatrix&b);//矩陣的乘法 friendostream&operator<<(ostream&ostr,SparseMatrix&SM);//矩陣的輸出重載函數(shù) friendistream&operator>>(istream&istr,SparseMatrix&SM);//矩陣的輸入重載函數(shù)};SparseMatrix::SparseMatrix(intmaxSz):maxTerms(maxSz){//構(gòu)造函數(shù)：構(gòu)造一個大小為maxTerm的三元組，行列數(shù)和非零元素個數(shù)都置零 if(maxSz<1){ cerr<<"矩陣初始化錯誤！"<<endl; exit(1); } smArray=newTrituple[maxSz]; assert(smArray!=NULL); Rows=Cols=Terms=0;}SparseMatrix::SparseMatrix(SparseMatrix&SM){//復(fù)制構(gòu)造函數(shù) Rows=SM.Rows;//賦值矩陣的性質(zhì) Cols=SM.Cols; Terms=SM.Terms; maxTerms=SM.maxTerms; smArray=newTrituple[maxTerms];//構(gòu)造三元組并賦與SM相同的值 assert(smArray!=NULL); for(inti=0;i<Terms;i++) smArray[i]=SM.smArray[i];}SparseMatrix::~SparseMatrix(){//析構(gòu)函數(shù)：釋放所有存儲 delete[]smArray;}SparseMatrix&SparseMatrix::operator=(SparseMatrix&SM){//賦值運算符重載 Rows=SM.Rows;//元素性質(zhì)的賦值 Cols=SM.Cols; Terms=SM.Terms; maxTerms=SM.maxTerms; for(inti=0;i<Terms;i++)//三元組所有元素賦值 smArray[i]=SM.smArray[i]; return*this;//返回的是對調(diào)用該函數(shù)的對象的引用，需顯式使用this指針；}ostream&operator<<(ostream&ostr,SparseMatrix&SM){//輸出運算符重載（為啥代模板就不能調(diào)用row？） ostr<<"#Rows="<<SM.Rows<<endl;//輸出該矩陣的性質(zhì) ostr<<"#Cols="<<SM.Cols<<endl; ostr<<"#Terms="<<SM.Terms<<endl; for(inti=0;i<SM.Terms;i++)//輸出該矩陣非零元素的位置及值 ostr<<i+1<<":"<<"SM<"<<SM.smArray[i].row<<","<<SM.smArray[i].col<<">="<< SM.smArray[i].value<<endl; returnostr;}istream&operator>>(istream&istr,SparseMatrix&SM){//輸入運算符重載 cout<<"Pleaseenternumberofrows,columns,andtermsofMatrix"<<endl; istr>>SM.Rows>>SM.Cols>>SM.Terms;//輸入元素的性質(zhì) if(SM.Terms>SM.maxTerms){ cerr<<"NumbersofTermsoverflow!"<<endl; exit(1); } for(inti=0;i<SM.Terms;i++){//依次輸入非零元素的坐標和值 cout<<"Enterrow,column,andvalueofterm:"<<i+1<<endl; cin>>SM.smArray[i].row>>SM.smArray[i].col>>SM.smArray[i].value; } returnistr;}/*SparseMatrixSparseMatrix::Transpose(){//轉(zhuǎn)置函數(shù) SparseMatrixb(maxTerms); b.Rows=Rows; b.Cols=Cols; b.Terms=Terms; b.maxTerms=maxTerms; if(Terms>0){ inti,k,CurrentB=0; for(k=0;k<b.Cols;k++) for(i=0;i<Terms;i++) if(smArray[i].col==k){ b.smArray[CurrentB].row=smArray[i].col; b.smArray[CurrentB].col=smArray[i].row; b.smArray[CurrentB].value=smArray[i].value; CurrentB++; } } returnb;}*/SparseMatrixSparseMatrix::Transpose(){//轉(zhuǎn)置函數(shù) int*rowSize=newint[Cols];//轉(zhuǎn)置矩陣每行非零元素的個數(shù) int*rowStart=newint[Cols];//轉(zhuǎn)置矩陣每行第一個非零元素對應(yīng)其三元組的下標 SparseMatrixb(maxTerms);//轉(zhuǎn)置后的矩陣對應(yīng)的三元組 b.Rows=Rows;//b的性質(zhì) b.Cols=Cols; b.Terms=Terms; b.maxTerms=maxTerms; if(Terms>0){ inti,j,CurrentB=0; for(i=0;i<Cols;i++)//對rowSize數(shù)組賦值 rowSize[i]=0; for(i=0;i<Terms;i++) rowSize[smArray[i].col]++; rowStart[0]=0;//對rowStart數(shù)組賦值 for(i=1;i<b.Rows;i++) rowStart[i]=rowStart[i-1]+rowSize[i-1]; for(i=0;i<Terms;i++){//遍歷三元組a，把各個元素按rowStart數(shù)組存在b中相應(yīng)的位置 j=rowStart[smArray[i].col];//a數(shù)組中行號按從小到大的順序排列，所以相同列最先遇到的元素肯定處在相應(yīng)轉(zhuǎn)置矩陣相應(yīng)行中的最前面 b.smArray[j].row=smArray[i].col;//把該元素按照找到的下標j存入b中 b.smArray[j].col=smArray[i].row; b.smArray[j].value=smArray[i].value; rowStart[smArray[i].col]++;//因為該值已經(jīng)存入b，所以轉(zhuǎn)置矩陣的該行下一個元素在b中對應(yīng)的下標為rowStart[smArray[i].col]++； } } delete[]rowSize;//釋放new申請的存儲空間 delete[]rowStart; returnb;}SparseMatrixSparseMatrix::Add(SparseMatrix&b){//轉(zhuǎn)置矩陣的加法 SparseMatrixResult(Rows*Cols);//結(jié)果存于Result里面 if(Rows!=b.Rows||Cols!=b.Cols){//規(guī)格相同的矩陣才能相加 cout<<"Incompatiblematrices"<<endl; returnResult; } Result.Rows=Rows; Result.Cols=Cols; Result.Terms=0; Result.maxTerms=Rows*Cols; inti=0,j=0,index_a,index_b;//i：遍歷a三元組；index_a:當前所指的a中元素在矩陣中的位置； while(i<Terms&&j<b.Terms){ index_a=smArray[i].row*Cols+smArray[i].col; index_b=b.smArray[j].row*b.Cols+b.smArray[i].col; if(index_a<index_b){//當前所指的a，b中兩個元素，a中元素位置在前 Result.smArray[Result.Terms].row=smArray[i].row;//直接把a的元素放在Result里面 Result.smArray[Result.Terms].col=smArray[i].col; Result.smArray[Result.Terms].value=smArray[i].value; i++;//i指針指向a中下一個元素 } if(index_a>index_b){ Result.smArray[Result.Terms].row=b.smArray[j].row; Result.smArray[Result.Terms].col=b.smArray[j].col; Result.smArray[Result.Terms].value=b.smArray[j].value; j++; } if(index_a==index_b){//位置相同 if(smArray[i].value+b.smArray[j].value){//如果兩個值相加的和不為零 Result.smArray[Result.Terms].row=smArray[j].row;//把相加的結(jié)果放在Result中 Result.smArray[Result.Terms].col=smArray[j].col; Result.smArray[Result.Terms].value=smArray[i].value+b.smArray[j].value; i++; j++; } } Result.Terms++;//存一個元素，非零元素的個數(shù)+1； } for(;i<Terms;i++){//b中元素已經(jīng)遍歷完，把a剩余的元素放入Result里面，此時i所指的第一個元素位置肯定在b中最后一個元素后面 Result.smArray[Result.Terms].row=smArray[i].row; Result.smArray[Result.Terms].col=smArray[i].col; Result.smArray[Result.Terms].value=smArray[i].value; i++; Result.Terms++; } for(;j<b.Terms;j++){ Result.smArray[Result.Terms].row=b.smArray[j].row; Result.smArray[Result.Terms].col=b.smArray[j].col; Result.smArray[Result.Terms].value=b.smArray[j].value; j++; Result.Terms++; } returnResult;}SparseMatrixSparseMatrix::Multiply(SparseMatrix&b){//矩陣的乘法 SparseMatrixResult(Rows*b.Cols);//存放矩陣相乘的結(jié)果 if(Cols!=b.Rows){//兩個矩陣能相乘的先決條件：第一個的列數(shù)等于第二個的行數(shù) cerr<<"Incompatiblematrices"<<endl; returnResult; } int*rowSize=newint[b.Rows];//b矩陣每行的非零元素個數(shù) int*rowStart=newint[b.Rows+1];//b矩陣每行第一個非零元素在b中的下標；為何加一？ int*temp=newint[b.Cols];//暫時存放