排序动态分配数组

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; 
} 

旁注：你没有平等字符串例外，所以我只是把它们与值越高字符串后面。