首页 > 代码库 > 链表节点类化

链表节点类化

 

用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;

}