顺序表(数据结构)---排队啦！（一）

前言：

 这节我们来学习和实现线性结构中最简单的顺序表，由于博主使用C语言实现的，所以读者要对C语言的结构体、指针、内存管理这三部分知识做到理解并掌握。看代码能理解，能看懂，相信自己的实力！

1.线性表的性质

 数据在内存中存储有两种结构、分别是逻辑结构和物理结构。顺序表就是逻辑结构中的线性结构+物理结构中的顺序结构。

 线性结构的性质：线性意味着内存中的数据之间的关系呈现一条线状。

 顺序结构的要求：顺序结构要求数据之间是有序的，数据元素与数据元素是紧挨着的，就像排队一样。

 顺序表的本质：看完线性结构和顺序结构后，脑海里有没有涌现一股灵感呢？是的，顺序表的本质就是一个数组。这个数组和普通的数组不太一样，我们普通的数组可以进行以下这样的操作：

#include <stdio.h>
int main()
{
    int arr[10] = {0};
    arr[0] = 1;
    arr[5] = 10;
    arr[9] = 20;
    return 0;
}

 假如我们要把3个整型值放到一个数组里面，普通数组可以将这3个整型值放到该数组中的任意位置；比如这个数组的第一个元素、第六个元素、最后一个元素分别被赋值了1、10、20。然而，顺序表要存放这3个值，只能按顺序存放在下标为0、1、2的元素位置上。

2.静态数组or动态数组

2.1静态数组

 静态数组是我们一开始就确定好数组的大小，在运行时不能改变数组存储多少。所以这里就有个问题：

当我们在用静态数组开辟空间的时候，给了100个元素空间，但实际情况需要存101个元素，但存不了了，数组已经满了

所以我决定给个大一点的数组，创建一个能存放1000个元素的数组，但实际情况只需要存200个元素，造成了不必要的浪费。

 总结：静态数组的缺陷就是，数组空间开辟小了不够用，开辟大了用不完。

2.2动态数组

 所以我们选择能根据具体的存储情况，开辟大小适合的数组，动态数组可以实现。

 动态开辟的空间是在堆区上开辟的，会使用到realloc函数开辟堆区上的空间，我们在这里描述一下这个函数的功能吧。realloc本意是追增空间，malloc才是一个纯正实现开辟空间的函数，但realloc的功能更强大。

realloc的功能

   相信没学过内存管理的同学一脸茫然，头顶打着问号，看图理解：

接收地址的指针未空指针的情况：

指针指向的堆空间够追加的情况：

指针指向的堆空间不够追加的情况：

 就这样，一开始给数组小一点的空间，空间不够了，在realloc的帮助下增容就实现动态数组了。一般每次增容，新容量都是原容量的2倍。

3.结构体的创建

 进度有点慢了，我们直接看代码：

 1.静态顺序表：

 将数组元素个数用宏(N)表示，此后凡是需要改变数组个数，不用一个一个改，只用改N就可以全部替换了；将顺序表的数组元素类型改名为SLDataType也是同理；

 2.动态顺序表

 其实动态数组的创建的一些情况还是和静态数组一样的，比如把struct SeqList的名字改成SL，元素类型用SLDataType。主要不同的点是用指针管理开辟的数组空间，多一个capacity变量表示数组的最大容量。

 补充：分模块写的重要性

test.c文件是用来测试SeqList的功能的一个文件。

SeqList.h用来声明接口函数的，还有一些宏，程序用得到的库函数头文件等。

SeqList.c是用来实现接口函数的。

 补充：使用宏#pragma once可以防止头文件被多次包含；我们引头文件的时候，编译器会把头文件里的内容复制一份放到我们的程序当中，如果我们多次引用，就会有很多重复的代码，这个宏就够很好的防止头文件被多次引用。

 好的，前提都说完了，进入正题。学习思想，实现接口函数。