为什么读入的单链表的内容会错位？

Question

#include<iostream>
using namespace std;
template<class T>
class listnode{
    public:
    listnode()
    {
        next=NULL;
    }
    listnode(T item,listnode<T>* next1=NULL)
    {
        data=item;
        next=next1;
    }
    T data;
    listnode<T> *next;
};

template<class T>
class list{
    public:
        list()
        {
            head=new listnode<T>;
            length=0;
        }
        list(T value,list<T>* next1)
        {
            data=value;
            next=next1;
        }
        bool Insert(T value,int i);
        int Findvalue(T value);
        listnode<T>* Findi(int i);
        bool Remove(int i);
        void display();
        T Display()
        {
            return data;
        }
        listnode<T>* Head()
        {
            return head;
        }
        int Length()
        {
            return length;
        }
    protected:
        listnode<T>* head;
        T data;
        listnode<T>* next;
        int length;
}; 

template<class T>
listnode<T>* list<T>::Findi(int i)
{
    if(i<0||i>length)
        return NULL;
    if (i==0)
    { 
        cout<<"Findi ok!"<<endl;
        return head;
    }
    int j=1;
    listnode<T>* p=head->next;
    if (j<i&&p!=NULL)
    {
        p=p->next;
        j++;
    }
    cout<<"Findi ok!"<<endl;
    return p;
}

template<class T>
bool list<T>::Insert(T value,int i)
{
    cout<<"Insert 1 ok!"<<endl;
    listnode<T>* p=Findi(i-1);
    if (p==NULL)
    {
        cout<<"so sad~"<<endl;
        return false;
    }
    listnode<T>* newp = new listnode<T>(value,p->next);
    if (newp==NULL)
        return false;
    p->next=newp;
    length++;
    cout<<"Insert ok!"<<endl;
    return true;
}

template<class T>
int list<T>::Findvalue(T value)
{
    listnode<T>* p=head->next;
    int i=1;
    while (i<length&&p->data!=value)
    {
        p=p->next;
        i++;
    }
    cout<<"Findvalue ok!"<<endl;
    return i;
}

template<class T>
bool list<T>::Remove(int i)
{
    listnode<T>* p=Findi(i-1),*q;
    if (p==NULL)
        return false;
    q=p->next;
    p->next=q->next;
    cout<<"q->data="<<q->data<<endl;
    delete q;
    length--;
    cout<<"Remove ok!"<<endl;
    return true;
}

template<class T>
void list<T>::display()
{
    listnode<T>* p=head->next;
    int i=1;
    while (i<=length)
    {
        cout<<p->data<<" ";
        i++;
        p=p->next;
    }
    cout<<"display ok!"<<endl;
    cout<<endl;
}

int main()
{
    list<int> list1;
    int num;
    int i=1,j=0;
    while (1)
    {
        cin>>num;
        list1.Insert(num,i);
        i++;
        if (cin.get()=='\n')
        {
            cout<<"break!"<<endl;
            break;
        }
    }
    list1.display();
    int num1;
    cin>>num1;
    j=list1.Findvalue(num1)-1;
    cout<<"j="<<j<<endl;
    list1.Remove(j);
    list1.display();
}

读入11 22 33 44 55 66以后，理想应该有11 22 33 44 55 66的返回，但是却返回了11 22 66 55 44 33。初步判断是Insert部分出错了，其他地方调试没有发现错误

Answer 1

你的Findi函数有bug
当i是0或者i是1，都能正确的返回位置
但是当i大于2之后，由于判断里有p不是空才执行next，导致p是空时返回的其实永远是第2项
而你每次insert的位置都是最后一个位置，是个空
因为每次都返回第二项，所以先插入的反而被挤到后面去，导致从第3项开始都是倒序的
其实你函数一开始已经判断了i是否越界，后面就别再判断p是不是空了