Thread: c++ double linked lists searching

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    4

    c++ double linked lists searching

    This is a homework assignment for class, note that this is suppose to be a introduction class... hence our teacher is crazy.
    Anyways, we are suppose to utilize the doublelinked list so that you input employee data to first name and ID.
    You are should be able to search the linked list using the next and previous nodes and find the matching ID you search for.
    He gives us the function prototypes for all of the functions we need...
    He also gave us the entire first function EmployeeDLLNode * Makedoublylinkedlist(int N) of the definition file.

    I've got it to call the first function in main and I am able to enter employee data, but after that it does not display it.
    I also have a bunch of compile errors with the display functions in main saying that start is undeclared. Do i need to create a pointer in main?
    Will that lose all the data that I stored from the first function?? little confused... also... any other tips would be great..
    I am lost right now, and my intro book for the class does not go over double linked lists well... found this site to be helpful so far, thought i'd try the forum peoples.

    thanks for time & help!!
    - Paul



    Code:
    //******************* employee.h ************
    #ifndef EMPLOYEE_H_
    #define EMPLOYEE_H_
    
    #include <iostream>
    #include <string>
    #include <math.h>
    #include <iomanip>
    using namespace std;
    
    typedef struct Employee
    {
      int ID;
      string firstname;
    } Employee; 
    
    typedef struct EmployeeDLLNode
    {
      EmployeeDLLNode * start;
      Employee data;
      struct EmployeeDLLNode * previous;
      struct EmployeeDLLNode * next;
    } EmployeeDLLNode;
    
    Employee Collectdata();
    EmployeeDLLNode * Makedoublylinkedlist(int N);
    void DisplayDLLofEmployees(Employee * start);
    EmployeeDLLNode * FindEmployeeById(EmployeeDLLNode * start, int id);
    void DisplayEmployee(Employee e);
    
    #endif 
    //  **************       DEFINITION FILE employee.cpp *****************
    
    #include "employee.h"
    
    // Step 1: Define pointers, Cycle through array and store data inputed
    EmployeeDLLNode * Makedoublylinkedlist(int N)
    {
      EmployeeDLLNode * start = new EmployeeDLLNode;
      start -> data = Collectdata();
      start -> previous = start = 0;
      EmployeeDLLNode * last = start;
    
      for (int i = 1; i < N; i++)
      {
        last = new EmployeeDLLNode;
        last -> next -> data = Collectdata();
        last -> next -> previous = last;
        last -> next -> next = 0;
        last = last -> next;
      }
      return start;
    }
    
    // Step 2: Input employee data
    Employee Collectdata()
    {
      Employee emp;
      cout << "Enter ID: ";
      cin >> emp.ID;
      cin.ignore();
      cout << "First name: ";
      cin >> emp.firstname;
      return emp;
    }
    
    // Step 3: Cycle through list, display employee data
    void DisplayDLLofEmployees(EmployeeDLLNode * start)
    {
      for(EmployeeDLLNode * i = start ; i != 0; i = i -> next)
      { 
        DisplayEmployee (i -> data);
      }
    }
    
    // Step 4: Display employee data
    void DisplayEmployee(Employee e)
    {
    	cout << e.ID << " " << e.firstname << endl;
    }
    
    // Step 5: Search linked list by ID (?????)
    EmployeeDLLNode * FindEmployeeById(EmployeeDLLNode * start, int id)
    {
      for(EmployeeDLLNode * i = start ; i != 0; i = i -> next)
      { 
    
    	// ????
      }
      return 0;
    }
    // ******************* main.cpp **************
    #include "employee.h"
    
    int main()
    {
     	for(;;)
    	{
    	             // Input data (Size of array)
    		cout << "How many employees? ";
    		int N;
    		cin >> N;
    						
    	// Creates a double linked list using previous and next pointers
      	    Makedoublylinkedlist(N);
      	    
      	    
      	    // Cycle through array to display employees (error)
                       DisplayDLLofEmployees(start);
            
      	    // Input data (ID search)
      	    cout << "Search ID: ";
      	    int id;
      	    cin >> id;
      	      
      	    // Searches double linked list for specified ID (????)
                         FindEmployeeById(start,id);
      		
    	    /*			
    		// DELETE LIST (RESET LIST)
    		
    		*/
    		
    		// PROMPT REPEAT 
    		cout << endl << endl
    		     << "Enter a 0 to end or a non-negative integer to repeat: ";
    		cout << endl << endl;
    		int flag;
    		cin >> flag;
    		if(!flag)
    		break;
    	}
    	return 0;
    }
    Last edited by Salem; 04-26-2007 at 10:05 AM. Reason: Code tags around the code only - OK

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    If you are able to write your own linked list, searching in it should be a piece of cake? So, I wouldn't call your teacher crazy...

    Code:
    typedef struct EmployeeDLLNode
    {
      EmployeeDLLNode * start;
      Employee data;
      struct EmployeeDLLNode * previous;
      struct EmployeeDLLNode * next;
    } EmployeeDLLNode;
    Normally a linked list node doesn't have a pointer to the head. You'll keep track of the head yourself, or, much better, make a linked list a class of its own and let this class keep track of the head.

    Code:
    EmployeeDLLNode * FindEmployeeById(EmployeeDLLNode * start, int id)
    {
      for(EmployeeDLLNode * i = start ; i != 0; i = i -> next)
      { 
    
    	if (i->data.ID == id) return i; //was it really so hard???
      }
      return 0;
    }
    By the way, in C++ you don't need to typedef your structs. So a usual struct declaration goes like
    Code:
    struct S
    {
        //...
    };
    Typedef'fing is used in C, because otherwise you'd need to use the following "ugliness" to instantiate a struct object:
    Code:
    struct S a_struct;
    In C++ you can write this without any typedef:
    Code:
    S a_struct;

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Ok, so you have other problems too.

    Your main error is - as I already pointed out - that it is not each individual node that have the pointer to the first member of the list (if it were so, you'd need to modify each node if the head should ever change), but it is the outside code - be it free functions (and main) or preferably a special linked list class.

    So, MakeLinkedList returns a pointer to the first node. You should store it and be careful not to lose it. Without it you can't call any of the other functions that need this pointer as an argument.

    And as general advice: compile and test each function you write before moving on, especially when dealing with something as non-trivial as a linked list.
    Last edited by anon; 04-26-2007 at 10:01 AM.

  4. #4
    Registered User
    Join Date
    Apr 2007
    Posts
    4

    hrmm

    Thansk for the help ANON! I have a code to return start. Is it not saving correctly so that my display functions cannot access it in main.cpp?

    could i do something like this in mai n.cpp?
    start = Makedoublylinkedlist(N);
    like that? or am i totatlly off

    Code:
    EmployeeDLLNode * Makedoublylinkedlist(int N)
    {
      EmployeeDLLNode * start = new EmployeeDLLNode;
      start -> data = Collectdata();
      start -> previous = start = 0;
      EmployeeDLLNode * last = start;
    
      for (int i = 1; i < N; i++)
      {
        last = new EmployeeDLLNode;
        last -> next -> data = Collectdata();
        last -> next -> previous = last;
        last -> next -> next = 0;
        last = last -> next;
      }
      return start;
    }
    Last edited by payling; 04-26-2007 at 10:16 AM.

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Exactly, except you'll need to declare the start of main too. So it is more like:
    Code:
    EmpoyeeDLLNode* start = Makedoublylinkedlist(N);
    Just the usual scope rules apply here to, as you are hopefully aware of.

  6. #6
    Registered User
    Join Date
    Apr 2007
    Posts
    4
    doy, i've got it almost all working... except i'm still getting 1 more compile error at the DisplayyDLLofEmployees function. here is my newest main.cpp version. I // the error. I'm thinking it doesn't like that I am calling to structs within the function...? I dunno. a little confused by the error msg.

    Code:
    #include "employee.h"
    
    int main()
    {
     	for(;;)
    	{
    		// Input size of array
    		cout << "How many employees? ";
    		int N;
    		cin >> N;
    						
    	    // Create dynamic array
    		
    		// Creates a double linked list using previous and next pointers
    	    EmployeeDLLNode * start = Makedoublylinkedlist(N);
    	       
            // ERROR: cannot convert 'EmployeeDLLNode * to 'Employee *" for argument
            // '1' to 'void DisplayDLLofEMployees
            DisplayDLLofEmployees(start);
            
      	    // Input ID for search
      	    cout << "Search ID: ";
      	    int id;
      	    cin >> id;
      	      
      	    // Searches double linked list for specified ID
            FindEmployeeById(start,id);
      		
    		
    		// Need function to reset (DELETE LIST)
    		
    
    		
    		// Repeat 
    		cout << endl << endl
    		     << "Enter a 0 to end or a non-negative integer to repeat: "
    	         << endl << endl;
    		int flag;
    		cin >> flag;
    		if(!flag)
    		break;
    	}
    	return 0;
    }

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    If DisplayDLLofEmployees expects a parameter of type Employee*, as the error message seems to indicate, then the function takes a wrong type of a parameter. An Employee* does not in any way help you to iterate over the list. The parameter type should be EmployeeDLLNode*

  8. #8
    Registered User
    Join Date
    Apr 2007
    Posts
    4
    Well, I was trying to iterate over the list because I needed the DisplayEmployee function to display each employee stored.

    could I just go like this...
    that would cycle through each pointer displaying each employee i would think?

    Code:
    void DisplayDLLofEmployees(EmployeeDLLNode * start)
    {
      for(EmployeeDLLNode * i = start ; i != 0; i = i -> next)
      { 
        i -> data;
        DisplayEmployee();
      }
    }

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    You should really reread your materials about functions and function arguments.
    Code:
    void DisplayDLLofEmployees(EmployeeDLLNode * start)
    {
      for(EmployeeDLLNode * i = start ; i != 0; i = i -> next)
      { 
        i -> data; //this does nothing
        DisplayEmployee(); //which employee's data would this display?
      }
    }
    What you need is a DisplayEmployee function that can be called like this:
    Code:
    DisplayEmployee(i->data);

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  2. Copying 2-d arrays
    By Holtzy in forum C++ Programming
    Replies: 11
    Last Post: 03-14-2008, 03:44 PM
  3. Conversion From C++ To C
    By dicon in forum C++ Programming
    Replies: 2
    Last Post: 06-10-2007, 02:54 PM
  4. Double Linked lists
    By Jamsan in forum C++ Programming
    Replies: 1
    Last Post: 03-11-2003, 09:46 AM
  5. double linked lists
    By susyb in forum C++ Programming
    Replies: 3
    Last Post: 11-29-2001, 06:09 AM