CSCI 132 Data Structures--Spring 2014

Assignment 6 Solutions

Solution list_functions.cc code:

/*******************************************************************
* Name: Brenda Student
* Date: 3/22/14
* Course: CSCI 132 Section 01
* Assignment: Assignment 6
* Instructor: Royden
* Program: list_functions.cc
* Purpose:  Implementation of various useful list functions and
* a main program to test them.
***************************************************************************/
#include <iostream>
#include "list.h"
#include "list.cc"
using namespace std;


Error_code interchange(int pos1, int pos2, List &a_list)
/* Post: Any entries at positions pos1 and pos2 of List a_list are interchanged. If either entry is
missing a code of range_error is returned. */
{
	List_entry entry1, entry2;	//entry values to be interchanged
	Error_code outcome = a_list.retrieve(pos1, entry1);
	if (outcome == success)
		outcome = a_list.retrieve(pos2, entry2);
	if (outcome == success)
		outcome = a_list.replace(pos1, entry2);
	if (outcome == success)
		outcome = a_list.replace(pos2, entry1);
	return outcome;
}	//end interchange()

void reverse_traverse_list(List &a_list, void (*visit)(List_entry &))
/* Post: The List a_list is traversed, in reverse order, and the function *visit is applied to all
entries. */
{
	List_entry item;	//temporary storage for list items
	for (int i = a_list.size( ) - 1; i >= 0; i--) {
		a_list.retrieve(i, item);
	(*visit)(item);
	} //endfor
} // end reverse_traverse_list()


Error_code join(List &list1, List &list2)
/* Post: All entries from list1 are copied onto the end of list2. A code of overflow is returned if
list2 is filled up before the copying is complete. */
{
	List_entry item;  //temporary storage for list items
	for (int i = 0; i < list1.size( ); i++) {
		list1.retrieve(i, item);
		if (list2.insert(list2.size( ), item) != success)
			return overflow;
	} //end for
	return success;
}  //end join()

void reverse(List &a_list)
/* Post: Reverses the order of all entries in a_list. A code of fail is returned in case the reversal
cannot be completed. */
{
	List temp;         //temporary list for reversing
	List_entry item;   //temporary storage for list items
	Error_code outcome = success;
	for (int i = 0; i < a_list.size( ); i++) {
		a_list.retrieve(i, item);
		if (temp.insert(i, item) != success)
			outcome = fail;
	} //end for
	for (int j = 0; j < a_list.size( ); j++) {
		temp.retrieve(j, item);
		a_list.replace(a_list.size( ) - 1 - j, item);
	} //end for
} //end reverse()

Error_code split(List &source, List &oddlist, List &evenlist)
/* Post: Copies all entries from source so that those in odd-numbered positions make up oddlist
and those in even-numbered positions make up evenlist. Returns an error code of
overflow in case either output list fills before the copy is complete. */
{
	List_entry item;	//temporary storage for list items
	Error_code outcome = success;
	for (int i = 0; i < source.size( ); i++) {
		source.retrieve(i, item);
		if (i % 2 != 0) {
			if (oddlist.insert(oddlist.size( ), item) == overflow)
				outcome = overflow;
		} else {
			if (evenlist.insert(evenlist.size( ), item) == overflow)
				outcome = overflow;
		}  //end if-else
	} //end for
	return outcome;
} //end split()

void print(int &x) {
/* Post: Print out value of x */
  cout << x << " ";
} //end print()


/*Program to test list functions*/
int main(void) {
	List myList;
	
	cout << "Creating list. " << endl;
	
	for (int i = 0; i < 10; i++) {
		myList.insert(i, i);
	}
	
	myList.traverse(print);
	
	cout << endl << endl << "Interchanging positions 2 and 3 of list. " << endl;
	Error_code outcome = interchange(2, 3, myList);
	if (outcome != success) {
		cout << "Error in interchange: " << outcome << endl;
	} else {
		myList.traverse(print);
	}
	
	cout << endl << endl << "Switching positions 2 and 3 back to original positions. " << endl;
	outcome = interchange(2, 3, myList);
	if (outcome != success) {
		cout << "Error in interchange: " << outcome << endl;
	} else {
		myList.traverse(print);
	}

	cout << endl << endl << "Printing list in reverse. " << endl;
	reverse_traverse_list(myList, print);
	
	cout << endl << endl << "Splitting list into odds and evens. " << endl;
	List oddList, evenList;
	outcome = split(myList, oddList, evenList);
	if (outcome != success) {
		cout << "Error in splitting list: " << outcome << endl;
	} else {
		cout << "Printing odd list. " << endl;
		oddList.traverse(print);
		cout << endl << endl << "Printing even list. " << endl;
		evenList.traverse(print);
	}
	
	cout << endl << endl << "Joining odd and even lists." << endl;
	outcome = join(oddList, evenList);
	if (outcome != success) {
		cout << "Error in joining lists. " << outcome << endl;
	} else {
		evenList.traverse(print);
	}
	
	cout << endl << endl << "Reversing list. " << endl;
	reverse(evenList);
	evenList.traverse(print);
	
	cout << endl;
	return 0;
} //end main()