linked list Looking for an assist to modify this program based on the following

Question

linked list Looking for an assist to modify this program based on the following info: Using two temporary linked list iterators: linkedListIterator tmp1; // Use for the topHalf of the list linkedListIterator tmp2; // Use for the lowerHalf of the list and three for-loops. modify a linked list with a perfectShuffle (); function (only modify the TODO line of code).. Here is the driver code: #include #include #include "linkedList.h" using namespace std; template void printList(linkedListType& list); template void perfectShuffle(linkedListType& list); int main(int argc, char **argv) { // Declare list variables linkedListType list; // Add some data to list 1 list.insertLast(121); list.insertLast(3); list.insertLast(541); list.insertLast(108); list.insertLast(634); list.insertLast(171); list.insertLast(189); list.insertLast(311); list.insertLast(234); list.insertLast(876); // Print out the lists cout << " List: "; printList(list); cout << endl; perfectShuffle(list); cout << " Perfect Shuffled: "; printList(list); return 0; } template void printList(linkedListType& list) { for (linkedListIterator itr = list.begin(); itr != list.end(); ++itr) { cout << *itr << " "; } return; } template void perfectShuffle(linkedListType& list) { // TODO: implement the details for a perfect shuffle return; } Use a for-loop to find the middle element in the list (e.g. list.length()/2) and insert it into the top half temporary list. Then delete if from the main list. Use another for-loop to divide the main list into two lists by inserting the elements into the two temporary lists. Use a third for-loop to merge the lists. Output: The output of the program after both functions are implemented will be: List: 121 3 541 108 634 171 189 311 234 876 Perfect Shuffled: 171 634 121 189 3 311 541 234 108 876 ** Press any key to continue **

Explanation / Answer

#include
#include
#include
#include

using namespace std;

typedef list LIST; // linked list type
typedef LIST::size_type LIST_SIZE; // size type for list, e.g., unsigned
typedef LIST::iterator LIST_ITER; // iterator type
typedef LIST::value_type LIST_CONTAINS; // type in the list, i.e., a string

void merge_sort(LIST_ITER beg, LIST_ITER end, LIST_SIZE sz);
void merge(LIST_ITER bLeft, LIST_ITER bRight, LIST_ITER end);

int main()
{
LIST l;
LIST_CONTAINS v;
// Read in the data...
while (cin >> v)
l.push_back(v);
// Merge the data...

LIST_ITER i = l.begin();
LIST_ITER iEnd = l.end();
merge_sort(i, iEnd, v.size());
// Output everything...
for (; i != iEnd; ++i)
{
cout << *i << ' ';
}
system("pause");
}

void merge_sort(LIST_ITER beg, LIST_ITER end, LIST_SIZE sz)
{
if(sz < 2)
{
return;
}
else
{
LIST_SIZE halfsz = (distance(beg, end)/2); //half of list size
LIST_ITER i1End = beg; //iterator for the end of the first list
advance(i1End, halfsz); //advance to the midpoint
i2 = i1End++; //iterator for the beginning of the second list
--end;//iterator for the end of the second list

merge_sort(beg, i1End, halfsz); //recursively pass first list
merge_sort(i2, end, halfsz); //recursively pass second list
}
merge(beg, i2, end);
}

void merge(LIST_ITER bLeft, LIST_ITER bRight, LIST_ITER end)
{

LIST temp;
LIST_ITER beg = bLeft;
LIST_ITER halfw = bRight;
LIST_ITER i = temp.begin();


while(beg != bRight && halfw != end)
{
if(*beg < *halfw)
{
temp.push_back(*halfw);
halfw++;
}
else
{
temp.push_back(*beg);
beg++;
}
}

while(beg != bRight)
{
temp.push_back(*beg);
beg++;
}
while(halfw != end)
{
temp.push_back(*halfw);
halfw++;
}

while(bLeft != end) ///HERE IS THE PREVIOUSLY POSTED CODE
{
*bLeft = *i;
++i;
++bLeft;
}

}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.