笔记
实现一个可以动态申请内存的线性存储结构。例如在插入数据时判断容量是否够用,不够时申请一块更大的内存,将数据复制过去,然后释放之前的内存。
动态数组结构体.paddr(void **)指向一列(void*)的第一个,其中每个(void*)指向存放的数据
数据由用户自己维护,要注意可能会出现的作用域的问题
要实现的功能
初始化、插入、遍历、删除(按位置、值)和销毁
源码
myDynamicArray.c
#include "myDynamicArray.h"
#include<stdio.h>
#include<memory.h>
#include<stdlib.h>
void dynamicHello(){
printf("Hello\n");
}
//新建一个动态数组,参数是初始容量的大小
struct myDynamicArray * init_mda(int cap){
if(cap < 0){
return NULL;
}
struct myDynamicArray * arr = malloc( sizeof(struct myDynamicArray) ); //结构体只需要一个
if(NULL == arr){
return NULL;
}
arr->m_capacity = cap;
arr->m_size = 0;
arr->pAddr = malloc( sizeof(void *) * cap); //申请一块区域,存储void*,大小是容量;pAddr指向这块区域
if(NULL == arr->pAddr){
printf("init mda malloc cap failed\n");
free(arr);
return NULL;
}
return arr;
}
void insert_mda(struct myDynamicArray * arr, int pos, void *data){
if(NULL == arr){
return;
}
//printf("pos=%d\tsize=%d\tcapacity=%d\n", pos, arr->m_size, arr->m_capacity);
if(pos < 0 || pos > arr->m_size){
pos = arr->m_size; //如果位置比size大或不合理,转换成尾插
}
//如果已经满载
if(arr->m_size >= arr->m_capacity){
//重新malloc申请内存、释放之前
int newCapacity = arr->m_capacity * 2;
void ** tmpaddr = malloc( sizeof(void *) * newCapacity);
if(NULL == tmpaddr){
printf("re malloc failed\n");
return;
}
memcpy(tmpaddr, arr->pAddr, sizeof(void*) * arr->m_capacity); //拷贝数据,数据存的是void*指针
//不拷贝数据,遍历时每项的void*指向的都是空,直接访问会越界
free(arr->pAddr); //释放之前的数据头指针
arr->pAddr = tmpaddr;
arr->m_capacity = newCapacity;
}
//printf("addr=0x%X\n",arr->pAddr);
//如果插入的位置在中间,之后的数据要依次向后移动
for(int i=arr->m_size-1; i >=pos; i--){
arr->pAddr[i+1] = arr->pAddr[i];
}
arr->pAddr[pos] = data; //插入数据
arr->m_size++;
}
//遍历
void foreach_mda(struct myDynamicArray *arr, void(*myforeach)(void *) ) {
if(NULL == arr){
return;
}
if(NULL == myforeach){
return;
}
for(int i=0;i<arr->m_size;i++){
myforeach( arr->pAddr[i]);
}
}
//按位置删除元素
void removeByPos_mda(struct myDynamicArray *arr, int pos){
if(NULL == arr){
return;
}
if(pos < 0 || pos >= arr->m_size){
return;
}
for(int i=pos; i<arr->m_size-1; i++){
arr->pAddr[i] = arr->pAddr[i+1];
}
arr->m_size--;
}
//按值删除元素
void removeByVal_mda(struct myDynamicArray *arr,void * data, int(*myCompare)(void*,void*) ){
if(NULL == arr || NULL == data){
return;
}
for(int i=0;i<arr->m_size;i++){
if( myCompare( arr->pAddr[i], data) ){
removeByPos_mda(arr,i);
//break; //重复元素
}
}
}
//擦除所有
void erasure_mda(struct myDynamicArray *arr){
if(NULL == arr){
return;
}
if(arr->pAddr != NULL){
free(arr->pAddr);
arr->pAddr = NULL;
}
free(arr);
//arr = NULL; //arr在这赋值为NULL并不会改变全局的arr的值,相当于指针是值传递进来的,可以修改它指向的地方,但修改不了它
}
myDynamicArray.h
#ifndef __MY_DYNAMIC_ARRAY_H
#define __MY_DYNAMIC_ARRAY_H
struct myDynamicArray
{
void** pAddr; //指向存数据的指针
int m_size; //大小
int m_capacity; //容量
};
void dynamicHello(void);
struct myDynamicArray * init_mda(int cap);
void insert_mda(struct myDynamicArray * arr, int pos, void *data);
void foreach_mda(struct myDynamicArray *arr, void(*myforeach)(void *) );
void removeByPos_mda(struct myDynamicArray *arr, int pos);
void removeByVal_mda(struct myDynamicArray *arr,void * data, int(*myCompare)(void*,void*) );
void erasure_mda(struct myDynamicArray *arr);
#endif
start0.c
#include<stdio.h>
#include<string.h>
#include "myDynamicArray.h"
struct Persion
{
int m_age;
char m_name[64];
};
void myPrint(void * dat){
struct Persion *a = dat;
if(NULL == dat){ //防止访问出错
return;
}
printf("%d\t%s\n",a->m_age,a->m_name);
}
int myCompare(void* d1,void* d2){
struct Persion *p1 = d1;
struct Persion *p2 = d2;
if(p1->m_age == p2->m_age){
if(strcmp(p1->m_name,p2->m_name) == 0){ //strcmp比较两个char*指向的字符串,<0表示s1<s2,>0表示s1>s2,=0表示s1=s2
return 1;
}
}
return 0;
}
void test01(int * dat){
*dat = 10;
dat = NULL;
}
int main(int argc, char *argv[]){
struct Persion p1 = {10,"a"};
struct Persion p2 = {11,"b"};
struct Persion p3 = {12,"c"};
struct Persion p4 = {13,"d"};
struct Persion p5 = {14,"e"};
dynamicHello();
struct myDynamicArray * arr = init_mda(2);
insert_mda(arr,0,&p1);
insert_mda(arr,1,&p2);
insert_mda(arr,2,&p3);
insert_mda(arr,3,&p4);
insert_mda(arr,4,&p5);
foreach_mda(arr,myPrint);
printf("---------------------\n");
removeByPos_mda(arr,2);
foreach_mda(arr,myPrint);
printf("---------------------\n");
struct Persion p9 = p1;
removeByVal_mda(arr,&p9,myCompare);
foreach_mda(arr,myPrint);
printf("---------------------\n");
erasure_mda(arr);
arr = NULL;
if(NULL == arr){
printf(" m arr==NULL\n");
}else{
printf("m arr not NULL\n");
}
foreach_mda(arr,myPrint);
printf("---------------------\n");
return 0;
}