一.顺序表介绍

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

(1)静态顺序表：使用定长数组存储，适用于确定知道需要存多少数据的场景

#define N 100
typedef int SeqListDataType;
typedef struct SeqList
{
SLDataType array[N]; // 定长数组
size_t size; // 有效数据的个数
}SeqList;

(2)动态顺序表：使用动态开辟的数组存储，可根据需要动态的分配空间大小。

typedef struct SeqList
{
SLDataType* array; // 指向动态开辟的数组
size_t size ; // 有效数据个数
size_t capicity ; // 容量空间的大小
}SeqList;

二.动态顺序表增删查功能实现

现在Seqlist.h里对相关功能的函数，结构体进行声明，和类型的重定义

#pragma once
//C库函数的头文件声明
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//自定义顺序表元素的类型
typedef int SeqListDateType;
//顺序表的结构体
typedef struct SeqList
{
  SeqListDateType* data;
  size_t size;
  size_t capacity;
}SL;
//基本的增删查改接口
//顺序表的初始化
void SeqListInit(SL* ps);
//顺序表销毁
void SqeListDestory(SL* ps);
//顺序表打印
void SeqListPrint(SL* ps);
//顺序表在pos位置插入x
void SeqListInsert(SL* ps, size_t pos, SeqListDateType x);
//顺序表删除pos位置的值
void SeqListErase(SL* ps, size_t pos);
//顺序表尾插
void SeqListPushBack(SL* ps, SeqListDateType x);
//顺序表尾删
void SeqListPopBack(SL* ps);
//顺序表头插
void SeqListPushFront(SL* ps, SeqListDateType x);
//顺序表头删
void SeqListPopFront(SL* ps);
//顺序表查找(找到了返回下标，找不到返回-1)
int SeqListFind(SL* ps, SeqListDateType x);

（1）顺序表的初始化:对数组开辟4个容量的空间，有效数据为0，容量为4

void SeqListInit(SL* ps)
{
  assert(ps);
  ps->data = (SeqListDateType*)malloc(4 * sizeof(SeqListDateType));
  if (ps->data == NULL)
  {
  printf("申请内存失败\n");
  exit(-1);
  }
  ps->size = 0;
  ps->capacity = 4;
}

（2）对开辟后的空间销毁

void SqeListDestory(SL* ps)
{
    //断言，保证指针的有效性，防止野指针
  assert(ps);
  free(ps->data);
  ps->data = NULL;
}

（3）打印顺序表的内容

void SeqListPrint(SL* ps)
{
    //断言，保证指针的有效性，防止野指针
  assert(ps);
  for (size_t i = 0; i < ps->size; i++)
  {
  printf("%d ", ps->data[i]);
  }
}

（4）检查空间，如果满了，进行原来空间1倍的增容；没满就啥都不干（这个函数只在SeqList.c内部使用，使用static修饰，SeqList.h也不用声明这个函数）

static void CheckCapacity(SL* ps)
{
    //断言，保证指针的有效性，防止野指针
  assert(ps);
  if (ps->size == ps->capacity)
  {
  ps->capacity *= 2;
  ps->data = (SeqListDateType*)realloc(ps->data, ps->capacity * sizeof(SeqListDateType));
  if (ps->data == NULL)
  {
    printf("增容失败\n");
    exit(-1);
  }
  }

（5）任意位置（position）插入数据

void SeqListInsert(SL* ps, size_t pos, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针，和保证输入的位置正确
  assert(ps&& pos <= ps->size);
  CheckCapacity(ps);//插入数据之前先检查空间是否足够
  //把pos位置后面的数据往后移动
  int end = (int)ps->size - 1;
  while ((int)pos <= end)
  {
  ps->data[end + 1] = ps->data[end];
  end--;
  }
  //在pos上插入数据
  ps->data[pos] = x;
  //插入之后有效数据加一
  ps->size++;
}

（6）任意位置（position）删除数据

void SeqListErase(SL* ps, size_t pos)
{
  //断言，保证指针的有效性，防止野指针，和保证输入的位置正确
  assert(ps&&pos < ps->size);
  //把pos位置后面的数据往前移动
  size_t start = pos;
  while ((int)start <= (int)ps->size - 2)
  {
  ps->data[start] = ps->data[start + 1];
  start++;
  }
  //删除之后有效数据减一
  ps->size--;
}

（7）尾部插入一个数据

void SeqListPushBack(SL* ps, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  CheckCapacity(ps);//插入数据之前先检查空间是否足够
  //直接在最后一个位置插入数据
  ps->data[ps->size] = x;
  //插入之后有效数据加一
  ps->size++;
}

（8）尾部删除一个数据

void SeqListPopBack(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  //直接有效数据减一，不会打印出来最后一个数据
  ps->size--;
}

（9）头部插入一个数据

void SeqListPushFront(SL* ps, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  CheckCapacity(ps);//插入数据之前先检查空间是否足够
  //把原来的所有数据往后移动，腾出第一个位置来
  size_t end = ps->size - 1;
  while ((int)end >= 0)
  {
  ps->data[end + 1] = ps->data[end];
  end--;
  }
  //头插
  ps->data[0] = x;
  //有效数据加一
  ps->size++;
}

（10）头部删除一个数据

void SeqListPopFront(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  //把第二个数据开始所有的数据往前移动
  for (size_t i = 0; i < ps->size - 1; i++)
  {
  ps->data[i] = ps ->data[i + 1];
  }
  //有效数据减一
  ps->size--;
}

（11）查找数据（找到了返回下标，找不到返回-1）

int SeqListFind(SL* ps, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  //根据下标遍历所有数据来查找
  for (size_t i = 0; i < ps->size; i++)
  {
  if (ps->data[i] == x)
  {
    //找到了就返回下标
    return i;
  }
  }
  //没找到就返回-1
  return -1;
}

三.完整代码

ps:完整代码包含在三个文件里

（1）SeqList.h

#pragma once
//C库函数的头文件声明
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//自定义顺序表元素的类型
typedef int SeqListDateType;
//顺序表的结构体
typedef struct SeqList
{
  SeqListDateType* data;
  size_t size;
  size_t capacity;
}SL;
//基本的增删查改接口
//顺序表的初始化
void SeqListInit(SL* ps);
//顺序表销毁
void SqeListDestory(SL* ps);
//顺序表打印
void SeqListPrint(SL* ps);
//顺序表在pos位置插入x
void SeqListInsert(SL* ps, size_t pos, SeqListDateType x);
//顺序表删除pos位置的值
void SeqListErase(SL* ps, size_t pos);
//顺序表尾插
void SeqListPushBack(SL* ps, SeqListDateType x);
//顺序表尾删
void SeqListPopBack(SL* ps);
//顺序表头插
void SeqListPushFront(SL* ps, SeqListDateType x);
//顺序表头删
void SeqListPopFront(SL* ps);
//顺序表查找(找到了返回下标，找不到返回-1)
int SeqListFind(SL* ps, SeqListDateType x);

（2）SeqList.c

#include"SeqList.h"
void SeqListInit(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  ps->data = (SeqListDateType*)malloc(4 * sizeof(SeqListDateType));
  if (ps->data == NULL)
  {
  printf("申请内存失败\n");
  exit(-1);
  }
  ps->size = 0;
  ps->capacity = 4;
}
void SqeListDestory(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  free(ps->data);
  ps->data = NULL;
}
void SeqListPrint(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  for (size_t i = 0; i < ps->size; i++)
  {
  printf("%d ", ps->data[i]);
  }
}
//检查空间，如果满了，进行增容
static void CheckCapacity(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  if (ps->size == ps->capacity)
  {
  ps->capacity *= 2;
  ps->data = (SeqListDateType*)realloc(ps->data, ps->capacity * sizeof(SeqListDateType));
  if (ps->data == NULL)
  {
    printf("增容失败\n");
    exit(-1);
  }
  }
}
void SeqListInsert(SL* ps, size_t pos, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针，和保证输入的位置正确
  assert(ps&& pos <= ps->size);
  CheckCapacity(ps);//插入数据之前先检查空间是否足够
  //把pos位置后面的数据往后移动
  int end = (int)ps->size - 1;
  while ((int)pos <= end)
  {
  ps->data[end + 1] = ps->data[end];
  end--;
  }
  //在pos上插入数据
  ps->data[pos] = x;
  //插入之后有效数据加一
  ps->size++;
}
void SeqListErase(SL* ps, size_t pos)
{
  //断言，保证指针的有效性，防止野指针，和保证输入的位置正确
  assert(ps&&pos < ps->size);
  //把pos位置后面的数据往前移动
  size_t start = pos;
  while ((int)start <= (int)ps->size - 2)
  {
  ps->data[start] = ps->data[start + 1];
  start++;
  }
  //删除之后有效数据减一
  ps->size--;
}
void SeqListPushBack(SL* ps, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  CheckCapacity(ps);//插入数据之前先检查空间是否足够
  //直接在最后一个位置插入数据
  ps->data[ps->size] = x;
  //插入之后有效数据加一
  ps->size++;
}
void SeqListPopBack(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  //直接有效数据减一，不会打印出来最后一个数据
  ps->size--;
}
void SeqListPushFront(SL* ps, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  CheckCapacity(ps);//插入数据之前先检查空间是否足够
  //把原来的所有数据往后移动，腾出第一个位置来
  size_t end = ps->size - 1;
  while ((int)end >= 0)
  {
  ps->data[end + 1] = ps->data[end];
  end--;
  }
  //头插
  ps->data[0] = x;
  //有效数据加一
  ps->size++;
}
void SeqListPopFront(SL* ps)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  //把第二个数据开始所有的数据往前移动
  for (size_t i = 0; i < ps->size - 1; i++)
  {
  ps->data[i] = ps ->data[i + 1];
  }
  //有效数据减一
  ps->size--;
}
int SeqListFind(SL* ps, SeqListDateType x)
{
  //断言，保证指针的有效性，防止野指针
  assert(ps);
  //根据下标遍历所有数据来查找
  for (size_t i = 0; i < ps->size; i++)
  {
  if (ps->data[i] == x)
  {
    //找到了就返回下标
    return i;
  }
  }
  //没找到就返回-1
  return -1;
}

（3）test.c(对顺序表进行测试)

#include"SeqList.h"
int main()
{
  //定义一个顺序表变量s
  SL s = { 0 };
  //顺序表接口功能的测试
  SeqListInit(&s);
  SeqListInsert(&s,0,1);
  SeqListInsert(&s, 1, 2);
  SeqListInsert(&s, 2, 3);
  SeqListErase(&s, 1);
  SeqListPrint(&s);
  printf("\n");
  return 0;
}

四.动态顺序表总结

1.可动态增长的数组

2.数据在数组中存储时必须是连续的

缺点：

1.中间或头部的插入删除很慢，需要挪动数据。时间复杂度为O（N）

2.空间不够时，增容会有一定的时间消耗和空间浪费

优点：

1.可以随机访问数据

2.cpu在缓存中拿数据时命中率高

【数据结构】实现顺序表的增删查改

一.顺序表介绍

二.动态顺序表增删查功能实现

三.完整代码

四.动态顺序表总结

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】实现顺序表的增删查改

一.顺序表介绍

二.动态顺序表增删查功能实现

三.完整代码

四.动态顺序表总结

热门文章

最新文章

相关课程

相关电子书