Removing duplicates from a linear singly linked list.
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Thread: Removing duplicates from a linear singly linked list.

  1. #1
    Join Date
    Jun 2008
    Posts
    17

    Removing duplicates from a linear singly linked list.

    I was trying to develop a procedure to delete duplicates from a linear singly linked list.

    To keep the things simple I hard coded the values into the sample list.

    I used the VC++6.0 compiler, using the console application.

    when I run the procedure I got runtime error. When I tried to debug, I found that the

    exception was occuring when deleting the duplicate node.

    Is there anything wrong with the procedure ?

    If so, could anybody correct it ?

    I had put my sincere efforts on this, but could not..

    I request kind assistance from any quarter.

    please find the attached the c++ source code file along with.
    Attached Files Attached Files

  2. #2
    Join Date
    Apr 1999
    Posts
    27,444

    Re: Removing duplicates from a linear singly linked list.

    Quote Originally Posted by sreehari_mysore View Post
    I was trying to develop a procedure to delete duplicates from a linear singly linked list.
    First, is this a 'C' or C++ program? If it's a C++ program, and this is not a school exercise, C++ has std::list and std::unique to do this work instead of coding this yourself.

    Second, did you use the debugger? If not, please do so, as questions as to "why does my program not work?" can be solved by using the debugger and single-step through the code, watching each variable.

    Also, if you're learning C++, Visual C++ 6.0 should not be used for learning. It is not an ANSI standard compiler (it is more than 10 years old), and many things that are standard and correct in ANSI C++ will not compile using VC 6.0, and things that are incorrect in ANSI C++ will compile in VC 6.0

    Get the latest version of Visual C++ if you are learning the language.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; January 20th, 2009 at 01:37 PM.

  3. #3
    Join Date
    Jun 2008
    Posts
    17

    Re: Removing duplicates from a linear singly linked list.

    Hi,

    This is not a C++ program. It is a simple C Program (non Object oriented). And not even the school homework.

    While Debugging, it generates the exceptional error while tying to delete the duplicate node i.e., free().


    I run this code on the latest Visual Studio 2005 compiler, using console application. But it also produces the same exceptional error.


    I even tried with some variations, using the code snippets given in some of the standard Text Books on the subject, Data Structures. But still the same result.


    Any ideas on this ?

    Could anybody kindly spend some of your valuable time on this ?

    Regards,
    Sreehari Mysore
    Last edited by sreehari_mysore; January 21st, 2009 at 01:29 PM. Reason: typo

  4. #4
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,891

    Re: Removing duplicates from a linear singly linked list.

    An error during free() usually means one of two things:
    1) The pointer you're trying to free was not returned from malloc() or calloc(), or
    2) You've managed to overwrite memory that doesn't belong to you at some point. The heap manager doesn't check for this until you invoke it, so the problem isn't necessarily anywhere near when the error arises.

    Are you on Windows or Linux? If the latter, try using valgrind to spot the issue.

  5. #5
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,206

    Re: Removing duplicates from a linear singly linked list.

    You can only call free on memory that was allocated using malloc. You're trying to free stack allocated structs.

  6. #6
    Join Date
    Apr 1999
    Posts
    27,444

    Re: Removing duplicates from a linear singly linked list.

    Quote Originally Posted by sreehari_mysore View Post
    Hi,

    This is not a C++ program. It is a simple C Program (non Object oriented).
    So why is the extension ".cpp"? It will be compiled as a C++ program given that extension using Visual Studio 2005.
    And not even the school homework.
    Anytime an assignment (that is too contrived to be a real-world program) is given to you, whether it is from a school, a friend, or you give one to yourself, it is "homework".
    I even tried with some variations, using the code snippets given in some of the standard Text Books on the subject, Data Structures. But still the same result.
    The error is obvious in that you're calling free() on values that were not returned to you by malloc().

    Since you made such a very simple error, all I can say is that you can't learn C or C++ programming from a Data Structures book. You learn C or C++ programming from C or C++ programming books. Data structures assumes you know the language already, and you're learning to build linked lists, trees, etc.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; January 22nd, 2009 at 08:52 PM.

  7. #7
    Join Date
    Nov 2003
    Posts
    1,405

    Re: Removing duplicates from a linear singly linked list.

    Quote Originally Posted by sreehari_mysore View Post
    Is there anything wrong with the procedure ?
    Yes there is.

    You're not in touch with your program.

    A program should be developed in small steps, and each step should be working. You start out with a working program and you finish with a working program.

    This is called Stepwise Refinement and it's the mother of all program development techniques.
    Last edited by _uj; January 23rd, 2009 at 04:08 AM.

  8. #8
    Join Date
    Jun 2008
    Posts
    17

    Re: Removing duplicates from a linear singly linked list.

    Ya ...
    that is known. all the memory cannot be deleted by free(). it can only delete the memory which is allocated by malloc().

    But here the problem is something else ....

    I am still working on that...

    regards,
    Shreehari

  9. #9
    Join Date
    Jun 2008
    Posts
    17

    Re: Removing duplicates from a linear singly linked list.

    I think there is nothing wrong in running a C program (non-object oriented) using .cpp extension.

    I agree that it is not a real world problem, but only an acadamic level one.

    It is known that all the memory cannot be deleted by free(). It can only delete the memory which is allocated by malloc().

    But here the problem is something else ....

    I am working on that ...

    Regards,
    Shreehari

  10. #10
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,357

    Re: Removing duplicates from a linear singly linked list.

    Quote Originally Posted by sreehari_mysore
    I think there is nothing wrong in running a C program (non-object oriented) using .cpp extension.
    C and C++ are different programming languages, and C++ is not quite a superset of C. For example, this is a valid C program that any standard conforming C++ compiler would fail to compile:
    Code:
    #include <stdlib.h>
    
    int main()
    {
        int *p = malloc(sizeof(*p));
        free(p);
        return 0;
    }
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  11. #11
    Join Date
    Apr 1999
    Posts
    27,444

    Re: Removing duplicates from a linear singly linked list.

    Quote Originally Posted by sreehari_mysore View Post
    I think there is nothing wrong in running a C program (non-object oriented) using .cpp extension.
    Have you ever tried to compile a real-world 'C' program, written by 'C'-only programmers in a C++ compiler? More times than not, there are hundreds of syntax errors when compiled using C++ rules. Not only that, there are some 'C' modules that require they be compiled using a 'C' compiler.

    So saying that there is nothing wrong in running a 'C' program using a .cpp extension is absolutely false.

    Regards,

    Paul McKenzie

  12. #12
    Join Date
    Jun 2008
    Posts
    17

    Re: Removing duplicates from a linear singly linked list.

    Quote Originally Posted by laserlight View Post
    C and C++ are different programming languages, and C++ is not quite a superset of C. For example, this is a valid C program that any standard conforming C++ compiler would fail to compile:
    Code:
    #include <stdlib.h>
    
    int main()
    {
        int *p = malloc(sizeof(*p));
        free(p);
        return 0;
    }

    C++ is not quite a superset of C.

    Yes... of course... but with a few changes, every C program is also a program of C++. the proper type casting is one among them in the example that was mentioned.

    Regards,
    Shreehari M

  13. #13
    Join Date
    Jun 2008
    Posts
    17

    Re: Removing duplicates from a linear singly linked list.

    Yes ... the proper changes as to be made to a C program to run it as a C++ program.

    But here, my intension is not a conflict between C and C++, but to develop a procedure to supress the duplicates of the list.

    And , I got some convencing solution for this .. at last...

    Thanks and Regards,
    Shreehari Mysore

  14. #14
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,891

    Re: Removing duplicates from a linear singly linked list.

    Quote Originally Posted by sreehari_mysore View Post
    C++ is not quite a superset of C.

    Yes... of course... but with a few changes, every C program is also a program of C++. the proper type casting is one among them in the example that was mentioned.

    Regards,
    Shreehari M
    That's becoming less and less true with each revision of their respective standards. You shouldn't be thinking that way anymore. For one thing, C99 supports static runtime-sized arrays, while C++ does not.

    Anyway, the easiest way to remove duplicates efficiently is to sort the list and then check adjacent nodes. In some very specific cases you can do something more efficient----for instance if the field you're sorting on has a small number of possible values you can just tick a box for each one as you encounter it and eliminate any nodes that correspond to ticked boxes.

    If you were to actually use C++ there would be a simple way: just insert the list into a std::set, and then read the results back into the list.
    Last edited by Lindley; January 26th, 2009 at 01:08 PM.

  15. #15
    Join Date
    Jun 2008
    Posts
    17

    Re: Removing duplicates from a linear singly linked list.

    I will certainly try it out with std::set.

    Regards,
    Shreehari

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center