timg.jpg
数据结构是一门对程序员来说很重要的学科，最近开始学习数据结构，写下此系列随笔，仅当作个学习笔记。
数据结构中，有线性结构和非线性结构。
数组作为线性结构中的一种，学习它对于之后学习链表有很大的帮助。
以下是对数组以及一些简单功能的实现。
数组类型的定义
数组类型的定义应该包括如下参数：
typedef struct Arr{
int * pBase;//存放的是数组第一个元素的地址
int len;//存放的是数组所能容纳的最大元素的个数
int cnt;//当前数组存放的有效个数
}ARRAY,* PARRAY;
数组的初始化
所有涉及到内存分配的操作都应该对内存分配是否成功进行判断。
void init(PARRAY pArr,int length){
//根据传入的参数，分配相应长度的空间
pArr->pBase = (int *)malloc(sizeof(int) * length);
if(NULL == pArr->pBase){
printf("内存分配失败，程序终止\n");
exit(-1);
}else{
pArr->len = length;//数组长度为传入的参数
pArr->cnt = 0;//数组初始的有效个数为0
}
}
判断数组是否为空
判断数组是否为空很简单，只需要获取数组有效个数cnt即可。
bool is_empty(PARRAY pArr){
if(0 == pArr->cnt){
return true;
}else{
return false;
}
}
判断数组是否满了
判断数组是否满了同样不难，只需要比较有效个数和长度即可
bool is_full(struct Arr * pArr){
if(pArr->len == pArr->cnt){
return true;
}else{
return false;
}
}
数组的追加
没什么可说的，追加之前判断一下数组是否已满
bool append_arr(PARRAY pArr,int element){
if(is_full(pArr)){
//如果数组已经满了，那么添加失败，返回false
return false;
}else{
//如果数组不满，那么添加元素，同时有效个数自增
pArr->pBase[pArr->cnt] = element;
pArr->cnt++;
}
}
数组的遍历
同样没什么可说的，遍历到有效个数为止
void show_arr(PARRAY pArr){
int index;
if(is_empty(pArr)){
printf("数组为空\n");
}else{
printf("数组的元素为：");
for(index = 0;index < pArr->cnt;index++){
if(index == (pArr->cnt-1)){
//如果是最后一个元素，就输出带换行
printf("%d\n",pArr->pBase[index]);
}else{
printf("%d ",pArr->pBase[index]);
}
}
}
}
数组的插入
在插入之前要判断一下用户传入的index是否正确，这里index是在第index个元素前面插入，因此index必须满足大于等于1，并且小于等于有效个数加1，比如说，数组有5个元素，那么index的取值只能是1~6，1表示在数组最前面插入，6表示在数组最后面插入，如果index大于等于6，那么就会造成数组有一个空存储的位置，这违反了数组连续存储的结构。
插入的过程是：先从后往前把元素往后“挪移”，然后把index位置的值替换成传入的element
bool insert_arr(PARRAY * pArr,int index,int element){
int i;
if(is_full(pArr)){
return false;
}else{
if(index < 1 || index > pArr->cnt+1){
return false;
}else{
for(i = pArr->cnt - 1;i >= index-1;i--){
pArr->pBase[i+1] = pArr->pBase[i];
}
pArr->pBase[index-1] = element;
pArr->cnt++;
}
}
}
数组的删除
pVal是用来接收删除的元素的，在删除之前依旧是判断数组是否为空以及判断index是否正确。
bool delete_arr(PARRAY * pArr,int index,int * pVal){
int i;
if(is_empty(pArr)){
return false;
}
if(index < 1 || pArr->cnt < index){
return false;
}
//把要删除的元素保存起来
*pVal = pArr->pBase[index-1];
//删除元素
for(i = index-1;i <= pArr->cnt-2;i++){
//12345
pArr->pBase[i] = pArr->pBase[i+1];
}
pArr->cnt--;
return true;
}
数组的倒置
倒置的基本思想是：从数组的两边开始往中遍历比较、交换数值，直到一方超过另外一方
void inversion_arr(struct Arr * pArr){
int t;
int i = 0;
int j = pArr->cnt-1;
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;
//i是总共比较多少趟，有五个数就比四趟，有六个数就比五趟，比较一趟得出一个最大数，直到剩下一个数
for(i = 0;i < pArr->cnt-1;i++){
//j规定了每一趟比较的过程，最大值是到哪里
for(j = 0;j < pArr->cnt-i-1;j++){
if(pArr->pBase[j] > pArr->pBase[j+1]){
t = pArr->pBase[j];
pArr->pBase[j] = pArr->pBase[j+1];
pArr->pBase[j+1] = t;
}
}
}
}
至此，一个简单的数组就创建完毕，试验一下功能。
01.png
02.png
（首图为网上资源，如有侵权，请联系我，第一时间删除！）
有任何我写错或者理解错的地方，欢迎大家在评论区指出来！
