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

Source

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


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

在这里插入图片描述


线性表的顺序表示和实现(二级指针实现)

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

在这里插入图片描述

线性表的定义:

在这里插入图片描述

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.删除和插入某个元素效率低。

在这里插入图片描述
小张学长呕心沥血之作,若有错误之处请多多指正。若有帮助,可以点赞关注哦!!!