顺序表的实现(头插、尾插、头删、尾删、查找、删除、插入)

// 顺序表的静态存储
#define N 100
typedef int SLDataType;
typedef struct SeqList
{
     SLDataType array[N]; // 定长数组
     size_t size;     // 有效数据的个数 
}SeqList;

// 顺序表的动态存储
typedef struct SeqList
2.2 接口实现： 
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大
了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态
的分配空间大小，所以下面我们实现动态顺序表。
{
     SLDataType* array;  // 指向动态开辟的数组
     size_t size ;       // 有效数据个数
     size_t capicity ;   // 容量空间的大小
}SeqList;

//#pragma once
#ifndef _SEQLIST_H_
#define _SEQLIST_H_
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
//增强程序的可维护性
#define MAX_SIZE 10
typedef int SQDataType;
//静态顺序表
//问题:给少了不够用,给多了用不完浪费,不能灵活控制
//typedef struct SeqList
//{
//  SQDataType a[MAX_SIZE];
//  int size;
//}SL;
typedef struct SeqList
{
  SQDataType *a;// 指向动态开辟的数组
  int size;  //有效的数据的个数
  int capacity;//容量
}SL;
//typedef struct SeqList SL;//定义为简写
// 基本增删查改接口
// 顺序表初始化
//增删查改等接口函数
//void SeqListInit(struct SeqList s);
//顺序表初始化
void SeqListInint(SL* ps);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList * psl);
//顺序表打印
void SeqListPrint(SL* ps);
// 顺序表销毁
void SeqListDestory(SL* ps);
//顺序表尾插
void SeqListPushBack(SL* ps, SQDataType x);
//顺序表头插
void SeqListPushFront(SL* ps, SQDataType x);
//顺序表头删
void SeqListPopBack(SL* ps);
//顺序表尾删
void SeqListPopFront(SL* ps);
// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SQDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos);
#endif

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

// 函数定义，传入一个指向顺序列表（SeqList）的指针  
void SeqListCheckCapacity(SL* ps)  
{  
    // 检查顺序列表是否已满，即当前大小（size）是否等于容量（capacity）  
    if (ps->size == ps->capacity)  
    {  
        // 如果满了，计算新的容量。如果当前容量为0，则新容量为4；否则，新容量为当前容量的2倍  
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;  
          
        // 使用realloc函数尝试调整顺序列表的数组大小  
        // realloc可能会改变原有内存块的位置，因此需要使用一个临时指针来接收结果  
        SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));  
          
        // 检查realloc是否成功  
        if (tmp == NULL)  
        {  
            // 如果失败，打印错误信息并退出程序  
            printf("realloc fail\n");  
            exit(-1);  
        }  
        else  
        {  
            // 如果成功，更新顺序列表的数组指针和容量  
            ps->a = tmp;  
            ps->capacity = newcapacity;  
        }  
    }  
}

// 打印顺序列表中的所有元素  
void SeqListPrint(SL* ps)  
{  
    // 通过循环遍历顺序列表中的每一个元素  
    for (int i = 0; i < ps->size; i++)  
    {  
         
        printf("%d ", ps->a[i]);  
    }  
    // 打印一个换行符，使得每次打印列表后都会换行，输出更清晰  
    printf("\n");  
}

// 销毁顺序列表的函数  
void SeqListDestroy(SL* ps)  
{  
    // 断言：确保传入的顺序列表指针ps不为空  
    assert(ps);  
  
    // 判断顺序列表的数组指针a是否不为空  
    if (ps->a != NULL)  
    {  
        // 释放数组指针a所指向的内存空间  
        free(ps->a);  
          
        // 将数组指针a设置为NULL，避免野指针  
        ps->a = NULL;  
          
        // 将顺序列表的大小设置为0，表示列表已空  
        ps->size = 0;  
          
        // 将顺序列表的容量设置为0，表示已没有分配内存空间  
        ps->capacity = 0;  
    }  
}

// 尾插法：在顺序列表的末尾插入一个新元素  
void SeqListPushBack(SL* ps, SQDataType x)  
{  
    //断言--粗暴的解决方式
    //assert(ps != NULL)
    assert(ps);
    
    // 检查当前顺序列表的容量是否足够，如果不够则进行扩容  
    SeqListCheckCapacity(ps);  
      
    // 在顺序列表的当前末尾位置插入新元素  
    ps->a[ps->size] = x;  
      
    // 更新顺序列表的大小（元素数量）  
    ps->size++;  
}

// 头插法：在顺序列表的开头插入一个新元素  
void SeqListPushFront(SL* ps, SQDataType x)  
{  
    // 检查当前顺序列表的容量是否足够，如果不够则进行扩容  
    SeqListCheckCapacity(ps);  
      
    // 初始化：设定一个变量来追踪当前需要移动的元素的位置  
    // 结束条件：当所有元素都已移动到它们的新位置时停止  
    // 迭代过程：从列表的末尾开始，将每个元素向后移动一个位置以腾出空间  
    int end = ps->size - 1; // 从列表的最后一个元素开始  
    while (end >= 0) // 当还有元素需要移动时继续循环  
    {  
        // 将当前位置的元素向后移动一个位置  
        ps->a[end + 1] = ps->a[end];  
        --end; // 移动到前一个元素  
    }  
  
    // 在顺序列表的开头（现在为空）插入新元素  
    ps->a[0] = x;  
      
    // 更新顺序列表的大小（元素数量）  
    ps->size++;  
}

// 头删：删除顺序列表的第一个元素  
void SeqListPopFront(SL* ps)  
{  
    // 断言，确保顺序列表不为空，即其大小大于0  
    // 如果ps->size <= 0，则触发断言错误，终止程序  
    assert(ps->size > 0);  
      
    // 初始化一个变量start，用于从第二个元素开始遍历  
    int start = 1;  
      
    // 当start小于列表大小时，执行循环  
    // 这个循环用于将第一个位置之后的元素都向前移动一个位置，从而覆盖掉第一个位置的元素  
    while (start < ps->size)  
    {  
        // 将下一个位置的元素移动到当前位置  
        ps->a[start - 1] = ps->a[start];  
        // start向后移动一个位置，继续处理下一个元素  
        start++;  
    }  
      
    // 因为第一个元素已经被覆盖，所以不需要额外处理  
    // 更新顺序列表的大小（元素数量），因为删除了一个元素，所以大小减1  
    ps->size--;  
}

// 尾删：删除顺序列表的最后一个元素  
void SeqListPopBack(SL* ps)  
{  
    // 断言，确保顺序列表不为空，即其大小大于0  
    // 如果ps->size <= 0，则触发断言错误，终止程序  
    assert(ps->size > 0);  
      
    // 可以选择将最后一个元素的值设置为0或其他默认值，以确保不留下未定义的值  
    // 但这取决于具体的应用需求，有时可能不需要这样做  
    //ps->a[ps->size - 1] = 0;  
      
    // 更新顺序列表的大小（元素数量），因为删除了一个元素，所以大小减1  
    ps->size--;  
}

// 在顺序列表的指定位置插入一个元素  
void SeqListInsert(SL* ps, int pos, SQDataType x)  
{  
    // 断言，确保插入的位置不会超出当前列表的大小  
    assert(pos >= 0 && pos < ps->size);  
      
    // 检查当前顺序列表的容量是否足够，如果不够则进行扩容  
    SeqListCheckCapacity(ps);  
  
    // 初始化一个变量end，用于从列表的末尾开始遍历  
    int end = ps->size - 1;  
      
    // 当end位置大于或等于要插入的位置pos时，执行循环  
    // 这个循环用于将pos位置及其之后的元素都向后移动一个位置，为插入新元素腾出空间  
    while (end >= pos)  
    {  
        // 将当前位置的元素向后移动一个位置  
        ps->a[end + 1] = ps->a[end];  
        // end向前移动一个位置，继续处理前一个元素  
        end--;  
    }  
  
    // 在腾出的位置pos处插入新元素x  
    ps->a[pos] = x;  
      
    // 更新顺序列表的大小（元素数量）  
    ps->size++;  
}

// 删除顺序列表中指定位置的元素  
void SeqListErase(SL* ps, int pos)  
{  
    // 断言，确保要删除的位置不会超出当前列表的大小  
    // 如果pos >= ps->size，则触发断言错误，终止程序  
    assert(pos >= 0 && pos < ps->size);  
      
    // 初始化一个变量start，用于从要删除的位置的下一个元素开始遍历  
    int start = pos + 1;  
      
    // 当start小于列表大小时，执行循环  
    // 这个循环用于将pos位置之后的元素都向前移动一个位置，覆盖掉pos位置的元素  
    while (start < ps->size)  
    {  
        // 将下一个位置的元素移动到当前位置  
        ps->a[start - 1] = ps->a[start];  
        // start向后移动一个位置，继续处理下一个元素  
        start++;  
    }  
      
    // 更新顺序列表的大小（元素数量），因为删除了一个元素，所以大小减1  
    ps->size--;  
}

int SeqListFind(SL* ps, SQDataType x)
{
  for (int i = 0;i< ps->capacity; i++)
  {
    if (ps->a[i] == x)
    {
      return i + 1;//下标为i，第i+1个数据
    }
  }
  return 0;
}