连续存储数组的算法演示

郝斌老师数据结构视频学习记录。
涉及到数组的初始化、插入、删除、查找、翻转、排序等。

/*
  1. 讲数组是为了讲泛型：
    存储不一样，操作就不一样；
    而泛型达到的效果是：存储不一样，但操作一样
  
  2. 试数，画图
 */
#include <stdio.h>
#include <malloc.h>	//包含了malloc函数
#include <stdlib.h>     //包含了exit函数
#include <stdbool.h> 

struct Arr
{
    int* pBase;     //存储的是数组第一个元素的地址
    int len;        //数组所能容纳的最大元素的个数
    int cnt;        //当前数组有效元素的个数
};                  //分号不能省

void Init_arr(struct Arr* pArr, int len);   //初始化数组
void Get_arr(struct Arr* pArr, int val);    //获取下标
bool Is_empty(struct Arr* pArr);    //判断数组是否为空
bool Is_full(struct Arr* pArr);     //判断数组是否已满
bool Append_arr(struct Arr* pArr, int val);     //追加
bool Insert_arr(struct Arr* pArr, int pos, int val);    //插入,pos从1开始

bool Delete_arr(struct Arr* pArr, int pos, int * pVal);     //删除
//如果用int，无法判断是否删除成功。bool不能返回删除的值，所以只能用指针
void Show_arr(struct Arr* pArr);
void Inversion_arr(struct Arr* pArr);   //翻转，倒置
void Sort_arr(struct Arr* pArr);        //排序

int main(void)
{
    struct Arr arr;
    int val;
    
    Init_arr(&arr, 6);
    Show_arr(&arr);
    Append_arr(&arr, 1);
    Append_arr(&arr, 10);
    Append_arr(&arr, -3);
    Append_arr(&arr, 6);
    Append_arr(&arr, 88);
    Append_arr(&arr, 11);
    
    Get_arr(&arr, 4);
    Insert_arr(&arr, 6, 99);
    
    //把val的地址发给pVal,在函数内部可以通过它修改val的值
    if( Delete_arr(&arr, 4, &val) ){
        printf("删除成功\n");
        printf("删除的元素是：%d\n", val);
    }
    else{
        printf("删除失败!\n");
    }
    
/*
    if( Append_arr(&arr, 7) ){
        printf("追加成功！\n");
    }
    else{
        printf("追加失败\n");
    }
*/
    Show_arr(&arr);
    Inversion_arr(&arr);
    printf("倒置之后的数组内容是：\n");
    Show_arr(&arr);
    Sort_arr(&arr);
    printf("排序后的数组内容是:\n");
    Show_arr(&arr);
    
    return 0;
}

void Init_arr(struct Arr* pArr, int len)
{
    pArr->pBase = (int*)malloc(sizeof(int)* len);
    if(NULL == pArr->pBase)
    {
        printf("动态分配内存失败！\n");
        exit(-1);   //终止整个程序
    }
    else
    {
        pArr->len = len;
        pArr->cnt = 0;
    }
    return;     //表示此函数终止了，增强可读性
}

void Get_arr(struct Arr* pArr, int val){
    if( Is_empty(pArr) )
        printf("获取下标失败！\n");
    else
    {
        for(int i=0; i<pArr->cnt; i++){
            if(pArr->pBase[i] == val)
            {
                printf("%d的数组下标为：", val);
                printf("%d\n", i);
            }
        }
    }
}

bool Is_empty(struct Arr* pArr)
{
    if(0 == pArr->cnt)
        return true;
    else
        return false;
}

bool Is_full(struct Arr* pArr)
{
    if(pArr->cnt == pArr->len)
        return true;
    else
        return false;
}

void Show_arr(struct Arr* pArr){	//此处的pArr来自arr，即结构体变量地址
    if(Is_empty(pArr))
    {		
    //*pArr错误，此处应该接收结构体变量的地址，而pArr已经是了，不需要加*
        printf("数组为空!\n");
    }
    else
    {
        for(int i=0; i<pArr->cnt; i++)
        {
            printf("%d ", pArr->pBase[i]);		
            //pArr[i],(*pArr[i])错误，因为都不是数组名
        }
        printf("\n");
    }
}

bool Append_arr(struct Arr* pArr, int val){
    //满时返回false
    if( Is_full(pArr) )
        return false;
    //不满时追加
    else
    {
        //是cnt，不是cnt+1，不是cnt-1————试数，下标与数组关系
        pArr->pBase[pArr->cnt] = val;
        (pArr->cnt)++;
        return true;
    }
}

//pos的值从1开始，即插入后的次序
bool Insert_arr(struct Arr* pArr, int pos, int val){
    if(Is_full(pArr))
        return false;
    
    if(pos<1 || pos>pArr->cnt+1)	//pos不能为负，不能大于有效个数+1
        return false;
    
    //i的值-不用记，试数，画图就行了
    for(int i=pArr->cnt-1; i>=pos-1; i--){
        pArr->pBase[i+1] = pArr->pBase[i];
    }
    pArr->pBase[pos-1] = val;
    (pArr->cnt)++;
    
    return true;
}

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];
    for(int i=pos; i<pArr->cnt; i++){
        pArr->pBase[i-1] = pArr->pBase[i];
    }
    pArr->cnt--;
    
    return true;
}

void Inversion_arr(struct Arr* pArr){
    int t;
    
    for(int i=0; i<pArr->cnt/2; i++){
        t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[pArr->cnt-1-i];
        pArr->pBase[pArr->cnt-1-i] = t;
    }
}

void Sort_arr(struct Arr* pArr){
    int t;
    
    for(int i=0; i<pArr->cnt-1; i++){
        for(int j=i+1; j<pArr->cnt; j++){
            if(pArr->pBase[i] > pArr->pBase[j]){
                t = pArr->pBase[i];
                pArr->pBase[i] = pArr->pBase[j];
                pArr->pBase[j] = t;
            }
        }
    }
}

---

其中Inversion_arr翻转数组可以使用折半方法：

void Inversion_arr(struct Arr* pArr){
    int t;
    
    for(int i=0; i<pArr->cnt/2; i++){
        t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[pArr->cnt-1-i];
        pArr->pBase[pArr->cnt-1-i] = t;
    }
}

相比于下面这种方法：

void Inversion_arr(struct Arr* pArr){
    int i = 0, j = pArr->cnt-1, t;
    
    while(i<j){
        t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[j];
        pArr->pBase[j] = t;
        i++;
        j--;
    }
}

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

下面再看查找数组，相信你已经猜到了，当然是二分啦！

void Get_arr(struct Arr* pArr, int val){
    if( Is_empty(pArr) ){
        printf("获取下标失败！\n");
    }
    else{
        for(int i=0;i<pArr->cnt;i++){
            if(pArr->pBase[i] == val){
                printf("%d的数组下标为：", val);
                printf("%d\n", i);
            }
        }
    }
}

上面这种方法是最笨、但也是最容易理解的方法，但是效率太低了。
那么就对它使用二分吧：

//第一种：左闭右闭
int Get_arr(struct Arr* pArr, int val){
    int left = 0;
    int right = pArr->cnt-1;
    
    while(left <= right){		
        int middle = (left + right)/2;
        if(val < pArr->pBase[middle]){
            right = middle-1;
        }
        else if(val > pArr->pBase[middle]){
            left = middle+1;
        }
        else
            return middle;
    }
    return -1;
}

//第二种：左闭右开
int Get_arr_2(struct Arr* pArr, int val){
    int left = 0;
    int right = pArr->cnt;
    
    while(left < right){		
        int middle = (left + right)/2;
        if(val < pArr->pBase[middle]){
            right = middle;
        }
        else if(val > pArr->pBase[middle]){
            left = middle+1;
        }
        else
            return middle;
    }
    return -1;
}