C++| Merge Linked Lists

Question

So I've been doing a home assignment on data structures and for more than a couple hours I'm in a dead end. To explain, I have to text files ListJava and ListDS where i take information in the format : Name Surname NUM grade . Both of the files contain the same names but not the same order. The assignment basically wants us to merge sort the files.

These are my structures:

typedef struct student
{
    string name;
    string surname;
    int am;
    int grade;
}StudentFile;
typedef struct node {

    StudentFile element;
    struct node* next;
}Node;

typedef struct stud 
{
    string name;
    string surname;
    int am;
    int grade;
    int grade2;
    struct stud* next;
}Student;

And here is my function where I merge them:

/*Merge Lists into one*/
Student* MergeLists(Node* headDS, Node* headJava, Student* head)
{
    bool flag = false;

    Student *a = new Student;
    Student *prev = NULL;
    Student *temp = NULL;
    Node *tempDS = headDS;
    Node *tempJava = headJava;
    Node *prevJava = NULL;

    if (head == NULL)
    {
        head = a; //mermory alocation for head<Student>
        temp = head;
    //  temp->next = NULL;
    }
    while (tempDS != NULL)
    {

        if(head != NULL)
        {

            if (tempDS->element.surname.compare(tempJava->element.surname) == 0) // if surnames are equal
            {
                prev = temp;

                temp->name = tempDS->element.name;
                temp->surname = tempDS->element.surname;
                temp->am = tempDS->element.am;
                temp->grade = tempDS->element.grade;
                temp->grade2 = tempJava->element.grade;

                tempJava = tempJava->next;
                tempDS = tempDS->next;
                temp = temp->next;
                flag = false; //meaning that prevJava can get a new value again.
            }
            else  // if DS > Java
            {
                /*Keep tempJava in mermory while iterating through the next nodes to find the temp that is equal to DS*/
                if (flag == false)
                {
                    prevJava = tempJava;
                    tempJava = tempJava->next;
                    flag = true;
                }
                else
                {
                    tempJava = tempJava->next;
                }

            }

            /*temp = temp->next;
            tempJava = tempJava->next;
            tempDS = tempDS->next;*/
        }
        prev->next = a;
    }
    a->next = NULL;

    return a;
}

The problem is on temp = temp->next line. Although the first run is perfectly fine and then correctly searches for the ListJava to find an equal name to ListDS temp value is 0xcdcdcdcd {...} and it throws me an exception:

Exception thrown at 0x00C38EF0 in Exercise3_zitima2.exe: 0xC0000005: Access violation reading location 0xCDCDCDE5.

How can i counter this error, I have really searched around tried things here and there but nothing seems to work out. I know this isn't a place to ask for someone to solve my assignment of course, just need a tad guidance.

Just a note, although it works you do not have to do `typedef struct student{ }StudentFile;` instead you can do `struct StudentFile{ };` - it's clearer and works pretty much the same. There's more about it in [this post](http://stackoverflow.com/a/612350/887210). — , Nov 12 '15 at 02:12

score 3 · Answer 1 · answered Nov 12 '15 at 02:05

3

Your Student struct doesn't have a constructor, so when you allocate one and assign it to a in MergeLists, a->next will have garbage in it. (The 0xCDCDCDCD is what MSVC fills allocated memory with so you can see these sorts of uninitialized usage.)

You either need to have a constructor set the next pointer to NULL or manually set it to NULL after you allocate it.

answered Nov 12 '15 at 02:05

1201ProgramAlarm

32,384
7
42
56

Nice thing to know about 0xCDCDCDCD. So in the Student struct, like this? : Student() { next = NULL; } – NickCh Nov 12 '15 at 02:26
@NickCh Even better, use constructor initialization list: `Student(): next(nullptr){}` – vsoftco Nov 12 '15 at 02:27
*sigh* I tried it still nothing, anyway I will keep working on your suggestions guys and see what I can do – NickCh Nov 12 '15 at 02:31

rcgldr · Answer 2 · 2015-11-12T11:15:12.090

1

A merge list function is normally used to merge two already sorted lists. No allocation of nodes is involved. The first node from one list is compared to the first node of the other list. The smaller node is removed from it's list and appended to what is an initially empty list that will end up with the merged nodes. The only node members that are changed are the next pointers. The process is repeated until the end of one of the lists is reached, and then the next pointer of the last node added to the merged list is set to point to the first node of the remainder of the other list, and the merge is done.

edited Nov 12 '15 at 11:15

answered Nov 12 '15 at 07:14

rcgldr

27,407
3
36
61

I wanted to make the sort later after I have seen that the current algorithm works. Though i have changed it completely now, have them sorted first and then merge them. – NickCh Nov 13 '15 at 11:36

C++| Merge Linked Lists

2 Answers2