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

процедура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, като приемем, че единственото място за съхраняване на възли и референции са нашите масиви.

Да предположим, че трябва да премахнем възел A от примера за Грешка: Референтен източник не е намерен и след това да освободим заетата памет. Пренареждането на всички указатели в списъка, така че възелът вече да не е част от списъка, е едно, но какво правим с пространството, използвано от този възел? И как да намерим място за нов възел, когато извикаме процедурата ново? За да разрешим проблема, можем да използваме втори свързан списък за съхраняване на информация за неизползваното пространство. Ще му се обадимсписък на неизползваните елементи. Сега, когато ниеИзтрий елемент от списъка, освобождаваме пространството, което използва, като го добавяме към списъка с неизползвани елементи и когато създаваменововъзел, - получаваме място за него, като го премахваме от списъка с неизползвани елементи. По този начин говорим за множество списъци в един масив.

Прост пример с два списъка (но няма списък с неизползвани елементи) е изобразен в Грешка: Референтен източник не е намерен. Този пример дефинира два възлови заглавни списъка hd1 = 0 иhd2 = 6, но и двата списъка имат един и същ краен възелz. (За да създадете множество списъци, процедурата за инициализацияlistInitializeтрябва да се промени, така че да може да управлява повече от една глава на списъка.) Сега,следващ [0] = 4, така че първият елемент от нашия списък еклавиш [4] (O). Защотоследващ [6] = 7, тогава първият елемент от втория списък еклавиш [7] (T),и т.н. Следващата диаграма показва нашите списъци, без да се използва паралелен масив.следващия, замествайки го с линии, свързващи възлите му. Третият показва същите два списъка, но разширен. И накрая, последната диаграма показва списъците в графичната форма, с която сме свикнали, както в Грешка: Референтен източник не е намерен.

Два списъка, съдържащи се в един масив

Всичко описано по-горе има за цел да ви помогне да разберете как системата управлява разпределението на ресурси. Всъщност проблемът, с който системата се справя, е по-сложен. Въпросът е, че възлите не трябва да са с еднакъв размер. Някои системи освобождават потребителя от необходимостта от директно обаждане разпорежда се за освобождаване на паметта чрез използване на алгоритмисъбиране на боклукза премахване на "изгубени" възли. Ако управлението на паметта се осигурява от среда за програмиране, както в Pascal, тогава обикновено няма причина да създавате свой собствен мениджър на паметта.