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();
    }
    //

score 1 · Accepted Answer

我对这段代码有一点警告

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

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

score 0 · Accepted Answer

我猜这是作业，所以我不打算编写代码。我建议您的 Insert() 函数可以通过比较输入字符串，然后执行插入逻辑，从头部遍历列表，直到它到达“正确”位置。那是假设您必须使用文字列表作为数据结构。如果您想要更好的平均插入性能，您可以使用二叉树作为您的底层结构，但这会使列表遍历更加复杂。

score 0 · Accepted Answer

你的问题在于这段代码：

    if (name < m_head->m_next->m_name)
    {
        m_head->m_next = new Node(name,age,m_head->m_next);
        m_num++;
        return true;
    }

为了以排序方式插入，我可能会使用某种带有递归函数调用的辅助函数。

但这可能有效：

Node *current = m_head;
if(name > m_head->m_name ){
    while(name > current->m_next->m_name){
        current = current->m_next;
    }
    current->m_next = new Node(name,age,current->m_next);
}
else{
    m_head = new Node(name,age,m_head);
}

这将以升序方式插入。我还没有测试它，但让我知道它是否有效！希望这可以帮助！

c++ - 将未排序的链接列表变成已排序的链接列表？(C++)

3 回答 3

Related

Reference