一、什么样的数据结构同时具备数组和链表的优点

一种同时具备数组和链表优点的数据结构是动态数组（Dynamic Array），也被称为可扩展数组（Resizable Array）。动态数组在底层使用的是数组，但是它可以根据需要动态地增加或减少数组的大小，因此它具有数组的随机访问特性。

同时，动态数组还可以在数组末尾快速添加或删除元素，这一点类似于链表操作，因此它也具有链表的灵活性。因此，动态数组既可以支持高效随机访问，又可以在需要时动态改变其大小，方便地进行插入、删除等操作，是一种非常实用的数据结构。在很多编程语言和标准库中都已经提供了动态数组的实现。

二、动态数组简介

在实际的编程中，往往会发生这种情况，即所需的内存空间取决于实际输入的数据，而无法预先确定。对于这种问题，用静态数组的办法很难解决。为了解决上述问题，C语言提供了一些内存管理函数，这些内存管理函数结合指针可以按需要动态地分配内存空间，来构建动态数组，也可把不再使用的空间回收待用，为有效地利用内存资源提供了手段。

动态数组，是相对于静态数组而言。静态数组的长度是预先定义好的，在整个程序中，一旦给定大小后就无法改变。而动态数组则不然，它可以随程序需要而重新指定大小。动态数组的内存空间是从堆（heap）上分配（即动态分配）的。是通过执行代码而为其分配存储空间。当程序执行到这些语句时，才为其分配。程序员自己负责释放内存。

1、为什么要使用动态数组

在实际的编程中，往往会发生这种情况，即所需的内存空间取决于实际输入的数据，而无法预先确定。对于这种问题，用静态数组的办法很难解决。为了解决上述问题，C语言提供了一些内存管理函数，这些内存管理函数结合指针可以按需要动态地分配内存空间，来构建动态数组，也可把不再使用的空间回收待用，为有效地利用内存资源提供了手段。

2、动态数组与静态数组的对比

对于静态数组，其创建非常方便，使用完也无需释放，要引用也简单，但是创建后无法改变其大小是其致命弱点。对于动态数组，其创建麻烦，使用完必须由程序员自己释放，否则严重会引起内存泄露。但其使用非常灵活，能根据程序需要动态分配大小。

3、如何构建动态数组

遵循原则：

申请的时候从外层往里层，逐层申请；释放的时候从里层往外层，逐层释放。

构建所需指针：

对于构建一维动态数组，需要一维指针；对于二维，则需要一维，二维指针；三维需要一，二，三维指针；依此类推。

构建所需函数：

void *malloc(unsigned int size)：成功，返回所开辟空间首地址；失败，返回空指针。作用为向系统申请size字节的 堆空间。void *calloc(unsigned int num,unsigned int size)：成功，返回所开辟空间首地址；失败，返回空指针。作用为按类型申请num个size字节的堆空间。void free(void *p)：无返回值。作用为释放p指向的堆空间。void *realloc(void *p,unsigned int size)：成功，返回新开辟空间首地址；失败，返回空指针。作用为将p指向的堆空间变为size。

说明：

规定为 void * 类型，这并不是说该函数调用后无返回值，而是返回一个结点的地址，该地址的类型为void（无类型或类型不确定），即一段存储区的首址，其具体类型无法确定，只有使用时根据各个域值数据再确定。可以用强制转换的方法将其转换为别的类型。例如：double *pd=NULL; pd=(double *)calloc(10,sizeof(double)); 表示将向系统申请10个连续的 double类型的存储空间，并用指针pd指向这个连续的空间的首地址。并且用(double)对calloc()的返回类型进行转换，以便把double类型数据的地址赋值给指针pd。使用sizeof的目的是用来计算一种类型的占有的字节数，以便适合不同的编译器。由于动态分配不一定成功，为此要附加一段异常处理程序，不致程序运行停止，使用户不知所措。通常采用这样的异常处理程序段： if(p==NULL) /* 或者 if（!p）*/ { printf(“动态申请内存失败！\n”); exit(1); //异 常退出 } 。这四个函数头文件均包含在中。分配的堆空间是没有名字的只能通过返回的指针找到它。绝不能对非动态分配存储块使用free。也不能对同一块内存区同时用free释放两次。 如：free(p);free(p); 。调用 free() 时, 传入指针指向的内存被释放, 但调用函数的指针值可能保持不变，因为p是作为形参而传递给了函数。严格的讲，被释放的指针值是无效的，因为它已不再指向所申请的内存区。这时对它的任何使用便可能会可带来问题。

malloc与calloc的区别：

对于用malloc分配的内存区间，如果原来没有被使用过，则其中的每一位可能都是0；反之，如果这部分内存空间曾经被分配、释放和重新分配，则其中可能遗留各种各样的数据。也就是说，使用malloc()函数的程序开始时（内存空间还没有被重新分配）能正常运行，但经过一段时间后（内存空间已被重新分配）可能会出现问题，因此在使用它之前必须先进行初始化（可用memset函数对其初始化为0），但调用calloc()函数分配到的空间在分配时就已经被初始化为0了。 当你在calloc()函数和malloc()函数之间作选择时，你需考虑是否要初始化所分配的内存空间，从而来选择相应的函数。

具体构建方法：

以三维整型数组array[n1][n2][n3]为例。

先遵循从外层到里层，逐层申请的原则：

最外层指针是array，它是个三维指针，所指向的是array[]，其为二维指针。所以给array申请内存应：

array=(int***)calloc(n1,sizeof(int**));

次层指针是array[]，它是个二维指针，所指向的是array[][]，其为一维指针。所以给array[]申请内存应：

for(i=0;i
最内层指针是array[][]，它是个一维指针，所指向的是array[][][]，其是个整型常量。所以给array[][]申请内存应：
for(i=0;i
当然，你可以把它们整合在一起为：
int i,j,k;int n1,n2,n3;int ***array;scanf("%d%d%d",&n1,&n2,&n3);array=(int***)calloc(n1,sizeof(int**));for(i=0;i
最后不要忘了释放这些内存，这要遵循释放的时候从里层往外层，逐层释放的原则：
for(i=0;i
延伸阅读1：数组与链表的优点有哪些
数组的优点：
随机访问性强查找速度快
链表的优点：
插入和删除效率低可能浪费内存内存空间要求高，必须有足够的连续内存空间数组大小固定，不能动态拓展              

                声明：本站稿件版权均属千锋教育所有，未经许可不得擅自转载。
              
              
              

  

    
10年以上业内强师集结，手把手带你蜕变精英
    

      
      
    
    

      
      
    
    
请您保持通讯畅通，专属学习老师24小时内将与您1V1沟通
    

      免费领取

    
  
  

    
今日已有369人领取成功
    

      

        

          刘同学 138****2860 刚刚成功领取
        
        

          王同学 131****2015 刚刚成功领取
        
        

          张同学 133****4652 刚刚成功领取
        
        

          李同学 135****8607 刚刚成功领取
        
        

          杨同学 132****5667 刚刚成功领取
        
        

          岳同学 134****6652 刚刚成功领取
        
        

          梁同学 157****2950 刚刚成功领取
        
        

          刘同学 189****1015 刚刚成功领取
        
        

          张同学 155****4678 刚刚成功领取
        
        

          邹同学 139****2907 刚刚成功领取
        
        

          董同学 138****2867 刚刚成功领取
        
        

          周同学 136****3602 刚刚成功领取
        
      
    
  

              

                                
                  

                    
                  
                  

                    
上一篇
                    databaseschema和databaseinstance有什么区别?
                  
                
                                
                  

                    
                  
                  

                    
下一篇
                    C#的开发，什么时候用到了栈的先进后出机制?