实现顺序表的增删查改

用户11039545

发布于 2024-04-15 08:26:44

1000

发布于 2024-04-15 08:26:44

文章被收录于专栏：c语言

现在让我们探索数据结构这个美妙的世界吧！

概念介绍

线性表是具有相同特性的数据元素的有限序列。线性表是一种在实际运用中广泛运用的线性结构，如线性表，栈，队列，字符串等。

顺序表的本质是数组，实现了对数组的封装，例如增删查改等功能。

顺序表分为静态顺序表和动态顺序表：

静态顺序表：

#define N 100
struct SeqList
{
    int arr[N];
    int size;//有效数据个数
};

动态顺序表：

struct SeqList
{
     int* arr;//动态数组
     int size;//有效数据个数
     int capacity;//空间大小
};

但是目前这个结构体只能存储int类型的数据，所以我们给数据类型起一个别名，让其更好存储其他类型的数据。

我们当前顺序表存储的类型进行替换：

typedef int SLDataType;

当前顺序表被我们修改成这样：

struct SeqList
{
     SLDataType* arr;//动态数组
     int size;//有效数据个数
     int capacity;//空间大小
};

但是每次引用我们的顺序表时，我们都要写SeqList，这样未免太麻烦了，于是我们想到用typedef一下来缩减我们的工作量。

typedef struct SeqList SL;

或者我们还可以采用另一种方式：

typedef struct SeqList
{
     SLDataType* arr;//动态数组
     int size;//有效数据个数
     int capacity;//空间大小
}SL;

初始化

void SLInit(SL* ps);
void SLInit(SL s)
{
   s.arr=NULL;
   s.size=s.capcity=0;
}

我们测试一下顺序表初始化的一些方法：

void SLTest01()
{
   SL s1;
   SLInit(s1);
}

int main()
{
   SLTest01();
   return 0;
}

这个程序初始化的结果竟然是错误的，那么问题出现在哪里呢？问题在于我们没有传地址，仅仅是传值调用了。那就让我们修改一下我们的代码吧。

void SLInit(SL* ps);
void SLInit(SL* ps)
{
   s.arr=NULL;
   s.size=s.capcity=0;
}

void SLTest01()
{
   SL s1;
   SLInit(&s1);
}

int main()
{
   SLTest01();
   return 0;
}

销毁

void SLDestroy(SL* ps);
void SLDestroy(SL* ps)
{
   if(ps->arr)
   {
      free(ps->arr);
   }
   ps->arr=NULL;
   ps->size=ps->capcity=0;
}

尾部插入

void SLPushBack(SL* ps, SLDataType x);//往哪儿插入未知，所以要传入结构体

如图所示，size从4变成了5。

void SLPushBack(SL* ps, SLDataType x)
{
  //我们要往size里面插入x
   ps->arr[size++]=x;//size后置加加，完成这个式子以后，size的空间被扩展
}

插入完成之后，让我们测试一下这个函数吧。

void SLTest01()
{
  SL s1;
  SLPushBack(&s1,1);
}

但是测试的结果竟然是错误的，这是为啥呢？

空间为0，不能往数组里插入数据。在插入数据之前，我们应该先检查空间够不够。

void SLPushBack(SL* ps, SLDataType x)
{
  //我们要往size里面插入x
   if(ps->capacity=ps->size)
   {
     //申请空间，增容通常是成倍地增加
     //如果malloc失败，会返回空指针
   int newCapacity=ps->capacity==0?4:2*ps->capacity;
     //我们再把申请来的空间给临时的tmp
   SLDataType*tmp=(SLDataType*)realloc(ps->arr,newCapacity*sizeof(SLDataTpye);
   if(tmp==NULL)
   {
       perror("realloc fail");
       exit(1);//直接退出程序，不再执行
    }
   ps->arr=tmp;//如果开辟成功，就把realloc出的新空间给arr
   ps->capacity=newCapacity;
     
   ps->arr[size++]=x;//size后置加加，完成这个式子以后，size的空间被扩展
}

如果我们插入空（NULL），这个程序就崩了。说明这个代码还不具备健壮性

那么我们可以如何解决呢？

if(ps==NULL)
{
   return;
}

这样遇到空，程序就会结束。我们也可以换一种方式：

assert(ps);

等价于assert(ps!=NULL); 这时如果为空，就直接一个弹窗出来报错了。

头部插入

void SLPushFront(SL* ps, SLDataType x);

插入数据我们就想到空间是否够用呢？

void SLPushFront(SL* ps, SLDataType x)
{
    assert(ps);//检查ps是否为空
    SLCheckCapacity(ps);
    //先让顺序表向后挪动一位
    for(int i=ps->size;i>0;i--)
    //要判断函数的终止条件，就要看最后一个移动的条件是什么？这个程序是从后往前挪动，那么最后一次挪动就是arr[0]挪动到arr[1]，那么i等于1，i大于0
    {
       ps->arr[i]=ps->arr[i-1];
     }
     ps->arr[0]=x;
     ps->size++;
}

在我们检查函数空间大小是否够用时，我们可以单独封装一个函数。

void SLCheckCapacity(SL*ps)
{
  //我们要往size里面插入x
   if(ps->capacity=ps->size)
   {
     //申请空间，增容通常是成倍地增加
     //如果malloc失败，会返回空指针
   int newCapacity=ps->capacity==0?4:2*ps->capacity;
     //我们再把申请来的空间给临时的tmp
   SLDataType*tmp=(SLDataType*)realloc(ps->arr,newCapacity*sizeof(SLDataTpye));
   if(tmp==NULL)
   {
       perror("realloc fail");
       exit(1);//直接退出程序，不再执行
    }
   ps->arr=tmp;//如果开辟成功，就把realloc出的新空间给arr
   ps->capacity=newCapacity;
}

当我们运行完一个程序时，打印一下查看结果是否正确。

void Print(SL s)
{
   for(int i=0;i<s.size;i++)
   {
      printf("%d",s.arr[i]);
   }
   printf("\n");
}

出乎意料的是，打印的结果不是我们想要的：

好吧，增加一个数据，我们的size忘了++了。

尾部删除

void SLPopBack(SL*PS)
{
//ps不能为空，所以要先判断一下
   assert(ps);
   assert(ps->size);//数据个数也不能为空
   ps->arr[size-1]=-1;
   --ps->size;
}

直接把size--，不影响增删查改数据。

头部删除

void SLPopFront(SL*ps)
{
   assert(ps);
   assert(ps->size);
   for(int i=0;i<ps->size-1;i++)
   {
      ps->arr[i]=ps->arr[i+1];//arr[size-1]=arr[size-2]
   }
   ps->size--;
}

在指定位置之前插入数据

void SLInsert(SL*ps,int pos,SLDataType x)
{
    assert(ps);
    assert(pos>=0&&pos<=ps->size);//可以等于，可以在size之前插入数据，在这里也就是尾插
    SLCheckCapacity(ps);//插入空间要够用 
    //让pos以及之后的数据整体往后挪动一位
    for(int i=ps->size;i<;i--)
    {
       ps->arr[i]=ps->arr[i-1];//arr[pos+1]=arr[pos];
     }
    ps->arr[pos]=x;
    ps->size++;
 }

删除指定位置的数据

void SLErase(SL*ps,int pos)
{
   assert(ps);//顺序表的地址不能为空
   assert(pos>=0&&pos>size);
   for(int i=pos;i<ps->size-1;i++)
   {
      ps->arr[i]=ps->arr[i+1];
   }
   ps->size--;
}

但是要注意的是pos不能等于size，size是有效数据的后一位。

找位置的元素

int SLFind(SL*ps,SLDataType x)
{
   assert(ps);
   for(int i=0;i<ps->size;i++)
   {
      if(ps->arr[i]==x)
      {
         return i;
      }
      else
         return -1;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-04-04，如有侵权请联系 cloudcommunity@tencent.com 删除

size