数据结构 二维码文件第6章主要算法的C++代码

第6章主要算法的C++代码顺序串的基本操作：/*顺序串的实现C++*/#include<iostream>usingnamespacestd;constintMAX_N=100;//定义数据类型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; } //复制串 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++){ //内容不等 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开始连续j个字符，返回新串，参数不正确时返回空串 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开始，返回新串，参数不正确时返回空串 SqStrInsertStr(Strings1,inti){ SqStrstr; str.length=0; //i为位置，与数组下标差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开始的连续j个字符，生成新串并返回，参数不正确时返回空串 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,生成新串并返回，参数不正确返回空串 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; } } //输出串（不带参数） voidDisplayStr(){ //空串处理 if(S.length==0){ cout<<"Empty."<<endl; } //否则输出串 else{ inti; for(i=0;i<S.length;i++){ cout<<S.data[i]; } cout<<endl; } } //输出串（带参数） 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{//自定义数据结构：矩阵元素的行，列，值； 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;//行数，列数，非零元素的个数 Trituple*smArray;//存非零元素的三元数组 intmaxTerms;//三元组最大可容纳的元素个数public: SparseMatrix(intmaxSz=DefaultSize);//构造函数 SparseMatrix(SparseMatrix&SM);//赋值构造函数 ~SparseMatrix();//析构函数 SparseMatrix&operator=(SparseMatrix&SM);//赋值运算符重载 SparseMatrixTranspose();//矩阵转置 SparseMatrixAdd(SparseMatrix&b);//矩阵的加法 SparseMatrixMultiply(SparseMatrix&b);//矩阵的乘法 friendostream&operator<<(ostream&ostr,SparseMatrix&SM);//矩阵的输出重载函数 friendistream&operator>>(istream&istr,SparseMatrix&SM);//矩阵的输入重载函数};SparseMatrix::SparseMatrix(intmaxSz):maxTerms(maxSz){//构造函数：构造一个大小为maxTerm的三元组，行列数和非零元素个数都置零 if(maxSz<1){ cerr<<"矩阵初始化错误！"<<endl; exit(1); } smArray=newTrituple[maxSz]; assert(smArray!=NULL); Rows=Cols=Terms=0;}SparseMatrix::SparseMatrix(SparseMatrix&SM){//复制构造函数 Rows=SM.Rows;//赋值矩阵的性质 Cols=SM.Cols; Terms=SM.Terms; maxTerms=SM.maxTerms; smArray=newTrituple[maxTerms];//构造三元组并赋与SM相同的值 assert(smArray!=NULL); for(inti=0;i<Terms;i++) smArray[i]=SM.smArray[i];}SparseMatrix::~SparseMatrix(){//析构函数：释放所有存储 delete[]smArray;}SparseMatrix&SparseMatrix::operator=(SparseMatrix&SM){//赋值运算符重载 Rows=SM.Rows;//元素性质的赋值 Cols=SM.Cols; Terms=SM.Terms; maxTerms=SM.maxTerms; for(inti=0;i<Terms;i++)//三元组所有元素赋值 smArray[i]=SM.smArray[i]; return*this;//返回的是对调用该函数的对象的引用，需显式使用this指针；}ostream&operator<<(ostream&ostr,SparseMatrix&SM){//输出运算符重载（为啥代模板就不能调用row？） ostr<<"#Rows="<<SM.Rows<<endl;//输出该矩阵的性质 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;//输入元素的性质 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(){//转置函数 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(){//转置函数 int*rowSize=newint[Cols];//转置矩阵每行非零元素的个数 int*rowStart=newint[Cols];//转置矩阵每行第一个非零元素对应其三元组的下标 SparseMatrixb(maxTerms);//转置后的矩阵对应的三元组 b.Rows=Rows;//b的性质 b.Cols=Cols; b.Terms=Terms; b.maxTerms=maxTerms; if(Terms>0){ inti,j,CurrentB=0; for(i=0;i<Cols;i++)//对rowSize数组赋值 rowSize[i]=0; for(i=0;i<Terms;i++) rowSize[smArray[i].col]++; rowStart[0]=0;//对rowStart数组赋值 for(i=1;i<b.Rows;i++) rowStart[i]=rowStart[i-1]+rowSize[i-1]; for(i=0;i<Terms;i++){//遍历三元组a，把各个元素按rowStart数组存在b中相应的位置 j=rowStart[smArray[i].col];//a数组中行号按从小到大的顺序排列，所以相同列最先遇到的元素肯定处在相应转置矩阵相应行中的最前面 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]++;//因为该值已经存入b，所以转置矩阵的该行下一个元素在b中对应的下标为rowStart[smArray[i].col]++； } } delete[]rowSize;//释放new申请的存储空间 delete[]rowStart; returnb;}SparseMatrixSparseMatrix::Add(SparseMatrix&b){//转置矩阵的加法 SparseMatrixResult(Rows*Cols);//结果存于Result里面 if(Rows!=b.Rows||Cols!=b.Cols){//规格相同的矩阵才能相加 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;//把相加的结果放在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++;//存一个元素，非零元素的个数+1； } for(;i<Terms;i++){//b中元素已经遍历完，把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);//存放矩阵相乘的结果 if(Cols!=b.Rows){//两个矩阵能相乘的先决条件：第一个的列数等于第二个的行数 cerr<<"Incompatiblematrices"<<endl; returnResult; } int*rowSize=newint[b.Rows];//b矩阵每行的非零元素个数 int*rowStart=newint[b.Rows+1];//b矩阵每行第一个非零元素在b中的下标；为何加一？ int*temp=newint[b.Cols];//暂时存放