【数据结构初阶】--顺序表(一)
🔥个人主页：@草莓熊Lotso
🎬作者简介：C++研发方向学习者
📖个人专栏： 《C语言》 《数据结构与算法》
⭐️人生格言：生活是默默的坚持，毅力是永久的享受。
前言：在上篇博客中我们学习了算法复杂度 ，明确了如何计算时间复杂度，能对写出来的代码进行一个评估，那么我们这篇博客将会给大家分享数据结构中顺序表的相关知识点。
目录
静态顺序表部分代码实现演示：(只包含.c文件和.h文件，测试文件这里就不写了)
一.初识顺序表
--在正式学习顺序表之前，我们先明确一下线性表这个概念
1.1--线性表
线性表(linear list)是n个具有相同特性的数据元素的有限序列，线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表，链表，栈，队列，字符串……
线性表在逻辑上是线性结构，也就是说连续的一条直线。但是在物理结构上并不一定是连续的。线性表在物理上存储时，通常以数组和链式结构的形式存储。
1.2--顺序表的概念与结构
--概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况采用数组存储。
- 逻辑结构：线性
- 物理结构：线性
顺序表和数组的区别：顺序表的底层结构是数组，对数组的封装，实现了常用的增删查改等结构
我们来举个例子对比一下数组和顺序表：(苍蝇馆子和米其林餐厅的对比)
二.顺序表的分类
2.1--静态顺序表
--使用定长数组存储元素
静态顺序表缺陷：空间给少了不够用，给少了造成空间浪费
//静态顺序表
typedef int SLDataType;
#define N6
typedef struct Seqlist {
SLDataType a[N];//定长数组
int size;//有效数据个数
}SL;
2.2--动态顺序表
--使用动态开辟的数组存储
//动态顺序表--按需申请
typedef struct Seqlist {
SLDataType a[N];//定长数组
int size;//有效数据个数
intcapacity;//空间容量
}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语言知识储备，以及上一篇的算法复杂度，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。
