C++从循环构建排序链接表

Question

我已经用头撞墙大约3个小时了，试图想出解决这个问题的办法，但我还是想不出来。我的测试程序就是这样写的。

int main()
{
  SimpList<int> intList;   // (empty) list of integers

  cout << "Let's build a sorted list of integers." << endl;
  cout << endl << "Uninitialized List: ";
  intList.print();
  cout << endl << "Length: " << intList.size() << endl;

  int intData[] = { 5, 3, -2, 7, 9, -8, 1, -4 };

  for (int i=0; i<8; i++)
    intList.insert( intData[i] );

  cout << endl << "After inserting 8 integers: ";
  intList.print();
  cout << endl << "Length: " << intList.size() << endl;

  system("PAUSE");
  return 0;
}

因此，链接列表是从一个数组和一个for循环初始化的。我的节点和列表的类代码在这里...

    template < typename T >   // Forward declaration of the SimpList class
class SimpList;

template < typename T >
class Node                 // Node class for the SimpList class
{
  private:
    // Constructors
    Node () { next = 0; }  // default constructor

    // Complete the definition inline
    Node ( const T &initItem, Node<T> *ptr ) { }

    // Data members
    T           item;   // Node data item
    Node        *next;  // Pointer to the next node

  friend class SimpList<T>;
};

template < typename T >
class SimpList
{
  public:

    // Constructor (add your code inline)
    SimpList ()
    {
      head = &PHONY;
      length = 0;
    }


    // List manipulation operations
    void insert ( const T &newitem );   // insert a data item
    bool remove ( T &item );            // remove data item
    bool find ( T &item ) const;        // find data item
    void clear ();                      // empty the list

    bool isEmpty () const { 
     if (length == 0)
         return true;
     else
         return false;
    }

    // length accessor method
    int size () const { 
        return length;
    }

    // print the list items
    void print () const;

  private: // data members
    Node<T> PHONY;      // empty node that anchors the list
    Node<T> *head;      // pointer to the beginning of the list
    int length;         // length of list
};

然后插入和打印函数如下所示...

template < typename T >
void SimpList<T>::print() const
{
  if (length == 0)
  {
    cout << "List is empty." << endl;
    return;
  }

  Node<T> *ptr = head->next;
  while (ptr != NULL)
  {
    cout << ptr->item << "  ";
    ptr = ptr->next;
  }
  cout << endl;
}

template < typename T >
void SimpList<T>::insert(const T& newitem) {

        Node<T> *currN = head->next;
        Node<T> *prevN = 0;
        Node<T> *tmp = new Node<T>();
        tmp->item = newitem;

        if(head->next == NULL ) {
          head->next = tmp;
        }
        else {
            prevN = head;
            while(currN != NULL && currN->item < newitem) {
                prevN = currN;
                currN = currN->next;
            }
            prevN->next = tmp;
        }
        length++;
        print();
}

我将最后一个"print()“插入到insert函数中，作为调试发生的事情的一种方式，输出结果非常令人困惑，因为它给了我

5 3 -2 -2 7-7 9 -8 -8 1 -8 -4

但我希望输出从小到大排序(-8 -4 -2 1 3 5 7 9)

编辑: solved...forget以更新currN旁边的tmp->。德尔普。

Answer 1

您需要解决的几个问题：

1. PHONY->next不为空，因此初始化将失败：

如果(head-> next == NULL ){ head->next=tmp；return；}

• 节点构造函数应该在0而不是this的旁边初始化，因此您永远不会遇到列表末尾的NULL条件。在insert is语句中，您应该从

• ->next开始搜索，当前您从currn = head开始搜索，这是不正确的。

• 您还需要适当地设置tmp->next，当您在列表中间插入时，请考虑这种情况。