顺序表的简单原理实现

#define  _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDatatype;
int newcapacity = 0;
struct SeqList
{
  SLDatatype* data;//其实我们有了地址还可以搞链表，我们动态顺序表存储方式其实是顺序存储的，所以我们不需要去记节点
  int size;
  int capacity;
};
typedef struct SeqList SL;
void SLInti(SL* ps);//初始化,千万不要写成void SLInti(SL s)，因为函数在传参的时候，形参是实参的一份临时拷贝
void SLInti(SL* ps)//一定得开辟个空间变量，因为他不像链表一样有个地址即可
{
  ps->data = NULL;
  ps->capacity = 0;
  ps->size = 0;
}
void CheckCapacity(SL* ps);//检查容量
void CheckCapacity(SL* ps)
{
  if (newcapacity == ps->capacity)
  {
    newcapacity = ps->capacity == 0 ? 4 : newcapacity * 2;//这个有什么作用呢，
     //因为这里是我们如果空间为0，扩两倍那等于没阔，所以我们如果是0的话空间就给4，而且用三目操作符又比
     //ifelse代码更简介，效率更高
    SLDatatype* ptr = (SLDatatype*)realloc(ps->data, newcapacity * sizeof(SLDatatype));
    if (ptr == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    ps->data = ptr;//为什么要给指针赋值，因为当我们在申请空间时，操作系统会去识别你需要的的空间是否被占用，如果
    //被占用那么操作系统会去重新分配个地址，释放原来的空间，并把原先的数据拷贝到新地址指向的空间
    //，因为我SL * ps们不知道realloc扩容后返回的地址是异地扩容还是原地扩容
  }
}
void SListPushBack(SL* ps, SLDatatype X);//尾插
void SListPushBack(SL* ps, SLDatatype X)//尾插
{
  CheckCapacity(ps);
  ps->data[ps->size] = X;
  ++ps->capacity;
  ++ps->size;
}
void SListPushFont(SL* ps, SLDatatype X);//头插
void SListPushFont(SL* ps, SLDatatype X)//头插
{
  assert(ps->size >= 0);//只能在有效数据内插入
  CheckCapacity(ps);
  int i = 0;
  for (i=ps->size;i>=1;--i)//从最后一个数据开始依次往后覆盖，最后把首元素插入
  {
    assert(ps->size < newcapacity);
    ps->data[i] = ps->data[i - 1];
  }
  ps->data[0] = X;//首元素插入
  ++ps->size;
  ++ps->capacity;
}
void SListPopBack(SL* ps, SLDatatype X);//尾删
void SListPopBack(SL* ps,SLDatatype X)
{ 
  assert(ps->size > 0);
  --ps->size;//删除一个size减去一个
}
void SListPrint(SL* ps);//打印数据
void SListPrint(SL* ps)
{
  for (int i=0;i<=ps->size-1;i++)
  {
    printf("%d->", ps->data[i]);//我们只打印有效数据就行，因为我们的size和capacity
  }//一直在追踪整个顺序表，我添加一个size+1一次，capacity+1次
  printf("\n");
}
void SListPopFront(SL* ps);//头删
void SListPopFront(SL* ps)
{
  assert(ps->size > 0);//判断里面有木有数
  assert(ps->capacity > 0);//没有就不删除
  for (int i=1;i<ps->size;i++)//直接看作删完，后面覆盖到前面，从第二个开始依次往前覆盖
  {
    ps->data[i - 1] = ps->data[i];
  }
  --ps->size;//删完之后减去个数
  --ps->capacity;//删完之后减去占用空间
}
int SListSearch(SL* ps, SLDatatype X);//搜索你要的数——返回下标，没找到返回-1
int SListSearch(SL* ps, SLDatatype X)//这里的SLDatatype X是你要找的数
{
  assert(ps->capacity > 0);
  for (int i=0;i<ps->size;i++)
  {
    if (ps->data[i]==X)
    {
      return i;//找到想要的数,返回他的下标
    }
  }
  return -1;//没找到返回-1
}
void SListDesignInsert(SL* ps, SLDatatype X,int x);//指定插入——找到那个数我们才插入，否则就不插入，
//所以我们在这里会判断一个是否找到下标
void SListDesignInsert(SL* ps, SLDatatype X,int x)//这里的SLDatatype X是我们找到的下标
{
  assert(ps->capacity > 0);
  CheckCapacity(ps);
  for (int i=ps->size;i>X;i--)//从后面的数依次存到后面
  {
    ps->data[i] = ps->data[i - 1];//没问题
  }
  ps->data[X] = x;
  ++ps->size;
  ++ps->capacity;
}
void SListDesignErase(SL* ps, SLDatatype X);
void SListDesignErase(SL* ps, SLDatatype X)//指定删除
{
  assert(ps->capacity > 0);
  for (int i=0;i<ps->size;i++)
  {
    if (X == ps->data[i])
    {
      int j = 0;
      for (j = i;j < ps->size-1;j++)//从前面的顺序依次往前面放
      {
        ps->data[j] = ps->data[j+1];//没问题
      }
      --ps->size;
      --ps->capacity;
      break;
    }
  }
}
void SListInsert(SL* ps, SLDatatype X,int x);
void SListInsert(SL* ps,SLDatatype X,int x)//随机插入---（其实我们也可以变成头插）——此时的SLDatatype X是下标
{
  assert(ps);
  assert(X >= 0 && X<=ps->size);
  CheckCapacity(ps);
  int Src = X ;
  int End = ps->size;
  while (Src<End)//要把头插和尾插的方面也考虑进去
  {
    ps->data[End] = ps->data[End - 1];
    --End;
  }
  ps->data[X] = x;
  ++ps->size;
  ++ps->capacity;
}
void SListErase(SL* ps, SLDatatype X);//随机删除——此时的SLDatatype X是下标
void SListErase(SL* ps, SLDatatype X)
{
  assert(ps);
  assert(ps->size>0);
  assert(X >= 0 && X<=ps->size - 1);
  int Src = X;
  int End = ps->size - 1;
  while (Src<End)//删除的顺序跟插入的顺序是不一样的
  {
    ps->data[Src] = ps->data[Src + 1];
    Src++;
  }
  --ps->size;
  --ps->capacity;
}
void Dsetory(SL* ps);
void Dsetory(SL* ps)
{
  free(ps->data);
  ps->data = NULL;
  ps->capacity = 0;
  newcapacity = 0;
  ps->size = 0;
}

#define  _CRT_SECURE_NO_WARNINGS 1
#include "10.26.h"
#include <stdio.h>
int main()
{
  SL s1;
  SLInti(&s1);
  SListPushFont(&s1, 2);
  SListPushFont(&s1, 3);
  SListPushFont(&s1, 4);
  SListPushFont(&s1, 5);
  SListPushFont(&s1, 6);
  SListDesignInsert(&s1, SListSearch(&s1, 6),7);
  SListPushBack(&s1, 7);
  SListPushBack(&s1, 8);
  SListPushBack(&s1, 9);
  SListPushBack(&s1, 10);
  SListDesignInsert(&s1, SListSearch(&s1, 4), 7);
  SListDesignInsert(&s1, SListSearch(&s1, 6), 7);
  SListDesignErase(&s1, SListSearch(&s1, 6), 7);
  SListPrint(&s1);
  SListInsert(&s1, 2, 8);
  SListInsert(&s1, 0, 8);
  SListInsert(&s1, 13, 8);
  SListPrint(&s1);
  SListErase(&s1, 0);
  SListErase(&s1, 10);
  SListErase(&s1, 2);
  SListPrint(&s1);
  Dsetory(&s1);
}