[Powered by Google Translate] [Coda] [Chris Gerber, Harvard University] Questo è CS50, CS50.TV] Una struttura di dati utili per memorizzare un insieme ordinato di elementi è una coda. Viene usato quando gli elementi devono essere rimossi nello stesso ordine in cui sono stati aggiunti. Questo concetto è denominato FIFO, che è un acronimo per primo entrato, primo uscito. Per aiutare a visualizzare questo, può essere utile picture una fila alla cassa in un negozio. Dato che le persone arrivano, aspettano sul retro della linea. Il cassiere poi prende giri servire i clienti nella parte anteriore, che poi uscire una riga alla volta. In informatica, si fa riferimento alla parte anteriore della coda come il capo e indietro come la coda. Un esempio di quando si potrebbe utilizzare questo in un'applicazione è una lista di attesa per le iscrizioni di classe. Come posti saranno disponibili nella classe, la persona a capo della lista d'attesa è prevista la possibilità di iscriversi nella classe. 

Una coda può essere costruita usando qualsiasi raccolta che memorizza dati in ordine, ad esempio una matrice o un elenco collegato. Insieme con la collezione per memorizzare gli elementi nella coda, occorre anche un metodo per aggiungere elementi alla fine della coda, che si chiama enqueuing, e un altro per rimuovere un elemento dalla testa della coda, che si chiama l'accodamento. Spesso è utile inserire un altro metodo per restituire la lunghezza corrente della coda nonché un metodo per verificare se la coda è vuota. Diamo un'occhiata a come si potrebbe implementare una coda di interi in C, utilizzando una matrice per la raccolta di elementi. Per prima cosa, creiamo una struttura chiamata coda per tenere le nostre variabili. Useremo una matrice a dimensione fissa indice 0 di interi per memorizzare gli elementi. Si comprenderà anche una testa variabile chiamata che memorizza l'indice dell'elemento che è attualmente alla testa della coda. Una terza variabile, detta lunghezza, saranno utilizzati per tenere traccia del numero di elementi nella matrice. In alternativa, si potrebbe considerare l'utilizzo di una coda variabile chiamata per puntare l'elemento di campo nella matrice. Prima di scrivere codice più, proviamo il nostro design. Cominciamo con una matrice vuota di lunghezza 0, con la testa a 0. Ora cerchiamo di accodare 4 valori - 6, 2, 3, e 1. La lunghezza sarà ora 4, e la testa rimane a 0. 

Che cosa succede se annullare l'accodamento di un valore? Sarà possibile ridurre la lunghezza di 3, impostare la testa a 1, e restituire il valore 6. Tale codice potrebbe essere simile. Qui abbiamo la funzione dequeue, che prende un puntatore alla coda - q - e un puntatore all'elemento, che è un tipo int. Per prima cosa controllare la lunghezza della coda per assicurarsi che sia maggiore di 0, per garantire che vi sia un elemento da dequeued. Poi guardiamo nella matrice elementi, a capo di posizione, e impostare il valore dell'elemento di essere il valore in quella posizione. Allora cambiamo la testa di essere l'indice del prossimo % Della capacità. Abbiamo quindi ridurre la lunghezza della coda di 1. Infine, si ritorna true per indicare che il dequeue avuto successo. Se si dequeue nuovo, la lunghezza sarà 2, la testa diventerà anche 2, e il valore restituito sarà 2. 

Cosa succede se accodare un altro valore, ad esempio un 7? Come eravamo alla fine della coda, dovremo avvolgere e memorizzare il valore 0 elemento della matrice. Matematicamente, questo può essere rappresentato aggiungendo la lunghezza all'indice della testa ed eseguire un modulo utilizzando la capacità coda. Qui che è 2 +2, che è 4% 4, che è 0. Traducendo questa idea di codice che abbiamo questa funzione. Qui vediamo la funzione enqueue, che prende un puntatore alla coda - q - e prende l'elemento da accodato, che è un numero intero. Abbiamo poi controllare per assicurarsi che la capacità della coda è ancora maggiore della lunghezza corrente della coda. Successivo, conservare le elemento dell'array elementi in corrispondenza dell'indice che è determinata dalla testa +% lunghezza della capacità della coda. Abbiamo quindi aumentare la lunghezza della coda di 1, e poi tornare true per indicare che la funzione di accodamento ha avuto successo. 

In aggiunta alle due funzioni che abbiamo detto, ci sono due funzioni aggiuntive. La prima è la funzione IsEmpty, che prende un puntatore alla coda e verifica che la lunghezza è 0. La seconda è la funzione di lunghezza, che tiene anche un puntatore alla coda e restituisce la lunghezza attuale della struttura. Questa breve panoramica ha dimostrato una possibile implementazione di una coda. Uno dei limiti di questa implementazione è che la coda ha una dimensione fissa massima. Se si tenta di aggiungere più elementi rispetto alla coda può contenere, potremmo avere bisogno di ignorare la richiesta e rilasciare l'elemento, o si può scegliere di restituire un certo tipo di errore. Utilizzando una lista collegata anziché una matrice renderebbe più facile dimensione dinamicamente coda. Tuttavia, dal momento che non hanno accesso diretto agli elementi di una lista concatenata, se non tenere traccia della coda, avremmo dovuto acquisire l'intero elenco legato arrivare alla fine ogni volta. Si potrebbe anche considerare l'utilizzo di una matrice di un altro tipo di dati, quali strutture, per creare le code di elementi più complessi. Ripensando al nostro esempio di una lista d'attesa di classe, queste strutture potrebbe rappresentare i singoli studenti. 

Il mio nome è Chris Gerber, e questo è CS50. [CS50.TV] E ritorni - >> ancora una volta. E ritorna true per indicare che - la coda ha avuto successo. -% Della capacità della coda - E 'intenzione di essere divertente in edit. [Risate]