【数据结构】顺序表详解从零开始步步解读画图理解并调试分
析
前⾔：
本章节将对顺序表的概念进⾏介绍，着重讲解动态顺序表。对常⽤的接⼝函数进⾏⼀个个讲解，并进⾏解析。顺序表讲解部分将从零实现顺序表接⼝函数，遇到问题我会进⾏⼀步步地调试说明，通过对本章的学习不仅能学会顺序表，还能实战练习下调试的技能。调试不仅仅是帮助我们分析程序到错误的，也可以让我们去观察和理解程序。调试才是硬技能！写⼀点点测⼀点点，不要写完了再来测，这样我们就可以很轻松的出问题。
C语⾔教学专栏：
调试的学习：
⼀、线性表的概念
【百度百科】线性表是最基本、最简单、也是最常⽤的⼀种数据结构。线性表（linear list）是数据结构的⼀种，⼀个线性表是n个具有相同特性的数据元素的有限序列。
线性表中数据元素之间的关系是⼀对⼀的关系，即除了第⼀个和最后⼀个数据元素之外，其它数据元素都是⾸尾相接的（注意，这句话只适⽤⼤部分线性表，⽽不是全部。⽐如，循环链表逻辑层次上也是⼀种线性表（存储层次上属于链式存储，但是把最后⼀个数据元素的尾指针指向了⾸位结点）。
概念：线性表（Linear list）是n个具有相同特性的数据元素的有限序列，线性表是⼀种在实际中⼴泛使⽤的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串等……
线性表在逻辑上是线性结构，呈现出⼀条线性，他们在逻辑上是挨着挨着的。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
⼆、顺序表
0x00 顺序表的概念
【百度百科】顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指⽤⼀组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采⽤顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中⼀组地址连续的存储单元中。
概念：顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储。在数组上完成数据的增删查改。顺序表⼀般可以分为静态顺序表和动态顺序表：
静态顺序表：使⽤定长数组存储元素
动态顺序表：使⽤动态开辟的数组存储
顺序表的本质是什么？
顺序表的本质就是数组，但是在数组的基础上它还要求数组是从头开始存，并且是连续存储的，不能跳跃间隔。换⾔之，顺序表既然叫顺序表，那么数据⼀定必须是挨着挨着存的。
0x01 静态顺序表
使⽤定长数组存储元素：
#define N 8
typedef int SLDataType
typedef struct SeqList {
SLDataType array[N]; //定长数组
size_t size; //有效数据的个数
} SeqList;
静态顺序表的特点：如果满了就不让插⼊。
静态顺序表的缺点：是给多少合适呢？这个往往难以斟酌，N给⼩了不够⽤，N给⼤了⼜浪费空间。
0x02 动态顺序表
使⽤动态开辟的数组存储元素：
typedef int SLDataType
typedef struct SeqList {
SLDataType* array; //指向动态开辟的数组
size_t size; //有效数据的个数
size_t capacity; //容量空间的⼤⼩
} SeqList;
三、接⼝实现
0x00 Q&A
为什么使⽤动态顺序表？
静态顺序表只适⽤于确定知道需要存多少数据的场景，如果静态顺序表的定长数组导致N定⼤了，就会造成空间浪费，如果N定⼩了⼜不够⽤。所以现实中基本都是使⽤动态顺序表，可以根据需要动态地分配空间⼤⼩。
什么是接⼝函数？
接⼝函数是在数据进⾏操作时进⾏调⽤的函数，通过调⽤数据结构的接⼝帮助你完成⼀系列操作。
0x00 基本增删查改接⼝
/* 接⼝函数 */
void SeqListInit(SL* psl); //初始化
void SeqListDestory(SL* psl); //销毁
void SeqListCheckCapacity(SL* psl); //检查是否需要增容
void SeqListPushBack(SL* psl, SLDataType x); //尾插
void SeqListPrint(SL* psl); //打印
void SeqListPushFront(SL* psl, SLDataType x); //头插
void SeqListPopBack(SL* psl); //尾删
void SeqListPopFront(SL* psl); //头删
int SeqListFind(SL* psl, SLDataType x); //查
int SeqListInsert(SL* psl, int pos, SLDataType x); //指定位置插⼊
int SeqListEarse(SL* psl, int pos); //指定位置删除
0x01顺序表初始化（SeqListInit）
为了养成模块化好习惯，我们尽量把代码分开来写。⾸先打开 VS2017，在解决⽅案资源管理器中的 "
头⽂件" ⽂件夹中创建SeqList.h ⽤来存放头⽂件。在 "源⽂件" ⽂件夹中创建 SeqList.c ⽤来实现函数，Test.c ⽤来测试我们的顺序表：
SeqList.h：
#pragma once
#include <stdio.h>
#include <stdlib.h>
typedef int SLDataType;
/* 动态顺序表 */
typedef struct SeqList {
SLDataType* array;
int size; //有效数据个数
int capacity; //数组实际能存数据的空间容量是多⼤
}SL;
/* 接⼝函数 */
void SeqListInit(SL* psl);
解读：
为了避免同⼀个头⽂件被包含多次我们可以使⽤ #pragma once（在C语⾔系列预处理章节提到过，为了加深印象我在这⾥不得不再重申⼀下）。
为了⽅便后续修改数据类型，我们可以使⽤ typedef 定义⼀个新的数据类型，这⾥我们把它取名为 SLDataType（顺序表数据类型）。
我们为了让定义的结构体使⽤时更⽅便，我们同样可以使⽤ typedef 将其定义为 SL（此时 SL = struct
SeqList，后续在使⽤时可以更加⽅便）。
最后声明我们要实现的接⼝函数——顺序表初始化函数并取名为 SeqListInit ，参数部分为 SL*psl（这⾥的 SL 就是之前被 typedef 定义的结构体 struct SeqList ），考虑到形参是只是实参的临时拷贝的问题，为了能够伤其内部，这⾥我们会使⽤址传递。所以，为了能够接收 "这个" 地址，我们使⽤指针 psl 来接收。
SeqList.c：
#include "SeqList.h"
/* 初始化 */
void SeqListInit(SL* psl) {
psl->array = NULL;
psl->size = psl->capacity = 0;
}
解读：
⾸先引⼊我们⾃⼰创建的头⽂件 #include "SeqList.h" ，我们就可以开始动⼿实现顺序表初始化函数了。
⾸先通过 psl 指向 array，将数组为空。因为是初始化，所以将有效数据个数和数组时即能存数据的空间容量⼀并置为0。
c语言listinsert函数Test.c：
#include "SeqList.h"
void TestSeqList1() {
SL sl;
SeqListInit(&sl);
}
int main() {
TestSeqList1();
return 0;
}
解读：测试代码部分，我们不在 main 函数内直接测试⽽是通过函数来测试，这样的好处是可以⽅便我们选择性的测试⼀部分的代码。为了测试，TestSeqList1 函数中⾸先创建⼀个结构体，这⾥取名为 sl ，随后将 sl 址传递传⼊ SeqListInit 函数中进⾏测试。
我们运⾏代码发现代码可以成功运⾏，我们下⾯进⼊调试来看⼀下 SeqListInit 函数是否起作⽤了。
调试代码：
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论