1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Coda]

2
00:00:02,000 --> 00:00:05,000
[Chris Gerber, Harvard University]

3
00:00:05,000 --> 00:00:07,000
Questo è CS50, CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Una struttura di dati utili per memorizzare un insieme ordinato di elementi è una coda.

5
00:00:11,000 --> 00:00:14,000
Viene usato quando gli elementi devono essere rimossi

6
00:00:14,000 --> 00:00:16,000
nello stesso ordine in cui sono stati aggiunti.

7
00:00:16,000 --> 00:00:20,000
Questo concetto è denominato FIFO, che è un acronimo per primo entrato, primo uscito.

8
00:00:20,000 --> 00:00:23,000
Per aiutare a visualizzare questo, può essere utile picture

9
00:00:23,000 --> 00:00:25,000
una fila alla cassa in un negozio.

10
00:00:25,000 --> 00:00:28,000
Dato che le persone arrivano, aspettano sul retro della linea.

11
00:00:28,000 --> 00:00:31,000
Il cassiere poi prende giri servire i clienti nella parte anteriore,

12
00:00:31,000 --> 00:00:34,000
che poi uscire una riga alla volta.

13
00:00:34,000 --> 00:00:37,000
In informatica, si fa riferimento alla parte anteriore della coda come il capo

14
00:00:37,000 --> 00:00:39,000
e indietro come la coda.

15
00:00:39,000 --> 00:00:41,000
Un esempio di quando si potrebbe utilizzare questo in un'applicazione

16
00:00:41,000 --> 00:00:44,000
è una lista di attesa per le iscrizioni di classe.

17
00:00:44,000 --> 00:00:46,000
Come posti saranno disponibili nella classe,

18
00:00:46,000 --> 00:00:50,000
la persona a capo della lista d'attesa è prevista la possibilità di iscriversi nella classe.

19
00:00:50,000 --> 00:00:53,000
>> Una coda può essere costruita usando qualsiasi raccolta

20
00:00:53,000 --> 00:00:57,000
che memorizza dati in ordine, ad esempio una matrice o un elenco collegato.

21
00:00:57,000 --> 00:01:00,000
Insieme con la collezione per memorizzare gli elementi nella coda,

22
00:01:00,000 --> 00:01:02,000
occorre anche un metodo per aggiungere elementi alla fine della coda,

23
00:01:02,000 --> 00:01:04,000
che si chiama enqueuing,

24
00:01:04,000 --> 00:01:07,000
e un altro per rimuovere un elemento dalla testa della coda,

25
00:01:07,000 --> 00:01:09,000
che si chiama l'accodamento.

26
00:01:09,000 --> 00:01:14,000
Spesso è utile inserire un altro metodo per restituire la lunghezza corrente della coda

27
00:01:14,000 --> 00:01:17,000
nonché un metodo per verificare se la coda è vuota.

28
00:01:17,000 --> 00:01:20,000
Diamo un'occhiata a come si potrebbe implementare una coda di interi in C,

29
00:01:20,000 --> 00:01:23,000
utilizzando una matrice per la raccolta di elementi.

30
00:01:23,000 --> 00:01:27,000
Per prima cosa, creiamo una struttura chiamata coda per tenere le nostre variabili.

31
00:01:27,000 --> 00:01:30,000
Useremo una matrice a dimensione fissa indice 0 di interi

32
00:01:30,000 --> 00:01:33,000
per memorizzare gli elementi.

33
00:01:33,000 --> 00:01:35,000
Si comprenderà anche una testa variabile chiamata

34
00:01:35,000 --> 00:01:39,000
che memorizza l'indice dell'elemento che è attualmente alla testa della coda.

35
00:01:39,000 --> 00:01:42,000
Una terza variabile, detta lunghezza, saranno utilizzati

36
00:01:42,000 --> 00:01:45,000
per tenere traccia del numero di elementi nella matrice.

37
00:01:45,000 --> 00:01:48,000
In alternativa, si potrebbe considerare l'utilizzo di una coda variabile chiamata

38
00:01:48,000 --> 00:01:51,000
per puntare l'elemento di campo nella matrice.

39
00:01:51,000 --> 00:01:53,000
Prima di scrivere codice più,

40
00:01:53,000 --> 00:01:55,000
proviamo il nostro design.

41
00:01:55,000 --> 00:01:58,000
Cominciamo con una matrice vuota di lunghezza 0,

42
00:01:58,000 --> 00:02:02,000
con la testa a 0.

43
00:02:02,000 --> 00:02:11,000
Ora cerchiamo di accodare 4 valori - 6, 2, 3, e 1.

44
00:02:11,000 --> 00:02:14,000
La lunghezza sarà ora 4,

45
00:02:14,000 --> 00:02:17,000
e la testa rimane a 0.

46
00:02:17,000 --> 00:02:20,000
>> Che cosa succede se annullare l'accodamento di un valore?

47
00:02:20,000 --> 00:02:24,000
Sarà possibile ridurre la lunghezza di 3,

48
00:02:24,000 --> 00:02:28,000
impostare la testa a 1,

49
00:02:28,000 --> 00:02:33,000
e restituire il valore 6.

50
00:02:33,000 --> 00:02:36,000
Tale codice potrebbe essere simile.

51
00:02:36,000 --> 00:02:38,000
Qui abbiamo la funzione dequeue,

52
00:02:38,000 --> 00:02:41,000
che prende un puntatore alla coda - q - e un puntatore all'elemento,

53
00:02:41,000 --> 00:02:44,000
che è un tipo int.

54
00:02:44,000 --> 00:02:47,000
Per prima cosa controllare la lunghezza della coda per assicurarsi che sia maggiore di 0,

55
00:02:47,000 --> 00:02:50,000
per garantire che vi sia un elemento da dequeued.

56
00:02:50,000 --> 00:02:54,000
Poi guardiamo nella matrice elementi, a capo di posizione,

57
00:02:54,000 --> 00:02:58,000
e impostare il valore dell'elemento di essere il valore in quella posizione.

58
00:02:58,000 --> 00:03:01,000
Allora cambiamo la testa di essere l'indice del prossimo

59
00:03:01,000 --> 00:03:04,000
% Della capacità.

60
00:03:04,000 --> 00:03:07,000
Abbiamo quindi ridurre la lunghezza della coda di 1.

61
00:03:07,000 --> 00:03:12,000
Infine, si ritorna true per indicare che il dequeue avuto successo.

62
00:03:12,000 --> 00:03:19,000
Se si dequeue nuovo, la lunghezza sarà 2,

63
00:03:19,000 --> 00:03:24,000
la testa diventerà anche 2,

64
00:03:24,000 --> 00:03:32,000
e il valore restituito sarà 2.

65
00:03:32,000 --> 00:03:35,000
>> Cosa succede se accodare un altro valore, ad esempio un 7?

66
00:03:35,000 --> 00:03:37,000
Come eravamo alla fine della coda,

67
00:03:37,000 --> 00:03:47,000
dovremo avvolgere e memorizzare il valore 0 elemento della matrice.

68
00:03:47,000 --> 00:03:50,000
Matematicamente, questo può essere rappresentato aggiungendo la lunghezza

69
00:03:50,000 --> 00:03:52,000
all'indice della testa

70
00:03:52,000 --> 00:03:55,000
ed eseguire un modulo utilizzando la capacità coda.

71
00:03:55,000 --> 00:04:00,000
Qui che è 2 +2, che è 4% 4,

72
00:04:00,000 --> 00:04:02,000
che è 0.

73
00:04:02,000 --> 00:04:05,000
Traducendo questa idea di codice che abbiamo questa funzione.

74
00:04:05,000 --> 00:04:08,000
Qui vediamo la funzione enqueue,

75
00:04:08,000 --> 00:04:10,000
che prende un puntatore alla coda - q -

76
00:04:10,000 --> 00:04:14,000
e prende l'elemento da accodato, che è un numero intero.

77
00:04:14,000 --> 00:04:18,000
Abbiamo poi controllare per assicurarsi che la capacità della coda

78
00:04:18,000 --> 00:04:21,000
è ancora maggiore della lunghezza corrente della coda.

79
00:04:21,000 --> 00:04:24,000
Successivo, conservare le elemento dell'array elementi

80
00:04:24,000 --> 00:04:30,000
in corrispondenza dell'indice che è determinata dalla testa +% lunghezza della capacità della coda.

81
00:04:30,000 --> 00:04:33,000
Abbiamo quindi aumentare la lunghezza della coda di 1,

82
00:04:33,000 --> 00:04:39,000
e poi tornare true per indicare che la funzione di accodamento ha avuto successo.

83
00:04:39,000 --> 00:04:42,000
>> In aggiunta alle due funzioni che abbiamo detto,

84
00:04:42,000 --> 00:04:44,000
ci sono due funzioni aggiuntive.

85
00:04:44,000 --> 00:04:46,000
La prima è la funzione IsEmpty,

86
00:04:46,000 --> 00:04:48,000
che prende un puntatore alla coda

87
00:04:48,000 --> 00:04:51,000
e verifica che la lunghezza è 0.

88
00:04:51,000 --> 00:04:53,000
La seconda è la funzione di lunghezza,

89
00:04:53,000 --> 00:04:55,000
che tiene anche un puntatore alla coda

90
00:04:55,000 --> 00:04:58,000
e restituisce la lunghezza attuale della struttura.

91
00:04:58,000 --> 00:05:03,000
Questa breve panoramica ha dimostrato una possibile implementazione di una coda.

92
00:05:03,000 --> 00:05:06,000
Uno dei limiti di questa implementazione

93
00:05:06,000 --> 00:05:08,000
è che la coda ha una dimensione fissa massima.

94
00:05:08,000 --> 00:05:11,000
Se si tenta di aggiungere più elementi rispetto alla coda può contenere,

95
00:05:11,000 --> 00:05:14,000
potremmo avere bisogno di ignorare la richiesta e rilasciare l'elemento,

96
00:05:14,000 --> 00:05:17,000
o si può scegliere di restituire un certo tipo di errore.

97
00:05:17,000 --> 00:05:20,000
Utilizzando una lista collegata anziché una matrice

98
00:05:20,000 --> 00:05:22,000
renderebbe più facile dimensione dinamicamente coda.

99
00:05:22,000 --> 00:05:26,000
Tuttavia, dal momento che non hanno accesso diretto agli elementi di una lista concatenata,

100
00:05:26,000 --> 00:05:28,000
se non tenere traccia della coda,

101
00:05:28,000 --> 00:05:32,000
avremmo dovuto acquisire l'intero elenco legato arrivare alla fine ogni volta.

102
00:05:32,000 --> 00:05:35,000
Si potrebbe anche considerare l'utilizzo di una matrice di un altro tipo di dati,

103
00:05:35,000 --> 00:05:39,000
quali strutture, per creare le code di elementi più complessi.

104
00:05:39,000 --> 00:05:42,000
Ripensando al nostro esempio di una lista d'attesa di classe,

105
00:05:42,000 --> 00:05:45,000
queste strutture potrebbe rappresentare i singoli studenti.

106
00:05:45,000 --> 00:05:48,000
>> Il mio nome è Chris Gerber, e questo è CS50.

107
00:05:48,000 --> 00:05:51,000
[CS50.TV]

108
00:05:51,000 --> 00:05:55,000
E ritorni - >> ancora una volta.

109
00:05:55,000 --> 00:06:00,000
E ritorna true per indicare che - la coda ha avuto successo.

110
00:06:00,000 --> 00:06:03,000
-% Della capacità della coda -

111
00:06:03,000 --> 00:06:06,000
E 'intenzione di essere divertente in edit. [Risate]