[数据结构与算法]数据结构顺序表介绍与基本操作（C语言）实现

顺序表的概念

? ? ???顺序表是用物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表可分为：

• 静态顺序表：使用定长数组存储元素。
  • 动态顺序表：使用动态开辟的数组存储元素。

?以下为动态顺序表的实现

????????首先要想实现顺序表上数据的增删查改?，我们需要接口函数来实现。

?声明接口函数

typedef int SLDateType; //重命名int
typedef struct SeqList
{
	SLDateType *a;
	size_t size;  //顺序表所含数据的个数
	size_t Capacity;  //顺序表所能存储数据的的大小

}SL;
//接口函数

//初始化顺序表
void SeqListInit(SL* ps);
//销毁顺序表
void SeqListDestory(SL*ps);
//打印顺序表
void SeqlistPrint(SL*ps);
//尾加
void SeqListPushBack(SL*ps, SLDateType x);
//尾删
void SeqListPopBack(SL*ps);
//前加
void SeqlisrPushFront(SL*ps, SLDateType x);
//前删
void SeqListPopFront(SL*ps);
// 顺序表查找
int SeqListFind(SL* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SL* ps, size_t pos);

?接口函数的定义

?初始化顺序表：

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

?销毁顺序表：

void SeqListDestory(SL*ps)
{
    free(ps->a);
    ps->a=NULL;
    ps->size = ps->Capacity = 0;
}

打印顺序表：

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

(在进行尾加之前需要检查是否有空间)

检查空间（没有就扩容）：

void SeqListCheckCapacity(SL*ps)
{
    if(ps->size == ps->Capacity)
    {
        int newcapacity = ps->Capacity == 0 ? 4 : 2 * (ps->Capacity);
        SLDateType *tmp = (SLDateType*)realloc(ps->a, newcapacity*sizeof(SLDateType));
        if(tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        ps->a = tmp;
        ps->Capacity = newcapacity;
    }
}

尾加：

void SeqListPushBack(SL*ps,SLDateType x)
{
    SeqListCheckCapacity(ps);//检查是否有空间没有就扩容
    ps->a[ps->size-1] = x;
    ps->size++;
}

尾删：

void SeqListPopBack(SL*ps)
{
    if(ps->size > 0)
    {
        ps->size--;
    }
}
或者暴力一点
void SeqListPopBack(SL*ps)
{
    assert(ps->size > 0);
    ps->size--;   
}

前加：

void SeqListPushFront(SL* ps, SLDatetype 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)
{
    int begin = 1;
    while(begin<=ps->size-1)
    {
        ps->a[begin-1] = ps->a[begin];
        begin++;
    }
    ps->size--;
}

顺序表查找：

int SeqListFind(SL* ps, SLDateType x)
{
    for(int i = 0; i< ps->size; i++)
    {
        if(x == ps->a[i])
        {
            return i;
        }
    }
    return -1;
    
}

顺序表在pos位置插入x:

void SeqListInsert(SL* p, size_t pos, SLDateType x)
{    
    assert(pos >= 0 && pos <= ps->size);
    SeqListCheckCapacity(ps);
    int end = ps->size-1;
    while(pos <= end)
    {
        ps->a[end+1] = ps->a[end];
        end--;
    }
    ps->a[pos] = x;
    ps->size++;
}

顺序表删除pos位置的值：

void SeqListErase(SL*ps, size_t pos)
{
    int end = pos+1;
    assert(pos >= 0 && pos < ps->size);//防止越界访问
    while(end < ps->size)
    {
        ps->a[end-1] = ps->a[end];
        end++;
    }
    ps->size--;
}

如果这个文章对你有用，请给我一个赞，感谢老铁。

?