初识顺序表---C语言

目录

一、什么是顺序表

二、顺序表的分类

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

三、动态顺序表的实现

实现最基本的增删查改功能

（1）增

（2）删

（3）查

（4）改

（5）最后不要忘记销毁创建的空间

---

一、什么是顺序表

顺序表是一种以数组为基础的结构，对数组进行封装，实现常用的增删改查等操作的。

二、顺序表的分类

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

（1）静态顺序表：使用定长数组来存储元素

//静态顺序表
#define N 10typedef int SLDateType;
typedef struct SeqList
{SLDateType arr[N];int size;//有效元素个数
}SL;

使用宏来定义一个常量，作为数组的长度

结构体中包括两个部分：定长数组和记录数组中有效元素个数的变量

缺点：空间是定死的，给多了浪费，给少了不够用

（2）动态顺序表：按需申请空间，减少空间浪费

//动态顺序表
typedef int SLDateType;typedef struct SeqList
{SLDateType* arr;int capacity;//当前内存大小int size;//有效元素个数
}SL;

结构体中包含三个部分：分别是数组指针、当前数组的大小、有效元素个数

三、动态顺序表的实现

实现最基本的增删查改功能

（1）增

//将判断空间是否足够封装为一个函数
void SLCheckCapcity(SL * ps)
{if (ps->capcity == ps->size){//判断capcity是否为0int newcapcity = ps->capcity == 0 ? 4 : 2 * ps->capcity;//使用realloc进行扩容SLtypeDate* tmp = (SLtypeDate*)realloc(ps->arr, newcapcity * sizeof(SLtypeDate));//由于realloc是有可能不成功的，所以要进行判断，并且不能直接赋值给结构体，避免原数据丢失if (tmp == NULL){perror("realloc");exit(1);}ps->arr = tmp;ps->capcity = newcapcity;}
}
void SLPushBack(SL*ps, SLtypeDate x)
{assert(ps);//插入数据要先判断内存够不够 相等则说明内存不够SLCheckCapcity(ps);ps->arr[ps->size++] = x;
}
//头插
void SLPushFront(SL* ps, SLtypeDate x)
{assert(ps);SLCheckCapcity(ps);for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}
//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLtypeDate x)
{assert(ps);//因为是之前所以可以等于assert(pos >= 0 && pos <= ps->size);SLCheckCapcity(ps);for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}

（2）删

//删除->尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);ps->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];}ps->size--;
}
//指定位置删除
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);assert(ps->size);for (int i = pos; i < ps->size; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

（3）查

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

（4）改

//修改
void SLModify(SL* ps, int pos, SLtypeDate x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->arr[pos] = x;
}

（5）最后不要忘记销毁创建的空间

//销毁
void SLDestory(SL* ps)
{if (ps->arr){free(ps->arr);}ps->size = 0;ps->capcity = 0;
}