Информатика и технология программирования

       

Упаковка последовательности нулей


В качестве примера рассмортим программу, которая упаковывает массив положительных вещественных чисел, " сворачивая" последовательности подряд идущих нулевых элементов. Формат упакованной последовательности следующий :



-последовательность ненулевых элементов кодируется целым счетчиком (типа int), за которым следуют сами элементы ;



-последовательность нулевых элементов кодируется отрицательным значением целого счетчика ;



-нулевое значение целого счетчика обозначает конец последовательности ;



-пример неупакованной и упакованной последовательностей : 2.2, 3.3, 4.4, 5.5, 0.0, 0.0, 0.0, 1.1, 2.2, 0.0, 0.0, 4.4 и 4, 2.2, 3.3, 4.4, 5.5, -3, 2, 1.1, 2.2, -2, 1, 4.4, 0

В процессе упаковки требуется подсчитывать количество подряд идущих нулей. При этом в выходной последовательности запоминается место расположения последнего счетчика - также в виде указателя. Смена счетчика происходит, если текущий и предыдущий элементы относятся к разным последовательностям (комбинации " нулевой - ненулевой" и наоборот).


//------------------------------------------------------bk44-01.cpp


void pack(int *p, double v[], int n)
{
int *pcnt=p++; // Указатель на последний счетчик


*pcnt=0;
for (int i=0; i&#60n; i++)
{ // Смена счетчика


if (i!=0 &#38&#38 (v[i]==0 &#38&#38 v[i-1]!=0) ||
v[i]!=0 &#38&#38 v[i-1]==0))
{ pcnt=p++; *pcnt=0; }
if (v[i]==0)
(*pcnt)--; // -1 к счетчику нулевых


else
{
(*pcnt)++ ; // +1 к счетчику ненулевых


*((double*)p)++ = v[i];
}
}
*p++ = 0;
}

Функция распаковки не в пример проще :


//------------------------------------------------------bk44-02.cpp


int unpack(int *p, double v[])
{ int i=0,cnt;
while ((cnt = *p++)!=0) // Пока нет нулевого счетчика


{
if (cnt&#60 0) // Последовательность нулей


while(cnt++!=0)
v[i++]=0;
else // Ненулевые элементы


while(cnt--!=0) // извлечь с преобразованием


v[i++]=*((double*)p)++;
} // типа указателя


}



Содержание раздела