0

我已经把头撞在墙上大约 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（）”插入到插入函数中，作为调试正在发生的事情的一种方式，输出非常令人困惑，因为它给了我

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

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

编辑：已解决...忘记更新 tmp-> 在 currN 旁边。DERP。

4

1 回答 1

0

您需要解决的几件事：

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

    if(head->next==NULL) {
  head->next=tmp;
  return;
}

  2. 节点构造函数应该在 0 旁边初始化而不是this，因此您永远不会在列表末尾遇到 NULL 条件。

  3. 在插入 else 语句中，您应该从 head->next 开始搜索，目前您从currn=开始搜索，head这PHONY是不正确的。

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

于 2013-02-07T04:30:31.183 回答