// 定义个数组
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;
    }
    
}
// 为了控制篇幅，这里不再进行罗列，可以直接去下载源码对比查看

// 代码的表示如下
typedef struct Node{
    int data;     //数据域
    struct Node *pNext;     // 指针域 - 指向相同类型的下一个节点
}*PNODE,NODE;  // PNODE 等价于 struct Node * ， NODE 等价于 struct Node
【只需要拿到 pNext 指针就能推算出整个链表】

// 创建一个值域为空的头结点,给头指针分配内存
PNODE pHead = (PNODE)malloc(sizeof(PNODE)); // 头指针

// 通过头节点遍历后面节点
PNODE p = pHead->pNext; //获得首节点
while (p != NULL) {
    printf("data = %d \n",p->data);
    p = p->pNext;
}
printf("遍历完毕，退出\n");
return;

bool isEmpty_list(PNODE pHead)
{
    if ((*pHead).pNext == NULL) {
        return false;
    }else{
        return true;
    }
}

int length_list(PNODE pHead)
{
    PNODE p = pHead->pNext;
    int len = 0;
    while (p->pNext == NULL) {
        len++;
        p = p->pNext;
    }
    return len;
}

其实思路很简单，主要是吧 p指向节点的的pNext 指向 q,
然后q所指向的下个节点直接指向原来p所指向的节点。
伪代码如下：
temp = p->pNext;
p->pNext -> q;
q->pNext = temp;
    
或者直接
q->pNext = P->pNext;
P->pNext = q;

bool insert_list(PNODE pHead , int pos , int val){
    
    // 判断位置是否合法
    PNODE q = pHead;   // 要插入的位置，如果是 <= 0,则直接插到最前面，如果是 pos = 1 就插入第一个后面,pos = n,就插到第 n 个后面
    int i = 0;
    while (i < pos) {
        if (q->pNext == NULL) {
            printf("要插入的位置不合法;大于链表长度\n");
            break;
        }else{
            q = q->pNext; //要被插入的节点
            i++;
        }
    }
    
    // 插入操作
    PNODE p = (PNODE)malloc(sizeof(NODE));
    if (p == NULL) {
        printf("动态分配内存失败\n");
        exit(0);
    }
    p->data = val;
    
    // 前一个节点为q， 直接添加到 q 后面。
    p->pNext = q->pNext;
    q->pNext = p;
    
    return true;
}

// 思路：
// 想要删除后面的节点，直接让 p 的指针域指向下下个节点就完成了
// 这里的删除其实很方便，但是有个容易造成内存泄漏的误区
// 因为直接删除之后，我们就无法在拿到 p 后面的节点的地址，然后无法释放，最终内存泄漏
// 最终实现：
temp = p->pNext;    // 临时变量保存要删除节点地址
p->pNext = p->pNext-pNext;  // p 的指针域指向下下个节点
free(temp);     // 释放被删除节点内存

bool delete_list(PNODE pHead , int pos , int * val){
    
    // 找到要被删除的元素保存起来
    PNODE p = pHead;
    int i = 0;
    while (i < pos - 1) { // 找到被删除节点的前一个节点
        
        if (p->pNext == NULL) {
            break;
        }
        p = p->pNext;
        i++;
    }
    
    if (i < pos && p->pNext == NULL) {
        printf("你要删除的位置非法，此位置不在链表长度范围之内\n");
        return false;
    }
    
    // 找到了要被删除的那个节点
    PNODE t = p->pNext;;
    *val = t->data;     // 把被删除节点的值传给外面
    
    p->pNext = t->pNext;  // 直接指向后面一个节点
    free(t);    // 释放被删除节点内存，防止内存泄漏
    
    return true;
}