数据结构&算法 数组

  • 数组

    数组是一个容器,可以容纳固定数量的项目,这些项目应为同一类型。大多数数据结构都利用数组来实现其算法。以下是了解数组概念的重要术语。
    • 元素 - 存储在数组中的每个项目称为元素。
    • 索引 - 数组中元素的每个位置都有一个数字索引,用于标识元素。
  • 数组表示

    可以使用不同的语言以各种方式声明数组。为了说明起见,让我们以C语言数组声明为例。
    可以使用不同的语言以各种方式声明数组。为了说明起见,让我们以C数组声明为例。
    根据上面的说明,以下是要考虑的重点。
    • 索引(index)从0开始。
    • 数组长度(size)为10,这意味着它可以存储10个元素。
    • 每个元素都可以通过其索引进行访问。例如,我们可以在索引6处获取一个元素为9。
  • 基本操作

    以下是数组支持的基本操作。
    • 遍历 -逐一打印所有数组元素。
    • 插入 -在给定的索引处添加一个元素。
    • 删除 -删除给定索引处的元素。
    • 搜索 -使用给定的索引或值搜索元素。
    • 更新 -更新给定索引处的元素。
    在C语言中,当使用size初始化数组时,它将按以下顺序为其元素分配默认值。
    颜色名称 效果
    bool false
    char 0
    int 0
    float 0.0
    double 0.0f
    void
    wchar_t 0
    遍历数组
    此操作将遍历数组的元素。
    以下程序遍历并打印数组的元素:
    
    #include <stdio.h>
    main() {
       int LA[] = {1,3,5,7,8};
       int item = 10, k = 3, n = 5;
       int i = 0, j = n;   
       printf("The original array elements are :\n");
       for(i = 0; i < n; i++) {
          printf("LA[%d] = %d \n", i, LA[i]);
       }
    }
    
    尝试一下
    当我们编译并执行上述程序时,它将产生以下结果
    
    The original array elements are :
    LA[0] = 1 
    LA[1] = 3 
    LA[2] = 5 
    LA[3] = 7 
    LA[4] = 8 
    
    插入操作
    插入操作是将一个或多个数据元素插入数组。根据要求,可以在数组的开头,结尾或任何给定的索引处添加新元素。在这里,我们看到了插入操作的实际实现,我们在数组的末尾添加了数据-
    以下是上述算法的实现-
    
    #include <stdio.h>
    
    main() {
       int LA[] = {1,3,5,7,8};
       int item = 10, k = 3, n = 5;
       int i = 0, j = n;
       
       printf("The original array elements are :\n");
    
       for(i = 0; i < n; i++) {
          printf("LA[%d] = %d \n", i, LA[i]);
       }
    
       n = n + 1;
      
       while( j >= k) {
          LA[j+1] = LA[j];
          j = j - 1;
       }
    
       LA[k] = item;
    
       printf("The array elements after insertion :\n");
    
       for(i = 0; i < n; i++) {
          printf("LA[%d] = %d \n", i, LA[i]);
       }
    }
    
    尝试一下
    当我们编译并执行上述程序时,它将产生以下结果-
    
    The original array elements are :
    LA[0] = 1 
    LA[1] = 3 
    LA[2] = 5 
    LA[3] = 7 
    LA[4] = 8 
    The array elements after insertion :
    LA[0] = 1 
    LA[1] = 3 
    LA[2] = 5 
    LA[3] = 10 
    LA[4] = 7 
    LA[5] = 8 
    
    删除操作
    删除是指从数组中删除现有元素并重新组织数组中的所有元素。
    假设LA是一个有N个元素的线性数组,K是一个正整数,K<=N。下面是删除在LA的第K个位置可用的元素的算法。
    
    1. Start
    2. Set J = K
    3. Repeat steps 4 and 5 while J < N
    4. Set LA[J] = LA[J + 1]
    5. Set J = J+1
    6. Set N = N-1
    7. Stop
    
    以下是上述算法的实现-
    
    #include <stdio.h>
    
    void main() {
       int LA[] = {1,3,5,7,8};
       int k = 3, n = 5;
       int i, j;
       
       printf("The original array elements are :\n");
      
       for(i = 0; i < n; i++) {
          printf("LA[%d] = %d \n", i, LA[i]);
       }
        
       j = k;
      
       while( j < n) {
          LA[j-1] = LA[j];
          j = j + 1;
       }
      
       n = n -1;
       
       printf("The array elements after deletion :\n");
      
       for(i = 0; i < n; i++) {
          printf("LA[%d] = %d \n", i, LA[i]);
       }
    }
    
    尝试一下
    当我们编译并执行上述程序时,它将产生以下结果-
    
    The original array elements are :
    LA[0] = 1 
    LA[1] = 3 
    LA[2] = 5 
    LA[3] = 7 
    LA[4] = 8 
    The array elements after deletion :
    LA[0] = 1 
    LA[1] = 3 
    LA[2] = 7 
    LA[3] = 8 
    
    搜索操作
    您可以根据数组元素的值或索引来搜索它。
    假设LA是一个有N个元素的线性数组,K是一个正整数,K<=N。下面是使用顺序搜索查找具有ITEM值的元素的算法。
    
    1. Start
    2. Set J = 0
    3. Repeat steps 4 and 5 while J < N
    4. IF LA[J] is equal ITEM THEN GOTO STEP 6
    5. Set J = J +1
    6. PRINT J, ITEM
    7. Stop
    
    以下是上述算法的实现-
    
    #include <stdio.h>
    
    void main() {
       int LA[] = {1,3,5,7,8};
       int item = 5, n = 5;
       int i = 0, j = 0;
       
       printf("The original array elements are :\n");
      
       for(i = 0; i < n; i++) {
          printf("LA[%d] = %d \n", i, LA[i]);
       }
        
       while( j < n){
          if( LA[j] == item ) {
             break;
          }
        
          j = j + 1;
       }
      
       printf("Found element %d at position %d\n", item, j+1);
    }
    
    尝试一下
    当我们编译并执行上述程序时,它将产生以下结果-
    
    The original array elements are :
    LA[0] = 1 
    LA[1] = 3 
    LA[2] = 5 
    LA[3] = 7 
    LA[4] = 8 
    Found element 5 at position 3
    
    更新操作
    更新操作是指以给定索引更新数组中的现有元素。
    假设LA是一个有N个元素的线性数组,K是一个正整数,K<=N。下面是更新在LA的第k个位置可用的元素的算法。
    
    1. Start
    2. Set LA[K-1] = ITEM
    3. Stop
    
    以下是上述算法的实现-
    
    #include <stdio.h>
    
    void main() {
       int LA[] = {1,3,5,7,8};
       int k = 3, n = 5, item = 10;
       int i, j;
       
       printf("The original array elements are :\n");
      
       for(i = 0; i < n; i++) {
          printf("LA[%d] = %d \n", i, LA[i]);
       }
        
       LA[k-1] = item;
    
       printf("The array elements after updation :\n");
      
       for(i = 0; i < n; i++) {
          printf("LA[%d] = %d \n", i, LA[i]);
       }
    }
    
    尝试一下
    当我们编译并执行上述程序时,它将产生以下结果-
    
    The original array elements are :
    LA[0] = 1 
    LA[1] = 3 
    LA[2] = 5 
    LA[3] = 7 
    LA[4] = 8 
    The array elements after updation :
    LA[0] = 1 
    LA[1] = 3 
    LA[2] = 10 
    LA[3] = 7 
    LA[4] = 8