顺序表的实现（数据结构）——C语言

目录

1.结构与概念

2.分类

3 动态顺序表的实现

SeqList.h

SeqList.c

创建SLInit：

尾插SLPushBack以及SLCheak（检查空间是否足够）：

头插SLPushFront：

尾删SLPopBack

头删SLPopFront

查找指定元素SLFind

指定位置插入SLInsert

指定位置删除SLEarse

打印元素SLPrint

销毁SLDestory

整体代码：

SeqList.h

SeqList.c

---

1.结构与概念

概念：顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储。顺序表的底层其实就是顺序表，只是将数组进行了了一下包装。

2.分类

静态顺序表：使⽤定⻓数组存储元素；动态顺序表：空间不够用时，可以增加空间，静态顺序表缺陷：空间给少了不够⽤，给多了造成空间浪费，所以这里实现的是动态顺序表。

3 动态顺序表的实现

这里先还是创建三个文件，即test.c,SeqList.c,SeqList.h，分别是测试文件，顺序表的头文件，顺序表的函数实现文件，首先要在头文件中定义顺序表的结构体类型，结构体中有定义的数组类型，数据个数，以及空间大小，这里的数据类型DataType，在前面可以直接通过更改typedef后面直接修改整个的数据类型，这里以int类型为例：

typedef int DataType;typedef struct SeqList
{DataType* arr;int size ;int capacity ;
}SL;

还有就是头文件中肯定要包含各种头文件，这样在其他文件中直接包含“SeqList.h”就可以直接是用了，以及后面要实现的增删查改的操作的的函数头文件都包含在内：

SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int DataType;typedef struct SeqList
{DataType* arr;int size ;int capacity ;
}SL;void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
void SLCheak(SL* ps);void SLPushback(SL* ps,DataType x);
void SLPushFront(SL* ps, DataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
void SLInsert(SL* ps, int pos,DataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, DataType x);

SeqList.c

在这个文件中就是实现增删查改的各种函数，首先第一个为创建一个顺序表

创建SLInit：

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

初始情况下，数组指向空，空间大小，数据个数为0；还有注意这里要传一级指针，因为这里要使ps发生改变，后面的函数实现基本都要传一级指针；

尾插SLPushBack以及SLCheak（检查空间是否足够）：

void SLCheak(SL* ps)
{if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;DataType* tmp = (DataType*)realloc(ps->arr, newcapacity*sizeof(DataType));if (tmp == NULL){perror("realloc fail");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}
}void SLPushback(SL* ps, DataType x)
{assert(ps);SLCheak(ps);ps->arr[ps->size] = x;ps->size++;
}

因为这里实现插入操作，第一考虑的是，空间是否足够可以插入，所以这里实现了一个检查空间是否足够的函数SLCheak，如果空间够，就不进行任何操作，如果不够就要申请空间，申请空间每次为上次的两倍，如果是0的话，就附一个初值为4，申请空间时要判断是否申请成功，这里使用realloc函数，申请成功后再给ps；

尾差操作则是先判断ps是否为空后，直接在数组最后一个位置放入x，然后数据个数ps->size再++；

头插SLPushFront：

void SLPushFront(SL* ps, DataType x)
{assert(ps);SLCheak(ps);for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps ->size++;
}

第一步任然是判断ps是否为空，以及空间大小是否足够，因为这里要在第一个位置插入，所以数组整体都要向后移动一位，这里就是一个for循环，为了避免数据被覆盖，从最后一个位置元素先向后移动再依次直到第一个元素被移到第二个位置结束，然后再插入元素x，ps->size再++；

尾删SLPopBack

void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);ps->size--;
}

尾删即从最后删除一个元素，这里可以直接简单化处理，直接将ps->size--,这样就访问不到原本size-1位置的数据，相当于是把最后一个元素删掉了；

头删SLPopFront

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--;
}

头删即从第一个元素删除，这里可以直接将后面的元素依次先前移动一位，直接将第一个元素覆盖，这里要注意循环介质的条件，是ps->size-1，再将ps->size--即可；

查找指定元素SLFind

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

这里就是遍历数组，与x比较，找到就返回就行了；

指定位置插入SLInsert

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

这里和头插有点相似，这里主要注意结束循环是i>pos,就是将pos之后的元素向后移动一位，再在pos位置插入x，元素个数ps->size++；

指定位置删除SLEarse

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

和头删有异曲同工之妙，也是注意循环结束条件是ps->size-1,将pos之后的元素向前移动一位，然后元素个数ps->size--即可；

打印元素SLPrint

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

遍历数组，依次输出即可；

销毁SLDestory

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

将数组置为NULL，以及空间和元素个数都置为0；

整体代码：

SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int DataType;typedef struct SeqList
{DataType* arr;int size ;int capacity ;
}SL;void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
void SLCheak(SL* ps);void SLPushback(SL* ps,DataType x);
void SLPushFront(SL* ps, DataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
void SLInsert(SL* ps, int pos,DataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, DataType x);

SeqList.c

#include"SeqList.h"void SLInit(SL* ps)
{ps->arr = NULL;ps->size = 0;ps->capacity = 0;
}void SLDestroy(SL* ps)
{if (ps->arr != NULL){ps->arr = NULL;}ps->size = 0;ps->capacity = 0;
}void SLCheak(SL* ps)
{if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;DataType* tmp = (DataType*)realloc(ps->arr, newcapacity*sizeof(DataType));if (tmp == NULL){perror("realloc fail");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}
}void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}void SLPushback(SL* ps, DataType x)
{assert(ps);SLCheak(ps);ps->arr[ps->size] = x;ps->size++;
}void SLPushFront(SL* ps, DataType x)
{assert(ps);SLCheak(ps);for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps ->size++;
}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 SLInsert(SL* ps, int pos, DataType x)
{assert(ps && pos < ps->size && pos >= 0);SLCheak(ps);for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}void SLErase(SL* ps, int pos)
{assert(ps && pos < ps->size && pos >= 0);for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}int SLFind(SL* ps, DataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}