数据结构与算法：数组

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

元素：存储在数组中的每一项叫做一个元素

下标：用来区分元素位置的数字指标

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

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

注意以下几个要点：

下标从零开始

数组长度为10意味着可以存储10个元素

元素可通过下标访问，例如可以从下标6提取数据27

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

遍历——依次打印所有数据元素

插入——在指定下标位置插入元素

删除——删除指定下标位置的元素

搜索——搜索指定下标的元素，或者按数值搜索

更新——更新指定下标位置的元素

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

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

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

1、Start2、SetJ=N3、SetN=N+14、Repeatsteps5and6whileJ=K5、SetLA[J+1]=LA[J]6、SetJ=J-17、SetLA[K]=ITEM8、Stop

用C语言表示如下：

#includestdio.hintmain(){intLA[]={1,3,5,7,8};intitem=10,k=3,n=5;inti=0,j=n;printf(Theoriginalarrayelementsare:\n);for(i=0;in;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(Thearrayelementsafterinsertion:\n);for(i=0;in;i++){printf(LA[%d]=%d\n,i,LA[i]);}return0;}

编译运行结果如下：

Theoriginalarrayelementsare:LA[0]=1LA[1]=3LA[2]=5LA[3]=7LA[4]=8Thearrayelementsafterinsertion:LA[0]=1LA[1]=3LA[2]=5LA[3]=10LA[4]=7LA[5]=8

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

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

假设A是一个有N个元素的数组，它可以存储的元素数量最大为MAX，首先我们要检查数组是否有足够的剩余空间来进行插入操作，然后再进行插入。

beginIFN=MAX,returnELSEN=N+1//所有元素后移ForAllElementsinAMovetonextadjacentlocationA[FIRST]=New_Elementend用C语言实现

#includestdio.h#defineMAX5intmain(){intarray[MAX]={2,3,4,5};intN=4;//数组中元素个数inti=0;//循环变量intvalue=1;//需要插入到数组开头的元素//打印插入前的数组printf(Printingarraybeforeinsertion?\n);for(i=0;iN;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(Printingarrayafterinsertion?\n);for(i=0;iN;i++){printf(array[%d]=%d\n,i,array[i]);}return0;}

程序运行结果如下：

Printingarraybeforeinsertion?array[0]=2array[1]=3array[2]=4array[3]=5Printingarrayafterinsertion?array[0]=1array[1]=2array[2]=3array[3]=4array[4]=52、在给定下标处插入

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

假设A是一个有N个元素的数组，它可以存储的元素数量最大为MAX。

beginIFN=MAX,returnELSEN=N+1SEEKLocationindexForAllElementsfromA[index]toA[N]MovetonextadjacentlocationA[index]=New_Elementend用C语言实现

#includestdio.h#defineMAX5intmain(){intarray[MAX]={1,2,4,5};intN=4;//数组中元素个数inti=0;//循环变量intindex=2;//插入位置intvalue=3;//待插入元素//打印插入前数组printf(Printingarraybeforeinsertion?\n);for(i=0;iN;i++){printf(array[%d]=%d\n,i,array[i]);}//插入位置后所有元素后移for(i=N;i=index;i--){array[i+1]=array[i];}//插入新元素array[index]=value;//元素个数加1N++;//打印插入后结果printf(Printingarrayafterinsertion?\n);for(i=0;iN;i++){printf(array[%d]=%d\n,i,array[i]);}return0;}

程序运行结果如下：

Printingarraybeforeinsertion?array[0]=1array[1]=2array[2]=4array[3]=5Printingarrayafterinsertion?array[0]=1array[1]=2array[2]=3array[3]=4array[4]=53、在给定下标后插入

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

假设A是一个有N个元素的数组，它可以存储的元素数量最大为MAX。

beginIFN=MAX,returnELSEN=N+1SEEKLocationindexForAllElementsfromA[index+1]toA[N]MovetonextadjacentlocationA[index+1]=New_Elementend用C语言实现

#includestdio.h#defineMAX5intmain(){intarray[MAX]={1,2,4,5};intN=4;//数组元素个数inti=0;//循环变量intindex=1;//新元素插入到此位置之后intvalue=3;//待插入元素//打印插入前元素printf(Printingarraybeforeinsertion?\n);for(i=0;iN;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;//元素个数加1N++;//打印插入结果printf(Printingarrayafterinsertion?\n);for(i=0;iN;i++){printf(array[%d]=%d\n,i,array[i]);}return0;}

程序运行结果如下

Printingarraybeforeinsertion?array[0]=1array[1]=2array[2]=4array[3]=5Printingarrayafterinsertion?array[0]=1array[1]=2array[2]=3array[3]=4array[4]=54、在给定下标前插入

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

beginIFN=MAX,returnELSEN=N+1SEEKLocationindexForAllElementsfromA[index-1]toA[N]MovetonextadjacentlocationA[index-1]=New_Elementend用C语言实现

#includestdio.h#defineMAX5intmain(){intarray[MAX]={1,2,4,5};intN=4;//数组元素个数inti=0;//循环变量intindex=3;//新元素插入到此位置之前intvalue=3;//待插入元素//打印插入前数组printf(Printingarraybeforeinsertion?\n);for(i=0;iN;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;//数组元素个数加1N++;//打印插入结果printf(Printingarrayafterinsertion?\n);for(i=0;iN;i++){printf(array[%d]=%d\n,i,array[i]);}return0;}

程序运行结果如下：

Printingarraybeforeinsertion?array[0]=1array[1]=2array[2]=4array[3]=5Printingarrayafterinsertion?array[0]=1array[1]=2array[2]=3array[3]=4array[4]=5四、删除操作

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

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

1.Start2.SetJ=K3.Repeatsteps4and5whileJN4.SetLA[J-1]=LA[J]5.SetJ=J+16.SetN=N-17.Stop算法实现

#includestdio.hintmain(){intLA[]={1,3,5,7,8};intk=3,n=5;inti,j;printf(Theoriginalarrayelementsare:\n);for(i=0;in;i++){printf(LA[%d]=%d\n,i,LA[i]);}j=k;while(jn){LA[j-1]=LA[j];j=j+1;}n=n-1;printf(Thearrayelementsafterdeletion:\n);for(i=0;in;i++){printf(LA[%d]=%d\n,i,LA[i]);}return0;}

程序运行结果如下：

Theoriginalarrayelementsare:LA[0]=1LA[1]=3LA[2]=5LA[3]=7LA[4]=8Thearrayelementsafterdeletion:LA[0]=1LA[1]=3LA[2]=7LA[3]=8五、搜索操作

可根据下标或者值进行搜索。

LA是一个有N个元素的数组，K是一个正整数，K=N，以下算法搜索值为ITEM的元素。

1.Start2.SetJ=03.Repeatsteps4and5whileJN4.IFLA[J]isequalITEMTHENGOTOSTEP65.SetJ=J+16.PRINTJ,ITEM7.Stop算法实现

#includestdio.hintmain(){intLA[]={1,3,5,7,8};intitem=5,n=5;inti=0,j=0;printf(Theoriginalarrayelementsare:\n);for(i=0;in;i++){printf(LA[%d]=%d\n,i,LA[i]);}while(jn){if(LA[j]==item){break;}j=j+1;}printf(Foundelement%datposition%d\n,item,j+1);return0;}

程序运行结果如下：

Theoriginalarrayelementsare:LA[0]=1LA[1]=3LA[2]=5LA[3]=7LA[4]=8Foundelement5atposition3六、更新操作

更新操作是指更新指定位置的数据元素。

LA是一个有N个元素的数组，K是一个正整数，K=N，以下算法更新第K个位置的元素。

1.Start2.SetLA[K-1]=ITEM3.Stop算法实现

#includestdio.hintmain(){intLA[]={1,3,5,7,8};intk=3,n=5,item=10;inti,j;printf(Theoriginalarrayelementsare:\n);for(i=0;in;i++){printf(LA[%d]=%d\n,i,LA[i]);}LA[k-1]=item;printf(Thearrayelementsafterupdation:\n);for(i=0;in;i++){printf(LA[%d]=%d\n,i,LA[i]);}return0;}

程序运行结果如下：

Theoriginalarrayelementsare:LA[0]=1LA[1]=3LA[2]=5LA[3]=7LA[4]=8Thearrayelementsafterupdation:LA[0]=1LA[1]=3LA[2]=10LA[3]=7LA[4]=8

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

转载请注明：http://www.92nongye.com/xxnr/204612748.html