Динамичке структуре – ред

Радио: Никола Радовановић


Увод

У овом уводу укратко ће бити објашњен појам динамичких типова података, и разлика у односу на статичке типове података.
Концентрисаћу се на теме везане за писање програма у програмском језику C++ .

Динамички типови података се, у основи, разликују од статичких типова података. Овај тип података је уведен због потребе за уштедом меморијских ресурса рачунара.

Статички типови података се чувају у DATA SEGMENT-у. Њихов број (тј. меморија коју ће заузети) се декларише на почетку програма. Дакле, њихов број мора бити унапред познат.
Програмер мора често да одвоји више меморијских локација за податке него што је заиста потребно, јер не зна шта ће корисник тражити од програма.Тако да програм често користи и десетоструко дуже низове и структуре него што ће корисник икад искоритити у истом. То је главна мана код оваквог писања програма.
Кончно, терминирањем програма, аутоматски се ослобађа меморијски простор који је заузео овај програм.
Динамичке промењиве се, у ове две ставке, разликују од статичких. Код ових типова података се не мора унапред знати колико ће промењивих бити потребно програму за рад.
Меморијски простор за промењиве резервише се и ослобађа током извршења програма функцијама као што су – calloc() ,malloc(), free()…. (описи ових функција налазе се у библиотеци <alloc.h> ).

Меморијске локације које резевишу, налазе се на HEAP-у, и приступамо им преко показивача које декларишемо у main-у, или као екстерне промењиве. Терминирањем програма неће се ослободити меморијске локације у HEAP-у, него их морамо ослободити пре затварања програма функцијом free().

Код near меморијских модела, HEAP се налази између DATA SEGMENT-а и STACK-а, и могуће је преклапање са STACK-ом, јер се и један и други шире према слободном простору између. Док tiny меморијски модел може користити само near HEAP, Small i medium модел могу користити и far HEAP који се налази изнад STACK-а.

Far меморијски модели користе искључиво far HEAP, који може да се шири до краја физичке меморије.
Програмски језик C++ користи по default-у small меморијски модел. При изради једноставнијих програма он се показао као довољан, али за веће програме препоручује се коришћење неког far модела.
Функција malloc() резервише меморијски простор за једну промењиву величине n бајтова, и враћа показивач на податке типа char. Показивач који функција враћа можемо конвертовати у показивач неког другог типа. Пример:

(int *a; unsigned n;)
a=(int *)malloc(n);

Ова конверзија није заиста неопходна, јер у новијим верзијама C++-а конверзија се врши аутоматски, јер функција malloc() враћа генерички показивач типа (void *). Ако не знамо напамет колико меморије користи неки тип података (нпр. struct lista{…}LISTA;), можемо у загради функције malloc(), уместо броја n, ставити оператор sizeof(tip podataka). Пример:

(LISTA *pokazivac;)
pokazivac=(LISTA *)malloc(sizeof(LISTA));

За адресирање far HEAP-а користимо функцију farmalloc(), са истим аргументима као и malloc(), при чему би требало знати да tiny меморијски модел неће радити са farmalloc()).

Ако желимо одједном да алоцирамо више меморијских локација у HEAP-у, користимо функцију calloc();

(unsigned x;)
pokazivac=(LISTA *)calloc(x,sizeof(LISTA));

Овим поступком резервишемо x*(sizeof(LISTA)) меморијских локација. Функција calloc() ове меморијске локације испуњава нулама.
За far HEAP користимо функцију farcalloc().Ова функција такође не може да ради са tiny меморијским моделом.
Да не би меморија резервисана на овај начин остала заузета (неупотребљива), меморијске локације које смо заузели ослобађамо употребом функције free(). Та радимо тако што за улазну вредност функције ставимо показивач на меморијску локацију коју желимо да ослободимо. Пример:

free(pokazivac);

Функција free() не враћа никакву вредност. За ослобађање меморијских локација у far HEAP-у користимо farfree(). Farfree() не ради са tiny меморијским моделом.

РЕД

Ред је врста стек меморије са FIFO начином рада (first in–first out).

Његова хардверска изведба је слична процесорском или графичком pipeline-у (цевоводу), са разликом што класичан pipeline обрађује податке док пролазе кроз њега. Принцип кретања података остаје исти – подаци који први уђу у ред, први излазе из њега.
Ми ћемо се бавити логичком организацијом реда у оперативној меморији.

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
typedef struct red_st{
char inf;
struct red_st *sledeci;
};
typedef red_st *RED_ST;
RED_ST p_red=NULL; //globalna promenjiva
void pisi(char ch)
{RED_ST novi, pomocni;
novi=(RED_ST)malloc(sizeof(red_st));
novi->inf=ch;
novi->sledeci=NULL;
if(p_red==NULL)
{p_red=novi;
}else
{ pomocni=p_red;
while(pomocni->sledeci!=NULL)
pomocni=pomocni->sledeci;
// posle 'while' ciklusa, "pomocni" pokazivaće na poslednji element
// u listi
pomocni->sledeci=novi;}}


—————————————————————————————–
функција 
pisi има значење еквивалентну наредби push. Из main-а узима карактер, и креира динамичку структуру. Користимо глобални показивач на почетак реда, тако да га могу функције нормално мењати
———————————————————————————–

void citaj(char *ch)
{RED_ST novi_pocetak;
*ch=p_red->inf;
novi_pocetak=p_red->sledeci;
free(p_red);
p_red=novi_pocetak;
}

———————————————————————————–

функција citaj је слична наредби pop, али узима елементе реда са супротне стране. Предаје карактер main-у, и ослобађа меморијски простор заузет структуром са којом ради

———————————————————————————–

void main()
{char ch;
int i;
clrscr();
// Upis u red ('a'..'z')
printf("\n\n\n\n\nUpis znakova u red: ");
for(ch='a'; ch<='z'; ch++)
{pisi(ch);
printf("%c",ch);}
//Iscitavanje reda (26x)
printf("\nIscitavanje reda: ");
for(i=1; i<=26; i++)
{citaj(&ch);
printf("%c",ch);
}
}

———————————————————————————–
главна функција main ,уз помоћ петљи, 26пута врти функције pisi и citaj. Преко функције pisi пуни структуре са 26 малих карактера (конкретно од a до z), а преко функције citaj исписује на екран.
Промењива 
*p_red је кориштена као глобална, да би могли директно да је мењамо из функција, уместо преко њене адресе.
Рад програма:

Upis znakova u red: abcdefghijklmnopqrstuvwxyz
Iscitavanje reda: abcdefghijklmnopqrstuvwxyz

Advertisements

Оставите одговор

Попуните детаље испод или притисните на иконицу да бисте се пријавили:

WordPress.com лого

Коментаришет користећи свој WordPress.com налог. Одјавите се / Промени )

Слика на Твитеру

Коментаришет користећи свој Twitter налог. Одјавите се / Промени )

Фејсбукова фотографија

Коментаришет користећи свој Facebook налог. Одјавите се / Промени )

Google+ photo

Коментаришет користећи свој Google+ налог. Одјавите се / Промени )

Повезивање са %s