数据结构&算法 插入数组



  • 数组插入

    在上一节中,我们了解了插入操作的工作方式。不一定总是在数组末尾插入元素。以下可能是数组插入的情况-
    • 在数组开头插入
    • 在数组的给定索引处插入
    • 在数组的给定索引之后插入
    • 在数组的给定索引之前插入
  • 在数组开头插入

    当插入发生在开始时,它将导致所有现有数据项向下移动一级。在这里,我们设计并实现了一种在数组的开头插入元素的算法。
    我们假设A是一个有N个元素的数组。它可以存储的元素的最大数量由MAX定义。我们将首先检查数组是否有空白空间来存储任何元素,然后继续执行插入过程。
    
    begin
    
    IF N = MAX, return
    ELSE
       N = N + 1
       
       For All Elements in A
          Move to next adjacent location
          
       A[FIRST] = New_Element
       
    end
    
    
    C语言实现
    
    #include <stdio.h>
    
    #define MAX 5
    
    void main() {
       int array[MAX] = {2, 3, 4, 5};
       int N = 4;        // number of elements in array
       int i = 0;        // loop variable
       int value = 1;    // new data element to be stored in array
    
       // print array before insertion
       printf("Printing array before insertion −\n");
       
       for(i = 0; i < N; i++) {
          printf("array[%d] = %d \n", i, array[i]);
       }
    
       // now shift rest of the elements downwards   
       for(i = N; i >= 0; i--) {
          array[i+1] = array[i];
       }
    
       // add new element at first position
       array[0] = value;
    
       // increase N to reflect number of elements
       N++;
    
       // print to confirm
       printf("Printing array after insertion −\n");
       
       for(i = 0; i < N; i++) {
          printf("array[%d] = %d\n", i, array[i]);
       }
    }
    
    
    当我们编译并执行上述程序时,它将产生以下结果
    
    Printing array before insertion −
    array[0] = 2
    array[1] = 3
    array[2] = 4
    array[3] = 5
    Printing array after insertion −
    array[0] = 0
    array[1] = 2
    array[2] = 3
    array[3] = 4
    array[4] = 5 
    
    
  • 在数组的给定索引处插入

    在这种情况下,我们获得了需要在其中插入新数据元素(值)的数组的确切位置(索引)。首先,我们将检查数组是否已满,如果不是,则将所有数据元素从该位置向下移动一步。这将为新的数据元素腾出空间。
    我们假设A是具有N个元素的数组。它可以存储的最大元素数由MAX定义。
    
    begin
    
    IF N = MAX, return
    ELSE
       N = N + 1
       
       SEEK Location index
       
       For All Elements from A[index] to A[N]
          Move to next adjacent location
    
       A[index] = New_Element
       
    end  
    
    
    C语言实现
    
    #include <stdio.h>
    
    #define MAX 5
    
    void main() {
       int array[MAX] = {1, 2, 4, 5};
       
       int N = 4;        // number of elements in array
       int i = 0;        // loop variable
       int index = 2;    // index location to insert new value
       int value = 3;    // new data element to be inserted
    
       // print array before insertion
       printf("Printing array before insertion −\n");
    
       for(i = 0; i < N; i++) {
          printf("array[%d] = %d \n", i, array[i]);
       }
    
       // now shift rest of the elements downwards   
       for(i = N; i >= index; i--) {
          array[i+1] = array[i];
       }
    
       // add new element at first position
       array[index] = value;
    
       // increase N to reflect number of elements
       N++;
    
       // print to confirm
       printf("Printing array after insertion −\n");
    
       for(i = 0; i < N; i++) {
          printf("array[%d] = %d\n", i, array[i]);
       }
    }
    
    
    当我们编译并执行上述程序时,它将产生以下结果
    
    Printing array before insertion −
    array[0] = 1
    array[1] = 2
    array[2] = 4
    array[3] = 5
    Printing array after insertion −
    array[0] = 1
    array[1] = 2
    array[2] = 3
    array[3] = 4
    array[4] = 5 
    
    
  • 在数组的给定索引之后插入

    在这种情况下,我们将获得数组的位置(索引),之后必须插入新的数据元素(值)。只有查找过程有所不同,其余活动与前面的示例相同。
    我们假设A是具有N个元素的数组。它可以存储的最大元素数由MAX定义。
    
    begin
    
    IF N = MAX, return
    ELSE
       N = N + 1
       
       SEEK Location index
       
       For All Elements from A[index + 1] to A[N]
          Move to next adjacent location
          
       A[index + 1] = New_Element
       
    end  
    
    
    C语言实现
    
    #include <stdio.h>
    
    #define MAX 5
    
    void main() {
       int array[MAX] = {1, 2, 4, 5};
       
       int N = 4;        // number of elements in array
       int i = 0;        // loop variable
       int index = 1;    // index location after which value will be inserted
       int value = 3;    // new data element to be inserted
    
       // print array before insertion
       printf("Printing array before insertion −\n");
    
       for(i = 0; i < N; i++) {
          printf("array[%d] = %d \n", i, array[i]);
       }
    
       // now shift rest of the elements downwards   
       for(i = N; i >= index + 1; i--) {
          array[i + 1] = array[i];
       }
    
       // add new element at first position
       array[index + 1] = value;
    
       // increase N to reflect number of elements
       N++;
    
       // print to confirm
       printf("Printing array after insertion −\n");
    
       for(i = 0; i < N; i++) {
          printf("array[%d] = %d\n", i, array[i]);
       }
    }
    
    
    当我们编译并执行上述程序时,它将产生以下结果
    
    Printing array before insertion −
    array[0] = 1
    array[1] = 2
    array[2] = 4
    array[3] = 5
    Printing array after insertion −
    array[0] = 1
    array[1] = 2
    array[2] = 3
    array[3] = 4
    array[4] = 5
    
    
  • 在数组的给定索引之前插入

    在这种情况下,我们将获得一个数组的位置(索引),在该位置之前必须插入一个新的数据元素(值)。这次我们一直搜索到索引1,即给定索引之前的一个位置,其余活动与前面的示例相同。
    我们假设A是具有N个元素的数组。它可以存储的最大元素数由MAX定义。
    
    begin
    
    IF N = MAX, return
    ELSE
       N = N + 1
       
       SEEK Location index
       
       For All Elements from A[index - 1] to A[N]
          Move to next adjacent location
          
       A[index - 1] = New_Element
       
    end   
    
    
    C语言实现
    
    #include <stdio.h>
    
    #define MAX 5
    
    void main() {
       int array[MAX] = {1, 2, 4, 5};
       
       int N = 4;        // number of elements in array
       int i = 0;        // loop variable
       int index = 3;    // index location before which value will be inserted
       int value = 3;    // new data element to be inserted
    
       // print array before insertion
       printf("Printing array before insertion −\n");
    
       for(i = 0; i < N; i++) {
          printf("array[%d] = %d \n", i, array[i]);
       }
    
       // now shift rest of the elements downwards   
       for(i = N; i >= index + 1; i--) {
          array[i + 1] = array[i];
       }
    
       // add new element at first position
       array[index + 1] = value;
    
       // increase N to reflect number of elements
       N++;
    
       // print to confirm
       printf("Printing array after insertion −\n");
    
       for(i = 0; i < N; i++) {
          printf("array[%d] = %d\n", i, array[i]);
       }
    }
    
    
    当我们编译并执行上述程序时,它将产生以下结果
    
    Printing array before insertion −
    array[0] = 1
    array[1] = 2
    array[2] = 4
    array[3] = 5
    Printing array after insertion −
    array[0] = 1
    array[1] = 2
    array[2] = 4
    array[3] = 5
    array[4] = 3