Bagaimana untuk melaksanakan baris gilir berasaskan tatasusunan menggunakan bahasa C

Dalam pengaturcaraan, baris gilir ialah struktur data yang biasa digunakan Banyak bahasa pengaturcaraan mempunyai pelaksanaan baris gilir mereka sendiri, seperti Queue dalam Java dan deque dalam Python. Walau bagaimanapun, dalam bahasa C, tiada pelaksanaan baris gilir sedia dibuat. Oleh itu, dalam bahasa C, kita perlu melaksanakan baris gilir dengan mentakrifkan tatasusunan dan menggunakan penunjuk dan helah lain.

Dalam artikel ini, kami akan memperkenalkan cara melaksanakan baris gilir berasaskan tatasusunan menggunakan bahasa C.

1. Tentukan struktur baris gilir

Kami boleh melaksanakan operasi baris gilir dengan mentakrifkan struktur baris gilir. Struktur baris gilir ini termasuk maklumat seperti saiz baris gilir, penunjuk kepala dan ekor, data elemen, dsb.

#define MAX_SIZE 100

typedef struct queue {
    int size;
    int front;
    int rear;
    int data[MAX_SIZE];
} Queue;

Dalam kod di atas, kami mentakrifkan pemalar MAX_SIZE untuk mewakili saiz maksimum baris gilir dan mengisytiharkan baris gilir bernama Gilir dengan mentakrifkan struktur.

Antaranya, saiz mewakili saiz baris gilir, hadapan mewakili penunjuk kepala baris gilir, belakang mewakili penunjuk ekor baris gilir, dan data ialah tatasusunan untuk menyimpan elemen.

2. Operasi permulaan baris gilir

Dalam pelaksanaan baris gilir, operasi permulaan baris gilir perlu dilakukan terlebih dahulu untuk memastikan penggunaan baris gilir yang betul.

void init(Queue *q) {
    q->size = 0;
    q->front = 0;
    q->rear = -1;
}

Dalam kod di atas, kami mentakrifkan fungsi inisialisasi init, yang menerima penuding q yang menunjuk kepada struktur baris gilir sebagai parameter, dan menetapkan saiz baris gilir kepada 0 dan penuding kepala kepada 0 , penunjuk ekor ditetapkan kepada -1, menunjukkan bahawa baris gilir kosong.

3. Operasi bergilir elemen

Kendalian baris gilir adalah untuk meletakkan elemen di hujung baris gilir Pelaksanaan di sini adalah untuk menambah elemen pada penghujung data tatasusunan , dan kemas kini kedudukan penuding belakang.

int enqueue(Queue *q, int value) {
    if(q->size == MAX_SIZE) {
        return 0;
    }
    q->rear++;
    q->data[q->rear] = value;
    q->size++;
    return 1;
}

Dalam kod di atas, tentukan dahulu sama ada baris gilir penuh, kembalikan 0 untuk menunjukkan bahawa sisipan gagal Jika tidak, gerakkan penunjuk belakang ke belakang satu bit dan tetapkan nilai elemen kepada data. Ekor tatasusunan, dan saiz baris gilir meningkat sebanyak 1, dan akhirnya mengembalikan 1 untuk menunjukkan pemasukan yang berjaya.

4. Operasi dequeue elemen

Operasi dequeue pada baris gilir adalah untuk mengeluarkan elemen di kepala baris gilir dan mengemas kini kedudukan penuding hadapan. Idea yang dilaksanakan di sini adalah untuk mengembalikan nilai elemen pada kedudukan hadapan dalam data, menggerakkan penunjuk hadapan ke belakang sedikit, dan mengemas kini saiz baris gilir pada masa yang sama.

int dequeue(Queue *q) {
    if(q->size == 0) {
        return -1;
    }
    int value = q->data[q->front];
    q->front++;
    q->size--;
    return value;
}

Dalam kod di atas, tentukan dahulu sama ada baris gilir kosong, ia akan mengembalikan -1 untuk menunjukkan bahawa baris gilir kosong dalam data dan menetapkan penuding hadapan kepada Selepas bergerak satu bit, saiz baris gilir dikurangkan sebanyak 1, dan nilai elemen dikembalikan.

5. Uji pelaksanaan baris gilir

Sekarang kita telah melaksanakan pelbagai operasi baris gilir, mari kita uji:

#include <stdio.h>

int main() {
    Queue myQueue;
    init(&myQueue);
    enqueue(&myQueue, 1);
    enqueue(&myQueue, 2);
    enqueue(&myQueue, 3);
    printf("%d\n", dequeue(&myQueue));
    printf("%d\n", dequeue(&myQueue));
    printf("%d\n", dequeue(&myQueue));
    return 0;
}

Di Atas Dalam kod ujian, kami mula-mula menentukan baris gilir bernama myQueue dan memulakannya menggunakan fungsi init. Kemudian kami menggunakan fungsi enqueue untuk memasukkan nombor 1, 2, dan 3 ke dalam baris gilir, dan menggunakan fungsi dequeue untuk mengalih keluar elemen daripada baris gilir dan mengeluarkannya ke skrin.

Output di sini hendaklah:

1
2
3

6. Ringkasan

Dalam artikel ini, kami mempelajari cara menggunakan bahasa C untuk melaksanakan baris gilir A daripada tatasusunan. Dengan mentakrifkan struktur baris gilir dan fungsi operasi yang berkaitan, kami boleh menambah, memadam dan mengakses elemen dalam baris gilir dengan mudah. Walaupun menyusahkan untuk menggunakan penunjuk untuk melaksanakan baris gilir, kaedah ini boleh membantu kami memahami dengan lebih baik prinsip baris gilir dan sangat membantu dalam mempelajari struktur data dan algoritma.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan baris gilir berasaskan tatasusunan menggunakan bahasa C. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!