circular linked->list help

This is a discussion on circular linked->list help within the C++ Programming forums, part of the General Programming Boards category; Here is my attempt at writing a circularly linked list. Everything compiles fine (using Borland) but when I try to ...

  1. #1
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903

    Post circular linked->list help

    Here is my attempt at writing a circularly linked list. Everything compiles fine (using Borland) but when I try to run this program.. it just locks up. Maybe an extra pair of eyes can help.

    push_node( ) uses head node insertion.. and will connect tail_ptr to head_ptr after the 6th node. Once this code is working, I will later add a "spin the wheel" function.. the will move all nodes clockwise by one node



    Code:
    #include<iostream>
    #include<cctype>
    #include<string>
    #include<iomanip>
    #include<conio.h>
    
    using namespace std;
    
    
    
    
    struct node
    {
    	string name;
    
    	node *next;
    	node *prev;
    };
    
    
    class Linkedlist
    {
    
    public:
    
    	Linkedlist();
    	void display_menu();
    	void display_graph();
    	string get_name(const int&);
    	void push_node();
    	void pop_node();
    	void exit_message();			
    	~Linkedlist();
    
    private:
    	
    	int node_counter;
    	string entry;
    	string name;
    	node *head_ptr;
    	node *tail_ptr;
    
    };
    
    
    
    int main()
    {
    	Linkedlist link;
    	
    	char option;
    
    	do
    	{	
    		clrscr();
    
    		link.display_menu();
    
    		link.display_graph();
    
    		option = toupper(getch());
    
    		switch(option)
    		{
    
    			case 'A':	link.push_node();
    						break;
    
    			case 'R':	link.pop_node();
    						break;
    
    			case 'E':	link.exit_message();
    						break;
    
    			default:	cout << "\n\nInvalid Entry, Try again.\n\n";
    
    		}
    	
    	}while (option != 'E');
    
    
    return 0;
    }
    
    
    
    
    ////////////////////////
    //Function Definitions//
    ////////////////////////
    
    
    //i would like to use something like this to initialize my struct
    //node::name(test) : next(NULL) : prev(NULL) { }
    
    Linkedlist::Linkedlist()
    {		
    	node_counter = 0;
    	node *head_ptr = NULL;
    	node *tail_ptr = NULL;
    }
    
    
    
    void Linkedlist::display_menu()
    {
    
    	cout << "\n\n\t\t*************************************"
    		 << "\n\t\t* Press 'A' to Add a name           *"
    		 << "\n\t\t* Press 'R' to Remove from the list *"
    		 << "\n\t\t* Press 'E' to Exit                 *"
    		 << "\n\t\t*************************************"
    		 << endl << endl << endl << endl;
    }
    
    
    
    
    
    void Linkedlist::display_graph()
    {
    	
    	cout << setw(35) << get_name(1) << endl << endl;
    
    	cout << setw(15) << get_name(6) << setw(50) << get_name(2) << endl << endl;
    
    	cout << setw(15) << get_name(5) << setw(50) << get_name(3) << endl << endl;
    
    	cout << setw(35) << get_name(4) << endl << endl << endl;
    
    }
    
    
    
    
    
    string Linkedlist::get_name(const int& iter)
    {
    	node *cursor;
    	string answer;
    
    	cursor = head_ptr;
    
    	for (int counter = 0; counter < iter && cursor->next != NULL; counter++)
    	{
    		cursor = cursor->next;
    		answer = cursor->name;
    	}
    
    	return answer;
    }
    
    
    
    
    void Linkedlist::push_node()
    {
    	++node_counter;
    
    	node *temp_ptr;		
    
    	temp_ptr = new node;
    
    	cout << "\n\n\tEnter Name: ";
    	getline(cin, entry);	
    	
    	temp_ptr->name = entry;
    	
    	if (head_ptr != NULL)			//This block will be the most frequent occurrance	
    	{								//Perform the double-link..  the old head node will
    		head_ptr->prev = temp_ptr;	//point to the new temp node..  and the new temp 
    		temp_ptr->next = head_ptr;	//node will point to the old head node.	
    	}
    
    	else //(head_ptr == NULL)	//This block is for the first node to be added to the 
    	{							//linked list.  This is a "special case" that will 
    		temp_ptr->next = NULL;	//facilitate the "empty list" scenario. When adding the first
    		tail_ptr = temp_ptr;	//node to the list, *next should be set to NULL..  also assign
    	}							//this node as the tail.
    
    	if (node_counter > 6)			//This block is designed to perform the circular closure
    	{								//of the linked list (this will occur after the 6th node) 
    		node *new_tail;				
    
    		new_tail = tail_ptr->prev;	//create a new tail (so we can delete the old one)
    
    		delete tail_ptr;			//delete the extra 7th node
    
    		new_tail->next = temp_ptr;	//perform the circular closure by having the last node 
    									//point to the new temporary head node
    		temp_ptr->prev = new_tail;	//and also have the new temp node point to the tail
    
    		tail_ptr = new_tail;		//tail_ptr will now be the 6th node.
    	}
    
    	head_ptr = temp_ptr;		//after all is done, assign the new temp node 
    								//as the head node.
    	if (node_counter < 6)			//if there are less than 6 nodes.. then the circle
    									//will not exist..  so the head node->prev should not
    		head_ptr->prev = NULL;		//point to anything
    
    	delete temp_ptr;
    }
    
    
    
    
    
    void Linkedlist::pop_node()
    {	
    
    	if (head_ptr == NULL)
    	
    		cout << "\n\n\tNo more nodes..!!\a ";
    
    	else
    	{
    		--node_counter;
    
    		node *new_head;
    
    		new_head = head_ptr->next;
    
    		delete head_ptr;
    
    		head_ptr = new_head;		
    
    		tail_ptr->next = NULL;	//Break the Circle
    		head_ptr->prev = NULL;	//
    	}
    
    	if (node_counter == 0)		//Make sure head_ptr and tail_ptr are NULL
    	{							//if all nodes have been popped.  
    		head_ptr = NULL;
    		tail_ptr = NULL;
    	}
    }
    
    
    
    
    
    void Linkedlist::exit_message()
    {
    	clrscr();
    
    	cout << "\n\n\tProgram written in c++ by David Weirich"
                 << "\ndrgreenthumb76@hotmail.com\n\n\n";
    }
    
    
    
    
    
    Linkedlist::~Linkedlist()
    {
    	while (node_counter)
    
    		pop_node();
    }
    Attached Files Attached Files
    Last edited by The Brain; 10-19-2004 at 02:59 AM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,660
    Look at this until you see something wrong...
    Code:
    Linkedlist::Linkedlist()
    {       
        node_counter = 0;
        node *head_ptr = NULL;
        node *tail_ptr = NULL;
    }
    Code:
    string Linkedlist::get_name(const int& iter)
    {
        node *cursor;
        string answer;
    
        cursor = head_ptr;
    
        for (int counter = 0; counter < iter && cursor->next != NULL; counter++)
    What if head_ptr is NULL?

    gg

    [Edit]That's right, I beat ya![/Edit]
    Last edited by Codeplug; 10-18-2004 at 07:40 PM.

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Not sure if this will solve all of your problems, but in your get_name function, when run the first time head pointer will be null, so cursor->next is going to crash.

  4. #4
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    thanks for the tips

    In my debugging attempts thus far, I noticed that I made a classic mistake in my add_node( ) function:


    In add_node( ) I make *temp_ptr which points to a newly created head node

    I then assign temp_ptr to head_ptr

    but then.. I made the classic mistake of deleting temp_ptr.. because I thought since I no longer need it.. I should return the pointer back to memory.

    However, this is not the case. By deleting temp_ptr, I was actually deleting what temp_ptr points to.. which is the head node (oops) Like any other local variable, temp_ptr will automatically be returned to memory after the function has been executed.

    Linked list rule of thumb.. Never call delete unless you are actually reducing the number of nodes.


    I also called delete with 'new_tail' in add_node( ) but I fixed it
    Last edited by The Brain; 10-19-2004 at 02:14 PM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  5. #5
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903

    Thumbs up yay.

    It works!!!




    Code:
    #include<iostream>
    #include<cctype>
    #include<string>
    #include<iomanip>
    #include<conio.h>
    
    using namespace std;
    
    
    
    
    struct node
    {
    	string name;
    
    	node *next;
    	node *prev;
    };
    
    
    class Linkedlist
    {
    
    public:
    
    	Linkedlist();
    	void display_menu();
    	void display_graph();
    	string get_name(int);
    	void push_node();
    	void pop_node();
    	void exit_message();			
    	~Linkedlist();
    
    private:
    	
    	int node_counter;
    	node *head_ptr;
    	node *tail_ptr;
    
    };
    
    
    
    int main()
    {
    	Linkedlist link;
    	
    	char option;
    
    	do
    	{	
    		clrscr();
    
    		link.display_menu();
    
    		link.display_graph();
    
    		option = toupper(getch());
    
    		switch(option)
    		{
    
    			case 'A':	link.push_node();
    						break;
    
    			case 'R':	link.pop_node();
    						break;
    
    			case 'E':	link.exit_message();
    						break;	
    
    		}
    	
    	}while (option != 'E');
    
    
    return 0;
    }
    
    
    
    
    ////////////////////////
    //Function Definitions//
    ////////////////////////
    
    
    //i would like to use something like this to initialize my struct
    //node::name(test) : next(NULL) : prev(NULL) { }
    
    Linkedlist::Linkedlist()
    {		
    	node_counter = 0;
    	head_ptr = NULL;
    	tail_ptr = NULL;
    }
    
    
    
    void Linkedlist::display_menu()
    {
    
    	cout << "\n\n\t\t*************************************"
    		 << "\n\t\t*               MENU                *"
    		 << "\n\t\t*************************************"
    		 << "\n\t\t* Press 'A' to Add a name           *"
    		 << "\n\t\t* Press 'R' to Remove from the list *"
    		 << "\n\t\t* Press 'E' to Exit                 *"
    		 << "\n\t\t*************************************"
    		 << "\n\t\t*    There are currently " << node_counter << " nodes    *"
    		 << "\n\t\t*************************************"
    		 << endl << endl << endl << endl << endl << endl;
    }
    
    
    
    
    
    void Linkedlist::display_graph()
    {
    	
    	cout << setw(36) << get_name(1) << endl << endl << endl << endl;
    
    	cout << setw(21) << get_name(6) << setw(30) << get_name(2) << endl << endl << endl << endl;
    
    	cout << endl;
    
    	cout << setw(21) << get_name(5) << setw(30) << get_name(3) << endl << endl << endl << endl;
    
    	cout << setw(36) << get_name(4) << endl << endl << endl;
    
    }
    
    
    
    
    
    string Linkedlist::get_name(int iter)
    {
    	if (iter > node_counter || head_ptr == NULL)
    
    		return "";
    
    	else if (head_ptr->next == NULL)
    
    		return head_ptr->name;
    
    	else
    	{		
    		--iter;
    		
    		node *cursor = head_ptr;		
    
    		for (int counter = 0; counter < iter; counter++)
    		
    			cursor = cursor->next;
    		
    		return cursor->name;	
    	}
    }
    
    
    	
    
    
    void Linkedlist::push_node()
    {
    	++node_counter;	
    
    	node *new_node;		
    
    	new_node = new node;
    
    	string entry;
    
    	cout << "\n\n\tEnter Name: ";
    	getline(cin,entry);	
    	
    	new_node->name = entry;
    	
    	if (head_ptr != NULL)			//This block will be the most frequent occurrance	
    	{								//Perform the double-link..  the old head node will
    		head_ptr->prev = new_node;	//point to the new temp node..  and the new temp 
    		new_node->next = head_ptr;	//node will point to the old head node.	
    		new_node->prev = NULL;
    	}
    
    	else //(head_ptr == NULL)	//This block is for the first node to be added to the 
    	{							//linked list.  This is a "special case" that will 
    		new_node->next = NULL;	//facilitate the "empty list". When adding the first
    		tail_ptr = new_node;	//node to the list, *next should be set to NULL..  also assign
    	}							//this node as the tail.
    
    	if (node_counter > 5)			//This block is designed to perform the circular closure
    	{								//linking the 6th node to the head node		
    		tail_ptr->next = new_node;
    		new_node->prev = tail_ptr;
    	}
    
    	if (node_counter > 6)		//This block will delete any added extra nodes
    	{		
    		node *new_tail;				
    
    		new_tail = tail_ptr->prev;	//create a new tail (so we can delete the old one)
    
    		delete tail_ptr;			//delete the extra 7th node
    
    		new_tail->next = new_node;	//perform the circular closure by having the last node 
    									//point to the new temporary head node
    		new_node->prev = new_tail;	//and also have the new temp  head node point to the tail
    
    		tail_ptr = new_tail;		//tail_ptr now points to the 6th node
    
    		--node_counter;				//node_counter max = 6
    	}
    
    	head_ptr = new_node;		//after all is done, assign the new temp node 
    								//as the head node.
    }
    
    
    
    
    
    void Linkedlist::pop_node()
    {	
    
    	if (head_ptr == NULL)
    	
    		cout << "\t\t\t\aNo more nodes..!! ";
    
    	else
    	{
    		if (head_ptr->next != NULL)
    		{
    			node *new_head;
    			new_head = head_ptr->next;			
    			delete head_ptr;
    			head_ptr = new_head;
    			tail_ptr->next = NULL;	//Break the Circle
    			head_ptr->prev = NULL;	//				
    		}
    
    		else
    		{
    			delete head_ptr;
    			head_ptr = NULL;
    			tail_ptr = NULL;				
    		}	
    
    		--node_counter;
    
    		if (node_counter < 0)
    
    			node_counter = 0;	//node_counter min = 0
    	}
    }
    
    
    
    
    
    void Linkedlist::exit_message()
    {
    	clrscr();
    
    	cout << "\nProgram written in c++ by David Weirich"
    		 << "\ndrgreenthumb76@hotmail.com\n\n\n";
    }
    
    
    
    
    
    Linkedlist::~Linkedlist()
    {
    	while (node_counter)
    
    		pop_node();
    }
    Attached Files Attached Files
    Last edited by The Brain; 10-19-2004 at 02:22 PM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  6. #6
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    I was wondering if someone could give me some good pseudocode for this program for a copy constructor.. that will be able to initialize new nodes.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  7. #7
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    I am trying to template this program so "name" can accept any type of data... but I got it debugged down to just 3 errors..



    Code:
    #include<iostream>
    #include<cctype>
    #include<string>
    #include<iomanip>
    #include<conio.h>
    
    using namespace std;
    
    
    
    template<class T>
    struct node
    {
    	T name;    
    
    	node *next;
    	node *prev;
    };
    
    
    template<class T>
    class Linkedlist
    {
    
    public:
    
    	Linkedlist();
    	void display_menu();
    	void display_graph();
    	T get_name(int);
    	void push_node();
    	void pop_node();
    	void exit_message();			
    	~Linkedlist();
    
    private:
    	
    	int node_counter;
    	node<T> *head_ptr;
    	node<T> *tail_ptr;
    
    };
    
    
    
    int main()
    {
    	Linkedlist link;
    	
    	char option;
    
    	do
    	{	
    		clrscr();
    
    		link.display_menu();
    
    		link.display_graph();
    
    		option = toupper(getch());
    
    		switch(option)
    		{
    
    			case 'A':	link.push_node();
    						break;
    
    			case 'R':	link.pop_node();
    						break;
    
    			case 'E':	link.exit_message();
    						break;	
    
    		}
    	
    	}while (option != 'E');
    
    
    return 0;
    }
    
    
    
    
    ////////////////////////
    //Function Definitions//
    ////////////////////////
    
    
    //i would like to use something like this to initialize my struct
    //node::node : name(test) : next(NULL), prev(NULL) { }
    
    template<class T>
    Linkedlist<T>::Linkedlist()
    {		
    	node_counter = 0;
    	head_ptr = NULL;
    	tail_ptr = NULL;
    }
    
    
    
    template<class T>
    void Linkedlist<T>::display_menu()
    {
    
    	cout << "\n\n\t\t*************************************"
    		 << "\n\t\t*               MENU                *"
    		 << "\n\t\t*************************************"
    		 << "\n\t\t* Press 'A' to Add a name           *"
    		 << "\n\t\t* Press 'R' to Remove from the list *"
    		 << "\n\t\t* Press 'E' to Exit                 *"
    		 << "\n\t\t*************************************"
    		 << "\n\t\t*    There are currently " << node_counter << " nodes    *"
    		 << "\n\t\t*************************************"
    		 << endl << endl << endl << endl << endl << endl;
    }
    
    
    
    
    
    template<class T>
    void Linkedlist<T>::display_graph()
    {
    	
    	cout << setw(36) << get_name(1) << endl << endl << endl << endl;
    
    	cout << setw(21) << get_name(6) << setw(30) << get_name(2) << endl << endl << endl << endl;
    
    	cout << endl;
    
    	cout << setw(21) << get_name(5) << setw(30) << get_name(3) << endl << endl << endl << endl;
    
    	cout << setw(36) << get_name(4) << endl << endl << endl;
    
    }
    
    
    
    
    template<class T>
    T Linkedlist<T>::get_name(int iter)
    {
    	if (iter > node_counter || head_ptr == NULL)
    
    		return "";
    
    	else if (head_ptr->next == NULL)
    
    		return head_ptr->name;
    
    	else
    	{		
    		--iter;
    		
    		node *cursor = head_ptr;		
    
    		for (int counter = 0; counter < iter; counter++)
    		
    			cursor = cursor->next;
    		
    		return cursor->name;	
    	}
    }
    
    
    	
    
    
    template<class T>
    void Linkedlist<T>::push_node()
    {
    	++node_counter;	
    
    	node *new_node;		
    
    	new_node = new node;
    
    	T entry;
    
    	cout << "\n\n\tEnter Name: ";
    	getline(cin,entry);	
    	
    	new_node->name = entry;
    	
    	if (head_ptr != NULL)			//This block will be the most frequent occurrance	
    	{								//Perform the double-link..  the old head node will
    		head_ptr->prev = new_node;	//point to the new temp node..  and the new temp 
    		new_node->next = head_ptr;	//node will point to the old head node.	
    		new_node->prev = NULL;
    	}
    
    	else //(head_ptr == NULL)	//This block is for the first node to be added to the 
    	{							//linked list.  This is a "special case" that will 
    		new_node->next = NULL;	//facilitate the "empty list". When adding the first
    		tail_ptr = new_node;	//node to the list, *next should be set to NULL..  also assign
    	}							//this node as the tail.
    
    	if (node_counter > 5)			//This block is designed to perform the circular closure
    	{								//linking the 6th node to the head node		
    		tail_ptr->next = new_node;
    		new_node->prev = tail_ptr;
    	}
    
    	if (node_counter > 6)		//This block will delete any added extra nodes
    	{		
    		node *new_tail;				
    
    		new_tail = tail_ptr->prev;	//create a new tail (so we can delete the old one)
    
    		delete tail_ptr;			//delete the extra 7th node
    
    		new_tail->next = new_node;	//perform the circular closure by having the last node 
    									//point to the new temporary head node
    		new_node->prev = new_tail;	//and also have the new temp  head node point to the tail
    
    		tail_ptr = new_tail;		//tail_ptr now points to the 6th node
    
    		--node_counter;				//node_counter max = 6
    	}
    
    	head_ptr = new_node;		//after all is done, assign the new temp node 
    								//as the head node.
    }
    
    
    
    
    
    template<class T>
    void Linkedlist<T>::pop_node()
    {	
    
    	if (head_ptr == NULL)
    	
    		cout << "\t\t\t\aNo more nodes..!! ";
    
    	else
    	{
    		if (head_ptr->next != NULL)
    		{
    			node *new_head;
    			new_head = head_ptr->next;			
    			delete head_ptr;
    			head_ptr = new_head;
    			tail_ptr->next = NULL;	//Break the Circle
    			head_ptr->prev = NULL;	//				
    		}
    
    		else
    		{
    			delete head_ptr;
    			head_ptr = NULL;
    			tail_ptr = NULL;				
    		}	
    
    		--node_counter;
    
    		if (node_counter < 0)
    
    			node_counter = 0;	//node_counter min = 0
    	}
    }


    Here are the errors (using Borland)


    C:\MySource>bcc32 circlelist.cpp
    Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
    circlelist.cpp:
    Error E2102 circlelist.cpp 48: Cannot use template 'Linkedlist<T>' without specifying specialization
    parameters in function main()
    Error E2040 circlelist.cpp 48: Declaration terminated incorrectly in function main()
    Error E2451 circlelist.cpp 56: Undefined symbol 'link' in function main()
    *** 3 errors in Compile ***




    please help if you can
    Attached Files Attached Files
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  8. #8
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    when you declare an instance of a templated class you have to indicate what type T is going to be. T has to be a valid type. so:

    Linkedlist <int> link;

    is a Linkedlist of int and

    Linkedlist <std::string> link;

    is a Linkedlist of std::string and

    Linkedlist <myClass> link;

    is a Linkedlist of a user defined type called myClass. Etc.

    I think that will get rid of your current error reports.

    As to constructors, you could try declaring a constructor for your struct type like this:
    Code:
    template<class T>
    struct node
    {
      T name; 
      node *next;
      node *prev;
     
      node(T n) : name(n), next(NULL), prev(NULL)
      {}
    };
    For a default, no-parameter constructor, you may not be able to initialize name. At least I can't figure out a way to allow a default value for all types....zero might work, but I don't know what happens if you initialize a std::string to 0. Leaving name unitialized isn't a problem from a legal standpoint; you just need to make sure you initialize it before you try to use it.

  9. #9
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903

    Cool

    Thanks Elad



    Here is my final product. It uses head node insertion and deletion. The circle will hold 6 nodes.. New nodes can be added by deleting nodes at the tail. After the 6th node has been entered, the user is then prompted with the option to spin the wheel forward/backward, which is accomplished simply by re-assigning the head_ptr and tail_ptr. My goal for this program was mainly just to demonstrate the circularly double-linked list data structure. I would like critique from experienced programmers.




    Code:
    #include<iostream>
    #include<cctype>
    #include<string>
    #include<iomanip>
    #include<conio.h>
    
    using namespace std;
    
    
    
    template<class T>
    struct node
    {
    	T name;
    
    	node *next;
    	node *prev;
    };
    
    
    template<class T>
    class Linkedlist
    {
    
    public:
    
    	Linkedlist();
    	void display_menu();
    	void display_graph();
    	T get_name(int);
    	void push_node();
    	void pop_node();
    	void spin_right();
    	void spin_left();
    	void exit_message();			
    	~Linkedlist();
    
    private:
    	
    	int node_counter;
    	node<T> *head_ptr;
    	node<T> *tail_ptr;
    
    };
    
    
    
    int main()
    {
    	Linkedlist<string> link;
    	
    	char option;
    
    	do
    	{	
    		clrscr();
    
    		link.display_menu();
    
    		link.display_graph();
    
    		option = toupper(getch());
    
    		switch(option)
    		{
    
    			case 'A':	link.push_node();
    						break;
    
    			case 'R':	link.pop_node();
    						break;	
    
    			case 'B':	link.spin_right();
    						break;
    			
    			case 'F':	link.spin_left();
    						break;
    			
    			case 'E':	link.exit_message();
    						break;
    
    
    		}
    	
    	}while (option != 'E');
    
    
    return 0;
    }
    
    
    
    
    ////////////////////////
    //Function Definitions//
    ////////////////////////
    
    
    //i would like to use something like this to initialize my struct
    //node::node : name(test) : next(NULL), prev(NULL) { }
    
    template<class T>
    Linkedlist<T>::Linkedlist()
    {		
    	node_counter = 0;
    	head_ptr = NULL;
    	tail_ptr = NULL;
    }
    
    
    
    template<class T>
    void Linkedlist<T>::display_menu()
    {
    
    	cout << "\n\n\t\t*************************************"
    		 << "\n\t\t*               MENU                *"
    		 << "\n\t\t*************************************"
    		 << "\n\t\t* Press 'A' to Add a name           *"
    		 << "\n\t\t* Press 'R' to Remove from the list *"
    		 << "\n\t\t* Press 'E' to Exit                 *"
    		 << "\n\t\t*************************************";
    	
    	if (node_counter < 6)
    	
    		cout << "\n\t\t*    There are currently " << node_counter << " nodes    *";
    
    	else
    		
    		cout << "\n\t\t*  <- 'B'  SPIN THE WHEEL!  'F' ->  *";
    		 
    	cout << "\n\t\t*************************************"
    		 << endl << endl << endl << endl << endl << endl;
    }
    
    
    
    
    
    template<class T>
    void Linkedlist<T>::display_graph()
    {
    	
    	cout << setw(36) << get_name(1) << endl << endl << endl << endl;
    
    	cout << setw(21) << get_name(6) << setw(30) << get_name(2) << endl << endl << endl << endl;
    
    	cout << endl;
    
    	cout << setw(21) << get_name(5) << setw(30) << get_name(3) << endl << endl << endl << endl;
    
    	cout << setw(36) << get_name(4) << endl << endl << endl;
    
    }
    
    
    
    
    template<class T>
    T Linkedlist<T>::get_name(int iter)
    {
    	if (iter > node_counter || head_ptr == NULL)
    	
    		return "";
    
    	else
    	{		
    		--iter;
    		
    		node<T> *cursor = head_ptr;		
    
    		for (int counter = 0; counter < iter; counter++)
    		
    			cursor = cursor->next;
    		
    		return cursor->name;	
    	}
    }
    
    
    	
    
    
    template<class T>
    void Linkedlist<T>::push_node()
    {
    	try
    	{
    		++node_counter;	
    
    		node<T> *new_node;	
    
    		new_node = new node<T>;
    
    		T entry;
    
    		cout << "\n\n\tEnter Name: ";
    		getline(cin,entry);	
    	
    		new_node->name = entry;
    	
    		if (head_ptr != NULL)			//This block will be the most frequent occurrance	
    		{								//Perform the double-link..  the old head node will
    			head_ptr->prev = new_node;	//point to the new temp node..  and the new temp 
    			new_node->next = head_ptr;	//node will point to the old head node.	
    			new_node->prev = NULL;
    		}
    
    		else //(head_ptr == NULL)	//This block is for the first node to be added to the 
    		{							//linked list.  This is a "special case" that will 
    			new_node->next = NULL;	//facilitate the "empty list". When adding the first
    			tail_ptr = new_node;	//node to the list, *next should be set to NULL..  also assign
    		}							//this node as the tail.
    
    		if (node_counter > 5)			//This block is designed to perform the circular closure
    		{								//linking the 6th node to the head node		
    			tail_ptr->next = new_node;
    			new_node->prev = tail_ptr;
    		}
    
    		if (node_counter > 6)		//This block will delete any added extra nodes
    		{		
    			node<T> *new_tail;				
    
    			new_tail = tail_ptr->prev;	//create a new tail (so we can delete the old one)
    
    			delete tail_ptr;			//delete the extra 7th node
    
    			new_tail->next = new_node;	//perform the circular closure by having the last node 
    									//point to the new temporary head node
    			new_node->prev = new_tail;	//and also have the new temp  head node point to the tail
    
    			tail_ptr = new_tail;		//tail_ptr now points to the 6th node
    
    			--node_counter;				//node_counter max = 6
    		}
    	
    		head_ptr = new_node;		//after all is done, assign the new temp node 
    								//as the head node.
    
    	}
    
    	catch (bad_alloc)
    	{
    		cout << "\t\aNo more usable memory, no new nodes can be added. ";
    	}
    
    	catch(...)
    	{
    		cout << "\t\aUnhandled Thrown Exception. ";
    	}
    
    }
    
    
    
    
    template<class T>
    void Linkedlist<T>::pop_node()
    {	
    
    	if (head_ptr == NULL)
    	
    		cout << "\t\t\t\aNo more nodes..!! ";
    
    	else
    	{
    		if (head_ptr->next != NULL)
    		{
    			node<T> *new_head;
    			new_head = head_ptr->next;			
    			delete head_ptr;
    			head_ptr = new_head;
    			tail_ptr->next = NULL;	//Break the Circle
    			head_ptr->prev = NULL;	//				
    		}
    
    		else
    		{
    			delete head_ptr;
    			head_ptr = NULL;
    			tail_ptr = NULL;				
    		}	
    
    		--node_counter;
    
    		if (node_counter < 0)
    
    			node_counter = 0;	//node_counter min = 0
    	}
    }
    
    
    
    
    template<class T>
    void Linkedlist<T>::spin_right()
    {
    	if (node_counter > 5)
    	{
    		head_ptr = head_ptr->next;
    		tail_ptr = tail_ptr->next;
    	}
    }
    
    
    
    
    
    template<class T>
    void Linkedlist<T>::spin_left()
    {
    	if (node_counter > 5)
    	{
    		head_ptr = head_ptr->prev;
    		tail_ptr = tail_ptr->prev;
    	}
    }
    
    
    
    
    template<class T>
    void Linkedlist<T>::exit_message()
    {
    	clrscr();
    
    	cout << "\nProgram written in c++ by David Weirich"
    		 << "\ndrgreenthumb76@hotmail.com\n\n\n";
    }
    
    
    
    
    
    template<class T>
    Linkedlist<T>::~Linkedlist()
    {
    	while (node_counter)
    
    		pop_node();
    }
    Attached Files Attached Files
    Last edited by The Brain; 10-21-2004 at 06:11 PM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. how do i reverse a circular double linked list
    By kobra_swe in forum C Programming
    Replies: 13
    Last Post: 04-08-2008, 04:20 PM
  2. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  3. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  4. Circular Double Linked List - Logic in Operator=
    By INFERNO2K in forum C++ Programming
    Replies: 5
    Last Post: 09-30-2006, 12:45 PM
  5. Circular Linked list ....
    By yescha in forum C Programming
    Replies: 1
    Last Post: 11-17-2001, 02:41 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21