前言

顺序表作为数据结构中的小小弟，还是很好应付的。说到数据结构，顺序表是我们的向导，它让你明白数据结构到底是干啥的，为啥数据结构这么的重要。

实际上，通讯录的底层就是一个顺序表，里面的增添联系人，删除联系人等一系列操作，都是基于顺序表实现的，这也侧面拖出了数据结构的作用。所以，学好数据结构是必须的。

要是能够自主实现通讯录，我肯定，顺序表学起来会非常的轻松。

初始化顺序表

实现顺序表需要三个文件：一个是.h为后缀的头文件SeqList.h：用来放相关头文件，宏定义，结构体声明，以及函数声明。一个是.c为后缀的C文件SeqList.c：用来实现函数接口。还有一个是.c为后缀的C文件test.c：用来测试代码。我们只要在SeqList.c文件和test.c文件最上面包含一下 SeqList.h文件，整个程序链接就OK了。

下面是所需头文件，宏定义，以及顺序表的定义的代码：

// 防止SeqList.h被重复包含
#pragma once
// 所需头文件：
// 输入输出所需头文件
#include <stdio.h>
// realloc，free所需头文件
#include <stdlib.h>
// 判空所需头文件
#include <stdbool.h>
// assert断言所需头文件
#include <assert.h>
// 初始化容量，每次增容也是增加这个数量
#define INIT_CAPACITY 8
// 这个为顺序表的数据类型
typedef int SLDateType;
// 顺序表
typedef struct SeqList
{
  // a指向一个在堆上的空间（就是顺序表）
  SLDateType* a;
  // 顺序表数据个数
  int size;
  // 顺序表容量
  int capacity;
}SL;  // typedef将struct SeqList重新命名为SL

定义好主体后，首先是对顺序表初始化。可以看到，上面的结构体也就是顺序表里面的成员都是未初始化的，所以第一步就是将他们初始化，这里引出一个初始化函数接口，下面是相关功能代码实现：

// 初始化顺序表
void SLInit(SL* ps)
{
    // 这里断言是防止ps为一个空指针（传个NULL直接暴打）
  assert(ps);
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}

打印顺序表

该接口放在前面实现是为了后面能够更好的测试：通过对顺序表的数据的一个直观的展现，我们可以及时发现某些接口的bug。

顺序表的结构体中定义了一个size，这里size的作用就体现出来了（当然，size的作用很大，不止是这里），我们可以通过size来对顺序表中的数据顺序打印：

// 打印顺序表
void SLPrint(SL* ps)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++) printf("%d ", ps->a[i]);
  printf("\n");
}

检查容量

当我们在顺序表中插入数据时，一定要检查容量够不够用，如果不够的话，再插入数据，就会出现非法访问空间的问题，此时程序会报错，因此这里要扩容。

由于size是统计数据个数的，所以，只要size等于capacity，就说明当前的容量已经满了，需要扩容。由于初始化顺序表时没有分配空间，所以当我们第一次插入数据的时候就要扩容，每次扩容增加的容量大小为INIT_CAPACITY(8)，而每增容一次，capacity就要更新一次。

下面是相关功能代码实现：

// 检查容量
void SLCheckCapacity(SL* ps)
{
  assert(ps);
  if (ps->size == ps->capacity)
  {
    int newcapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity + INIT_CAPACITY;
    // 开始没有空间，其功能相当于malloc
    SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * newcapacity);
    assert(tmp);
    ps->a = tmp;
    ps->capacity = newcapacity;
  }
}

这一步实现后，每次插入数据就要引用该函数检查一下容量。

判空

判空很容易理解，这里如果通讯录为空，返回真，不为空，返回假。

下面是相关功能代码实现：

// 判空
bool SLEmpty(SL* ps)
{
  assert(ps);
  return ps->size == 0;
}

顺序表数据个数

该功能只要返回size就ok啦。

// 顺序表数据个数
int SLSize(SL* ps)
{
  assert(ps);
  return ps->size;
}

尾部插入

尾部插入就是在最末尾插入数据，首先当然是要检查一下容量，然后将要插入的数据插入进去，最后size计数一次，该函数的功能就OK啦。

下面是相关功能代码实现：

void SLPushBack(SL* ps, SLDateType x)
{
  assert(ps);
  SLCheckCapacity(ps);
  ps->a[ps->size++] = x;
}

尾部删除

如果顺序表中没有数据，那还删个啥呢？直接assert暴打，也就是判断一下size是否大于0(判空一下)。
尾部删除实际上只要size减一就可以了，至于删除的那个数据改不改为0，都无所谓，因为打印不会打印到那个数据，还有就是，不能在那个位置释放空间（free）,这是规定不允许的，要有占着茅坑不拉屎的原则。

下面是相关功能代码实现：

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

头部插入

对顺序表头部的操作相比于尾部的操作麻烦的多，主要是因为，顺序表是一段连续的空间，在头部插入或者删除需要挪动后面的数据，这样以来，整个程序的效率也会降低，但这是没办法的，该挪动还是嘚挪动，不然怎么进行操作对吧。（顺序表最明显的缺点）

挪动的时候，只要从后面开始依次将每一个数据向后挪动一位，直到将第一个数据挪动完停止挪动，再将要插入的数据放在头部即可，这里需要注意以下边界问题。

当然size要计数一次，可不敢忘记了。

下面是相关功能代码实现：

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

头部删除

只要是删除就要assert判断是否要暴打。
有了头部插入的经验，头部删除显得游刃有余了，相反的，只要将每个数据向前挪动，也就是依次覆盖即可，最终第一个数据被覆盖的无影无踪。

当然size要减一，可不敢忘记了。

下面是相关功能代码实现：

void SLPopFront(SL* ps)
{
  assert(ps && !SLEmpty(ps));
  for (int i = 0; i < ps->size - 1; i++) ps->a[i] = ps->a[i + 1];
  ps->size--;
}

在pos位置插入数据

首先插入需要检查容量。

在pos位置插入数据，首先对这个pos理解一下：本章的pos不是下标，注意！他不是下标，而是规规矩矩的第几个位置，比如一串数列1，2，3，4，第一个位置就是只1所占的位置，如果要在第一个位置插入，那么1就会到当前的2的位置上去，也就是所谓的第二个位置。所以，这个pos，是以用户角度出发，但我们实现函数的时候要脑子清醒：我们操作的实际上是下标。

同样的，与头插差不多，都是要挪动数据，只不过挪动的数据范围不同，要操作的数的位置也不同，这也就更加要注意边界问题了。

当然，操作完成后，要记得size计数一次噢。

下面是相关功能代码实现：

// 在pos位置插入,pos表示在第几个位置插入，不是下标
void SLInsert(SL* ps, int pos, SLDateType x)
{
  assert(ps);
  SLCheckCapacity(ps);
  for (int i = ps->size; i > pos - 1; i--) ps->a[i] = ps->a[i - 1];
  ps->a[pos - 1] = x;
  ps->size++;
}

有了该函数之后，前面的头插尾插都可以复用这个函数。

删除pos位置的数据

既然是删除，首先就要来一套assert检查看是否要毒打。

删除，就是将pos后面的数据依次往前挪，最终pos这个位置上的数据会被覆盖，因为会挪动数据，依次效率也不是很高。

当然别忘了size减一噢。

下面是相关功能代码实现：

// 删除第pos个数据，pos不是下标，表示删除第几个
void SLErase(SL* ps, int pos)
{
  assert(ps && !SLEmpty(ps) && pos > 0 && pos <= ps->size);
  for (int i = pos - 1; i < ps->size - 1; i++) ps->a[i] = ps->a[i + 1];
  ps->size--;
}

有了该函数后，前面的头删，尾删都可以复用这个函数。

查找数据

查找数据就是遍历一遍顺序表，如果找到了就返回下标加一，没找到就返回-1。

下面是相关功能代码实现：

// 查找数据，返回正常对应位置，不是下标位置, 没找到返回-1
int SLFind(SL* ps, SLDateType val)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
    if (ps->a[i] == val) return i + 1;
  return -1;
}

修改数据

修改数据也是根据pos位置来修改的，传入你想修改的位置，然后传入修改后的新数据，然后直接在pos - 1(下标)位置修改，不需要遍历。

如果传入的pos不正确，直接暴打。
当然也可以先查找，在修改，也就是说，查找数据和修改数据两个接口函数可以一起用。

**下面是相关功能代码实现：**
```c
// 修改数据,修改pos正常对应位置，不是下标
void SLModify(SL* ps, int pos, SLDateType Mval)
{
  assert(ps && pos > 0 && pos <= ps->size);
  ps->a[pos - 1] = Mval;
}

销毁顺序表

由于向堆申请了空间，因此程序结束后需要将空间返还给系统，这里说的粗暴了点，销毁顺序表。

下面是相关功能代码实现：

// 销毁顺序表
void SLDestroy(SL* ps)
{
  assert(ps);
  free(ps->a);
  ps->capacity = 0;
  ps->size = 0;
}

整体代码

SeqList.h

// 防止SeqList.h被重复包含
#pragma once
// 所需头文件：
// 输入输出所需头文件
#include <stdio.h>
// realloc，free所需头文件
#include <stdlib.h>
// 判空所需头文件
#include <stdbool.h>
// assert断言所需头文件
#include <assert.h>
// 初始化容量，每次增容也是增加这个数量
#define INIT_CAPACITY 8
// 这个为顺序表的数据类型
typedef int SLDateType;
// 顺序表
typedef struct SeqList
{
  // a指向一个在堆上的空间（就是顺序表）
  SLDateType* a;
  // 顺序表数据个数
  int size;
  // 顺序表容量
  int capacity;
}SL;  // typedef将struct SeqList重新命名为SL
// 初始化顺序表
void SLInit(SL* ps);
// 打印顺序表
void SLPrint(SL* ps);
// 检查容量
void SLCheckCapacity(SL* ps);
// 尾插 尾删 头插 头删
void SLPushBack(SL* ps, SLDateType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDateType x);
void SLPopFront(SL* ps);
// 在pos位置插入,pos表示在第几个位置插入，不是下标
void SLInsert(SL* ps, int pos, SLDateType x);
// 删除第pos个数据，pos不是下标，表示删除第几个
void SLErase(SL* ps, int pos);
// 查找数据，返回对应位置，不是下标位置, 没找到返回-1
int SLFind(SL* ps, SLDateType val);
// 修改数据
void SLModify(SL* ps, int pos, SLDateType Mval);
// 判空
bool SLEmpty(SL* ps);
// 顺序表数据个数
int SLSize(SL* ps);
// 使用了realloc，在堆上申请了空间，程序结束时要返还空间给系统
// 销毁顺序表
void SLDestroy(SL* ps);

SeqList.c

#include "SeqList.h"
// 初始化顺序表
void SLInit(SL* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}
// 打印顺序表
void SLPrint(SL* ps)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++) printf("%d ", ps->a[i]);
  printf("\n");
}
// 检查容量
void SLCheckCapacity(SL* ps)
{
  assert(ps);
  if (ps->size == ps->capacity)
  {
    int newcapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity + INIT_CAPACITY;
    // 开始没有空间，其功能相当于malloc
    SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * newcapacity);
    assert(tmp);
    ps->a = tmp;
    ps->capacity = newcapacity;
  }
}
// 尾插 尾删 头插 头删
void SLPushBack(SL* ps, SLDateType x)
{
  //assert(ps);
  //SLCheckCapacity(ps);
  //ps->a[ps->size++] = x;
  SLInsert(ps, ps->size + 1, x);
}
void SLPopBack(SL* ps)
{
  //assert(ps && !SLEmpty(ps));
  //ps->size--;
  SLErase(ps, ps->size);
}
void SLPushFront(SL* ps, SLDateType x)
{
  //assert(ps);
  //SLCheckCapacity(ps);
  //for (int i = ps->size; i > 0; i--) ps->a[i] = ps->a[i - 1];
  //ps->a[0] = x;
  //ps->size++;
  SLInsert(ps, 1, x);
}
void SLPopFront(SL* ps)
{
  //assert(ps && !SLEmpty(ps));
  //for (int i = 0; i < ps->size - 1; i++) ps->a[i] = ps->a[i + 1];
  //ps->size--;
  SLErase(ps, 1);
}
// 在pos位置插入,pos表示在第几个位置插入，不是下标
void SLInsert(SL* ps, int pos, SLDateType x)
{
  assert(ps);
  SLCheckCapacity(ps);
  for (int i = ps->size; i > pos - 1; i--) ps->a[i] = ps->a[i - 1];
  ps->a[pos - 1] = x;
  ps->size++;
}
// 删除第pos个数据，pos不是下标，表示删除第几个
void SLErase(SL* ps, int pos)
{
  assert(ps && !SLEmpty(ps) && pos > 0 && pos <= ps->size);
  for (int i = pos - 1; i < ps->size - 1; i++) ps->a[i] = ps->a[i + 1];
  ps->size--;
}
// 查找数据，返回正常对应位置，不是下标位置, 没找到返回-1
int SLFind(SL* ps, SLDateType val)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
    if (ps->a[i] == val) return i + 1;
  return -1;
}
// 修改数据,修改pos正常对应位置，不是下标
void SLModify(SL* ps, int pos, SLDateType Mval)
{
  assert(ps && pos > 0 && pos <= ps->size);
  ps->a[pos - 1] = Mval;
}
// 判空
bool SLEmpty(SL* ps)
{
  assert(ps);
  return ps->size == 0;
}
// 顺序表数据个数
int SLSize(SL* ps)
{
  assert(ps);
  return ps->size;
}
// 销毁顺序表
void SLDestroy(SL* ps)
{
  assert(ps);
  free(ps->a);
  ps->capacity = 0;
  ps->size = 0;
}

test.c

#include "SeqList.h"
void test1()
{
  SL s;
  SLInit(&s);
  SLPushBack(&s, 1);
  SLPrint(&s);
  SLPushBack(&s, 2);
  SLPrint(&s);
  SLPushBack(&s, 3);
  SLPrint(&s);
  SLPushBack(&s, 4);
  SLPrint(&s);
  SLPushBack(&s, 5);
  SLPrint(&s);
  SLPushBack(&s, 6);
  SLPrint(&s);
  SLDestroy(&s);
}
void test2()
{
  SL s;
  SLInit(&s);
  SLPushFront(&s, 1);
  SLPrint(&s);
  SLPushFront(&s, 2);
  SLPrint(&s);
  SLPushFront(&s, 3);
  SLPrint(&s);
  SLPushFront(&s, 4);
  SLPrint(&s);
  SLPushFront(&s, 5);
  SLPrint(&s);
  SLPushFront(&s, 6);
  SLPrint(&s);
  SLPopFront(&s);
  SLPrint(&s);
  SLPopFront(&s);
  SLPrint(&s);
  SLPopFront(&s);
  SLPrint(&s);
  SLPopFront(&s);
  SLPrint(&s);
  SLPopFront(&s);
  SLPrint(&s);
  SLPopFront(&s);
  SLPrint(&s);
  SLDestroy(&s);
}
void test3()
{
  SL s;
  SLInit(&s);
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPushBack(&s, 5);
  SLPrint(&s);
  SLInsert(&s, 3, 99999);
  SLPrint(&s);
  SLErase(&s, 3);
  SLPrint(&s);
  SLModify(&s, SLFind(&s, 3), 99999);
  SLPrint(&s);
  SLDestroy(&s);
}
int main()
{
  //test1();
  //test2();
  test3();
  return 0;
}

写在最后

学到这里，数据结构总算是入门了，当然数据结构后面还有很长的路要走，要继续努力！

感谢阅读本小白的博客，错误的地方请严厉指出噢！

【数据结构】顺序表

前言

初始化顺序表

打印顺序表

检查容量

判空

顺序表数据个数

尾部插入

尾部删除

头部插入

头部删除

在pos位置插入数据

删除pos位置的数据

查找数据

修改数据

销毁顺序表

整体代码

写在最后

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】顺序表

前言

初始化顺序表

打印顺序表

检查容量

判空

顺序表数据个数

尾部插入

尾部删除

头部插入

头部删除

在pos位置插入数据

删除pos位置的数据

查找数据

修改数据

销毁顺序表

整体代码

写在最后

热门文章

最新文章

相关课程

相关电子书