C++ 中的排序链表不会插入

Question

我正试图为排序链表创建一个类，该类继承自未排序链表的类，并覆盖insert函数，但程序没有将我给它的值插入到列表中，我不知道为什么。

这是我的插入函数：

class SLList : public LList<Elem>
{
public:
    SLList(){LList::LList();}
    ~SLList(){}
    bool insert(const Elem& item)
    {
            Elem curr;
            for(setStart();getValue(curr);next())
            {
                if(!IntComparision::lt(curr, item)) break;
                return LList<Elem>::insert(item);
            }
    }
};

这是我的其余代码：

// Singly-linked list node
template <class Elem> 
class Link
{
public:
    Elem element;      // Value for this node
    Link *next;        // Pointer to next node in list
    Link( const Elem& elemval , Link* nextval= NULL ) // 1st Constructor
    { element= elemval ;  next= nextval; }
    Link( Link* nextval= NULL ) // 2nd Constructor
    { next= nextval; }
};

template <class Elem>
class List
{
public:
virtual void clear()= 0;
virtual bool insert(const Elem&)= 0;
virtual bool append(const Elem&)= 0;
virtual bool remove(Elem&)= 0;
virtual void setStart()= 0;
virtual void setEnd()= 0;
virtual void prev()= 0;
virtual void next()= 0;
virtual int leftLength() const= 0;
virtual int rightLength() const= 0;
virtual bool setPos(int pos)= 0;
virtual bool getValue(Elem&) const= 0;
virtual void print() const= 0;
};
class IntComparision
{
public:
    static bool eq( int a , int b )
    { return a==b; }
    static bool lt( int a , int b )
    { return a<b; }
    static bool gt( int a , int b )
    { return a>b; }
};
const int DefaultListSize=10;
// Singly Linked list implementation
template <class Elem> 
class LList: public List<Elem>
{
private:
    Link<Elem>* head;       // Pointer to list header
    Link<Elem>* tail;       // Pointer to last Elem in list 
    Link<Elem>* fence;      // Last element on left side
    int leftcnt;            // Size of left partition
    int rightcnt;           // Size of right partition
    void init() // Intialization routine
    {
        fence= tail= head= new Link<Elem>;
        leftcnt= rightcnt= 0;
    }
    void removeall() // Return link nodes to free store
    {
        while( head != NULL )
        {
            fence= head;
            head= head->next;
            delete fence;
        }
    }
public:
    LList(  ) // Constructor
    { init(); }
    ~LList() { removeall(); }  // Destructor
    void clear()
    { removeall() ; init(); }
    bool insert( const Elem& );
    bool append( const Elem& );
    bool remove( Elem& );
    void setStart()
    { fence= head ; rightcnt+= leftcnt ; leftcnt= 0; }
    void setEnd()
    { fence= tail ; leftcnt+= rightcnt ; rightcnt= 0; }
    void prev();
    void next()
    {
        if ( fence != tail ) // Don't move fence if right empty
      { fence= fence->next ; rightcnt-- ; leftcnt++ ; }
    }
    int leftLength() const  { return leftcnt; }
    int rightLength() const { return rightcnt; }
    bool setPos( int pos );
    bool getValue( Elem& it ) const
    {
        if( rightLength() == 0 ) return false;
        it= fence->next->element;
        return true;
    }
    void print() const;
};
template <class Elem> // Insert at front of right partition
bool LList<Elem>::insert( const Elem& item )
{
    fence->next= new Link<Elem>( item , fence->next ); 
    if ( tail == fence )
        tail= fence->next;  // New tail
    rightcnt++;
    return true;
}
template <class Elem> // Append Elem to end of the list
bool LList<Elem>::append( const Elem& item )
{
    tail= tail->next= new Link<Elem>( item , NULL );
    rightcnt++;
    return true;
}
// Remove and return first Elem in right partition
template <class Elem> bool LList<Elem>::remove( Elem& it )
{
    if ( fence->next == NULL ) return false; // Empty right
    it= fence->next->element;       // Remember value
    Link<Elem>* ltemp= fence->next; // Remember link node
    fence->next= ltemp->next;       // Remove from list
    if ( tail == ltemp )
        tail = fence; // Reset tail
    delete ltemp;                    // Reclaim space
    rightcnt--;
    return true;
}
// Move fence one step left; no change if left is empty
template <class Elem> void LList<Elem>::prev()
{
    Link<Elem>* temp= head;
    if ( fence == head )
      return; // No previous Elem
    while ( temp->next != fence )
        temp= temp->next;
    fence = temp;
    leftcnt--;
    rightcnt++;
}
// Set the size of left partition to pos
template <class Elem>
bool LList<Elem>::setPos( int pos )
{
    if (  (pos < 0) || ( pos > rightcnt+leftcnt )  )
        return false;
    fence= head;
    for( int i=0 ; i<pos ; i++ )
        fence= fence->next;
    return true;
}
template <class Elem> void LList<Elem>::print() const
{
    Link<Elem>* temp= head;
    cout << "< ";
    while ( temp != fence )
    {
        cout << temp->next->element << " ";
        temp= temp->next;
    }
    cout << "| ";
    while ( temp->next != NULL )
    {
        cout << temp->next->element << " ";
        temp= temp->next;
    }
    cout << ">n";
}
template <class Elem>
class SLList : public LList<Elem>
{
public:
    SLList(){LList::LList();}
    ~SLList(){}
    bool insert(const Elem& item)
    {
        Elem curr;
        for(setStart();getValue(curr);next())
        {
            if(!IntComparision::lt(curr, item)) break;
                return LList<Elem>::insert(item);
        }
    }
};

提前谢谢。

Answer 1

在插入循环中似乎有一个不必要的break：

 for(setStart();getValue(curr);next())
 {
     if(!IntComparision::lt(curr, item)) break;  //What?
        return LList<Elem>::insert(item);
 }

这样做的目的是，如果第一个项目大于要插入的项目，您最终将不会插入任何内容。如果没有，则应将该项插入到列表头（假设插入代码有效）。

根据压痕，我认为你实际上想做：

 for(setStart();getValue(curr);next())
 {
     if(!IntComparision::lt(curr, item)) 
     {
         return LList<Elem>::insert(item);
     }
 }

您可以省略if语句中的{ }，但如果您包含它们，它会更明确，也不容易出错。