数组操作

数组操作说明

数组的常用操作主要包括，数组的初始化、数组元素的插入、数组元素的删除、数组追加元素、获取元素、数组排序、数组倒置以及数组的遍历等。

数组定义

数组的结构如下：

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

我们定义了一个数组结构 Arr，其有三个成员，具体每个成员的意思见上面的注释。

数组初始化

函数原型

int init_arr(struct Arr *pArray, int length); //初始化 

参数

参数	说明
pArray	需要初始化的数组的首地址。
length	数组的长度。

返回值

初始化成功返回 0，否则返回 1。

说明

使用 init_arr 初始化一个数组 pArray，并将其长度初始化为 length。

具体实现

int init_arr(struct Arr *pArray, int length)
{
    //使用malloc为数组的pBase字段分配内存，分配的内存大小为数组的长度乘以每个成员的字节大小
	pArray->pBase = (int*)malloc(sizeof(int)*length);
    //如果分配后的内存为 NULL，那么说明内存分配失败，直接返回
	if (NULL == pArray->pBase)
	{
		printf("动态内存分配失败!\n");
		return 1;
	}
	//分配为内存之后，还需要将数组的最大长度属性设置为length
	pArray->len = length;
    //将数组当前的元素个数设置为0
	pArray->cnt = 0;
	return 0;
}

注意

在调用 init_arr 函数时，第一个参数 pArray 不能为 NULL，如果为 NULL，那么这时候访问 pArray->pBase 程序会异常。

数组追加元素

函数原型

int append_arr(struct Arr *pArray, int val);  //追加

参数

参数	说明
pArray	需要追加的数组的首地址。
val	需要追加的元素。

返回值

初始化成功返回 0，否则返回 1。

说明

使用 append_arr 在数组的最后添加一个元素 val。

具体实现

int append_arr(struct Arr *pArray, int val)
{
    //如果数组已经满了，则直接返回
	if (is_full(pArray))
	{
		return 1;
	}
    //未添加元素之前数组的长度为cnt,数组的最大索引为cnt-1
    //因此，现在我们只需要将数组的索引为cnt的位置设置为需要插入的值即可
	pArray->pBase[pArray->cnt] = val;
    //插入了一个元素，需要将当前数组的长度加一
	(pArray->cnt)++;
	return 0;
}

注意

在调用 append_arr 函数时，第一个参数 pArray 不能为 NULL，如果为 NULL，那么这时候访问 pArray->pBase 程序会异常。

数组插入元素

函数原型

int insert_arr(struct Arr *pArray, int pos, int val); //插入元素

参数

参数	说明
pArray	需要插入的数组的首地址。
pos	需要插入的位置，从1开始，而不是从0开始。
val	需要插入的元素。

返回值

初始化成功返回 0，否则返回 1。

说明

使用 insert_arr 在数组的位置 pos 插入一个元素 val。

图解

首先，我们创建的数组如下图所示：

我们需要在 POS 的位置插入元素，我们将 POS 位置的所有元素往后移动一位，具体如下图所示：

此时 POS 位置为空，现在，我们直接将元素放入到 POS 位置，具体如下图所示：

此时，元素 POS 位置成功插入了元素 VAL。

具体实现

int insert_arr(struct Arr *pArray, int pos, int val)
{
    //判断数组是否已经满了
	if (is_full(pArray))
	{
		return 1;
	}
	//如果pos小于1或者pos已经大于了数组的最大索引，直接返回
	if (pos < 1 || pos >pArray->cnt+1)
	{
		return 1;
	}
    //首先，把从pos位置开始后面的所有元素往后移动一格
	int i = pArray->cnt-1;
	for(; i >= pos-1 ; --i)
	{
		pArray->pBase[i+1] = pArray->pBase[i];
	}
	//在pos位置（也就是索引为post-1）插入元素val 
	pArray->pBase[pos-1] = val;
    //将数组的长度加一
	(pArray->cnt)++;
	return 0;
}

注意

在调用 insert_arr 函数时，第一个参数 pArray 不能为 NULL，如果为 NULL，那么这时候访问 pArray->cnt 程序会异常。

数组删除元素

函数原型

int delete_arr(struct Arr *pArray, int pos, int *pVal);//删除元素

参数

参数	说明
pArray	需要删除的数组的首地址。
pos	需要删除的位置，从1开始，而不是从0开始。
pVal	删除后返回的元素的值。

返回值

初始化成功返回 0，否则返回 1。

说明

使用 delete_arr 在数删除组的位置 pos 出的元素，并将返回值赋值给 pVal。

具体实现

int delete_arr(struct Arr *pArr, int pos, int *pVal)
{
    //如果数组为空，直接返回
	if (is_empty(pArr))
	{
		return 1;
	}
    //如果删除的位置小于1或者大于数组的当前长度，直接返回
	if (pos < 1 || pos > pArr->cnt)
	{
		return 1;
	}
    //将要删除的值保存到返回值中
	*pVal = pArr->pBase[pos-1];
	int i = 0;
    //从索引pos开始，将后面的每一个元素向前移动一次即可
	for(i = pos; i < pArr->cnt; ++i)
	{
		pArr->pBase[i-1] = pArr->pBase[i];
	}
    //删除了一个元素，因此，整个长度减一
	pArr->cnt--;
	return 0;
}

判断数组为空

函数原型

int is_empty(struct Arr *pArray); //判断数组为空

参数

参数	说明
pArray	需要判断为空的数组的首地址。

返回值

如果数组为空返回 0，否则返回 1。

说明

判断数组 pArray 是否为空，如果为空，则返回 0，否则返回 1。

具体实现

int is_empty(struct Arr *pArray)
{
    //如果数组的当前长度cnt为0，则表明为空
	if(pArray->cnt == 0)
	{
		return 0;
	}
	return 1;
}

判断数组是否满

函数原型

int is_full(struct Arr *pArray);

参数

参数	说明
pArray	需要判断是否满的数组的首地址。

返回值

如果数组满了返回 0，否则返回 1。

说明

判断数组 pArray 是否满，如果满了，则返回 0，否则返回 1。

具体实现

int is_full(struct Arr *pArray)
{
    //直接判断数组的长度是否等于初始化的长度
    //如果相等，则说明数组满了，否则，就是数组未满
	if (pArray->len == pArray->cnt)
	{
		return 0;
	}
	return 1;
}

数组排序

函数原型

void sort_arr(struct Arr *pArray);

参数

参数	说明
pArray	需要排序的数组的首地址。

返回值

无返回值。

说明

该排序算法会修改原数组。

具体实现

void sort_arr(struct Arr *pArr)
{
	int i, j, t;
    //从数组索引0开始遍历，一直遍历到数组的长度减一
	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;
			}
		}
	}
}

技术细节

我们直接使用选择排序即可。

数组反转

函数原型

void inversion_arr(struct Arr *pArray);

参数

参数	说明
pArray	需要反转的数组的首地址。

返回值

无返回值。

说明

该反转算法会修改原数组。

图解

首先，我们创建的数组如下图所示：

现在，我们只需要将数组的第一个元素和最后一个元素互换位置，将第二个元素和倒数第二个元素互换位置，将第三个元素和倒数第三个元素互换位置，一直互换到数组的中间一个元素或者前后两个位置相遇即可，具体如下图所示：

互换完成后，数组如下图所示：

此时，整个数组的所有元素都交换完成，数组变成了逆序。

具体实现

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;
	}
	return 0;
}

数组遍历

函数原型

void show_arr(struct Arr *pArray);

参数

参数	说明
pArray	需要遍历的数组的首地址。

返回值

无返回值。

具体实现

void show_arr(struct Arr *pArray)
{
    //如果数组为空，则直接返回
	if (is_empty(pArray))
	{
		printf("数组内容为空\n");
		return;
	}
    //从索引0开始，挨着遍历到数组的长度即可
	int i = 0;
	for(i = 0; i < pArray->cnt; i++)
	{
		printf("%d ", pArray->pBase[i]);
	}
	printf("\n");
}

案例

数组操作的综合案例如下：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
struct Arr
{
	int *pBase; //存储的是数组的第一个元素的地址 
	int len;   //数组能容纳的最大元素的个数 
	int cnt;   //当前数组有效元素的个数 
};
//初始化数组
int init_arr(struct Arr *pArray, int length);
//数组追加元素
int append_arr(struct Arr *pArray, int val);
//在pos位置处插入元素val，pos的值从1开始 
int insert_arr(struct Arr *pArray, int pos, int val);
//删除数组pos出的元素，并将删除的值返回到pVal中
int delete_arr(struct Arr *pArray, int pos, int *pVal);
//判断数组是否为空
int is_empty(struct Arr *pArray);
//判断数组是否已满
int is_full(struct Arr *pArray);
//对数组排序
void sort_arr(struct Arr *pArray);
//倒叙数组
void inversion_arr(struct Arr *pArray);
//打印数组
void show_arr(struct Arr *pArray);
int main(void) 
{
    printf("嗨客网（www.haicoder.net）\n");
	struct Arr arr;
	//初始化数组的长度为6 
	init_arr(&arr, 6);
	//向数组里面添加五个元素 
	append_arr(&arr, 1);
	append_arr(&arr, 2);
	append_arr(&arr, 3);
	append_arr(&arr, 4);
	append_arr(&arr, 5);
	printf("\n============数组插入元素===========\n");
	//在数组的第一个位置插入元素100 
	insert_arr(&arr, 1, 100);
	//打印数组
	show_arr(&arr);
	printf("\n============数组删除元素===========\n");
	int deleteVal = 0;
	delete_arr(&arr, 3, &deleteVal);
	show_arr(&arr);
	printf("\n============逆序数组===========\n");
	inversion_arr(&arr);
	show_arr(&arr);
	printf("\n============数组排序===========\n");
	sort_arr(&arr);
	show_arr(&arr);
	return 0;
}
int init_arr(struct Arr *pArray, int length)
{
    //使用malloc为数组的pBase字段分配内存，分配的内存大小为数组的长度乘以每个成员的字节大小
	pArray->pBase = (int*)malloc(sizeof(int)*length);
    //如果分配后的内存为 NULL，那么说明内存分配失败，直接返回
	if (NULL == pArray->pBase)
	{
		printf("动态内存分配失败!\n");
		return 1;
	}
	//分配为内存之后，还需要将数组的最大长度属性设置为length
	pArray->len = length;
    //将数组当前的元素个数设置为0
	pArray->cnt = 0;
	return 0;
}
int append_arr(struct Arr *pArray, int val)
{
    //如果数组已经满了，则直接返回
	if (is_full(pArray) == 0)
	{
		return 1;
	}
    //未添加元素之前数组的长度为cnt,数组的最大索引为cnt-1
    //因此，现在我们只需要将数组的索引为cnt的位置设置为需要插入的值即可
	pArray->pBase[pArray->cnt] = val;
    //插入了一个元素，需要将当前数组的长度加一
	(pArray->cnt)++;
	return 0;
}
int insert_arr(struct Arr *pArray, int pos, int val)
{
    //判断数组是否已经满了
	if (is_full(pArray) == 0)
	{
		return 1;
	}
	//如果pos小于1或者pos已经大于了数组的最大索引，直接返回
	if (pos < 1 || pos >pArray->cnt+1)
	{
		return 1;
	}
    //首先，把从pos位置开始后面的所有元素往后移动一格
	int i = pArray->cnt-1;
	for(; i >= pos-1 ; --i)
	{
		pArray->pBase[i+1] = pArray->pBase[i];
	}
	//在pos位置（也就是索引为post-1）插入元素val 
	pArray->pBase[pos-1] = val;
    //将数组的长度加一
	(pArray->cnt)++;
	return 0;
}
int delete_arr(struct Arr *pArr, int pos, int *pVal)
{
    //如果数组为空，直接返回
	if (is_empty(pArr) == 0)
	{
		return 1;
	}
    //如果删除的位置小于1或者大于数组的当前长度，直接返回
	if (pos < 1 || pos > pArr->cnt)
	{
		return 1;
	}
    //将要删除的值保存到返回值中
	*pVal = pArr->pBase[pos-1];
	int i = 0;
    //从索引pos开始，将后面的每一个元素向前移动一次即可
	for(i = pos; i < pArr->cnt; ++i)
	{
		pArr->pBase[i-1] = pArr->pBase[i];
	}
    //删除了一个元素，因此，整个长度减一
	pArr->cnt--;
	return 0;
}
int is_empty(struct Arr *pArray)
{
    //如果数组的当前长度cnt为0，则表明为空
	if(pArray->cnt == 0)
	{
		return 0;
	}
	return 1;
}
int is_full(struct Arr *pArray)
{
    //直接判断数组的长度是否等于初始化的长度
    //如果相等，则说明数组满了，否则，就是数组未满
	if (pArray->len == pArray->cnt)
	{
		return 0;
	}
	return 1;
}
void sort_arr(struct Arr *pArr)
{
	int i, j, t;
    //从数组索引0开始遍历，一直遍历到数组的长度减一
	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;
			}
		}
	}
}
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;
	}
	return 0;
}
void show_arr(struct Arr *pArray)
{
    //如果数组为空，则直接返回
	if (is_empty(pArray) == 0)
	{
		printf("数组内容为空\n");
		return;
	}
    //从索引0开始，挨着遍历到数组的长度即可
	int i = 0;
	for(i = 0; i < pArray->cnt; i++)
	{
		printf("%d ", pArray->pBase[i]);
	}
	printf("\n");
}

程序运行后，输出如下：

我们看到，整个数组的操作运行结果如上所示。