1.3. Линейно свързани индексирани блокови списъци
Ориз. 10. Индексиран списък с блокове
В диапазона между първите два директни указателя (фиг. 10) можете да вмъкнете още 15 елемента. С всяко вмъкване номерата на позициите във втория и третия ред на индексната таблица се увеличават. Трябва да се отбележи, че за двойно свързан блоков списък обикновено не е възможно да се избере посоката на итерация (от началото или от края), за да се гарантира движение от най-близката референтна точка. Следователно можем да се съгласим винаги да се движим в една посока, например от главата до опашката.
Да предположим, че списъкът с блокове съдържа 10 000 елемента в 500 блока, размерът на блока е 20. Нека индексната таблица съдържа 6 записа. Тогава обхватът на индексиране е = 500/5 = 100 блока. В този случай можете да добавите или премахнете до 5 блока, т.е. 520 = 100 произволни елемента в същия диапазон на индекса, тъй като int(500/5) = int(501/5) = . = int(504/5) int(505/5). Ако списъкът изисква произволен достъп, така че произволните достъпи до клетки да са произволни и равномерно разпределени, операциите за вмъкване/изтриване ще се извършват равномерно във всички диапазони на индекси и няма да е необходимо пълно обхождане на списъка за дълго време. Интерес представляват и случаите, при които операциите с произволен достъп се извършват не по единни, а по други закони на разпределение. За създаване на генератор на случайни променливи с даден закон на разпределение може да се използва методът на обратните функции. Състои се в това, че за дадена функция на разпределение F(x) на случайна променлива се намира функция Q(x), обратна на нея, така че Q(F(x)) x. След това, замествайки стойността на случайна променлива r, равномерно разпределена върху [0,1], като аргумент на функцията Q(x), се получава случайна променлива Q(r) с необходимия закон на разпределение F(x).За да генерирате приблизително нормално разпределена случайна променлива с нулева средна стойност и единична дисперсия, можете първо да генерирате s равномерно разпределени върху [0,1] случайни променливи Ri и след това да изчислите стойността X = (R1+R2+. +Rs-s/2)/ (s/12) 1/2.