Come dovrei implementare una coda di priorità sicura in C?

Voglio dire "non succederà". Tuttavia, ciò non sarebbe molto utile, e forse non del tutto accurato, neanche.

Prima di tutto, la "sicurezza" è piuttosto vaga, ma penso che possiamo scomporla:

• Sii sicuro per la memoria. Non assegnare buffer troppo piccoli, non deviare i puntatori wild, non sovraccaricare i buffer, ecc.

• Avere una buona complessità asintotica. Avere semplicemente una serie di voci non ordinate richiederebbe O (n) per estrarre l'elemento con la massima priorità. Prendi in considerazione l'utilizzo di un heap binario invece.

• Non perdi memoria. Ogni chiamata a malloc dovrebbe avere una chiamata corrispondente a free .

In secondo luogo, impara abbastanza C per lavorare con le strutture dati. Proverò a fornire una rapida panoramica:

struct

Definisci i tipi di dati composti utilizzando la parola chiave struct . Esempio:

struct Foo
{
    int n[10];
};

sono come le classi in C ++ o Java, ma non puoi incorporare i metodi direttamente in esse.

Quando usi il tipo, devi dire struct Foo (C ++ ti lascia fuori struct , ma non C). Per evitare questo inconveniente, considera l'utilizzo di typedef :

typedef struct Foo Foo;

Puntatori

Considera un nodo ad albero binario:

struct Node
{
    int value;
    struct Node *left;
    struct Node *right;
};

Qui left e% co_de puntano ad altre strutture Nodo. Se dovessimo estrarre gli asterischi:

struct Node
{
    int value;
    struct Node left;
    struct Node right;
};

Quindi significherebbe che right e left esistono proprio qui, in questo oggetto. Ciò richiederebbe un oggetto infinitamente grande! Il compilatore rifiuterà questo codice.

Un puntatore può essere pensato come:

• Un riferimento a un'altra struttura dati

• Un numero che rappresenta una posizione in memoria. Pensa alla memoria come a una gigantesca serie di byte. Il sistema operativo decide dove mettere le cose. Un puntatore è un indice in quell'array.

Allocazione

Quindi, come chiediamo al sistema operativo di riservare spazio per un oggetto? Chiamiamo malloc :

struct Node *node = malloc(sizeof(struct Node));

right riserva il numero richiesto di byte di memoria e restituisce un puntatore che ci dice dove sono quei byte. Non inizializza la memoria su nulla, quindi attualmente contiene dati inutili.

malloc calcola la dimensione di un tipo di dati (in fase di compilazione).

Possiamo anche allocare cose direttamente nello stack:

struct Node node;

Come nel caso di sizeof , malloc conterrà spazzatura. Qui, node è un valore. Possiamo trasformarlo in un puntatore usando l'operatore di riferimento di C node :

struct Node *node_ptr = &node;

I vantaggi dell'allocazione sullo stack sono:

• È molto più veloce di &

• È liberato automaticamente

Lo svantaggio è che malloc non è valido al di fuori dell'ambito corrente. Pertanto, non possiamo restituire i puntatori alle strutture allocate nello stack.

Accesso alle strutture

L'operatore di accesso alla struttura in C è node_ptr :

struct Node node;
node.value = 42;

Per accedere a un valore di struttura dietro un puntatore, possiamo combinare gli operatori . (puntatore di dereferenza) e * (membro di struttura):

(*node).value = 42; /* . has higher operator precedence */

Ancora meglio, usa l'operatore di abbreviazione . :

node->value = 42;

Esempio semplice

Ecco un programma di esempio che definisce un nodo ad albero binario e le operazioni di base su di esso.

/* Needed for printf and perror */
#include <stdio.h>

/* Needed for malloc, free, and exit */
#include <stdlib.h>

typedef struct Node Node;

struct Node
{
    int value;
    Node *left;
    Node *right;
};

Node *node_new(int value, Node *left, Node *right)
{
    Node *node = malloc(sizeof(Node));

    if (node == NULL) {
        perror("node_new");
        exit(EXIT_FAILURE);
    }

    node->value = value;
    node->left = left;
    node->right = right;
    return node;
}

void node_delete(Node *node)
{
    if (node != NULL) {
        node_delete(node->left);
        node_delete(node->right);
        free(node);
    }
}

void node_dump(Node *node)
{
    if (node != NULL) {
        node_dump(node->left);
        printf("%d\n", node->value);
        node_dump(node->right);
    }
}

int main(void)
{
    Node *node =
        node_new(4,
            node_new(2,
                node_new(1, NULL, NULL),
                node_new(3, NULL, NULL)
            ),
            node_new(6,
                node_new(5, NULL, NULL),
                node_new(7, NULL, NULL)
            )
        );

    node_dump(node);
    node_delete(node);
    return 0;
}

Spero che questo aiuti.

Penso che sarebbe meglio imparare questo (puntatori e altri) più velocemente facendo piuttosto che cercando di imparare prima.

qui ci sono alcuni suggerimenti:

1. Una coda può essere facilmente implementata sotto forma di elenco collegato. Quindi, se hai un'idea generale di come vengono creati gli elenchi collegati (singoli o doppi), mantenendo un puntatore per successivo (e precedente) e aggiornali in modo appropriato, sei più o meno fatto.

2. Per quanto riguarda la priorità, in sostanza devi mantenere un punteggio (come diciamo int ) su ciascun nodo, quindi ogni volta che inserisci il nodo devi attraversare fino a quando la priorità del punto è inferiore alla priorità del nuovo nodo entrante. Scambia opportunamente i successivi (precedenti) puntatori del nodo.

3. A proposito di sicurezza, questo non è molto chiaro, ma generalmente, per scrivere codice sicuro, è necessario assicurarsi di non portare buffer finiti (puntatori) senza lunghezze note e non scrivere dati in nessun buffer che possa potenzialmente scrivere in aree di memoria sconosciute. Qui è necessaria una grande elaborazione oltre lo scopo qui.

Suggerimenti:

1. Non dimenticare di malloc ogni nodo prima di insertino e free dopo la rimozione (o l'utilizzo).

2. Crea una funzione di debug - validate_all_nodes() e attraversa l'intero elenco per vedere che tutti i nodi sono corretti. Utilizzare questa funzione ogni volta che si desidera eseguirne il debug.

Se l'insieme di priorità è piccolo e la memoria virtuale è abbondante, è un approccio ragionevole utilizzare una serie di strutture di coda, indicizzate per priorità, in cui il consumatore itera l'array dalla coda ad alta priorità alla ricerca di una coda diversa da zero contare. Se gli elementi in coda sono puntatori, una struttura di coda basata su un buffer circolare "classico" con indici in / out dovrebbe andare bene. Se la coda di priorità è quella di produttore / consumatore, allora hai bisogno della solita coppia di semafori e di una sezione critica, (o qualche altro meccanismo di segnalazione / protezione appropriato).

I vantaggi di questo appoach è che non è necessario iterare un elenco, (o navigare un albero), elementi in coda su push / pop e inoltre, in generale, non c'è malloc / free / realloc per push / pop, (cioè nessuna contesa su memory-manager)

Il problema dell'uso della memoria può essere mitigato da qualche codice extra per lo spazio del buffer della coda di malloc / realloc / free se necessario, ma questo ovviamente richiede più codice all'interno del blocco delle code, (specialmente se si scopre che una coda deve essere riallocato più grande), che ha un impatto sulla contesa: (