Tietojenkäsittelytieteessä jono on lineaarinen tietorakenne, jossa komponentit laitetaan toiseen päähän ja poistetaan toisesta päästä 'first-in, first-out' (FIFO) -periaatteen mukaisesti. Tätä tietorakennetta voidaan käyttää toimintosarjan ohjaamiseen tai tietojen tallentamiseen. C on tietokonekieli, joka sisältää jono-ominaisuudet taulukoiden tai linkitettyjen luetteloiden muodossa.
Ominaisuudet:
- Jono on lineaarisen tietorakenteen tyyppi, joka voidaan muodostaa taulukon tai linkitetyn luettelon avulla.
- Elementit siirretään jonon takaosaan samalla, kun ne poistetaan etupuolelta.
- Enqueue (lisää elementti taakse) ja dequeue (poista elementti edestä) ovat kaksi jonotoimintoa.
- Kun elementtejä lisätään ja poistetaan usein, jono voidaan rakentaa pyöreäksi jonoksi muistin tuhlaamisen estämiseksi.
Arrayn käyttäminen:
Jos haluat toteuttaa jonon C:ssä taulukon avulla, määritä ensin jonon enimmäiskoko ja määritä sen kokoinen taulukko. Etu- ja takakokonaisluvut asetettiin vastaavasti arvoon 1. Etumuuttuja edustaa jonon etuelementtiä ja takamuuttuja takaelementtiä.
Ennen kuin työnnämme uuden elementin jonon lopulliseen paikkaan, meidän on suurennettava takamuuttujaa yhdellä. Jono on nyt täynnä eikä muita lisäelementtejä voi lisätä, kun taka-asema saavuttaa jonon maksimikapasiteetin. Lisäämme elementin jonon etuosaan ja suurennamme etumuuttujaa yhdellä vain elementin poistamiseksi jonosta. Jos etu- ja taka-asemat ovat samat eikä komponentteja voi enää poistaa, voidaan sanoa, että jono on tyhjä.
10 potenssiin 6
Alla on esimerkki C-kielellä kirjoitetusta jonosta, joka käyttää taulukkoa:
C-ohjelmointikieli:
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Koodin tulos on:
mikä on aakkosnumero
Lähtö:
10 20 30 Queue is empty-1
Selitys:
- Ensin jonetaan kolme elementtiä 10, 20 ja 30 jonoon.
- Sitten poistamme jonosta ja tulostamme jonon etuosan, joka on 10.
- Seuraavaksi poistamme jonosta ja tulostamme uudelleen jonon etuosan, joka on 20.
- Sitten poistamme jonosta ja tulostamme uudelleen jonon etuosan, joka on 30.
- Lopuksi teemme jonon tyhjästä jonosta, joka tulostaa 'Jono on tyhjä' ja palauttaa -1.
Linkitetyn luettelon käyttäminen:
Toinen vaihtoehtoinen tapa jonon muodostamiseen ohjelmointikielellä C on linkitetyn listan käyttö. Jokainen jonon solmu ilmaistaan tällä menetelmällä solmulla, joka sisältää elementin arvon ja osoittimen jonon seuraavaan solmuun. Jonon ensimmäisen ja viimeisen solmun kirjaamiseksi käytetään etu- ja takaosoittimia.
Luomme uuden solmun elementin arvolla ja asetamme sen seuraavan osoittimen arvoon NULL lisätäksesi elementin jonoon. Uuteen solmuun asetamme etu- ja takaosoittimet, jos jono on tyhjä. Jos ei, päivitämme takaosoittimen ja asetamme vanhan takasolmun seuraavan osoittimen osoittamaan uuteen solmuun.
Kun solmu poistetaan jonosta, edellinen solmu poistetaan ensin, sitten etuosoitin päivitetään jonon seuraavaan solmuun ja lopuksi vapautetaan poistetun solmun käyttämä muisti. Jos etuosoitin on NULL poistamisen jälkeen, jono on tyhjä.
muuta merkkijono int
Tässä on esimerkki jonosta, joka on toteutettu C:ssä linkitetyn luettelon avulla:
C-ohjelmointikieli:
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Koodin tulos on:
Lähtö:
arp-a-komento
10 20 30 Queue is empty-1
Selitys:
- Ensin jonetaan kolme elementtiä 10, 20 ja 30 jonoon.
- Sitten poistamme jonosta ja tulostamme jonon etuosan, joka on 10.
- Seuraavaksi poistamme jonosta ja tulostamme uudelleen jonon etuosan, joka on 20.
- Sitten poistamme jonosta ja tulostamme uudelleen jonon etuosan, joka on 30.
- Lopuksi yritämme purkaa jonosta tyhjästä jonosta, joka tulostaa viestin 'Jono on tyhjä' ja palauttaa -1.
Edut:
- Jonot ovat erityisen hyödyllisiä sellaisten algoritmien toteuttamisessa, jotka edellyttävät elementtien käsittelyä tarkassa järjestyksessä, kuten leveysensimmäinen haku ja tehtävien ajoitus.
- Koska jonooperaatioilla on O(1)-aikainen monimutkaisuus, ne voidaan suorittaa nopeasti jopa valtavissa jonoissa.
- Jonot ovat erityisen joustavia, koska ne voidaan yksinkertaisesti toteuttaa taulukon tai linkitetyn luettelon avulla.
Haitat:
- Jonoa, toisin kuin pinoa, ei voida rakentaa yhdellä osoittimella, mikä tekee jonon toteutuksesta hieman enemmän mukana.
- Jos jono on muodostettu taulukoksi, se saattaa pian täyttyä, jos siihen lisätään liian monta elementtiä, mikä voi johtaa suorituskykyongelmiin tai mahdollisesti kaatumiseen.
- Käytettäessä linkitettyä listaa jonon toteuttamiseen, kunkin solmun muistin lisäys voi olla merkittävä, erityisesti pienille elementeille.
Johtopäätös:
Sovelluksia, jotka käyttävät jonoja, ratkaisevaa tietorakennetta, ovat käyttöjärjestelmät, verkot ja pelit, vain muutamia mainitakseni. Ne ovat ihanteellisia algoritmeille, joiden on käsiteltävä elementtejä tietyssä järjestyksessä, koska ne on helppo luoda käyttämällä taulukkoa tai linkitettyä luetteloa. Jonoissa on kuitenkin haittoja, jotka on otettava huomioon valittaessa tietorakennetta tietylle sovellukselle, kuten muistin kulutus ja toteutuksen monimutkaisuus.