nlist.cpp

文件中是我编写的两个数据结构

 /************************************************************************/
/*                             NList.cpp                                */
/************************************************************************/
#include <stdio.h>

#ifndef _NLIST_CPP_ 
#define _NLIST_CPP_
#if !defined (_NLIST_H_)
#include "NList.h"
# endif
#endif


//////////////////////////////////////////////////////////////////////////
//initialize
//////////////////////////////////////////////////////////////////////////
//Order List
//////////////////////////////////////////////////////////////////////////

template<class T>
void  SetNull(OList<T> *p)
{
   p->size=0;
}

//Length
template<class T>
int Length(OList<T> *p)
{
   return (p->size);
}

template<class T>
T Get(OList<T> *p,int i)
{
   if(i<1 && i>p->size)
   {
      printf("Position wrong!\n");
      return T(0);
   }
   else
      return (p->list[i-1]);
}

template<class T>
int Locate(OList<T> *p, T x)
{
   int i=0;
   while(i<p->size && p->list[i]!=x)  i++;
   if(i==p->size)
      return (-1);
   else 
      return (i+1);
}

template<class T>
void Insert(OList<T> *p,T x,int i)
{
   int  j;
   if(i<1 && i>p->size+1)
      printf("Position wrong!\n");
   else
   {
      p->size++;
      for(j=p->size-1;j>=i;j--)
        p->list[j]=p->list[j-1];
      p->list[j]=x;
   }
}

template<class T>
void Delete(OList<T> *p,int i)
{
  int j;
  if(i>p->size || i<1)
      printf("Position wrong!\n");
  else
  {
      for(j=i-1;j<p->size-1;j++)
         p->list[j]=p->list[j+1];
      p->size--;
  }     
           
}

template<class T>
void  Display(OList<T> *p)
{
  int j;
  if(p->size==0)
     printf("The list is null!\n");
  else
  {
     printf(" Order List :");
     if(p->size==1)
        printf("%c",p->list[p->size]);
     else
     {
        for(j=0;j<p->size-1;j++)
          printf("%c->",p->list[j]);
        printf("%c",p->list[j]);
     }
     printf("\n");
  }
}

//////////////////////////////////////////////////////////////////////////
//initialize
//////////////////////////////////////////////////////////////////////////
//Single List
//////////////////////////////////////////////////////////////////////////

template<class T>
void  SetNull(SNode<T> **p)
{
   *p=NULL;
}
//
template<class T>
int Length(SNode<T> **p)
{
   int n=0;
   SNode<T>  *q=*p;
   while (q!=NULL)
   {
     n++;
     q=q->next;
   }
   return (n);
}

template<class T>
T Get(SNode<T> **p,int i)
{
   int j=1;
   SNode<T>  *q=*p;
   while(j<i && q!=NULL)
   {
     q=q->next;
     j++;
   }
   if(q!=NULL)
      return (q->Data);
   else
   {
      printf("position wrong!\n");
      return T(0);
   }

}

template<class T>
int Locate(SNode<T> **p, T x)
{
   int n=0;
   SNode<T> *q=*p;
   while(q!=NULL && q->Data!=x)
   {
      q=q->next;
      n++;
   }
   if(q==NULL)
      return (-1);
   else
      return (n+1);
}

template<class T>
void Insert(SNode<T> **p,T x,int i)
{
  int j=1;
  SNode<T>  *s,*q;
  s=new SNode<T>;
  s->Data=x;
  q=*p;
  if(i==1)
  {
     s->next=q;
     *p=s;
  }
  else
  {
     while (j<i-1 && q->next!=NULL)
     {
       q=q->next;
       j++;
     }
     if(j==i-1)
     {
       s->next=q->next;
       q->next=s;
     }
     else
       printf("position wrong!\n");       
  }

}

template<class T>
void Delete(SNode<T> **p,int i)
{
   int j=1;
   SNode<T> *q=*p,*t;
   if(i==1)
   {
      t=q;
      *p=q->next;
   }
   else
   {
      while (j<i-1 && q->next!=NULL) 
      {
         q=q->next;
         j++;
      }
      if(q->next!=NULL && j==i-1)
      {
         t=q->next;
         q->next=t->next;
      }
      else
       printf("position wrong!\n");      
   }
   if(t!=NULL)
      delete t;

}

template<class T>
void Display(SNode<T> **p)
{
   SNode<T> *q;
   q=*p;
   printf("Single display:");
   if(q==NULL)
      printf("List is null!");
   else if(q->next==NULL)
      printf("%c\n",q->Data);
   else
   {
      while (q->next!=NULL) 
      {
         printf("%c->",q->Data);
         q=q->next;
      }  
      printf("%c\n",q->Data);
   }
   printf("\n"); 
 
}

//////////////////////////////////////////////////////////////////////////
//initialize
//////////////////////////////////////////////////////////////////////////
//DHead List
//////////////////////////////////////////////////////////////////////////

template<class T>
void  SetNull(DNode<T> **p)
{
   *p=NULL;
}

template<class T>
int Length(DNode<T> **p)
{
   int n=0;
   DNode<T>  *q=*p;
   while (q!=NULL)
   {
     n++;
     q=q->right;
   }
   return (n);
}

template<class T>
T Get(DNode<T> **p,int i)
{
   int j=1;
   DNode<T>  *q=*p;
   while(j<i && q!=NULL)
   {
     q=q->right;
     j++;
   }
   if(q!=NULL)
      return (q->Data);
   else
   {
      printf("position wrong!\n");
      return T(0);
   }

}

template<class T>
int Locate(DNode<T> **p, T x)
{
   int n=0;
   DNode<T> *q=*p;
   while(q!=NULL && q->Data!=x)
   {
      q=q->right;
      n++;
   }
   if(q==NULL)
      return (-1);
   else
      return (n+1);
}

template<class T>
void Insert(DNode<T> **p,T x,int i)
{
  int j=1;
  DNode<T>  *s,*q;
  s=new DNode<T>;
  s->Data=x;
  s->left=s->right=NULL;
  q=*p;
  if(i==1)
  {
     s->right=q;
     if(q!=NULL)
        q->left=s;
     *p=s;
  }
  else
  {
     while (j<i-1 && q->right!=NULL)
     {
       q=q->right;
       j++;
     }
     if(j==i-1)
     {
       if(q->right!=NULL)
       {
          s->right=q->right;          
          q->right->left=s;
          s->left=q;
          q->right=s;
       }
       else
       {
          s->left=q;
          q->right=s;
       }

     }
     else
       printf("position wrong!\n");       
  }

}

template<class T>
void Delete(DNode<T> **p,int i)
{
   int j=1;
   DNode<T> *q=*p,*t;
   if(i==1)
   {
      t=q;
      q=q->right;
      if(q!=NULL)
         q->left=NULL;
      *p=q;
   }
   else
   {
      while (j<i-1 && q->right!=NULL) 
      {
         q=q->right;
         j++;
      }
      if(q->right!=NULL && j==i-1)
      {
         t=q->right;
         if(t->right!=NULL)
         {
            q->right=t->right;
            q->right->left=q;
         }
         else
            q->right=NULL;
         
      }
      else
       printf("position wrong!\n");      
   }
   if(t!=NULL)
      delete t;

}

template<class T>
void Display(DNode<T> **p)
{
   DNode<T> *q;
   q=*p;
   printf("Single display:");
   if(q==NULL)
      printf("List is null!");
   else if(q->right==NULL)
      printf("%c\n",q->Data);
   else
   {
      while (q->right!=NULL) 
      {
         printf("%c->",q->Data);
         q=q->right;
      }  
      printf("%c\n",q->Data);
   }
   printf("\n"); 
 
}

//////////////////////////////////////////////////////////////////////////
//initialize
//////////////////////////////////////////////////////////////////////////
//Single Circle List
//////////////////////////////////////////////////////////////////////////

template<class T>
void  SetNull(CNode<T> **p)
{
   *p=NULL;
}
//
template<class T>
int Length(CNode<T> **p)
{
   int n=0;
   CNode<T>  *q=*p,*head=*p;
   if(q==NULL)
      return 0;
   n=1;
   while(q->next!=head )//&& q!=p->chead
   {
   	 n++;
     q=q->next;
   }
   return (n);
}

template<class T>
T Get(CNode<T> **p,int i)
{
   int j=1;
   CNode<T>  *q=*p,*head=*p;
   if(q==NULL)
      return T(0);

   while(j<i)// && q->next!=head
   {
     q=q->next;
     j++;
   }
//   if(j!=i)
   return (q->Data); //     printf("position wrong!\n");      return T(0);
}

template<class T>
int Locate(CNode<T> **p, T x)
{
   int n=0;
   CNode<T> *q=*p,*head=*p;
   if(q==NULL)
      return (-1);

   while(q->next!=head && q->Data!=x)
   {
      q=q->next;
      n++;
   }
   if(q->next==head && q->Data!=x)
      return (-1);
   else
      return (n+1);
}

template<class T>
void Insert(CNode<T> **p,T x,int i)
{
  int j=1;
  CNode<T>  *s,*q,*head=*p,*tail=*p;
  s=new CNode<T>;
  s->Data=x;
  q=*p;
  if(q==NULL)
  {
     s->next=s;
     *p=s;
     head=s;
     return;
  } 

  while (tail->next!=head) 
  {
     tail=tail->next;
  }
     
  if(i==1)
  {
     s->next=q;
     tail->next=s;
     *p=s;
     head=s;
  }
  else
  {
     while (j<i-1)// && q->next!=NULL)&& q->next->next!=head
     {
       q=q->next;
       j++;
     }
     if(q->next==head)
     {
       s->next=q->next;
       q->next=s;
       //head=s;
       *p=head;
     }
     else
     {
       s->next=q->next;
       q->next=s;
       *p=head;       
     }
        
  }

}

template<class T>
void Delete(CNode<T> **p,int i)
{
   int j=1;
   CNode<T> *q=*p,*t,*tail=*p,*head=*p;
   if(q==NULL)
      return;

   while (tail->next!=head) 
   {
      tail=tail->next;
   }

   if(i==1)
   {
      t=q;
      tail->next=q->next;
      *p=q->next;
   }
   else
   {
      while (j<i-1)//  && q->next!=NULL
      {
         q=q->next;
         j++;
      }
      if(q->next==head)// j==i-1&& q->next!=NULL
      {
         t=q->next;
         q->next=t->next;
         *p=t->next;
      }
      else
      {
         t=q->next;
         q->next=t->next;
         *p=head;
      }
         
   }
   if(t!=NULL)
      delete t;

}

template<class T>
void Display(CNode<T> **p)
{
   CNode<T> *q,*head=*p;
   q=*p;
   printf("Single display:");
   if(q==NULL)
      printf("List is null!");
   else if(q->next==head)
      printf("%c\n",q->Data);
   else
   {
      while (q->next!=head) 
      {
         printf("%c->",q->Data);
         q=q->next;
      }  
      printf("%c\n",q->Data);
   }
   printf("\n"); 
 
}