Големина на текста:
Съставни структури от данни. Списъци. Дървета
Списъци
Свързани списъци – последователно преминаване от един на един през съвкупност от
елементи се организират като свързан списък – основна структура от данни, където
всеки елемент съдържа информация, необходима, за да се достигне следващия елемент.
Главно предимство на свързаните списъци пред масивите е, че списъци ни снабдяват
със способността ефективно да преподреждаме елементите. Има няколко начина за
организиране на свързани списъци, всички започващи със следната дефиниция: свързан
списък е множество от елементи, където всеки елемент е част от възел, който
също съдържа връзка към възел.
Възлите се дефинират под формата на указатели към възли, така че към свързаните
списъци понякога се отнасяме като към самосвързани структури. Свързания списък
може да бъде също и циклична структура, но като цяло се считат като реализация на
последователна подредба на множество от елементи.
Първо се разглеждат възли с точно една връзка и в повечето приложения се работи с
едносвързани списъци, където всички възли, с изключение може би на първия и
последния, имат точно по една връзка, сочеща към тях. В някои среди за програмиране
свързаните списъци се дефинират като променливи. Заделянето на памет е централно
условие за ефективната употреба на свързаните списъци. Въпреки дефинирането на
единична структура (struct node) има много екземпляри на тази структура, един за
всеки възел, които могат да се използват. Когато искаме да ползваме, но във възел, е
необходимо да се създаде екземпляр на структурата node и да се заделя памет за нея.
Например: обикновено пишем код, като следния:
Linx = malloc (sizeof * x); за да наредим на функцията malloc от stdlib.h и оператора
sizeof да заделят памет за един възел и да върнат указател към него в променливата х.
Простотата на вмъкването и триенето е raison d’etre на свързаните списъци.
За да се изтрие или премахне възела, следващ даден възел х от свързан списък, се задава
t да сочи възела, който ще бъде премахван, след което се указва връзката на х да сочи
към t ?next.
За да се вмъкне даден възел t към свързан списък в позиция следваща друг даден възел
х се насочва t ? next, след което се насочва x ? next към t.
Заделяне на памет за списъци.
Предимство на свързаните списъци пред масивите е, че те в общия случай нарастват и
намаляват по време на съществуването си. По конкретно – техния максимален размер
не е необходимо да се знае предварително. Основния проблем е да разберем как
системната функция malloc би могла да бъде реализирана. Например при изтриване на
възел от списък, едно е да се пренаредят връзките, така че възела вече да не е закачен за
списъка, но какво прави системата с пространството, заемано от възела?
Системната функция free е противоположна на malloc. Когато не се използва част от
заделената памет, викаме free, за да информиране системата, че паметта е свободна за
по-нататъшна употреба. Всички възли, които не са в някакъв използван списък, могат
да се пазят заедно в едносвързан списък, който се нарича свободен списък.
1
Дървета
Дърветата са математически абстракции, които играят централна роля при
конструирането и анализа на алгоритми, защото:
-дърветата се използват, за да се опишат динамични свойства на алгоритмите;
-с помощта на дърветата се изграждат и използват ясно формулирани
структури от данни, които са конкретна реализация на дървета.
В компютърните приложения една от най-известните употреби на дървовидни
структури е за организация на файлови системи. Има много различни типове дървета и
е важно да се разбере разликата между абстракцията и конкретната реализация, с които
работим, за дадено приложение. Обсъждане без формализация на различните типове
дървета, които са необходими да бъдат разгледани с намаляващ ред на обобщеност:
- дървета, дървета с корен, наредени дървета, м-арни дървета, бинарни дървета.
Едно дърво е непразна съвкупност от върхове и ребра, които удовлетворяват конкретни
изисквания. Върхът е прост обект (също възел), който може да има име и да носи друга
асоциирана информация, а реброто е връзката между два върха. Път в дървото е
списък от различни върхове, в който последователните върхове са свързани с ребра в
дървото. Дефиниращо свойство за дърво е, че има само един път, свързващ всеки два
възела. Несвързано множество от дървета се нарича гора.
Дърво с корен е това, при което един възел е определен за корен на дървото. При
дървото с корен всеки възел е корен на поддърво, състоящо се от този възел и всички
възли под него. Има точно един път между корена и всеки от останалите възли в
дървото. Всеки възел, освен корена, има точно един възел над себе си, който се нарича
негов родител. Възлите директно под даден възел се наричат негови деца. Възлите без
деца се наричат листа или терминални възли. Ако всеки възел има определен брой деца,
появяващи се в определен ред, тогава имаме м-арно дърво. В такова дърво често е
подходящо да се дефинират специални външни възли, които нямат деца.
Бинарно дърво е наредено дърво, състоящо се от два типа възли; ВЪНШНИ ВЪЗЛИ,
които нямат деца и ВЪТРЕШНИ ВЪЗЛИ, имащи точно по две деца.
2

Това е само предварителен преглед

За да разгледате всички страници от този документ натиснете тук.
Последно свалили материала:
ДАТА ИНФОРМАЦИЯ ЗА ПОТРЕБИТЕЛЯ
19 ное 2020 в 19:45 ученик на 22 години от София - kkk?, випуск 2017
24 окт 2019 в 20:33 потребител
06 авг 2019 в 12:19 студент на 23 години от Добрич - Шуменски унивеститет "Епископ Константин Преславски " Колеж-Добрич, факулетет - Колеж Добрич, специалност - ИИТ, випуск 2019
11 мар 2019 в 22:55 родител
01 дек 2018 в 13:50 ученичка на 39 години от Бургас - СОУ "Димчо Дебелянов", випуск 2000
03 юли 2018 в 14:06 ученичка на 28 години от Ямбол - ПГСГ "К. Фичето", випуск 2010
26 апр 2018 в 10:58 студент на 25 години от Добрич - Шуменски унивеститет "Епископ Константин Преславски " Колеж-Добрич, факулетет - Колеж Добрич, специалност - ИИТ, випуск 2016
19 апр 2018 в 14:55 ученик на 25 години от Ловеч - ПМГ, випуск 2014
02 фев 2018 в 16:46 студент на 38 години от София - СУ "Св. Климент Охридски", факулетет - Факултет по математика и информатика, випуск 2020
09 дек 2017 в 19:09 ученик на 24 години от Дулово - СОУ "Христо Ботев", Паисиево, випуск 2015
 
Домашни по темата на материала
Да се направи код и графика на алгоритъма на работа на Форд Фалкерсон
добавена от topul_dujd 14.11.2014
0
3
Подобни материали
 

Задача по C++

24 окт 2006
·
614
·
1
·
208
·
203

Урок по програмиране на Английски език.
 

Основи на входно/изходния интерфейс в среда Windows

09 мар 2006
·
375
·
4
·
684
·
40
·
1

Работа с текст.. Клавиатура.. Мишка.. Таймер..Дъщерни контроли..
 

Създаване на програма

11 мар 2006
·
698
·
3
·
216
·
173
·
1

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

Проследяване изпълнението и настройване на програми на C/C++ с Turbo Debugger

16 мар 2006
·
152
·
8
·
690
·
49

Проследяване изпълнението и настройване на програми на C/C++ с Turbo Debugger - задачи с решения към тях.
 

Настройване на програми на асемблерен език

16 мар 2006
·
202
·
9
·
1,651
·
59

Настройване на програми на асемблерен език - задачи с решения към тях. Упражнение.
1 2 3 4 5 » 11
 
Онлайн тестове по Програмиране
Програмиране и използване на компютрите
междинен тест по Програмиране за Неучащи от 1 клас
Тестът се състои от 21 въпроса върху кратка история на компютрите. Всички въпроси са затворени и изискват един верен отговор.
(Лесен)
21
11
1
3 мин
12.11.2014
Тест по програмиране за 3-ти курс върху PHP
тематичен тест по Програмиране за Студенти от 3 курс
Това е първият тест по Програмиране в среда интернет за трети курс на специалност КТИД. Съдържа 24 задачи - всяка от тях само с по един верен отговор.
(Труден)
24
12
1
4 мин
14.11.2013
» виж всички онлайн тестове по програмиране

Структури от данни

Материал № 34638, от 11 юни 2007
Свален: 339 пъти
Прегледан: 153 пъти
Качен от:
Предмет: Програмиране, Информатика, ИТ
Тип: Тема
Брой страници: 2
Брой думи: 518
Брой символи: 4,118

Потърси помощ за своята домашна:

Имаш домашна за "Структури от данни"?
Намери бързо решение, с помощтта на потребители на Pomagalo.com:

Намери частен учител

Виторио Белоречки
преподава по Програмиране
в град София
с опит от  4 години
267 32

Николай Ненков
преподава по Програмиране
в град София
с опит от  6 години
432 78

виж още преподаватели...
Последно видяха материала
Сродни търсения