Свързани списъци

процедураdeleteNext (t: цяло число);започнетеследващ [t]: = следващ [следващ [t]];край;

процедураinsertAfter (v: цяло число; t: цяло число);започнетеx: = x + 1; ключ [x]: = v; следващ [x]: = netx [t]; следващ [t]: = xкрай;

Показалецx замества процедурата за разпределяне на динамична паметново: сочи към следващата неизползвана позиция в масива.

Грешка: Референтен източник не е намерен показва как списъкът от нашия пример може да бъде представен като паралел­отделни масиви и как този изглед е свързан с графичното представяне­използване, което все още използваме­Наречен. Ключът и следващите масиви са показани вляво, както биха се появили, ако бяхме вмъкнали от­първоначално празен списък SLAIT, където S, L и A се вмъкват след head, I след L и T след S. Позиция 0 е началото на списъка, а позиция 1 е неговият край (това се задава, когато­инициализация на списъка). Следователно следващ [0] = 4 е първият възел от списъка с ключ за стойност [4] (A); Тъй като next [4] = 3, следващият (втори) елемент ще бъде ключ [3] (L) и т.н. Във втората диаграма отляво индексите на масива се заменят с редове, вместо да записваме номера на следващия елемент в списъка, ние просто чертаем линия, свързваща го със следващия елемент. В третата диаграма ние „изправяме“ списъка, а след това в последната дясна диаграма просто използваме обичайното графично представяне на свързания списък.

списъци

Внедряване на свързан списък с масиви

Връщайки се към аналогията с компютърната памет, нека изградим аналогия за динамично разпределение и освобождаване на паметта. Операционната система е поставена в такова положение, че възлите се съхраняват в същия масив (памет - масив) като връзките. И така, ние искаме да внедрим вградените процедури new и dispose, като приемем, че единственото място за съхраняване на възли и референции са нашите масиви.