Упорядоченная вставка связанного списка - если есть заявления - PullRequest
Новая
       29

Упорядоченная вставка связанного списка - если есть заявления

0 голосов
/ 08 декабря 2018

что меня смущает, так это часть кода: 

if (newitem >= first->info)//e.g., 25 > 3
             {
               newNode->link = first->link;
               first->link = newNode;
               first = newNode;
           }     

^^^^^^^^^^^^^^^^^^^^^^^^^

Я смущен, потому что мне интересно, когда вы создаете связанный список из вставки узлов, где «first» в конечном итоге указывает на?Указывает ли это на последний узел в связанном списке?

Также это объявляется: 

 template <class Type>
 struct nodeType
 {
     Type info;
     nodeType<Type> *link;
 };

И сначала объявляется как указатель в защищенной области моего класса как: 

 nodeType<Type> *first;

Почему сначала объявляется какузел вместо обычного указателя?Я думал, что это будет указывать на первый узел в связанном списке.

Это функция вставки, которую мой профессор дал в качестве демонстрации в рамках большой демонстрации шаблонного класса: 

void insertNode(const Type& newitem)
{
    nodeType<Type> *current; //pointer to traverse the list
    nodeType<Type> *trailCurrent; //pointer just before current
    nodeType<Type> *newNode;  //pointer to create a node

    bool  found;

    newNode = new nodeType<Type>; //create the node

    newNode->info = newitem;   //store newitem in the node
    newNode->link = NULL;      //set the link field of the node
    //to NULL

    if (first == NULL)  //Case 1    e.g., 3
    {
        first = newNode;
        first->link = newNode;
        count++;
    }
    else
    {
        if (newitem >= first->info)//e.g., 25 > 3
        {
            newNode->link = first->link;
            first->link = newNode;
            first = newNode;
        }
        else
        {
            trailCurrent = first; //e.g., 1 < 3
            current = first->link;
            found = false;

            while (current != first && !found)
                if (current->info >= newitem)
                    found = true;
                else
                {
                    trailCurrent = current;
                    current = current->link;
                }

            trailCurrent->link = newNode;
            newNode->link = current;
        }

        count++;
    }//end else
}

Связанный список создается только с помощью этой функции, ноЯ еще не понял эту функцию.Если кто-то может помочь объяснить это, это было бы чрезвычайно полезно.Спасибо.

...