Suggestions on how to traverse a linked list of linked lists as if it is a 2D-Vector?
Hi All,
I've already had some help on this forum, I'm so glad I found it -- I'm working on an assignment and I'm just struggling with a concept as I'm quite a newcomer with C++.
We are being taught to use doubly-linked lists rather than arrays (therefore the method to traverse between lists to access data is rather inefficient as it involves starting from the beginning each time) - and I'd like some suggestions on how to get started, as I can't think of the right way to do it... maybe to utilise a "row number" for the horizontal lists... I'm not sure.
Anyway, suggestions are very welcome, and I will post my code (it's all in one cpp file). Essentially I need to be able to traverse the list up and down so that I can see all the spaces to the immediate left, top and bottom of a position in one of the rows.
The function "calculate_metrics" alllll the way at the bottom is what I'm up to - I'm so close to getting it all functional! :D
Code:
#include <iostream>
#include <fstream>
#include <list>
#include <ctype.h>
#include <cstdlib>
using namespace std;
class row
{
private:
list<char> row_chars;
int row_number;
public:
row(int number)
{
row_number = number;
}
void store_chars(char ch);
void new_row();
void print_row();
bool is_match(char data);
void clear_row();
bool is_char_valid();
bool is_outside_maze(char findData);
bool check_counts(int hash, int s, int f);
int get_row_number();
};
void load_maze(list<row> &maze_rows, row &row_chars, const string &filein);
void print_maze(list<row> &maze_rows);
bool find_char(const char &findData,
list<row>::iterator &itr, list<row> &maze_rows);
int count_char(const char &findData,
list<row>::iterator &itr, list<row> &maze_rows);
bool is_maze_valid(list<row>::iterator &itr, list<row> &maze_rows);
bool is_outside(const char &findData,
list<row>::iterator &itr, list<row> &maze_rows);
int test_maze(list<row> &maze_rows);
void calculate_metrics(list<row> &maze_rows);
int main (int argc, char *argv[])
{
string filein;
list<row> maze_rows;
row row_chars(1);
//Make sure a maze file was provided
if (argc != 2)
{
cout << "Must supply 1 argument to this program\n";
return 0;
}
filein = argv[1];
//Loading the file into lists...
load_maze(maze_rows, row_chars, filein);
//Running the tests on the lists...
if(test_maze(maze_rows) == 0)
{
cout << "Unable to load maze " << filein << " \n";
exit(0);
}
print_maze(maze_rows);
//Calculate and print the maze metrics...
calculate_metrics(maze_rows);
return 0;
}
void row::store_chars(char ch)
{
row_chars.push_back(ch);
}
void row::new_row()
{
row_number++;
}
void row::print_row()
{
for(list<char>::iterator list_iter = row_chars.begin();
list_iter != row_chars.end(); list_iter++)
cout << *list_iter;
}
bool row::is_match(char data)
{
//Return false if it cannot find the provided char in the row
for(list<char>::iterator list_iter = row_chars.begin();
list_iter != row_chars.end(); list_iter++)
{
if(*list_iter == data)
return true;
}
return false;
}
void row::clear_row()
{
row_chars.clear();
}
bool row::is_char_valid()
{
//Return true if all the chars match up with one of the specified characters
for(list<char>::iterator list_iter = row_chars.begin();
list_iter != row_chars.end(); list_iter++)
{
if(*list_iter == '#' || *list_iter == 's' || *list_iter == 'f'
|| *list_iter == ' ' || *list_iter == '\n')
continue;
else
return false;
}
return true;
}
bool row::is_outside_maze(char findData)
{
//Return true if the char is outside the maze
int hash_count, s_count, f_count;
hash_count = s_count = f_count = 0;
for(list<char>::iterator list_iter = row_chars.begin();
list_iter != row_chars.end(); list_iter++)
{
if(*list_iter == '#')
hash_count++;
if(*list_iter == 's')
s_count++;
if(*list_iter == 'f')
f_count++;
if(check_counts(hash_count, s_count, f_count))
continue;
else
return true;
}
return false;
}
bool row::check_counts(int hash, int s, int f)
{
if((s > 0 || f > 0) && hash == 0)
return false;
else
return true;
}
int row::get_row_number()
{
return row_number;
}
void load_maze(list<row> &maze_rows, row &row_chars, const string &filein)
{
ifstream fin;
char ch;
//open stream to filein
fin.open(filein.c_str());
if (!fin)
{
cerr << "Unable to load maze " << filein << " \n";
exit(0);
}
while (!fin.eof())
{
fin.get(ch);
row_chars.store_chars(ch);
if(ch == '\n')
{
maze_rows.push_back(row_chars);
row_chars.clear_row();
row_chars.new_row();
}
}
fin.close();
}
void print_maze(list<row> &maze_rows)
{
for(list<row>::iterator list_iter = maze_rows.begin();
list_iter != maze_rows.end(); list_iter++)
list_iter->print_row();
}
bool find_char(const char &findData,
list<row>::iterator &itr, list<row> &maze_rows)
{
// Check if char is found in list
for (itr = maze_rows.begin(); itr != maze_rows.end(); itr++)
{
if (itr->is_match(findData))
return true;
}
return false;
}
int count_char(const char &findData,
list<row>::iterator &itr, list<row> &maze_rows)
{
// Check how many times the char occurs in the row
int data_count = 0;
for (itr = maze_rows.begin(); itr != maze_rows.end(); itr++)
{
if (itr->is_match(findData))
data_count++;
}
return data_count;
}
bool is_maze_valid(list<row>::iterator &itr, list<row> &maze_rows)
{
// Testing if chars in the maze are valid
for (itr = maze_rows.begin(); itr != maze_rows.end(); itr++)
{
if (itr->is_char_valid())
continue;
else
{
cout << "invalid character in maze\n";
return false;
}
}
return true;
}
bool is_outside(const char &findData,
list<row>::iterator &itr, list<row> &maze_rows)
{
//Testing if char is placed inside or outside of the maze
for (itr = maze_rows.begin(); itr != maze_rows.end(); itr++)
{
if (itr->is_outside_maze(findData))
return true;
}
return false;
}
int test_maze(list<row> &maze_rows)
{
list<row>::iterator list_iter;
//Testing to see if 's' is contained in the maze...
if(!find_char('s', list_iter, maze_rows))
{
cout << "Error - no start found in maze";
return(0);
}
//Testing to see if 'f' is contained in the maze...
if(!find_char('f', list_iter, maze_rows))
{
cout << "Error - no finish found in maze";
return(0);
}
//Testing to see if maze contains valid characters...
if(!is_maze_valid(list_iter, maze_rows))
{
return(0);
}
//Testing to see if there is only one 's' and 'f'
// contained in the maze...
if(count_char('s', list_iter, maze_rows) != 1)
{
cout << "Error - multiple start found in maze\n";
return(0);
}
if (count_char('f', list_iter, maze_rows) != 1)
{
cout << "Error - multiple finish found in maze\n";
return(0);
}
//Testing to see if 's' or 'f' is declared
// outside of the maze...
if(is_outside('s', list_iter, maze_rows))
{
cout << "Error - start declared outside of maze\n";
return(0);
}
if(is_outside('f', list_iter, maze_rows))
{
cout << "Error - finish declared outside of maze\n";
return(0);
}
return(1);
}
void calculate_metrics(list<row> &maze_rows)
{
/*Calculate the total number of branches in the maze*/
/*Calculate the total number of dead ends in the maze*/
int branches, dead_ends;
branches = dead_ends = 0;
cout << "\nNumber of branches in maze is " << branches << "\n";
cout << "Number of dead-ends in maze is " << dead_ends << "\n";
}
