Поотделно-свързани списъци

В свързан списък, всеки елемент от информацията съдържа връзка към следващия елемент от списъка. Всеки елемент на данни обикновено е структура, която се състои от информация и комуникация поле показалка. Концептуално свързан списък изглежда така, както е показано на фиг. 22.2.

Фиг. 22.2 поединично свързан списък

Има два основни начина за изграждане на свързан списък. Първият начин - сложи новите елементи в долната част на списъка. [1] Вторият - да се вмъкне елементи в определена позиция в списъка, например, във възходящ ред. Методът на изграждане зависи списък алгоритъм функция добавяне член. Да започнем с един прост начин да създадете списък с поставяне елементи в края на краищата.

slstore () функцията по-долу създава свързан списък, като поставите всяка от следващия елемент от списъка. Като параметри са преминали указател към адреса тип структура. съдържа нов запис, и указател към последния елемент в списъка. Ако списъкът е празен, указател към последния елемент трябва да бъде нула.

Въпреки, че е създадена от списък с slstore функция () може да се сортира в отделна операция след създаването си, то е по-лесно просто да се създаде подреден списък, вмъкване на всеки нов елемент до желаната позиция в последователността. Освен това, ако в списъка е вече подредени, че има смисъл да подкрепи нейната системност, вмъкване на нови елементи в съответните позиции. За вмъкване на елемент по този начин изисква последователен изглед на списък, докато няма място намери нов елемент, а след това постави нов рекорд в намери позиция и да преинсталирате връзки.

Когато поставите елемент в свързан списък може да бъде един от следните три ситуации: документа става е поставена на първия елемент между другите два, става последния елемент. Фиг. 22.3 показва позоваването промяна верига във всеки случай.

Фиг. 22.3. Създава се нов елемент в свързан списък (в който инфо - полеви данни)

Следната функция, sls_store (). вмъква адрес тип структура в мейлинг лист, като го поръчате възходящ в стойността на име на поле. Функцията се указател към указател към първия и последния елементи от списъка, както и указател към член на вмъкване. Тъй като първите и последните елементи от списъка могат да бъдат променяни, sls_store () функция, ако е необходимо, се актуализира автоматично на указатели към началото и в края на списъка. Първата покана за тази функция, първия и последния указатели трябва да са равни на нула.

Преминете през елементите на списъка, свързан е много проста: да се започне от самото начало и следвайте указателните табели. Обикновено бюст код фрагмент е толкова малък, че да влиза в друга процедура - например, функция за търсене, изтриване или представяне на съдържанието. По този начин, функцията по-долу показва всички имена от списъка с адреси:

Когато се обаждате функциите на индикаторите () Параметърът за начало трябва да бъде указател към първата структура в списъка. След това, функцията продължава към следващия елемент, което е индикация за следващото поле показалка. Процесът спира, когато следващия нула.

За да получите елемент от списъка, просто трябва да мине през верижните звена. По-долу е пример за функция за търсене в съдържанието на името на полето:

Тъй като функцията за търсене () връща указател към влизането в списък, съдържащ желаното име, тип връщане е описан като указател към адреса структура. При липса на нула (NULL) връща в списъка на подходящи клетки.

Премахването на елемента от свързания списък е проста. Точно както във вложката, има три възможни случаи: премахване на първия елемент, изтриване на елемент в средата на, заличаването на последния елемент. Фиг. 22.4 показва всичките три операции.

Фиг. 22.4. Премахването на елемента от свързан списък

По-долу е функция, която премахва определен елемент от списъка с адресни структури.

sldelete () функция трябва да преминат указатели към подвижен елемент, предхождащи изтривани първия и последния елементи. При изтриване указател към първия елемент предхождащ елемент да бъде равна на нула (NULL). Тази функция автоматично актуализира индексите започват и последен. ако някой от тях се отнася до влизането да бъдат премахнати.

В свързан списък, има един голям недостатък: не е възможно да прочетете свързан списък и в обратната посока. Поради тази причина, често се използва двойно-свързани списъци.

[1] Не забравяйте, че свързан списък, като въжето, на двата края: в началото и в края.
[2] Често наричан още Sentinel.