2.顺序表

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

1.顺序表的介绍

线性表的顺序结构就是顺序表；顺序表是用一段连续的存储单元依次存储线性表的数据元素的线性结构，一般情况下采用数组进行存储，在数组中完成增删查改；

2.顺序表的实现

2.1.概念以及结构

顺序表是用一段物理地址连续的存储单元一次存储数据的线性结构；

顺序表一般可以分为：

1.静态表：使用定长的数组进行存储

2.动态表：使用动态开辟的数组进行存储

我们正常情况下不会使用静态的顺序表，原因很简单，我们就拿csdn来说，假如csdn对用户信息存储的时候使用的是一个静态的顺序表，这个时候就会面临一个问题，就是你怎么知道csdn未来的用户有多少呢？假如空间不够了，我们增的多了怕浪费资源，增的少了，又怕后续不够用，而且我们每次尽心增加和删除空间都是非常麻烦的，所以我们正常情况下不会使用静态顺序表，而是使用动态，所以对于静态顺序表，我们不过多演示；

2.2.动态顺序表

2.2.1初始化操作

由于需要进行动态开辟空间，所以先判断是否是空指针，之后进行申请一块空间，之后完成初始化；

void InitList(SeqList* L)
{
assert(L);

L->data = NULL;
L->length = 0;
L->capacity = 0;

DataType* tmp = (DataType*)malloc(sizeof(DataType) * InitCapacity);
if (tmp == NULL) {
printf("malloc fail\\n");
return; /* void 函数不能 return 0 */
}
L->data = tmp;
L->capacity = InitCapacity;
}

2.2.2:扩容操作

简单的扩容操作就是将容量扩大到原来的两倍就可以了，首先是判断当有效数据的个数等于容量空间的大小的时候就需要进行扩容操作了，我们扩容一般是直接扩大两倍，我们这里主要用relloc来进行开辟空间；

int IncreaseCapacity(SeqList* L)
{
if (L == NULL) {
return 0;
}
if (L->length < L->capacity) { /* ★ 还有空位就不扩 */
return 1;
}

size_t newCap = (L->capacity == 0) ? (size_t)InitCapacity
: L->capacity * 2;

if (newCap > (size_t)-1 / sizeof(DataType)) {
printf("容量溢出\\n");
return 0;
}

DataType* tmp = (DataType*)realloc(L->data, newCap * sizeof(DataType));
if (tmp == NULL) {
printf("realloc fail\\n");
return 0;
}
L->data = tmp;
L->capacity = newCap;
return 1;
}

2.2.3：建立顺序表

我们这里主要使用的是数组的形式

void CreatList(SeqList* L, const DataType a[], int n)
{
assert(L && a);

for (int i = 0; i < n; i++)
{
if (!PushBack(L, a[i])) {
printf("建立失败：已放入 %d 个\\n", i);
return;
}
}
}

2.2.4：销毁

销毁操作需要将动态申请的空间全部进行释放

void Destroy(SeqList* L)
{
if (L == NULL) {
return;
}
free(L->data);
L->data = NULL; /* ★ 防野指针 */
L->length = 0;
L->capacity = 0;
}

2.2.5：头插

头插的过程就是将此时链表中的内容给整体向后移动一位，然后在头部放上新的内容就行了；

int PushFront(SeqList* L, DataType x)
{
if (L == NULL) {
return 0;
}
if (!IncreaseCapacity(L)) { /* ★ 传参调用 */
printf("头插失败：扩容异常\\n");
return 0;
}

for (size_t i = L->length; i > 0; i–) {
L->data[i] = L->data[i – 1];
}

L->data[0] = x;
L->length++;
return 1;
}

2.2.6：头删

这里直接将后面的内容覆盖过来就行了；

int PopFront(SeqList* L)
{
assert(L);

if (L->length == 0) { /* ★ 0 不是 NULL */
printf("头删失败：表为空\\n");
return 0;
}

for (size_t i = 0; i + 1 < L->length; i++) { /* ★ 防下溢 */
L->data[i] = L->data[i + 1]; /* ★ 是 data[i] */
}

L->length–;
return 1; /* ★ 成功返回 1 */
}

2.2.7：尾插：

这里在尾部插入一个数据

int PushBack(SeqList* L, DataType x)
{
if (L == NULL) { /* ★ == 不是 = */
return 0;
}
if (!IncreaseCapacity(L)) {
printf("尾插失败：扩容异常\\n");
return 0;
}

L->data[L->length] = x;
L->length++;
return 1; /* ★ 成功返回 1 */
}

2.2.8：尾删：

这里是直接将有效数据个数减去1就行了；

int PopBack(SeqList* L)
{
if (L == NULL) {
return 0;
}
if (L->length == 0) {
printf("尾删失败：表为空\\n");
return 0;
}
L->length–;
return 1;
}

3.总代码

1.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "1.h"

/* ================= ① 初始化 ================= */
void InitList(SeqList* L)
{
assert(L);

L->data = NULL;
L->length = 0;
L->capacity = 0;

DataType* tmp = (DataType*)malloc(sizeof(DataType) * InitCapacity);
if (tmp == NULL) {
printf("malloc fail\\n");
return; /* void 函数不能 return 0 */
}
L->data = tmp;
L->capacity = InitCapacity;
}

/* ================= ② 扩容 ================= */
int IncreaseCapacity(SeqList* L)
{
if (L == NULL) {
return 0;
}
if (L->length < L->capacity) { /* ★ 还有空位就不扩 */
return 1;
}

size_t newCap = (L->capacity == 0) ? (size_t)InitCapacity
: L->capacity * 2;

if (newCap > (size_t)-1 / sizeof(DataType)) {
printf("容量溢出\\n");
return 0;
}

DataType* tmp = (DataType*)realloc(L->data, newCap * sizeof(DataType));
if (tmp == NULL) {
printf("realloc fail\\n");
return 0;
}
L->data = tmp;
L->capacity = newCap;
return 1;
}

/* ================= ③ 建立 ================= */
void CreatList(SeqList* L, const DataType a[], int n)
{
assert(L && a);

for (int i = 0; i < n; i++)
{
if (!PushBack(L, a[i])) {
printf("建立失败：已放入 %d 个\\n", i);
return;
}
}
}

/* ================= ④ 销毁 ================= */
void Destroy(SeqList* L)
{
if (L == NULL) {
return;
}
free(L->data);
L->data = NULL; /* ★ 防野指针 */
L->length = 0;
L->capacity = 0;
}

/* ================= ⑤ 头插 ================= */
int PushFront(SeqList* L, DataType x)
{
if (L == NULL) {
return 0;
}
if (!IncreaseCapacity(L)) { /* ★ 传参调用 */
printf("头插失败：扩容异常\\n");
return 0;
}

for (size_t i = L->length; i > 0; i–) {
L->data[i] = L->data[i – 1];
}

L->data[0] = x;
L->length++;
return 1;
}

/* ================= ⑥ 头删 ================= */
int PopFront(SeqList* L)
{
assert(L);

if (L->length == 0) { /* ★ 0 不是 NULL */
printf("头删失败：表为空\\n");
return 0;
}

for (size_t i = 0; i + 1 < L->length; i++) { /* ★ 防下溢 */
L->data[i] = L->data[i + 1]; /* ★ 是 data[i] */
}

L->length–;
return 1; /* ★ 成功返回 1 */
}

/* ================= ⑦ 尾插 ================= */
int PushBack(SeqList* L, DataType x)
{
if (L == NULL) { /* ★ == 不是 = */
return 0;
}
if (!IncreaseCapacity(L)) {
printf("尾插失败：扩容异常\\n");
return 0;
}

L->data[L->length] = x;
L->length++;
return 1; /* ★ 成功返回 1 */
}

/* ================= ⑧ 尾删 ================= */
int PopBack(SeqList* L)
{
if (L == NULL) {
return 0;
}
if (L->length == 0) {
printf("尾删失败：表为空\\n");
return 0;
}
L->length–;
return 1;
}

/* ================= 辅助 ================= */
void PrintList(const SeqList* L)
{
if (L == NULL) return;
for (size_t i = 0; i < L->length; i++) {
printf("%d ", L->data[i]);
}
printf("\\n");
}

int Length(const SeqList* L) { return L ? (int)L->length : 0; }
int IsEmpty(const SeqList* L) { return (L && L->length == 0) ? 1 : 0; }

头文件1.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define InitCapacity 4

typedef int DataType;

typedef struct SeqList
{
DataType* data; /* 动态数组 */
size_t length; /* 有效元素个数 */
size_t capacity; /* 容量 */
} SeqList;

/* ① 初始化 ② 建立 ③ 增容 ④ 销毁 */
void InitList(SeqList* L);
void CreatList(SeqList* L, const DataType a[], int n);
int IncreaseCapacity(SeqList* L);
void Destroy(SeqList* L);

/* ⑤ 头插 ⑥ 头删 ⑦ 尾插 ⑧ 尾删 */
int PushFront(SeqList* L, DataType x);
int PopFront(SeqList* L);
int PushBack(SeqList* L, DataType x);
int PopBack(SeqList* L);

/* 辅助 */
void PrintList(const SeqList* L);
int Length(const SeqList* L);
int IsEmpty(const SeqList* L);

测试文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "1.h"

int main(void)
{
SeqList L;
InitList(&L);

printf("空表: "); PrintList(&L); /* 空行 */

/* 尾插 1 2 3 */
PushBack(&L, 1); PushBack(&L, 2); PushBack(&L, 3);
printf("尾插 1 2 3: "); PrintList(&L); /* 1 2 3 */

/* 头插 0 */
PushFront(&L, 0);
printf("头插 0: "); PrintList(&L); /* 0 1 2 3 */

/* 尾插触发扩容（4 -> 8）*/
PushBack(&L, 4); PushBack(&L, 5); PushBack(&L, 6); PushBack(&L, 7);
printf("继续尾插: "); PrintList(&L); /* 0 1 2 3 4 5 6 7 */
printf("当前 capacity = %d\\n", (int)L.capacity); /* 8 */

/* 头删 */
PopFront(&L);
printf("头删一次: "); PrintList(&L); /* 1 2 3 4 5 6 7 */

/* 尾删 */
PopBack(&L);
printf("尾删一次: "); PrintList(&L); /* 1 2 3 4 5 6 */

printf("length = %d, empty = %d\\n", Length(&L), IsEmpty(&L));

/* 边界 */
Destroy(&L);
PopFront(&L); /* 应提示：表为空 */
PopBack(&L); /* 应提示：表为空 */

/* 销毁后再建立，验证 capacity=0 也能恢复 */
InitList(&L);
PushBack(&L, 99);
printf("重建后: "); PrintList(&L); /* 99 */
Destroy(&L);

return 0;
}

📌 相关阅读：

下一篇：

《链表》