Datorzinātnē rinda ir lineāra datu struktūra, kurā komponenti tiek ievietoti vienā galā un noņemti no otra gala saskaņā ar FIFO (first-in, first-out) principu. Šo datu struktūru var izmantot darbību secības kontrolei vai datu glabāšanai. C ir datorvaloda ar rindas iespējām, kas iekļautas masīvu vai saistīto sarakstu veidā.
Raksturlielumi:
- Rinda ir lineāras datu struktūras veids, ko var izveidot, izmantojot masīvu vai saistītu sarakstu.
- Elementi tiek pārvietoti uz rindas aizmuguri, kamēr tie tiek noņemti no priekšpuses.
- Rinda (elementa pievienošana aizmugurē) un dequeue (elementa noņemšana no priekšpuses) ir divas rindas darbības.
- Ja elementi tiek pievienoti un noņemti bieži, rindu var izveidot kā apļveida rindu, lai novērstu atmiņas izšķērdēšanu.
Izmantojot masīvu:
Lai ieviestu rindu programmā C, izmantojot masīvu, vispirms definējiet rindas maksimālo lielumu un deklarējiet šāda izmēra masīvu. Priekšējie un aizmugurējie veselie skaitļi tika attiecīgi iestatīti uz 1. Priekšējais mainīgais apzīmē rindas priekšējo elementu, bet aizmugurējais mainīgais apzīmē aizmugures elementu.
virknes pārvēršana par veselu skaitli Java
Pirms jaunā elementa nosūtīšanas uz rindas galīgo pozīciju, mums jāpalielina aizmugures mainīgais par 1. Rinda tagad ir pilna un nevar pievienot citus papildu elementus, kad aizmugures pozīcija sasniedz rindas maksimālo ietilpību. Mēs pievienojam elementu rindas priekšpusē un palielinām priekšējo mainīgo tikai par vienu, lai noņemtu elementu no rindas. Ja priekšējā un aizmugurējā pozīcija ir vienāda un vairs nevar dzēst nevienu komponentu, mēs varam teikt, ka rinda ir tukša.
Tālāk ir parādīts C valodā rakstītas rindas gadījums, kurā tiek izmantots masīvs:
C programmēšanas valoda:
#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; } Koda izvade būs:
Izvade:
java sadalīta virkne ar atdalītāju
10 20 30 Queue is empty-1
Paskaidrojums:
- Pirmkārt, mēs rindā ievietojam trīs elementus 10, 20 un 30.
- Pēc tam mēs noņemam rindu un izdrukājam rindas priekšējo elementu, kas ir 10.
- Pēc tam mēs noņemam rindu un vēlreiz izdrukājam rindas priekšējo elementu, kas ir 20.
- Pēc tam mēs noņemam rindu un vēlreiz izdrukājam rindas priekšējo elementu, kas ir 30.
- Visbeidzot, mēs izveidojam rindu no tukšas rindas, kas izvada “Rinda ir tukša” un atgriež -1.
Saistītā saraksta izmantošana:
Vēl viena alternatīva pieeja rindas izveidošanai programmēšanas valodā C ir saistīta saraksta izmantošana. Katrs rindas mezgls, izmantojot šo metodi, tiek izteikts ar mezglu, kurā ir elementa vērtība un rādītājs uz nākamo rindas mezglu. Lai sekotu līdzi rindas pirmajam un pēdējam mezglam, tiek izmantoti attiecīgi priekšējie un aizmugurējie rādītāji.
Mēs izveidojam jaunu mezglu ar elementa vērtību un iestatām tā nākamo rādītāju uz NULL, lai rindai pievienotu elementu. Jaunajam mezglam mēs iestatām priekšējo un aizmugurējo rādītāju, ja rinda ir tukša. Ja nē, mēs atjauninām aizmugurējo rādītāju un iestatām vecā aizmugurējā mezgla nākamo rādītāju, kas norāda uz jauno mezglu.
Dzēšot mezglu no rindas, vispirms tiek dzēsts iepriekšējais mezgls, pēc tam priekšējais rādītājs tiek atjaunināts uz nākamo rindas mezglu un visbeidzot tiek atbrīvota atmiņa, kuru aizņēma noņemtais mezgls. Ja pēc noņemšanas priekšējais rādītājs ir NULL, rinda ir tukša.
Šeit ir piemērs rindai, kas ieviesta C valodā, izmantojot saistīto sarakstu:
masīvs.kārtot java
C programmēšanas valoda:
#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; } Koda izvade būs:
Izvade:
java atjaunināšana
10 20 30 Queue is empty-1
Paskaidrojums:
- Pirmkārt, mēs rindā ievietojam trīs elementus 10, 20 un 30.
- Pēc tam mēs noņemam rindu un izdrukājam rindas priekšējo elementu, kas ir 10.
- Pēc tam mēs noņemam rindu un vēlreiz izdrukājam rindas priekšējo elementu, kas ir 20.
- Pēc tam mēs noņemam rindu un vēlreiz izdrukājam rindas priekšējo elementu, kas ir 30.
- Visbeidzot, mēs cenšamies izņemt rindu no tukšās rindas, kas izdrukā ziņojumu 'Rinda ir tukša' un atgriež -1.
Priekšrocības:
- Rindas ir īpaši noderīgas, lai ieviestu algoritmus, kas prasa elementu apstrādei precīzā secībā, piemēram, meklēšanu pēc platuma un uzdevumu plānošanu.
- Tā kā rindas operācijām ir O(1) laika sarežģītība, tās var izpildīt ātri pat milzīgās rindās.
- Rindas ir īpaši elastīgas, jo tās var vienkārši ieviest, izmantojot masīvu vai saistīto sarakstu.
Trūkumi:
- Atšķirībā no kaudzes rindu nevar izveidot ar vienu rādītāju, padarot rindas ieviešanu nedaudz vairāk iesaistītu.
- Ja rinda tiek veidota kā masīvs, tā drīz var aizpildīties, ja tiek pievienots pārāk daudz elementu, izraisot veiktspējas problēmas vai, iespējams, avāriju.
- Ja rindas ieviešanai tiek izmantots saistīts saraksts, katra mezgla atmiņas apjoms var būt ievērojams, īpaši maziem elementiem.
Secinājums:
Lietojumprogrammas, kurās tiek izmantotas rindas, kas ir ļoti svarīga datu struktūra, ietver operētājsistēmas, tīklus un spēles, lai nosauktu tikai dažas. Tie ir ideāli piemēroti algoritmiem, kuriem elementi jāapstrādā noteiktā secībā, jo tos ir vienkārši izveidot, izmantojot masīvu vai saistīto sarakstu. Tomēr rindām ir trūkumi, kas jāņem vērā, izvēloties datu struktūru konkrētai lietojumprogrammai, piemēram, atmiņas patēriņš un ieviešanas sarežģītība.