main.cpp
Code: Select all
#include "linked_array_list.h"
#include <iostream>
using namespace std;
//function main
//PRECONDITIONS: As a testing function, there is minimal error checking
// for valid user input so care should be taken when using
//POSTCONDITIONS: Modifies the linked_array_list object as requested
// until the program is exited
int main()
{
linked_array_list mylist;
char input = ' ';
int tmp;
cout << "**linked_array_list testing program**" << endl;
while (input != 'q')
{
cout << endl << "Select one of the following options: " << endl;
cout << "[i]nsert an integer value into the list" << endl;
cout << "[d]elete an integer value from the list" << endl;
cout << "[v]iew the current contents of the list" << endl;
cout << "[q]uit" << endl;
cin >> input;
switch(input)
{
case 'i':
cout << endl << "Enter a number to add to the list: ";
cin >> tmp;
mylist.insert_data(tmp);
break;
case 'd':
cout << endl << "Enter a number to delete from the list: ";
cin >> tmp;
mylist.delete_data(tmp);
break;
case 'v':
cout << endl << mylist << endl;
break;
case 'q':
break;
default:
cerr << endl << "That is not a valid choice" << endl;
break;
}
}
system("PAUSE");
return 0;
}Code: Select all
#ifndef _LINKED_ARRAY_LIST_H
#define _LINKED_ARRAY_LIST_H
#include "array_node.h"
#include <iostream>
class linked_array_list {
public:
//CONSTRUCTOR for the linked_array_list class
linked_array_list();
linked_array_list(const int& new_data);
//DESTRUCTOR for the linked_array_list class
~linked_array_list();
//MEMBER FUNCTIONS for the linked_array_list class
void insert_data(const int& new_data);
void delete_data(const int& data_value);
//NON-MEMBER FUNCTIONS for the linked_array_list class
friend std::ostream& operator <<(std::ostream& output, const linked_array_list& lal);
private:
//PRIVATE MEMBER FUNCTIONS for the linked_array_list class
void consolidate_array_nodes();
array_node* head_pointer;
array_node* tail_pointer;
};
#endifCode: Select all
#include "linked_array_list.h"
linked_array_list::linked_array_list()
{
head_pointer = new array_node();
tail_pointer = head_pointer;
}
linked_array_list::linked_array_list(const int& new_data)
{
head_pointer = new array_node(new_data);
tail_pointer = head_pointer;
}
linked_array_list::~linked_array_list()
{
array_node* tmp;
while(head_pointer != NULL)
{
tmp = head_pointer;
head_pointer = head_pointer->get_link();
delete tmp;
}
}
void linked_array_list::insert_data(const int& new_data)
{
array_node* tmp;
//check if the data can be stored in an existing node
for (tmp = head_pointer; tmp != NULL; tmp = tmp->get_link())
{
if (tmp->insert_data(new_data))
return;
}
//if no free space found, create a new node to store the data
tmp = new array_node(new_data);
tail_pointer->set_link(tmp);
tail_pointer = tmp;
}
void linked_array_list::delete_data(const int& data_value)
{
array_node* tmp;
//loop through the nodes, deleting all instances of the data_value
for (tmp = head_pointer; tmp != NULL; tmp = tmp->get_link())
tmp->delete_data(data_value);
//check if any nodes can be eliminated
consolidate_array_nodes();
}
//TODO: This code is still problematic
//some corrupted data sometimes finds its way into the nodes
void linked_array_list::consolidate_array_nodes()
{
//if only one node exists, there is no need to consolidate
if (head_pointer == tail_pointer)
return;
//loop through the nodes, looking for half-empty nodes
array_node* tmp_node = head_pointer;
for (; tmp_node != NULL; tmp_node = tmp_node->get_link())
{
//a half-empty node found
if (tmp_node->get_no_free() >= tmp_node->get_no_used())
{
//check for adequate free space in other nodes
size_t free_spaces = 0;
array_node* tmp_node2 = head_pointer;
for (; tmp_node2 != NULL; tmp_node2 = tmp_node2->get_link())
{
if (tmp_node2 != tmp_node)
free_spaces += tmp_node2->get_no_free();
}
if (free_spaces >= tmp_node->get_no_used())
{
//we need to break the node from the list
if (tmp_node != head_pointer)
{
tmp_node2 = head_pointer;
for (; tmp_node2->get_link() != tmp_node; tmp_node2 = tmp_node2->get_link());
tmp_node2->set_link(tmp_node->get_link());
if (tmp_node == tail_pointer)
tail_pointer = tmp_node2;
}
else
head_pointer = tmp_node->get_link();
//redistribute the node's data
unsigned i = 0;
int* tmp_data = tmp_node->get_data();
tmp_node2 = head_pointer;
for (; i < tmp_node->get_no_used(); tmp_node2 = tmp_node2->get_link())
{
while (tmp_node2->insert_data(tmp_data[i]))
++i;
}
//a little housekeeping here
array_node* tmp_delete = tmp_node;
int* tmp_delete_data = tmp_data;
tmp_node = head_pointer;
delete tmp_delete;
delete tmp_delete_data;
}
}
}
}
std::ostream& operator <<(std::ostream& output, const linked_array_list& lal)
{
unsigned i = 1;
array_node* tmp = lal.head_pointer;
//loop through the nodes, adding its data to the ostream
for (; tmp != NULL; tmp = tmp->get_link())
{
output << "Node " << i << std::endl;
output << *tmp << std::endl;
++i;
}
return output;
}Code: Select all
#ifndef _ARRAY_NODE_H
#define _ARRAY_NODE_H
#include <bitset>
#include <iostream>
class array_node{
public:
//CONSTRUCTOR for the array_node class
array_node();
array_node(const int& initial_data);
//ACCESSORS for the array_node class
void set_link(array_node* new_link);
array_node* get_link();
//MEMBER FUNCTIONS for the array_node class
bool insert_data(const int& new_data);
void delete_data(const int& data_value);
int* get_data();
size_t get_no_free();
size_t get_no_used();
//NON-MEMBER FUNCTIONS for the array_node class
friend std::ostream& operator <<(std::ostream& output, const array_node& anode);
private:
static const size_t MAX_SIZE = 5;
int data[MAX_SIZE];
array_node* link;
std::bitset<MAX_SIZE> elements_used;
};
#endifCode: Select all
#include "array_node.h"
array_node::array_node()
:link(NULL)
{}
array_node::array_node(const int& initial_data)
:link(NULL)
{
data[0] = initial_data;
elements_used.flip(0);
}
void array_node::set_link(array_node* new_link)
{
link = new_link;
}
array_node* array_node::get_link()
{
return link;
}
bool array_node::insert_data(const int& new_data)
{
//if true, no free array spots available
if (elements_used.count() == MAX_SIZE)
return false;
//else, look for a free spot to insert the data
size_t i;
for (i = 0; i < MAX_SIZE; ++i)
{
if (!elements_used[i])
{
data[i] = new_data;
elements_used.flip(i);
return true;
}
}
//this line should never be reached
return false;
}
void array_node::delete_data(const int& data_value)
{
//search for data matching data_value
//if found, free it's space
size_t i;
for (i = 0; i < MAX_SIZE; ++i)
{
if (data[i] == data_value)
elements_used.flip(i);
}
}
int* array_node::get_data()
{
//set up a container array
int* data_array = new int[elements_used.count()];
//fill the temp array with node values
size_t i, j = 0;
for (i = 0; i < MAX_SIZE; ++i)
{
if (elements_used[i])
{
data_array[j] = data[i];
++j;
}
}
return data_array;
}
size_t array_node::get_no_free()
{
return MAX_SIZE - elements_used.count();
}
size_t array_node::get_no_used()
{
return elements_used.count();
}
std::ostream& operator <<(std::ostream& output, const array_node& anode)
{
size_t i;
//fill up the ostream in the same manner
//as the array with get_data()
for (i = 0; i < array_node::MAX_SIZE; ++i)
{
if (anode.elements_used[i])
output << anode.data[i] << " ";
}
output << std::endl;
return output;
}
. Also remove system("pause"); .Its not really a great way do it also , replace return 0 in main by return EXIT_SUCCESS or return EXIT_FAILURE and so on ..... . I am a bit lazy to go through your entire code. 
. Then use the gui interface to perform the debugging