本文概述
- Java
- C#
可以通过分配固定大小的数组(通常大于立即需要的元素数量)来构造简单的动态数组。动态数组的元素连续存储在基础数组的开始处, 而到基础数组末尾的其余位置则保留或未使用。通过使用保留空间, 可以在恒定时间内将元素添加到动态数组的末尾, 直到该空间被完全消耗为止。
当所有空间都被消耗掉并且要添加一个附加元素时, 需要增加基础固定大小的数组的大小。通常, 调整大小是很昂贵的, 因为你必须分配一个更大的数组, 并从该数组中复制所有你已过度使用的元素, 然后才能最终添加项目。
方法：当我们在数组中输入一个元素但数组已满时, 你将创建一个函数, 该函数将创建一个新数组, 其大小为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 variablepublic DynamicArray()
{
array = new int [ 1 ];
count = 0 ;
size = 1 ;
}
// function add an element at the end of arraypublic 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 indexpublic 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: 16No of elements in array: 9Elements of array after shrinkSize of array:1 2 3 4 5 6 7 8 9 Size of array: 9No of elements in array: 9Elements 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: 18No of elements in array: 10Elements 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: 18No of elements in array: 9Elements 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: 18No of elements in array: 8推荐阅读
- 冠状病毒爆发如何结束（使用数据结构可视化）
- 热备路由器协议(HSRP)和虚拟路由器冗余协议(VRRP)介绍
- 算法题（Hosoya三角形介绍和代码实现）
- Hopcroft–Karp最大匹配算法S2（代码实现）
- 自学机器学习探索路|模型评估与选择
- 生活感悟|我注册了某音帐号之后。。。(内涵推荐算法)
- Haproxy配合Nginx搭建Web集群
- LVM与磁盘配额
- docker-Namespace隔离