Po nizih je druga najbolj priljubljena struktura podatkov Povezani seznam. Povezani seznam je linearna podatkovna struktura, sestavljena iz verige vozlišč, v kateri vsako vozlišče vsebuje vrednost in kazalec na naslednje vozlišče v verigi. V tem članku poglejmo, kako v C. izvesti povezani seznam
Kaj je povezani seznam v jeziku C?
Povezani seznam je linearna podatkovna struktura. Vsak povezan seznam ima dva dela, odsek s podatki in odsek z naslovi, ki vsebuje naslov naslednjega elementa na seznamu, ki se imenuje vozlišče.
Velikost povezanega seznama ni določena in podatkovne postavke je mogoče dodati kjer koli na seznamu. Pomanjkljivost je, da moramo do vozlišča priti do prvega vozlišča do vozlišča, ki ga potrebujemo. Povezani seznam je kot matrika, vendar za razliko od matrike ni zaporedno shranjen v pomnilniku.
Najbolj priljubljene vrste povezanega seznama so:
Primer povezanega seznama
Oblika: [podatki, naslov]
Glava -> [3,1000] -> [43,1001] -> [21,1002]
V primeru je številka 43 prisotna na lokaciji 1000, naslov pa v prejšnjem vozlišču. Tako je predstavljen povezan seznam.
Osnovne funkcije povezanega seznama
Na povezanem seznamu v C. je mogoče implementirati več funkcij. Poskusimo jih razumeti s pomočjo primera programa.Najprej ustvarimo seznam, ga prikažemo, vstavimo na katero koli lokacijo, izbrišemo lokacijo. Naslednja koda vam bo pokazala, kako izvajati operacije na seznamu.
kako sestavim java program -
#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 vozlišče {int info struct vozlišče * naslednje} struct vozlišče * začetek = NULL int main () {int izbira while (1) {printf ('n MENU n') printf ('n 1.Ustvari n') printf ('n 2.Prikaži n') printf ('n 3.Vstavi v začetek n ') printf (' n 4.Vstavi na koncu n ') printf (' n 5.Vstavi na določen položaj n ') printf (' n 6.Izbriši z začetka n ') printf (' n 7.Izbriši s konca n ') printf (' n 8.Izbriši iz določenega položaja n ') printf (' n 9.Izhod n ') printf (' n ----------------- --------------------- n ') printf (' Vnesite svojo izbiro: t ') stikalo scanf ('% d '& & choice) (izbira) {primer 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 () primer preloma 9: izhod (0) odmor privzeto: printf ('n Napačna izbira: 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 ('nVnesite podatkovno vrednost vozlišča: 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 prazen: n ') return} else {ptr = start printf (' nElementi seznama so: n '), medtem ko (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 ('nVnesite vrednost podatkov za vozlišče: 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 ('nVnesite podatkovno vrednost vozlišča: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> naslednji! = NULL) {ptr = ptr-> naslednji} ptr-> naslednji = 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 ('nVnesite položaj novega vozlišča, ki ga želite vstaviti: t') scanf ('% d' , & pos) printf ('nVnesite podatkovno vrednost vozlišča: 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: [Pazljivo ravnajte] 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- > naslednji! = NULL) {temp = ptr ptr = ptr-> naslednji} temp-> naslednji = NULL printf ('nIzbrisani element je:% dt', ptr-> info) brezplačno (ptr)}} void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} else {printf ('nVnesite položaj vozlišča, ki ga želite izbrisati : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nIzbrisani element je:% dt ', ptr-> info) brezplačno (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) brezplačno (ptr)}}}Prvi del te kode je ustvarjanje strukture. Ustvari se povezana struktura seznama, da bo lahko hranila podatke in naslov, kot jih potrebujemo. To se naredi, da prevajalnik dobi idejo, kako naj bo vozlišče.
vozlišče struct {int info struct vozlišče * naslednje}V strukturi imamo podatkovno spremenljivko, imenovano info, ki vsebuje podatke, in spremenljivko kazalca, ki kaže na naslov. Na povezanem seznamu lahko izvedete različne operacije, na primer:
- ustvari ()
- zaslon ()
- insert_begin ()
- insert_end ()
- ] insert_pos ()
- delete_begin ()
- delete_end ()
- delete_pos ()
Te funkcije pokliče glavna funkcija, ki jo poganja meni. V glavni funkciji od uporabnika vzamemo podatke glede na to, kakšno operacijo želi uporabnik opraviti v programu. Nato se vhod pošlje v ohišje stikala in temelji na vnosu uporabnika.
Na podlagi tega, kateri vhod je na voljo, bo funkcija poklicana. Nato imamo različne funkcije, ki jih je treba rešiti. Oglejmo si vsako od teh funkcij.
Ustvari funkcijo
Najprej obstaja funkcija za ustvarjanje povezanega seznama. To je osnovni način ustvarjanja povezanega seznama. Omogočamo si ogled kode.
void create () {struct node * temp, * ptr printf ('nVnesite podatkovno vrednost za vozlišče: 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}}Izhod
je a ima javo
Najprej sta ustvarjena dva kazalca tipa vozlišče, ptr in temp . Uporabnik vzamemo vrednost, ki jo potrebujemo za dodajanje na povezani seznam, od uporabnika in jo shranimo v informacijski del spremenljivke temp in temp naslednjega, ki je naslovni del, dodelimo za nulo. Na začetku seznama je začetni kazalec. Nato preverimo začetek seznama. Če je začetek seznama ničen, potem začetnemu kazalcu dodelimo temp. V nasprotnem primeru preidemo na zadnjo točko, kjer smo dodali podatke.
Za to dodelimo ptr začetno vrednost in prehodimo do ptr-> naslednji = null . Nato dodelimo ptr-> naslednji naslov temp. Na podoben način obstaja koda za vstavljanje na začetku, vstavljanje na koncu in vstavljanje na določenem mestu.
Funkcija prikaza
Tu je koda za funkcijo prikaza.
void display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n') return} else {ptr = start printf ('nElementi seznama so: n') while (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> naslednji}}}Izhod
V funkciji prikaza najprej preverimo, ali je seznam prazen, in vrnemo, če je prazen. V naslednjem delu damo začetno vrednost ptr. Nato zaženemo zanko, dokler ptr ni nič in natisnemo podatkovni element za vsako vozlišče, dokler ptr ni nič, kar določa konec seznama.
Izbriši funkcijo
Tu je delček kode za brisanje vozlišča s povezanega seznama.
void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} else {printf ('nVnesite položaj vozlišče, ki ga je treba izbrisati: 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 = 0next if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nThe izbrisani element je:% dt ', ptr-> info) brezplačno (ptr)}}}Izhod
V postopku brisanja najprej preveri, ali je seznam prazen, če da, obstaja. Če ni prazen, od uporabnika zahteva, da se položaj izbriše. Ko uporabnik vstopi v položaj, preveri, ali je prvo mesto, če da, dodeli ptr za zagon in premakne začetni kazalec na naslednje mesto in izbriše ptr. Če je položaj ni nič , nato zažene zanko for od 0 pa vse do položaja, ki ga vnese uporabnik in shrani v poz spremenljivka. Obstaja izjava if, s katero lahko odločite, ali vnesena pozicija ni prisotna. Če ptr je enako nič , potem ni prisoten.
Mi dodeli ptr temp v zanki for in ptr se nato premakne na naslednji del. Po tem, ko je položaj najden. Spremenljivko temp naredimo tako, da zadrži vrednost ptr-> naslednji s tem preskoči ptr. Nato se ptr izbriše. Podobno lahko to storimo za brisanje prvega in zadnjega elementa.
Dvojno povezan seznam
Imenuje se dvojno povezan seznam, ker obstajata dva kazalci , ena točka do naslednjega vozlišča in druge točke do prejšnjega vozlišča. Operacije, ki se izvajajo v dvojno povezanih napravah, so podobne kot pri posamično povezanem seznamu. Tu je 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 -> prejšnji p2 = p -> naslednji p1 - > next = p -> next if (p2! = NULL) // če vozlišče ni zadnje vozlišče p2 -> previous = p -> previous} else printf ('Element ne obstaja !!! n')} void Prikaži (Seznam l) {printf ('Element seznama so ::') Položaj p = l-> naslednji, medtem ko (p! = NULL) {printf ('% d ->', p-> e) p = p- > naslednji}} int main () {int x, pos, ch, i Seznam l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> previous = NULL l-> next = NULL List p = l printf ('IZVAJANJE LISTA DVOJNO POVEZANEGA SEZNAMA IST ADTnn ') do {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnnEnter the choice :: ') scanf ('% d ', & ch) stikalo (ch) {case 1: p = l printf (' Enter the element to be insert :: ') scanf ('% d', & x) printf ('Vnesite položaj elementa ::') scanf ('% d', & pos) za (i = 1 inaprej} Vstavi (x, l, p) primer preloma 2: p = l printf ('Vnesite element, ki ga želite izbrisati ::') scanf ('% d', & x) Izbriši (x, p) primer preloma 3: Prikaz (l) odmor}} medtem ko (pogl<4) } Izhod
pl sql vadnica s primeri
Kot vidite, je koncept operacij precej preprost. Dvojno povezan seznam ima enake operacije kot posamezno povezan seznam v programskem jeziku C. Edina razlika je v tem, da obstaja še ena spremenljivka naslova, ki pomaga pri boljšem prečkanju seznama v dvojno povezanem seznamu.
Upam, da ste razumeli, kako izvajati osnovne operacije na posamezno in dvojno povezanem seznamu v C.
Če se želite naučiti povezanega seznama v Javi, je tukaj .
Če naletite na kakršna koli vprašanja, vas prosimo, da vsa vprašanja postavite v oddelku za komentarje »Povezani seznam v C« in naša ekipa vam bo z veseljem odgovorila.