动态数组是如何工作和实现的？

本文概述

Java
C#

动态数组(C ++中的向量, Java中的ArrayList)会在我们尝试插入时自动增长, 而新项目没有更多空间了。通常, 该区域的大小会增加一倍。

可以通过分配固定大小的数组(通常大于立即需要的元素数量)来构造简单的动态数组。动态数组的元素连续存储在基础数组的开始处, 而到基础数组末尾的其余位置则保留或未使用。通过使用保留空间, 可以在恒定时间内将元素添加到动态数组的末尾, 直到该空间被完全消耗为止。

当所有空间都被消耗掉并且要添加一个附加元素时, 需要增加基础固定大小的数组的大小。通常, 调整大小是很昂贵的, 因为你必须分配一个更大的数组, 并从该数组中复制所有你已过度使用的元素, 然后才能最终添加项目。

方法：当我们在数组中输入一个元素但数组已满时, 你将创建一个函数, 该函数将创建一个新数组, 其大小为double值, 或者根据你的需要, 将所有元素从先前数组复制到新数组中, 并返回此新数组。另外, 我们可以减小数组的大小。并在给定位置添加元素, 然后在默认位置和该位置移除该元素。

动态阵列的主要功能

添加元素：如果数组大小不足, 请在末尾添加元素, 然后扩展数组的大小, 并在原始数组和给定索引的末尾添加元素。完成所有复制操作需要O(n)时间, 其中n是数组中元素的数量。附加费用很高。在固定长度的数组中, 追加仅花费O(1)时间。

但是, 只有在我们插入完整数组时, 追加操作才会占用O(n)时间。这是非常罕见的, 特别是如果每次空间用完时我们将数组的大小加倍。因此, 在大多数情况下, 附加时间仍为O(1)时间, 有时为O(n)时间。

在动态数组中, 可以在需要时创建固定大小的数组, 并在数组中添加更多元素, 然后使用以下方法：

删除元素：从数组中删除元素, 默认为remove()方法, 从末尾删除元素, 仅在最后一个索引处存储零, 还可以通过调用i为索引的removeAt(i)方法在特定索引处删除元素。 removeAt(i)方法将所有右元素从给定索引移到左侧。

调整数组大小：当数组右侧的数据为空/零(不包括由你添加)时, 该数组将占用未返回的内存, 则srinkSize()方法将释放额外的内存。当所有空间都被消耗掉并且要添加一个附加元素时, 则基础固定大小的数组需要增加大小。通常, 调整大小是很昂贵的, 因为你必须分配一个更大的数组, 并从该数组中复制所有你已过度使用的元素, 然后才能最终添加项目。

动态数组的简单代码。在下面的代码中, 数组将变为完整大小, 我们将所有元素复制到新的double大小数组(可变大小数组)中。示例代码如下

Java

// Java program deals with all operation of a dynamic array
// add, remove, resize memory of array is the main feature
public class DynamicArray {
  
     // create three variable array[] is a array, // count will deal with no of element add by you and
     // size will with size of array[]
     private int array[];
     private int count;
     private int size;
     // constructor initialize value to variable
  
     public DynamicArray()
     {
         array = new int [ 1 ];
         count = 0 ;
         size = 1 ;
     }
     // function add an element at the end of array
  
     public void add( int data)
     {
  
         // check no of element is equql to size of array
         if (count == size) {
             growSize(); // make array size double
         } // insert element at end of array
         array[count] = data;
         count++;
     }
  
     // function makes size double of array
     public void growSize()
     {
  
         int temp[] = null ;
         if (count == size) {
  
             // temp is a double size array of array
             // and store array elements
             temp = new int [size * 2 ];
             {
                 for ( int i = 0 ; i < size; i++) {
                     // copy all array value into temp
                     temp[i] = array[i];
                 }
             }
         }
  
         // double size array temp initialize
         // into variable array again
         array = temp;
         
         // and make size is double also of array
         size = size * 2 ;
     }
  
     // function shrink size of array
     // which block unnecessary remove them
     public void shrinkSize()
     {
         int temp[] = null ;
         if (count > 0 ) {
  
             // temp is a count size array
             // and store array elements
             temp = new int [count];
             for ( int i = 0 ; i < count; i++) {
  
                 // copy all array value into temp
                 temp[i] = array[i];
             }
  
             size = count;
  
             // count size array temp initialize 
             // into variable array again
             array = temp;
         }
     }
     // function add an element at given index
  
     public void addAt( int index, int data)
     {
         // if size is not enough make size double
         if (count == size) {
             growSize();
         }
  
         for ( int i = count - 1 ; i >= index; i--) {
  
             // shift all element right 
             // from given index
             array[i + 1 ] = array[i];
         }
  
         // insert data at given index
         array[index] = data;
         count++;
     }
  
     // function remove last element or put
     // zero at last index
     public void remove()
     {
         if (count > 0 ) {
             array[count - 1 ] = 0 ;
             count--;
         }
     }
  
     // function shift all element of right
     // side from given index in left
     public void removeAt( int index)
     {
         if (count > 0 ) {
             for ( int i = index; i < count - 1 ; i++) {
  
                 // shift all element of right 
                 // side from given index in left
                 array[i] = array[i + 1 ];
             }
             array[count - 1 ] = 0 ;
             count--;
         }
     }
  
     public static void main(String[] args)
     {
         DynamicArray da = new DynamicArray();
  
         // add 9 elements in array
         da.add( 1 );
         da.add( 2 );
         da.add( 3 );
         da.add( 4 );
         da.add( 5 );
         da.add( 6 );
         da.add( 7 );
         da.add( 8 );
         da.add( 9 );
  
         // print all array elements after add 9 elements
         System.out.println( "Elements of array:" );
         for ( int i = 0 ; i < da.size; i++) {
             System.out.print(da.array[i] + " " );
         }
  
         System.out.println();
  
         // print size of array and no of element
         System.out.println( "Size of array: " + da.size);
         System.out.println( "No of elements in array: " +
                                               da.count);
  
         // shrinkSize of array
         da.shrinkSize();
  
         // print all array elements
         System.out.println( "Elements of array " + 
                    "after shrinkSize of array:" );
         for ( int i = 0 ; i < da.size; i++) {
             System.out.print(da.array[i] + " " );
         }
         System.out.println();
  
         // print size of array and no of element
         System.out.println( "Size of array: " + da.size);
         System.out.println( "No of elements in array: " + 
                                                da.count);
  
         // add an element at index 1
         da.addAt( 1 , 22 );
  
         // print Elements of array after adding an
         // element at index 1
         System.out.println( "Elements of array after" + 
                       " add an element at index 1:" );
         for ( int i = 0 ; i < da.size; i++) {
             System.out.print(da.array[i] + " " );
         }
  
         System.out.println();
  
         // print size of array and no of element
         System.out.println( "Size of array: " + da.size);
         System.out.println( "No of elements in array: " + 
                                                da.count);
  
         // delete last element
         da.remove();
  
         // print Elements of array after delete last 
         // element
         System.out.println( "Elements of array after" + 
                               " delete last element:" );
         for ( int i = 0 ; i < da.size; i++) {
             System.out.print(da.array[i] + " " );
         }
  
         System.out.println();
  
         // print size of array and no of element
         System.out.println( "Size of array: " + da.size);
         System.out.println( "No of elements in array: " + 
                                               da.count);
  
         // delete element at index 1
         da.removeAt( 1 );
  
         // print Elements of array after delete
         // an element index 1
         System.out.println( "Elements of array after" + 
                       " delete element at index 1:" );
         for ( int i = 0 ; i < da.size; i++) {
             System.out.print(da.array[i] + " " );
         }
         System.out.println();
  
         // print size of array and no of element
         System.out.println( "Size of array: " + da.size);
         System.out.println( "No of elements in array: " +
                                                da.count);
     }
}

C#

// C# program deals with all operation 
// of dynamic array add, remove, resize 
// memory of array is the main feature
using System;
  
public class DynamicArray 
{
  
     // create three variable array[] is 
     // a array, count will deal with no 
     // of element add by you and
     // size will with size of array[]
     private int []array;
     private int count;
     private int size;
      
     // constructor initialize value to variable
     public DynamicArray()
     {
         array = new int [1];
         count = 0;
         size = 1;
     }
  
     // function add an element at the end of array
     public void add( int data)
     {
  
         // check no of element is equql to size of array
         if (count == size) 
         {
             growSize(); // make array size double
         } 
          
         // insert element at end of array
         array[count] = data;
         count++;
     }
  
     // function makes size double of array
     public void growSize()
     {
  
         int []temp = null ;
         if (count == size) 
         {
  
             // temp is a double size array of array
             // and store array elements
             temp = new int [size * 2];
             {
                 for ( int i = 0; i < size; i++) 
                 {
                     // copy all array value into temp
                     temp[i] = array[i];
                 }
             }
         }
  
         // double size array temp initialize
         // into variable array again
         array = temp;
          
         // and make size is double also of array
         size = size * 2;
     }
  
     // function shrink size of array
     // which block unnecessary remove them
     public void shrinkSize()
     {
         int []temp = null ;
         if (count > 0) 
         {
  
             // temp is a count size array
             // and store array elements
             temp = new int [count];
             for ( int i = 0; i < count; i++) 
             {
  
                 // copy all array value into temp
                 temp[i] = array[i];
             }
  
             size = count;
  
             // count size array temp initialize 
             // into variable array again
             array = temp;
         }
     }
      
     // function add an element at given index
     public void addAt( int index, int data)
     {
         // if size is not enough make size double
         if (count == size)
         {
             growSize();
         }
  
         for ( int i = count - 1; i >= index; i--)
         {
  
             // shift all element right 
             // from given index
             array[i + 1] = array[i];
         }
  
         // insert data at given index
         array[index] = data;
         count++;
     }
  
     // function remove last element or put
     // zero at last index
     public void remove()
     {
         if (count > 0) 
         {
             array[count - 1] = 0;
             count--;
         }
     }
  
     // function shift all element of right
     // side from given index in left
     public void removeAt( int index)
     {
         if (count > 0)
         {
             for ( int i = index; i < count - 1; i++) 
             {
  
                 // shift all element of right 
                 // side from given index in left
                 array[i] = array[i + 1];
             }
             array[count - 1] = 0;
             count--;
         }
     }
  
     // Driver code
     public static void Main()
     {
         DynamicArray da = new DynamicArray();
  
         // add 9 elements in array
         da.add(1);
         da.add(2);
         da.add(3);
         da.add(4);
         da.add(5);
         da.add(6);
         da.add(7);
         da.add(8);
         da.add(9);
  
         // print all array elements after add 9 elements
         Console.WriteLine( "Elements of array:" );
         for ( int i = 0; i < da.size; i++) 
         {
             Console.Write(da.array[i] + " " );
         }
  
         Console.WriteLine();
  
         // print size of array and no of element
         Console.WriteLine( "Size of array: " + da.size);
         Console.WriteLine( "No of elements in array: " +
                                             da.count);
  
         // shrinkSize of array
         da.shrinkSize();
  
         // print all array elements
         Console.WriteLine( "Elements of array " + 
                 "after shrinkSize of array:" );
         for ( int i = 0; i < da.size; i++) 
         {
             Console.Write(da.array[i] + " " );
         }
         Console.WriteLine();
  
         // print size of array and no of element
         Console.WriteLine( "Size of array: " + da.size);
         Console.WriteLine( "No of elements in array: " + 
                                             da.count);
  
         // add an element at index 1
         da.addAt(1, 22);
  
         // print Elements of array after adding an
         // element at index 1
         Console.WriteLine( "Elements of array after" + 
                     " add an element at index 1:" );
         for ( int i = 0; i < da.size; i++) 
         {
             Console.Write(da.array[i] + " " );
         }
  
         Console.WriteLine();
  
         // print size of array and no of element
         Console.WriteLine( "Size of array: " + da.size);
         Console.WriteLine( "No of elements in array: " + 
                                             da.count);
  
         // delete last element
         da.remove();
  
         // print Elements of array after delete last 
         // element
         Console.WriteLine( "Elements of array after" + 
                             " delete last element:" );
         for ( int i = 0; i < da.size; i++) 
         {
             Console.Write(da.array[i] + " " );
         }
  
         Console.WriteLine();
  
         // print size of array and no of element
         Console.WriteLine( "Size of array: " + da.size);
         Console.WriteLine( "No of elements in array: " + 
                                             da.count);
  
         // delete element at index 1
         da.removeAt(1);
  
         // print Elements of array after delete
         // an element index 1
         Console.WriteLine( "Elements of array after" + 
                     " delete element at index 1:" );
         for ( int i = 0; i < da.size; i++) 
         {
             Console.Write(da.array[i] + " " );
         }
         Console.WriteLine();
  
         // print size of array and no of element
         Console.WriteLine( "Size of array: " + da.size);
         Console.WriteLine( "No of elements in array: " +
                                             da.count);
     }
}
  
/* This code contributed by PrinciRaj1992 */

输出如下：

Elements of array:
1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 
Size of array: 16
No of elements in array: 9
Elements of array after shrinkSize of array:
1 2 3 4 5 6 7 8 9 
Size of array: 9
No of elements in array: 9
Elements of array after add an element at index 1:
1 22 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 
Size of array: 18
No of elements in array: 10
Elements of array after delete last element:
1 22 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 
Size of array: 18
No of elements in array: 9
Elements of array after delete element at index 1:
1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 
Size of array: 18
No of elements in array: 8

本文概述

动态阵列的主要功能

Java

C#

相关推荐

评论抢沙发

评论前必须登录！

猜你喜欢

热门标签

回顶部

本文概述

动态阵列的主要功能

Java

C#

相关推荐

评论 抢沙发

评论前必须登录！

猜你喜欢

热门标签

回顶部

评论抢沙发