首页 > 代码库 > 链表节点类化
链表节点类化
用c++类将单向链表类化,保存后可以方便的进行数的排序,插入操作; 调试成功的!
#include using namespace std;
class ListNode//创造节点成分
{
public:
ListNode(int datavalue)//构造函数一
{ value=http://www.mamicode.com/datavalue; }
ListNode()//构造函数二
{ }
int value;//节点的值
ListNode *previous;//上一个节点的指针
ListNode *next;//下一个节点的指针
ListNode operator=(const ListNode *LN)//定义此类的等号重载
{
value=http://www.mamicode.com/LN->value;
previous=LN->previous;
next=LN->next;
}
};
class List//创造链表,使用ListNode节点
{
public:
List()//构造函数初始化对象
{
head=NULL;
tail=NULL;//将头部和尾部的指针指向空
listcount=0;//将节点的数量初始化为零
current=NULL;//现在操作的节点位置,初始化为空
}
int listcount;//定义节点个数的记录变量
ListNode *head;//定义头指针
ListNode *tail;//定义尾指针
ListNode *current;//定义现在操作的指针
void MoveHead();//移动到头部
void MoveTail();//移动到尾部;
void MoveNext();//移动到下一个;
void MoveFore();//向上一个移动一个位置
void Append(int);//在整个链表后面添加新数据
void Insert(int);//在正在操作的数据的前面添加新数据
bool IsNull();//判断链表是否为空
bool IsBof();//判断当前操作的current指针是否在头部
bool IsEof();//判断当前操作的current指针是否在尾部
int GetCurrent();//得到当前操作指针current指向的value的值
void InsertAscend(int);//按照升序方式插入
void InsertDescend(int);//降序插入
void PrintAll();//从头到尾输出所有数据到屏幕
};
//下面是所有函数的具体内容
void List::MoveHead()
{
current=head;//令current指针指向头指针
}
void List::MoveTail()
{
current=tail;//令current指针指向尾指针
}
void List::MoveFore()//向上一个移动一个位置
{
if(!IsBof())//判断是否此时指针在头部,如果在就不移动,不在向上移动
{
current=current->previous;
}
}
void List::MoveNext()//向下一个移动一个位置
{
if(!IsEof())//判断是否此时指针在尾部,如果不在才可向后移动
{ current=current->next; }
}
void List::Append(int datavalue)//在整个链表的最后添加数据
{
ListNode *newnode=new ListNode;//开辟新节点
newnode->value=http://www.mamicode.com/datavalue;//将参数付给新节点
if(IsNull())//判断此链表是否为空,若为空就直接加上这个数据
{
head=newnode;//头指针指向新节点
tail=newnode;//尾指针也指向新节点
tail->next=NULL;//尾指针指向空
head->previous=NULL;//头指针的保存上一个节点的应指向空
current=tail;//现在操作的指针的指向新加的数据
listcount++;//新增一个数
}
else//如果不为空,就在尾部添加
{
tail->next=newnode;//在尾部添加,直接使尾指针指向新节点
newnode->previous=tail;//不要忘记将新节点的指向前一个节点的指针赋值
tail=newnode;//时尾指针后移 tail->next=NULL; current=tail; listcount++;
}
}
void List::Insert(int datavalue)//注意是在当前操作的值前加新节点
{
ListNode *newnode=new ListNode;
newnode->value=http://www.mamicode.com/datavalue;
if(IsNull())//此处同上
{
head=newnode;
tail=newnode;
tail->next=NULL;
head->previous=NULL;
current=head; listcount++;
}
else if(IsBof())//判断当前操作指针current是否为在头指针位置
{ newnode->next=head;//让新节点指向头节点
head->previous=newnode;
newnode->previous=NULL;
head=newnode;
current=head;//更新操作节点的指针值
}
else //在当前操作指针current前加新节点
{
newnode->next=current;
current->previous->next=newnode;
newnode->previous=current->previous;
current->previous=newnode;
current=newnode;
listcount++;
}
}
bool List::IsNull()//判断是否为空的函数
{
if(listcount==0)
return true;
return false;
}
bool List::IsBof()//判断是否为头指针
{
if(current==head)
return true;
return false;
}
bool List::IsEof()//判断是否为尾指针
{
if(current==tail)
return true;
return false;
}
int List::GetCurrent()//获取当前操作值的值
{ return current->value; }
void List::InsertAscend(int datavalue)//按照升序插入新数据
{
ListNode *newnode=new ListNode;
newnode->value=http://www.mamicode.com/datavalue;
if(IsNull())
{
head=newnode;
tail=newnode;
tail->next=NULL;
head->previous=NULL;
current=head;
listcount++;
}
else if(head->value>datavalue)//判断头指针是否大于新节点值,如果大于,则就可以将新节点直接插在头部前面
{
MoveHead();//将指针移向头部
Insert(datavalue);//使用了上面的插入函数
}
else if(tail->value<datavalue)//判断头指针是否大于新节点值,如果大于,则就可以将新节点直接插在头部前面
{ MoveTail();
Append(datavalue);
}
else if(GetCurrent()>datavalue)//如果当前操作值大于新节点值
{
while(GetCurrent()>datavalue)
{ MoveFore();//向上走一个指针
}
MoveNext();//因为此时指针指向的值小于新节点,这也是上面循环跳出的原因,所以应该再将指针后移一个位置
Insert(datavalue);
}
else
{
while(GetCurrent()<=datavalue)//如果此时current指针指向的值小于新节点值
{ MoveNext();//就向后移动一个指针,直到找到第一个比它大的值
}
Insert(datavalue);//在找到的第一个比他大的值前面插入
}
}
void List::InsertDescend(int datavalue)//按照降序插入,分析类似于上面升序插入
{ ListNode *newnode=new ListNode;
newnode->value=http://www.mamicode.com/datavalue;
if(IsNull())
{ head=newnode;
tail=newnode;
tail->next=NULL;
head->previous=NULL;
current=head;
listcount++;
}
else if(tail->value>datavalue)
{
MoveTail();
Append(datavalue);
}
else if(head->value<datavalue)
{ MoveHead();
Insert(datavalue); }
else if(GetCurrent()>datavalue)
{ while(GetCurrent()>datavalue)
{ MoveNext(); }
Insert(datavalue);
}
else { while(GetCurrent()<=datavalue)
{ MoveFore(); }
MoveNext();//降序插入和升序插入在这个位置 是否需要回走一个指针有差别,细心分析
Insert(datavalue);
}
}
void List::PrintAll()//打印所有数据
{ MoveHead();
int i=0;
while(current!=NULL)
{ if(i>7)
{
i=0;
cout<<endl;
}
if(i>0)
cout<<" ";
cout<<(current->value);
current=current->next;
i++; }
}
//一个使用这个l类函数的例子
int main()
{
//freopen("classdata.txt","r",stdin);
List Num;
int i,n;
cin>>n;
for(i=0;i<n;i++)
{
int t;
cin>>t;
Num.InsertDescend(t);
}
Num.PrintAll();
return 0;
}