Coada circulară în C: Cum se implementează?
Publicat: 2020-10-23Datele sunt aranjate într-o coadă circulară într-un model circular unde ultimul element este conectat la primul element. Spre deosebire de coada liniară în care sarcinile sunt executate pe FIFO (First In First Out), ordinea circulară a cozii de execuție a sarcinilor se poate modifica. Operațiile de inserare și ștergere pot fi efectuate în orice poziție.
Coada circulară este mai eficientă decât coada liniară. În reprezentarea grafică a unei cozi circulare, puteți observa că pozițiile față și spate sunt conectate, făcându-l un cerc în care operațiunile sunt întotdeauna executate pe baza FIFO. Fiecare element nou este adăugat la capătul din spate și șters din partea din față. O coadă circulară are o utilizare mai bună și are o complexitate de timp de O(1).
Sursă
Cuprins
Aplicații ale unei cozi circulare
- Programarea CPU: Cozile circulare folosesc spațiile de memorie goale care se găsesc în cozile liniare.
- Sistemul de circulație: În sistemul de circulație, cu ajutorul cozilor circulare, semafoarele sunt acționate la intervalul de timp stabilit.
- Managementul memoriei: sistemele de operare mențin frecvent o serie de procese care sunt pregătite pentru a fi executate sau care așteaptă să apară un anumit eveniment.
Aflați: Programul C pentru sortarea cu bule: sortarea cu bule în C
Exemplu de cod cu explicație
Linia 1: // (1) Preprocesoare
Linia 2: // Setați limita cozii la 5 elemente
Linia 3: #include<stdio.h>
Linia 4: #define LIM 5
Linia 5: // (2) Declarații de tip de date din coadă
Linia 6: // datele dețin date; delPos, poziție din care să ștergeți; lungime, nu. de
Linia 7: // elemente prezente în prezent în coadă
Linia 8: typedef struct queue {
Linia 9: int date[LIM], delPos, lungime;
Linia 10: } Q;
Rândul 11: // (3) Declarații globale
Linia 12: // Funcții și variabilă globală q a tipului de coadă struct
Linia 13: Q q;
Linia 14: void ui_Q_Ops(), insertQel(), deleteQel(), displayQels(), initQ();
Linia 15: // (4) Apelează funcția UI după inițializare
Linia 16: int main()
Linia 17: {
Linia 18: initQ();
Linia 19: ui_Q_Ops();
Linia 20: returnează 0;
Linia 21: }
Linia 22: // (5) Inițializați coada
Linia 23: void initQ()
Linia 24: {
Linia 25: q.lungime = 0;
Linia 26: q.delPos = 0;
Linia 27: }
Linia 28: // (6) Menu Driven Loop apelează funcțiile corecte
Linia 29: void ui_Q_Ops()
Linia 30: {
Linia 31: int alegere=0;
Linia 32: introducere caracter[16];
Linia 33: while(choice!=4){
Linia 34: printf(” \n ———————-\n “);
Linia 35: printf(” 1. Inserați în coadă \n “);
Linia 36: printf(” 2. Șterge din coadă \n “);
Linia 37: printf(” 3. Afișează elementele din coadă \n “);
Linia 38: printf(” 4. Ieșire din program \n “);
Linia 39: printf(” Introduceți alegerea: “);
Linia 40: if (fgets(input, 15, stdin) != NULL){
Linia 41: dacă (sscanf(input, „%d”, &choice) == 1){
Linia 42: comutare(alegere){
Linia 43: cazul 1: insertQel();
Linia 44: pauză;
Linia 45: cazul 2: deleteQel();
Linia 46: pauză;
Linia 47: cazul 3: displayQels();
Linia 48: pauză;
Rândul 49: cazul 4: retur;
Linia 50: implicit: printf(„Alegere nevalidă\n”);
Linia 51: continua;
Linia 52: }
Linia 53: } altfel
Linia 54: printf(” Alegere nevalidă \n “);
Linia 55: }
Linia 56: }
Linia 57: }
Linia 58: // (7) Inserați în coadă
Linia 59: // Dacă lungimea este aceeași cu Limita MAX, coada este plină. În caz contrar, inserați
Linia 60: // realizat circular cu lungimea sumă și modul delPos prin MAX Limit
Linia 61: // și lungimea de increment
Linia 62: void insertQel()
Linia 63: {
Rândul 64: int el, inspos;
Linia 65: introducere caracter[16];
Linia 66: dacă (lungime q == LIM){
Linia 67: printf(” Coada este plină \n “);
Linia 68: retur;
Linia 69: }
Linia 70: inspos = (q.delPos + q.lungime) % LIM;
Linia 71: printf(” Introduceți elementul de inserat: “);
Linia 72: if (fgets(input, 15, stdin) != NULL){
Linia 73: if (sscanf(input, „%d”, &el)){
Linia 74: q.data[inspos] = el;
Linia 75: q.lungime++;
Linia 76: } altfel
Linia 77: printf(” Intrare nevalidă \n “);
Linia 78: }
Linia 79: }
Linia 80: // (8) Ștergeți din coadă
Linia 81: // Dacă Lungimea este 0, coada este goală, în caz contrar ștergeți la delPos
Linia 82: // și reduceți lungimea
Linia 83: void deleteQel()
Linia 84: {
Linia 85: dacă (lungime q == 0){
Linia 86: printf(” Coada este goală \n “);
Linia 87: } else {
Linia 88: printf(”Element șters %d \n “, q.data[q.delPos]);
Linia 89: q.delPos = (q.delPos + 1) % LIM;
Linia 90: q.lungime–;
Linia 91: }
Linia 92: }
Linia 93: // (9) Afișează elementele Cozii
Linia 94: // Afișează într-o manieră circulară rulând o buclă începând cu delPos
Linia 95: // și adăugarea iteratorului și a modulului prin Limita maximă
Linia 96: void displayQels()
Linia 97: {
Linia 98: int i;
Linia 99: dacă (lungime q == 0){
Linia 100: printf(” Coada este goală \n “);
Linia 101: } else {
Linia 102: printf(” Elementele cozii sunt: “);
Linia 103: for(i = 0; i < q.length; i++){
Linia 104: printf(“%d “, q.data[(q.delPos+i)%LIM]);
Linia 105: }
Linia 106: printf(” \n “);
Linia 107: }
Linia 108: }
Linia 109:
Ieșiri:
Operații pe o coadă circulară
1. insertQel() – Inserarea unui element în coada circulară
Într-o coadă circulară, funcția enQueue() este utilizată pentru a insera un element în coada circulară. Într-o coadă circulară, noua caracteristică este întotdeauna introdusă în poziția din spate. Funcția enQueue() ia o valoare întreagă ca parametru și o inserează în coada circulară. Următorii pași sunt implementați pentru a insera un element în coada circulară:
Pasul 1 – Verificați dacă lungimea este aceeași cu Limita MAX. Dacă este adevărat, înseamnă că coada este PLINĂ. Dacă este PLIN, atunci afișați „Coada este plină” și opriți funcția.
Pasul 2 – Dacă NU este COMPLET, atunci introduceți valoarea care este obținută circular cu lungimea sumă și modulul delPos cu Limita MAX și lungimea incrementală
2. deleteQel() – Ștergerea unui element din coada circulară
Într-o coadă circulară, deQueue() este o funcție folosită pentru a șterge un element din coada circulară. Într-o coadă circulară, elementul este întotdeauna șters din poziția frontală. Funcția deQueue() nu ia nicio valoare ca parametru. Următorii pași sunt implementați pentru a șterge un element din coada circulară...
Pasul 1 - Verificați dacă coada este GOLĂ. (față == -1 și& spate == -1)
Pasul 2 – Dacă este GOL, atunci afișați „Coada este goală” și opriți funcția.
Pasul 3 – Dacă NU este GOL, atunci afișați elementele șterse în funcție de poziții. După ce fiecare element este adăugat, treceți la următoarea limită de coadă a modului de poziție.
3. displayQels() – Afișează elementele de coadă care sunt prezente în coada circulară. Următorii pași sunt implementați pentru a afișa elementele unei cozi circulare:
Pasul 1 – Verificați dacă coada este GOLĂ.
Pasul 2 – Dacă lungimea este 0, este GOL, apoi afișați „Coada este goală” și terminați funcția.
Pasul 3 – Dacă NU este GOL, atunci definiți o variabilă întreagă „i”.
Pasul 4 – Setați i la 0.
Pasul 5 – Din nou, afișați elementele în funcție de poziție și măriți valoarea cu unu (i++). Repetați același lucru până când „i <q.length” devine FALS.
Coada circulară poate fi implementată și folosind lista legată. Următorii sunt algoritmii:
- Algoritm pentru coadă:
if (FRONT == NULL) // Inserarea într-o coadă goală
FRONT = REAR = newNode
sfârşitul dacă
altfel
REAR -> next = newNode // Se introduce după ultimul element
REAR = nouNod
sfarsitul altceva
SPATE -> următorul = FRONT
Terminați coada
- Algoritm pentru scoatere la coadă:
if(FRONT == NULL) // Condiție pentru underflow
Tipăriți „Coadă sub depășire”
sfârşit Decodarea
sfârşitul dacă
else if(FRONT == REAR) // Coada conține un singur nod
temp = FRONT -> date
liber (temp)
FRONT = FRONT -> următor
SPATE -> următorul = FRONT
sfârşitul dacă
else if (FRONT == N – 1) // Dacă FRONT este ultimul nod
front = 0 // Faceți FRONT ca prim nod
sfârşitul dacă
sfârşit Decodarea
Citește și: Python Vs C: Comparație completă una lângă alta
Concluzie
Structurile de date și algoritmii sunt de mare importanță și nu doar în programarea C, ci și în alte limbaje. Valoarea sa este fără precedent, iar pentru subiecte de o asemenea importanță, este mai bine să investești în cursuri concepute și îndrumate de experți, care vor oferi un plus de valoare excelentă portofoliului tău. upGrad oferă o gamă largă de cursuri puternice, care nu numai că îți îmbunătățesc abilitățile, ci construiesc piloni puternici de bază.
Este proiectat de renumitul IIIT-B, unde nu numai că oferă conținut de calitate premium, ci și te fac parte dintr-o rețea puternică în care te vei conecta cu oameni care evoluează pe aceeași cale de carieră, precum și cu experții din industrie care rezolvă îndoielile și te sprijină de fiecare dată.
Te-ar ajuta să le cunoști mentalitatea și procesul de gândire. Iar unul dintre lucrurile unice pe care le obțineți la upGrad este că puteți opta pentru opțiunile EMI și puteți folosi ușor buzunarele.
Sperăm că veți avea o oportunitate excelentă de învățare în executarea acestor proiecte C. Dacă sunteți interesat să aflați mai multe și aveți nevoie de mentorat de la experții din industrie, consultați Diploma PG de la upGrad și IIIT Banglore în Dezvoltare Software Full-Stack .