连续存储数组的算法演示之二

Akari2023-12-142024-03-09

[toc]
上集回顾：连续存储数组的算法演示 | Akari的小站
完善了一下思路，总结了一下知识点。

数组的增删改查——也就是顺序表。

一、线性结构

把所有的结点用一根直线穿起来，节点类似于数组中的元素，或者说是
逻辑上具有单个独立意义的个体。

1.1 连续存储【数组】

1.1.1 什么叫做数组

元素类型相同，大小相等（数组传参，只要传进去首地址和长度就行）

1.1.2 数组的优缺点

优点：

存取速度快

缺点：

事先必须知道数组的长度

插入删除元素很慢

空间通常是有限制的

需要大块连续的内存块

插入删除元素的效率很低

1.2 离散存储【链表】

优点：

空间没有限制

插入删除元素很快

缺点：

存取速度很慢

栈和队列是一种特殊的线性结构，是连续存储或离散存储的一种应用

二、线性表的顺序存储的表示

2.1 郝斌老师

仅仅只使用 a[10] 是不够的，此算法要求更多。

typedef struct Arr{
    int * pBase;    // 存储的是数组第一个元素的地址
    int length;     // 数组所能容纳的最大元素的个数
    int count;      // 当前数组有效元素的个数，即当前元素个数。
}Array;     // 结构体别名 && 分号不能省

2.2 传统写法

线性表（List）:零个或多个数据元素的有限序列。
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

#defne MAXSIZE 20
typedef int ElemType;
typedef struct{
    ElemType data[MAXSIZE];
    int length;
}SqlList;

这里我们就发现描述顺序存储结构需要三个属性:

存储空间的起始位置:数组data，它的存储位置就是存储空间的存储位置。

线性表的最大存储容量: 数组长度 MAXSIZE。

线性表的当前长度: length。

这两种方法只是表示方法不一样，本质是一致的。

三、数据长度与线性表长度的区别

这里有两个概念“数组的长度”和“线性表的长度”需要区分一下。

数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。那么数组的大小一定不可以变吗？有书中谈到可以动态分配的一维数组。是的，一般高级语言，比如C、C＋＋都可以用编程手段实现动态分配数组，不过这会带来性能上的损耗。

线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。
在任意时刻，线性表的长度应该小于等于数组的长度。

四、连续存储数组的算法演示

完整程序如下：


#include <stdio.h>
#include <malloc.h>     //包含了malloc函数
#include <stdlib.h>     //包含了exit函数
#include <stdbool.h>

typedef struct Arr{
    int * pBase;    // 存储的是数组第一个元素的地址
    int length;     // 数组所能容纳的最大元素的个数
    int count;      // 当前数组有效元素的个数，即当前元素个数。
}Array;     // 结构体别名 && 分号不能省

void array_Init( Array * pArr, int length );
bool array_IsEmpty ( Array * pArr );
bool array_IsFull ( Array * pArr );
bool array_Append ( Array * pArr, int val );
void array_Traverse ( Array * pArr );
void array_Inverse ( Array * pArr );
bool array_Insert( Array * pArr, int pos, int val );
bool array_Delete( Array * pArr, int pos, int * pVal );
int array_Find ( Array * pArr, int val );
void array_SortSelete ( Array * pArr );
void array_SortBubble ( Array * pArr );
void array_SortQuick ( Array * pArr , int low, int high);
int FindPos ( Array * pArr, int low, int high );

int main (void)
{
    Array arr;  // 定义了一个结构体变量，名字是 arr
    
    int length;
    printf("初始化的数组长度：");
    scanf("%d", &length);
    array_Init(&arr, length);   // 初始化
    
    // 测试：追加
    array_Append(&arr, 1);
    array_Append(&arr, 34);
    array_Append(&arr, -5);
    array_Append(&arr, 12);
    array_Append(&arr, 4);
    array_Traverse(&arr);
    
    // 测试：翻转、倒置
    array_Inverse(&arr);
    array_Traverse(&arr);
    
    // 测试：插入
    if ( array_Insert(&arr, 3, 0) ){
        printf("插入成功！插入的元素是：%d\n", 0);
    }
    array_Traverse(&arr);
    
    // 测试：删除
    int pVal;
    if ( array_Delete(&arr, 3, &pVal) ){
        printf("删除成功！删除的元素是：%d\n", pVal);
    }
    array_Traverse(&arr);
    
    // 测试：查找
    int val;
    printf("输入要查找的元素：\n");
    scanf("%d", &val);
    printf("%d\n", array_Find(&arr, val));  // 如果是二分，必须先排序，否则会出错！

    // 测试：排序
//  array_SortSelete(&arr);
//  array_SortBubble(&arr);
    array_SortQuick(&arr, 0, length - 1);
    array_Traverse(&arr);

    return 0;
}


void array_Init( Array * pArr, int length ){
    pArr->pBase = (int *)malloc(sizeof(int) * length);
    
    if( NULL == pArr->pBase ){
        printf("动态内存分配失败！\n");
        exit(-1);
    }
    else{
        pArr->length = length;
        pArr->count = 0;
    }
}

bool array_IsEmpty ( Array * pArr ){
    if( 0 == pArr->count ){
        return true;
    }
    else
        return false;
}

bool array_IsFull ( Array * pArr ){
    if( pArr->count == pArr->length ){
        return true;
    }
    else
        return false;
}

void array_Traverse ( Array * pArr ){
    if( array_IsEmpty( pArr ) ){
        printf("数组为空！\n");
    }
    else{
        for( int i=0; i<pArr->count; i++ ){
        printf("%d ", pArr->pBase[i]);
    }
    printf("\n");
    }
}

bool array_Append ( Array * pArr, int val ){
    if( array_IsFull( pArr ) ){
        return false;
    }
    
    pArr->pBase[pArr->count] = val;
    (pArr->count)++;
    return true;
}

// 折半思想
void array_Inverse ( Array * pArr ){
    for( int i = 0; i < pArr->count / 2; i++ ){
        int t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[pArr->count - 1 - i];
        pArr->pBase[pArr->count - 1 - i] = t;
    }
}

bool array_Insert( Array * pArr, int pos, int val ){
    if ( array_IsFull( pArr ) ){
        return false;
    }
    
    if ( pos < 1 || pos > pArr->count + 1 ){
        return false;
    }
    
    for ( int i = pArr->count - 1; i >= pos - 1; i-- ){
        pArr->pBase[i + 1] = pArr->pBase[i];
    }
    pArr->pBase[pos - 1] = val;
    pArr->count++;
    
    return true;
}

bool array_Delete( Array * pArr, int pos, int * pVal ){
    if ( array_IsEmpty( pArr ) ){
        return false;
    }
    
    if ( pos < 1 || pos > pArr->count ){
        return false;
    }
    
    *pVal = pArr->pBase[pos - 1];
    for ( int i = pos; i < pArr->count; i++ ){
        pArr->pBase[i - 1] = pArr->pBase[i];
    }
    pArr->count--;
    
    return true;
}

/* 1、循环遍历
int array_Find ( Array * pArr, int val ){
    if ( array_IsEmpty( pArr ) ){
        return false;
    }

    int pos = -1;
    for ( int i = 0; i < pArr->count - 1; i++ ){
        if ( val == pArr->pBase[i] ){
            pos = i;
            break;
        }
    }

    return pos;
}*/

/* 2、二分查找：左闭右闭 （必须是有序数组！）
int array_Find ( Array * pArr , int val ){
    if ( array_IsEmpty( pArr ) ){
        return -1;
    }

    int left = 0, right = pArr->count - 1;

    while ( left <= right ){
        int middle = ( right - left ) / 2 + left;

        if ( val < pArr->pBase[middle] ){
            right = middle - 1;
        }
        else if ( val > pArr->pBase[middle] ){
            left = middle + 1;
        }
        else
            return middle;
    }
    return -1;
  }*/

// 2、二分查找：左闭右开 （必须是有序数组！）
int array_Find ( Array * pArr , int val ){
    if ( array_IsEmpty( pArr ) ){
        return -1;
    }

    int left = 0, right = pArr->count;

    while ( left < right ){
        int middle = ( right - left ) / 2 + left;

        if ( val < pArr->pBase[middle] ){
            right = middle;
        }
        else if ( val > pArr->pBase[middle] ){
            left = middle + 1;
        }
        else
            return middle;
    }
    return -1;
}

void array_SortSelete ( Array * pArr ){
    for ( int i = 0; i < pArr->count - 1; i++ ){
        for ( int j = i + 1; j < pArr->count; j++ ){
            if( pArr->pBase[i] > pArr->pBase[j] ){
                int t = pArr->pBase[i];
                pArr->pBase[i] = pArr->pBase[j];
                pArr->pBase[j] = t;
            }
        }
    }
}

void array_SortBubble ( Array * pArr ){
    for ( int i = 0; i < pArr->count - 1; i++ ){
        for ( int j = 0; j < pArr->count - 1 - i; j++ ){
            if ( pArr->pBase[j] > pArr->pBase[j + 1] ){
                int t = pArr->pBase[j];
                pArr->pBase[j] = pArr->pBase[j + 1];
                pArr->pBase[j + 1] = t;
            }
        }
    }
}

// 快排母函数
void array_SortQuick( Array * pArr , int low, int high){
    int pos;
    
    if ( low < high ){
        pos = FindPos( pArr, low, high );
        array_SortQuick( pArr, low, pos - 1 );
        array_SortQuick( pArr, pos + 1, high );
    }

    if ( low >= high ){     // 直接返回，避免无限递归。
        return;
    }
}

// 标准分割函数
int FindPos ( Array * pArr, int low, int high )
{
    int val = pArr->pBase[low];
    
    while ( low < high )
    {
        while ( low < high && pArr->pBase[high] >= val ){
            high--;
        }
        pArr->pBase[low] = pArr->pBase[high];
        
        while ( low < high && pArr->pBase[low] <= val ){
            low++;
        }
        pArr->pBase[high] = pArr->pBase[low];
    }
    pArr->pBase[low] = val;
    
    return high;
}

数组的结构体代码：

typedef struct Arr{
    int * pBase;    // 存储的是数组第一个元素的地址
    int length;     // 数组所能容纳的最大元素的个数
    int count;      // 当前数组有效元素的个数，即当前元素个数。
}Array;     // 结构体别名 && 分号不能省

定义了一个数据类型，该数据类型的名字叫做 struct Arr，该数据类型含有 3 个成员，分别为 pBase，len，cnt。

main 函数中定义

#include <stdio.h>

typedef struct Arr{
    int * pBase;    // 存储的是数组第一个元素的地址
    int length;     // 数组所能容纳的最大元素的个数
    int count;      // 当前数组有效元素的个数，即当前元素个数。
}Array;     // 结构体别名 && 分号不能省

int main(void)
{
    Array arr;  // 定义了一个结构体变量，名字是 arr

    return 0;
}

注意：此处仅仅是定义了 arr，还没有初始化。

那么此程序涉及到的函数有：

目前我们还不知道函数的形参、返回类型，均先默认 void 类型。

void array_Init ( );    // 初始化
void array_Traverse ( );    // 遍历
void array_Append ( );      // 追加
void array_IsEmpty ( );     // 判断数组是否为空
void array_IsFull ( );      // 判断数组是否已满
void array_Insert ( );      // 插入元素
void array_Delete ( );      // 删除元素
void array_Inverse ( );     // 翻转、倒置
void array_Find ( );    // 查找
void array_Sort ( );    // 排序

4.0 函数的传参问题

假设以上函数中形参都是普通变量，那么在调用此函数并执行完毕后，形参的内存会被释放，而且传递进来的实参和形参是两块不一样的内存，无法达到更改实参变量值的目的。

所以以上的函数内的形参都是以指针的方式进行定义，传递的实参为是要被修改的变量的指针(地址)，可以通过指针修改变量的值，而且在被调函数执行完毕后，被调函数的内存被释放，但是通过指针操作而被修改的变量的值不会被改变，从而达到修改变量值的目的。

从而达在被调函数如 void array_Init (); 中修改主调函数 main() 函数中 struct Arr arr; 变量的值

4.1 初始化数组 array_Init()

4.1.1 算法步骤

函数返回值类型：此函数的目的是初始化数组，不需要返回值 void

输入想要初始化的数组长度 length，然后动态内存分配长度为 length 的数组，并把分配的内存地址传给数组的首地址

如果动态内存分配失败则退出。

否则将数组的长度 = length，数组的当前元素个数 = 0;

4.1.2 代码实现

void array_Init( Array * pArr, int length ) // 初始化为总长度为 length 的数组
{
    pArr->pBase = (int *)malloc(sizeof(int) * length);  // 动态内存分配，首元素地址保存在 pBase
    
    if( NULL == pArr->pBase ){  // 分配是否成功
        printf("动态内存分配失败！\n");
        exit(-1);   // 终止程序
    }
    else{
        pArr->length = length;  // 数组中能存储的最大元素个数
        pArr->count = 0;    // 数组有效元素个数为 0
    }
    return;     // 表示此函数终止了，增强可读性
}

4.1.3 测试

输入样例：

6

输出样例：

初始化的数组长度：6

#include <stdio.h>
#include <malloc.h>     //包含了malloc函数
#include <stdlib.h>     //包含了exit函数

void array_Init( Array * pArr, int length );    // 函数声明

int main (void)
{
    Array arr;  // 定义结构体变量，名字是 arr

    int length;
    printf("初始化的数组长度：");
    scanf("%d", &length);
    array_Init(&arr, length);   // 初始化

    return 0;
}

void array_Init( Array * pArr, int length )
{
    pArr->pBase = (int *)malloc(sizeof(int) * length);
    
    if( NULL == pArr->pBase ){
        printf("动态内存分配失败！\n");
        exit(-1);
    }
    else{
        pArr->length = length;
        pArr->count = 0;
    }
}

4.2 判断是否为空 array_IsEmpty()

4.2.1 算法步骤

判断，函数返回值类型为 bool；

如果当前元素个数 = 0，即 count = 0，返回 true

否则，返回 false

4.2.2 代码实现

bool array_IsEmpty ( Array * pArr )
{
    if( 0 == pArr->count ){
        return true;
    }
    else
        return false;
}

4.3 判断是否为满 array_IsFull()

4.3.1 算法步骤

判断，函数返回值类型为 bool；

如果当前元素个数 = 数组最大元素个数，即 count = length，返回 true

否则，返回 false

4.3.2 代码实现

bool array_IsFull ( Array * pArr )
{
    if( pArr->count == pArr->length ){
        return true;
    }
    else
        return false;
}

4.4 遍历 array_Traverse()

4.4.1 算法步骤

好了，数组初始化，判断是否空、满都已完成，接下来自然而然就是遍历了，只有遍历输出才能测试后续的函数是否成功呀！

遍历，可能成功，可能失败。bool
因为如果数组为空，遍历失败。

数组不为空时才遍历

4.4.2 代码实现

注意：这里的 else不能少，不然判断为空之后，还会继续执行 for 循环！

void array_Traverse ( Array * pArr )
{
    if( array_IsEmpty( pArr ) ){
        printf("数组为空！\n");
    }
    else{   // 这里的 else 不能少
    // 数组的遍历——数组怎么遍历的，这里就怎么遍历
    for( int i=0; i<pArr->count; i++ ){
        printf("%d ", pArr->pBase[i]);
    }
    printf("\n");
    }
}

4.5 追加元素 array_Append()

初始化已经完毕了，但是数组里没有元素、是空的，所以要追加元素。

4.5.1 算法步骤

追加，可能成功，可能失败。bool
因为如果数组已满，也就是 count == length 时，追加失败。

满时返回false

不满时追加

追加数据 val

当前元素个数 +1

4.5.2 代码实现

bool array_Append ( Array * pArr, int val ) // 追加元素 val
{
    // 满时返回 false
    if( array_IsFull( pArr ) ){
        return false;
    }
    
    // 不满时追加
    pArr->pBase[pArr->count] = val; // 追加数据 val
    (pArr->count)++;    // 当前元素个数自增
    return true;
}

注意到：

pArr->pBase[pArr->count] = val; // 追加数据 val
(pArr->count)++; // 当前元素个数自增

这里就把 pArr->pBase 当成数组首地址就可，类似于 a[10] 的 a。

4.5.3 测试

输入样例：

6

1 34 -5 12 4

输出样例：

初始化的数组长度：6
成功追加元素： 1
成功追加元素： 34
成功追加元素： -5
成功追加元素： 12
成功追加元素： 4
1 34 -5 12 4

#include <stdio.h>
#include <malloc.h>     //包含了malloc函数
#include <stdlib.h>     //包含了exit函数
#include <stdbool.h>

typedef struct Arr{
    int * pBase;    // 存储的是数组第一个元素的地址
    int length;     // 数组所能容纳的最大元素的个数
    int count;      // 当前数组有效元素的个数，即当前元素个数。
}Array;     // 结构体别名 && 分号不能省

void array_Init( Array * pArr, int length );
bool array_IsEmpty ( Array * pArr );
bool array_IsFull ( Array * pArr );
bool array_Append ( Array * pArr, int val );
void array_Traverse ( Array * pArr );


int main (void)
{
    Array arr;  // 定义了一个结构体变量，名字是 arr
    
    int length;
    printf("初始化的数组长度：");
    scanf("%d", &length);
    array_Init(&arr, length);   // 初始化
    
    // 测试：追加
    if( array_Append(&arr, 1) ) printf("成功追加元素： %d\n", 1);
        else printf("追加失败！\n");
    if( array_Append(&arr, 34) ) printf("成功追加元素： %d\n", 34);
        else printf("追加失败！\n");
    if( array_Append(&arr, -5) ) printf("成功追加元素： %d\n", -5);
        else printf("追加失败！\n");
    if( array_Append(&arr, 12) ) printf("成功追加元素： %d\n", 12);
        else printf("追加失败！\n");
    if( array_Append(&arr, 4) ) printf("成功追加元素： %d\n", 4);
        else printf("追加失败！\n");
    array_Traverse(&arr);
    
    return 0;
}


void array_Init( Array * pArr, int length )
{
    pArr->pBase = (int *)malloc(sizeof(int) * length);
    
    if( NULL == pArr->pBase ){
        printf("动态内存分配失败！\n");
        exit(-1);
    }
    else{
        pArr->length = length;
        pArr->count = 0;
    }
}

bool array_IsEmpty ( Array * pArr )
{
    if( 0 == pArr->count ){
        return true;
    }
    else
        return false;
}

bool array_IsFull ( Array * pArr )
{
    if( pArr->count == pArr->length ){
        return true;
    }
    else
        return false;
}

void array_Traverse ( Array * pArr )
{
    if( array_IsEmpty( pArr ) ){
        printf("数组为空！\n");
    }
    else{
        for( int i=0; i<pArr->count; i++ ){
        printf("%d ", pArr->pBase[i]);
    }
    printf("\n");
    }
}

bool array_Append ( Array * pArr, int val )
{
    if( array_IsFull( pArr ) ){
        return false;
    }
    
    pArr->pBase[pArr->count] = val;
    (pArr->count)++;
    return true;
}

4.6 翻转、倒置 array_Inverse()

正着可以输出，那反过来也可以！

4.6.1 算法步骤

定义元素下标最大值 j 和最小值 i 中数据进行互换，之后元素最小下标 i++ 自增和元素最大下标 j– 自减进行数据互换，剩下的元素依次进行类推，直到最中间元素的数据互换完，

至于元素个数为奇数、偶数会不会有影响：数组总共奇数个元素，则中间元素不存在互换问题；偶数个元素则两两成对无中间元素

4.6.2 代码实现

void Array_Inverse ( Array * pArr )
{
    int i = 0;  //元素刚开始下标 0
    j = pArr->count - 1;    //元素最大下标要减 1
    
    while ( i < j ) // 两数互换，两杯水互换,引入第三个杯子 t
    {
        int t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[j];
        pArr->pBase[j] = t;
        
        i++;
        j--;
    }
}

也可以用 for 循环，但是没有 while 直观，而且 for 容易出错。

void Array_Inverse ( Array * pArr )
{
    int i = 0, j = pArr->count - 1;
    for( i=0; i<j; i++ ){
        int t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[j];
        pArr->pBase[j] = t;

        // i++;    // for 循环里面已经 i++了，这里多余。
        j--;
    }
}

But！上面这种方法太麻烦了：

// 折半思想
void array_Inverse ( Array * pArr )
{
    for( int i = 0; i < pArr->count / 2; i++ ){ // 折半
        int t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[pArr->count - 1 - i];
        pArr->pBase[pArr->count - 1 - i] = t;
    }
    // 同样不存在奇偶不一致会导致出问题的情况
}

上面的第一种方法并不是最优解，因为它需要使用额外的空间来存储输入的数组，即使是在原地翻转数组的情况下，交换的操作次数也更多。
而这种方法更简洁的方法在不使用额外空间的情况下原地翻转数组，而且只需要一次遍历，每次将首尾元素进行交换，从而实现原地翻转数组。

4.6.3 测试

输入样例：

6

输出样例：

初始化的数组长度：6
1 34 -5 12 4
4 12 -5 34 1

#include <stdio.h>
#include <malloc.h>     //包含了malloc函数
#include <stdlib.h>     //包含了exit函数
#include <stdbool.h>

typedef struct Arr{
    int * pBase;    // 存储的是数组第一个元素的地址
    int length;     // 数组所能容纳的最大元素的个数
    int count;      // 当前数组有效元素的个数，即当前元素个数。
}Array;     // 结构体别名 && 分号不能省

void array_Init( Array * pArr, int length );
bool array_IsEmpty ( Array * pArr );
bool array_IsFull ( Array * pArr );
bool array_Append ( Array * pArr, int val );
void array_Traverse ( Array * pArr );
void array_Inverse ( Array * pArr );


int main (void)
{
    Array arr;  // 定义了一个结构体变量，名字是 arr
    
    int length;
    printf("初始化的数组长度：");
    scanf("%d", &length);
    array_Init(&arr, length);   // 初始化
    
    // 测试：追加
    array_Append(&arr, 1);
    array_Append(&arr, 34);
    array_Append(&arr, -5);
    array_Append(&arr, 12);
    array_Append(&arr, 4);
    array_Traverse(&arr);
    
    // 测试：翻转、倒置
    array_Inverse(&arr);
    array_Traverse(&arr);
    
    return 0;
}


void array_Init( Array * pArr, int length )
{
    pArr->pBase = (int *)malloc(sizeof(int) * length);
    
    if( NULL == pArr->pBase ){
        printf("动态内存分配失败！\n");
        exit(-1);
    }
    else{
        pArr->length = length;
        pArr->count = 0;
    }
}

bool array_IsEmpty ( Array * pArr )
{
    if( 0 == pArr->count ){
        return true;
    }
    else
        return false;
}

bool array_IsFull ( Array * pArr )
{
    if( pArr->count == pArr->length ){
        return true;
    }
    else
        return false;
}

void array_Traverse ( Array * pArr )
{
    if( array_IsEmpty( pArr ) ){
        printf("数组为空！\n");
    }
    else{
        for( int i=0; i<pArr->count; i++ ){
        printf("%d ", pArr->pBase[i]);
    }
    printf("\n");
    }
}

bool array_Append ( Array * pArr, int val )
{
    if( array_IsFull( pArr ) ){
        return false;
    }
    
    pArr->pBase[pArr->count] = val;
    (pArr->count)++;
    return true;
}

void array_Inverse ( Array * pArr )	// 折半思想
{
    for( int i = 0; i < pArr->count / 2; i++ ){
        int t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[pArr->count - 1 - i];
        pArr->pBase[pArr->count - 1 - i] = t;
    }
}

4.7 插入 array_Insert()

~~直到现在我都觉得插入和删除真的不简单啊，每次都得想半天······~~

4.7.1 算法步骤

插入，可能失败，可能成功，所以是 bool

在 pos 位置处插入 val，且 pos 的位置从 1 开始

如果数组已满，插入失败，返回 false

如果插入的位置 pos < 1 || pos > 当前元素个数+1，插入失败，返回 false

pos 后的元素后移，再插入val。

下标不一致的问题：
这是插入操作的关键步骤，因为 pos 从 1 开始，而数组下标从 0 开始，那么怎么处理才能使 pos 后的元素后移，这样刚好可以使下一步插入 val 呢？

画图，不懂就画图：

原数组为：

1 34 -5 12 4

现在我要在第 3 个位置插入 0，则插入之后的数组为

1 34 0 -5 12 4

那么要使从 pos 后的元素均后移，这里是从下标从 1 开始的视角看待的，也就是我们人类的视角。
那么从数组下标的角度来看的话：即 pos - 1 及其之后的元素均后移。
之后 pos - 1 的处的元素就空出来了，也就是说这一步要达到的效果就是：通过某种手段，将 pos 后的元素后移，使得 pos 处的元素空出来，之后直接插入即可。

4.7.2 代码实现

bool array_Insert( Array * pArr, int pos, int val ) //pos的值从 1 开始，即插入后的次序（以正常视角）
{
    if ( array_IsFull( pArr ) ){    // 已满，不能插入
        return false;
    }
    
    if ( pos < 1 || pos > pArr->count + 1 ){    // pos 的值不合法时不能插入
        return false;
    }
    
    // 当前元素个数-1 = 最后一个元素下标
    // 终止条件：当 i = pos - 1 时终止，即此时的位置留给 val
    for ( int i = pArr->count - 1; i >= pos - 1; i-- ){ //pos 后的元素先右移，再插入 val
        pArr->pBase[i + 1] = pArr->pBase[i];    // i 赋给 i+1，元素右移
    }
    pArr->pBase[pos - 1] = val; // 插入数据 val
    pArr->count++;  // 有效元素个数自增
    
    return true;
}

4.7.3 测试

原数组为：

1 34 -5 12 4

在第 3 个位置插入 0，则插入之后的数组为

1 34 0 -5 12 4

输入样例：

6

输出样例：

初始化的数组长度：6
1 34 -5 12 4
插入成功！插入的元素是：0
1 34 0 -5 12 4

#include <stdio.h>
#include <malloc.h>     //包含了malloc函数
#include <stdlib.h>     //包含了exit函数
#include <stdbool.h>

typedef struct Arr{
    int * pBase;    // 存储的是数组第一个元素的地址
    int length;     // 数组所能容纳的最大元素的个数
    int count;      // 当前数组有效元素的个数，即当前元素个数。
}Array;     // 结构体别名 && 分号不能省

void array_Init( Array * pArr, int length );
bool array_IsEmpty ( Array * pArr );
bool array_IsFull ( Array * pArr );
bool array_Append ( Array * pArr, int val );
void array_Traverse ( Array * pArr );
void array_Inverse ( Array * pArr );
bool array_Insert( Array * pArr, int pos, int val );


int main (void)
{
    Array arr;  // 定义了一个结构体变量，名字是 arr
    
    int length;
    printf("初始化的数组长度：");
    scanf("%d", &length);
    array_Init(&arr, length);   // 初始化
    
    // 测试：追加
    array_Append(&arr, 1);
    array_Append(&arr, 34);
    array_Append(&arr, -5);
    array_Append(&arr, 12);
    array_Append(&arr, 4);
    array_Traverse(&arr);
    
//  // 测试：翻转、倒置
//  array_Inverse(&arr);
//  array_Traverse(&arr);
    
    // 测试：插入
    if ( array_Insert(&arr, 3, 0) ){
        printf("插入成功！插入的元素是：%d\n", 0);
    }
    array_Traverse(&arr);
    
    return 0;
}


void array_Init( Array * pArr, int length )
{
    pArr->pBase = (int *)malloc(sizeof(int) * length);
    
    if( NULL == pArr->pBase ){
        printf("动态内存分配失败！\n");
        exit(-1);
    }
    else{
        pArr->length = length;
        pArr->count = 0;
    }
}

bool array_IsEmpty ( Array * pArr )
{
    if( 0 == pArr->count ){
        return true;
    }
    else
        return false;
}

bool array_IsFull ( Array * pArr )
{
    if( pArr->count == pArr->length ){
        return true;
    }
    else
        return false;
}

void array_Traverse ( Array * pArr )
{
    if( array_IsEmpty( pArr ) ){
        printf("数组为空！\n");
    }
    else{
        for( int i=0; i<pArr->count; i++ ){
        printf("%d ", pArr->pBase[i]);
    }
    printf("\n");
    }
}

bool array_Append ( Array * pArr, int val )
{
    if( array_IsFull( pArr ) ){
        return false;
    }
    
    pArr->pBase[pArr->count] = val;
    (pArr->count)++;
    return true;
}

void array_Inverse ( Array * pArr )	// 折半思想
{
    for( int i = 0; i < pArr->count / 2; i++ ){
        int t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[pArr->count - 1 - i];
        pArr->pBase[pArr->count - 1 - i] = t;
    }
}

bool array_Insert( Array * pArr, int pos, int val )
{
    if ( array_IsFull( pArr ) ){
        return false;
    }
    
    if ( pos < 1 || pos > pArr->count + 1 ){
        return false;
    }
    
    for ( int i = pArr->count - 1; i >= pos - 1; i-- ){
        pArr->pBase[i + 1] = pArr->pBase[i];
    }
    pArr->pBase[pos - 1] = val;
    pArr->count++;
    
    return true;
}

4.8 删除 array_Delete()

跟插入差不多其实。

4.8.1 算法步骤

删除，可能成功，可能失败。bool

如果 pos < 1 || pos > count 插入失败

返回要删除 pos 位置的数据

删除完毕后，pos 后的元素前移

4.8.2 注意事项

在删除之前，应该先返回要删除的值，以便于清除删除了哪个数据。

下标不一致的问题：删除操作的话，直接把从 pos 位置后的元素前移就可以了，相当于直接覆盖了。pos 也是从 1 开始，所以 for 循环内是 count，而不是 count - 1。

画图，不懂就画图：

原数组为：

1 34 0 -5 12 4

删除第 3 个位置的 0，则删除之后的数组为：

1 34 -5 12 4

4.8.3 代码实现

bool Delete_arr(struct Arr * pArr, int pos, int * pVal){
    if(Is_empty(pArr)){
        return false;
    }
    
    if(pos < 1 || pos > pArr->cnt){ // 只能删除已有的元素
        return false;
    }
    
    *pVal = pArr->pBase[pos-1]; // 返回要删除 pos 位置的数据
    for(int i = pos; i < pArr->cnt; i++){ // 删除完毕后，pos 位置后的元素再左移
        pArr->pBase[i-1] = pArr->pBase[i];  // 元素左移
    }
    pArr->cnt--;    // 有效元素个数自减
    
    return true;
}

4.8.4 测试

原数组为：

1 34 0 -5 12 4

删除第 3 个位置的 0，则删除之后的数组为：

1 34 -5 12 4

输入样例：

6

输出样例：

初始化的数组长度：6
1 34 -5 12 4
插入成功！插入的元素是：0
1 34 0 -5 12 4
删除成功！删除的元素是：0
1 34 -5 12 4

#include <stdio.h>
#include <malloc.h>     //包含了malloc函数
#include <stdlib.h>     //包含了exit函数
#include <stdbool.h>

typedef struct Arr{
    int * pBase;    // 存储的是数组第一个元素的地址
    int length;     // 数组所能容纳的最大元素的个数
    int count;      // 当前数组有效元素的个数，即当前元素个数。
}Array;     // 结构体别名 && 分号不能省

void array_Init( Array * pArr, int length );
bool array_IsEmpty ( Array * pArr );
bool array_IsFull ( Array * pArr );
bool array_Append ( Array * pArr, int val );
void array_Traverse ( Array * pArr );
void array_Inverse ( Array * pArr );
bool array_Insert( Array * pArr, int pos, int val );
bool array_Delete( Array * pArr, int pos, int * pVal );


int main (void)
{
    Array arr;
    
    int length;
    printf("初始化的数组长度：");
    scanf("%d", &length);
    array_Init(&arr, length);
    
    // 测试：追加
    array_Append(&arr, 1);
    array_Append(&arr, 34);
    array_Append(&arr, -5);
    array_Append(&arr, 12);
    array_Append(&arr, 4);
    array_Traverse(&arr);
    
//  // 测试：翻转、倒置
//  array_Inverse(&arr);
//  array_Traverse(&arr);
    
    // 测试：插入
    if ( array_Insert(&arr, 3, 0) ){
        printf("插入成功！插入的元素是：%d\n", 0);
    }
    array_Traverse(&arr);
    
    // 测试：删除
    int pVal;
    if ( array_Delete(&arr, 3, &pVal) ){
        printf("删除成功！删除的元素是：%d\n", pVal);
    }
    array_Traverse(&arr);
    
    return 0;
}

void array_Init( Array * pArr, int length )
{
    pArr->pBase = (int *)malloc(sizeof(int) * length);
    
    if( NULL == pArr->pBase ){
        printf("动态内存分配失败！\n");
        exit(-1);
    }
    else{
        pArr->length = length;
        pArr->count = 0;
    }
}

bool array_IsEmpty ( Array * pArr )
{
    if( 0 == pArr->count ){
        return true;
    }
    else
        return false;
}

bool array_IsFull ( Array * pArr )
{
    if( pArr->count == pArr->length ){
        return true;
    }
    else
        return false;
}

void array_Traverse ( Array * pArr )
{
    if( array_IsEmpty( pArr ) ){
        printf("数组为空！\n");
    }
    else{
        for( int i=0; i<pArr->count; i++ ){
        printf("%d ", pArr->pBase[i]);
    }
    printf("\n");
    }
}

bool array_Append ( Array * pArr, int val )
{
    if( array_IsFull( pArr ) ){
        return false;
    }
    
    pArr->pBase[pArr->count] = val;
    (pArr->count)++;
    return true;
}

void array_Inverse ( Array * pArr )	// 折半思想
{
    for( int i = 0; i < pArr->count / 2; i++ ){
        int t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[pArr->count - 1 - i];
        pArr->pBase[pArr->count - 1 - i] = t;
    }
}

bool array_Insert( Array * pArr, int pos, int val )
{
    if ( array_IsFull( pArr ) ){
        return false;
    }
    
    if ( pos < 1 || pos > pArr->count + 1 ){
        return false;
    }
    
    for ( int i = pArr->count - 1; i >= pos - 1; i-- ){
        pArr->pBase[i + 1] = pArr->pBase[i];
    }
    pArr->pBase[pos - 1] = val;
    pArr->count++;
    
    return true;
}

bool array_Delete( Array * pArr, int pos, int * pVal )
{
    if ( array_IsEmpty( pArr ) ){
        return false;
    }
    
    if ( pos < 1 || pos > pArr->count ){
        return false;
    }
    
    *pVal = pArr->pBase[pos - 1];
    for ( int i = pos; i < pArr->count; i++ ){
        pArr->pBase[i - 1] = pArr->pBase[i];
    }
    pArr->count--;
    
    return true;
}

4.9 查找 array_Find()

即查找某个元素，如果存在返回下标，不存在返回 -1。

1、循环遍历

前提条件：无重复元素。
遍历数组，如果在数组中找到与待查找元素 val 相等的元素，返回下标即可。

代码实现：

int array_Find ( Array * pArr, int val )
{
    if ( array_IsEmpty( pArr ) ){   // 数组是否为空
        return false;
    }
    
    int pos = -1;
    for ( int i = 0; i < pArr->count - 1; i++ ){    // 遍历查找
        if ( val == pArr->pBase[i] ){
            pos = i;
            break;  // 终止
        }
    }

    return pos;
}

输入样例：

初始化的数组长度：6
1 34 -5 12 4
输入要查找的元素：
12

输出样例：

3

2、二分查找

具体的关于二分的知识可以去看之前写的二分查找的帖子：二分查找 | Akari的小站
参考：二分查找算法，数组有序不是必要条件！ - 知乎

关于二分查找的要求：

1. 必须有序：

二分查找算法的前提是要在有序数组中进行查找。在无序数组中使用二分查找是不可行的，因为二分查找的基本思想是通过比较中间元素与目标值的大小关系，缩小查找范围。

如果数组是无序的，无法通过比较中间元素的大小关系来确定目标值在数组的哪一部分，因此无法有效地缩小查找范围。在这种情况下，通常会选择其他查找算法，比如线性查找，它可以在无序数组中进行查找。

总结起来，二分查找适用于有序数组，而线性查找等算法适用于无序数组。

2. 可以无序，但是有条件：

先来一段维基百科概念。“二分查找算法，也称折半搜索算法，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。”

简单来说，就是在序列中找到一个分割点，使得我们需要找的答案一定在某一边的子序列而不在另一边的子序列，之后继续在找到子序列中给出分割点，无限二分下去直到找到目标，这使得原本需要一次遍历的查找时间复杂度降为了*O(log N)*。
若要将二分查找推广应用，这里有很重要的一点是：使用二分查找不一定要求数组是有序的。只需要能够找到一个分割点，将序列分为两个类别即可，通常来说这个分割点用中点。上述最基础的二分法是分为哪两个类别呢？小于中间值的为一类，大于中间值的为另一类。如果在无序的数组中，可以将数组按不同的方法分类。

因此，记住一点，使用二分法不一定要求有序，只要求可以确定答案一定会出现在其中一边即可。但是一般条件比较苛刻！

代码实现：

1、二分查找：左闭右闭：

int array_Find ( Array * pArr , int val )
{
    if ( array_IsEmpty( pArr ) ){
        return -1;
    }

    int left = 0, right = pArr->count - 1;

    while ( left <= right ){
        int middle = ( right - left ) / 2 + left;

        if ( val < pArr->pBase[middle] ){
            right = middle - 1;
        }
        else if ( val > pArr->pBase[middle] ){
            left = middle + 1;
        }
        else
            return middle;
    }
    return -1;
}

2、二分查找：左闭右开：

int array_Find ( Array * pArr , int val )
{
    if ( array_IsEmpty( pArr ) ){
        return -1;
    }

    int left = 0, right = pArr->count;

    while ( left < right ){
        int middle = ( right - left ) / 2 + left;

        if ( val < pArr->pBase[middle] ){
            right = middle;
        }
        else if ( val > pArr->pBase[middle] ){
            left = middle + 1;
        }
        else
            return middle;
    }
    return -1;
}

4.10 排序

因为目前学了选择、冒泡、快排，所以就想着都实现一下。
附上之前写的帖子：~~(大佬轻喷······)~~

~~嘶~ 突然想起来，冒泡的帖子我一直拖拖拖······到现在也没写······（才···才不是因为懒呢！）~~

4.10.1 选择排序

代码实现：

void array_SortSelete ( Array * pArr )
{
    for ( int i = 0; i < pArr->count - 1; i++ ){
        for ( int j = i + 1; j < pArr->count; j++ ){
            if( pArr->pBase[i] > pArr->pBase[j] ){
                int t = pArr->pBase[i];
                pArr->pBase[i] = pArr->pBase[j];
                pArr->pBase[j] = t;
            }
        }
    }
}

4.10.2 冒泡排序

代码实现：

void array_SortBubble ( Array * pArr )
{
    for ( int i = 0; i < pArr->count - 1; i++ ){
        for ( int j = 0; j < pArr->count - 1 - i; j++ ){
            if ( pArr->pBase[j] > pArr->pBase[j + 1] ){
                int t = pArr->pBase[j];
                pArr->pBase[j] = pArr->pBase[j + 1];
                pArr->pBase[j + 1] = t;
            }
        }
    }
}

4.10.3 快速排序

代码实现：

// 快排母函数
void array_SortQuick( Array * pArr , int low, int high)
{
    int pos;
    
    if ( low < high ){
        pos = FindPos( pArr, low, high );
        array_SortQuick( pArr, low, pos - 1 );
        array_SortQuick( pArr, pos + 1, high );
    }
    
    if ( low >= high ){     // 直接返回，避免无限递归
        return;
    }
}

// 标准分割函数
int FindPos ( Array * pArr, int low, int high )
{
    int val = pArr->pBase[low];
    
    while ( low < high ){
        while ( low < high && pArr->pBase[high] >= val ){
            high--;
        }
        pArr->pBase[low] = pArr->pBase[high];
        
        while ( low < high && pArr->pBase[low] <= val ){
            low++;
        }
        pArr->pBase[high] = pArr->pBase[low];
    }
    pArr->pBase[low] = val;
    
    return high;
}