计算两个字符串链表中的共同数据项，需要考虑重复选项的情况

Problem
/*
// Given two lists of strings build a new list that has all strings that appear in both the original lists. If the same string appears more than once output it as many times as it appears in both lists
//
// Example:
// "dog", "bird", "elephant", "dog", "dog", "cat"
// "cat", "dog", "dog", "cat", "cat", "fish"
// Result (order doesn't matter)
// "dog", "dog", "cat"

*/

Solution
[cpp]
#include
#include
#include
#include
#include

using namespace std;

void find_comm_strings(list& output, list& listA, list& listB)
{
listA.sort();
listB.sort();

list::const_iterator citA = listA.begin();
list::const_iterator citB = listB.begin();

while(citA != listA.end() && citB != listB.end()){
int eq = (*citA).compare(*citB);
if(eq == 0){
output.push_back(*citA);
citA ++;
citB ++;
}
else if (eq > 0){
citB ++;
}
else{
citA ++;
}
}
}

int main(int argc, char* argv[])
{
list listA;
list listB;
list output;

cout << "list A:" << endl;
listA.push_back("dog");
listA.push_back("bird");
listA.push_back("elephant");
listA.push_back("dog");
listA.push_back("dog");
listA.push_back("cat");
copy(listA.begin(), listA.end(), ostream_iterator(cout, ","));
cout << endl;

cout << "list B:" << endl;
listB.push_back("cat");
listB.push_back("dog");
listB.push_back("dog");
listB.push_back("cat");
listB.push_back("cat");
listB.push_back("fish");
copy(listB.begin(), listB.end(), ostream_iterator(cout, ","));
cout << endl;

find_comm_strings(output, listA, listB);

cout << "common strings" << endl;
copy(output.begin(), output.end(), ostream_iterator(cout, ","));
cout << endl;

return 0;
}

#include
#include
#include
#include
#include

using namespace std;

void find_comm_strings(list& output, list& listA, list& listB)
{
listA.sort();
listB.sort();

list::const_iterator citA = listA.begin();
list::const_iterator citB = listB.begin();

while(citA != listA.end() && citB != listB.end()){
int eq = (*citA).compare(*citB);
if(eq == 0){
output.push_back(*citA);
citA ++;
citB ++;
}
else if (eq > 0){
citB ++;
}
else{
citA ++;
}
}
}

int main(int argc, char* argv[])
{
list listA;
list listB;
list output;

cout << "list A:" << endl;
listA.push_back("dog");
listA.push_back("bird");
listA.push_back("elephant");
listA.push_back("dog");
listA.push_back("dog");
listA.push_back("cat");
copy(listA.begin(), listA.end(), ostream_iterator(cout, ","));
cout << endl;

cout << "list B:" << endl;
listB.push_back("cat");
listB.push_back("dog");
listB.push_back("dog");
listB.push_back("cat");
listB.push_back("cat");
listB.push_back("fish");
copy(listB.begin(), listB.end(), ostream_iterator(cout, ","));
cout << endl;

find_comm_strings(output, listA, listB);

cout << "common strings" << endl;
copy(output.begin(), output.end(), ostream_iterator(cout, ","));
cout << endl;

return 0;
}
Output
[cpp]
list A:
dog,bird,elephant,dog,dog,cat,
list B:
cat,dog,dog,cat,cat,fish,
common strings
cat,dog,dog,
Press any key to continue . . .

list A:
dog,bird,elephant,dog,dog,cat,
list B:
cat,dog,dog,cat,cat,fish,
common strings
cat,dog,dog,
Press any key to continue . . .