Writing ADT Functions

[Jedijacob]

Hi, I was given an assignment to write two functions.

The first function is rather easy and I think I have it. However, the second function is an ADT function called MergeList, which merges two lists using a linked list implementation with a dummy node. The function returns the new list.

List MergeLists(List L1, List L20
{
  list newlist;
  newlist = (List)malloc(sizeof(listCDT));
  if(!newlist)
  {
    printf("Memory allocation error!\n");
    exit(1);
  }
  newlist->size = 0;
  newlist->link = (listnode*)malloc(sizeof(listnode));
  if (!newlist)
  {
     printf("Memory allocation error!\n");
     exit(1);
  }
  (newlist->link)->link = (L1->link)->link;
                             .
                             .
                             .

return newlist;
}

I realize that I must traverse L1 and see when the link is NULL then make the link to (L2->link)->link. Is this correct? Does my code seem to be in order so far? Can anyone offer any suggestions or corrections? Thanks so much. As always, your help is GREATLY appreciated!!!

Thanks,
Jacob

[quzah]

Are you just trying to append one list to the next? Or are you sorting them both into one list, or what exactly? If all you're doing is appending one to the other:

for( node = list1; node->next; node = node->next )
    ;

node->next = list2;

return list1;

That assumes you've actually passed two valid lists. It then appends the second list on the first, and returns the first list. (Which is now actually both lists in one long list.)

If you're sorting them and making one big sorted list out of both of them, then you just write a function to insert in order, one node. You then call that function with each individual node of either list, inserting into the other. When you're done, return the big list.


Quzah.

[Jedijacob]

I must create a new list that appends the two lists that are input into the function. However, those two functions must remain unchanged; so, if I printed out one of the original list it would remain the same. Thanks for your help Quzah. Any more help would be greatly appreciated! Thanks!!!

[quzah]

Well you should generalize this as much as you can. You can reuse your "create node" function (or whatever you call it).Now, this assumes you have a function which will take a list to add to, and what to add, and do your allocation and addition in one shot. If you don't have one, you should. If you don't want one:

for each node in list one
    allocate a new node
    copy the data from this current item into the  new node
    add this new node to the end of the new list
for each node in list two
    allocate a new node
    copy the data from this current item into the  new node
    add this new node to the end of the new list

return the new list

This is homework after all, you should at least do something on your own.

Quzah.

[Jedijacob]

I'm so sorry. Computer science instructor just e-mailed us correcting the assignment. He states that a new list must be created that is independent of L1 and L2; so, he can destroy L1 or L2 and still be able to print out the new list. I have written some code and I'll post it below and maybe I can get some feedback =)! Thanks again!!!

List MergeLists(List L1, List L2)
{
  List newlist;
  listnode *tmp;

  newlist = (List)malloc(sizeof(listCDT));
  if(!newlist)
  {
    printf("Memory allocation error!\n");
    exit(1);
  }
  newlist->link = (listnode*)malloc(sizeof(listnode));
  if(!newlist)
  {
    printf("Memory allocation error!\n");
    exit(1);
  }
  (newlist->link)->link = NULL;

  if((L1->link)->link == NULL && (L2->link)->link == NULL)
    return newlist;

  else if((L1->link)->link == NULL)
  {
    (newlist->link)->link = (L2->link)->link;
    return newlist;
  }

  else if((L2->link)->link == NULL)
  {
    (newlist->link)->link = (L1->link)->link;
    return newlist;
  }

  else
  {
    (newlist->link)->link = (L1->link)->link;
    tmp = (L1->link)->link;
    while(tmp->link != NULL)
      tmp = tmp->link;
    tmp->link = (L2->link)->link;
    return newlist;
  }

}

[Hammer]

Did you read quzah's last post? Does that help you?