Thread: Suggestions on how to traverse a linked list of linked lists as if it is a 2D-Vector?

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    35

    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!

    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"; 
    }

  2. #2
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    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.
    A very interesting problem.

    My ideas:
    -Store your column in a variable (the only way you'll know if you're on the space directly above another is if you count how many spaces you were over)
    -Make the doubly-linked list into a 4-link list (ie, store pointers to the left, right, top and bottom in each node) (this means ditching the STL but if you have to access the immediate top, left, right, and bottom spaces a lot it will speed things up)
    Consider this post signed

  3. #3
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Sounds to me like you are using the wrong container for the job at hand.

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Bubba View Post
    Sounds to me like you are using the wrong container for the job at hand.
    Yeah. The STL is nifty but you should not be constrained by it because you don't know how to write a custom data structure. Try a graph or "4-link" list as bernt says.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    Apr 2010
    Posts
    35
    Thanks for the suggestions guys - I ended up doing it quite a slow way, without needing to define my own list. To be honest I'm simply not up to that level yet, I've had a bit of Java experience but I only started properly trying to learn C++ yesterday...

    It did end up working though, and passed all the functionality tests in the submission program for the assignment. No doubt the next assignment will be a lot harder and probably will require me to learn how to correctly define lists an such :P

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List from Standard Input
    By mercuryfrost in forum C Programming
    Replies: 14
    Last Post: 08-24-2009, 12:05 AM
  2. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM