数据结构（六）连续存储数组算法

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
//定义了一个数据类型，该数据类型的名字叫做struct Arr,该数据类型含义三个成员
struct Arr {
     int *pBase; //存储数组第一个元素的地址
     int len;    //数组所能容纳的最大元素的个数
     int cnt;    //当前数组有效元素的个数
};
void init_arr(struct Arr *pArr, int length);    //初始化数组
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 get();    //获取元素
bool is_empty(struct Arr *pArr);    //判断是否为空
bool is_full(struct Arr *pArr);        //判断是否满
void sort_arr(struct Arr *pArr);    //对数组进行排序
void show_arr(struct Arr *pArr);    //输出数组
void inversion_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, 2);
     append_arr(&arr, -3);
     append_arr(&arr, 4);
     append_arr(&arr, 10);
     append_arr(&arr, 3);
     insert_arr(&arr,3,2);
     if ( delete_arr(&arr,1,&val)) {
         printf("删除成功！\n");
     printf("您删除的元素是：%d\n", val);
     } else {
          printf("删除失败！\n");
     }
     show_arr(&arr);
     inversion_arr(&arr);
     printf("倒置之后：");
     show_arr(&arr);
     sort_arr(&arr);
     printf("\n排序之后：");
     show_arr(&arr);
     return 0;
}

void init_arr(struct Arr *pArr, int length) {
    //为数组元素申请内存空间，空间大小是数组的长度
    pArr->pBase = (int *)malloc(sizeof(int)*length);
    //如果数组第一个元素中没有值，说明申请内存空间失败
    if (NULL == pArr->pBase) {
        printf("分配失败！");
        exit(-1);
    } else {
        //赋予数组的长度以及当前数组元素的个数
        pArr->len = length;
        pArr->cnt = 0;
    }
    return;
}

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

void show_arr(struct Arr * pArr) {
    if (is_empty(pArr)) {
        printf("数组为空！\n");
    } else {
        for (int i = 0; i < pArr->cnt; ++i) {
            printf("%d ", pArr->pBase[i]);
        }
        printf("\n");
    }
}

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

bool append_arr(struct Arr * pArr, int val) {
   if (is_full(pArr)) {
       printf("数组已满！");
       return false;
   } else {
       pArr->pBase[pArr->cnt] = val;
       (pArr->cnt)++;
       return true;
   }
}

bool insert_arr(struct Arr *pArr, int pos, int val) {
    //临时存放当前元素的位置
    int i;
    //数组已满的时候无法插入
    if (is_full(pArr)) {
        return false;
    }
    //在第一个元素之前无法插入，在最后一个元素之后没法插入
    if (pos<1  pos > pArr->len+1) {
        return false;
    }
    //pos之后的元素往后移动，找到最后一个元素的下标，开始的位置是pos-1
    for(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) {
    int i;
    //如果没有元素也就无法删除
    if (is_empty(pArr)) {
        return false;
    }
    
    if (pos<1  pos > pArr->len+1) {
        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 i = 0;
    int j = pArr->cnt-1;
    int t;
    while (i < j) {
        t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[j];
        pArr->pBase[j] = t;
        i++;
        j--;
    }
}

void sort_arr(struct Arr * pArr) {
    //排序：使用的是冒泡排序算法
    int i, j, t;
     for (i = 0; i < pArr->cnt; ++i) {
          for (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;
               }
          }
     }
}