6 replies to this topic

[nishbur]

hi everybody! thank you for viewing my post in order to help me
i've created to linked list below start_ptr and begin_ptr.
i just want to join the 2 linked lists in any order and i want to display the results
the selected code below (in bold) is the one that should be modified to get the appropriate result 
thank u 

#include < iostream.h>

struct node
{
    int age;
    node *nxt;
};

node *start_ptr= NULL;
node *current;
int choice = 7;

struct node1
{
    int age1;
    node1 *nxt;
};

node1 *begin_ptr= NULL;
node1 *current1;


void add_node1()
  {  node *temp, *temp2;   // Temporary pointers

     // Reserve space for new node and fill it with data
     temp = new node;
     cout << endl<<"Please enter number: ";
     cin >> temp->age;
     temp->nxt = NULL;

     // Set up link to this node
     if (start_ptr == NULL)
       { start_ptr = temp;
     current = start_ptr;
       }
     else
       { temp2 = start_ptr;
         // We know this is not NULL - list not empty!
         while (temp2->nxt != NULL)
           {  temp2 = temp2->nxt;
              // Move to next link in chain
           }
         temp2->nxt = temp;
       }
  }

void display_node1()
  {  node *temp;
     temp = start_ptr;
     cout << endl;
     if (temp == NULL)
       cout << "The list is empty!" << endl;
     else
       { while (temp != NULL)
       {  // Display details for what temp points to
              cout << "Age : " << temp->age << endl;
               cout << endl;
          temp = temp->nxt;

       }
     cout << "End of list!" << endl;
       }
  }
void add_node2()
  {  node1 *temp, *temp2;   // Temporary pointers

     // Reserve space for new node and fill it with data
     temp = new node1;
     cout <<endl<< "Please enter number: ";
     cin >> temp->age1;
     temp->nxt = NULL;

     // Set up link to this node
     if (begin_ptr == NULL)
       { begin_ptr = temp;
     current1 = begin_ptr;
       }
     else
       { temp2 = begin_ptr;
         // We know this is not NULL - list not empty!
         while (temp2->nxt != NULL)
           {  temp2 = temp2->nxt;
              // Move to next link in chain
           }
         temp2->nxt = temp;
       }
  }

void display_node2()
  {  node1 *temp;
     temp = begin_ptr;
     cout << endl;
     if (temp == NULL)
       cout << "The list is empty!" << endl;
     else
       { while (temp != NULL)
       {  // Display details for what temp points to
              cout << "Age : " << temp->age1 << endl;
               cout << endl;
          temp = temp->nxt;

       }
     cout << "End of list!" << endl;
       }
  }
[B]
void merge_list(struct node1 *begin_ptr ,struct node *start_ptr)
{    
    if (start_ptr == NULL || begin_ptr == NULL)
    return; // In case of null pointers, do nothing
    while (begin_ptr->nxt != NULL)
    begin_ptr = begin_ptr->nxt;
    begin_ptr->nxt = start_ptr;

}[/B]



void main()
{
    start_ptr = NULL;
    begin_ptr = NULL;

    do
    {
        cout << "***************************"<<endl;
        cout << "1.Add Records to list #1"<<endl<<endl;
        cout << "2.Display list #1" <<endl<<endl;
        cout << "3.Add Records to list #2"<<endl<<endl;
        cout << "4.Display list #2" <<endl<<endl;
        cout << "5.Merge list #1 and list #2"<<endl<<endl;
        cout << "6.Display Merged list" <<endl<<endl;
        cout << "7.Quit"<<endl<<endl;
        cout << endl;
        cout << " >>>";

        cin>> choice;
        switch(choice)
        {
            case 1: add_node1();break;
            case 2: display_node1();break;
            case 3: add_node2();break;
            case 4: display_node2();break
            case 5: merge_list();break;
            case 6: display_list();
        
        
        }
    }
        while (choice != 7);
}

[bobdark]

How about something like this:

typedef struct nodeStruct {
    element   value;
    struct nodeStruct* next;
    struct nodeStruct* previous;
//    int index;
}  listNodeStruct;
typedef  listNodeStruct* listNode;

typedef struct listHeadStruct{
    listNode head;
    listNode tail;
    listNode iterator;
    copy userCopy;
    compare userCompare;
//    print userPrint;
    kill userKill;
    
} listStruct;
typedef listStruct* list;

ListResult merge(list first, list second){
    //params check
    first->tail->next = second->head;
    second->head->previous = first->tail;
    first->tail = second->tail;
    return ListSuccess;
}

I took the declarations of list and list node from my old implementation of list and just quickly wrote the approximate code for merge.So sorry if it doesn't compile or whatever. ListResult is an enum I defined and didn't put it here, it uses mostly to indicate what was wrong if some function could not be executed properly.
Oh and same for the copy, kill, print, compare - those are typedefs for functions that should be provided by the user.

[nishbur]

hi bobdark i am newbie in programming i know u trying hard to help
but can u upload ur hold program or e-mail ur cpp file in order for me to understand it well
thanks for ur help

[bobdark]

I'm very sorry but I can not upload these specific files for some reasons. I will be very glad though to help you by explaining and pointing out errors in your code.

[nishbur]

thanks bobdark i'll try explain it more in order for you to help

list 

*********
| 1 | 4 | -> NULL
*********


list2

*********
| 9 | 7 | -> NULL
*********

how to list3 should be


list3

******************
| 1 | 4 |9 | 7 | -> NULL (Unsorted)
*****************

or

******************
| 1 | 4 |7 |9 | -> NULL (sorted)
*****************

below in the code (modified from that posted before)

void merge_list()
{

don't know really what to write, despite having google the answer 


}

#include < iostream.h>

[B]struct node
{
    int age;
    node *nxt;
};

node *list= NULL;
node *list1 =  NULL;
node *list2= NULL;
node *current;
node *current1;[/B] 

int choice = 7;


void add_node1()
  {  node *temp, *temp2;   // Temporary pointers

     // Reserve space for new node and fill it with data
     temp = new node;
     cout << endl<<"Please enter number: ";
     cin >> temp->age;
     temp->nxt = NULL;

     // Set up link to this node
     if (list == NULL)
       { list = temp;
     current = list;
       }
     else
       { temp2 = list;
         // We know this is not NULL - list not empty!
         while (temp2->nxt != NULL)
           {  temp2 = temp2->nxt;
              // Move to next link in chain
           }
         temp2->nxt = temp;
       }
  }

void display_node1()
  {  node *temp;
     temp = list;
     cout << endl;
     if (temp == NULL)
       cout << "The list is empty!" << endl;
     else
       { while (temp != NULL)
       {  // Display details for what temp points to
              cout << "Age : " << temp->age << endl;
               cout << endl;
          temp = temp->nxt;

       }
     cout << "End of list!" << endl;
       }
  }
void add_node2()
  {  node *temp, *temp2;   // Temporary pointers

     // Reserve space for new node and fill it with data
     temp = new node;
     cout << endl<<"Please enter number: ";
     cin >> temp->age;
     temp->nxt = NULL;

     // Set up link to this node
     if (list1 == NULL)
       { list1 = temp;
     current1 = list1;
       }
     else
       { temp2 = list1;
         // We know this is not NULL - list not empty!
         while (temp2->nxt != NULL)
           {  temp2 = temp2->nxt;
              // Move to next link in chain
           }
         temp2->nxt = temp;
       }
  }

void display_node2()
  {  node *temp;
     temp = list1;
     cout << endl;
     if (temp == NULL)
       cout << "The list is empty!" << endl;
     else
       { while (temp != NULL)
       {  // Display details for what temp points to
              cout << "Age : " << temp->age << endl;
               cout << endl;
          temp = temp->nxt;

       }
     cout << "End of list!" << endl;
       }
  }

[B]void merge_list()
{

}[/B] 

[B]    
void main()
{
    list = NULL;
    list1 = NULL;
    List2 = NULL;
[/B] 
    do
    {
        cout << "***************************"<<endl;
        cout << "1.Add Records to list #1"<<endl<<endl;
        cout << "2.Display list #1" <<endl<<endl;
        cout << "3.Add Records to list #2"<<endl<<endl;
        cout << "4.Display list #2" <<endl<<endl;
        cout << "5.Merge list #1 and list #2"<<endl<<endl;
        cout << "6.Display Merged list" <<endl<<endl;
        cout << "7.Quit"<<endl<<endl;
        cout << endl;
        cout << " >>>";

        cin>> choice;
        switch(choice)
        {
            case 1: add_node1();break;
            case 2: display_node1();break;
            case 3: add_node2();break;
            case 4: display_node2();break;
    [B]        case 5: merge_list();[/B]
            
        }
    }
        while (choice != 7);
}

    

Edited by ZekeDragon, 21 March 2010 - 12:38 AM.
You should use [code] tags instead of [quote] tags.

[nishbur]

thanks bolid! i would be really gratefull if u continue help

the end of list should point to list2

list->list2
list3= list->list2

how will i code it , i am trying for the past 7 days, still i can't get an answer

[bobdark]

You didn't get my idea. You represent your linked list only by the first node, from which all other nodes are reachable. So if you want to merge two such lists, you have to find the last node in one of them, and concatenate to this node the first node of the second list.
I represent a list by a struct that has pointers to first and last nodes of the list, and other useful information. This helps because I don't have to iterate over the whole list in order to find the last node. In my implementation I access the last node and make it's 'next' field point to the 'head' of the second list.
If you want it sorted, the implementation depends on the invariants you keep true. If the given lists are sorted, what you do is this: you keep two iterators, one per list, at the start each iterator points to the first node of each list.
At each step you compare the nodes that are pointed to by the iterators and for the smaller node, insert it to the new list and advance its iterator to the next node in that list.
When one of the lists finishes, concatenate the rest of the second list to the resulted new list. Basically its called merge sort if I'm not wrong - try googling it.
If your lists are not sorted, you will have to find at each iteration the minimal value and insert it to the new list. Of course there are other methods too, there are even tutorials here in the forum on array sorting - you can read them and use the provided ideas and methods.
I'm sorry if I was unclear, if you don't understand I will right down the algorithms later.