Thread: linked list problems

  1. #1
    Registered User
    Join Date
    Dec 2008
    Posts
    7

    linked list problems

    hello
    the problem is like this i have a linked list, i need to delete the nods that have info 'a'

    the program is this one


    Code:
    #include <iostream>
    
    using namespace std;
    
    struct nod
    {
    	char info;
    	nod *urm;//urm is pointer to the next node
    };nod *prim,*ultim;//prim remembers the first node, ultim remembers the
                                     last one   
    
    void adaugare (char a);
    void verificare();
    void primnod();
    int main()
    {
    	int n;//size of list
    	char k; //info
    	cout<<"cate elemente vrei sa adaugi in lista? ";
    	cin>>n;    
    	primnod();//the function that declares the frist node
    	for(int i=2;i<=n;i++)
    	{	
                        cout<<"dati valoarea pt elementul al"<<i<<"-lea ";
    	    cin>>k;
    	    adaugare(k);
    	}
    	nod *x= new nod;
    
    	verificare();
    	x=prim;
    	for(x=prim;x<=ultim;x=x->urm)
    	{
    		cout<<x->info<<" ";
    		if(x->urm==NULL)
    		{cout<<endl;
    		 break;
    		}
    	}
    	cout<<"merge";
    
    	return 0;
    }
    void primnod()
    {
    	nod *p=new nod;
    	cout<<"introduceti valoarea primului nod ";
    	cin>>p->info;
    	prim=ultim=p;
    	p->urm=NULL;
    	
    
    }
    void adaugare(char a)
    {
    	nod *p= new nod;
    	p->info= a;
    	ultim->urm=p;
    	ultim=p;
    	p->urm=NULL;
    	
    }
    void verificare()
    {	nod *x=new nod;
    	nod *q=new nod;
    	x=prim;
    	q=prim;
    	while(prim->info=='a')
    	{
    		nod *p;
    		p=prim;
    		prim=p->urm;
    		delete p;
    	}
    
    	
    
    	
    	
    	while(q->urm!=NULL)
    	{	
    		
    		if(q->urm->info=='a')
    		{
    			nod *i=new nod;
    			
    			i=q->urm;
    			while(i->info='a')
    			{
    			 nod *t= new nod;
    			 t=i;
    			 i=t->urm;
    			delete t;
    			}
    			q->urm=i->urm;
    			delete i;
    
    		}
    		q->urm=q->urm->urm;
    	
    	}
    
    
    	
    }
    i want u to look at the verificare function and after the verification if the first node is a...

    exactly this part
    Code:
    	while(q->urm!=NULL)
    	{	
    		
    		if(q->urm->info=='a')
    		{
    			nod *i=new nod;
    			
    			i=q->urm;
    			while(i->info='a')
    			{
    			 nod *t= new nod;
    			 t=i;
    			 i=t->urm;
    			delete t;
    			}
    			q->urm=i->urm;
    			delete i;
    
    		}
    		q->urm=q->urm->urm;
    	
    	}
    i thinked like this, i positioned with q before the node with 'a' info i created a pointer to q->urm then i entered in a while loop and created a pointer to start delete the nodes with a...if they are more in line...

    please tell me what is wrong, i'm sorry for my bad format, this is my first post on this forum...

    //best regards

  2. #2
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    1) It is while(i->info=='a') and you don't check if t->urm != NULL
    2) In your code you do for example nod* x = new nod and then x = prim
    Why do you do this? You are creating garbage. x will point to the pointer returned by new nod and then x will point to prim. The memory allocated and returned by new nod won't be pointed by any pointer, so garbage! You don't need to allocate space for x. You do this errors in several spots in your code. Fix 'em.

    Do the above, compile/run and post again

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If this is supposed to be C++, aren't you supposed to use a class for nod?

    You have lots of memory leaks where you do something like:
    Code:
    	nod *x= new nod;
    
    	verificare();
    	x=prim;
    You allocate a new node in x, then call verificare, and then assign x with prim. At this point, the newly allocated node is lost and not freed.

    I'm still trying to understand your overall code (actually, I started by replacing the names with english ones for next, head and tail.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Further:
    Code:
    	for(x=prim;x<=ultim;x=x->urm)
    is not correct. You can not rely on the last allocated pointer being at a higher address than the first one, not to mention that "NULL" is numerically lower than ALL pointers that are not NULL, so you would loop in the case where x is NULL and ultim isn't!

    If you delete the last (ultim) node in verificare, what happens? [This is a general question, not related to the above that should use ultim anyways]

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Typically you do this when you want to iterate a non-array-based structure
    Code:
    for(x =  start; x != end; x = x->urm)
    Loop until you reach the end.
    In your case start = prim, end = NULL. Because only the last node's urm will point to NULL

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by C_ntua View Post
    Typically you do this when you want to iterate a non-array-based structure
    Code:
    for(x =  start; x != end; x = x->urm)
    Loop until you reach the end.
    In your case start = prim, end = NULL. Because only the last node's urm will point to NULL
    Correct. I usually write it (using English names
    Code:
    for(p = head; p; p = p->next)
    ...
    assuming that end is marked with a 0 (NULL).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Dec 2008
    Posts
    7
    thank you very much for reply's , i didn't expect that much reply's


    ok so i have here a linked list with n nodes
    i've wrote it in english

    Code:
    #include <iostream>
    
    using namespace std;
    
    struct node
    {
    	char info;
    	node *next;
    };node *first,*last;
    
    void newnode(char a);
    int main()
    {	
    	int n;
    	char k;
    	first=last=NULL;
    	cout<<"enter the number of nodes that the list have ";
    	cin>>n;
    	node *p=new node;
    	cout<<"enter the first node info ";
    	cin>>p->info;
    	p->next=NULL;
    	first=last=p;
    	for(int i=2;i<=n;i++)
    	{
    		cout<<"enter the value for "<<i<<"node ";
    		cin>>k;
    		newnode(k);
    	}
    	node *x=first;
    	while(x->next!=NULL)
    	{
    		cout<<x->info;
    		x=x->next;
    	}cout<<x->info;
    
    	return 0;
    }
    
    void newnode(char a)
    {
    	node *i=new node;
    	i->info=a;
    	last->next=i;
    	last=i;
    	i->next=NULL;
    	
    	
    }
    i have a couple of questions

    first one when i entered the while to show the nodes from the list. it works but gives an error. I'm sure is when i reach the last node it tries to do last->next and it dosen't exist. I know this but how can i correct this
    Code:
    while(x<=last)
    	{
    		cout<<x->info;
    		x=x->next;
    		
    	}
    this show me the entire list but gives an error. it tries to go to the next from the last node which dosen't exist

    second question

    can somebody give me some hint to delete nodes with an explicit info( i know we must see at the entrance at the middle and at the end) but i want to see how on this exemple

    3 question

    i have to implement 2 3 4 top down algorithm, i know it is with trees, until the end of the semester(btw i'm a fresh student ) ..where i can read some good tutorials


    thank's a lot for informations

    //best regards
    Last edited by masterg; 12-03-2008 at 08:59 PM.

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Really, you can do it like this:
    Code:
    x = head;
    while(x)
    {
        ... do stuff with x. 
        x = x->next;
    }
    (or use the for-loop style that I posted earlier).

    You should NEVER compare pointers using < or > unless they are pointing to THE SAME block of memory. If there are pointers that come from different calls to new, you can not know if the pointer is bigger or smaller than the other one you get, because there is absolutely no guarantee that new gives you memory in any particular order [it may start at a high address and go lower, if you delete something allocated early, and then use new, it will probably give you back what you just deleted, etc, etc]

    Deleting nodes need to take care of:
    deleting the first node - must update the "head" pointer.
    deleting the last node - must update the "tail" pointer.
    deleting in the middle - update next-pointer of the previous element to point to the next element.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Registered User
    Join Date
    Dec 2008
    Posts
    7
    thanks mats, your information is great but i have a question
    lets assume the next linked list
    1 2 3 3 3 5 6

    if i want to delete 3 i would delete first 3 and i'l be linked with next one

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I would probably write a generic function that deletes ONE item, and then use that repeatedly to remove the 3 bits. It's not much different, but it's often easier to deal with a slightly simpler problem.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    Registered User
    Join Date
    Dec 2008
    Posts
    7
    ok..so i'm back

    this the code so far
    Code:
    #include <iostream>
    
    using namespace std;
    
    struct node
    {
    	char info;
    	node *next;
    };node *first,*last;
    
    void newnode(char a);
    void removefirst();
    void removemiddle(node *&x);
    int main()
    {	
    	int n;
    	char k;
    	first=last=NULL;
    	cout<<"enter the number of nodes that the list have ";
    	cin>>n;
    	node *p=new node;
    	cout<<"enter the first node info ";
    	cin>>p->info;
    	p->next=NULL;
    	first=last=p;
    	for(int i=2;i<=n;i++)
    	{
    		cout<<"enter the value for "<<i<<"node ";
    		cin>>k;
    		newnode(k);
    	}
    	
    	removefirst();
    	node *x=first;
    	while(x->next!=NULL)
    	{
    		if(x->next->info=='a')
    		{
    			while(x->next->info=='a')
    			removemiddle(x);
    		}
    		
    			x=x->next;
    	}
    	x=first;
    	while(x)
    	{
    		cout<<x->info;
    		x=x->next;
    	}
    
    	return 0;
    }
    
    void newnode(char a)
    {
    	node *i=new node;
    	i->info=a;
    	last->next=i;
    	last=i;
    	i->next=NULL;
    	
    }
    
    void removefirst()
    
    {
    	while(first->info=='a')
    	{
    		node *c;
    		c=first;
    		first=first->next;
    		delete c;
    	}
    }
    
    void removemiddle(node *&x)
    {
    	node *c;
    	c=x->next;
    	x=c->next;
    	
    	delete c;
    	
    }

    i have problems with the removemiddle function, some help ???
    when i try to output. it outputs the first nodes before the node with info a ... i think there is a problem with node->next but i can't figure it out

  12. #12
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853

    Post

    Code:
    void removemiddle(node *&x)
    {
    	node *c;
    	c=x->next;
    	x=c->next;
    	
    	delete c;
    	
    }
    You pass the pointer by reference. Either pass the reference of x (node& x) or pass the pointer (node* x). You have in your code node* x = first; and then removemiddle(x); so you want void removemiddle(node* x).

    Also, the logic is wrong. You want this:
    Code:
    void removemiddle(node *x)
    {
            node* prev;
            //find previous node from x
            for (prev = head; prev  != NULL; prev  = prev ->next
                if ( prev ->next == x)
                     break;
            if (prev == NULL) {
                printf("The node doesn't exist in list");
                return;
            }
            // You have [prev] -> [x] -> [x->next]
            //link the previous o x node with the next of x node
            prev->next = x->next;
            // Now you have [prev] -> [x->next]   
            //delete safely x    
    	delete x; 
    }
    Now, finding the middle node of course isn't a good idea. But WAIT. You knew this. So you pass the previous node as I see. Well, it is a good idea to give GOOD NAMES! This would have saved me the trouble
    Code:
    void removemiddle(node *prevNode)
    So in your case:
    Code:
    void removemiddle(node *prevNode)
    {
            // You have [prevNode] -> [prevNode->next] -> [prevNode->next->next]
            //link the previous o x node with the next of x node
            prevNode->next = prevNode->next->next;
            // Now you have [prevNode]  -> [prevNode->next->next]  
            //delete safely prevNode->next    
    	delete prevNode->next ; 
    }
    Finally, since this is C++, you could make a class and pout the removes functions inside the class. That would make your code much cleaner. You would have a class node and a class list. The list class would only have a node* head, tail and the remove/add functions. So you would check if it is the middle, head or tail (by comparing with head or tail). You could just do "list.Remove(char a)" and the correct method/function would be invoked. Try it.

    Also, do you actually need the tail? Tail makes sense in a double linked list. Otherwise not really. Because you can find which is the tail. It is the node that has next == NULL and only that. So you don't need the tail

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    C_ntua: You are deleting prevNode->next when you've just changed it to prevNode->next->next - so the code would need to SAVE the original prevNode->next, then delete the saved value after updating it.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by C_ntua
    Also, do you actually need the tail? Tail makes sense in a double linked list. Otherwise not really. Because you can find which is the tail. It is the node that has next == NULL and only that. So you don't need the tail
    It depends. For example, it makes sense to maintain a pointer to the tail of a singly linked list intended to implement a queue.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Quote Originally Posted by laserlight View Post
    It depends. For example, it makes sense to maintain a pointer to the tail of a singly linked list intended to implement a queue.
    Yeah, you're right on that.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Help!
    By mbk in forum C Programming
    Replies: 3
    Last Post: 01-31-2008, 03:54 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 07:47 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  5. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 10:33 PM