顺序表（一）

一、顺序表定义

1、顺序表概念

1.1、线性表的概念

线性表是数据结构的一种，一个线性表是n个具有相同特性的元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。常见的线性表：顺序表、链表、栈、队列等。
线性表在逻辑上是线性结构但在物理上不一定是连续的。

1.2、顺序表的概念

顺序表是线性表的一种，它将数据元素存储在一段连续的存储空间中，每个元素占据一个存储单元，并按照逻辑顺序依次存放。顺序表的逻辑和物理都是线性结构。
顺序表的底层结构就是数组，顺序表通常采用数组实现，通过对数组进行封装，实现了增删改查操作。

2、顺序表分类

顺序表有静态顺序表和动态顺序表两种。

2.1、静态顺序表的定义

  struct SeqList
 {
   int arr[100];//定长数组
   int size;//顺序表当前有效的数据个数
 };

2.2、动态顺序表的定义

struct SeqList
{
  int* arr;//动态内存开辟，确定大小之后再去动态申请
  int size;//有效的数据个数
  int capacity;//空间大小
};
 

动态顺序表和静态顺序表相比，更加灵活，方便随时改变其空间大小，从而方便对其结构进行增删查改所以接下来的所有操作都是基于动态顺序表。

二、动态顺序表基础

1、创建一个顺序表

 typedef int SLDataType;
 typedef struct SeqList
 {
   SLDataType* arr;
   int capacity;//动态顺序表申请空间的大小
   int size;//顺序表中有效的数据个数
 }SL;
 //或者单独写一行 typedef struct SeqList SL;
 

通过 typedef 将 int 改名为 SLDataType，定义了一个类型名字，方便后期快速修改。将SeqList 改名为 SL，方便使用。

2、顺序表初始化

创建完成顺序表之后，需要对顺序表进行初始化。

void SLInit(SL* ps)
{
  ps->arr = NULL;
  ps->size = ps->capacity = 0;
}

ps 是指针变量，用于接受地址，这里进行的是址拷贝

3、顺序表的销毁

前言:

顺序表的销毁主要是为了释放不再使用的内存空间，避免内存泄漏。在程序运行过程中，顺序表可能会动态地分配内存空间来存储元素。当顺序表不再需要时，如果不进行销毁操作，之前分配的内存空间将不会被系统回收，导致内存资源浪费，进而可能引发内存泄漏问题。

 void SLDestroy(SL* ps)
 {
   if(ps->arr)
   {
     free(ps->arr)
   }//判断顺序表不为空即申请的有空间，有空间要销毁
   ps->arr = NULL;//销毁完arr要置为空
   ps->capacity = ps->size =0;//size 和capacity也要销毁
}

4、顺序表扩容检查

在进行顺序表的插入操作中，如果capacity为0，则插入不了数据，这时候要进行扩容，所以在进行插入操作之前，要进行扩容检查操作。

 void SLCheckCapacity(SL* ps,SLDataType x)
 {
   assert(ps);//ps不能为空
   if(ps->capacity == ps->size)//当capacity与size的值相等时，说明需要扩容
   {
      int newCapaciry =ps-> capacity = 0 ? 4: 2*ps->capacity;
      //当capacity初始化为0时，直接相乘的结还是0！所以capacity不能为0，定义一个新的变量newCapacity，扩容以2倍扩容
      SLDataType* tmp = (SLDataType*)realloc(ps->arr;newCapacity*sizeof(SLDataType));//扩容用realloc函数，定义一个新的变量tmp,r如果申请空间成功，再将tmp的值给ps->arr
      if(tmp == NULL)
      {
        perror("realloc fail!");
        exit(1);
      }//如果tmp为空，说明申请空间失败，报错
      ps->arr = tmp;//申请空间成功
      ps->capacity = newCapacity;//空间大小同步改为capacity
 }

5、顺序表的打印

传址

 void SLPrint(SL* ps)
 {
   for(int i = 0;i<ps->size;i++)
   {
    printf("%d",ps->arr[i]);
   }
printf("\n");

或者传值

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

两种写法都可以

未完待续…