singlelist.cpp

我们计算机科学学院教授上数据结构的课件

#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>

#define NN 12
#define MM 20
typedef int ElemType;
struct sNode
{
  ElemType data;
  struct sNode *next;
};

void InitList(struct sNode **HL)
{
  *HL=NULL;
}

void ClearList(struct sNode **HL)
{
  struct sNode *cp,*np;
  cp=*HL;
  while(cp!=NULL)
  {
    np=cp->next;
    free(cp);
    cp=np;
  }
  *HL=NULL;
}

int SizeList(struct sNode *HL)
{
  int i=0;
  while(HL!=NULL)
  {
    i++;
    HL=HL->next;
  }
  return i;
}

int EmptyList(struct sNode *HL)
{
  if(HL==NULL)
    return 1;
  else
    return 0;
}

ElemType GetElem(struct sNode *HL,int pos)
{
  int i=0;
  if(pos<1)
  {
    cout<<"pos is not correct!"<<endl;
    exit(1);
  }
  while(HL!=NULL)
  {
    i++;
    if(i==pos) break;
    HL=HL->next;
  }
  if(HL!=NULL)
    return HL->data;
  else
  {
    cout<<"pos error!"<<endl;
    exit(1);
  }
}

void TraverseList(struct sNode *HL)
{
  while(HL!=NULL)
  {
    cout<<HL->data<<"   ";
    HL=HL->next;
  }
  cout<<endl;
}

ElemType * FindList(struct sNode *HL,ElemType x)
{
  while(HL!=NULL)
  {
    if(HL->data==x)
      return &HL->data;
    else
      HL=HL->next;
  }
  return NULL;
}

int UpdatePosList(struct sNode *HL,int pos,ElemType x)
{
  int i=0;
  struct sNode *p=HL;
  while(p!=NULL)
  {
    i++;
    if(pos==i)
       break;
    else
      p=p->next;
  }
  if(pos==i)
  {
     p->data=x;
     return 1;
  }
  else
    return 0;
}

void InsertFirstList(struct sNode **HL,ElemType x)
{
  struct sNode *newp;
  newp=(struct sNode *)malloc(sizeof(struct sNode));
  if(newp==NULL)
  {
    cout<<"Memory allocation error!"<<endl;
    exit(1);
  }
  newp->data=x;
  newp->next=*HL;
  *HL=newp;
}

void InsertLastList(struct sNode **HL,ElemType x)
{
  struct sNode *newp;
  newp=(struct sNode *)malloc(sizeof(struct sNode));
  if(newp==NULL)
  {
    cout<<"Memory allocation error!"<<endl;
    exit(1);
  }
  newp->data=x;
  newp->next=NULL;
  if(*HL==NULL)
    *HL=newp;
  else
  {
    struct sNode *p=*HL;
    while(p->next!=NULL) p=p->next;
    p->next=newp;
  }
}

int InsertPosList(struct sNode **HL,int pos,ElemType x)
{
  int i=0;
  struct sNode *newp;
  struct sNode *cp=*HL,*ap=NULL;
  if(pos<=0)
  {
    cout<<"Pos is not correct!"<<endl;
    return 0;
  }
  while(cp!=NULL)
  {
    i++;
    if(pos==i) break;
    else
    {
      ap=cp;cp=cp->next;
    }
  }
  newp=(struct sNode *)malloc(sizeof(struct sNode));
  if(newp==NULL)
  {
    cout<<"Memory alloction error!"<<endl;
    return 0;
  }
  newp->data=x;
  if(ap==NULL)
  {
    newp->next=cp;
    *HL=newp;
  }
  else
  {
    newp->next=cp;
    ap->next=newp;
  }
  return 1;
}

void InsertOrderList(struct sNode **HL,ElemType x)
{
  struct sNode *cp=*HL,*ap=NULL;
  struct sNode *newp;
  newp=(struct sNode *)malloc(sizeof(struct sNode));
  if(newp==NULL)
  {
    cout<<"Memory alloction error!"<<endl;
    return ;
  }
  newp->data=x;
  if(cp==NULL || x<cp->data)
  {
    newp->next=cp;
    *HL=newp;
    return ;
  }
  while(cp!=NULL)
  {
    if(x<cp->data) break;
    else
    {
      ap=cp;cp=cp->next;
    }
   }
   newp->next=cp;
   ap->next=newp;
}

ElemType DeleteFirstList(struct sNode **HL)
{
  ElemType temp;
  struct sNode *p=*HL;
  if(*HL==NULL)
  {
    cout<<"List is Empty!Can't delete."<<endl;
    exit(1);
  }
  *HL=(*HL)->next;
  temp=p->data;
  free(p);
  return temp;
}

ElemType DeleteLastList(struct sNode **HL)
{
  ElemType temp;
  struct sNode *cp=*HL;
  struct sNode *ap=NULL;
  if(cp==NULL)
  {
    cout<<"List is Empty!Can't delete."<<endl;
    exit(1);
  }
  while(cp->next!=NULL)
  {
    ap=cp;cp=cp->next;
  }
  if(ap==NULL)         //Only one node
    *HL=(*HL)->next;
  else
     ap->next=NULL;
  temp=cp->data;
  free(cp);
  return temp;
}

ElemType DeletePosList(struct sNode **HL,int pos)
{
  int i=0;
  ElemType temp;
  struct sNode *cp=*HL;
  struct sNode *ap=NULL;
  if(cp==NULL || pos<=0)
  {
    cout<<"List is Empty or Pos is not correct!"<<endl;
    exit(1);
  }
  while(cp!=NULL)
  {
    i++;
    if(i==pos)break;
    ap=cp;cp=cp->next;
  }
  if(cp==NULL)
  {
    cout<<"Pos is error!"<<endl;
    exit(1);
  }
  if(pos==1)
    *HL=(*HL)->next;
  else
    ap->next=cp->next;
  temp=cp->data;
  free(cp);
  return temp;
}

int DeleteValueList(struct sNode **HL,ElemType x)
{
  struct sNode *cp=*HL;
  struct sNode *ap=NULL;
  while(cp!=NULL)
  {
    if(cp->data==x)break;
    ap=cp;cp=cp->next;
  }
  if(cp==NULL) return 0;
  if(ap==NULL)
    *HL=(*HL)->next;
  else
    ap->next=cp->next;
  free(cp);
  return 1;
}

int main()
{
  int a[NN];
  int i;
  struct sNode *p,*h,*s;

  InitList(&p);

  for(i=0;i<NN;i++)
    a[i]=rand()%MM;
  cout<<"Random is:    ";
  for(i=0;i<NN;i++)
   cout<<a[i]<<"  ";
  cout<<endl;

  for(i=0;i<NN;i++)
    InsertFirstList(&p,a[i]);
  TraverseList(p);

  cout<<"List Size is:"<<SizeList(p)<<endl;

  for(h=p;h!=NULL;h=h->next)
    while(DeleteValueList(&(h->next),h->data));

  cout<<"Delete repeat Number:";
  TraverseList(p);

  h=NULL;
  for(s=p;s!=NULL;s=s->next)
    InsertOrderList(&h,s->data);
 cout<<"Order List:";
 TraverseList(h);
 ClearList(&p);

      system("PAUSE");
      return 0;
}