Matriisien jälkeen toiseksi suosituin tietorakenne on Linked List. Linkitetty luettelo on lineaarinen tietorakenne, joka koostuu solmuketjusta, jossa kukin solmu sisältää arvon ja osoittimen ketjun seuraavaan solmuun. Tässä artikkelissa katsotaan, miten linkitetty luettelo otetaan käyttöön C: ssä.
Mikä on linkitetty luettelo C: ssä?
Linkitetty luettelo on lineaarinen tietorakenne. Jokaisessa linkitetyssä luettelossa on kaksi osaa, dataosio ja osoiteosio, joka pitää sisällään luettelon seuraavan elementin, jota kutsutaan solmuksi, osoitteen.
Linkitetyn luettelon kokoa ei ole vahvistettu, ja tietoerät voidaan lisätä mihin tahansa luettelon sijaintiin. Haittana on, että päästäksesi solmuun, meidän on kuljettava aina ensimmäisestä solmusta vaadittavaan solmuun. Linkitetty luettelo on kuin matriisi, mutta toisin kuin matriisi, sitä ei tallenneta peräkkäin muistiin.
Linkitetyn luettelon suosituimmat tyypit ovat:
Esimerkki linkitetystä luettelosta
Muoto: [tiedot, osoite]
Pää -> [3,1000] -> [43,1001] -> [211002]
Esimerkissä numero 43 on paikassa 1000 ja osoite on edellisessä solmussa. Näin linkitetty luettelo on edustettuna.
Linkitetyn luettelon perustoiminnot
C: n linkitetyssä luettelossa voidaan käyttää useita toimintoja. Yritetään ymmärtää ne esimerkkiohjelman avulla.Ensinnäkin luomme luettelon, näytämme sen, lisätään mihin tahansa kohtaan, poistamme sijainnin. Seuraava koodi näyttää, kuinka luettelossa olevat toiminnot suoritetaan.
#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 solmu {int info struct solmu * seuraava} struct solmu * start = NULL int main () {int choice while (1) {printf ('n MENU n') printf ('n 1.Create n') printf ('n 2.Display n') printf ('n 3.Lisää alku n ') printf (' n 4.Lisää lopussa n ') printf (' n 5.Lisää määritettyyn kohtaan n ') printf (' n 6.Poistaa alusta n ') printf (' n 7.Poista lopusta n ') printf (' n 8.Poista määritetystä sijainnista n ') printf (' n 9.Poistu n ') printf (' n ----------------- --------------------- n ') printf (' Anna valintasi: t ') scanf ('% d ', & choice) -kytkin (valinta) {tapaus 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 Väärä valinta: 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 ('nSyötä solmun tietoarvo: 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}} mitätön näyttö () {struct solmu * ptr if (start == NULL) {printf ('nList on tyhjä: n ') return} else {ptr = aloita printf (' nLuettelon elementit ovat: n '), kun taas (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> seuraava}}} void insert_begin () {struct solmu * temp temp = (struct solmu *) malloc (sizeof (struct solmu)) if (temp == NULL) {printf ('ei muistia: n') return} printf ('nSyötä solmun data-arvo: t ') scanf ('% d ', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {temp-> next = start start = temp }} void insert_end () {struct solmu * temp, * ptr temp = (struct solmu *) malloc (sizeof (struct solmu)) if (temp == NULL) {printf ('n Muistitilaa ei ole: n') return} s rintf ('nSyötä solmun tietoarvo: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> seuraava! = NULL) {ptr = ptr-> seuraava} ptr-> seuraava = temp}} void insert_pos () {struct solmu * ptr, * temp int i, pos temp = (struct solmu *) malloc ( sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nSyötä uuden lisättävän solmun sijainti: t') scanf ('% d' , & pos) printf ('nSyötä solmun tietoarvo: 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 ('nSijaintia ei löydy: [Käsittele varoen] n') return}} temp-> seuraava = ptr-> seuraava ptr -> seuraava = temp}} void delete_begin () {struct solmu * ptr if (ptr == NULL) {printf ('nList on tyhjä: n') return} else {ptr = start start = start-> seuraava printf (' nPoistettu elementti on:% dt ', ptr-> info) vapaa (ptr)}} void delete_end () {struct solmu * temp, * ptr if (start == NULL) {printf (' nList on tyhjä: ') exit (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ('nPoistettu elementti on:% dt', ptr-> info) vapaa (ptr)} else {ptr = start while (ptr- > seuraava! = NULL) {temp = ptr ptr = ptr-> seuraava} temp-> seuraava = NULL printf ('nPoistettu elementti on:% dt', ptr-> info) vapaa (ptr)}} mitätön delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nLista on tyhjä: n') exit (0)} else {printf ('nSyötä poistettavan solmun sijainti : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nPoistettu elementti on:% dt ', ptr-> info) vapaa (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nPoistettu elementti on: % dt ', ptr-> info) ilmainen (ptr)}}}
Tämän koodin ensimmäinen osa on rakenteen luominen. Linkitetty luettelorakenne luodaan, jotta se voi pitää tiedot ja osoitteen tarpeen mukaan. Tämä tehdään antamaan kääntäjälle käsitys siitä, kuinka solmun pitäisi olla.
struct solmu {int info struct solmu * seuraava}
Rakenteessa meillä on tietomuuttuja nimeltä info tietojen pitämiseksi ja osoitinmuuttuja osoittamaan osoitetta. Linkitetyssä luettelossa voidaan suorittaa useita toimintoja, kuten:
- luoda()
- näyttö()
- lisää_alku ()
- insert_end ()
- ] insert_pos ()
- delete_begin ()
- delete_end ()
- delete_pos ()
Näitä toimintoja kutsutaan valikkopohjaisella päätoiminnolla. Päätoiminnossa otamme käyttäjän panoksen sen perusteella, minkä toiminnon käyttäjä haluaa tehdä ohjelmassa. Tulo lähetetään sitten kytkentäkoteloon ja käyttäjän syötteen perusteella.
Toiminnon kutsutaan sen mukaan, mikä syöttö syötetään. Seuraavaksi meillä on erilaisia toimintoja, jotka on ratkaistava. Tarkastellaan kaikkia näitä toimintoja.
Luo toiminto
Ensinnäkin linkitetyn luettelon luomiseen on luotava toiminto. Tämä on linkitetyn luettelon luomisen perustapa. Antaa meidän tarkastella koodia.
void create () {struct solmu * temp, * ptr printf ('nSyötä solmun data-arvo: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL ) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> seuraava} ptr-> seuraava = temp}}
Tuotos
Ensinnäkin luodaan kaksi tyypin osoitinta solmu, ptr ja lämpötila . Otamme käyttäjältä linkitettyyn luetteloon lisättävän arvon ja tallennamme sen temp-muuttujan info-osaan ja osoitamme seuraavaksi osoitteen osaksi nollaksi temp. On aloitusosoitin, joka pitää luettelon alkua. Sitten tarkistamme luettelon alun. Jos luettelon alku on tyhjä, osoitamme aloitusosoittimelle temp. Muussa tapauksessa siirrymme viimeiseen kohtaan, johon tiedot on lisätty.
Tätä varten osoitamme ptr: n alkuarvon ja traverse tillin ptr-> seuraava = nolla . Sitten annamme ptr-> seuraava lämpötilan osoite Vastaavalla tavalla on annettu koodi, joka lisätään alkuun, lisätään loppuun ja lisätään määritettyyn kohtaan.
Näytön toiminto
Tässä on näyttötoiminnon koodi.
void display () {struct solmu * ptr if (start == NULL) {printf ('nList on tyhjä: n') return} else {ptr = aloita printf ('nListaelementit ovat: n') kun taas (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> seuraava}}}
Tuotos
Näyttötoiminnossa tarkistamme ensin, onko luettelo tyhjä, ja palaamme, jos se on tyhjä. Seuraavassa osassa määritetään alkuarvo ptr: lle. Suoritamme sitten silmukan, kunnes ptr on tyhjä ja tulostamme jokaisen solmun tietoelementin, kunnes ptr on tyhjä, mikä määrittää luettelon lopun.
Poista toiminto
Tässä on koodinpätkä solmun poistamiseksi linkitetystä luettelosta.
void delete_pos () {int i, pos struct solmu * temp, * ptr if (start == NULL) {printf ('nLista on tyhjä: n') exit (0)} else {printf ('nSyötä poistettava solmu: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nPoistettu elementti on:% dt ', ptr-> info ) free (ptr)} else {ptr = aloita (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> seuraava printf ('nThe poistettu elementti on:% dt ', ptr-> info) ilmainen (ptr)}}}
Tuotos
Poistoprosessissa se tarkistaa ensin, onko luettelo tyhjä, jos kyllä, se on olemassa. Jos se ei ole tyhjä, se pyytää käyttäjää poistamaan sijainti. Kun käyttäjä syöttää sijainnin, se tarkistaa, onko se ensimmäinen sijainti, jos kyllä se antaa ptr aloittaa ja siirtää aloituskohdan seuraavaan paikkaan ja poistaa ptr. Jos sijainti ei ole nolla , sitten se suorittaa for for -silmukan 0: sta käyttäjän syöttämään ja tallennettuun kohtaan pos muuttuja. On if-lauseke, jolla päätetään, onko syötetty asema puuttuva. Jos ptr on yhtä suuri kuin nolla , niin sitä ei ole läsnä.
Me määritä ptr lämpötilaan for-silmukassa ja ptr siirtyy sitten seuraavaan osaan. Tämän jälkeen kun sijainti löytyy. Teemme temp-muuttujan pitämään arvon ptr-> seuraava siten ohittaa ptr. Sitten ptr poistetaan. Vastaavasti se voidaan tehdä ensimmäisen ja viimeisen elementin poistamiseksi.
Epäillysti linkitetty luettelo
Sitä kutsutaan kaksinkertaisesti linkitetyksi luetteloksi, koska niitä on kaksi viitteitä , yksi piste seuraavaan solmuun ja muut pisteet edelliseen solmuun. Kaksinkertaisesti linkitetyt toiminnot ovat samanlaisia kuin yksittäisesti linkitetyn luettelon. Tässä on perustoimintojen koodi.
muunna päivämäärämerkkijono päivämääräksi
#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode List typedef PtrToNode Position struct Node {int e Position edellinen sijainti seuraava} void Insert (int x, List l, Position p) {Position TmpCell TmpCell = (struct Node *) malloc (sizeof (struct Node)) if (TmpCell == NULL) printf ('Muisti loppu tilasta') muu {TmpCell-> e = x TmpCell-> edellinen = p TmpCell-> seuraava = p-> seuraava p-> seuraava = TmpCell}} void Poista (int x, Lista l) {Sijainti p, p1, p2 p = Etsi (x, l) if (p! = NULL) {p1 = p -> edellinen p2 = p -> seuraava p1 - > seuraava = p -> seuraava jos (p2! = NULL) // jos solmu ei ole viimeinen solmu p2 -> edellinen = p -> edellinen} else printf ('Elementtiä ei ole olemassa !!! n')} mitätön Näyttö (Lista l) {printf ('Luettelon elementit ovat ::') Sijoita p = l-> seuraava, kun (p! = NULL) {printf ('% d ->', p-> e) p = p- > seuraava}} int main () {int x, pos, ch, i Lista l, l1 l = (struct Solmu *) malloc (sizeof (struct Node)) l-> edellinen = NULL l-> seuraava = NULL List p = l printf ('KAKSIN LINKITTY LUETTELO L IST ADTnn ') do {printf (' nn1. CREATEn 2. POISTA 3. NÄYTTÖ 4. QUITnnSyötä valinta :: ') scanf ('% d ', & ch) -kytkin (ch) {tapaus 1: p = l printf (' Syötä lisättävä elementti :: ') scanf ('% d', & x) printf ('Syötä elementin sijainti ::') scanf ('% d', & pos) kohteelle (i = 1 iseuraava} Lisää (x, l, p) taukotapa 2: p = l printf ('Syötä poistettava elementti ::') scanf ('% d', & x) Poista (x, p) tauko 3: Näyttö (l) tauko}} (ch<4) }
Tuotos
Joten, kuten näette, toiminnan käsite on melko yksinkertainen. Kaksinkertaisesti linkitetyllä luettelolla on samat toiminnot kuin yksinkertaisella linkitetyllä luettelolla C-ohjelmointikielellä. Ainoa ero on, että on olemassa toinen osoitemuuttuja, joka auttaa kulkemaan luetteloa paremmin kaksinkertaisesti linkitetyssä luettelossa.
Toivon, että olet ymmärtänyt, kuinka suoritat perustoiminnot C: n yksitellen ja kaksoislinkitetyllä luettelolla.
Jos haluat oppia linkitetyn luettelon Java-ohjelmassa, tässä on a .
Jos kohtaat kysymyksiä, kysy rohkeasti 'Linkitetyn luettelon C: ssä' kommenttiosassa, ja tiimimme vastaa mielellään.