数据结构动态数组

• 能被?计算机识别

• 计算机存储数据的方式 ，数据和数据之间的关系
• ?数据结构是算法需要处理的载体.
• ?数据结构分类
  • ?逻辑结构
    • ?集合结构
    • ?线性结构
      • ?一对一的关系 除了第一个元素只有一个前驱和最后一个元素只有后继? 其他元素各有一个前驱和后继
    • ?树形结构
      • ?一对多的关系 根节点没有前驱 页节点没有后继
    • ?图形结构
      • ?多对多的关系
  • ?物理结构
    • ?顺序存储
      • ?连续的空间
    • ?链式存储
      • ?独立的空间

• 特定问题解决步骤
• ?算法是为了解决实际问题而设计的

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//动态数组类
struct dynamicArray
{
??????? //数组地址
??????? void **m_addr;
??????? //数组大小
??????? int m_size;
??????? //数组容量
??????? int m_capacity;
};
//测试代码
struct Person
{
??????? char name[64];
??????? int age;
};

//初始化动态数组
struct dynamicArray *init_DynamicArray(int capacity);
//按位插入数据
void insert_DynamicArray(struct dynamicArray *array, int pos, void *data);
//遍历数据
void foreach_DynamicArray(struct dynamicArray *array, void (*myPrintf)(void *));
//按位删除数据
void removeByPos_DynamicArray(struct dynamicArray *array, int pos);
//按值删除数据
void removeByValue_DynamicArray(struct dynamicArray *array, void *data, int (*myComparePerson)(void *, void *));
//自定义表较
int myComparePerson(void *data1, void *data2);
//自定义打印
void myPrintPerson(void *data);
//删除数组
void destory_DynamicArray(struct dynamicArray *array);

//vim dynamicArray.c

#include"dynamicArray.h"
//初始化动态数组
struct dynamicArray *init_DynamicArray(int capacity)
{
?? ?//非法条件
?? ?if(capacity<=0)
?? ?return NULL;
?? ?//结构体分配堆空间
?? ?struct dynamicArray *array = malloc(sizeof(struct dynamicArray));
?? ?//分配失败
?? ?if(NULL==array)
?? ?return NULL;
?? ?//初始化数组
?? ?//为数组中每个空间分配地址
?? ?array->m_addr = 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)
?? ?{
?? ??? ?//扩大容量
?? ??? ?int newCapacity = array->m_capacity*2;
?? ??? ?//分配新数组
?? ??? ?void **newSpace = malloc(sizeof(void *)*newCapacity);
?? ??? ?//把之前的数组拷贝到新数组
?? ??? ?memcpy(newSpace, array->m_addr, sizeof(void *)*array->m_capacity);
?? ??? ?//释放之前的数组
?? ??? ?free(array->m_addr);
?? ??? ?//更新数组
?? ??? ?array->m_addr = newSpace;
?? ??? ?array->m_capacity = newCapacity;
?? ?}
?? ?//按位遍历数组中的元素
?? ?for(int i=array->m_size-1; i>=pos; i--)
?? ?{
?? ??? ?//个元素向后移动
?? ??? ?array->m_addr[i+1] = array->m_addr[i];
?? ?}
?? ?//按位插入数组
?? ?array->m_addr[pos] = data;
?? ?//更新数组大小
?? ?array->m_size++;
}
//遍历数组
void foreach_DynamicArray(struct dynamicArray *array, void (*myPrintf)(void *))
{
?? ?//非法条件
?? ?if(array==NULL)
?? ?return;
?? ?if(myPrintf==NULL)
?? ?return;
?? ?//遍历
?? ?for(int i=0; i<array->m_size; i++)
?? ?{
?? ??? ?//callback
?? ??? ?myPrintf(array->m_addr[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->m_addr[i] = array->m_addr[i+1];
?? ?}
?? ?//更新数组大小
?? ?array->m_size--;
}
//按值删除
void removeByValue_DynamicArray(struct dynamicArray *array, void *data, int (*myComparePerson)(void *, void *))
{
?? ?//非法条件
?? ?if(NULL==array)
?? ?return;
?? ?if(NULL==data)
?? ?return;
?? ?//遍历
?? ?for(int i=0; i<array->m_size; i++)
?? ?{
?? ??? ?//callback对比条件成立
?? ??? ?if(myComparePerson(array->m_addr[i], data))
?? ??? ?{
?? ??? ??? ?//成立后按位删除 i是成立元素
?? ??? ??? ?removeByPos_DynamicArray(array, i);
?? ??? ??? ?//跳出条件
?? ??? ??? ?break;
?? ??? ?}
?? ?}
}
//自定义callback
int myComparePerson(void *data1, void *data2)
{
?? ?struct Person *p1 = data1;
?? ?struct Person *p2 = data2;
?? ?//strcmp字符串比较函数
?? ?return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;
}
//自定义print
void myPrintPerson(void *data)
{
?? ?struct Person *p = data;
?? ?printf("姓名:%s 年龄:%d\n", p->name, p->age);
}
//删除数组
void destory_DynamicArray(struct dynamicArray *array)
{?? ?
?? ?//非法条件
?? ?if(NULL==array)
?? ?return;
?? ?//释放数组中元素
?? ?if(NULL!=array->m_addr)
?? ?{
?? ??? ?free(array->m_addr);
?? ??? ?array->m_addr = NULL;
?? ?}
?? ?//释放数组
?? ?free(array);
?? ?array = NULL;
}

int main()
{
?? ?//初始化动态数组
?? ?struct dynamicArray *array = init_DynamicArray(5);
?? ?//printf
?? ?printf("size=%dcapacity=%d\n", array->m_size, array->m_capacity);
?? ?//测试代码
?? ?//初始化Person结构体
?? ?struct Person p1 = {"小明", 20};
?? ?struct Person p2 = {"小红", 20};
?? ?struct Person p3 = {"小李", 21};
?? ?struct Person p4 = {"小额", 22};
?? ?struct Person p5 = {"小敏", 23};
?? ?struct Person p6 = {"小小", 24};
?? ?//往数组插入数据
?? ?insert_DynamicArray(array, 0, &p1);
?? ?insert_DynamicArray(array, 1, &p2);
?? ?insert_DynamicArray(array, 2, &p3);
?? ?insert_DynamicArray(array, 3, &p4);
?? ?insert_DynamicArray(array, 4, &p5);
?? ?insert_DynamicArray(array, 5, &p6);
?? ?//遍历数组中的数据
?? ?foreach_DynamicArray(array, myPrintPerson);
?? ?printf("size=%dcapacity=%d\n", array->m_size, array->m_capacity);
?? ?//按位删除数组中元素
?? ?removeByPos_DynamicArray(array, 0);
?? ?foreach_DynamicArray(array, myPrintPerson);
?? ?printf("size=%dcapacity=%d\n", array->m_size, array->m_capacity);
?? ?//按值删除数组中元素
?? ?struct Person p7 = {"小小", 24};
?? ?removeByValue_DynamicArray(array, &p7, myComparePerson);
?? ?foreach_DynamicArray(array, myPrintPerson);
?? ?printf("size=%dcapacity=%d\n", array->m_size, array->m_capacity);
?? ?return 0;
}