排序動態分配數組

Question

由於某種原因，我無法發現導致我失敗測試用例的錯誤。即時通訊編寫一個功能，應該做到以下幾點。

int separate(string a[], int n, string separator); 
Rearrange the elements of the array so that all the elements whose value is < separator come before all the other elements, and all the elements whose value is > separator come after all the other elements. Return the position of the first element that, after the rearrangement, is not < separator, or n if there are no such elements. For example, 
string cand[6] = { "donald", "jill", "hillary", "tim", "evan", "bill" }; 
int x = separate(cand, 6, "gary"); // returns 3 
// cand must now be 
//  "donald" "evan" "bill" "jill" "tim" "hillary" 
// or "evan" "bill" "donald" "hillary" "jill" "tim" 
// or one of several other orderings. 
// All elements < "gary" (i.e., "evan", "bill", and "donald") 
// come before all others 
// All elements > "gary" (i.e., "tim", "jill", and "hillary") 
// come after all others 

我的方法是使用動態分配的數組來存儲大於分隔符的值。

int split(string a[], int n, string separator){ 

int lessThanSep = 0; 
int greatThanSep = 0; 

for(int i = 0; i < n; i++){ 
    if(a[i] < separator){ //adding the number that are less Than Seperator 
     lessThanSep++; 
    } 
    else if(a[i] > separator){ //adding the number that are Greater Than  Seperator 
     greatThanSep++; 
    } 
} 
int finalSize = greatThanSep + lessThanSep; 

string *lessThan = new string[lessThanSep](); 
string *greatThan = new string[greatThanSep](); 

string *final = new string[finalSize](); 


for(int i = 0; i < n; i++){ 
    if(a[i] < separator){ //adding the number that are less Than Seperator 
     lessThan[i] = a[i]; 
    } 
    else if(a[i] > separator){ //adding the number that are Greater Than Seperator 
     greatThan[i] = a[i]; 
    } 
} 
for(int i = 0; i < lessThanSep; i++) 
    final[i] = lessThan[i]; 

for(int i = lessThanSep; i < greatThanSep; i++) 
    final[i] = greatThan[i]; 

for(int i = 0; i < finalSize; i++){ 
    if(final[i] > separator) 
     return i; 
} 

return n; 
} 

這裏是我的測試用例...第一個。

void testSplit() 
    { 
    string stuffAns[] = {"animals", "bagels", "camels", "dolphins", "earwax"}; 
    string stuff1[] = {"animals", "bagels", "camels", "dolphins", "earwax"}; 
    string stuff2[] = {"animals", "bagels", "camels", "dolphins", "earwax"}; 
    string stuff3[] = {"animals", "bagels", "camels", "dolphins", "earwax"}; 
    string stuff4[] = {"animals", "bagels", "camels", "dolphins", "earwax"}; 
    string stuff5[] = {"animals", "bagels", "camels", "dolphins", "earwax"}; 

assert(split(stuff1, 5, "camels")==2); //test if a sorted array (target in the middle) returns the right index 
assert(split(stuff2, 5, "animals")==0); //test if a sorted array (target in the front) returns the right index 
assert(split(stuff3, 5, "az")==1); //test if a sorted array (target nonexistent but at index 1) returns the right index 
assert(split(stuff4, 5, "ear")==4); //test if a sorted array (target one before the end) returns the right index 
assert(split(stuff5, 5, "ez")==5); //test if n is returned if all strings are less than "ez" 

for(int k=0; k<5; k++) //check that no arrays are changed, since they were already sorted 
{ 
    assert(stuff1[k]==stuffAns[k]); 
    assert(stuff2[k]==stuffAns[k]); 
    assert(stuff3[k]==stuffAns[k]); 
    assert(stuff4[k]==stuffAns[k]); 
    assert(stuff5[k]==stuffAns[k]); 
} 


string stuffAns6[] = {"c", "b", "a", "q", "d", "z"}; 
string stuffAns7[] = {"c", "d", "q", "b", "a", "z"}; 
string stuff6[] = {"c", "q", "d", "b", "a", "z"}; 
string stuff7[] = {"c", "q", "d", "b", "a", "z"}; 

assert(split(stuff6, 6, "ce")==3); //see if correct position is returned in an unsorted array 

for(int k=0; k<5; k++) 
{ 
    assert(stuff6[k]==stuffAns6[k]); //see if the array is sorted as expected 
} 

assert(split(stuff7, 3, "darnit")==2); //see if correct position is returned in an unsorted array 

for(int k=0; k<5; k++) 
{ 
    assert(stuff7[k]==stuffAns7[k]); //see if the array is sorted as expected 
} 

cerr << "All tests for split() succeeded!" << endl; 
} 

任何幫助將不勝感激。

Answer 1

除非你必須使用數組，我可以建議使用std :: list嗎？你分割功能看起來更清潔和更簡單的使用這個庫：

int split(list<string> &L, int n, string S) { 
    list<string> temp; 
    int m = 0; 
    for (list<string>::iterator i = L.begin(); i != L.end(); i++) { 
     if (*i < S) temp.push_front(*i); 
     else { 
      temp.push_back(*i); 
      m++; 
     } 
    } 
    L.swap(temp); 
    return m ? L.size() - m : n; 
} 

旁註：你沒有平等字符串例外，所以我只是把它們與值越高字符串後面。