第2章数组 6789第5人出局 9[5第1人出局,i=0 k=7「2346 895第7人出局,i=4 k=6「2346 k=5236|8 678933333 第 人出局,i=2 第 43 人出局 k=4268|9 第6人出局,i=1 k=32896 第9人出局,i=2 k=228‖9|6 第2人出局,i=0 8‖296 71|5第8人出局,i=0 逆置 928最终出局顺序 报错信息m=0是无效的参数! 例:n=9,s=1,m=10 3456789第1人出局,i=0 第3人出局,i=1 k=72456789‖3 第6人出局,i=3 k=624578963 第2人出局,i=0 k=545789 第9人出局,i k=44 78 第5人出局, k=3 第7人出局, k=2 第4人出局,i=0 第8人出局,i=0 逆置 148最终出局顺序 当m=1时,时间代价最大。达到(n-1)+(n-2)+…+1=n(n-1)2≈O(n2)。 3设有一个线性表(eo,el,…,en2,c1)存放在一个一维数组 A[array Size]中的前n个数组元素位置。 请编写一个函数将这个线性表原地逆置,即将数组的前n个原址内容置换为(cnl,cen2,…;,el,eo)。 【解答】 template<class Type> void inverse( Type Al int n)( for(inti=0;i<=(n-1)/2;i++){ tmp =AO: A0=An-i-1: An-i-1=tmp; 2-4假定数组A[ array Size]中有多个零元素,试写出一个函数,将A中所有的非零元素依次移到数组A 的前端A[](0≤i≤ array Size) 【解答】 因为数组是一种直接存取的数据结构,在数组中元素不是像顺序表那样集中存放于表的前端,而 是根据元素下标直接存放于数组某个位置,所以将非零元素前移时必须检测整个数组空间,并将后面 变成零元素的空间清零。函数中设置一个辅助指针free,指示当前可存放的位置,初值为0。 template<class Type> void Array <Type> : compact( )i int free =0第 2 章 数组 11 0 1 2 3 4 5 6 7 8 k = 9 1 2 3 4 5 6 7 8 9 第 5 人出局, i = 4 k = 8 1 2 3 4 6 7 8 9 5 第 1 人出局, i = 0 k = 7 2 3 4 6 7 8 9 1 5 第 7 人出局, i = 4 k = 6 2 3 4 6 8 9 7 1 5 第 4 人出局, i = 2 k = 5 2 3 6 8 9 4 7 1 5 第 3 人出局, i = 1 k = 4 2 6 8 9 3 4 7 1 5 第 6 人出局, i = 1 k = 3 2 8 9 6 3 4 7 1 5 第 9 人出局, i = 2 k = 2 2 8 9 6 3 4 7 1 5 第 2 人出局, i = 0 8 2 9 6 3 4 7 1 5 第 8 人出局, i = 0 逆置 5 1 7 4 3 6 9 2 8 最终出局顺序 例：n = 9, s = 1, m = 0 报错信息 m = 0 是无效的参数！ 例：n = 9, s = 1, m = 10 0 1 2 3 4 5 6 7 8 k = 9 1 2 3 4 5 6 7 8 9 第 1 人出局, i = 0 k = 8 2 3 4 5 6 7 8 9 1 第 3 人出局, i = 1 k = 7 2 4 5 6 7 8 9 3 1 第 6 人出局, i = 3 k = 6 2 4 5 7 8 9 6 3 1 第 2 人出局, i = 0 k = 5 4 5 7 8 9 2 6 3 1 第 9 人出局, i = 4 k = 4 4 5 7 8 9 2 6 3 1 第 5 人出局, i = 1 k = 3 4 7 8 5 9 2 6 3 1 第 7 人出局, i = 1 k = 2 4 8 7 5 9 2 6 3 1 第 4 人出局, i = 0 8 4 7 5 9 2 6 3 1 第 8 人出局, i = 0 逆置 1 3 6 2 9 5 7 4 8 最终出局顺序 当 m = 1 时，时间代价最大。达到( n-1 ) + ( n-2 ) + ∙∙∙∙∙∙ + 1 = n(n-1)/2  O(n2 )。 2-3 设有一个线性表 (e0, e1, …, en-2, en -1) 存放在一个一维数组 A[arraySize]中的前 n 个数组元素位置。 请编写一个函数将这个线性表原地逆置，即将数组的前 n 个原址内容置换为 (en-1, en-2, …, e1, e0)。 【解答】 template<class Type> void inverse ( Type A[ ], int n ) { Type tmp; for ( int i = 0; i <= ( n-1 ) / 2; i++ ) { tmp = A[i]; A[i] = A[n-i-1]; A[n-i-1] = tmp; } } 2-4 假定数组A[arraySize]中有多个零元素, 试写出一个函数, 将A 中所有的非零元素依次移到数组A 的前端 A[i]（0 i  arraySize）。 【解答】 因为数组是一种直接存取的数据结构，在数组中元素不是像顺序表那样集中存放于表的前端，而 是根据元素下标直接存放于数组某个位置，所以将非零元素前移时必须检测整个数组空间，并将后面 变成零元素的空间清零。函数中设置一个辅助指针 free，指示当前可存放的位置，初值为 0。 template<class Type> void Array<Type> :: compact( ) { int free = 0;