【数据结构与算法】：带你手搓顺序表（C/C++篇）-阿里云开发者社区

一、顺序表

1.1 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

245098735341e4bfc3808f360a294f58_43938dda41b146aeb35df6d163af843d.png

二、顺序表

8ec3e333ea6ea6a365935e018fdb2a41_511ff7bde5a542b1a2b3fa2e5e7c31e8.png

2.1 概念及结构

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

顺序表一般可以分为：

静态顺序表：使用定长数组存储。

typedef int SLDataType;//便于类型的改动
#define N 100
// 静态顺序表
typedef struct SeqList
{
  SLDataType arr[N];  // 定长数组
  int size; //  有效数据个数
}SL;

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费

动态顺序表：使用动态开辟的数组存储。

typedef int SLDataType;//便于类型的改动
// 动态顺序表
typedef struct SeqList
{
  SLDataType* arr;
  int size;  // 有效数据的个数
  int capacity;  // 空间大小
}SL;

.2 实现方法

首先要创建三个文件，创建一个SeqList.h的头文件用于函数的声明， SeqList.c用于函数的实现，test.c用于代码测试

SeqList.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 定义顺序表的结构
typedef int SLDataType;  //便于类型的改动
//#define N 100
 静态顺序表
//typedef struct SeqList
//{
//  SLDataType arr[N];  // 定长数组
//  int size; //  有效数据个数
//}SL;
// 动态顺序表
typedef struct SeqList
{
  SLDataType* arr;
  int size;  // 有效数据的个数
  int capacity;  // 空间大小
}SL;
// 顺序表的初始化
void SLInit(SL* ps);
// 顺序表的销毁
void SeqListDestory(SL* ps);
// 顺序表的打印
void SLPrint(SL s);
// 扩容
void SLCheckCapacity(SL* ps);
// 顺序表的增删查改等接口函数
// 尾插法
void SeqListPopBack(SL* ps, SLDataType x);
// 头插法
void SLPushFront(SL* ps, SLDataType x);
// 尾部删除
void SLPopBack(SL* ps);
// 头部删除
void SLPopFront(SL* ps);
// 指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x);
// 指定位置删除
void SLErase(SL* ps, int pos);
// 顺序表的查找
int SLFind(SL* ps, SLDataType x);
// 顺序表元素的索引
int SLIndex(SL* ps, int index);
// 顺序表元素的修改
void SLMod(SL* ps, int index, SLDataType x);

SeqList.c文件

1. 顺序表的初始化

// 顺序表的初始化
void SLInit(SL* ps)
{
  ps->arr = NULL;
  ps->size = ps->capacity = 0;  // 开始空间为0
 }

初始化的时候，可以选择申请原始空间大小，也可以选择不申请空间。

2. 顺序表的销毁

// 顺序表的销毁
void SeqListDestory(SL* ps)
{
  if (ps->arr) // arr不为空，释放空间
  {
    free(ps->arr);
  }
  ps->arr = NULL;  // 置为空指针
  ps->size = ps->capacity = 0;
}

代码测试：

test.c文件

#include"SeqList.h"
void SLTest01()
 {
  SL sl;
  // 初始化
  SLInit(&sl);
  // 销毁
  SeqListDestory(&sl);
}
int main()
{
  SLTest01();
  return 0;
}

3. 扩容

注意：每次扩容新空间不能太大，也不能太小，太大容易造成空间浪费，太小则会导致频繁扩容而影响程序效率。

这里采用的是成倍扩容：

// 扩容
void SLCheckCapacity(SL* ps)
{
  if (ps->capacity == ps->size)
  {
    // 申请空间
    // 三目运算来判断原始空间是否为0
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;   // 如果为0，默认申请4个空间大小
    SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
    if (tmp == NULL)  // 申请失败
    {
      perror("realloc");
      return 1;
    }
    // 申请成功
    ps->arr = tmp;
    ps->capacity = newCapacity;
  }
}

4. 尾部插入/尾部删除

// 尾插法
void SeqListPopBack(SL* ps, SLDataType x)
{
  assert(ps);  // 判断传入的是否是空指针 
  // 插入数据前先查看空间够不够
  SLCheckCapacity(ps);
  // ps->arr[ps->size] = x;
  // ++ps->size;  // 插入数据之后size要加1
  ps->arr[ps->size++] = x;
}

// 尾部删除
void SLPopBack(SL* ps)
{
  assert(ps);  // 判断传入的是否是空指针
  assert(ps->size); // 确保数据域不为空
  --ps->size;  // 删除最后一个元素
}

5. 头部插入/头部删除

// 头插法
void SLPushFront(SL* ps, SLDataType x)
{
  assert(ps);  // 判断传入的是否是空指针
  // 先判断空间是否足够
  SLCheckCapacity(ps);
  // 先让顺序表中的元素整体往后挪动一位
  for (int i = ps->size; i > 0; i--)
  {
    ps->arr[i] = ps->arr[i - 1]; // arr[1] = arr[0];
  }
  ps->arr[0] = x; // 将元素插在下标为0的位置
  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;  // 删除后大小减一
}

6. 指定位置插入/删除

1. 元素指定位置插入

顺序表的元素插入，就是指给定一个索引和一个元素，将这个元素插入到对应的索引位置上，这个位置以后的所有元素都要往后移动一个位置。

2. 元素指定位置删除

顺序表的元素删除，就是指给定一个索引，将这个索引上的元素删除，并且把这个索引位置以后的所有元素都往前移动一个位置。

// 指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
  assert(ps);  // 判断传入的是否是空指针
  assert(pos >= 0 && pos <= ps->size);
  // 先判断空间是否足够，不够就扩容
  SLCheckCapacity(ps);
  // 让pos及其之后的元素往后挪
  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);  // 判断传入的是否是空指针
  assert(pos >= 0 && pos < ps->size);
  // pos之后的元素往前挪
  for (int i = pos;i < ps->size - 1; i++)
  {
    ps->arr[i] = ps->arr[i + 1];
  }
  // 删除元素后，数据域大小要减一
  ps->size--;
}

7. 顺序表的查找

顺序表的元素查找，是指在顺序表中查找指定元素是否存在，如果存在则返回该元素的索引，否则返回-1。由于需要遍历整个顺序表进行元素对比，所以查找的时间复杂度为 O(n) 。

元素查找的顺序：

第1步、遍历整个顺序表，对顺序表中的每个元素，和指定元素进行比较，如果相等则返回当前的索引；

第2步、如果遍历完所有的顺序表元素，都没有找到相等的元素，则返回 -1；

// 顺序表的查找
int SLFind(SL* ps, SLDataType x)
{
  assert(ps);  // 判断传入的是否是空指针
  for (int i = 0; i < ps->size; i++)
  {
    if (ps->arr[i] == x)  // 找到了
      return i;
  }
  // 未找到
  return -1;
}

8. 顺序表元素的索引

顺序表的元素索引，是指给定一个索引值，通过下标访问，直接在顺序表中获取元素的值，时间复杂度 O(1)。

// 顺序表元素的索引
int SLIndex(SL* ps, int index)
{
  assert(index >= 0 && index < ps->size);
  return ps->arr[index];
}

9. 顺序表元素的修改

顺序表的元素修改是指将顺序表中指定位置的元素更新为新的值。

9. 顺序表元素的修改
顺序表的元素修改是指将顺序表中指定位置的元素更新为新的值。
在这里插入图片描述

10. SeqList.c完整代码

#include"SeqList.h"

// 顺序表的初始化
void SLInit(SL* ps)
{
  ps->arr = NULL;
  ps->size = ps->capacity = 0;  // 开始空间为0
 }

// 顺序表的销毁
void SeqListDestory(SL* ps)
{
  if (ps->arr) 
  {
    free(ps->arr);
  }
  ps->arr = NULL;
  ps->size = ps->capacity = 0;
}

// 打印
void SLPrint(SL s)
{
  for (int i = 0; i < s.size; i++)
  {
    printf("%d ", s.arr[i]);
  }
  printf("\n");
}

// 扩容
void SLCheckCapacity(SL* ps)
{
  if (ps->capacity == ps->size)
  {
    // 申请空间
    // 三目运算来判断原始空间是否为0
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;   // 如果为0，默认申请4个空间大小
    SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
    if (tmp == NULL)  // 申请失败
    {
      perror("realloc");
      return 1;
    }
    // 申请成功
    ps->arr = tmp;
    ps->capacity = newCapacity;
  }
}
// 尾插法
void SeqListPopBack(SL* ps, SLDataType x)
{
  assert(ps);  // 判断传入的是否是空指针 
  // 插入数据前先查看空间够不够
  SLCheckCapacity(ps);
  // ps->arr[ps->size] = x;
  // ++ps->size;  // 插入数据之后size要加1
  ps->arr[ps->size++] = x;
}

// 头插法
void SLPushFront(SL* ps, SLDataType x)
{
  assert(ps);  // 判断传入的是否是空指针
  // 先判断空间是否足够
  SLCheckCapacity(ps);
  // 先让顺序表中的元素整体往后挪动一位
  for (int i = ps->size; i > 0; i--)
  {
    ps->arr[i] = ps->arr[i - 1]; // arr[1] = arr[0];
  }
  ps->arr[0] = x; // 将元素插在下标为0的位置
  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, SLDataType x)
{
  assert(ps);  // 判断传入的是否是空指针
  assert(pos >= 0 && pos <= ps->size);
  // 先判断空间是否足够，不够就扩容
  SLCheckCapacity(ps);
  // 让pos及其之后的元素往后挪
  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);  // 判断传入的是否是空指针
  assert(pos >= 0 && pos < ps->size);
  // pos之后的元素往前挪
  for (int i = pos;i < ps->size - 1; i++)
  {
    ps->arr[i] = ps->arr[i + 1];
  }
  // 删除元素后，数据域大小要减一
  ps->size--;
}

// 顺序表的查找
int SLFind(SL* ps, SLDataType x)
{
  assert(ps);  // 判断传入的是否是空指针
  for (int i = 0; i < ps->size; i++)
  {
    if (ps->arr[i] == x)  // 找到了
      return i;
  }
  // 未找到
  return -1;
}

// 顺序表元素的索引
int SLIndex(SL* ps, int index)
{
  assert(index >= 0 && index < ps->size);
  return ps->arr[index];
}

// 顺序表元素的修改
void SLMod(SL* ps, int index, SLDataType x)
{
  assert(ps); // 判断传入的是否是空指针
  assert(index >= 0 && index < ps->size);
  ps->arr[index] = x;  // 指定下标元素修改
}

【数据结构与算法】：带你手搓顺序表（C/C++篇）