Напредне структуре
Манипулација са низовима
Правилно налажење слободног слота
Овај пример показује како пронаћи слободно место у низу користећи стандардне програмске праксе.
new
gMyArray[10];
stock FindEmptySlot()
{
new
i = 0;
while (i < sizeof(gMyArray) && gMyArray[i])
{
i++;
}
if (i == sizeof(gMyArray)) return -1;
return i;
}
Ово основно објашњење претпоставља да је слот у низу празан ако му је вредност 0. Петља пролази кроз све вредности у низу (што се такође може урадити са константом) докле год вредности нису 0. Када достигне вредност која је 0, услов у петљи ће не успети и петља завршава без коришћења break што је уобичајена пракса, али се не препоручује у ситуацијама као што је ова. Ова функција такође враћа -1 ако слободни слот није пронађен, што би требало да се провери на другом крају. Уобичајеније би било користити пронађени идентификатор одмах:
MyFunction()
{
new
i = 0;
while (i < sizeof (gMyArray) && gMyArray[i])
{
i++;
}
if (i == sizeof (gMyArray))
{
printf("No free slot found");
return 0;
}
printf("Slot %d is empty", i);
// Користите пронађени слот у вашем коду за шта год желите
return 1;
}
Очигледно би заменили израз "gMyArray[i]" са вашим сопственим индикатором слота у употреби.
List
Introduction
Lists are a very useful type of structure, they're basically an array where the next piece or relevant data is pointed to by the last piece.
Example:
Say you have the following array:
3, 1, 64, 2, 4, 786, 2, 9
Ако желите да сортирате низ, завршили бисте са:
1, 2, 2, 3, 4, 9, 64, 786
Ако, међутим, желите да оставите податке у оригиналном редоследу али и да их знате по редоследу бројева из неког разлога (само је пример), имате проблем, како треба да имате бројеве у два реда одједном? Ово би била добра употреба листова. Да бисте из ових података направили листу, требао би вам дводимензионални низ где је друга димензија величине 2 ћелије, прва димензија садржи оригинални број, а друга индекс следећег највећег броја. Такође бисте морали имати посебну променљиву да бисте држали индекс најмањег броја, па би ваш нови низ изгледао овако:
start = 1
3, 1, 64, 2, 4, 786, 2, 9
4, 3, 5, 6, 7, -1, 0, 2
Следећи индекс повезан са 786 је -1, што је невалидан индекс низа и означава крај листе, тј. нема више бројева. Оба броја 2 очигледно могу бити у оба реда, прва јединица у низу је и прва у листи јер је највероватније да ће се прво сусрести.
Друга предност овог метода сортирања бројева је да је додавање више бројева много брже. Ако бисте желели да додате још један број 3 у сортиран низ, морали бисте прво померити барем 4 броја за једно место у десно да направите простор, што није страшно овде, али веома споро код већих низова. Са верзијом листе, могли бисте само додати 3 на крај низа и изменити једну вредност у листи:
start = 1
3, 1, 64, 2, 4, 786, 2, 9, 3
8, 3, 5, 6, 7, -1, 0, 2, 4
^ измените ову вредност ^ следећи највиши слот
Ниједан други број није померен, па ниједни индекси нису потребни за ажурирање, само направите да следећи најнижи број показује на нови број и направите да нови број показује на број на који је следећи најнижи показивао. Уклањање вредности је још лакше:
start = 1
3, 1, 64, X, 4, 786, 2, 9, 3
8, 6, 5, 6, 7, -1, 0, 2, 4
^ Changed to jump over the removed value
Овде је прва 2 уклоњена и број који је показивао на ту вредност (1) је ажуриран да показује на вредност на коју је уклоњена вредност показивала. У овом примеру, ни показивач ни број уклоњене вредности нису заиста уклоњени, али не можете приступити тој локацији следећи листу, па није битно, ефективно је уклоњено.
Типови
Листе у горе наведеним примерима биле су само основне једноструке листе, али можете имати и двоструке листе где свака вредност показује на следећу вредност и последњу вредност. Обично имају и показивач на крај листе да би се могло кретати уназад (нпр. да се добију бројеви у силазном поретку):
start = 1
end = 5
value: 3, 1, 64, 2, 4, 786, 2, 9, 3
next: 8, 3, 5, 6, 7, -1, 0, 2, 4
last: 6, -1, 7, 1, 8, 2, 3, 4, 0
Морате бити пажљиви са овима, посебно када имате више од једне вредности, тако да последњи показивач показује на вредност чији се следећи показивач одмах враћа, на пример ово је погрешно:
2, 3, 3
1, 2, -1
-1, 2, 0
Показивач следеће вредности за 2 показује на 3 у слоту један, али показивач последње вредности за ту тројку не враћа се на два, оба списка су у реду по њиховом редоследу (будући да два тројка могу бити било који други начин), али заједно су погрешни, исправна верзија би била:
2, 3, 3
1, 2, -1
-1, 0, 2
Оба ова списка почињу и завршавају на последње две бројке, задњи списак у погрешном примеру почиње са средњим бројем.
Други тип списка је петља где последња вредност показује на прву. Очигледна предност овога је што можете доћи до било које вредности од било које друге вредности без претходног знања да ли је циљ испред или иза почетне тачке, само треба пазити да не уђете у бесконачну петљу пошто нема експлицитне -1 крајне тачке. Ови списци и даље имају почетне тачке. Можете такође направити двоструко петљење списака где имате следећи и последњи списак, оба која се петљају:
start = 1
end = 5
3, 1, 64, 2, 4, 786, 2, 9, 3
8, 3, 5, 6, 7, 1, 0, 2, 4
6, 5, 7, 1, 8, 2, 3, 4, 0
Мешани списи
Мешани списи су низови који садрже више списака одједном. Пример би могао бити низ вредности, сортиран списком, са другим списком који повезује све неискориштене слотове тако да знате где можете додати нову вредност. Пример (X значи неискориштен (слободан) слот):
sortedStart = 3
unusedStart = 1
value: 34, X, X, 6, 34, 46, X, 54, 23, 25, X, 75, X, 45
sort: 4, 8, 13, 7, 11, 9, 0, -1, 5
free: 2, 6, 10, 12, -1
Очигледно је да се два списка никада не мењају, па оба могу користити исти слот за њихову следећу вредност:
sortedStart = 3
unusedStart = 1
value: 34, X, X, 6, 34, 46, X, 54, 23, 25, X, 75, X, 45
next: 4, 2, 6, 8, 13, 7, 10, 11, 9, 0, 12, -1, -1, 5
Код
Пре него што почнете са кодом, морате одлучити који вид листе је најбољи за вашу апликацију, што се потпуно заснива на апликацији и није лако покрити овде. Сви ови примери су мешани списци, један за потребне вредности, а један за неискоришћене слотове.
Овде је приказано како написати код за листу која је нумерички сортирана у узлазном редоследу.
#define NUMBER_OF_VALUES (10)
enum E_DATA_LIST
{
E_DATA_LIST_VALUE,
E_DATA_LIST_NEXT
};
new
gListData[NUMBER_OF_VALUES][E_DATA_LIST],
gUnusedStart = 0,
gListStart = -1; // Почиње без листе
// Ова функција иницијализује листу
List_Setup()
{
new
i,
size = NUMBER_OF_VALUES;
size--;
for (i = 0; i < size; i++)
{
// На почетку су сви слотови неискоришћени
gListData[i][E_DATA_LIST_NEXT] = i + 1;
}
// Заврши листу
gListData[size][E_DATA_LIST_NEXT] = -1;
}
// Ова функција додаје вредност на листу (користећи основно сортирање)
List_Add(value)
{
// Провера да ли има слободних слотова у низу
if (gUnusedStart == -1) return -1;
new
pointer = gListStart,
last = -1,
slot = gUnusedStart;
// Додај вредност на низ
gListData[slot][E_DATA_LIST_VALUE] = value;
// Ажурирај неиспуњену листу
gUnusedStart = gListData[slot][E_DATA_LIST_NEXT];
// Петља кроз листу док не дођемо до већег/истог броја
while (pointer != -1 && gListData[pointer][E_DATA_LIST_VALUE] < value)
{
// Сачувај позицију последње вредности
last = pointer;
// Пређи на следећи слот
pointer = gListData[pointer][E_DATA_LIST_NEXT];
}
// Ако смо дошли до овде, потрошили смо вредности или стигли до веће
// Проверите да ли смо проверили неке бројеве
if (last == -1)
{
// Први број је већи или нема листе
// У оба случаја додајте нову вредност на почетак листе
gListData[slot][E_DATA_LIST_NEXT] = gListStart;
gListStart = slot;
}
else
{
// Стави нову вредност на листу
gListData[slot][E_DATA_LIST_NEXT] = pointer;
gListData[last][E_DATA_LIST_NEXT] = slot;
}
return slot;
}
// Ова функција уклања вредност са датог слота у низу (враћено од List_Add)
List_Remove(slot)
{
// Да ли је ово важан слот
if (slot < 0 || slot >= NUMBER_OF_VALUES) return 0;
// Прво пронађите слот пре
new
pointer = gListStart,
last = -1;
while (pointer != -1 && pointer != slot)
{
last = pointer;
pointer = gListData[pointer][E_DATA_LIST_NEXT];
}
// Да ли смо пронашли слот на листи
if (pointer == -1) return 0;
if (last == -1)
{
// Вредност је прва на листи
// Прескочите овај слот на листи
gListStart = gListData[slot][E_DATA_LIST_NEXT];
}
else
{
// Вредност је на листи
// Прескочите овај слот на листи
gListData[last][E_DATA_LIST_NEXT] = gListData[slot][E_DATA_LIST_NEXT];
}
// Додајте овај слот на неиспуњену листу
// Неиспуњена листа није у неком редоследу, тако да то није битно
gListData[slot][E_DATA_LIST_NEXT] = gUnusedStart;
gUnusedStart = slot;
return 1;
}
Бинарна стабла
Увод
Бинарна дрвета су веома брз метод претраге података у низу користећи веома специјалан систем листова. Најпознатије бинарно дрво је вероватно игра од 20 питања, са само 20 да/не питања можете имати преко 1048576 ставки. Бинарно дрво, као што његово име указује, је тип стабла, слично породичном стаблу, где свака ставка има 0, 1 или 2 деце. Не користе се за поређење података као листа, већ за сортирање података за веома ефикасну претрагу. Основна идеја је да почнете са ставком негде близу средине поређане листе објеката (на пример, средњи број у сортираном низу) и поредите је са вредношћу коју желите пронаћи. Ако је исто, пронашли сте своју ставку, ако је веће, премештате се на ставку десно (не одмах десно, ставка десно од средње ставке би била ставка на три четвртине), ако је мање, премештате се лево, па поновите процес.
Пример
1 2 5 6 7 9 12 14 17 19 23 25 28 33 38
Имате претходно поређани низ и желите пронаћи у којем је слоту број 7 (ако уопште постоји), у овом примеру вероватно је ефикасније просто пролазити кроз низ да бисте га пронашли, али то није суштина, та метода време потраге повећава линеарно са величином низа, док време бинарне претраге расте експоненцијално са увећањем величине низа. Тј. низ од 128 ставки ће узети дупло више времена да се претражи просто у пореду као низ од 64 ставке, али бинарна претрага од 128 ставки ће узети само једну проверу више него бинарна претрага од 64 ставке, врло мало.
Ако конструишемо бинарно дрво из горе наведених података добијамо: 
Ако читате са лева на десно, игноришући вертикални аспект, видите да су бројеви у редоследу. Сада можемо покушати пронаћи број 7.
Почетни број је 14, 7 је мањи од 14, па идемо на слот на који показује леви грана 14. Ово нас доводи до 6, 7 је већи од 6, па идемо десно до 9, затим опет лево до 7. Овај метод је узео 4 поређења да пронађе број (укључујући крајњу проверу да потврдимо да смо на 7), коришћењем обичне претраге било би потребно 5.
Рецимо да нема 7, имали бисмо овакво бинарно дрво: 
Ово, за разлику од претходног примера, има једног детета (9), као и 2 и 0 детета. Добијате савршено дрво само када имате (2^n)-1 бројева (0, 1, 3, 7, 15, 31 ...), било који други бројеви дају не баш пуну стаблу. У овом случају када дођемо до 9, где ће бити 7, открићемо да нема леве гране, што значи да 7 не постоји (не може бити нигде другде у стаблу, размислите о томе), па враћамо -1 за неисправан слот.
Балансирани и не балансирани
Стабла у горе наведеним примерима се зову балансирана бинарна стабла, што значи да су све гране приближно исте дужине (очигледно у другом примеру нема довољно бројева да би то било тако, али је што је могуће ближе). Конструисање балансираних стабала није једноставно, опште прихваћени метод конструкције скоро балансираних стабала је стављање бројева у насумичном редоследу, ово може значити да ћете на крају имати нешто као на пример ово: 
Очигледно је да је ово стабло још увек исправно, али десна страна је много већа од леве, међутим проналазак 25 још увек захтева само 7 поређења у овом случају у поређењу са 12 у обичном списку. Такође, докле год почнете са прилично средњим бројем, метод убацивања насумичног уношења треба да произведе приближно балансирано стабло. Најгора ствар коју можете учинити је да ставите бројеве по редоследу јер онда неће бити ни левих грана (или десних грана ако је обраћено), међутим иако је у овом најгорем случају бинарном стаблу потребно исто време да претражи као и обични списак.
Модификација
Додавање
Додавање вредности у бинарно стабло је релативно једноставно, само пратите стабло кроз, користећи вредност коју желите да додате као референцу док не стигнете до празног гране и онда додате број на том месту. Нпр. ако бисте желели да додате број 15 у наше оригинално балансирано стабло, завршили бисте на левој гране од 17. Ако бисмо желели да додамо број 8 у друго балансирано стабло (оно без 7) завршили бисмо на старом слоту за 7 на лево од 9.
Брисање
Брисање броја из бинарног стабла може бити тешко или лако. Ако је број на крају гране (нпр. 1, 5, 7, 12 итд. у оригиналном стаблу) једноставно их уклоните. Ако број има само једно дете (нпр. 9 у другом примеру) једноставно преместите то дете (нпр. 12) у њихову позицију (тако да би деца од 6 била 2 и 12 у новом другом примеру са 9 уклоњен). Брисање постаје интересантно када је нод има два детета. Постоји најмање четири начина да се то уради:
Први метод је најједноставнији за рачунарску обраду. Основна идеја је да изаберете један од грана (леву или десну, претпоставимо десну за ову објашњење) и заменимо нод који сте уклонили са првим нодом те гране (тј. десним дететом нода који сте уклонили). Затим идете лево кроз нову грану док не стигнете до краја и ставите леву грану тамо. Нпр. ако сте уклонили 14 из оригиналног примера, завршили бисте са 25 на врху стабла и 6 придруженом левој грану од 17. Ова метода је брза али брзо доводи до врло не балансираних стабала.
Други метод је да се сви бројеви који су деца нода који сте управо уклонили поново изграде у ново бинарно стабло, а затим ставите врх тог стабла у нод који сте управо уклонили. Ово чува стабло приближно балансираним али је очигледно спорије.
Трећи метод је да се комбинују два претходна метода и поново изграде стабло на месту, ово је комплексније за кодирање али чува стабло балансираним и брже је него други метод (иако нигде није толико брз као први).
Последњи наведени метод је једноставно поставити заставицу на вредност која каже да се више не користи, ово је још брже од првог метода и одржава структуру али значи да не можете поново користити слотове осим ако касније не пронађете вредност за замену.