PTA 7 - 7 싱글 체인 시트 생 성 및 옮 겨 다 니 기 (30 분)

40181 단어 데이터 구조
PTA 7 - 7 싱글 체인 시트 생 성 및 옮 겨 다 니 기 (30 분)
#include 
#include 
#include 
using namespace std;
typedef int T;
struct LinkNode //    
{
      T data;//   
      LinkNode* next;//  
      LinkNode(const T& item, LinkNode* ptr=NULL)
      {
            data=item;
            next=ptr;
      }
      LinkNode(LinkNode* ptr=NULL)
      {
            next=ptr;
      }
};
class List
{
private:
      LinkNode * first;
public:
      List()//    
      {
          first=NULL;
      }
      //List(const T& x);
//      List(int n,);
      List(const List& L)//      
      {
         first=NULL;
         CopyList(L);
      }
      List& operator=(const List& L)//       
      {
          if(this==&L)
            return *this;
      MakeEmpty();
      CopyList(L);
      return *this;
      }
      ~List()//    
      {
          MakeEmpty();
      }
      void InputFront(const T& elem)//   
      {
          LinkNode *L=new LinkNode(elem);
          L->next=first;
          first=L;
      }
      void InputRear(const T& elem)//   
      {
          LinkNode *L=new LinkNode(elem);
          LinkNode *p=first;
          while(p->next!=NULL)
          {
              p=p->next;
          }
          p->next=L;
      }
      void MakeEmpty()//    
      {
          while(first!=NULL)
          {
              LinkNode *p=first;
              first=first->next;
              delete p;
          }
      }
      int Length() const//         
      {
          int c=0;
          LinkNode *p=first;
          while(p!=NULL)
          {
              c++;
              p=p->next;
          }
          return c;
      }
      LinkNode* Search(const T& x)//        x,            ,     
      {
          LinkNode *p=first;
          while(p!=NULL)
          {
              if(p->data==x)
              {
                  break;
              }
              p=p->next;
          }
          return p;
      }
      LinkNode* Locate(int i)//      i      ,i         
      {
          LinkNode *p=first;
          int c=0;
          while(c<i-1)
          {
              if(p==NULL) break;
              p=p->next;
          }
          return p;
      }
      bool GetData(int i, T& x)//     i   ,     x
      {
          if(Locate(i)!=NULL)
          {
              x=Locate(i)->data;
              return true;
          }
          return false;
      }
      void CopyList(const List& L)
      {
          LinkNode *newNode,*iter,*rear;
          if(L.first==NULL)
            return;
      newNode=new LinkNode(L.first->data);
      first=newNode;
      iter=L.first->next;
      rear=newNode;
      while(iter)
      {
            newNode=new LinkNode(iter->data);
            rear->next=newNode;
            iter=iter->next;
            rear=rear->next;
      }
      }
      void SetData(int i, const T& x)//     i    x
      {
          if(Locate(i)!=NULL)
          {
              Locate(i)->data=x;
          }
      }
      bool Insert(int i, const T& x)//     i        x
      {
        LinkNode *pre;
        LinkNode *newNode;
        pre=first;
        if(i==1)
        {
            newNode=new LinkNode(x);
            newNode->next=first;
            first=newNode;
            return true;
        }
        else{
        for(int j=1; j<i-1; j++)
        {
            if(pre==NULL)
                break;
            pre=pre->next;
        }
        if(pre==NULL)
        {
            cerr<<"       "<<endl;
            return false;
        }
        else
        {
            newNode=new LinkNode(x);
            newNode->next=pre->next;
            pre->next=newNode;
        }
        return true;}
      }
      bool Remove(int i, T& x)//     i      ,        x
      {
          LinkNode *p,*q;
          if(i==1)
          {
              p=first;
              first=first->next;
              delete p;
              return true;
          }
          else if(Locate(i)!=NULL)
          {
              p=first;
              for(int j=0;j<i-2;j++)
              {
                  p=p->next;
              }
              q=p->next;
              p->next=q->next;
              delete q;
              return true;
          }
          return false;
      }
      bool IsEmpty() const//        
      {
          return first==NULL;
      }
      bool IsFull() const;//        
      void Sort()//          
      {
           T n,c=0,x;
           LinkNode *p=first,*q;
           if(IsEmpty()==false)
           {
               n=first->data;
               p=p->next;
           }
           while(p!=NULL)
           {
               if(p->data<=n)
               {
                   n=p->data;
                   q=new LinkNode(n);
                   q=q->next;
                   Remove(c,x);
                   continue;
               }
               p=p->next;
               c++;
           }
           MakeEmpty();
           first=q;
      }
      List Combine(List &L)
      {
          List newList;
          LinkNode *p=first,*q=L.first;
          int c=1;
          while(p!=NULL&&q!=NULL)
          {
              if(p->data<=q->data)
              {
                  newList.Insert(c++,p->data);
                  p=p->next;
              }
              else
              {
                  newList.Insert(c++,q->data);
                  q=q->next;
              }
          }
          while(p!=NULL)
          {
              newList.Insert(c++,p->data);
              p=p->next;
          }
          while(q!=NULL)
          {
              newList.Insert(c++,q->data);
              q=q->next;
          }
          return newList;
      }
      void Input(int n)
      {
          int num;
          for(int i=0;i<n;i++)
          {
              cin>>num;
              Insert(i+1,num);
          }
      }
      friend ostream& operator<<(ostream& out, const List& L)//        
      {
          LinkNode *p=L.first;
          for(int i=0;i<L.Length();i++)
          {
              if(i==L.Length()-1) cout<<p->data;
              else{
              cout<<p->data<<" ";
              p=p->next;}
          }
          return out;
      }
      friend istream& operator>>(istream& in, List& L)//        
      {
          T n,num;
          in>>n;
          for(int i=0;i<n;i++)
          {
              cin>>num;
              L.Insert(i+1,num);
          }
          return in;
      }
};
int main()
{
      List lst1;
      cin>>lst1;
      cout<<lst1;
}

좋은 웹페이지 즐겨찾기