logo

Uvod u strukture podataka

Od izuma računala ljudi koriste izraz ' Podaci ' za upućivanje na informacije o računalu, bilo prenesene ili pohranjene. Međutim, postoje podaci koji postoje iu vrstama naloga. Podaci mogu biti brojevi ili tekstovi napisani na komadu papira, u obliku bitova i bajtova pohranjenih u memoriji elektroničkih uređaja, ili činjenice pohranjene u umu osobe. Kako se svijet počeo modernizirati, ovi su podaci postali značajan aspekt svačijeg svakodnevnog života, a različite implementacije omogućile su im da ih drugačije pohranjuju.

Podaci je zbirka činjenica i brojki ili skup vrijednosti ili vrijednosti određenog formata koji se odnosi na jedan skup vrijednosti stavke. Podatkovne stavke se zatim klasificiraju u podstavke, što je skupina stavki koje nisu poznate kao jednostavni primarni oblik stavke.

Razmotrimo primjer gdje se ime zaposlenika može raščlaniti na tri podstavke: ime, srednje i prezime. Međutim, ID dodijeljen zaposleniku općenito će se smatrati jednom stavkom.

Uvod u strukture podataka

Slika 1: Predstavljanje podatkovnih stavki

U gore navedenom primjeru, stavke kao što su ID, Dob, Spol, Ime, Sredina, Prezime, Ulica, Lokalitet itd. su elementarne podatkovne stavke. Nasuprot tome, Ime i Adresa su grupne podatkovne stavke.

Što je struktura podataka?

Struktura podataka je grana informatike. Proučavanje strukture podataka omogućuje nam razumijevanje organizacije podataka i upravljanja protokom podataka kako bismo povećali učinkovitost bilo kojeg procesa ili programa. Struktura podataka je poseban način pohranjivanja i organiziranja podataka u memoriji računala tako da se ti podaci mogu lako dohvatiti i učinkovito koristiti u budućnosti kada to bude potrebno. Podacima se može upravljati na različite načine, kao što je logički ili matematički model za određenu organizaciju podataka poznat kao struktura podataka.

Opseg određenog podatkovnog modela ovisi o dva čimbenika:

  1. Prvo, mora biti dovoljno učitan u strukturu da odražava definitivnu korelaciju podataka s objektom iz stvarnog svijeta.
  2. Drugo, formiranje bi trebalo biti tako jednostavno da se može prilagoditi za učinkovitu obradu podataka kad god je to potrebno.

Neki primjeri struktura podataka su nizovi, povezani popisi, stog, red čekanja, stabla, itd. Strukture podataka naširoko se koriste u gotovo svim aspektima računalnih znanosti, tj. dizajnu prevoditelja, operativnim sustavima, grafici, umjetnoj inteligenciji i mnogim drugim.

Strukture podataka glavni su dio mnogih algoritama informatike jer omogućuju programerima da učinkovito upravljaju podacima. Igra ključnu ulogu u poboljšanju performansi programa ili softvera, budući da je glavni cilj softvera pohraniti i dohvatiti korisničke podatke što je brže moguće.

poboljšana for loop java

Osnovna terminologija vezana uz strukture podataka

Strukture podataka su građevni blokovi bilo kojeg softvera ili programa. Odabir odgovarajuće strukture podataka za program iznimno je izazovan zadatak za programera.

Slijede neke temeljne terminologije koje se koriste kad god su uključene strukture podataka:

    Podaci:Podatke možemo definirati kao elementarnu vrijednost ili zbirku vrijednosti. Na primjer, ime i ID Zaposlenika su podaci koji se odnose na Zaposlenika.Podatkovne stavke:Pojedinačna jedinica vrijednosti poznata je kao podatkovna stavka.Stavke grupe:Podatkovne stavke koje imaju podređene podatkovne stavke poznate su kao grupne stavke. Na primjer, ime zaposlenika može imati ime, srednje ime i prezime.Osnovne stavke:Podatkovne stavke koje se ne mogu podijeliti u podstavke poznate su kao elementarne stavke. Na primjer, ID zaposlenika.Entitet i atribut:Klasu određenih objekata predstavlja entitet. Sastoji se od različitih atributa. Svaki atribut simbolizira specifično svojstvo tog entiteta. Na primjer,
Atributi iskaznica Ime Spol Naziv radnog mjesta
Vrijednosti 1234 Stacey M. Hill Žena Programer softvera

Entiteti sa sličnim atributima čine an Skup entiteta . Svaki atribut skupa entiteta ima raspon vrijednosti, skup svih mogućih vrijednosti koje se mogu dodijeliti određenom atributu.

Izraz 'informacija' ponekad se koristi za podatke s danim atributima smislenih ili obrađenih podataka.

    Polje:Jedna elementarna jedinica informacija koja simbolizira svojstvo entiteta poznata je kao polje.Snimiti:Zbirka različitih podatkovnih stavki poznata je kao Zapis. Na primjer, ako govorimo o entitetu zaposlenika, tada se njegovo ime, ID, adresa i naziv radnog mjesta mogu grupirati kako bi se formirao zapis za zaposlenika.Datoteka:Zbirka različitih zapisa jedne vrste entiteta poznata je kao datoteka. Na primjer, ako postoji 100 zaposlenika, bit će 25 zapisa u povezanoj datoteci koja sadrži podatke o svakom zaposleniku.

Razumijevanje potrebe za podatkovnim strukturama

Kako aplikacije postaju sve složenije, a količina podataka svakim danom raste, to može dovesti do problema s pretraživanjem podataka, brzinom obrade, obradom više zahtjeva i mnogim drugim. Strukture podataka podržavaju različite metode za organiziranje, upravljanje i učinkovito pohranjivanje podataka. Uz pomoć struktura podataka, možemo lako preći podatkovne stavke. Strukture podataka osiguravaju učinkovitost, mogućnost ponovne upotrebe i apstrakciju.

Zašto bismo trebali naučiti strukture podataka?

  1. Strukture podataka i algoritmi dva su ključna aspekta računalne znanosti.
  2. Strukture podataka omogućuju nam organiziranje i pohranjivanje podataka, dok nam algoritmi omogućuju smislenu obradu tih podataka.
  3. Učenje struktura podataka i algoritama pomoći će nam da postanemo bolji programeri.
  4. Moći ćemo napisati kod koji je učinkovitiji i pouzdaniji.
  5. Također ćemo moći brže i učinkovitije rješavati probleme.

Razumijevanje ciljeva struktura podataka

Strukture podataka zadovoljavaju dva komplementarna cilja:

    Ispravnost:Strukture podataka dizajnirane su za ispravan rad za sve vrste unosa na temelju domene od interesa. Drugim riječima, ispravnost čini primarni cilj strukture podataka, koji uvijek ovisi o problemima koje bi struktura podataka trebala riješiti.Učinkovitost:Strukture podataka također zahtijevaju da budu učinkovite. Trebao bi brzo obraditi podatke bez korištenja mnogih računalnih resursa poput memorijskog prostora. U stanju stvarnog vremena, učinkovitost podatkovne strukture ključni je faktor u određivanju uspjeha i neuspjeha procesa.

Razumijevanje nekih ključnih značajki struktura podataka

Neke od značajnih značajki struktura podataka su:

    Robusnost:Općenito, svi računalni programeri imaju za cilj proizvesti softver koji daje točan izlaz za svaki mogući ulaz, zajedno s učinkovitim izvršenjem na svim hardverskim platformama. Ova vrsta robusnog softvera mora upravljati valjanim i nevažećim unosima.Prilagodljivost:Izrada softverskih aplikacija poput web-preglednika, procesora teksta i internetske tražilice uključuje ogromne softverske sustave koji zahtijevaju ispravan i učinkovit rad ili izvođenje dugi niz godina. Štoviše, softver se razvija zbog novih tehnologija ili tržišnih uvjeta koji se neprestano mijenjaju.Ponovno korištenje:Značajke poput mogućnosti ponovne upotrebe i prilagodljivosti idu ruku pod ruku. Poznato je da programer treba mnogo resursa za izradu bilo kojeg softvera, što ga čini skupim poduzećem. Međutim, ako je softver razvijen na višekratnu upotrebu i prilagodljiv način, tada se može primijeniti u većini budućih aplikacija. Stoga je izvođenjem kvalitetnih struktura podataka moguće izgraditi softver koji se može ponovno koristiti, što se čini isplativim i štedi vrijeme.

Klasifikacija struktura podataka

Struktura podataka isporučuje strukturirani skup varijabli međusobno povezanih na različite načine. On čini osnovu alata za programiranje koji označava odnos između elemenata podataka i omogućuje programerima učinkovitu obradu podataka.

Strukture podataka možemo klasificirati u dvije kategorije:

  1. Primitivna struktura podataka
  2. Neprimitivna struktura podataka

Sljedeća slika prikazuje različite klasifikacije struktura podataka.

Uvod u strukture podataka

Slika 2: Klasifikacije struktura podataka

Primitivne strukture podataka

    Primitivne strukture podatakasu strukture podataka koje se sastoje od brojeva i znakova koji dolaze ugrađeni u programe.
  1. Ovim strukturama podataka može se manipulirati ili njima upravljati izravno pomoću instrukcija na razini stroja.
  2. Osnovni tipovi podataka poput Cijeli broj, float, znak , i Booleov potpadaju pod primitivne strukture podataka.
  3. Ove se vrste podataka također nazivaju Jednostavni tipovi podataka jer sadrže znakove koji se ne mogu dalje dijeliti

Neprimitivne strukture podataka

    Neprimitivne strukture podatakasu one strukture podataka izvedene iz primitivnih struktura podataka.
  1. Ovim strukturama podataka ne može se manipulirati niti njima upravljati izravno pomoću uputa na razini stroja.
  2. Fokus ovih struktura podataka je na formiranju skupa podatkovnih elemenata koji je ili homogena (isti tip podataka) ili heterogena (različiti tipovi podataka).
  3. Na temelju strukture i rasporeda podataka, te strukture podataka možemo podijeliti u dvije podkategorije -
    1. Linearne strukture podataka
    2. Nelinearne strukture podataka

Linearne strukture podataka

Podatkovna struktura koja čuva linearnu vezu između svojih podatkovnih elemenata poznata je kao linearna podatkovna struktura. Raspored podataka je linearan, pri čemu se svaki element sastoji od nasljednika i prethodnika osim prvog i posljednjeg podatkovnog elementa. Međutim, to nije nužno točno u slučaju memorije, budući da raspored možda nije sekvencijalan.

Na temelju raspodjele memorije, linearne strukture podataka dalje se klasificiraju u dvije vrste:

    Statičke strukture podataka:Strukture podataka fiksne veličine poznate su kao statičke strukture podataka. Memorija za te podatkovne strukture dodjeljuje se u vrijeme kompajlera, a korisnik ne može promijeniti njihovu veličinu nakon kompajliranja; međutim, podaci pohranjeni u njima mogu se mijenjati.
    The Niz je najbolji primjer statičke strukture podataka budući da imaju fiksnu veličinu, a njezini se podaci mogu kasnije mijenjati.Dinamičke strukture podataka:Podatkovne strukture koje imaju dinamičku veličinu poznate su kao dinamičke podatkovne strukture. Memorija ovih struktura podataka dodjeljuje se u vrijeme izvođenja, a njihova veličina varira tijekom vremena izvođenja koda. Štoviše, korisnik može promijeniti veličinu kao i podatkovne elemente pohranjene u tim podatkovnim strukturama tijekom izvođenja koda.
    Povezani popisi, nizovi , i repovi su uobičajeni primjeri dinamičkih struktura podataka

Vrste linearnih struktura podataka

Slijedi popis linearnih struktura podataka koje općenito koristimo:

1. Nizovi

An Niz je podatkovna struktura koja se koristi za prikupljanje više podatkovnih elemenata iste vrste podataka u jednu varijablu. Umjesto pohranjivanja višestrukih vrijednosti istih tipova podataka u zasebnim nazivima varijabli, mogli bismo ih pohraniti sve zajedno u jednu varijablu. Ova izjava ne znači da ćemo morati ujediniti sve vrijednosti iste vrste podataka u bilo kojem programu u jedan niz te vrste podataka. Ali često će biti trenutaka kada su neke specifične varijable istih tipova podataka povezane jedna s drugom na način prikladan za niz.

Niz je popis elemenata gdje svaki element ima jedinstveno mjesto na popisu. Podatkovni elementi niza dijele isto ime varijable; međutim, svaki nosi drugačiji indeksni broj koji se naziva indeks. Bilo kojem podatkovnom elementu s popisa možemo pristupiti uz pomoć njegovog položaja na popisu. Dakle, ključna značajka nizova koju treba razumjeti jest da su podaci pohranjeni na neprekidnim memorijskim lokacijama, što korisnicima omogućuje da prolaze kroz podatkovne elemente niza koristeći njihove odgovarajuće indekse.

testiranje softvera
Uvod u strukture podataka

Slika 3. Niz

Nizovi se mogu klasificirati u različite vrste:

    Jednodimenzionalni niz:Niz sa samo jednim redom podatkovnih elemenata poznat je kao jednodimenzionalni niz. Pohranjuje se na uzlazno mjesto pohrane.Dvodimenzionalni niz:Niz koji se sastoji od više redaka i stupaca podatkovnih elemenata naziva se dvodimenzionalni niz. Također je poznat kao Matrix.Višedimenzionalni niz:Višedimenzionalni niz možemo definirati kao niz nizova. Višedimenzionalni nizovi nisu ograničeni na dva indeksa ili dvije dimenzije jer mogu uključivati ​​onoliko indeksa koliko je potrebno.

Neke primjene polja:

  1. Možemo pohraniti popis elemenata podataka koji pripadaju istoj vrsti podataka.
  2. Niz djeluje kao pomoćna pohrana za druge strukture podataka.
  3. Niz također pomaže u pohrani podatkovnih elemenata binarnog stabla fiksnog broja.
  4. Niz također djeluje kao pohrana matrica.

2. Povezani popisi

A Povezani popis je još jedan primjer linearne podatkovne strukture koja se koristi za dinamičko pohranjivanje zbirke podatkovnih elemenata. Elementi podataka u ovoj strukturi podataka predstavljeni su čvorovima, povezanim pomoću veza ili pokazivača. Svaki čvor sadrži dva polja, informacijsko polje sastoji se od stvarnih podataka, a polje pokazivača sastoji se od adresa sljedećih čvorova na popisu. Pokazivač posljednjeg čvora povezane liste sastoji se od nultog pokazivača jer ne pokazuje ni na što. Za razliku od polja, korisnik može dinamički prilagoditi veličinu povezanog popisa prema zahtjevima.

Uvod u strukture podataka

Slika 4. Povezani popis

Povezani popisi mogu se klasificirati u različite vrste:

    Pojedinačno povezani popis:Pojedinačno povezani popis najčešći je tip povezanog popisa. Svaki čvor ima podatke i polje pokazivača koji sadrži adresu sljedećeg čvora.Dvostruko povezani popis:Dvostruko povezana lista sastoji se od informacijskog polja i dva polja pokazivača. Informacijsko polje sadrži podatke. Prvo polje pokazivača sadrži adresu prethodnog čvora, dok drugo polje pokazivača sadrži referencu na sljedeći čvor. Dakle, možemo ići u oba smjera (unazad kao i naprijed).Kružni povezani popis:Kružni povezani popis sličan je pojedinačno povezanom popisu. Jedina ključna razlika je u tome što posljednji čvor sadrži adresu prvog čvora, tvoreći kružnu petlju u kružnom povezanom popisu.

Neke primjene povezanih popisa:

  1. Povezani popisi pomažu nam implementirati nizove, redove, binarna stabla i grafikone unaprijed definirane veličine.
  2. Također možemo implementirati funkciju operativnog sustava za dinamičko upravljanje memorijom.
  3. Povezani popisi također omogućuju implementaciju polinoma za matematičke operacije.
  4. Možemo koristiti Circular Linked List za implementaciju operativnih sustava ili aplikacijskih funkcija koje Round Robin izvršavanje zadataka.
  5. Kružni povezani popis također je koristan u dijaprojekciji gdje korisnik zahtijeva da se vrati na prvi slajd nakon što se prikaže zadnji slajd.
  6. Dvostruko povezani popis koristi se za implementaciju gumba naprijed i natrag u pregledniku za kretanje naprijed i nazad na otvorenim stranicama web stranice.

3. Stogovi

A Stog je linearna struktura podataka koja slijedi LIFO (Last In, First Out) princip koji omogućuje operacije poput umetanja i brisanja s jednog kraja snopa, tj. s vrha. Stogovi se mogu implementirati uz pomoć kontinuirane memorije, polja, i nekontinuirane memorije, povezane liste. Primjeri hrpe iz stvarnog života su hrpe knjiga, špil karata, hrpe novca i još mnogo toga.

Uvod u strukture podataka

Slika 5. Primjer snopa iz stvarnog života

Gornja slika predstavlja primjer snopa iz stvarnog života gdje se operacije izvode samo s jednog kraja, poput umetanja i uklanjanja novih knjiga s vrha snopa. To podrazumijeva da se umetanje i brisanje u stogu može izvršiti samo s vrha stoga. Možemo pristupiti samo vrhovima hrpe u bilo kojem trenutku.

Primarne operacije u stogu su sljedeće:

sql poredak po datumu
    Gurnuti:Operacija umetanja novog elementa u stog naziva se operacija guranja.Pop:Operacija uklanjanja ili brisanja elemenata iz hrpe naziva se pop operacija.
Uvod u strukture podataka

Slika 6. Stog

Neke primjene nizova:

  1. Stog se koristi kao privremena struktura za pohranu za rekurzivne operacije.
  2. Stog se također koristi kao pomoćna struktura pohrane za pozive funkcija, ugniježđene operacije i odgođene/odgođene funkcije.
  3. Pozivima funkcija možemo upravljati pomoću skupova.
  4. Stogovi se također koriste za procjenu aritmetičkih izraza u različitim programskim jezicima.
  5. Skupovi su također korisni u pretvaranju infiks izraza u postfiks izraze.
  6. Stogovi nam omogućuju provjeru sintakse izraza u programskom okruženju.
  7. Možemo spojiti zagrade koristeći Stacks.
  8. Stogovi se mogu koristiti za preokretanje niza.
  9. Skupovi su korisni u rješavanju problema koji se temelje na praćenju unatrag.
  10. Možemo koristiti Stacks u dubinskom pretraživanju u obilasku grafa i stabla.
  11. Stogovi se također koriste u funkcijama operativnog sustava.
  12. Stogovi se također koriste u funkcijama UNDO i REDO u uređivanju.

4. Repovi

A Red je linearna struktura podataka slična stogu s određenim ograničenjima umetanja i brisanja elemenata. Umetanje elementa u red čekanja vrši se na jednom kraju, a uklanjanje na drugom ili suprotnom kraju. Stoga možemo zaključiti da struktura podataka Queue slijedi FIFO (First In, First Out) načelo za manipuliranje elementima podataka. Implementacija redova čekanja može se izvršiti korištenjem polja, povezanih popisa ili nizova. Neki primjeri redova iz stvarnog života su red na šalteru za prodaju karata, pokretne stepenice, autopraonica i mnogi drugi.

Uvod u strukture podataka

Slika 7. Primjer reda čekanja iz stvarnog života

Gornja slika stvarna je ilustracija šaltera za ulaznice za kino koji nam može pomoći da razumijemo red čekanja u kojem je kupac koji prvi dođe uvijek prvi uslužen. Kupac koji dođe zadnji nesumnjivo će biti posljednji uslužen. Oba kraja reda su otvorena i mogu izvršavati različite operacije. Drugi primjer je linija dvorana s hranom gdje se gost ubacuje sa stražnje strane dok se gost uklanja s prednje strane nakon pružanja usluge koju je tražio.

Sljedeće su primarne operacije reda:

powershell vs bash
    Stavi u red:Umetanje ili dodavanje nekih podatkovnih elemenata u red čekanja naziva se stavljanje u red. Umetanje elementa uvijek se vrši uz pomoć stražnjeg pokazivača.Isključi iz reda:Brisanje ili uklanjanje podatkovnih elemenata iz reda čekanja naziva se Dequeue. Brisanje elementa uvijek se vrši uz pomoć prednjeg pokazivača.
Uvod u strukture podataka

Slika 8. Red

Neke primjene redova čekanja:

  1. Redovi se općenito koriste u operaciji pretraživanja širine u Graphovima.
  2. Redovi se također koriste u operacijama raspoređivača poslova operativnih sustava, poput reda međuspremnika tipkovnice za pohranjivanje tipki koje pritisnu korisnici i reda čekanja međuspremnika ispisa za pohranu dokumenata koje ispisuje pisač.
  3. Redovi su odgovorni za CPU raspoređivanje, raspoređivanje poslova i raspoređivanje diska.
  4. Redovi prioriteta koriste se u operacijama preuzimanja datoteka u pregledniku.
  5. Redovi se također koriste za prijenos podataka između perifernih uređaja i CPU-a.
  6. Redovi su također odgovorni za rukovanje prekidima koje generiraju korisničke aplikacije za CPU.

Nelinearne strukture podataka

Nelinearne strukture podataka su strukture podataka u kojima elementi podataka nisu poredani redoslijedom. Ovdje umetanje i uklanjanje podataka nije izvedivo na linearan način. Postoji hijerarhijski odnos između pojedinačnih stavki podataka.

Vrste nelinearnih struktura podataka

Slijedi popis nelinearnih struktura podataka koje općenito koristimo:

1. Drveće

Stablo je nelinearna struktura podataka i hijerarhija koja sadrži skup čvorova tako da svaki čvor stabla pohranjuje vrijednost i popis referenci na druge čvorove ('djecu').

Struktura podataka stabla specijalizirana je metoda za organiziranje i prikupljanje podataka u računalu kako bi se učinkovitije koristili. Sadrži središnji čvor, strukturne čvorove i podčvorove povezane preko rubova. Također možemo reći da se struktura podataka stabla sastoji od povezanih korijena, grana i lišća.

Uvod u strukture podataka

Slika 9. Stablo

Drveće se može klasificirati u različite vrste:

    Binarno stablo:Struktura podataka stabla u kojoj svaki nadređeni čvor može imati najviše dva djeteta naziva se binarnim stablom.Stablo binarnog pretraživanja:Binarno stablo pretraživanja struktura je podataka stabla u kojoj možemo jednostavno održavati sortirani popis brojeva.AVL stablo:AVL stablo je samobalansirajuće binarno stablo pretraživanja gdje svaki čvor održava dodatne informacije poznate kao faktor ravnoteže čija je vrijednost -1, 0 ili +1.B-stablo:B-stablo je posebna vrsta samobalansirajućeg binarnog stabla pretraživanja gdje se svaki čvor sastoji od više ključeva i može imati više od dva djeteta.

Neke primjene drveća:

  1. Stabla implementiraju hijerarhijske strukture u računalnim sustavima poput direktorija i datotečnih sustava.
  2. Stabla se također koriste za implementaciju navigacijske strukture web stranice.
  3. Možemo generirati kod poput Huffmanova koda koristeći Drveće.
  4. Stabla su također korisna pri donošenju odluka u igračkim aplikacijama.
  5. Stabla su odgovorna za implementaciju prioritetnih redova za funkcije raspoređivanja OS-a temeljene na prioritetima.
  6. Stabla su također odgovorna za raščlanjivanje izraza i iskaza u prevoditeljima različitih programskih jezika.
  7. Stabla možemo koristiti za pohranu ključeva podataka za indeksiranje za sustav upravljanja bazom podataka (DBMS).
  8. Spanning Trees nam omogućuje usmjeravanje odluka u računalnim i komunikacijskim mrežama.
  9. Stabla se također koriste u algoritmu za pronalaženje puta implementiranom u aplikacije umjetne inteligencije (AI), robotike i videoigara.

2. Grafikoni

Graf je još jedan primjer nelinearne strukture podataka koja se sastoji od konačnog broja čvorova ili vrhova i bridova koji ih povezuju. Grafikoni se koriste za rješavanje problema stvarnog svijeta u kojem označavaju problemsko područje kao mrežu kao što su društvene mreže, mreže krugova i telefonske mreže. Na primjer, čvorovi ili vrhovi Grafa mogu predstavljati jednog korisnika u telefonskoj mreži, dok rubovi predstavljaju vezu između njih putem telefona.

Struktura podataka Grafa, G, smatra se matematičkom strukturom koja se sastoji od skupa vrhova, V i skupa rubova, E kao što je prikazano u nastavku:

G = (V,E)

Uvod u strukture podataka

Slika 10. Grafikon

Gornja slika predstavlja graf koji ima sedam vrhova A, B, C, D, E, F, G i deset rubova [A, B], [A, C], [B, C], [B, D], [B, E], [C, D], [D, E], [D, F], [E, F] i [E, G].

Ovisno o položaju vrhova i rubova, grafovi se mogu klasificirati u različite vrste:

piton kaminja
    Nulti grafikon:Graf s praznim skupom rubova naziva se nulti graf.Trivijalni graf:Graf koji ima samo jedan vrh naziva se trivijalni graf.Jednostavan grafikon:Graf koji nema niti samopetlje niti više rubova poznat je kao jednostavan graf.Višestruki grafikon:Za graf se kaže da je Multi ako se sastoji od više bridova, ali ne i vlastitih petlji.Pseudograf:Graf sa samopetljama i više rubova naziva se pseudo graf.Neusmjereni graf:Graf koji se sastoji od neusmjerenih rubova poznat je kao neusmjereni graf.Usmjereni grafikon:Graf koji se sastoji od usmjerenih bridova između vrhova poznat je kao usmjereni graf.Povezani grafikon:Graf s barem jednim putem između svakog para vrhova naziva se povezanim grafom.Isključeni grafikon:Graf u kojem ne postoji nikakva staza između barem jednog para vrhova naziva se nepovezanim grafom.Uobičajeni grafikon:Graf u kojem svi vrhovi imaju isti stupanj naziva se regularnim grafom.Potpuni grafikon:Graf u kojem svi vrhovi imaju brid između svakog para vrhova poznat je kao potpuni graf.Grafikon ciklusa:Za graf se kaže da je ciklus ako ima najmanje tri vrha i brida koji tvore ciklus.Ciklični grafikon:Za graf se kaže da je ciklički ako i samo ako postoji barem jedan ciklus.Aciklički grafikon:Graf koji ima nula ciklusa naziva se aciklički graf.Konačni graf:Graf s konačnim brojem vrhova i rubova poznat je kao konačni graf.Beskonačni graf:Graf s beskonačnim brojem vrhova i rubova poznat je kao beskonačni graf.Bipartitni graf:Graf u kojem se vrhovi mogu podijeliti u nezavisne skupove A i B, a svi vrhovi skupa A trebaju biti povezani samo s vrhovima prisutnim u skupu B s nekim bridovima naziva se bipartitni graf.Planarni grafikon:Za graf se kaže da je planar ako ga možemo nacrtati u jednoj ravnini s dva ruba koji se međusobno sijeku.Eulerov graf:Za graf se kaže da je Eulerov ako i samo ako su svi vrhovi parni stupnjevi.Hamiltonov graf:Povezani graf koji se sastoji od Hamiltonovog kruga poznat je kao Hamiltonov graf.

Neke primjene grafova:

  1. Grafikoni nam pomažu predstaviti rute i mreže u aplikacijama za prijevoz, putovanja i komunikaciju.
  2. Grafikoni se koriste za prikaz ruta u GPS-u.
  3. Grafikoni nam također pomažu predstaviti međusobne veze u društvenim mrežama i drugim mrežnim aplikacijama.
  4. Grafikoni se koriste u aplikacijama za mapiranje.
  5. Grafovi su odgovorni za prikaz korisničkih preferencija u aplikacijama za e-trgovinu.
  6. Grafikoni se također koriste u komunalnim mrežama kako bi se identificirali problemi koji se postavljaju pred lokalne ili općinske korporacije.
  7. Grafikoni također pomažu u upravljanju korištenjem i dostupnošću resursa u organizaciji.
  8. Grafovi se također koriste za izradu mapa veza dokumenata web stranica kako bi se prikazala povezanost između stranica putem hiperveza.
  9. Grafovi se također koriste u robotskim kretnjama i neuronskim mrežama.

Osnovne operacije podatkovnih struktura

U sljedećem odjeljku raspravljat ćemo o različitim vrstama operacija koje možemo izvesti za manipulaciju podacima u svakoj strukturi podataka:

    Prolazak:Prolazak kroz podatkovnu strukturu znači pristup svakom podatkovnom elementu točno jednom kako bi se njime moglo upravljati. Na primjer, prijelaz je potreban prilikom ispisivanja imena svih zaposlenika u odjelu.Traži:Pretraživanje je još jedna operacija strukture podataka koja znači pronaći lokaciju jednog ili više podatkovnih elemenata koji zadovoljavaju određena ograničenja. Takav element podataka može ali ne mora biti prisutan u danom skupu elemenata podataka. Na primjer, operacijom pretraživanja možemo pronaći imena svih zaposlenika koji imaju iskustvo duže od 5 godina.Umetanje:Umetanje znači umetanje ili dodavanje novih podatkovnih elemenata u zbirku. Na primjer, možemo koristiti operaciju umetanja za dodavanje pojedinosti o novom zaposleniku kojeg je tvrtka nedavno zaposlila.Brisanje:Brisanje znači ukloniti ili izbrisati određeni podatkovni element s danog popisa podatkovnih elemenata. Na primjer, operacijom brisanja možemo izbrisati ime zaposlenika koji je napustio posao.Sortiranje:Sortiranje znači poredati elemente podataka uzlaznim ili silaznim redoslijedom, ovisno o vrsti aplikacije. Na primjer, možemo upotrijebiti operaciju sortiranja kako bismo rasporedili imena zaposlenika u odjelu abecednim redom ili procijenili tri najbolja izvođača u mjesecu raspoređivanjem učinka zaposlenika silaznim redoslijedom i izdvajanjem pojedinosti tri najbolja.Sjediniti:Spajanje znači kombiniranje podatkovnih elemenata dva sortirana popisa kako bi se formirao jedan popis sortiranih podatkovnih elemenata.Stvoriti:Create je operacija koja se koristi za rezerviranje memorije za podatkovne elemente programa. Ovu operaciju možemo izvršiti pomoću iskaza deklaracije. Stvaranje strukture podataka može se odvijati tijekom sljedećeg:
    1. Vrijeme kompajliranja
    2. Vrijeme izvođenja
      Na primjer, malloc() funkcija se koristi u jeziku C za stvaranje strukture podataka.
    Izbor:Odabir znači odabir određenog podatka iz dostupnih podataka. Možemo odabrati bilo koji određeni podatak određivanjem uvjeta unutar petlje.Ažuriraj:Operacija ažuriranja omogućuje ažuriranje ili izmjenu podataka u strukturi podataka. Također možemo ažurirati bilo koje podatke specificiranjem nekih uvjeta unutar petlje, poput operacije odabira.Cijepanje:Operacija razdvajanja omogućuje nam da podijelimo podatke u različite poddijelove smanjujući ukupno vrijeme završetka procesa.

Razumijevanje apstraktnog tipa podataka

Prema Nacionalni institut za standarde i tehnologiju (NIST) , struktura podataka je raspored informacija, općenito u memoriji, radi bolje učinkovitosti algoritma. Strukture podataka uključuju povezane popise, hrpe, redove, stabla i rječnike. Oni također mogu biti teoretski entitet, poput imena i adrese osobe.

Iz gore navedene definicije možemo zaključiti da operacije u strukturi podataka uključuju:

  1. Visoka razina apstrakcija poput dodavanja ili brisanja stavke s popisa.
  2. Pretraživanje i sortiranje stavke na popisu.
  3. Pristup stavci najvišeg prioriteta na popisu.

Kad god struktura podataka obavlja takve operacije, to je poznato kao an Vrsta sažetka podataka (ADT) .

Možemo ga definirati kao skup podatkovnih elemenata zajedno s operacijama nad podacima. Izraz 'sažetak' odnosi se na činjenicu da se podaci i temeljne operacije definirane na njima proučavaju neovisno o njihovoj implementaciji. To uključuje što možemo učiniti s podacima, a ne kako to možemo učiniti.

Implementacija ADI-ja sadrži strukturu pohrane za pohranjivanje podatkovnih elemenata i algoritama za temeljni rad. Sve strukture podataka, kao što su niz, povezani popis, red čekanja, stog itd., primjeri su ADT-a.

Razumijevanje prednosti korištenja ADT-a

U stvarnom svijetu, programi se razvijaju kao posljedica novih ograničenja ili zahtjeva, tako da modificiranje programa općenito zahtijeva promjenu jedne ili više struktura podataka. Na primjer, pretpostavimo da želimo umetnuti novo polje u evidenciju zaposlenika kako bismo pratili više pojedinosti o svakom zaposleniku. U tom slučaju možemo poboljšati učinkovitost programa zamjenom niza povezanom strukturom. U takvoj situaciji, ponovno pisanje svake procedure koja koristi modificiranu strukturu nije prikladno. Stoga je bolja alternativa odvojiti strukturu podataka od informacija o njezinoj implementaciji. Ovo je načelo iza korištenja apstraktnih tipova podataka (ADT).

Neke primjene struktura podataka

Slijede neke primjene struktura podataka:

  1. Strukture podataka pomažu u organizaciji podataka u memoriji računala.
  2. Strukture podataka također pomažu u predstavljanju informacija u bazama podataka.
  3. Strukture podataka omogućuju implementaciju algoritama za pretraživanje podataka (na primjer, tražilica).
  4. Možemo koristiti strukture podataka za implementaciju algoritama za manipuliranje podacima (na primjer, programi za obradu teksta).
  5. Također možemo implementirati algoritme za analizu podataka pomoću struktura podataka (na primjer, rudari podataka).
  6. Strukture podataka podržavaju algoritme za generiranje podataka (Na primjer, generator slučajnih brojeva).
  7. Strukture podataka također podržavaju algoritme za komprimiranje i dekomprimiranje podataka (Na primjer, uslužni program za zip).
  8. Također možemo koristiti strukture podataka za implementaciju algoritama za šifriranje i dešifriranje podataka (na primjer, sigurnosni sustav).
  9. Uz pomoć Data Structures, možemo izgraditi softver koji može upravljati datotekama i direktorijima (Na primjer, upravitelj datoteka).
  10. Također možemo razviti softver koji može renderirati grafiku koristeći podatkovne strukture. (Na primjer, web preglednik ili softver za 3D renderiranje).

Osim ovih, kao što je ranije spomenuto, postoje mnoge druge primjene struktura podataka koje nam mogu pomoći u izradi bilo kojeg željenog softvera.