Question

新手，C++单链表插入数据出错，有注释

#include <iostream>
using namespace std;
//结点
class SLNode{
public:
int data;
SLNode *next;
SLNode(SLNode *nextNode = NULL){ next = nextNode; }
SLNode(const int &item, SLNode *nextNode = NULL){ data = item; next = nextNode; }
};

//单链表
class SLList{
private:
SLNode *head,*tail,*ptr;
int size;
public:
SLList(){ head = tail = ptr = new SLNode(); size = 0; }
SLList(int &item);
~SLList(){
while (!IsEmpty()){ptr = head->next; head->next = ptr->next; delete ptr;}delete head;
}
bool IsEmpty()const{ return head->next == NULL; }
void StartArrInsert(const int &item);

void OrderInsert(const int &item);
void display();
};

void SLList::StartArrInsert(const int &item)
{
if (IsEmpty()){
head->next = new SLNode(item, head->next);
tail = head->next;
}
else{
tail->next = new SLNode(item, NULL);
tail = tail->next;

}
size++;
}
//按由小到大顺序插入
void SLList::OrderInsert(const int &item)
{//小于链表第一个数时
if (item < head->next->data){ head->next = new SLNode(item, head->next); size++; }
else {
//以下三行出问题。是插入数字大于最后一个数和在中间插入时。

if (item > tail->data){ tail->next = new SLNode(item, tail->next); tail = tail->next; size++; }
else { if (item > ptr->next->data){ ptr = ptr->next; }
ptr->next = new SLNode(item, ptr->next);
}
}
}

void SLList::display()
{
ptr = head->next;
while (ptr->next != NULL){ cout << ptr->data; ptr = ptr->next; }
}

int main()
{
int a[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
SLList arr;
for (int i = 0; i <= 10; i++){ int k = a[i]; arr.StartArrInsert(k); }
int k;
cout << "please write the number to insert" << endl;
cin >> k;
arr.OrderInsert(k);
arr.display();
}

Answer 1

你的代码有4处错误：

1. 主函数中的a[10]只有10个元素，可是后面的for中却是i <= 10，导致最后一个结点的data可能是个很大的数，使你输入的数插不到最后面去。改成for (int i = 0; i < 10; i++)就可以了。
   

2. void SLList::display()

   {
       ptr = head->next;
       while (ptr->next != NULL){cout << ptr->data;ptr = ptr->next; }

   }这个函数逻辑有错，不会显示最后一个结点。改如下就可以了——        

   void SLList::display(){

        ptr = head->next;

        do{

           cout << ptr->data;

        }while((ptr = ptr->next)!= NULL); 

   }

   3.在任意插入的代码段

        else { if (item > ptr->next->data){ ptr = ptr->next; }
        ptr->next = new SLNode(item, ptr->next); 

      有严重问题：首先>号应该是<号。一是这个>号导致输入的数据只要大于第1个结点的data,就总是插在第1个结点后面；二是这段代码没有寻找item应当插入的合适位置，只作了个判断，是严重逻辑错误。改如下便可——

else{

    for(ptr=head->next;ptr->next;ptr=ptr->next)

        if(item < ptr->next->data){ 

            ptr->next = new SLNode(item, ptr->next);

            break;

        }

}

   4.插入最后的判断句if (item > tail->data)要改为if (item >= tail->data)，不然当输入与最后一个结点的data相等时则不会成功插入。

相信这样就可以了……

Answer 2

建链表时应加个头结点，这便于在表头插入数据，还有链表尾指向的地方好像有点问题，解决这两个问题后，就可用如下代码统一插入数据，而不需去讨论在什么地方插入。
void SLList::OrderInsert(const int &item){
tail=head->next;
while(tail && item>tail->data) tail=tail->next;
tail->next=new SLNode(item, tail->next);
size++;
}

追问

要求就是在原链表的由小到大顺序上，按序插入