Nakon nizova, druga najpopularnija struktura podataka je Povezani popis. Povezani popis je linearna struktura podataka, napravljena od lanca čvorova u kojem svaki čvor sadrži vrijednost i pokazivač na sljedeći čvor u lancu. U ovom članku, pogledajmo kako implementirati povezani popis u C.
Što je povezani popis u C-u?
Povezani popis linearna je struktura podataka. Svaki povezani popis ima dva dijela, odjeljak podataka i odjeljak adrese koji sadrži adresu sljedećeg elementa na popisu, koji se naziva čvor.
Veličina povezanog popisa nije fiksna, a stavke podataka mogu se dodati na bilo koje mjesto na popisu. Mana je što da bismo došli do čvora, moramo prijeći sve od prvog čvora do čvora koji nam je potreban. Povezani popis je poput niza, ali za razliku od niza, on se ne pohranjuje uzastopno u memoriju.
Najpopularnije vrste povezanog popisa su:
Primjer povezanog popisa
Format: [podaci, adresa]
Glava -> [3,1000] -> [43,1001] -> [21,1002]
U primjeru je broj 43 prisutan na mjestu 1000, a adresa je na prethodnom čvoru. Tako je predstavljen povezani popis.
Osnovne funkcije povezanog popisa
Na povezanom popisu u C. može se implementirati više funkcija. Pokušajmo ih razumjeti uz pomoć primjera programa.Prvo stvorimo popis, prikažemo ga, umetnemo na bilo koje mjesto, izbrišemo mjesto. Sljedeći će vam kôd pokazati kako izvoditi radnje na popisu.
java system.exit (1)
#include #include void create () void display () void insert_begin () void insert_end () void insert_pos () void delete_begin () void delete_end () void delete_pos () struct node {int info struct node * next} struct node * start = NULL int main () {izbor int dok (1) {printf ('n MENU n') printf ('n 1.Create n') printf ('n 2.Prikaži n') printf ('n 3.Umetnite na početak n ') printf (' n 4.Umetni na kraj n ') printf (' n 5.Umetni na navedenom položaju n ') printf (' n 6.Izbriši s početka n ') printf (' n 7.Izbriši s kraja n ') printf (' n 8.Izbriši s navedenog položaja n ') printf (' n 9.Izlaz n ') printf (' n ----------------- --------------------- n ') printf (' Unesite svoj izbor: t ') prekidač scanf ('% d ', & choice) (izbor) {slučaj 1 : create () break case 2: display () break case 3: insert_begin () break case 4: insert_end () break case 5: insert_pos () break case 6: delete_begin () break case 7: delete_end () break case 8: delete_pos () break case 9: exit (0) break default: printf ('n Pogrešan izbor: n') break}} return 0} voi d create () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') exit (0) } printf ('nUnesite vrijednost podataka za čvor: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void display () {struct node * ptr if (start == NULL) {printf ('nList je prazan: n ') return} else {ptr = start printf (' nElementi popisa su: n ') while (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> next}}} void insert_begin () {struct node * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nUnesite vrijednost podataka za čvor: t ') scanf ('% d ', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {temp-> next = start start = temp }} void insert_end () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} str rintf ('nUnesite vrijednost podataka za čvor: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void insert_pos () {struct node * ptr, * temp int i, pos temp = (struct node *) malloc ( sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nUnesite položaj za umetanje novog čvora: t') scanf ('% d' , & pos) printf ('nUnesite vrijednost podataka čvora: t') scanf ('% d', & temp-> info) temp-> next = NULL if (pos == 0) {temp-> next = start start = temp} else {for (i = 0, ptr = startinext if (ptr == NULL) {printf ('nPosition not found: [Pažljivo postupajte] n') return}} temp-> next = ptr-> next ptr -> next = temp}} void delete_begin () {struct node * ptr if (ptr == NULL) {printf ('nList is Empty: n') return} else {ptr = start start = start-> next printf (' nIzbrisani element je:% dt ', ptr-> info) free (ptr)}} void delete_end () {struct node * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') exit (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ('nIzbrisani element je:% dt', ptr-> info) free (ptr)} else {ptr = start while (ptr- > sljedeći! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('nIzbrisani element je:% dt', ptr-> info) besplatno (ptr)}} void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nPopis je prazan: n') exit (0)} else {printf ('nUnesite položaj čvora koji treba izbrisati : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nIzbrisani element je:% dt ', ptr-> info) besplatno (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nIzbrisani element je: % dt ', ptr-> info) besplatno (ptr)}}}Prvi dio ovog koda je stvaranje strukture. Stvorena je povezana struktura popisa tako da može sadržavati podatke i adresu onako kako su nam potrebni. To je učinjeno kako bi kompajler dobio ideju o tome kakav treba biti čvor.
struct čvor {int info struct node * next}U strukturi imamo varijablu podataka koja se naziva info koja sadrži podatke i varijablu pokazivača koja usmjerava na adresu. Na povezanom popisu mogu se izvršiti razne operacije, poput:
- stvoriti()
- prikaz()
- insert_begin ()
- insert_end ()
- ] insert_pos ()
- delete_begin ()
- delete_end ()
- delete_pos ()
Te funkcije naziva glavna funkcija upravljana izbornikom. U glavnoj funkciji od korisnika uzimamo podatke na temelju toga koju operaciju korisnik želi učiniti u programu. Ulaz se zatim šalje na kućište sklopke i temelji se na korisničkom unosu.
Na temelju ponuđenog ulaza funkcija će biti pozvana. Dalje, imamo različite funkcije koje treba riješiti. Pogledajmo svaku od ovih funkcija.
Stvori funkciju
Prvo, postoji funkcija stvaranja za stvaranje povezanog popisa. Ovo je osnovni način stvaranja povezanog popisa. Omogućimo nam da pogledamo kod.
void create () {struct node * temp, * ptr printf ('nUnesite vrijednost podataka za čvor: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL ) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}}Izlaz
Prvo se kreiraju dva pokazivača tog tipa čvor, ptr i temp . Od korisnika preuzimamo vrijednost koja je potrebna za dodavanje na povezani popis i pohranjujemo je u info dio varijable temp i nulu dodijeljujemo temp sljedećeg koji je adresni dio. Postoji početni pokazivač koji drži početak popisa. Zatim provjeravamo početak popisa. Ako je početak popisa nula, tada dodijeljujemo temp početnom pokazivaču. Inače prelazimo na zadnju točku u koju su dodani podaci.
kako inicijalizirati klasu u pythonu
Za to dodijeljujemo ptr početnu vrijednost i prelazimo do ptr-> next = null . Zatim dodjeljujemo ptr-> sljedeći adresa temp. Na sličan način postoji i kod za umetanje na početku, umetanje na kraj i umetanje na određeno mjesto.
Funkcija prikaza
Evo koda za funkciju prikaza.
void display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n') return} else {ptr = start printf ('nElementi popisa su: n') while (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> sljedeći}}}Izlaz
U funkciji prikaza prvo provjeravamo je li popis prazan i vraćamo se ako je prazan. U sljedećem dijelu početnu vrijednost dodjeljujemo ptr. Zatim izvodimo petlju dok ptr nije nula i ispisujemo element podataka za svaki čvor, sve dok ptr ne postane nula, što specificira kraj popisa.
Izbriši funkciju
Evo isječka koda za brisanje čvora s povezanog popisa.
void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nPopis je prazan: n') exit (0)} else {printf ('nUnesite položaj čvor za brisanje: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nIzbrisani element je:% dt ', ptr-> info ) free (ptr)} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nThe izbrisani element je:% dt ', ptr-> info) besplatno (ptr)}}}Izlaz
U procesu brisanja prvo provjerava je li popis prazan, ako da, postoji. Ako nije prazan, traži od korisnika brisanje pozicije. Jednom kada korisnik uđe u poziciju, provjerava je li to prva pozicija, ako da, dodjeljuje ptr za pokretanje i pomicanje početnog pokazivača na sljedeće mjesto i briše ptr. Ako je položaj nije nula , zatim pokreće for petlju od 0 pa sve do pozicije koju je korisnik unio i pohranio u poz varijabilna. Postoji izjava if kojom se odlučuje ako upisano mjesto nije prisutno. Ako ptr jednak je nuli , tada nije prisutan.
Mi dodijeli ptr temp u petlju for, a ptr zatim prelazi na sljedeći dio. Nakon ovoga kada se pronađe položaj. Izrađujemo varijablu temp da zadrži vrijednost od ptr-> sljedeći preskačući tako ptr. Tada se ptr briše. Slično se može učiniti za brisanje prvog i posljednjeg elementa.
Popis dvostruko povezanih
Naziva se dvostruko povezanim popisom jer postoje dva pokazivači , jedna točka na sljedeći čvor i druge točke na prethodni čvor. Operacije izvedene u dvostruko povezanim sličnim su operacijama pojedinačno povezanog popisa. Evo koda za osnovne operacije.
#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode List typedef PtrToNode Position struct Node {int e Position previous Position next} void Insert (int x, List l, Position p) {Position TmpCell TmpCell = (struct Node *) malloc (sizeof (struct Node)) if (TmpCell == NULL) printf ('Memory out of spacen') else {TmpCell-> e = x TmpCell-> previous = p TmpCell-> next = p-> next p-> next = TmpCell}} void Delete (int x, List l) {Position p, p1, p2 p = Find (x, l) if (p! = NULL) {p1 = p -> prethodni p2 = p -> sljedeći p1 - > next = p -> next if (p2! = NULL) // ako čvor nije zadnji čvor p2 -> previous = p -> previous} else printf ('Element ne postoji !!! n')} void Prikaz (Popis l) {printf ('Element popisa su ::') Položaj p = l-> sljedeći dok (p! = NULL) {printf ('% d ->', p-> e) p = p- > sljedeći}} int main () {int x, pos, ch, i Popis l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> previous = NULL l-> next = NULL List p = l printf ('Dvostruko vezana provedba popisa L IST ADTnn ') do {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnnEnter the choice :: ') scanf ('% d ', & ch) switch (ch) {case 1: p = l printf (' Enter the element to be insert :: ') scanf ('% d', & x) printf ('Unesite položaj elementa ::') scanf ('% d', & pos) za (i = 1 isljedeća} Umetni (x, l, p) slučaj prekida 2: p = l printf ('Unesite element koji će se izbrisati ::') scanf ('% d', & x) Izbriši (x, p) slučaj prekida 3: Prikaz (l) prekid}} dok (pogl<4) } Izlaz
Kao što vidite, koncept operacija je prilično jednostavan. Dvostruko povezani popis ima iste operacije kao i pojedinačno povezani popis u programskom jeziku C. Jedina je razlika u tome što postoji još jedna varijabla adrese koja pomaže u boljem prelasku kroz popis na dvostruko povezanom popisu.
Nadam se da ste razumjeli kako izvoditi osnovne operacije na pojedinačno i dvostruko povezanom popisu u C.
Ako želite naučiti povezani popis na Javi, evo a .
Ako naiđete na neko pitanje, slobodno postavite sva svoja pitanja u odjeljku za komentare 'Povezani popis u C' i naš će tim rado odgovoriti.