0.前言
本篇文章包含了不少的代码测试情况,以及经过调试之后如何找出bug的情况,也悉数列举。本篇文章虽然没有菜单,是1.0版本,日后本菜鸟的代码能力提高之后会逐步完善。但是此文章经过了本人的详细思考,以及理解情况，也可以给大佬们和朋友们列举一些反例,也希望大家可以从中吸取经验,最后希望大佬们如果乐意的话可以考虑给我留下个免费的赞,您的支持是我创作的最大动力,感谢!
在讲解这一章开始时，我先说明一下什么是数据结构。
什么是数据结构？
数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的
数据元素的集合。
数据结构是由三部分进行组成，分别是:逻辑结构、存储结构和数据的运算
1.逻辑结构:
这里的一般线性表就是顺序表的意思。
1.1线性结构:
1.2非线性结构:
(1)集合
集合中的数据元素除了同属一个集合外，其它是没有关系的。
(2)树形结构
(3)图形结构或者网状结构
2.存储结构
一.线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
线性表在物理上存储时，通常以数组和链式结构的形式存储
二.顺序表
概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
储。在数组上完成数据的增删查改。
顺序表与数组的关系:(非常容易混淆)
这块我简单提一下顺序表和数组的关系:
对于数组而言:
数组的元素是可以随机存放的,因为：数组通过下标访问是可以任意存储的
可以看到值已经放进去了
对于顺序表而言:
顺序表是要连续存放的是,这个连续存放,不是指的是值连续,而是空间连续(意思是你存放的时候，不能跳着存，必须从0下标开始，依次向后存放)
简单地讲:
顺序表不能随意存储,顺序表必须从0下标开始,依次向后存放,意思就是他是顺序存储的,不会出现空一个位置的情况。
顺序表一般可以分为：动态和静态顺序表,
动态顺序表:也是基于数组实现的，只不过它可以实现扩容，而数组是固定长度大小的
1.静态顺序表：使用定长数组存储元素
图解:
定义静态顺序表:
#define N 10 typedef int SLDatatype;//这个地方可以避免写死类型是int,以后想换就换 struct SeqList { SLDatatype a[N];//为了避免写死数组大小,需要改的时候到处改,那就使用宏定义 int size; };
静态顺序表的缺点:
如果存满了还想存入数据,那就不能继续存储了,因为空间是固定的
#define N 10
N-->改成10000,如果这个地方要存储10001,那还是不够存储,如果存不满10000个空间,那会浪费空间
总体来说:给小了不够用，给多了浪费
因此：
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间
大小，所以下面我们实现动态顺序表。
2.动态顺序表：使用动态开辟的数组存储
图解:
定义动态顺序表
//动态顺序表 typedef int SLDatatype;//这个位置换成double会导致问题,可能会导致全元素都是0 typedef struct SeqList { SLDatatype* a;//指向动态开辟的数组 int size; //存储的有效数据的个数 int capacity;//容量空间的大小 }SL;//类型名重定义
接口实现
1️⃣ 初始化:SLInit
void SLInit(SL* psl);//动态顺序表初始化
错误的初始化:
正确的初始化:
void SLInit(SL* psl) { //malloc扩容因为malloc类型是->void* malloc (size_t size);所以需要强制转换 psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//开4个比较合适 //开辟失败会返回NULL,并打印错误信息 if (psl->a == NULL) { perror("malloc fail"); return; } psl->capacity = 4;//使用结构体指针指向访问对象的成员,当前容量 psl->size = 0;//当前有效信息个数 }
图解:
2️⃣销毁：SLDestroy
SLDestroy(SL* psl);//顺序表销毁
void SLDestroy(SL* psl)//销毁不是整没了，而是还给操作系统了 { free(psl->a);//这里不free的话会产生野指针 psl->a = NULL; psl->size = 0; psl->capacity = 0; }
3️⃣检查容量:SLCheckCapacity
说明一下:
realloc是新增到多少空间,比如说我本来是20个int的空间，(int*)realloc(arr,40),这是把空间整体扩到40个int,不是说增了多少，后面这个40的位置是整体的大小,而不是20+40=60。
这个realloc的知识点可以看这篇文章，比较详细地展开说明:http://t.csdn.cn/H3I26
void SLCheckCapacity(SL* psl) { if (psl->size == psl->capacity)//有效信息的个数等于当前容量 { SLDatatype* tmp =(SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2); if (tmp == NULL)//申请空间过大可能会申请失败 { perror("realloc fail"); return; } psl->a = tmp;//原地扩容用的是原来的地址，异地扩容用的是新的 psl->capacity *= 2;//当前容量*2 } }
图解:
(SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);
这个地方扩2倍是比较合适的。
4️⃣顺序表打印:SLPrint
void SLPrint(SL*psl);//顺序表打印
void SLPrint(SL* psl) { for (int i = 0; i < psl->size; i++) { printf("%d ", psl->a[i]); } printf("\n"); }
打印顺序表的每个元素
5️⃣尾部插入:SLPushBack
void SLPushBack(SL* psl, SLDatatype x); //顺序表尾插
void SLPushBack(SL* psl, SLDatatype x) { assert(psl); SLCheckCapacity(psl);//容量初始值为4,检查当前容量,不够则扩容 psl->a[psl->size++] = x; }
调用测试尾部插入的代码:
void TestSeqList1() { SL s; SLInit(&s); SLPushBack(&s, 1); SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushFront(&s,5); SLPrint(&s); SLDestroy(&s); }
执行:
