Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

[SOLVED] Copy Linked List Function

linked list

  • This topic is locked This topic is locked
17 replies to this topic

#13 kernelcoder

kernelcoder

    CC Devotee

  • Expert Member
  • PipPipPipPipPipPip
  • 990 posts
  • Location:Dhaka
  • Programming Language:C, Java, C++, C#, Visual Basic .NET
  • Learning:Objective-C, PHP, Python, Delphi/Object Pascal

Posted 23 May 2012 - 09:04 AM

Where is the definition of Elem structure? Where is the creation of the structure while taking input from console?
  • 0

#14 Agent001

Agent001

    CC Regular

  • Member
  • PipPipPip
  • 41 posts

Posted 23 May 2012 - 09:07 AM

That bit of code is a part of a bigger program, so it would be too long to post it all.
The loading of the list works good, i tested that.

Here's the structure.
//Element
typedef struct elem {
    int priority;
    float start,end;
    struct elem *next;
} Elem;

  • 0

#15 kernelcoder

kernelcoder

    CC Devotee

  • Expert Member
  • PipPipPipPipPipPip
  • 990 posts
  • Location:Dhaka
  • Programming Language:C, Java, C++, C#, Visual Basic .NET
  • Learning:Objective-C, PHP, Python, Delphi/Object Pascal

Posted 23 May 2012 - 09:20 AM

Well, do you want us to fix compile errors for you? Please try your best to paste some code that will compile without errors.
  • 0

#16 Agent001

Agent001

    CC Regular

  • Member
  • PipPipPip
  • 41 posts

Posted 23 May 2012 - 09:27 AM

The code from this post compiles without errors - the program starts.

But, as i said - it doesn't do the following:
when i enter x amout of SAME ELEMENETS - for example, i enter 4 elements, of which, all have the same parameters - the program should leave only one element in the list, and delete other 3.

But, it doesn't do that, and i can't figure out why.

As far as i can see, it does the rest fine.

EDIT:
I'm just testing it out now:
it seems that whenever i enter more than two same elements, it leaves me two same elements in the list.
I enter five same elements in the list, it leaves me 2 same elements, instead of one.
I enter four same elements it leaves me only two, but when i enter two it leaves me one.

When i say same elements, i mean - i enter five times 12 and 13... If i enter them 5 times, that means i have 5 overlaping elements, and only one should stay in the list.
  • 0

#17 kernelcoder

kernelcoder

    CC Devotee

  • Expert Member
  • PipPipPipPipPipPip
  • 990 posts
  • Location:Dhaka
  • Programming Language:C, Java, C++, C#, Visual Basic .NET
  • Learning:Objective-C, PHP, Python, Delphi/Object Pascal

Posted 23 May 2012 - 10:30 AM

Well, I didn't look into your code as I said it was causing compiling errors here. You know, we want to help you to learn. In your case, I was expecting some code that I'll be able to compile and see output and help you to find out errors in your code. I think your problem was in the deletion of a item. When you need to delete a node from a linked list, you have to link the next node to the previous node before deletion. However, following is the code that I made as your requirements. I even tested with the two samples you said.

#include <stdio.h>

struct __Elem__
{
       int priority;
       float start, end;
       struct __Elem__ *next;
};

typedef struct __Elem__ Elem;

Elem *copy(Elem *L1)
{
     Elem*  L2 = 0;
     Elem* preElem = 0;

     // Move through all the nodes in source list.
     while(L1 != 0) {

          // Create the memory for the destination list node.
          Elem *elem = (Elem*)malloc (sizeof(Elem));

          if(elem == 0) {
               printf("Failed allocation!"), exit(1);
          }

          // Copy the data from the source to dest node
          elem->priority = L1->priority;
          elem->start = L1->start;
          elem->end = L1->end;
          elem->next = 0;

          if (L2 == 0) {
                // keep the root for the destination list.
                L2 = elem;
                preElem = elem;
          }
          else {
                // point the newly created node to the previous created node.
                preElem->next = elem;
                // keep the new node to use it as previous node in next node creation.
                preElem = elem;
          }

          L1 = L1->next;
    }

    return L2;
}


void print(Elem* l)
{
     // Loop through the L2 and print value for each node of it
     while(l != 0) {
          printf("%d %.2f %.2f\n", l->priority, l->start, l->end);
          l = l->next;
     }
}


void deleteList(Elem* l)
{
     Elem* tmp;
     while(l != 0) {
          tmp = l->next;
          free(l);
          l = tmp;
     }
}


int isOverlapp(Elem* first, Elem *second)
{
     return (first->end >= second->start && first->end <= second->end) ||
          (second->end >= first->start && second->end <= first->end) ? 1 : 0;
}

Elem* removeOverlapping(Elem* L)
{
     Elem* root = (Elem*)malloc (sizeof(Elem));
     int removeFirst = 0;
     Elem* i = L, *j;
     Elem* pre1, *pre2; 
     root->next = L;
     pre1 = root;

     while(i != 0 && i->next != 0) {
          j = i->next;
          pre2 = i;

          while (j != 0) {
               if (isOverlapp(i, j)) {
                    if (i->priority < j->priority) {
                         removeFirst = 1;
                    }
                    else if (i->priority > j->priority) {
                         removeFirst = 0;
                    }
                    else {
                         removeFirst = i->start > j->start ? 1 : 0;
                    } 

                    if (removeFirst) {
                         pre1->next = i->next;
                         free(i);
                         i = pre1;
                         break;
                    } 
                    else {
                         pre2->next = j->next;
                         free(j);
                         j = pre2;
                    } 
               }

               pre2 = j;
               j = j->next;
          } 

          pre1 = i;
          i = i->next;
     }

     L = root->next;
     free(root);
     return L;
}


Elem* create(int p, float s, float e)
{
    Elem * node = (Elem*)malloc (sizeof(Elem)); // First node
    node->priority = p; node->start = s; node->end = e;
    node->next = 0;
    return node;
} 


void main()
{
     Elem * L;
     // Example1: mix items
     L = create(1, 12, 13);
     L->next = create(1, 11.30f, 13.30f);
     L->next->next = create(2, 12.30f, 13.30f);
     L->next->next->next = create(1, 12, 13);
     L->next->next->next->next = create(1, 12, 13);
     printf("Example 1.... Original List#\n");
     print(L);

     printf("\n\nAfter removing overlappiing#\n");
     L = removeOverlapping(L);
     print(L);
     deleteList(L);


     // Example 2: All items are same
     L = create(1, 12, 13);
     L->next = create(1, 12, 13);
     L->next->next = create(1, 12, 13);
     L->next->next->next = create(1, 12, 13);
     L->next->next->next->next = create(1, 12, 13);
     printf("\n\n\nEample 2..... Original List#\n");
     print(L);

     printf("\n\nAfter removing overlappiing#\n");
     L = removeOverlapping(L);
     print(L);
     deleteList(L);          
}

  • 0

#18 Agent001

Agent001

    CC Regular

  • Member
  • PipPipPip
  • 41 posts

Posted 23 May 2012 - 10:45 AM

kernelcoder, thank you very much for your effort.
the thing is that i need to do several things in this task, and make all of them as functions.

So, i have one function to load the list, one to delete it, one (which you helped me make it) to copy one list to another, one function to append an element to the end of the list, one to append the function to the begining of the list and so on.

The program has around 400 lines of code, and it's divided into several files. So that's why i didn't post it.

I had a function that deletes a certain element from a list (for example, 3rd or fourth or...) and i used that one in my function.

However - i see that the error was that i incremented the counter j without a reason. When i delete the element bellow the one with whom i'm comparing it to - i decrement the lenght of a list by one, and i increment j which represents the current position of the second element - and that's my error.

IE, when i compare first and third element, and i delete the third one, the fourth element in my old list becomes third one, but my counters says i compare first and fourth, and that's why one element is skipped.
  • 0





Also tagged with one or more of these keywords: linked list

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download