sequencelinear.cpp

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

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

typedef int ElemType;
struct List
{
  ElemType *list;
  int size;
  int MaxSize;
};

void InitList(struct List *L,int ms)
{
  if (ms<=0)
  {
    cout<<"ms ERROR"<<endl;
    exit(1);
  }
  L->MaxSize=ms;
  L->list=(ElemType *)malloc(ms*sizeof(ElemType));
  if(!L->list)
  {
    cout<<"malloc error!"<<endl;
    exit(1);
  }
  L->size=0;
}

void ClearList(struct List *L)
{
  if(L->list!=NULL)
  {
    free(L->list);
    L->list=0;
    L->size=L->MaxSize=0;
  }
}

int SizeList(struct List *L)
{
  return L->size;
}

int EmptyList(struct List *L)
{
  if (L->size==0)
    return 1;
  else
    return 0;
}

ElemType GetElem(struct List *L,int pos)
{
  if (pos<1 || pos>L->size)
  {
    cout<<"OverFlow"<<endl;
    exit(1);
  }
  return L->list[pos-1];
}

void TraverseList(struct List *L)
{
  int i;
  for(i=0;i<L->size;i++)
  {
    cout<<L->list[i]<<"   ";
  }
  cout<<endl;
}

int FindList(struct List *L,ElemType x)
{
  int i;
  for(i=0;i<L->size;i++)
    if (L->list[i]==x) return i;
  return -1;
}

int UpdatePosList(struct List *L,int pos,ElemType x)
{
   if (pos<1 || pos>L->size)
     return 0;
   L->list[pos-1]=x;
   return 1;
}

void againMalloc(struct List *L)
{
  ElemType *p=(ElemType *)realloc(L->list,2*L->MaxSize*sizeof(ElemType));
  if(!p)
  {
    cout<<"remalloc error!"<<endl;
    exit(1);
  }
  L->list=p;
  L->MaxSize=2*L->MaxSize;
}

void InsertFirstList(struct List *L,ElemType x)
{
  int i;
  if(L->size==L->MaxSize)
    againMalloc(L);
  for(i=L->size-1;i>=0;i--)
    L->list[i+1]=L->list[i];
  L->list[0]=x;
  L->size++;
}

void InsertLastList(struct List *L,ElemType x)
{
  if(L->size==L->MaxSize)
   againMalloc(L);
  L->list[L->size]=x;
  L->size++;
}

int InsertPosList(struct List *L,int pos,ElemType x)
{
  int i;
  if(pos<1 || pos>L->size+1)
   return 0;
  if(L->size==L->MaxSize)
   againMalloc(L);
  for(i=L->size-1;i>=pos-1;i--)
    L->list[i+1]=L->list[i];
  L->list[pos-1]=x;
  L->size++;
  return 1;
}

void InsertOrderList(struct List *L,ElemType x)
{
  int i,j;
  if(L->size==L->MaxSize)
    againMalloc(L);
  for(i=0;i<L->size;i++)
    if(x<L->list[i]) break;
  for(j=L->size-1;j>=i;j--)
    L->list[j+1]=L->list[j];
  L->list[i]=x;
  L->size++;
}

ElemType DeleteFirstList(struct List *L)
{
  ElemType temp;
  int i;
  if(L->size==0)
  {
    cout<<"linear is empty"<<endl;
    exit(1);
  }
  temp=L->list[0];
  for(i=1;i<L->size;i++)
    L->list[i-1]=L->list[i];
  L->size--;
  return temp;
}

ElemType DeleteLastList(struct List *L)
{
  if (L->size==0)
  {
    cout<<"linear is empty"<<endl;
    exit(1);
  }
  L->size--;
  return L->list[L->size];
}

ElemType DeletePosList(struct List *L,int pos)
{
  ElemType temp;
  int i;
  if(pos<1 || pos>L->size)
  {
    cout<<"pos is not correct"<<endl;
    exit(1);
  }
  temp=L->list[pos-1];
  for(i=pos;i<L->size;i++)
  {
    L->list[i-1]=L->list[i];
  }
  L->size--;
  return temp;
}

int DeleteValueList(struct List *L,ElemType x)
{
   int i,j;
   for(i=0;i<L->size;i++)
     if(L->list[i]==x) break;
   if(i==L->size) return 0;

   for(j=i+1;j<L->size;j++)
    L->list[j-1]=L->list[j];
  L->size--;
  return 1;
}


int main()
{
  int a[10]={2,4,6,8,10,12,14,16,18,20};
  int i;
  struct List L;
  InitList(&L,5);
  for(i=0;i<10;i++)
    InsertLastList(&L,a[i]);

  InsertPosList(&L,11,48);
  InsertPosList(&L,1,64);

  cout<<"The forth Element is "<<GetElem(&L,4)<<endl;

  TraverseList(&L);

  cout<<FindList(&L,10)<<endl;

  UpdatePosList(&L,3,20);

  DeleteFirstList(&L);
  DeleteFirstList(&L);
  DeleteLastList(&L);
  DeleteLastList(&L);

  DeletePosList(&L,5);
  DeletePosList(&L,7);

  cout<<SizeList(&L)<<endl;
  cout<<EmptyList(&L)<<endl;

  TraverseList(&L);
  ClearList(&L);

      system("PAUSE");
      return 0;
}