第16讲快慢排序课后作业

呆呆打Dota

#include<iostream>
#include<time.h>
#include<cstdlib>
using namespace std;

//结点类的实现及定义

class ListNode
{
        int data;
        ListNode *Next;
public:
        ListNode():Next(NULL){}
        ListNode(int Value):Next(NULL),data(Value){}
        ~ListNode(){};
        void SetNext(ListNode *next);
        ListNode *GetNext();
        int GetData();       
};

void ListNode::SetNext(ListNode *next)
{
        Next=next;
}

ListNode* ListNode::GetNext()
{
        return Next;
}

int ListNode::GetData()
{
        return data;
}

//链表类的实现及定义

class List
{
        ListNode *head;
        ListNode *tail;
public:
        List();
        ~List(){};
        int GetCount();
        void AddTail(int Value);
        ListNode *GetHead();
        void OutPut();
        void GetMidNode();
};

List::List()
{
        head=tail=new ListNode;
        tail->SetNext(NULL);
}

int List::GetCount()
{
        int count=0;
        ListNode *p=new ListNode;
        p=head->GetNext();
        while(p!=NULL)
        {
                ++count;
                p=p->GetNext();
        }
        return count;
}

void List::AddTail(int Value)
{
        ListNode *add=new ListNode(Value);
        tail->SetNext(add);
        tail=tail->GetNext();
        tail->SetNext(NULL);
}

ListNode* List::GetHead()
{
        return head;
}

void List::OutPut()
{
        ListNode *p=new ListNode;
        p=head->GetNext();
        while(p!=NULL)
        {
                cout<<p->GetData()<<" ";
                p=p->GetNext();
        }
        cout<<endl;
}

void List::GetMidNode()
{
        ListNode *search,*mid;
        search=mid=head;
        while(search->GetNext()!=NULL)
        {
                if(search->GetNext()->GetNext()!=NULL)
                {
                        search=search->GetNext()->GetNext();
                        mid=mid->GetNext();
                }
                else
                {
                        search=search->GetNext();
                        mid=mid->GetNext();
                }
        }
        cout<<mid->GetData()<<endl;
}

int main()
{
        List A;
        srand(time(NULL));
        for(int i=0;i<20;i++)
        {
                A.AddTail(rand()%50);
        }
        A.OutPut();
        A.GetMidNode();
       
        system("pause");
        return 0;
}