Динамични списъци 1

Свързаните списъци - структурата на данните, съставен от възли, всеки от които съдържа както действителните данни и един или два линка ( "връзка") към следващия и / или предишен възел в списъка. Съществуват няколко вида на списъци, ето някои от тях: просто свързани еднопосочно, просто се поставя двойно свързан пръстен носител, двойно свързан пръстен.

Поотделно свързан списък еднопосочно.

Чрез просто свързан еднопосочно списък подразбира изпълнение серия подреждане на елементи, изложени. Като се започне с определен възел, ние вярваме, че е на първо място в този сайт има връзки към следващия, и така нататък. В повечето случаи, на първата точка като празен, защото тогава е по-лесно да се работи с списъка. В свързан списък, всеки възел има препратка единствено към следващия елемент, тоест, не можем да се премести в края на списъка, преди да започне. Еднопосочното списък завършва с позоваване NULL.

Нека да мислим за това, което бихме могли функции трябва да работите със списъка. Може би това - организацията на списъка, сортиране на списък изход, вмъкване на нов елемент в списък, подредени. Така че първо трябва да се организира самия възел, от съвкупността от които ще формират списъка.

Сега ние трябва да започнем да се създаде променлива от тип списък, който ще сочи към първия елемент
списък.

списък * старт = нов списък; // памет за първа точка
стартов> следващата = NULL; // в този момент първият елемент е в същото време и последният е в непосредствена близост се отнася до NULL

Точно както ние памет за първия елемент, просто трябва да се направи, както и за всички последващи такива.
А сега да разгледаме част от кода, който ще генерира списък.

списък * p_list = започне;
за (INT I = 0; и<20; i+=2)
списък * TMP = нов списък; // памет за
tmp-> т = I; // тук всичко е ясно
tmp-> следващата = NULL; // ние вмъкнете възел в края на списъка и така следващия = NULL
p_list-> следващата = ТМР; // сега p_list-> следващите точки пред създаден възел
p_list = p_list-> следващата; // Преместете показалеца на последния елемент.
>

Тук ние използваме работа показалеца, за да не се промени в началото, която винаги сочи към първия възел в списъка. След изпълнението на този код нашия списък изглежда така:

Нека да извлече конзола създаден списък. За да направите това, напишете отделна функция:

нищожен шоу (списък * започнете) // създаване - на върха на показалеца на списък.
списък * p_list; // указател работник
p_list = стартов> следващия; // в началото, той се отнася до втория възел в списъка.






докато (p_list! = NULL)
Cout <артикул < p_list = p_list-> следващата; // движи показалеца на един възел.
>
>

списък * ТМР = нов списък; // памет за новия възел
tmp-> т = ел;
tmp-> следващата = p_list-> следващата;
p_list-> следващата = ТМР; // Поставете възел след възел, посочи от p_list
прекъсване;
>
p_list = p_list-> следващата; // поставяне на курсора на следващия елемент.
ако (p_list-> следващата == NULL ел> = p_list-> т) // проверка не е необходима, за да вмъкнете възел на списъка.
списък * TMP = нов списък;
tmp-> т = ел;
tmp-> следващата = NULL; // Тъй като ние вмъкнете възел в края на списъка на следващия елемент, че трябва да се отнася към NULL
p_list-> следващата = ТМР; // вложка възел в списъка.
прекъсване;
>

Опитайте се да се направи схема на елемент на вмъкване в списъка. Това е вашата домашна работа)
Сега пиша функция, която ще подредите списъка. Ние ще използваме един от най-простите алгоритми за сортиране - метод на мехурчето.

нищожен вид (списък * започнете) // създаване - на върха на показалеца на списък.
списък * p_list; // указател към външната страна на tsykla
списък * pp_list; // за вътрешно
за (p_list = стартов> до ;! p_list = NULL; p_list = p_list-> следващата) // минава през списък на всички възли
за (pp_list = стартов> до ;! pp_list-> следващата = NULL; pp_list = pp_list-> следващата) // но тук само към възела, до която посочва NULL
// нормални стойности за обмен
ако (pp_list-> т> pp_list-> от следващо> т)
Int ТМР;
ТМР = pp_list-> т; //
pp_list-> т = pp_list-> от следващо> т;
pp_list-> от следващо> т = ТМР;
>

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

нищожен Dell (списък * старт, Int ел) // указател към горната част на списъка и стойността, която ние се стремим в списъка, ако намерим средства за изтриване.
списък * p_list = стартов> следващата; // указател работник, който ще бъде използван, за да преминете през списъка.
списък * предишна = започне; // указател, който винаги ще сочи към предишния елемент, за да p_list.
докато (p_list! = NULL) // работи в пълен списък
// провери - дали премахването на необходимостта да
ако (p_list-> т == ел)
// timesign възел, който ще запише стойността на възел да бъде заличена.
списък * TMP = нов списък;
* Tmp = * p_list;
// сега ние трябва да направим така, че следващия елемент на предишния възел сочи възел, който е след p_list, т.е. p_list-> следващия
prev-> следващата = p_list-> следващата;
изтриете ПТУ;
>
предишна = p_list; // движи назад показалеца на един елемент
p_list = p_list-> следващата; // просто се движат по-нататък.
>
>

Ето как се оглежда:

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

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

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