首页 > 其他分享 >1.动态数组

1.动态数组

时间：2023-05-31 15:59:30浏览次数：47  
标签：struct int void DynamicArray pAddr 数组 array 动态

1.动态数组结构

  上图所示，该动态数组有3个元素，空间容量是6，每个元素类型为void*，因为void*可以接受任何类型指针，可以用来存各种类型指针。第一个元素地址为pAddr，第一个元素为*pAddr。

用结构体表示动态数组为：

//动态数组结构体
struct dynamicArray
{
	void** pAddr;//维护真实在堆区的数组的指针
	int m_capacity;//数组容量
	int m_size;//数组大小
};

对应上图m_size是3，m_capacity是6

2.动态数组的操作

2.1动态数组的初始化操作

//初始化数组
struct dynamicArray * init_DynamicArray(int capacity);
struct dynamicArray* init_DynamicArray(int capacity)
{
	if (capacity <= 0)
	{
		return NULL;
	}

	//给数组分配空间
	struct dynamicArray* array = malloc(sizeof(struct dynamicArray));//array为数组名，是第一个元素的地址
	if (array == NULL)//判断分配空间操作是否成功，不成功立即退出
	{
		return;
	}
	//给数组初始化
	array->pAddr = malloc(sizeof(void*) * capacity);
	array->m_capacity = capacity;
	array->m_size = 0;

	return array;
}

2.2动态数组的插入操作

//插入数组
void insert_DynamicArray(struct dynamicArray * array, int pos, void * data);
//array为需要做插入操作的数组，所插数据的插入位置为pos、值为data，这里是插入一个数据
void insert_DynamicArray(struct dynamicArray * array, int pos, void * data)
{
	if (array == NULL)//无法对未分配空间的数组做插入操作
	{
		return;
	}
	if (data == NULL)//无法插入一个无效值
	{
		return;
	}

	//无效位置  尾插
	if (pos < 0 || pos > array->m_size)
	{
		pos = array->m_size;
	}

	//判断是否满了，如果满动态扩展
	if (array->m_size == array->m_capacity)
	{
		//1、计算新空间大小   这里多分配空间，是防止多次分配空间，以空间换时间
		int newCapacity = array->m_capacity * 2;//array->m_capacity等价于(*array).m_capacity

		//2、创建新空间
		void ** newSpace = malloc(sizeof(void *)* newCapacity);//sizeof(void *)为每个元素大小

		//3、将原有数据拷贝到新空间下
		memcpy(newSpace, array->pAddr, sizeof(void *) * array->m_capacity);

		//4、释放原有内存空间
		free(array->pAddr);

		//5、更新新空间指向
		array->pAddr = newSpace;

		//6、更新新容量
		array->m_capacity = newCapacity;
	}

	//插入新元素

	//移动元素 进行插入新元素
	for (int i = array->m_size - 1; i >= pos; i--)//将插入位置后的元素先后移，从尾元素开始
	{
		//数据向后移动
		array->pAddr[i + 1] = array->pAddr[i];
	}

	//将新元素 插入到指定位置上
	array->pAddr[pos] = data;
	//更新大小
	array->m_size++;
}

2.3动态数组的遍历操作

//打印数组
void foreach_DynamicArray(struct dynamicArray * array, void(*myPrint)(void*));
void foreach_DynamicArray(struct dynamicArray * array, void(*myPrint)(void*))
{
	if (array == NULL)
	{
		return;
	}
	if (myPrint == NULL)
	{
		return;
	}

	for (int i = 0; i < array->m_size; i++)
	{
		myPrint(array->pAddr[i]);
	}
}

2.4动态数组的删除操作

//删除数组  按位置删除
void removeByPos_DynamicArray(struct dynamicArray * array, int pos)
{
	if (NULL == array)
	{
		return;
	}

	if (pos < 0 || pos > array->m_size - 1)
	{
		return;
	}

	//数据前移
	for (int i = pos; i < array->m_size - 1; i++)
	{
		array->pAddr[i] = array->pAddr[i + 1];
	}

	//更新数组大小
	array->m_size--;
}

//按值删除数据
void removeByValue_DynamicArray(struct dynamicArray * array, void * data, int(*myCompare)(void *, void *))
{
	if (array == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	for (int i = 0; i < array->m_size; i++)
	{
		if (myCompare(array->pAddr[i], data))
		{
			//如果找到要删除的数据，i就是要删除的具体位置
			removeByPos_DynamicArray(array, i);
			break;
		}
	}
}


int myComparePerson(void * data1, void *data2)
{
	struct Person *  p1 = data1;
	struct Person *  p2 = data2;

	return  strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;
}

removeByValue_DynamicArray(array, &p, myComparePerson);

2.5销毁数组

//销毁数组
void destroy_DynamicArray(struct dynamicArray* array)
{
	if (array == NULL)
	{
		return;
	}

	if (array->pAddr != NULL)
	{
		free(array->pAddr);
		array->pAddr = NULL;
	}
    
	free(array);
	array = NULL;
}

3.完整代码

头文件：dynamicArray.h

#pragma  once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

//动态数组结构体
struct dynamicArray
{
	void ** pAddr; //维护真实在堆区创建的数组的指针

	int m_capacity;  // 数组容量

	int m_size;   //数组大小
};

//初始化数组
struct dynamicArray * init_DynamicArray(int capacity);

//插入数组
void insert_DynamicArray(struct dynamicArray * array, int pos, void * data);

//遍历数组
void foreach_DynamicArray(struct dynamicArray * array, void(*myPrint)(void*));

//删除数组  按位置删除
void removeByPos_DynamicArray(struct dynamicArray * array, int pos);

//按值删除数据
void removeByValue_DynamicArray(struct dynamicArray * array, void * data, int(*myCompare)(void *, void *));

//销毁数组
void destroy_DynamicArray(struct dynamicArray* array);

01 动态数组.c

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#include "dynamicArray.h"

////动态数组结构体
//struct dynamicArray
//{
//	void ** pAddr; //维护真实在堆区创建的数组的指针
//
//	int m_capacity;  // 数组容量
//
//	int m_size;   //数组大小
//};
//
//
////初始化数组
//struct dynamicArray * init_DynamicArray(int capacity)
//{
//	if (capacity <= 0)
//	{
//		return NULL;
//	}
//
//	//给数组分配空间
//
//	struct dynamicArray * array  = malloc(sizeof(struct dynamicArray));
//	if (array == NULL)
//	{
//		return NULL;
//	}
//
//	//给数组初始化
//	array->pAddr = malloc(sizeof(void *)* capacity);
//	array->m_capacity = capacity;
//	array->m_size = 0;
//	
//	return array;
//}
//
////插入数组
//void insert_DynamicArray(struct dynamicArray * array , int pos  , void * data)
//{
//	if ( array == NULL)
//	{
//		return;
//	}
//	if ( data == NULL)
//	{
//		return;
//	}
//
//	//无效位置  尾插
//	if (pos < 0 || pos > array->m_size)
//	{
//		pos = array->m_size;
//	}
//
//	//判断是否满了，如果满动态扩展
//	if (array->m_size == array->m_capacity)
//	{
//		//1、计算新空间大小
//		int newCapacity = array->m_capacity * 2;
//
//		//2、创建新空间
//		void ** newSpace = malloc(sizeof(void *)* newCapacity);
//
//		//3、将原有数据拷贝到新空间下
//		memcpy(newSpace, array->pAddr, sizeof(void *)* array->m_capacity);
//
//		//4、释放原有内存空间
//		free(array->pAddr);
//
//		//5、更新新空间指向
//		array->pAddr = newSpace;
//
//		//6、更新新容量
//		array->m_capacity = newCapacity;
//	}
//
//	//插入新元素
//
//	//移动元素 进行插入新元素
//	for (int i = array->m_size - 1; i >= pos; i--)
//	{
//		//数据向后移动
//		array->pAddr[i + 1] = array->pAddr[i];
//	}
//
//	//将新元素 插入到指定位置上
//	array->pAddr[pos] = data;
//	//更新大小
//	array->m_size++;
//}
//
//
////遍历数组
//void foreach_DynamicArray(struct dynamicArray * array, void(*myPrint)(void*))
//{
//	if (array == NULL)
//	{
//		return;
//	}
//	if (myPrint == NULL)
//	{
//		return;
//	}
//
//	for (int i = 0; i < array->m_size;i++)
//	{
//		myPrint(array->pAddr[i]);
//	}
//}
//
//
////删除数组  按位置删除
//void removeByPos_DynamicArray(struct dynamicArray * array , int pos)
//{
//	if ( NULL == array)
//	{
//		return;
//	}
//
//	if (pos < 0  || pos > array->m_size - 1)
//	{
//		return;
//	}
//
//	//数据前移
//	for (int i = pos; i < array->m_size - 1;i++)
//	{
//		array->pAddr[i] = array->pAddr[i + 1];
//	}
//
//	//更新数组大小
//	array->m_size--;
//
//}
//
////按值删除数据
//void removeByValue_DynamicArray(struct dynamicArray * array , void * data , int (* myCompare)(void * ,void *))
//{
//	if ( array == NULL)
//	{
//		return;
//	}
//	if ( data == NULL)
//	{
//		return;
//	}
//
//	for (int i = 0; i < array->m_size;i++)
//	{
//		if (myCompare(array->pAddr[i], data))
//		{
//				//如果找到要删除的数据，i就是要删除的具体位置
//			removeByPos_DynamicArray(array, i);
//			break;
//		}
//	}
//
//}
//
////销毁数组
//void destroy_DynamicArray(struct dynamicArray* array)
//{
//	if (array == NULL)
//	{
//		return;
//	}
//
//	if (array->pAddr != NULL)
//	{
//		free(array->pAddr);
//		array->pAddr = NULL;
//	}
//
//
//	free(array);
//	array = NULL;
//}
//

//测试
struct Person
{
	char name[64];
	int age;
};


void myPrintPerson(void *data)
{
	struct Person * p = data;
	printf("姓名： %s 年龄：%d\n", p->name, p->age);

}

int myComparePerson(void * data1, void *data2)
{
	struct Person *  p1 = data1;
	struct Person *  p2 = data2;

	return  strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;
}

int main(){

	//初始化动态数组
	struct dynamicArray * array = init_DynamicArray(5);

	//准备数据
	struct Person p1 = { "亚瑟", 18 };
	struct Person p2 = { "妲己", 20 };
	struct Person p3 = { "安琪拉", 19 };
	struct Person p4 = { "凯", 21 };
	struct Person p5 = { "孙悟空", 999 };
	struct Person p6 = { "李白", 999};

	printf("插入数据前： 容量：%d  大小：%d\n", array->m_capacity, array->m_size);

	//插入数据
	insert_DynamicArray(array, 0, &p1);
	insert_DynamicArray(array, 0, &p2);
	insert_DynamicArray(array, 1, &p3);
	insert_DynamicArray(array, 0, &p4);
	insert_DynamicArray(array, -1, &p5);
	insert_DynamicArray(array, 2, &p6);

	// 凯 妲己 李白 安琪拉  亚瑟  孙悟空

	//遍历数据
	foreach_DynamicArray(array, myPrintPerson);


	printf("插入数据后： 容量：%d  大小：%d\n", array->m_capacity, array->m_size);


	//测试删除 按位置删除
	removeByPos_DynamicArray(array, 2);
	printf("---------------------\n");
	foreach_DynamicArray(array, myPrintPerson);
	printf("删除数据后： 容量：%d  大小：%d\n", array->m_capacity, array->m_size);

	struct Person  p = { "亚瑟", 18 };
	removeByValue_DynamicArray(array, &p, myComparePerson);
	printf("---------------------\n");
	foreach_DynamicArray(array, myPrintPerson);
	printf("删除数据后： 容量：%d  大小：%d\n", array->m_capacity, array->m_size);


	//array->pAddr = NULL;
	//array->m_capacity = 0;
	//array->m_size = 0;

	//销毁数组
	destroy_DynamicArray(array);
	array = NULL;

	system("pause");
	return EXIT_SUCCESS;
}

dynamicArray.c

#include "dynamicArray.h"

//初始化数组
struct dynamicArray * init_DynamicArray(int capacity)
{
	if (capacity <= 0)
	{
		return NULL;
	}

	//给数组分配空间

	struct dynamicArray * array = malloc(sizeof(struct dynamicArray));
	if (array == NULL)
	{
		return NULL;
	}

	//给数组初始化
	array->pAddr = malloc(sizeof(void *)* capacity);
	array->m_capacity = capacity;
	array->m_size = 0;

	return array;
}

//插入数组
void insert_DynamicArray(struct dynamicArray * array, int pos, void * data)
{
	if (array == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	//无效位置  尾插
	if (pos < 0 || pos > array->m_size)
	{
		pos = array->m_size;
	}

	//判断是否满了，如果满动态扩展
	if (array->m_size == array->m_capacity)
	{
		//1、计算新空间大小
		int newCapacity = array->m_capacity * 2;

		//2、创建新空间
		void ** newSpace = malloc(sizeof(void *)* newCapacity);

		//3、将原有数据拷贝到新空间下
		memcpy(newSpace, array->pAddr, sizeof(void *)* array->m_capacity);

		//4、释放原有内存空间
		free(array->pAddr);

		//5、更新新空间指向
		array->pAddr = newSpace;

		//6、更新新容量
		array->m_capacity = newCapacity;
	}

	//插入新元素

	//移动元素 进行插入新元素
	for (int i = array->m_size - 1; i >= pos; i--)
	{
		//数据向后移动
		array->pAddr[i + 1] = array->pAddr[i];
	}

	//将新元素 插入到指定位置上
	array->pAddr[pos] = data;
	//更新大小
	array->m_size++;
}


//遍历数组
void foreach_DynamicArray(struct dynamicArray * array, void(*myPrint)(void*))
{
	if (array == NULL)
	{
		return;
	}
	if (myPrint == NULL)
	{
		return;
	}

	for (int i = 0; i < array->m_size; i++)
	{
		myPrint(array->pAddr[i]);
	}
}


//删除数组  按位置删除
void removeByPos_DynamicArray(struct dynamicArray * array, int pos)
{
	if (NULL == array)
	{
		return;
	}

	if (pos < 0 || pos > array->m_size - 1)
	{
		return;
	}

	//数据前移
	for (int i = pos; i < array->m_size - 1; i++)
	{
		array->pAddr[i] = array->pAddr[i + 1];
	}

	//更新数组大小
	array->m_size--;

}

//按值删除数据
void removeByValue_DynamicArray(struct dynamicArray * array, void * data, int(*myCompare)(void *, void *))
{
	if (array == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	for (int i = 0; i < array->m_size; i++)
	{
		if (myCompare(array->pAddr[i], data))
		{
			//如果找到要删除的数据，i就是要删除的具体位置
			removeByPos_DynamicArray(array, i);
			break;
		}
	}

}

//销毁数组
void destroy_DynamicArray(struct dynamicArray* array)
{
	if (array == NULL)
	{
		return;
	}

	if (array->pAddr != NULL)
	{
		free(array->pAddr);
		array->pAddr = NULL;
	}

	free(array);
	array = NULL;
}

参考资料来源：

黑马程序员

标签：struct,int,void,DynamicArray,pAddr,数组,array,动态
From： https://www.cnblogs.com/codemagiciant/p/17446358.html

相关文章

  • Web - js数组对象去重
    letarr=[{id:'1',key:'1',value:'明月'},{id:'3',key:'2',value:'可欣'}}]Map()方法set方法设置key所对应的键值，然后返回整个Map结构。如果key已经有值，则键值会被更新，否则就新生成该键。values方法可......
  • 循环数组的最大子段和
    题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1050 题意：给定一个长度为50000的数组，求它的循环数组的最大子段和。分析：本题与普通的最大子段和问题不同的是，最大子段和可以是首尾相接的情况，即可以循环。那么这个题目的最    大子段和有两种情况    ......
  • Java中常见转换-数组与list互转、驼峰下划线互转、Map转Map、List转Map、进制转换的多
    场景Java中数组与List互转的几种方式数组转List1、最简单的方式,Arrays.asList(array);创建的是不可变列表，不能删除和新增元素String[]array=newString[]{"a","b"};List<String>stringList=Arrays.asList(array);System.out.println(strin......
  • C/C++杂记：运行时类型识别（RTTI）与动态类型转换原理
    运行时类型识别（RTTI）的引入有三个作用：配合typeid操作符的实现；实现异常处理中catch的匹配过程；实现动态类型转换dynamic_cast。1.typeid操作符的实现1.1.静态类型的情形C++中支持使用typeid关键字获取对象类型信息，它的返回值类型是conststd::type_info&，例：#include<type......
  • 1439. 有序矩阵中的第 k 个最小数组和
    给你一个m *n的矩阵mat，以及一个整数k，矩阵中的每一行都以非递减的顺序排列。你可以从每一行中选出1个元素形成一个数组。返回所有可能数组中的第k个最小数组和。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/find-the-kth-smallest-sum-of-a-matrix-with-so......
  • 二分法应用——搜索旋转数组，以前一直在纠结a[0],a[-1],a[mid], target三者关系，其实最
    62·搜索旋转排序数组  描述给定一个有序数组，但是数组以某个元素作为支点进行了旋转(比如，0124567可能成为4567012)。给定一个目标值target进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。你可以假设数组中不存在重复的元素。背完这套刷题模板，真......
  • 多维数组遍历
    #include<stdio.h>intmain(){intarr[][3]={{1,2},{3,4,5}};inti=0;intj=0;intlen=0;for(i=0;i<2;i++){for(j=0;j<3;j++){printf("arr[%d][%d]:%d",i,j,arr[i][j]);}prin......
  • heapq 对有序的数组列表进行整体排序
     """功能：实现对有序的多个数组整体排序，获取topk个最小元素"""fromheapqimport*defheap_sort(arr,top_k):q=[]foriinrange(len(arr)):heappush(q,(arr[i][0],i,0))result=[]forkinrange(top_k):ifq:......
  • Gym - 101174F[(DSU)+树状数组]
    题目链接:https://vjudge.net/problem/Gym-101174F 解题思路:其实这题不同启发式合并也可以做，对rank排个序，然后在做个dfs序，把rank值小的先插入树状数组中更新，然后对每个节点查询它的dfs序的区间和就好了。对于DSU来说就更加无脑了，本来就是"暴力"，所以我们直接DSU再加一个树状数组维......
  • 动态IP地址的原理是什么？如何更换自己的网络IP？
    动态IP地址的原理是通过动态主机配置协议（DynamicHostConfigurationProtocol，DHCP）来分配和管理IP地址。DHCP是一种网络协议，它允许计算机在连接到网络时自动获取IP地址、子网掩码、默认网关和其他网络配置信息。当您连接到互联网或局域网时，您的计算机或路由器将发送DHCP请......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99