顺序表的概念与结构

概念：顺序表就是在内存中申请一段连续的空间来存放我们需要存放的数据，一般使用数组的方法来实现。
那顺序表跟数组有什么区别？
他们的本质是一样的，都是使用数组来存放数据。
顺序表相当于数组的加工与包装。
就好比我们下馆子吃的清炒西兰花，在米其林餐厅就会通过摆盘与封装，改个名字叫绿野仙踪，使其看起来更加高大上。
但是我们不能说顺序表就是数组，他们是不等价的，只能说底层结构采用的是数组的方式来实现我们的目的。

静态顺序表

我们学习C语言，肯定知道静态内存或者动态内存。
那静态顺序表也一样，就是利用定长数组来存放数据，它的空间在确定之后是不能随便更改的。

#ifndef __SEQLIST_H_//防止预编译重复个定义
#define __SEQLIST_H_
typedef int SLDateType//给数据类型重定义，方便后面更改数据类型
typedef struct SeqList
{SLDateType arr[10];//变长数组int size;//数组内有效元素个数
};SL
#endif

动态顺序表

之前C语言中学习过动态内存管理，里面有个函数叫realloc：
它的作用是给动态申请的内存追加空间，动态顺序表就可以通过他来实现。

#ifndef __SEQLIST_H_//防止预编译重复个定义
#define __SEQLIST_H_
typedef int SLDateType//给数据类型重定义，方便后面更改数据类型
typedef struct SeqList
{SLDateType* arr;//这里改为指针，动态内存开辟成功后首地址给他int size;//数组内有效元素个数
};SL
#endif

动态顺序表的基本只是就介绍完了，接下来我们来实现一下动态顺序表的功能。

动态顺序表的实现

用SeqList,h头文件声明一些动态顺序表的功能函数，SeqList.c文件实现功能函数的编写，最后在test.c文件里面测试编译。

SeqList.h的创建

#ifndef __SEQLIST_H_//防止预编译重复个定义
#define __SEQLIST_H_
typedef int SLDateType//给数据类型重定义，方便后面更改数据类型
typedef struct SeqList//创建一个结构体来存放动态顺序表的起始地址
//有效数据个数以及现在的内存大小
{SLDateType* arr;//这里改为指针，动态内存开辟成功后首地址给他int capacity//动态顺序表的内存大小int size;//数组内有效元素个数
};SLvoid LS_Init(SL* ps);//初始化void LS_Destry(SL* ps);//销毁动态内存void SL_CheckCapacity(SL* ps);//检查动态内存是否已满void SL_Print(SL* ps);//打印内存有效数据void SL_PushBack(SL* ps, typedate x);//在末尾放置void SL_PushFront(SL* ps, typedate x);//在第一个位置放置void SL_Inser(SL* ps, typedate x, int pos);//在指定下标位置插入数据void SL_PopBack(SL* ps);//删除最后一位数据void SL_PopFront(SL* ps);//删除第一位数据void SL_Deser(SL* ps, int pos);//删除指定位置数据void Find(SL* ps, typedate x);//寻找某个数据的位置#endif

初始化动态顺序表（LS_Init）

void LS_Init(SL* ps)
{ps->arr=NULL;//给起始地址设置为空指针ps->size=ps->capacity=0;//数据有效个数与空间大小设为0；
}

动态顺序表的销毁（LS_Destry）

void LS_Destry(SL* ps)
{assert(ps->arr);//检查arr是否为NULLfree(ps->arr);//释放动态开辟的空间ps->arr=NULL;ps->size=ps->capacity=0;//数据有效个数与空间大小设为0；
}

检查动态内存空间是否已满（SL_CheckCapacity）

这个地方我们要用到三目操作符，防止有的人忘记或者没接触过，再介绍一下它的用法：

int m = 表达式?x:y;

当表达式成立时，就将x的值赋值给m，表达式不成立就将y的值赋值给m。

这里我们用SL_CheckCapacity满足检查内存是否够用以及第一次创建内存的操作。

void SL_CheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newdate = ps->capacity == 0 ? 4 : 2 * ps->capacity;typedate * tmp=(typedate*)realloc(ps->arr, newdate * sizeof(typedate));assert(tmp);ps->arr = tmp;ps->capacity = newdate;}
}

如果数据有效个数与内存空间大小一致，那就代表空间使用完了，就需要申请空间，所以判断一下条件是否成立。
成立后如果内存大小为0，就说明是第一次创建，我们给newdate 赋值为4，在realloc函数中创建，如果不是第一次创建，就追加一倍的空间。

动态顺序表打印有效数据（SL_Print）

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

在末尾存放数据（SL_PushBack）

void SL_PushBack(SL* ps,typedate x)//在末位置添加数据
{assert(ps);SL_CheckCapacity(ps);ps->arr[ps->size++] = x;//放完数据后让数据有效个数+1
}

在起始位置添加有效数据（SL_PushFront）

要在第一个位置存放数据而不覆盖其他数据，就需要将数据整体后移一位。
根据最后一次移位条件：把下标为0的位置移到下标为1的位置可得for循环判定条件i>0,这样i最小是1。

void SL_PushFront(SL* ps, typedate x)//在起始位置添加有效数据
{assert(ps);SL_CheckCapacity(ps);for (int i =ps->size ; i>0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}

在指定位置添加数据（SL_Inser）

这个与在起始位置存放数据类似，将指定位置后面的数据后移一位即可。

void SL_Inser(SL* ps, typedate x,int pos)//在指定位置添加数据
{assert(ps);assert(pos >= 0 && pos <= ps->size);//保证存放的位置在开辟的空间内部SL_CheckCapacity(ps);for (int i = ps->size; i>pos; i--){ps->arr[i] = ps->arr[i - 1];  }ps->arr[pos] = x;ps->size++;
}

删除最后一位数据（SL_PopBack）

我们访问数据是基于有效数据个数访问的，直接将有效数据-1，这样我们便认为最后一个数据不是有效数据，就不会访问，跟删除效果一样。

void SL_PopBack(SL* ps)//删除最后一位数据
{assert(ps);ps->size--;
}

在起始位置删除数据（SL_PopFront）

我们将数据整体前移一位，让有效数据-1即可。

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

删除任意位置的数据（SL_Deser）

这个与在起始位置删除数据一样，将指定位置后面的数据往前移一位即可。

void SL_Deser(SL* ps,int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);for(int i = pos; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

寻找内存中的某个数据的位置（Find）

void Find(SL* ps, typedate x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){printf("找到了，下标是%d\n", i);return 0;}}printf("找不到\n");
}

测试顺序表（test.c）

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"int main()
{SL s;LS_Init(&s);//初始化SL_PushBack(&s, 1);//末尾放置SL_PushBack(&s, 2);//末尾放置SL_PushBack(&s, 3);//末尾放置SL_PushFront(&s, 0);//起始放置SL_Print(&s);//打印，结果应该是0 1 2 3SL_Inser(&s, 9,2);//在下标2的位置存放9SL_Print(&s);//结果：0 1 9 2 3SL_PopBack(&s);//删除末位SL_Print(&s);//结果： 0 1 9 2SL_PopFront(&s);//删除起始位SL_Print(&s);// 1 9 2SL_Deser(&s, 1);//删除下表1的数据SL_Print(&s);//1 2Find(&s, 2);//寻找2的下标LS_Destry(&s);//下标应该是1return 0;
}

---