Возникли проблемы с вставкой узлов в порядке - PullRequest
Новая
       71

Возникли проблемы с вставкой узлов в порядке

0 голосов
/ 03 июля 2019

У меня есть связанный список, в который я должен вставить объекты, основываясь на одном из полей объекта, я должен вставить узлы в связанный список в правильном порядке.

У меня отлично работала сортировка при использовании массивов и векторов, но у меня возникли проблемы просто с аспектом вставки связанного списка. мой вызов getLink () предназначен для функции, которая получает мою ссылку, которая = next. 

void sortedInsert(DomNodePtr& head, string fName, string lName, float CGPA, int rScore,string prov){
     DomNodePtr here = head;
     DomNodePtr tempPtr;
     tempPtr = new DomNode(fName, lName, CGPA, rScore, prov, head);

     while (here->getCumGPA() > CGPA && here->getLink() != NULL){
     here = here->getLink();

     }
     if (here->getCumGPA() < CGPA){
         tempPtr->setLink(here->getLink());
         here->setLink(tempPtr);
     }
     else if (here->getCumGPA() > CGPA){
         here = tempPtr;
     }
}

По сути, я хочу, чтобы студенты с наивысшим совокупным средним баллом были отсортированы выше, чем учащиеся с более низким CGPA. Я знаю, что часть моей проблемы заключается в том, что я не включаю студентов с более низким CGPA, но я борюсь с этой частью. Он также выводит около 10 студентов, когда я печатаю связанный список, хотя на самом деле их около 100, и они не в правильном порядке.

1 Ответ

1 голос
/ 03 июля 2019

При добавлении нового ученика в список есть три случая:

  • CGPA для нового элемента меньше, чем значения CPGA всех элементов в списке. В этом случае студент должен быть прикреплен к концу списка.
  • У студента CPGA больше, чем у всех элементов списка: новый элемент должен быть добавлен в начало списка

  • Студент имеет CPGA между двумя существующими элементами. Здесь новый элемент должен быть вставлен между этими элементами. Поэтому вы должны отслеживать предыдущий элемент, у которого CPGA больше, чем CPGA нового элемента. 

    void sortedInsert(DomNodePtr& head, string fName, string lName, float CGPA, int rScore,string prov){
    DomNodePtr here = head;
    DomNodePtr tempPtr;
    tempPtr = new DomNode(fName, lName, CGPA, rScore, prov, head);

    DomNodePtr previous = NULL; // keeping track of the previous element

    while (here->getCumGPA() >= CGPA && here->getLink() != NULL){
        previous = here;
        here = here->getLink();
    }
    if (here->getLink() == NULL){
        // Insert new student at the end of the list
        // If CPGA is larger for all students in the list

        here->setLink(tempPtr);
    }
    else if (previous = NULL) {
        // The new student has the highest CGPA and
        // has to be added at the head of the list
        tempPtr->setLink(here);
    }
    else{
        // Insert the student between the current
        // and the previous elements of the list

        previous->setLink(tempPtr);
        tempPtr->setLink(here);
    }
}
...