字符串連接問題

姓名：王繼宏學(xué)號：100321058字符串連接問題字符串連接問題任務(wù)描述分析問題解決方案選擇算法提升性能核心代碼任務(wù)描述所謂字符串連接問題是指將n個字符串前后拼接成一個字符串。不同的接力方式將得到不同的結(jié)果。例如n=3時，3個字符串a(chǎn)b，aa，cd

相互連接可能的結(jié)果有：aaabcd，aacdab，abaacd，abcdaa，cdaaab，cdabaa。對于給定的n個字符串，找出一種最佳的連接方式，使得采用該連接方式得到的字符串在所有連接的結(jié)果中，字典序最小。分析問題問題核心使得給定的n個字符串連接后的字典序最小問題轉(zhuǎn)換將給定字符串按照字典序排序的原理，以字典序升序的方式由小到大進行排序。問題實質(zhì)綜上所述，該問題的實質(zhì)為對字符串進行字典序比較排序，即：排序問題字典序兩個字符串的字典序比較通過逐個比較兩個字符串中字符的ASCII碼，ASCII碼小的字典序小，反之則大。多個字符串連接后的字典序比較與單個字符串間的比較有不同之處；字符串的字典序，在字符串與其他字符串連接后，字典序出現(xiàn)變化；例如too與toooo相比，too的字典序小，按照由小到大的方式連接后，tootoooo的字典序大于tooootoo解決方案比較兩個字符串連接后的字典序可以將兩個字符串以兩種不同的連接方式連接，再將連接后的字符串進行比較，再根據(jù)比較結(jié)果，判定最終結(jié)果。根據(jù)以上的比較方式，對給定的n個字符串進行比較排序，排序結(jié)果為最佳的連接方式。選擇算法基于比較的排序算法有冒泡排序、插入排序、選擇排序以及快速排序。冒泡排序、插入排序、選擇排序這三種算法在最壞及平均情況下需要O(n2)計算時間?？焖倥判蛑恍枰狾(nLogn)時間。所以算法上選擇使用快速排序。提升性能根據(jù)前面的情況，我們可以了解到，在算法執(zhí)行的過程中，主要的兩個操作為字符串位置的移動以及字符串的字典序比較。提升性能字符串位置的移動一般情況下可以通過string的swap()函數(shù)來實現(xiàn)。但是查看swap()的源代碼后，發(fā)現(xiàn)該函數(shù)的操作相對較多； 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; }}為避免過多的操作，可以使用一個指向字符串的指針數(shù)組來保存字符串，需要交換位置時，直接對指針進行操作可提高效率。提升性能字符串的字典序比較一般情況下可以使用以下的代碼實現(xiàn)strings1,s2;stringstrTemp1,strTemp2;strTemp1=s1+s2;strTemp2=s2+s1;strTemp>strTemp2;從以上的代碼可以看出，在每一次的比較中，都會有兩次以下操作。分配一塊內(nèi)存將s1,s2的內(nèi)容分別復(fù)制到新內(nèi)存比較結(jié)束后釋放strTemp1、strTemp2內(nèi)存頻繁的內(nèi)存申請和釋放操作會增加系統(tǒng)開銷。設(shè)計一個函數(shù)，根據(jù)字典序的比較方式，逐一對兩個字符進行比較，避免內(nèi)存的申請和釋放；該函數(shù)的參數(shù)為參加比較的兩個字符串的引用。引用類型的參數(shù)可以避免傳值過程的拷貝操作。核心代碼//---------------------------------------------//比較兩個字符串的字典序//大于返回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