数据结构与算法

《数据结构与算法》由会员分享，可在线阅读，更多相关《数据结构与算法（67页珍藏版）》请在装配图网上搜索。

1、数据结构与算法2006.9-2007.1#include class szcl int e;public:szcl()e=0;szcl(int value)e=value;int get_value()return e;main()szcl a13=3,5,7,*elem;for(int i=0,i3,i+)cout a1i.get_value()“n”;/打印静态数组打印静态数组 elem=&a1;for(int i=0,i3,i+)cout elemget_value()“n”;/打印动态数组打印动态数组 elem+;return 0;#include#include template c

2、lass Array Type*elements;/数组存放空间数组存放空间 int ArraySize;/当前长度当前长度 void getArray();/建立数组空间建立数组空间 public:Array(int Size=DefaultSize);Array(const Array&x);Array()delete elements;Array&operator=(const Array&A);Type&operato (int i);operator Type*()const return elements;int Length()const return ArraySize;voi

3、d ReSize(int sz);template void Array:getArray()/私有函数：创建数组存储空间私有函数：创建数组存储空间 elements=new TypeArraySize;if(elements=0)cerr Memory Allocation Error endl;template void Array:Array(int sz)/构造函数构造函数 if(sz=0)cerr Invalid Array Size endl;return;ArraySize=sz;getArray();template Array:Array(const Array&x)/复制构

4、造函数复制构造函数 int n=ArraySize=x.ArraySize;elements=new Typen;if(elements=0)cerr Memory Allocation Error endl;Type*srcptr=x.elements;Type*destptr=elements;while(n-)*destptr+=*srcptr+;template Type&Array:operator (int i)/按数组名及下标按数组名及下标i，取数组元素的值，取数组元素的值 if(i ArraySize-1)cerr Index out of Range endl;return

5、elementi;Positioni=Positioni-1+Numberi-1 template void Array:Resize(int sz)if(sz=0&sz!=ArraySize)Type*newarray=new Typesz;if(newarray=0)cerr Memory Allocation Error endl;int n=(sz=ArraySize)?sz:ArraySize;Type*srcptr=elements;Type*destptr=newarray;while(n-)*destptr+=*srcptr+;delete elements;elements=

6、newarray;ArraySize=sz;时时 0 0,)(时时 0 0,)(iliLOCiiLOC1LOC(i)=LOC(i-1)+l=+i*l11211101122212021121110110201000mnanananamaaaamaaaamaaaaa m1,m2,m3,mnnnjnjkkjnnnnnnimiimimmmimmmiiiiLOC111143232121),(,()template class SeqList Type*data;/顺序表存储数组顺序表存储数组 int MaxSize;/最大允许长度最大允许长度 int last;/当前最后元素下标当前最后元素下标publ

7、ic:SeqList(int MaxSize=defaultSize);SeqList()delete data;int Length()const return last+1;int Find(Type&x)const;int IsIn(Type&x);int Insert(Type&x,int i);int Remove(Type&x);int Next(Type&x);int Prior(Type&x);int IsEmpty()return last=-1;int IsFull()return last=MaxSize-1;Type&Get(int i)return i last？NU

8、LL:datai;template SeqList:SeqList(int sz)/构造函数构造函数 if(sz 0)MaxSize=sz;last=-1;data=new TypeMaxSize;template int SeqList:Find(Type&x)const/搜索函数：在表中从前向后顺序查找搜索函数：在表中从前向后顺序查找 x int i=0;while(i last)return-1;else return i;顺序搜索图示 x=48 x=50niniicpACN10=212)(11)2(111)(1=10nnnnnninACNni 221)(1)(1 0)1(11)(11=

9、0nnnnnninnAMNnitemplate int SeqList:Insert(Type&x,int i)/在表中第在表中第 i 个位置插入新元素个位置插入新元素 x if(i last+1|last=MaxSize-1)return 0;/插入不成功插入不成功 else last+;for(int j=last;ji;j-)dataj=dataj-1;datai=x;return 1;/插入成功插入成功 102121)(11)(1=ninnnninnAMN template int SeqList:Remove(Type&x)/在表中删除已有元素在表中删除已有元素 x int i=Fi

10、nd(x);/在表中搜索在表中搜索 x if(i=0)last-;for(int j=i;j=last;j+)dataj=dataj+1;return 1;/成功删除成功删除 return 0;/表中没有表中没有 x template void Union(SeqList&LA,SeqList&LB)int n=LA.Length();int m=LB.Length();for(int i=1;i=m;i+)Type x=LB.Get(i);/在在LB中取一元素中取一元素 int k=LA.Find(x);/在在LA中搜索它中搜索它 if(k=-1)/若未找到插入它若未找到插入它 LA.Ins

11、ert(n+1,x);n+;template void Intersection(SeqList&LA,SeqList&LB)int n=LA.Length();int m=LB.Length();int i=1;while(i n)Type x=LA.Get(i);/在在LA中取一元素中取一元素 int k=LB.Find(x);/在在LB中搜索它中搜索它 if(k=-1)LA.Remove(i);n-;else i+;/未找到在未找到在LA中删除它中删除它 iniinnnxaxaxaxaaxP02210 )(n阶多项式阶多项式Pn(x)有有n+1项。项。系数系数 a0,a1,a2,an 指

12、数指数 0,1,2,n。按升幂排列。按升幂排列class Polynomial public:Polynomial();/构造函数构造函数 int operator!();/判是否零多项式判是否零多项式 Coefficient Coef(Exponent e);Exponent LeadExp();/返回最大指数返回最大指数 Polynomial Add(Polynomial poly);Polynomial Mult(Polynomial poly);float Eval(float x);/求值求值#include class power double x;int e;double mul

13、;public:power(double val,int exp);double get_power()return mul;power:power(double val,int exp)/按按val值计算乘幂值计算乘幂 x=val;e=exp;mul=1.0;if(exp=0)return;for(;exp0;exp-)mul=mul*x;main()power pwr(1.5,2);cout pwr.get_power()“n”;private:int degree;float coef maxDegree+1;pl.degree=n pl.coefi=ai,0 i nprivate:in

14、t degree;float*coef;Polynomial:Polynomial(int sz)degree=sz;coef=new float degree+1;：class Polynomial;class term /多项式的项定义多项式的项定义friend Polynomial;private:float coef;/系数系数 int exp;/指数指数;class Polynomial /多项式定义多项式定义public:private:static term termArrayMaxTerms;/项数组项数组 static int free;/当前空闲位置指针当前空闲位置指针 /

15、term Polynomial:termArrayMaxTerms;/int Polynomial:free=0;int start,finish;/多项式始末位置多项式始末位置 A(x)=2.0 x1000+1.8 B(x)=1.2+51.3x50+3.7x101 两个多项式存放在两个多项式存放在termArray中中Polynomial Polynomial:Add(Polynomial B)Polynomial C;int a=start;int b=B.start;C.start=free;float c;while(a=finish&b :NewTerm(termArrayb.coe

16、f,termArrayb.exp);b+;break;case:NewTerm(termArraya.coef,termArraya.exp);a+;for(;a=finish;a+)/a未检测完时未检测完时 NewTerm(termArraya.coef,termArraya.exp);for(;b=maxTerms)cout Too many terms in polynomials”endl;return;termArrayfree.coef=c;termArrayfree.exp=e;free+;000001500390170000000000602228000000000110091

17、0000B 0000280000000091039000000006000017000110150022000A6776 template class SparseMatrix int Rows,Cols,Terms;/行行/列列/非零元素数非零元素数 Trituple smArrayMaxTerms;public:/三元组表三元组表 SparseMatrix(int MaxRow,int Maxcol);SparseMatrix Transpose();/转置转置 SparseMatrix /相加相加 Add(SparseMatrix b);SparseMatrix /相乘相乘 Multip

18、ly(SparseMatrix b);template class SparseMatrix;template class Trituple friend class SparseMatrix private:int row,col;/非零元素所在行号非零元素所在行号/列号列号 Type value;/非零元素的值非零元素的值 r ra aw w c co ol l v va al lu ue e0000015003901700000000006022280000000001100910000B 0000280000000091039000000006000017000110150022000

19、A6776 行行行行(r ro ow w)列列列列(c co ol l)值值值值(v va al lu ue e)行行行行(r ro ow w)列列列列(c co ol l)值值值值(v va al lu ue e)0 0 0 3 3 2 22 2 0 0 0 4 4 9 91 1 1 0 0 6 6 1 15 5 1 1 1 1 1 1 11 1 2 1 1 1 1 1 11 1 2 2 2 5 5 2 28 8 3 1 1 5 5 1 17 7 3 3 3 0 0 2 22 2 4 2 2 3 3 -6 6 4 3 3 2 2 -6 6 5 3 3 5 5 3 39 9 5 5 5 1 1

20、 1 17 7 6 4 4 0 0 9 91 1 6 5 5 3 3 3 39 9 7 5 5 2 2 2 28 8 7 6 6 0 0 1 16 6 template SparseMatrix SparseMatrix:Transpose()SparseMatrix b;b.Rows=Cols;b.Cols=Rows;b.Terms=Terms;/转置矩阵的列数转置矩阵的列数,行数和非零元素个数行数和非零元素个数 if(Terms 0)int CurrentB=0;/转置三元组表存放指针转置三元组表存放指针 for(int k=0;kCols;k+)for(int i=0;iTerms;i+

21、)if(smArrayi.col=k)b.smArrayCurrentB.row=k;b.smArrayCurrentB.col=smArrayi.row;b.smArrayCurrentB.value=smArrayi.value;CurrentB+;return b;0123456 语语 义义rowSize 1 1 1 2 0 2 1矩矩阵阵 A 各各列列非非零零元元素素个个数数rowStart 0 1 2 3 5 5 7矩矩阵阵 B 各各行行开开始始存存放放位位置置 for(int i=0;iCols;i+)rowSizei=0;for(i=0;iTerms;i+)rowSizesmAr

22、rayi.col+;rowStart0=0;for(i=1;i Cols;i+)rowStarti=rowStarti-1+rowSizei-1;template SparseMatrixSparseMatrix:FastTranspos()int*rowSize=new intCols;int*rowStart=new intCols;SparseMatrix b;b.Rows=Cols;b.Cols=Rows;b.Terms=Terms;if(Terms 0)for(int i=0;iCols;i+)rowSizei=0;for(i=0;iTerms;i+)rowSizesmArrayi.

23、col+;rowStart0=0;for(i=1;i Cols;i+)rowStarti=rowStarti-1+rowSizei-1;for(i=0;iTerms;i+)int j=rowStartsmArrayi.col;b.smArrayj.row=smArrayi.col;b.smArrayj.col=smArrayi.row;b.smArrayj.value=smArrayi.value;rowStartsmArrayi.col+;delete rowSize;delete rowStart;return b;const int maxLen=128;class String int

24、 curLen;/串的当前长度串的当前长度 char*ch;/串的存储数组串的存储数组 public:String(const String&ob);String(const char*init);String();String()delete ch;int Length()const return curLen;String&operator()(int pos,int len);int operator=(const String&ob)const return strcmp(ch,ob.ch)=0;int operator!=(const String&ob)const return s

25、trcmp(ch,ob.ch)!=0;int operator!()const return curLen=0;String&operator=(const String&ob);String&operator+=(const String&ob);char&operator (int i);int Find(String pat)const;String:String(const String&ob)/复制构造函数：复制构造函数：从已有串从已有串ob复制复制 ch=new charmaxLen+1;if(!ch)cout “Allocation Errorn”;exit(1);curLen=

26、ob.curLen;strcpy(ch,ob.ch);String:String(const char*init)/复制构造函数复制构造函数:从已有字符数组从已有字符数组*init复制复制 ch=new charmaxLen+1;if(!ch)cout “Allocation Errorn”;exit(1);curLen=strlen(init);strcpy(ch,init);String:String()/构造函数：创建一个空串构造函数：创建一个空串 ch=new charmaxLen+1;if(!ch)cout “Allocation Errorn”;exit(1);curLen=0;c

27、h0=0;提取子串的算法示例pos+len-1 pos+len-1 curLen-1 curLen String&String:operator()(int pos,int len)/从串中第从串中第pos个位置起连续提取个位置起连续提取len个字符个字符/形成子串返回形成子串返回 if(pos=maxLen|len=curLen)len=curLen-pos;tempcurLen=len;/子串长度子串长度 for(int i=0,j=pos;ilen;i+,j+)tempchi=chj;/传送串数组传送串数组 tempchlen=0;/子串结束子串结束 return temp;String

28、&String:operator=(const String&ob)/串赋值：从已有串串赋值：从已有串ob复制复制 if(&ob!=this)delete ch;ch=new char maxLen+1;/重新分配重新分配 if(!ch)cerr “Out Of Memory!n”;exit(1);curLen=ob.curLen;/串复制串复制 strcpy(ch,ob.ch);else cout “Attempted assignment of a String to itself!n”;return*this;char&String:operator (int i)/按串名提取串中第按串

29、名提取串中第i个字符个字符 if(i=curLen)cout “Out Of Boundary!n”;exit(1);return chi;String&String:/串连接串连接operator+=(const String&ob)char*temp=ch;/暂存原串数组暂存原串数组 curLen+=ob.curLen;/串长度累加串长度累加 ch=new char maxLen+1;if(!ch)cerr “Out Of Memory!n”;exit(1);strcpy(ch,temp);/拷贝原串数组拷贝原串数组 strcat(ch,ob.ch);/连接连接ob串数组串数组 delete temp;return*this;