CODEWITHSUNDEEP
c++singly-linked-list
NickCh
NickCh

Reputation: 55

C++| Merge Linked Lists

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.

Upvotes: 1

Views: 163

Answers (2)

rcgldr
rcgldr

Reputation: 28826

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.

Upvotes: 1

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32732

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.

Upvotes: 3

Related Questions