学习笔记：线性表的顺序表示和实现(二级指针实现)

“理想主义的花，最终会盛开在浪漫主义的土壤里，我的热情永远不会熄灭在现实的平凡之中”

线性表的顺序表示和实现（二级指针实现）

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

线性表的定义：

struct DynamicArray{
    
	//数组存储元素空间的首地址
	void **addr;
	//存储数据内存中最大能够容纳多少元素
	int capacity; //容量
	//当前存储数据的内存中有多少个元素
	int size; //大小 
}; 

基础操作：

1. 初始化数组

//初始化数组
struct DynamicArray * Init_DynamicArray(int capacity)
{
    
	if(capacity <= 0){
    
		return NULL;
	}   
	struct DynamicArray *arr = (struct DynamicArray *)malloc(sizeof(struct DynamicArray));
	if(NULL == arr){
    
		return NULL;
	}
	arr->capacity = capacity;
	arr->addr = (void**)malloc(sizeof(void*)*arr->capacity);
	arr->size = 0;
	
	return arr; 
}

2. 插入数组

算法思路：

1. 如果指针为空，插入位置不合理，抛出异常。
2. 如果线性表长度大于等于数组容量，则抛出异常或增加容量。
3. 从最后一个元素开始向前遍历到第pos个位置，分别将他们都向后移动一个位置；
4. 将要插入的元素填入位置pos处。
5. 表长加1。

void Insert_DynamicArray(struct DynamicArray *arr,int pos,void *data){
    
	if(NULL == arr){
        //判断指针是否为空 
		return;
	}
	if(NULL == data){
    
		return;
	}
	if(pos < 0 || pos > arr->size){
    
		pos = arr->size;
	}
	
	//判断空间是否足够
	if(arr->size >= arr->capacity){
    
		//1.申请了一块更大的内存空间 
		int newcapacity = arr->capacity*2;
		void **newspace = (void**)malloc(sizeof(void*)*newcapacity);
		
		//2. 将原来空间的数据拷贝到新空间
		memcpy(newspace,arr->addr,sizeof(void*)*arr->capacity);
		
		//3.释放原来空间的内存
		free(arr->addr);
		
		//4.更新addr指向
		arr->addr = newspace;
		arr->capacity =  newcapacity;
		
	} 
	
	//移动元素，给pos位置空出位置来
	for(int i = arr->size-1; i>= pos; --i){
    
		arr->addr[i+1] = arr->addr[i];
	} 
	
	//将新元素插入到pos位置
	arr->addr[pos] = data; 
	arr->size++;
}

3. 删除元素

3.1 位置删除

算法思路：

1. 如果指针为空，删除位置不合理，抛出异常。
2. 从删除元素位置开始遍历到最后一个元素位置，分别将他们向前移动一个位置。
3. 表长减1。

//位置删除
void RemoveByPos_DynamicArray(struct DynamicArray *arr,int pos){
    
	if (NULL == arr){
    
		return;
	}
	
	if(pos < 0|| pos > arr->size-1){
    
		return;
	} 
	for (int i = pos; i <arr->size-1; i++)   //覆盖位置元素即可 
	{
    
		arr->addr[i] = arr->addr[i+1];
	}
	
	arr->size--;
}

3.2 按值删除

//按值删除
void RemoveByValue_DynamicArray(struct DynamicArray *arr, void *data, int(*compare)(void*, void *))
//注意：不是单纯的比较地址，而是比较指定内容是否符合comepare规则。
{
    
	if (NULL == arr)
	{
    
		return;
	}

	if (NULL == data)
	{
    
		return;
	}

	if (NULL == compare)
	{
    
		return;
	}

	int i;
	for (i = 0; i < arr->size; ++i)
	{
    
		if (compare(arr->addr[i], data))
		{
    
			RemoveByPos_DynamicArray(arr, i);
			break;
		}
	}

}

4. 遍历数组

//遍历
void myPrint(void *data)
{
    
	struct Person *person = (struct Person *)data;
	printf("Name:%s Age:%d\n",person->name,person->age);
}

void Foreach_DynamicArray(struct DynamicArray *arr,void(*_callback)(void*)){
    
	if(NULL == arr){
    
		return;
	}
	if(NULL == _callback){
    
		return;
	}
	
	for(int i = 0; i < arr->size; ++i){
    
		_callback(arr->addr[i]);
	}
}

5.销毁数组

//销毁数组
void Destory_DynamicArray(struct DynamicArray *arr){
    
	if (NULL == arr){
    
		return;
	}
	if (arr->addr!=NULL){
    
		free(arr->addr);
		arr->addr = NULL;
	}
	
	free(arr);
	arr = NULL; 
} 

操作测试：

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

int myCompare(void *d1,void *d2)
{
    
	struct Person *p1 = (struct Person *)d1;
	struct Person *p2 = (struct Person *)d2;

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

void test(){
    
	//创建动态数组 
	struct DynamicArray *da = Init_DynamicArray(5);
	//动态数组添加元素
	struct Person p1 = {
    "aaa",10};
	struct Person p2 = {
    "bbb",20};
	struct Person p3 = {
    "ccc",30};
	struct Person p4 = {
    "ddd",40};
	struct Person p5 = {
    "eee",50};
	struct Person p6 = {
    "fff",60};
	
	
	Insert_DynamicArray(da,0,&p1);
	Insert_DynamicArray(da,0,&p2);
	Insert_DynamicArray(da,0,&p3);
	Insert_DynamicArray(da,1,&p4);
	Insert_DynamicArray(da,1,&p5);
	
	printf("capacity:%d\n",da->capacity);
	Insert_DynamicArray(da,100,&p6);  //3,5,4,2,1,6
	printf("capacity:%d\n",da->capacity);
	
	
	Foreach_DynamicArray(da,myPrint);
	
	printf("---------------------------\n");
	RemoveByPos_DynamicArray(da,2);
	Foreach_DynamicArray(da,myPrint);

	printf("---------------------------\n");	
	struct Person pDel = {
    "aaa",10};
	RemoveByValue_DynamicArray(da,&pDel,myCompare);

	da->addr = NULL;

	Foreach_DynamicArray(da, myPrint);

	销毁
	Destory_DynamicArray(da);
}

小结：
数组：一次性分配一块连续的存储区域。

• ​ 优点：随机访问元素效率高。
• ​ 缺点：
• 1.需要分配一块连续的存储区域（很大区域，有可能分配失败）。
  2.删除和插入某个元素效率低。

小张学长呕心沥血之作，若有错误之处请多多指正。若有帮助，可以点赞关注哦！！！