c++ - 将未排序的链表转换为已排序的链表？ (C++)

Question

我在尝试将 INSERT 函数转换为按字母顺序对节点排序的函数时遇到问题。我已经写下了到目前为止我尝试过的内容……但它只检查第一个节点的名称，看它是否大于函数参数中新节点的给定名称。有人可以告诉我如何通过每个节点移动并能够比较它们的键(名称)并相应地将它们左右放置吗？下面是我的代码和我的 INSERT 函数到目前为止......

  // UnSortedLnkList.h
    //----------------------------

    #include <iostream>
    #include <afxwin.h>

    using namespace std;

    #define new DEBUG_NEW

    struct Node  {
        string m_name;  // key
        int m_age;

        Node* m_next;
        Node(const string& name, int age, Node* next = NULL);
    };

    ostream& operator<< (ostream&, const Node&);

    class ULnkList  {
        friend ostream& operator<< (ostream&, const ULnkList&); // 1.5
    public:
        ULnkList();
        // copy ctor
        ULnkList(const ULnkList& existingList );            // 5
        ~ULnkList();                                        // 4

        bool IsEmpty() const;
        int Size() const;
        bool Insert(const string& name, int age);           // 1
        bool Delete(const string& name);                    // 3
        bool Lookup(const string& name, int& age) const;    // 2

        ULnkList& operator =(const ULnkList& list2);        // 6

        bool Delete2(const string& name);   


    private:

        Node* m_head;   // points to head of the list
        int m_num;     // the number of entries in the list

        // helper functions:
        void Clear();                                       // 7
        void Copy(const ULnkList& list2);                   // 8
    };


    // UnSortedLnkList.cpp
    //----------------------------
    #include "UnSortedLnkList.h"
    #include <iostream>
    #include <string>
    using namespace std;

    Node::Node(const string& name, int age, Node* next)
    : m_name(name), m_age(age), m_next(next)
    {}


    ostream& operator<< (ostream& os, const Node& n)    // cout << n;
    {
        os << "Name: " << n.m_name << "\tAge: " << n.m_age;
        return os;
    }

    ULnkList::ULnkList()
    : m_head(new Node("",-99,NULL)), m_num(0)
    {
        //m_head = new Node("",-99,NULL);
    }
    //
    ULnkList::ULnkList(const ULnkList& existingList ) 
    {
        Copy(existingList);
    }

    void ULnkList::Copy(const ULnkList& existingList)
    {
        m_num = existingList.m_num;
        // create dummy node
        m_head = new Node("",-99,NULL);
        // traverse existing list
        Node *pe = existingList.m_head->m_next;
        Node *pThis = m_head;
        while( pe != 0)
        {
            // create a copy of the Node in OUR list
            pThis->m_next  = new Node(pe->m_name,pe->m_age,0);

            // update pointers
            pe = pe->m_next;
            pThis = pThis->m_next;
        }
    }

    void ULnkList::Clear()
    {
        Node *p = m_head->m_next;
        Node *tp = m_head;          // trail pointer
        while( p != 0)
        {
            delete tp;

            // update pointers
            tp = p;  // 
            p = p->m_next;
        }

        delete tp;
    }

    ULnkList& ULnkList::operator =(const ULnkList& list2)  // list1 = list2;
    {
        // list1 = list1;  // check for self-assignment
        if( this != &list2 )
        {
            this->Clear(); // normally Clear();
            this->Copy(list2);
        }

        // l1 = l2 = l3;

        return *this;
    }

    bool ULnkList::IsEmpty() const
    {
        return m_num == 0;
        // return m_head->m_next == NULL;
    }

    int ULnkList::Size() const
    {

        return m_num;
    }
    //

    ULnkList::Insert(const string& name, int age)
    {
        Node *current = m_head->m_next;
        Node *previous = m_head;
        if (m_head->m_next == NULL) 
        {
            m_head->m_next   = new Node(name,age,m_head->m_next); 
            m_num++;
            return true;
        }
        if (name < m_head->m_next->m_name)
        {
            m_head->m_next = new Node(name,age,m_head->m_next);
            m_num++;
            return true;
        }




        return true;
    }

    //
    ostream& operator<< (ostream& os, const ULnkList& list) // cout << list;
    {
        Node *p = list.m_head->m_next; // first node with data

        while( p != 0 )
        {
            cout << *p << endl;  // ????

            // update p
            p = p->m_next;
        }
        cout << "--------------------------------------" << endl;

        return os;
    }

    //   input: name
    //// output: age if found
    bool ULnkList::Lookup(const string& name, int& age) const
    {
        // linear search
        Node *p = m_head->m_next;

        while( p != 0)
        {
            if( name == p->m_name )
            {
                // found it
                age = p->m_age;
                return true;
            }

            // update p
            p = p->m_next;
        }
        return false;
    }
    //
    bool ULnkList::Delete(const string& name)
    {
        Node *p = m_head->m_next;
        Node *tp = m_head;          // trail pointer
        while( p != 0)
        {
            if( name == p->m_name )
            {
                // found it, so now remove it
                // fix links
                tp->m_next = p->m_next;
                // delete the node
                delete p;

                return true;
            }

            // update pointers
            tp = p;  // tp = tp->m_next;
            p = p->m_next;
        }
        return false;
    }

    bool ULnkList::Delete2(const string& name)
    {
        Node *p = m_head;
        while( p->m_next != 0 )     // ?????
        {
            if( p->m_next->m_name == name )
            {
                Node *save = p->m_next;
                // remove the node
                // fix links
                p->m_next = p->m_next->m_next;
                // delete memory
                delete save;
                return true;
            }

            // update pointers
            p = p->m_next;
        }
        return false;
    }
    //
    ULnkList::~ULnkList()
    {
        Clear();
    }
    //

Answer 1

我对这段代码有一个警告

if(name > m_head->m_name ){
while(name > current->m_next->m_name){
    current = current->m_next;
}
// add temp = current->next
current->m_next = new Node(name,age)
// current->next->next = temp

您不希望在插入位置后丢失列表。