Динамичното разпределение съхранение
функция Р = разпределят (N) връща указател към памет обект на дължина N една,
В C - р = нов (N) (неопределен вид указател).
1) типизиране курсор.
На езика на силно типизиране Int * р и овъгляване * г - не са еквивалентни => трябва да въведете превръщане.
2) Освобождаване на заделената памет
· Ясно механизъм (програмист) - функция унищожи (р);
· Не е ясен механизъм (ОС) - е унищожена, когато няма връзка с обекта може да се извършва чрез таймер за завършване на програмите и в, преливник.
3) Проблемът с висящи предмети (когато един динамични obeks се отнася до друг динамичен обект)
Споменът все още се противопоставя на липсата на препратки. Унищожаването на обекта, може да загубите всичките си препратки към subobjects.
4) Проблемът с висящи указатели (ostyutsya препратки към изтрити обекти);
5) фрагментация на паметта
Унищожи P3 и Р5 - новия обект паметта е достатъчно, но няма твърда
Когато се работи с динамична памет в присъствието на явни механизми унищожаване:
1) Да не се допуска наличието на висящи предмети. За да направите това, първо трябва да унищожи всички вградени обекти.
2) Да се избягва висящи референции, т.е. след унищожаването на обекта за унищожаване и връзка към него - .. P = NULL.
3) Намаляване фрагментация. За да направите това, вие трябва да унищожи предмети в обратен ред на тяхното създаване: p5 - P4 - P3.
Изпълнение на динамичен механизъм памет в C:
1) Изолиране на купчината чрез функция невалидни * изчистване на (размер size_t).
Например, ако имате нужда от масив от 10 елемента, след което:
може да бъде по-голяма, отколкото се изисква size_t размер на необходимия размер памет (за подравняване)
2) Функция нищожен * calloc (size_t бр, size_t размер);
всички стойности в паметта не е получил никакви.
3) без шупли (невалидни * р)
указател показва блок памет предварително заловен операции изчистване, calloc, презаделяне, т. е. броят на байтовете освободен = брой байтове, получени в улавянето
Int превръщане без шупли ((невалидни *) А);
4) невалидни функция * презаделяне (невалидни * р, size_t нов размер)
Преоразмерявате памет блок преди заловен, стр - указател към началото на блока, размер - размера в байтове. Блокът може да бъде преместен в паметта, когато преоразмеряване.
Дървета. Определение, класификация, начини на представяне.
Wood с основа тип Т - е:
1) или празен дърво
2) или върха на Т с определен брой свързани отделните дървета с основа тип Т (поддървета).
(Wood, посочена всеки връх - поддърво)
Top, които пряко се отнася до друг връх - нейната потомък. Свържи се с връх - предшественик.
Top, който няма наследници - листът на дървото.
Ако сме номер върховете, така че всеки следващ е наследник на едно ниво по-високо, върховете при 0 ниво - в основата на дървото.
Най-високо, което не е листо - интериор връх.
Нивото на всеки връх - дълбочината (височина). и дълбочината на дървото - максимална дълбочина на всички негови върхове.
Брой на преки потомци на връх е степента на степента на връх на едно дърво - максимума от всички възможни степени.
Броят на клонове (ръбове), което е необходимо да се премине от корена на връх х се нарича дължината на пътя на х (корен път е 0).
Дължината на пътя на цялото дърво (вътрешна дължина на пътя) - сумата от дължините на пътища за всички негови върхове.
Средната дължина на пътя, се определя от формула :.
Дървото се нарича санитаря. Ако са подредени всички клонове, произтичащи от всеки възел.
Поръчаните дървета са на втора степен се наричат двоични дървета.
N-солна дървета (над 2) се наричат силно разклоняване степен.
Дървета с минимална височина, посочени перфектно балансирани (броят на върховете в ляво и дясно-дървото се различава с не повече от 1 - условието за всички върхове).
Изразяването на такива рекурсивни структури изисква използването на връзки.
Има много различни начини, за да представляват дървета (пример за двоично дърво):
1) списък оглед двоично дърво на основата на елементите, съответстващи на възлите на дървото. Всеки елемент има поле за данни и двата показалеца области. Указателят се използва за свързване на елемент с дясната дете, а друг - в ляво. Листата са празни низходящи указатели. С този метод на представяне на дървото, не забравяйте да запишете указател към възела, който е в основата на дървото.
Може да се отбележи, че този метод на представяне е подобно на простите линейни списъци. И това сходство не е случайно. Всъщност смята за начин за представяне на двоичен дърво е вид multispiska формира от набор от линейна комбинация от списъци. Всеки линеен списък комбинира възли по пътя от корена на дървото на един от листата.
структура binary_tree * ляво;
структура binary_tree * право;
Тогава празен дървото само да се определи чрез създаване Коренът на нула:
Root = NULL;
2) Под формата на масив лесният изглежда пълно двоично дърво, защото то винаги има строго определен брой върхове във всяко ниво. Върховете могат да бъдат номерирани последователно от ляво на дясно през нивата и използва тези номера като индекс в едномерен масив.
Ако броят на нивата на дървото по време на лечението няма да се промени значително, такъв начин на представяне на пълно двоично дърво ще бъде много по-икономичен от всеки списък структура.
Основният недостатък обсъжда начини да представляват двоичен дърво е, че структурата на данните е статична. Размерът на масива се избира въз основа на максималния възможен брой двоични нива на дърветата. И малко от пълна дървен материал, толкова по-малко памет се използва ефективно.
Двоични операции дърво.
Binary Tree - ограничен набор от елементи (възли), който е или празна, или се състои от корен с две отделни двоични поддървета се наричат ляво и дясно поддърво на корена.
За да се конструира двоично дърво с N върха, с минимална височина, използвайте следните правила:
0) Ако п = 0, тогава спре;
1) Изграждане отгоре
2) Изграждане с ляво поддърво възли;
3) Изграждане с право поддърво на възли.
Операции с двоични дървета:
· Представката кръг - отгоре, отляво, отдясно (+ аб):
prefix_walk (структура binary_tree * т)
· Инфикса заобикаляйки - наляво, отгоре, полето (А + В);
· Postfix - ляво, дясно, отгоре (AB +);
Ако използвате, за да открие елементите на данните за стойността на уникален ключ се използва двоично търсене търсене дърво дърво - всички възли в правилната поддървото> х (горе), всички възли в лявата поддървото N елементи могат да бъдат организирани в двоичен дърво с височина не повече от log2 (N). Ето защо, за да се намери сред елементите N може да изисква не повече от log2 (N) сравнения, ако дървото е перфектно балансиран. От това следва, че дървото - тя е по-подходяща структура за организиране на търсене, например, от линеен списък.Свързани статии