数组下标处理问题(0和1)
2011年09月30日


数组下标处理问题(0和1)

 主要是针对于插入排序算法写的程序,其他情况可以借鉴这些思路。

 

数学上或者通常意义上,下标都是从1开始的但是在多数编程语言里面数组下标都是从0开始的,这就很恼火了,简单一个下标处理起来却异常麻烦!请看

例如:

(1)典型的数组下标越界问题

假设有个数组:a[0] a[1],我们要用插入法排序,把a[1]插入到a[0]前面,插入法是这样写的

while( a[j]>temp)       // j=0; temp=a[1];

{a[j+1]=a[j--];}

a[j+1]=temp;

其原理是把比temp(即a[1])小的元素挨个往后移,腾出前面的一个位置将temp插进去,但是当j=0是,如果a[0]>a[1],那么j将减小到-1,在执行while时就会遇到a[-1]。为了解决这个问题,每次都要判断j是否越界,即写成

if( j != 0 ) // 防止越界

       j--;

else

       break;

而且这样写还不行,越界问题解决了,逻辑问题上又有问题,所以说很蛋疼。通常为了避免下标越界的问题,某些人喜欢用a[0]做“哨兵”(即把上面的temp换成a[0]),这样就回避了越界的问题,代码简洁了许多。但是使用“哨兵”对数据结构有要求,那就是a[0]要空出来,不存数据,专门做哨兵。

(2)下标默认为1的情况

       在 MATLAB 中所有下标默认是自然数(1,2,3),不允许出现0这就恼火了,因为所有的算法都是从0开始的,要是没有0会出现一些逻辑问题,所以后来我只能用“p_{k}”这种形式来表示向量的下标了,传统的数组根本用不上。

 

下标0和1矛盾的解决方案

 刚才说了,一种方法就是每次都检测是否会越界,例如下面的直接插入排序算法:

/* ****************************************************************************
直接插入排序(无哨兵的情况)
       作者:zollty
**************************************************************************** */
#include<stdio.h>
 
void InsertSort(int *a, int r)
{     //注意传递参数的时候r为尾元素的下标,即r=n-1
       int i, j;
       int temp;
       for(i=1; i<=r; i++)
       {
              temp=a[i];
              j=i-1;
              while( a[j]>temp )
              {
                     a[j+1]=a[j];
                     if( j != 0 )//检查越界
                     {
                            j--;
                     }
                     else
                     {//理论上j--后j=-1,但是不能再执行while(a[j]>temp),所以break
                            j=-1;
                            break;
                     }
              }
              if( j != i-1 )//如果没有执行while则无需赋值。
              {
                     a[j+1]=temp;
              }
       }
}
 
//专门打印整型数组的函数,n为元素个数.
void print(int s[], int n)
{
       int i;
       for(i=0; i<n; i++)
              printf("%d ", s[i]);
       printf("\n");
}
 
int main(void)
{
       int a[6]={6,5,4,3,2,1};
       print(a,6);
       InsertSort(a, 5);
       print(a,6);
       return 0;
}

第二种方案,设置哨兵,但倘若数据是从0开始储存的就不适合,所以要用另外一个数组去拷贝原数组,新生成的数组首元素不存数据。算法如下:

/* ****************************************************************************
直接插入排序(a[0]作哨兵)
       作者:zollty
**************************************************************************** */
#include<stdio.h>
 
void InsertSort(int *a, int r)
{     //注意传递参数的时候r为尾元素的下标,即r=n-1
       int i, j;
       for(i=2; i<=r; i++)
       {
              a[0]=a[i];
              j=i-1;
              while( a[j]>a[0] )
              {
                     a[j+1]=a[j];
                     j--;
              }
              if( j != i-1 )
              {
                     a[j+1]=a[0];
              }
       }
       a[0]=0;
}
 
//专门打印整型数组的函数,n为元素个数.
void print(int s[], int n)
{
       int i;
       for(i=0; i<n; i++)
              printf("%d ", s[i]);
       printf("\n");
}
 
int main(void)
{
       int a[6]={6,5,4,1,2,3};
       int b[7], i;
       for(i=0, b[0]=0; i<6; i++)
              b[i+1]=a[i];
       print(b,7);
       InsertSort(b, 6);
       print(b,7);
       return 0;
}

也可以把拷贝数组a的操作放在插入算法内部,这样就可以直接传递一般格式的数组。

 

然而,上面这种拷贝记录,在新记录上操作的方法要拷贝数据过来,如果不拷贝回去,那么a数组就相当于报废了,倘若a数组还有其他函数调用,那么就必须拷贝回去,拷过来又拷过去,效率就稍微低了一点。

下面是我发明的头尾哨兵法,这不仅仅是一个算法,而是一种通用的思路。

/* ****************************************************************************
直接插入排序(头尾哨兵法)
       作者:zollty
 
  思路是这样的:我们先把a[0]的值保存,然后用a[0]做哨兵,最后再恢复a[0]的值并
插入到合适的位置,这就相当于我们先对a[1]到a[r]进行排序,然后再插入a[0],插入
的时候又有可能插入到最末尾的情况,这是又会造成越界,所以还必须用最末尾的元素
a[r]做哨兵,这就是为什么我取名为“头尾哨兵法”的原因。
**************************************************************************** */
#include<stdio.h>
 
void InsertSort(int *a, int r)
{     //注意传递参数的时候r为尾元素的下标,即r=n-1
       int i, j, temp;
       temp=a[0];//保存a[0]的值,避免丢失,a[0]将要做哨兵
       for(i=2; i<=r; i++)
       {
              a[0]=a[i];
              j=i-1;
              while( a[j]>a[0] )
              {
                     a[j+1]=a[j];
                     j--;
              }
              if( j != i-1 )
              {
                     a[j+1]=a[0];
              }
       }
 
       a[0]=temp;//a[0]不再是哨兵,还原a[0]的值
       temp=a[r];//保存a[r],a[r]将要做哨兵
       a[r]=a[0];
 
       j=1;
       while( a[r]>a[j] )
       {
              a[j-1]=a[j];
              j++;
       }
       if( temp>a[r] )//如果a[0]比a[r]大,则a[r]要放在次末尾的位置
       {
              a[j-1]=a[r];
              a[r]=temp;
       }
       else  //a[0]比a[r]小,直接放在a[r]的前面
       {
              a[j-1]=temp;
       }
}
 
//专门打印整型数组的函数,n为元素个数.
void print(int s[], int n)
{
       int i;
       for(i=0; i<n; i++)
              printf("%d ", s[i]);
       printf("\n");
}
 
int main(void)
{
       int a[6]={6,5,4,1,2,3};
       print(a,6);
       InsertSort(a, 5);
       print(a,6);
       return 0;
}

 最后,再来回顾一下解决下标的方法:

1. 最直接的方法就是每次检查是否越界,但是要执行多次类属于if(j!=0)的判断;

2. 代码量最简单的方法就是把a[0]当做哨兵用,排序的时候只对a[1]到a[r]排序

3. 最高效但是思路稍微复杂一点的方法是我自创的“首尾哨兵法”,对a[1]到a[r]排序,然后插入a[0],同对a[0]到a[r]排序而言效率差不多,但最主要是它解决了普通哨兵法要求首元素储存为哨兵的要求。