Големина на текста:
Съставни структури от данни. Списъци. Дървета
Списъци
Свързани списъци – последователно преминаване от един на един през съвкупност от
елементи се организират като свързан списък – основна структура от данни, където
всеки елемент съдържа информация, необходима, за да се достигне следващия елемент.
Главно предимство на свързаните списъци пред масивите е, че списъци ни снабдяват
със способността ефективно да преподреждаме елементите. Има няколко начина за
организиране на свързани списъци, всички започващи със следната дефиниция: свързан
списък е множество от елементи, където всеки елемент е част от възел, който
също съдържа връзка към възел.
Възлите се дефинират под формата на указатели към възли, така че към свързаните
списъци понякога се отнасяме като към самосвързани структури. Свързания списък
може да бъде също и циклична структура, но като цяло се считат като реализация на
последователна подредба на множество от елементи.
Първо се разглеждат възли с точно една връзка и в повечето приложения се работи с
едносвързани списъци, където всички възли, с изключение може би на първия и
последния, имат точно по една връзка, сочеща към тях. В някои среди за програмиране
свързаните списъци се дефинират като променливи. Заделянето на памет е централно
условие за ефективната употреба на свързаните списъци. Въпреки дефинирането на
единична структура (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

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

За да разгледате всички страници от този документ натиснете тук.

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

Съставни структури от данни. Списъци. Дървета...
Изпратен от:
ssena
на 2007-06-11
Добавен в:
Теми
по Програмиране
Статистика:
339 сваляния
виж още
 
Домашни по темата на материала
Да се направи код и графика на алгоритъма на работа на Форд Фалкерсон
добавена от topul_dujd 14.11.2014
0
3
Подобни материали
 

Задача по C++

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

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

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

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

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

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

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

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

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

16 мар 2006
·
152
·
8
·
690

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

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

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

Настройване на програми на асемблерен език - задачи с решения към тях. Упражнение.
1 2 3 4 5 » 11
 
Онлайн тестове по Програмиране
ПСТ-1
изпитен тест по Програмиране за Студенти от 3 курс
Тест по ПСТ-1 ТУ София, ИПФ Сливен. Всеки въпрос има само един верен отговор.
(Труден)
21
8
1
4 мин
28.05.2015
Програмиране С++
изпитен тест по Програмиране за Студенти от 3 курс
Тестът включва въпроси върху указатели, програмиране С++, структури от данни. Всички въпроси са затворени и изискват само един верен отговор.
(Труден)
20
13
1
4 мин
02.10.2014
» виж всички онлайн тестове по програмиране

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

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

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

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

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

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

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

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