数据结构与算法：数组

数组是一个可以存储固定数量数据元素的容器，并且这些元素必须是同一种数据类型。很多数据结构都会使用数组来实现其算法，以下是理解数组概念的两个重要术语：

元素：存储在数组中的每一项叫做一个元素
下标：用来区分元素位置的数字指标

一、数组的表示

不同的编程语言会使用不同的方式声明数组，此处我们采用C语言形式:

数组声明

每个元素对应的下标如下：

数组下标

注意以下几个要点：

下标从零开始
数组长度为10意味着可以存储10个元素
元素可通过下标访问，例如可以从下标6提取数据27

二、基本操作

数组的基本操作有以下几种：

遍历——依次打印所有数据元素
插入——在指定下标位置插入元素
删除——删除指定下标位置的元素
搜索——搜索指定下标的元素，或者按数值搜索
更新——更新指定下标位置的元素

在C语言中，声明数组并确定数组长度后，编译器会自动按如下规律给数组元素分配值：

Data Type	Default Value
bool	false
char	0
int	0
float	0.0
double	0.0f
void
wchar_t	0

三、插入操作

插入操作是将一个或多个元素插入到数组中，插入位置可以是开头、末尾或者任意给定位置。

举例

假设LA是一个无序线性数组，有N个元素，K是一个正整数，K≦N，下面的算法是将一个元素插入到数组LA的第K个位置。

1、Start

2、Set J=N

3、Set N = N+1

4、Repeat steps 5 and 6 while J >= K

5、Set LA[J+1] = LA[J]

6、Set J = J-1

7、Set LA[K] = ITEM

8、Stop

用C语言表示如下：

#include <stdio.h>

int 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]);
   }
   return 0;
}

编译运行结果如下：

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

（译者注：上述程序实际上是不安全的，因为数组的长度不确定，在Visual Studio中运行会发生“Run-Time Check Failure #2 – Stack around the variable ‘LA’ was corrupted.”错误，但不影响结果的显示。此处仅希望读者理解插入的思想。可使用动态数组或者数据结构中的线性表解决这个问题，或者使用这份教程中的另一种方法，见下方。）

其它类型的插入操作

1、在数组开头插入

在开头进行插入时，会导致所有的数据项后移一位，这里我们设计一个算法来实现这个操作。

算法

假设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

int main() {
   int array[MAX] = {2, 3, 4, 5};
   int N = 4;     // 数组中元素个数
   int i = 0;     // 循环变量
   int value = 1; // 需要插入到数组开头的元素

   // 打印插入前的数组
   printf("Printing array before insertion −\n");
   
   for(i = 0; i < N; i++) {
      printf("array[%d] = %d \n", i, array[i]);
   }

   // 数组所有元素后移一位 
   for(i = N; i >= 0; i--) {
      array[i+1] = array[i];
   }

   // 在开头插入新元素
   array[0] = value;

   // N加1反映数组元素个数的变化
   N++;

   // 打印插入后结果
   printf("Printing array after insertion −\n");
   
   for(i = 0; i < N; i++) {
      printf("array[%d] = %d\n", i, array[i]);
   }
   return 0;
}

程序运行结果如下：

Printing array before insertion −

array[0] = 2

array[1] = 3

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

2、在给定下标处插入

这种情况下，我们给出了插入的明确位置，首先检查数组是否已满，如果未满，则将插入位置处及之后的所有元素后移一位，为待插入元素腾出空间。

算法

假设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

int main() {
   int array[MAX] = {1, 2, 4, 5};
   
   int N = 4;        // 数组中元素个数
   int i = 0;        // 循环变量
   int index = 2;    // 插入位置
   int value = 3;    // 待插入元素

   // 打印插入前数组
   printf("Printing array before insertion −\n");

   for(i = 0; i < N; i++) {
      printf("array[%d] = %d \n", i, array[i]);
   }

   // 插入位置后所有元素后移   
   for(i = N; i >= index; i--) {
      array[i+1] = array[i];
   }

   // 插入新元素
   array[index] = value;

   // 元素个数加1
   N++;

   // 打印插入后结果
   printf("Printing array after insertion −\n");

   for(i = 0; i < N; i++) {
      printf("array[%d] = %d\n", i, array[i]);
   }
   return 0;
}

程序运行结果如下：

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

3、在给定下标后插入

这种情况下我们需要将新元素插入到指定位置的后面，除了寻找插入位置的过程与前面不同，其他均与前面操作相同。

算法

假设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

int main() {
   int array[MAX] = {1, 2, 4, 5};
   
   int N = 4;        // 数组元素个数
   int i = 0;        // 循环变量
   int index = 1;    // 新元素插入到此位置之后
   int value = 3;    // 待插入元素

   // 打印插入前元素
   printf("Printing array before insertion −\n");

   for(i = 0; i < N; i++) {
      printf("array[%d] = %d \n", i, array[i]);
   }

   // 插入位置后元素后移   
   for(i = N; i >= index + 1; i--) {
      array[i + 1] = array[i];
   }

   // 插入新元素
   array[index + 1] = value;

   // 元素个数加1
   N++;

   // 打印插入结果
   printf("Printing array after insertion −\n");

   for(i = 0; i < N; i++) {
      printf("array[%d] = %d\n", i, array[i]);
   }
return 0;
}

程序运行结果如下

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

4、在给定下标前插入

同理，仅将插入位置改为index-1。

算法

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

int main() {
   int array[MAX] = {1, 2, 4, 5};
   
   int N = 4;        // 数组元素个数
   int i = 0;        // 循环变量
   int index = 3;    // 新元素插入到此位置之前
   int value = 3;    //待插入元素

   // 打印插入前数组
   printf("Printing array before insertion −\n");

   for(i = 0; i < N; i++) {
      printf("array[%d] = %d \n", i, array[i]);
   }

   // 插入位置后元素后移   
   for(i = N; i >= index - 1; i--) {
      array[i + 1] = array[i];
   }

   // 插入新元素
   array[index - 1] = value;

   // 数组元素个数加1
   N++;

   // 打印插入结果
   printf("Printing array after insertion −\n");

   for(i = 0; i < N; i++) {
      printf("array[%d] = %d\n", i, array[i]);
   }
   return 0;
}

程序运行结果如下：

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

四、删除操作

删除是指数组中删除指定元素并重新排列数组。

算法

假设LA是一个有N个元素的数组，K是一个正整数，K<=N，下面的算法删除第K个位置的元素。

1. Start

2. Set J=K

3. Repeat steps 4 and 5 while J < N

4. Set LA[J-1] = LA[J]

5. Set J = J+1

6. Set N = N-1

7. Stop

算法实现

#include <stdio.h>
int 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]);
   }
   return 0;
}

程序运行结果如下：

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>
int 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);
   return 0;
}

程序运行结果如下：

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，以下算法更新第K个位置的元素。

1.Start

2.Set LA[K-1] = ITEM

3.Stop

算法实现

#include <stdio.h>
int 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]);
   }
   return 0;
}

程序运行结果如下：

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

转载请参看关于博客页面相关要求。

文章

数据结构与算法：数组

一、数组的表示

二、基本操作

三、插入操作

举例

其它类型的插入操作

1、在数组开头插入

算法

用C语言实现

2、在给定下标处插入

算法

用C语言实现

3、在给定下标后插入

算法

用C语言实现

4、在给定下标前插入

算法

用C语言实现

四、删除操作

算法

算法实现

五、搜索操作

算法

算法实现

六、更新操作

算法

算法实现

关于 “数据结构与算法：数组” 的 1 个意见

2019年九月
一	二	三	四	五	六	日
« 7月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30