数据结构(二) -- 数组和链表
数据结构主要可以分为两大模块：
线性结构
非线性结构
本文主要开始讲线性结构。
什么是线性结构线性结构，顾名思义，就是这些数据所有节点都能被一根线(指针)联系起来的一种结构。
线性结构的存储方式：
连续存储：【数组】
离散存储：【链表】
线性结构的常见应用方式：
栈
队列
专题 :【递归】
数组和链表本小节学习数组和链表，从底层去了解和实现数组与链表，并分析两者对应的优缺点
数组数组是最常见的链式存储结构，它是一段连续的内存空间，在内存中我们可以简单表示为下图样式
通过上图我们可以把代码中int arr[6] = {1,2,3,4,5,6};执行的操作从内存中脑补出来，同时我们可以简单分析一下，数组应该有的一些基本使用。如
初始化、
添加新元素、
插入新元素、
删除某个元素、
判断是否为空数组、
是否是满数组、
排序
倒序
查询是否包含某个元素
······
本小节就带着你手把手实现一个简单的数组的封装，借此来了解数组的数据结构以及内部的一些基本算法知识。这里就简单的以一个 int 类型的数组来示例，后面学到泛型的时候便可更加好的理解数组的实现。
首先简单分析一下数组中基本的属性，我们有上面的数组内存中的逻辑图可以确定数组有对应的内存空间，有一个内存起始地址，因为系统分配内存的时候长度是一定的，所以数组中有一个表示最大长度的属性，数组中的元素也可能会根据实际个数不定，所以肯定有元素个数的标记，这个标记不仅可以拿来查看数组元素个数，也能确定了元素的下标。通过简单的分析我们可以总结数组中基本的属性如下：
【pBase】 数组首字节地址
【length】 数组长度(决定分配的内存大小)
【count】 数组中有效元素个数
下面就根据上面的分析来实现一个简单的数组，这里只说一下思路，完整代码请在这里下载数组实现代码
// 定义个数组 typedef struct Array { int length; // 数组长度 int count; // 数组当前元素数 count int *pBase; // 数组的首字节地址 }* PMyArray,MyArray; //两个别名，PMyArray 类似java中类名，定义的对象不带 * , MyArray类似于OC中的类型，定义的对象带 * 。 // 要实现的一些基本方法 /** 初始化数组*/ void init_Arr(MyArray *pArr, int len); /** 追加数组*/ bool append_Arr(MyArray *pArr, int value); /** 插入数组*/ bool insert_Arr(MyArray *pArr, int index , int value); /** 删除数组*/ bool delete_Arr(MyArray *pArr, int index , int * pVal); /** 是否满载*/ bool is_full(MyArray *pArr); /** 是否为空*/ bool is_empty(MyArray *pArr); /** 排序数组*/ void sort_Arr(MyArray *pArr); /** 展示数组*/ void show_Arr(MyArray *pArr); /** 倒序数组*/ void inversion_Arr(MyArray *pArr); /** 获取一个默认初始化的数组*/ MyArray * get_Arr(void); int main(void) { MyArray arr; // 声明 int len = 6; // 定义数组长度 init_Arr(&arr,len); // 初始化 // 添加元素 int time = 0; while (time < len) { append_Arr(&arr, 100 + time); time++; } insert_Arr(&arr, 6, 200); // 插入元素 insert_Arr(&arr, 7, 300); insert_Arr(&arr, arr.count, 400); insert_Arr(&arr, 0, 500); insert_Arr(&arr, 3, 600); show_Arr(&arr); // 打印数组元素 int val; //delete_Arr(&arr, 3 ,NULL); // 删除第三个元素 delete_Arr(&arr, 3 ,&val); printf("被删除的元素是 %d \n",val); show_Arr(&arr); // 打印数组元素 inversion_Arr(&arr); // 倒序排列一下 show_Arr(&arr); // 打印数组元素 sort_Arr(&arr); // 排序数组 show_Arr(&arr); // 打印数组元素 #pragma mark -- OOP // 类似于 OC 中的面向对象用法 MyArray * array3 = get_Arr(); printf("array3 address is %p\n",array3); printf("array3 address is %p\n",&array3); show_Arr(array3); // 类似于 java 中的面向对象用法 PMyArray myArray4 = get_Arr(); printf("array4 address is %p\n",myArray4); printf("array4 address is %p\n",&myArray4); show_Arr(myArray4); return 0; } // 初始化数组，对内部元素基本初始化 void init_Arr(MyArray *pArr,int len){ (*pArr).pBase = (int *)malloc(sizeof(int) * len); // 先分配一段内存空间，长度为 len * int长度。 if(pArr->pBase == NULL) { printf("内存分配失败，初始化失败\n"); exit(-1); // 终止程序 }else { pArr->length = len; pArr->count = 0; } return; } /** 实现数组插入 1. 判断插入下标是否越界 2. 如果插入前数组已经满了，就增大一个长度，重新插入 3. 如果插入前数组未满 3.1 当插入位置小于最大元素下标，先把要插入目标点后面的元素往后移动一个单位。 如在{1，2，4，5}中第3个位置插入3，结果为{1，2，3，4，5} 3.2 当插入位置大于等于最大元素下标，直接在原来数组后面add最后一个元素。 如在{1，2}中第5个位置插入 3 结果为{1，2，3} @param pArr 要操作的数组的指针 @param index 要插入的index 即下标 @param value 要插入的值 @return 返回插入成功/失败 */ bool insert_Arr(MyArray *pArr, int index , int value){ // 为减少篇幅，建议直接下载源码 } /** 实现数组删除某个元素 并可以从外部获得被删除元素的值 1. 判断删除下标是否越界 2. 判断原数组是否为空 3. 如果删除前先保存对应 index 的值赋值给外部变量 把要删除目标点后面的元素往前移动一个单位。 如在{1，2，3，4，5}中第3个位置删除3，结果为{1，2，4，5} @param pArr 要操作的数组的指针 @param index 要伤处的index 即下标 @param pVal 要删除值的地址 @return 返回删除成功/失败 */ bool delete_Arr(MyArray *pArr , int index ,int *pVal) { // 为减少篇幅，建议直接下载源码 } /** 往数组尾部添加元素 @param pArr 数组指针 @param value 要添加的元素值 @return 添加成功/失败 */ bool append_Arr(MyArray *pArr,int value){ if (!is_full(pArr)) { // 判断是不是已经满了数组 // 数组未满，添加 pArr->pBase[pArr->count] = value; pArr->count++; return true; }else{ printf("数组已经满了,无法从尾部追加元素，请尝试从前面插入\n"); return false; } } // 为了控制篇幅，这里不再进行罗列，可以直接去下载源码对比查看