数据结构入门：顺序表基础剖析

文章标题：

数据结构入门：顺序表的基础解读

文章内容：

🔥个人主页：@草莓熊Lotso

🎬作者简介： C++研发方向的学习者

📖个人专栏：************************************《C语言》《数据结构与算法》****************************************

⭐️人生格言： 生活是默默的坚持，毅力是永久的享受。

前言：在上一篇博客中我们学习了算法复杂度，知道了如何计算时间复杂度，能够对编写的代码进行评估。而这篇博客将会为大家分享数据结构中顺序表的相关知识。

---

目录

一.初识顺序表

1.1–线性表

1.2–顺序表的概念与结构

二.顺序表的分类

2.1–静态顺序表

2.2–动态顺序表

三.动态顺序表的实现 –初始化

seqlist.h：

seqlist.c：

test.c：

静态顺序表部分代码实现演示：(只包含.c文件和.h文件，测试文件这里就不写了)

---

一.初识顺序表

–在正式学习顺序表之前，先明确线性表这个概念

1.1–线性表

线性表（linear list）是由n个具有相同特性的数据元素组成的有限序列，是实际中广泛应用的数据结构，常见的线性表有顺序表、链表、栈、队列、字符串等。

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

1.2–顺序表的概念与结构

–概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般采用数组存储。

• 逻辑结构：线性
• 物理结构：线性

顺序表和数组的区别：

• 顺序表的底层结构是数组，是对数组的封装，实现了常用的增删查改等操作

举个例子对比数组和顺序表：（好比苍蝇馆子和米其林餐厅的对比）

---

二.顺序表的分类

2.1–静态顺序表

–使用定长数组存储元素

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

//静态顺序表
typedef int SLDataType;
#define N 6
typedef struct Seqlist {
SLDataType a[N];//定长数组
int size;//有效数据个数
}SL;

2.2–动态顺序表

–使用动态开辟的数组存储

//动态顺序表–按需申请

typedef struct Seqlist {
SLDataType a[N];//定长数组
int size;//有效数据个数

int capacity;//空间容量
}SL;

---

三.动态顺序表的实现 –初始化

–这里分三个文件来实现动态顺序表，静态顺序表不在此演示，但博主会把静态顺序表的部分实现代码放在最后，大家可自行查看。

seqlist.h：

#pragma once
#include<stdio.h>
#include<stdlib.h>

//定义顺序表的结构
typedef int SLTDataType;
typedef struct Seqlist
{
    SLTDataType* arr;//存储数据
    int size;//有效数据个数
    int capacity;//空间容量
}SL;


//顺序表初始化
void SLInit(SL* ps);

重要提示：

****

这里对int类型和顺序表进行了重命名，给int重命名是为了后续修改方便，比如想把用了SLTDataType的变量从int改成char，只需在重命名处修改即可。

然后对顺序表重命名，将其命名为SL，后续使用更便捷清晰。重命名这部分知识点在结构体博客中有更详细讲述，感兴趣可点击链接查看，结构体知识对后续数据结构学习很重要。

【自定义类型-
结构体】–结构体类型，结构体变量的创建和初始化，结构体内存对齐，结构体传参，结构体实现位段

seqlist.c：

#define _CRT_SECURE_NO_WARNINGS
#include"seqlist.h"

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

重点提示：

先看初始化，至于尾插、头插等接口实现后续文章会讲。这里初始化简单，没特别需注意的，大家应该能看懂，不展开详述，补充下arr初始化可直接malloc申请空间，个人更倾向这样写，后续如何使用下篇博客会讲。

test.c：

#define _CRT_SECURE_NO_WARNINGS

#include"seqlist.h"

void test1()
{
    SL s1;
    SLInit(&s1);
}

int main()
{
    test1();
    return 0;
}

重点提示：

传参数得用传址调用形式，否则会出错（会报未初始化局部变量s1错误），因为传值调用修改形参不影响实参，地址不同，而传址调用形参修改影响实参，可参考之前指针超详解2中swap函数例子，那篇博客对传址调用和传值调用讲述更详细。

【C语言指针超详解(二)】–const修饰指针变量，野指针的辩析，assert断言，指针的使用和传址调用

注意：除部分情况外（数组名），有取地址操作符才是变量传地址。

编写代码最好常测试，避免写大量代码后测试找问题难修正。若不常测试，程序写完发现问题难入手，就算找到错误修改工作量也大。写一个板块就测试，能及时找错修正，测试习惯一定要有。

静态顺序表部分代码实现演示：(只包含.c文件和.h文件，测试文件这里就不写了)

1.SeqList.h

#pragma once

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

// 增强程序可维护性
#define  MAX_SIZE  10000
typedef int SQDataType;
// 静态顺序表
// 问题：给少了不够用，给多了用不完浪费，不能灵活控制
typedef struct SeqList
{
    SQDataType a[MAX_SIZE];
    int size;
}SL;

//typedef struct SeqList SL;

// 增删查改等接口函数
void SeqListInit(SL* ps);

// 头插 尾插 头删 尾删
void SeqListPushBack(SL* ps, SQDataType x);
void SeqListPushFront(SL* ps, SQDataType x);
void SeqListPopBack(SL* ps);
void SeqListPopFront(SL* ps);

2.SeqList.c

#include "SeqList.h"
//// 增删查改等接口函数
void SeqListInit(SL* ps)
{
    memset(ps->a, 0, sizeof(SQDataType)*MAX_SIZE);
    ps->size = 0;
}

// 头插 尾插 头删 尾删
void SeqListPushBack(SL* ps, SQDataType x)
{
    if (ps->size >= MAX_SIZE)
    {
        printf("SeqList is Full\n");
        return;
    }

    ps->a[ps->size] = x;
    ps->size++;
}

void SeqListPushFront(SL* ps, SQDataType x);
void SeqListPopBack(SL* ps);
void SeqListPopFront(SL* ps);

大家还可看看静态顺序表尾插实现，先尝试理解，这样后续动态顺序表尾插实现能更好入手。

小预告：初始化部分讲完了，因初始化简单没拆开讲，通过图应能很好理解，下篇文章将继续讲尾插、头插、头删、尾删等接口实现，会拆开详细讲，助于理解过程及注意点。

---

往期回顾：

【数据结构初阶】–算法复杂度的深度解析

【C语言指针超详解(六)】–sizeof和strlen的对比，数组和指针笔试题解析，指针运算笔试题解析

【C语言动态内存管理】–动态内存分配的意义，malloc和free，calloc和realloc，常见的动态内存的错误，动态内存经典笔试题分析，柔性数组，总结C/C++中程序内存区域划分
【自定义类型-
结构体】–结构体类型，结构体变量的创建和初始化，结构体内存对齐，结构体传参，结构体实现位段

结语：
本篇文章到此结束，是数据结构与算法专栏第二篇，下篇博客将接着分享顺序表其他知识点。感兴趣可先看往期回顾中几篇文章，都是数据结构重要C语言知识储备及上一篇算法复杂度。若文章有帮助，欢迎评论、点赞、收藏加关注，感谢支持。