字符串连接问题

姓名：王继宏学号：100321058字符串连接问题字符串连接问题任务描述分析问题解决方案选择算法提升性能核心代码任务描述所谓字符串连接问题是指将n个字符串前后拼接成一个字符串。不同的接力方式将得到不同的结果。例如n=3时，3个字符串ab，aa，cd

相互连接可能的结果有：aaabcd，aacdab，abaacd，abcdaa，cdaaab，cdabaa。对于给定的n个字符串，找出一种最佳的连接方式，使得采用该连接方式得到的字符串在所有连接的结果中，字典序最小。分析问题问题核心使得给定的n个字符串连接后的字典序最小问题转换将给定字符串按照字典序排序的原理，以字典序升序的方式由小到大进行排序。问题实质综上所述，该问题的实质为对字符串进行字典序比较排序，即：排序问题字典序两个字符串的字典序比较通过逐个比较两个字符串中字符的ASCII码，ASCII码小的字典序小，反之则大。多个字符串连接后的字典序比较与单个字符串间的比较有不同之处；字符串的字典序，在字符串与其他字符串连接后，字典序出现变化；例如too与toooo相比，too的字典序小，按照由小到大的方式连接后，tootoooo的字典序大于tooootoo解决方案比较两个字符串连接后的字典序可以将两个字符串以两种不同的连接方式连接，再将连接后的字符串进行比较，再根据比较结果，判定最终结果。根据以上的比较方式，对给定的n个字符串进行比较排序，排序结果为最佳的连接方式。选择算法基于比较的排序算法有冒泡排序、插入排序、选择排序以及快速排序。冒泡排序、插入排序、选择排序这三种算法在最坏及平均情况下需要O(n²)计算时间。快速排序只需要O(nLogn)时间。所以算法上选择使用快速排序。提升性能根据前面的情况，我们可以了解到，在算法执行的过程中，主要的两个操作为字符串位置的移动以及字符串的字典序比较。提升性能字符串位置的移动一般情况下可以通过string的swap()函数来实现。但是查看swap()的源代码后，发现该函数的操作相对较多； voidswap(_Myt&_X){ if(allocator==_X.allocator){

std::swap(_Ptr,_X._Ptr);

std::swap(_Len,_X._Len);

std::swap(_Res,_X._Res); }else{

Myt_Ts=*this;*this=_X,_X=_Ts; }}为避免过多的操作，可以使用一个指向字符串的指针数组来保存字符串，需要交换位置时，直接对指针进行操作可提高效率。提升性能字符串的字典序比较一般情况下可以使用以下的代码实现strings1,s2;stringstrTemp1,strTemp2;strTemp1=s1+s2;strTemp2=s2+s1;strTemp>strTemp2;从以上的代码可以看出，在每一次的比较中，都会有两次以下操作。分配一块内存将s1,s2的内容分别复制到新内存比较结束后释放strTemp1、strTemp2内存频繁的内存申请和释放操作会增加系统开销。设计一个函数，根据字典序的比较方式，逐一对两个字符进行比较，避免内存的申请和释放；该函数的参数为参加比较的两个字符串的引用。引用类型的参数可以避免传值过程的拷贝操作。核心代码//---------------------------------------------//比较两个字符串的字典序//大于返回BIGGER//等于返回EQUAL//小于返回SMALLER//---------------------------------------------#defineBIGGER1#defineEQUAL0#defineSMALLER-1int

dictCompare(string&s1,string&s2){

intlen1=s1.length(); if(len1==0)returnSMALLER;

intlen2=s2.length(); if(len2==0)returnBIGGER;

int

totalLen=len1+len2; charc1,c2;

for(inti=0;i<totalLen;i++){

if(i<len1) c1=s1[i]; else c1=s2[i-len1];

if(i<len2) c2=s2[i]; else c2=s1[i-len2]; if(c1<c2)returnSMALLER; if(c1>c2)returnBIGGER; } returnEQUAL;}核心代码//定义字符串指针类型typedefstring*PString;//---------------------------------------------//快速排序//---------------------------------------------voidquicksort(PString*str,intleft,intright){

if((right-left)<=0)return;

stringstrKey=*str[left];

int

keyPos=left+1;

PString

pTemp;

for(inti=left+1;i<=right;i++){

if(dictCompare(strKey,*str[i])==BIGGER){

pTemp=str[i];

str[i]=str[keyPos];

str[keyPos]=pTemp;

keyPos++; } }

pTemp=str[left];

str[left]=str[keyPos-1]; str[keyPos-1]=pTemp;

quicksort(str,left,keyPos-1);

quicksort(str,keyPos,right);}核心代码intmain(){

PString*pStrAry;

intcount;

cin>>count;

pStrAry=newPString[count];

for(inti=0;i<count;i++){

pStrAry[i]=newstring;

cin>>*(pStrAry[i]); } quicksort(pStrAry,0,cou