数据结构与算法设计PPT (11).pdf

《数据结构与算法设计PPT (11).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (11).pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3章 字符串与数组3.1 字符串抽象数据类型字符串(String)字符串是n(0)个字符的有限序列，记作S:“c1c2c3cn”其中，S 是串名字“c1c2c3cn”是串值ci 是串中字符n 是串的长度。const intmaxLen=128;class String intcurLen;/串的当前长度char*ch;/串的存储数组public:String(const String&ob);String(const char*init);String();String()delete ch;intLength()const returncurLen;字符串抽象数据类型和类定义String&

2、operator()(intpos,int len);int operator=(constString&ob)const return strcmp(ch,ob.ch)=0;int operator!=(constString&ob)const return strcmp(ch,ob.ch)!=0;int operator!()const return curLen=0;String&operator=(constString&ob);String&operator+=(constString&ob);char&operator (int i);int Find(String&pat)con

3、st;字符串操作类型的特点 字符串中是一个线性结构，数据元素是字符 线性表主要做数据元素的插入删除 字符串是子串的查找、插入和删除操作String:String(constString&ob)/复制构造函数：从已有串ob复制ch=new charmaxLen+1;if(!ch)cerr “存储分配错 n”;exit(1);curLen=ob.curLen;strcpy(ch,ob.ch);字符串部分操作的实现String:String(const char*init)/复制构造函数:从已有字符数组*init复制ch=new charmaxLen+1;if(!ch)cerr “存储分配错 n”;

4、exit(1);curLen=strlen(init);strcpy(ch,init);String:String()/构造函数：创建一个空串ch=new charmaxLen+1;if(!ch)cerr “存储分配错n”;exit(1);curLen=0;ch0=0;提取子串的算法示例pos+len-1 pos+len-1 curLen-1 curLenString&String:operator()(int pos,intlen)/从串中第pos 个位置起连续提取len个字符形/成子串返回String*temp=new String;/动态分配if(pos=maxLen|len=curLe

5、n)len=curLen-pos;tempcurLen=len;/子串长度for(inti=0,j=pos;i len;i+,j+)tempchi=chj;/传送串数组tempchlen=0;/子串结束return*temp;例：串st=“university”,pos=3,len=4使用示例subSt=st(3,4)提取子串subSt为“vers”String&String:operator=(constString&ob)/串赋值：从已有串ob复制if(&ob!=this)delete ch;ch=new char maxLen+1;/重新分配if(!ch)cerr “内存不足!n”;ex

6、it(1);curLen=ob.curLen;/串复制strcpy(ch,ob.ch);else cout “字符串自身赋值出错!n”;return*this;char&String:operator (int i)/按串名提取串中第i个字符if(i=curLen)cout “字符串下标超界!n”;exit(1);return chi;例：串st=“university”,使用示例newSt=st；newChar=st1;数组赋值newSt=“university”提取字符newChar=nString&String:operator+=(const String&ob)/串连接char*temp=ch;/暂存原串数组curLen+=ob.curLen;/串长度累加ch=new char maxLen+1;if(!ch)cerr “字符串下标超界!n”;exit(1);strcpy(ch,temp);/拷贝原串数组strcat(ch,ob.ch);/连接ob串数组delete temp;return*this;例：串st1=“beijing”,st2=“university”,使用示例st1+=st2;连接结果st1=“beijing university”st2=“university”