delete multiple numbers from linked list

This is a discussion on delete multiple numbers from linked list within the C Programming forums, part of the General Programming Boards category; This program has to scan linked list & find occurrence o more then one instance of a number, then delete ...

  1. #1
    Registered User
    Join Date
    Jun 2004
    Posts
    123

    delete multiple numbers from linked list

    This program has to scan linked list & find occurrence o more then one instance of a number, then delete it. Output I get sometimes shows deletion of only one instance of multiple numbers, and sometimes I get the following error: "unhandalled exception in “filename: memory adress” access violation".
    I presume problem is in delemiddle.
    Please help.
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    
    typedef struct ITEM  {
    	int data;
    	struct ITEM *next;
    }item;
    
    
    void display (item *S)
    {
    	if (S==NULL) return;
    		
    	printf ("%d\t", S->data);
    	display(S->next);
    	
    }
    
    void FREE (item *headptr)
    {
    	if (headptr==NULL) return;
    	FREE (headptr->next);
    	
    }
    
    void addfirst (item **hp, int dt)
    {
    	item *temp;
    	temp=(item *)malloc (sizeof (item));
    	if (!temp) exit (1);
    	temp->data=dt;
    	temp->next =(*hp);
    	(*hp)=temp;
    }
    
    void add (item **hp, int dt)
    {
    	item  *move =(*hp);
    	item *newitem;
    	newitem=(item *)malloc (sizeof (item));
    	if (!newitem) exit (1);
    	newitem->data=dt;
    	while (move->next!=NULL)
    		move=move->next;
    	newitem->next =move->next;
    	move->next=newitem;
    }
    
    void delemiddle (item *first)            //delete extra number
    {
    	item *temp=first->next;
    	item *move=temp->next;
    	first->next=move;
    	FREE (temp);
    }
    
    void find (item **hp)    //scan list
    {
    
    	item *q=(*hp);
    	item *p=(*hp)->next;
    	while (p)
    	{
    
    		if (q->data==p->data)
    		{
    			q=p;
    			p=p->next;
    			delemiddle (p);
    		}
    
    		q=p;
    		p=p->next;
    		
    	}
    }
    
    
    
    int main (void)
    {
    	item *head=NULL;
    	int i, dt, num;
    	printf ("enter number of items\n");
    	scanf ("%d", &num);
    	for (i=0;i<num;i++)
    	{
    		printf ("enter number\n");
    		scanf ("%d", &dt);
    	if (head==NULL)
    		addfirst (&head, dt);
    	else
    		add (&head, dt);
    	}
    
    	display (head);
    	find (&head);
    	putchar ('\n');
    	display (head);
                    putchar ('\n');
    	FREE (head);
    return (1);
    }
    TIA,
    Ronen
    Last edited by ronenk; 01-15-2005 at 05:03 AM.

  2. #2
    Registered User
    Join Date
    Aug 2004
    Posts
    77
    When you find a match in the while loop of find() you then advance to the next entry in the list and delete that entry. You probably want to delemiddle(q) there instead, since q was set to point to the duplicate. Another problem there is that you advance twice in that function if you find a match, which could be causing it to skip additional duplicates. You may want to try something like:

    Code:
    if (q->data==p->data)
    {
        delemiddle (q);
        p = q->next;
    }
    
    q=p;
    p=p->next;
    I didn't try to run the program yet, but that extra move could be throwing things off.

  3. #3
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    orginally posted by Exile:
    if (q->data==p->data)
    {
    delemiddle (q);
    p = q->next;
    }

    q=p;
    p=p->next;
    tried this one, but it didn't work for me.

    I have modified this program a little: FREE & delemiddle functions where removed. find function has a little addition of scanning all list with all members plus free() the duplicate members.
    still I dont get good results.

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    
    typedef struct ITEM  {
    	int data;
    	struct ITEM *next;
    }item;
    
    
    void display (item *S)
    {
    	if (S==NULL) return;
    		
    	printf ("%d\t", S->data);
    	display(S->next);
    	
    }
    
    
    
    void addfirst (item **hp, int dt)
    {
    	item *temp;
    	temp=(item *)malloc (sizeof (item));
    	if (!temp) exit (1);
    	temp->data=dt;
    	temp->next =(*hp);
    	(*hp)=temp;
    }
    
    void add (item **hp, int dt)
    {
    	item  *move =(*hp);
    	item *newitem;
    	newitem=(item *)malloc (sizeof (item));
    	if (!newitem) exit (1);
    	newitem->data=dt;
    	while (move->next!=NULL)
    		move=move->next;
    	newitem->next =move->next;
    	move->next=newitem;
    }
    
    
    void find (item **hp)
    {
    
    	item *q=(*hp);
    	item *p=(*hp)->next, *temp;
    	while (q->next)
    	{	
    		while (p)
    		{
    			if (q->data==p->data)
    			{				
    					temp=q;
    					(*hp)=p;
    					free(temp);
    					q=(*hp);
    					p=q->next;
    			}
    		p=p->next;
    		}
    	q=q->next;
    	p=p->next;
    	}
    }
    
    int main (void)
    {
    	item *head=NULL;
    	int i, dt, num;
    	printf ("enter number of items\n");
    	scanf ("%d", &num);
    	for (i=0;i<num;i++)
    	{
    		printf ("enter number\n");
    		scanf ("%d", &dt);
    	if (head==NULL)
    		addfirst (&head, dt);
    	else
    		add (&head, dt);
    	}
    
    	display (head);
    	find (&head);
    	putchar ('\n');
    	display (head);
    	putchar ('\n');
    }

  4. #4
    Registered User
    Join Date
    Aug 2004
    Posts
    77
    Code:
    void find (item **hp)
    {
    	item *q=(*hp); 
    	item *p=(*hp)->next, *temp;
    
    	while (q->next)
    	{//This loop appears to loop through all elements in the list
    		while (p)
    		{//This loop also appears to loop through all elements in the list, I don't think you need both
    
    			if (q->data==p->data)
    			{//We found a matched value, the second copy of the value, p, should be removed
    
    					temp=q;
    					(*hp)=p;
                                            //when you change the value of hp you change the head of the list
                                            //this will effectively remove all entries before p
    					free(temp);
    					q=(*hp);
    					p=q->next;
    			}
    		p=p->next;
    		}
    	q=q->next;
    	p=p->next;
    	}
    }
    I think you are a little further from the solution on this version. When you remove a value you need to remove the value from p not q. You don't save any information on previous entries in your list so you can reset the next value in the list entry before q.

    What you need to do is adjust the next value in q, then free() p, then adjust your p value and continue looping.

    Code:
    void find (item **hp)
    {
        item *q=(*hp); 
        item *p=(*hp)->next, *temp;
    
        while (q->next)
        {
            if (q->data == p->data)
            {//Remove the duplicate in p
                q->next = p->next;
                free(p);
            }
            else
            {//Only advance to the next list entry if no match occurs
                q = q->next;
            }
            //Always reset p so that you keep moving through the list
            p = q->next;
        }
    You were OK with the delemiddle() function since thats what it did. The trouble you had was that when you advanced twice it was possible for you to try to advance past the end of the list which caused the memvory protection faults, or jump past a value that was a match.

  5. #5
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    That's perfect!
    Let’s go one step further. If want to check for duplication number accross the list.This is what I wrote & I get errors.

    Code:
    void find (item **hp)
    {
        item *q=(*hp); 
        item *p=(*hp)->next, *temp;
    
        while (q->next)
        {
    		while (p->next)
    		{
    			if (q->data == p->data)
    			{
    				temp=p;
    				p = p->next;
    				free(p);
    				p=temp;
    			}
    			else
    			{
    				p = p->next;
    			}
    		}
            q = q->next;
        }
    }

  6. #6
    Registered User
    Join Date
    Aug 2004
    Posts
    77
    Code:
    temp=p;
    p = p->next;
    free(p);
    p=temp;
    You set temp equal to p, then got rid of p by free()-ing it. So when you set p equal to temp you aren't getting anything useful in p, so next time through the loop when you try to read from p->next its gonna bomb with a memory protection error, since that buffer is gone.

    Next issue is you aren't updating the entry in the list before p. So when you remove p, the previou list entry will still point to the entry that was removed. You will need to keep track of that previous entry to do that update.

    Code:
    void find (item **hp)
    {
        item *q=(*hp); 
        item *p=(*hp)->next, *temp, *Prev;
    
        while (q->next)
        {
            Prev = q; //Set the initial previous value
            while (p->next)
            {
                if (q->data == p->data)
                {
                    Prev->next=p->next; //Correct the previous enty
                    temp = p->next;
                    p = p->next;
                    free(p);
                    p=temp;
                }
                else
                {
                    Prev = p; //Update the previous value
                    p = p->next;
                }
            }
            q = q->next;
        }
    }
    I think that will cover the correction of the previous entry. The whole point of that is to keep the links in the list correct.

  7. #7
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    I had to modify this function a bit, & it still doesn't fluently do the job. What i noticed was that on smaller lists: up to 5 five numbers, its OK. above it: list got lost...
    Code:
    void find (item **hp)
    {
        item *q=(*hp); 
        item *p=(*hp)->next, *temp, *Prev;
        while (q->next)
        {
            Prev = q;
            while (p)
            {
                if (q->data == p->data)
                {
                    Prev->next=p; 
                    temp = p->next ;
                    free(p);
                    p=temp;
    	Prev->next=p;
    	p=Prev;
               }
                else
                {
                    Prev = p; 
             
                }
                p = p->next;
            }
            q = q->next;
            p=q->next;
    
        }
    }
    please help me with the fine tuning of it.

    TIA,

    Ronen.

  8. #8
    Registered User
    Join Date
    Aug 2004
    Posts
    77
    After compiling and playing with the program for a bit I saw a few issues with the code. It seems you caught them and attempted some fixes. Guess thats what I get for not testing it before posting.

    Anyway,

    Code:
    void find (item **hp)
    {
        item *q=(*hp); 
        item *p=(*hp)->next, *temp, *Prev;
        while (q->next)
        {
            Prev = q;
            while (p)
            {
                if (q->data == p->data)
                {
    //p is the list entry you are about to get rid of.  You need to have 
    //The list skip it, so this should be: Prev->next = p->next;
                    Prev->next=p; 
                    temp = p->next ;
                    free(p);
                    p=temp;
    //You just free()-ed p, so its an invalid buffer you definately do not
    //want to save a pointer to an invalid buffer
    	Prev->next=p;
    	p=Prev;
               }
                else
                {
                    Prev = p; 
             
                }
                p = p->next;
            }
            q = q->next;
            p=q->next;
    
        }
    }
    Once I made those couple changes it seemed to work fine for lists of up to 20 entries. The line Prev->next = p; is the one that is causing the crashes. Next pass through the loop causes it to attempt to access the invalid buffer which causes a memory protection fault.

    Aside from the two comments I have in the code block above, everything else seemed fine.

  9. #9
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    tried to run code & its still no good.

    //p is the list entry you are about to get rid of. You need to have
    //The list skip it, so this should be: Prev->next = p->next;
    this comment is clear & I've fixed it.


    //You just free()-ed p, so its an invalid buffer you definately do not
    //want to save a pointer to an invalid buffer
    didn't understand this one , though. what is the buttom line here?

  10. #10
    Registered User
    Join Date
    Aug 2004
    Posts
    77
    The line right after the comment:
    Code:
    Prev->next=p;
    isn't needed. I didn't want to just say take it out since you may have been intending to do something else. When I ran it everything worked without that line.
    Last edited by Exile; 01-18-2005 at 08:15 AM.

  11. #11
    Registered User
    Join Date
    Aug 2004
    Posts
    77
    Theres probably a few other cleanup type things that could be done. Like temp holds the same information as Pre->next, so you may be able get rid of temp.

    And you aren't cleaning up all of the list properly. The original FREE() function didn't actually release the buffers. You said you got rid of that function so I can't say how that works now.

    I think though the core logic you were looking for is working.

  12. #12
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    this is the code i'm rubning without Prev->next=p; & i still get errors.
    Code:
    void find (item **hp)
    {
        item *q=(*hp); 
        item *p=(*hp)->next, *temp, *Prev;
    
        while (q->next)
        {
            Prev = q;
            while (p)
            {
    		
                if (q->data == p->data)
                {
                    Prev->next=p->next; 
                    temp = p->next ;
                    free(p);
                    p=temp;
    				p=Prev;
    			}
                else
                {
                    Prev = p; 
                
                }
    			p = p->next;
            }
            q = q->next;
    		p=q->next;
    
        }
    }

  13. #13
    Registered User
    Join Date
    Aug 2004
    Posts
    77
    What are the numbers you enter, and what is the error you are getting?

  14. #14
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    this is a sample of input:
    enter number of items
    10
    enter number
    1
    enter number
    2
    enter number
    3
    enter number
    1
    enter number
    2
    enter number
    3
    enter number
    1
    enter number
    2
    enter number
    3
    enter number
    1

    this is the error i get in the debbuger: "unhandalled exception in “filename: memory adress” access violation"

  15. #15
    Registered User
    Join Date
    Aug 2004
    Posts
    77
    Code:
    void find (item **hp)
    {
        item *q=(*hp); 
        item *p=(*hp)->next, *temp, *Prev;
    
        while (q->next)
        {
            Prev = q;
            while (p)
            {
    		
                if (q->data == p->data)
                {
                    Prev->next=p->next; 
                    temp = p->next ;
                    free(p);
                    p=temp;
    		p=Prev;
    	    }
                else
                {
                    Prev = p; 
                
                }
    	    p = p->next;
            }
    
    //These updates are causing the problem, comments below
            q = q->next;
    	p=q->next;
    
        }
    }
    In your example the list becomes:
    1, 2, 3, 1, 2, 3, 1, 2, 3, 1
    On the first pass through all the 1's are removed, so the list becomes:
    1, 2, 3, 2, 3, 2, 3
    On the second pass all of the 2's are removed, so the list becomes:
    1, 2, 3, 3, 3
    As it goes through that it removes the extra 3's, and the list is:
    1, 2, 3
    And q is pointing to the 3. Now q then gets set to q->next, which is NULL sine its the last entry in the list. When the loop goes through the condition looks at q->next, since q is NULL its crashing because NULL is an invalid pointer. So to fix it you can change the end of the loop to be:

    Code:
    if (q->next != NULL)
    {
        q = q->next;
        p=q->next;
    }
    else
    {
        break;
    }
    You may be able to get away with setting the condition of the outer loop to:
    Code:
    while ((q != NULL)&&(q->next != NULL))
    but I didn't test that to see how well it worked.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. deleting a node in linked list
    By BoneXXX in forum C Programming
    Replies: 18
    Last Post: 12-17-2007, 12:30 PM
  2. instantiated from here: errors...
    By advocation in forum C++ Programming
    Replies: 5
    Last Post: 03-27-2005, 09:01 AM
  3. linked list recursive function spaghetti
    By ... in forum C++ Programming
    Replies: 4
    Last Post: 09-02-2003, 03:53 PM
  4. doubly linked list error.
    By noob2c in forum C++ Programming
    Replies: 12
    Last Post: 09-01-2003, 11:49 PM
  5. Array, Linked List, or Binary Tree?
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 01-05-2002, 10:07 PM

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