C语言 数据结构之连续存储数组的算法

数据结构之数组定义及基本操作

　　数据结构中最基本的一个结构就是线性结构，而线性结构又分为连续存储结构和离散存储结构。所谓的连续存储结构其实就是数组。

　　数组本质其实也是数据的一种存储方式，既然有了数据的存储，就会涉及到如何对数据进行寻址的问题。首先，先说一下在数组中数据是如何存储的，在内存中，数组中的数据是以一组连续的数据集合的形式存在于内存中。当我们访问存在于内存中的数组时，我们应该找到其在内存中的地址，当我们找到数据的地址后我们就可以找到对应的数据。了解了以上知识后，我们就可以进行数组的设计了（我们就可以设计自己的数组供别人去使用了，哈哈）。

　　了解了以上知识后，第一个问题就来了，如何才能找到数据在内存中的地址？这个问题其实很简单，因为数组在内存中是一组连续的数据集合，所以我们只要知道数组首地址，然后通过对应字节长度的加减就可以找到对应字节数的数据，有了这些就可以定义出我们的数组，但是，作为一个合理的数组，还应该有数组长度的标志len和数组有效元素的标志cnt。由此给出对数组的定义（本例中采用结构体，对结构体不了解的朋友可以去查一下）

struct Arr
{
  int *pbase; //存储的是数组的第一个元素的地址
  int len; //数组所能容纳的最大元素的个数
  int cnt; //数组有效元素的个数  

};

上述代码定义了一个struct Arr的结构体，这个结构体就是一个数组，其中有存储数组元素中首地址的成员，有存储数组长度和数组有效元素个数的成员。

　　有了对结构体的定义之后，就应该涉及到对数组的基本操作，包括数组的初始化，判断数组是否为空，对数组进行显示，判断数组是否已满，对数组的最后追加一个元素，对数组元素的插入。其中，主要的算法就是对数组元素的插入，插入算法的核心就是首先应该先将被插入及插入位置之后的元素后移，然后将空出来的位置插入我们要插入的元素。一下给出c语言的实现：

void init_arr(struct Arr * pArr,int len)
{
  pArr->pbase=(int *)malloc(sizeof(int)*len);
  if(NULL==pArr->pbase){
    printf("动态内存分配失败");
    exit(-1); //终止整个程序 
  }
  else{
    pArr->len=len;
    pArr->cnt=0;
  }
}

 
int is_empty(struct Arr * pArr){
  if(pArr->cnt==0){
    return 0;  //0代表true 
  }
  else{
    return 1;  //1代表false 
  }
}


void show_arr(struct Arr * pArr){  
  if(is_empty(pArr)==0){
    printf("当前数组为空！");
  }
  else{
    int i;
    for(i=0; icnt; ++i){
      printf("%d  ",pArr->pbase[i]);
    }
    printf("n");
  }
}


int is_full(struct Arr * pArr){
  if(pArr->cnt==pArr->len){
    return 0; //0代表true，表示已满 
  }
  else{
    return 1; //1代表false，表示未满 
  }
}


int append_arr(struct Arr *pArr,int val){
  if(is_full(pArr)==0){
    return 0;
  }
  else{
    pArr->pbase[pArr->cnt]=val;
    pArr->cnt++;
    return 1;
  }
}


int insert_arr(struct Arr *pArr,int pos,int val){
  if(is_full(pArr)==0){
    return 0; //0表示当前数组已满，无法再进行插入 
  }  
  //在数组可插入的情况下，应该检查用户输入的pos位置值是否合理
  if(pos<0||pos>(pArr->len)){
    return 1; //1表示当前用户插入位置不合法 
  } 
  //移动位置 
  int i;
  for(i=pArr->cnt  -1;i>=pos-1;--i){
    pArr->pbase[i+1]=pArr->pbase[i];
  } 
  //空缺位置插入元素
  pArr->pbase[pos-1]=val;
  return 2; //2表示当前插入成功 
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！