Question

单链表输入输出，删除与插入问题，为什么最后运行后老是不对呢，到底是哪里出问题了，求神人帮忙

class List;
class ListNode
{ friend class List;
private:
int data; //数据元素域
ListNode *link; //域指针域
public:
ListNode(const int item,ListNode *p=NULL)
{
data=item;
link=p;
}
};
class List
{public:
List();
virtual ~List();
int Getlength();
int Find(int x);
int Insert (const int x,const int i);
int Remove(int i);
void input();
void output();
private:
ListNode*first,*last; //表头和表尾指针
};
下面是.cpp文件里面的
void List::input()
{
int n,count=1;
ListNode *newnode=new ListNode(1,NULL) ;
ListNode *p=first;
p->link=newnode;
cout<<"请输入要建立的单链表的总结点数：";
cin>>n; //n表示链表结点的个数
if (n>=count)
{
while (1)
{
cin>>p->data;
if (count==n)
break;
count++;
p->link=newnode;
p=p->link;
}
p->link=NULL; }
}
void List::output()
{
ListNode *p=first;
while (1)
{
cout<<p->data<<endl;
if(p->link==NULL)
break;
p=p->link;
}
}
int List::Getlength()
{
//遍历
ListNode *p=first;
int c=1; //c表示结点的个数
while (1)
{
p=p->link; //使p从第一个结点指向下一个结点
c++;
if (p->link==NULL)
break;
}
return c;
}
int List::Find(int x)
{
//搜索x
ListNode *p =first;
int i=1;
while (p!=NULL&&p->data!=x)
{
p=p->link;
i++;
}
return i;

}
int List::Insert(const int x,const int i)
{
//在链表第i个结点处插入新元素x
ListNode *n =first;
int k=0;
while (n!=NULL&&k<i-1)
{
n=n->link;
k++;
} //找到第i-1个结点
if(n==NULL&&first!=NULL)
{
cout<<"无效的插入位置"<<endl;
return 0;

}
ListNode *newnode=new ListNode(x,NULL) ; //创建新结点，其数据为x，指针为0
if(first ==NULL||i ==0)
{
//插在表前
newnode->link=first;
if (first==NULL)
{
last=newnode;
}
first=newnode;
}
else
{
//插在表中或表尾
newnode->link=n->link;
if (n->link==NULL)
{
last=newnode; //在链表尾插入

}
n->link=newnode;
}
return 1;
}
int List::Remove(int i)
{
//在链表中删除等i个结点
ListNode *p=first,*q;
int k=0;
while(p!=NULL&&k<i-1)
{
p=p->link;
k++; //找第i-1个结点
if (p==NULL||p->link==NULL)
{
cout<<"无效的删除位置！"<<endl;
return 0;
}
if (i==0)
{
//删除表中第1个结点
q=first; //q保存被删结点地址
p=first=first->link; //修改first
}
else
{
//删除表中或表尾元素
q=p->link;
p->link=p->link;
}
if (q==last)
{
last=p; //可能修改last
}
k=q->data;
delete q;
return 1;
}
}
void main()
{
List l;
l.input();
int length=l.Getlength();
cout<<"单链表的长度为"<<length<<endl;
int location=l.Find(3);
cout<<"3元素在单链表的第"<<location<<"个位置"<<endl;
l.Insert(4,2);
cout<<"在第二个位置加入4后单链表变为:"<<endl;
l.output();
l.Remove(4);
cout<<"删除第4个结点之后单链表变为:"<<endl;
l.output();
}

Answer 1

#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
class List;
class ListNode
{ friend class List;
private:
int data; //数据元素域
ListNode *link; //域指针域
public:
ListNode(const int item,ListNode *p = NULL)
{
data=item;
link=p;
}
};
class List
{public:
List()
{
first = last = new ListNode(-1,NULL);//<-------------修改,创建链表时创建了头结点
first->link = NULL;
}
//virtual ~List();
int Getlength();
int Find(int x);
int Insert (const int x,const int i);
void Remove(int i);
void input();
void output();
private:
ListNode *first,*last; //表头和表尾指针
};
void List::input()
{
int n,i;
cout<<"请输入要建立的单链表的总结点数：";//<-------------修改,重写了input函数
cin>>n; //n表示链表结点的个数
ListNode *p;
for(i = 0;i < n;i++)
{
p = new ListNode(1,NULL) ;
cin >> p->data;
p->link = NULL;
last->link = p;
last = p;
}
//int n,count=1;
// ListNode *newnode=new ListNode(1,NULL) ;
//ListNode *p=first;
//p->link=newnode;
//cout<<"请输入要建立的单链表的总结点数：";
//cin>>n; //n表示链表结点的个数
//if (n>=count)
//{
// while (1)
// {
// cin>>p->data;
// if (count==n)
// break;
// count++;
// p->link=newnode;
// p=p->link;
// }
// p->link=NULL;
//}
}
void List::output()
{
ListNode *p=first;
while (1)
{
cout<<p->data<<endl;
if(p->link==NULL)
break;
p=p->link;
}
}
int List::Getlength()
{
//遍历
ListNode *p=first;
int c=1; //c表示结点的个数
while (1)
{
p=p->link; //使p从第一个结点指向下一个结点
c++;
if (p->link==NULL)
break;
}
return c;
}
int List::Find(int x)
{
//搜索x
ListNode *p =first;
int i=1;
while (p!=NULL&&p->data!=x)
{
p=p->link;
i++;
}
return i;

}
int List::Insert(const int x,const int i)
{
//在链表第i个结点处插入新元素x
ListNode *n =first;
int k=0;
while (n!=NULL&&k<i-1)
{
n=n->link;
k++;
} //找到第i-1个结点
if(n==NULL&&first!=NULL)
{
cout<<"无效的插入位置"<<endl;
return 0;

}
ListNode *newnode=new ListNode(x,NULL) ; //创建新结点，其数据为x，指针为0
if(first ==NULL||i ==0)
{
//插在表前
newnode->link=first;
if (first==NULL)
{
last=newnode;
}
first=newnode;
}
else
{
//插在表中或表尾
newnode->link=n->link;
if (n->link==NULL)
{
last=newnode; //在链表尾插入

}
n->link=newnode;
}
return 1;
}
void List::Remove(int i)
{
ListNode *p = first,*q;
int count = 1;
while(count != i&&p->link != NULL)//<-------------修改,重写了Remove函数
{
count++;
p = p->link;
}
if(p->link != NULL)
{
q = p->link;
p->link = p->link->link;
free(q);
}
if(p->link == NULL)
{
last = p;
}
////在链表中删除等i个结点
//ListNode *p=first,*q;
//int k=0;
//while(p!=NULL&&k<i-1)
//{
// p=p->link;
// k++; //找第i-1个结点
// if (p==NULL||p->link==NULL)
// {
// cout<<"无效的删除位置！"<<endl;
// return 0;
// }
// if (i==0)
// {
// //删除表中第1个结点
// q=first; //q保存被删结点地址
// p=first=first->link; //修改first
// }
// else
// {
// //删除表中或表尾元素
// q=p->link;
// p->link=p->link;
// }
// if (q==last)
// {
// last=p; //可能修改last
// }
// k=q->data;
// delete q;
// return 1;
//}
}
void main()
{
List l;
l.input();
int length=l.Getlength();
cout<<"单链表的长度为"<<length<<endl;
int location=l.Find(3);
cout<<"3元素在单链表的第"<<location<<"个位置"<<endl;
l.Insert(4,2);
cout<<"在第二个位置加入4后单链表变为:"<<endl;
l.output();
l.Remove(4);
cout<<"删除第4个结点之后单链表变为:"<<endl;
l.output();
system("pause");
}
/*输入
4
1
2
3
4
得到的结果是正确的
由于加入了头结点
原有的一些函数需要修改，如output，find等函数，我没改，就修改了input()和Remove()
*/