数组方式二：两重while循环，将间隔计数的直接写成了程序，未用循环，这样移植性差了
//#define SIZE 1000 //#define STEP 2 //#define DELFLAG (SIZE + 1)
void ArrayTest2(void) { int arr[SIZE]; for (int i=0;i < SIZE;++i) arr[i]=i; // 实际情况并非一定如此啊 int j=0; int count=0; while(count < SIZE-1) // 999保留了最后一个未删除的数 { while(arr[j00]==DELFLAG) j=(++j)%SIZE;
j=(++j)%SIZE; // 第一个未访问的数
while(arr[j%SIZE]==DELFLAG) j=(++j)%SIZE;
j=(++j)%SIZE; // 第二个未访问的数
while(arr[j%SIZE]==DELFLAG) j=(++j)%SIZE;
arr[j]=DELFLAG; //删除第三个未访问的数 ++count; } while(arr[j]==DELFLAG) // 扫描最后一个未删除的数 j=(++j)%SIZE;
cout << j << endl; }
优化版本：程序的逻辑功能划分明确，每个while处理一层逻辑，结构更易懂，程序的移植性强，while中的循环次数可随意更改 上面方法中的step在程序中固定了 void ArrayTest3Opt(void) { int arr[SIZE]; for (int i=0;i < SIZE;++i) arr[i]=i; // 实际情况并非一定如此啊 int j=0; int count=0; int stepcounter=0; int delindex = 0; while(count < SIZE) // 删除总次数 { // 删除一个 while(stepcounter <= STEP) // 寻找第三个未访问的数 { while(arr[j%SIZE]==DELFLAG) //剔除已删除的 j=(++j)%SIZE;
j=(++j)%SIZE; // (++j)中的j为一个未访问的数，而非保存后的j，故下面delindex = j -1; stepcounter ++; } //delindex = j -1; // 由于上面j加一后可能溢出重头开始了，因此先加SIZE delindex = (j + SIZE -1)%SIZE; // 保存当前删除数的下标 stepcounter = 0; arr[delindex]=DELFLAG; // 删除第三个未访问的数 ++count; }
标志数组方式三： 对于只读数组，也可以置标志，访问完毕后能够恢复初始序列即可 当前存放的数是正数，且有一定的范围，可是利用其最高位做为已经删除标志，最后一个删除的数其最高位为0，下标可知，实际数据可知。所以数据删除完后，清除最高位的删除标志，即可恢复原始序列。 //define delFLAG (1 << ((sizeof(int)*8) - 1)) // 注意上述首位置1的定义，考虑了int字节个数的影响，对于嵌入式软件工程师来说时刻考虑跨平台的移植性能，是个很重要的素质 void _ArrayTest3(void) { int arr[SIZE]; int currentSize=SIZE; //指示当前数组中还剩余有效元素的个数，为0时表示删除/完毕； int count=0; //计数用； int lastdel = 0; int i = 0;
for(int k=0;k<SIZE;k++) { arr[k]= SIZE - k; } // i用％循环计数，终止条件是删除的只剩最后一个数了 while(currentSize!=0) { if(arr[i] >= 0 ) // 当前数大于等于0时，未删除，已经删除的则看下一个 { // 按照计数间隔计数，达到间隔时删除数据 if( count++ == STEP) { lastdel = i; arr[i] |= delFLAG; //将此数最高位置为1，此时其为负数，表示删除 currentSize--;//有效元素减一； count=0;//并将计数值归零； } } i=(i+1)%SIZE; } cout<<"the original array location of the last del value is: "<<lastdel<<endl; // 清除最高位的1，恢复原始数组 for(k=0;k<SIZE;k++) { arr[k] &= ~delFLAG; // 注意这种清除方式的移植性很高 }}
时间复杂度比在初始数组中置标志多了最后的清除删除标志，空间复杂度为0，没有额外申请空间保存访问标志和下标，相比额外申请1000个空间处理只读数组空间效率高。 比下面循环队列的空间效率高，时间效率低，因为此法访问了已经删除的无效数据。
这个题看似说只能使用数组,但可以考虑使用数组完成链表的功能,建议再开一个1000大小的数组,每个元素里面放的是另外一个数组中对应元素的脚标，即0-999.然后循环按此数组循环，修改链表是通过置访问标志来实现的，最后一个未置标志的数就是原始下标了，原数组中就是最后删除的实际数据。不用动原来的数组里面的数据..
