Операции со списками при последовательном хранении

При выборе метода хранения линейного списка следует учитывать, какие операции будут выполняться и с какой частотой, время их выполнения и объем памяти, требуемый для хранения списка.

Пусть имеется линейный список с целыми значениями и для его хранения используется массив d (с числом элементов 100), а количество элементов в списке указывается переменной l. Реализация указанных ранее операций над списком представляется следующими фрагментами программ которые используют объявления:

float d[100];

int i,j,l;

1) печать значения первого элемента (узла)

if (i<0 || i>l) printf("\n нет элемента");

else printf("d[%d]=%f ",i,d[i]);

2) удаление элемента, следующего за i-тым узлом

if (i>=l) printf("\n нет следующего ");

l--;

for (j=i+1;j<="1" ||="" i="">=l) printf("\n нет соседа");

else printf("\n %d %d",d[i-1],d[i+1]);

4) добавление нового элемента new за i-тым узлом

if (i==l || i>l) printf("\n нельзя добавить");

else

{ for (j=l; j>i+1; j--) d[j+1]=d[j];

d[i+1]=new; l++;

}

5) частичное упорядочение списка с элементами К1,К2,...,Кl в

список K1',K2',...,Ks,K1,Kt",...,Kt", s+t+1=l так, чтобы K1'=K1;

после упорядочения указатель v указывает на элемент K1' (см. рис.19)

Рис.19. Схема частичного упорядочения списка.

ND *v;

float k1;

k1=dl->val;

r=dl;

while( r->n!=NULL )

{ v=r->n;

if (v->valn=v->n;

v->n=dl;

dl=v;

}

else r=v;

}

Количество действий, требуемых для выполнения указанных операций над списком в связанном хранении, оценивается соотношениями: для операций 1 и 2 - Q=l; для операций 3 и 4 - Q=1; для операции 5 - Q=l.