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

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

3
00:00:05,000 --> 00:00:07,000
Això és CS50, CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Una estructura de dades útil per emmagatzemar una col · lecció ordenada d'elements és una cua.

5
00:00:11,000 --> 00:00:14,000
S'usa quan els elements necessiten ser remoguts

6
00:00:14,000 --> 00:00:16,000
en el mateix ordre en què s'han afegit.

7
00:00:16,000 --> 00:00:20,000
Aquest concepte es coneix com FIFO, que és un acrònim de primer a entrar, primer en sortir.

8
00:00:20,000 --> 00:00:23,000
Per ajudar a visualitzar aquest, pot ser útil per a foto

9
00:00:23,000 --> 00:00:25,000
una fila per pagar en una botiga.

10
00:00:25,000 --> 00:00:28,000
Com la gent arriba, esperen al final de la línia.

11
00:00:28,000 --> 00:00:31,000
El caixer llavors fan torns per servir els clients al front,

12
00:00:31,000 --> 00:00:34,000
que surti de la línia al mateix temps.

13
00:00:34,000 --> 00:00:37,000
En informàtica, ens referim a la part davantera de la cua al cap

14
00:00:37,000 --> 00:00:39,000
i la part posterior com la cua.

15
00:00:39,000 --> 00:00:41,000
Un exemple de quan es pot utilitzar en una aplicació d'aquest

16
00:00:41,000 --> 00:00:44,000
és una llista d'espera per a inscripcions de classe.

17
00:00:44,000 --> 00:00:46,000
Quan es disposi de seients a la classe,

18
00:00:46,000 --> 00:00:50,000
la persona al capdavant de la llista d'espera s'ofereix l'oportunitat de inscriure a la classe.

19
00:00:50,000 --> 00:00:53,000
>> Una cua pot ser construïda usant qualsevol col · lecció

20
00:00:53,000 --> 00:00:57,000
que emmagatzema les dades en ordre, com ara una matriu o una llista enllaçada.

21
00:00:57,000 --> 00:01:00,000
Juntament amb la col · lecció per emmagatzemar els elements de la cua,

22
00:01:00,000 --> 00:01:02,000
també es necessita un mètode per afegir elements al final de la cua,

23
00:01:02,000 --> 00:01:04,000
que es diu enqueuing,

24
00:01:04,000 --> 00:01:07,000
i una altra per eliminar un element del cap de la cua,

25
00:01:07,000 --> 00:01:09,000
que es diu desencua.

26
00:01:09,000 --> 00:01:14,000
Sovint és útil incloure un altre mètode per tornar la longitud actual de la cua

27
00:01:14,000 --> 00:01:17,000
així com un mètode per comprovar si la cua és buida.

28
00:01:17,000 --> 00:01:20,000
Anem a veure com podem implementar una cua d'enters en C,

29
00:01:20,000 --> 00:01:23,000
utilitzant una matriu per a la col · lecció d'elements.

30
00:01:23,000 --> 00:01:27,000
En primer lloc, vam crear una estructura anomenada cua per contenir les nostres variables.

31
00:01:27,000 --> 00:01:30,000
Anem a utilitzar una matriu de mida fixa 0 índex d'enters

32
00:01:30,000 --> 00:01:33,000
per emmagatzemar els elements.

33
00:01:33,000 --> 00:01:35,000
També s'inclouen un cap variable anomenada

34
00:01:35,000 --> 00:01:39,000
que emmagatzema l'índex de l'element que es troba actualment al cap de la cua.

35
00:01:39,000 --> 00:01:42,000
Una tercera variable, anomenada longitud, s'utilitzarà

36
00:01:42,000 --> 00:01:45,000
per fer un seguiment del nombre d'elements en la matriu.

37
00:01:45,000 --> 00:01:48,000
Com a alternativa, es pot considerar l'ús d'una variable anomenada cua

38
00:01:48,000 --> 00:01:51,000
perquè apunti a l'element últim camp a la matriu.

39
00:01:51,000 --> 00:01:53,000
Abans d'escriure codi més,

40
00:01:53,000 --> 00:01:55,000
anem a provar el nostre disseny.

41
00:01:55,000 --> 00:01:58,000
Anem a començar amb una matriu buida de longitud 0,

42
00:01:58,000 --> 00:02:02,000
amb el cap a 0.

43
00:02:02,000 --> 00:02:11,000
Ara anem a enqueue 4 valors - 6, 2, 3, i 1.

44
00:02:11,000 --> 00:02:14,000
La longitud serà ara 4,

45
00:02:14,000 --> 00:02:17,000
i el cap es quedarà a 0.

46
00:02:17,000 --> 00:02:20,000
>> Què passa si treure de la cua un valor?

47
00:02:20,000 --> 00:02:24,000
Anem a reduir la longitud a 3,

48
00:02:24,000 --> 00:02:28,000
establir el cap a 1,

49
00:02:28,000 --> 00:02:33,000
i tornar el valor 6.

50
00:02:33,000 --> 00:02:36,000
Aquest codi es veuria així.

51
00:02:36,000 --> 00:02:38,000
Aquí tenim la funció de treure de la cua,

52
00:02:38,000 --> 00:02:41,000
que pren un punter a la cua - q - i un punter a l'element,

53
00:02:41,000 --> 00:02:44,000
que és un tipus int.

54
00:02:44,000 --> 00:02:47,000
En primer lloc, comprovar la longitud de la cua per assegurar-se que és més gran que 0,

55
00:02:47,000 --> 00:02:50,000
per assegurar que hi ha un element a ser llevades de la cua.

56
00:02:50,000 --> 00:02:54,000
Després ens fixem en la matriu d'elements, en la posició del cap,

57
00:02:54,000 --> 00:02:58,000
i escolliu el valor d'element a ser el valor en aquesta posició.

58
00:02:58,000 --> 00:03:01,000
Després canviem el cap per ser el següent índex

59
00:03:01,000 --> 00:03:04,000
% De la capacitat.

60
00:03:04,000 --> 00:03:07,000
A continuació, reduir la longitud de la cua per 1.

61
00:03:07,000 --> 00:03:12,000
Finalment, tornem true per indicar que el treure de la cua s'ha realitzat correctament.

62
00:03:12,000 --> 00:03:19,000
Si treure de la cua de nou, la longitud serà 2,

63
00:03:19,000 --> 00:03:24,000
el cap també es convertirà en dues,

64
00:03:24,000 --> 00:03:32,000
i el valor de retorn serà 2.

65
00:03:32,000 --> 00:03:35,000
>> Què passa si encolar altre valor, com un 7?

66
00:03:35,000 --> 00:03:37,000
Com ja es trobaven al final de la cua,

67
00:03:37,000 --> 00:03:47,000
haurem de embolicar i emmagatzemar el valor a 0 element de la matriu.

68
00:03:47,000 --> 00:03:50,000
Matemàticament, això es pot representar mitjançant l'addició de la longitud

69
00:03:50,000 --> 00:03:52,000
per l'índex del cap

70
00:03:52,000 --> 00:03:55,000
i la realització d'un mòdul utilitzant la capacitat de la cua.

71
00:03:55,000 --> 00:04:00,000
Aquí és a dir 2 +2, que és 4% 4,

72
00:04:00,000 --> 00:04:02,000
que és 0.

73
00:04:02,000 --> 00:04:05,000
Traduint aquesta idea de codificar tenim aquesta funció.

74
00:04:05,000 --> 00:04:08,000
Aquí veiem la funció de posada en cua,

75
00:04:08,000 --> 00:04:10,000
que pren un punter a la cua - q -

76
00:04:10,000 --> 00:04:14,000
i pren l'element a encolar, que és un nombre enter.

77
00:04:14,000 --> 00:04:18,000
A continuació comprovar per assegurar-se que la capacitat de la cua

78
00:04:18,000 --> 00:04:21,000
és encara més gran que la longitud actual de la cua.

79
00:04:21,000 --> 00:04:24,000
A continuació, es guarda l'element en la matriu d'elements

80
00:04:24,000 --> 00:04:30,000
en l'índex que es determina pel cap% + longitud de la capacitat de la cua.

81
00:04:30,000 --> 00:04:33,000
A continuació, augmentar la longitud de la cua per 1,

82
00:04:33,000 --> 00:04:39,000
i després tornar true per indicar que la funció de posada en cua s'ha realitzat correctament.

83
00:04:39,000 --> 00:04:42,000
>> A més de les dues funcions que hem esmentat,

84
00:04:42,000 --> 00:04:44,000
hi ha dues funcions addicionals.

85
00:04:44,000 --> 00:04:46,000
La primera és la funció IsEmpty,

86
00:04:46,000 --> 00:04:48,000
que pren un punter a la cua

87
00:04:48,000 --> 00:04:51,000
i verifica que la longitud és 0.

88
00:04:51,000 --> 00:04:53,000
La segona és la funció de longitud,

89
00:04:53,000 --> 00:04:55,000
que també té un punter a la cua

90
00:04:55,000 --> 00:04:58,000
i retorna la longitud actual de l'estructura.

91
00:04:58,000 --> 00:05:03,000
Aquesta breu ressenya ha demostrat una possible implementació d'una cua.

92
00:05:03,000 --> 00:05:06,000
Una de les limitacions a aquesta implementació

93
00:05:06,000 --> 00:05:08,000
és que la cua té una mida màxima fix.

94
00:05:08,000 --> 00:05:11,000
Si tractem d'afegir més elements que la cua pot contenir,

95
00:05:11,000 --> 00:05:14,000
és possible que hàgim d'ignorar la sol · licitud i deixar anar l'element,

96
00:05:14,000 --> 00:05:17,000
o potser prefereix tornar algun tipus d'error.

97
00:05:17,000 --> 00:05:20,000
Ús d'una llista vinculada en lloc d'una matriu

98
00:05:20,000 --> 00:05:22,000
faria més fàcil a mida dinàmicament la cua.

99
00:05:22,000 --> 00:05:26,000
No obstant això, ja que no tenen accés directe als elements d'una llista enllaçada,

100
00:05:26,000 --> 00:05:28,000
si no mantenim un registre de la cua,

101
00:05:28,000 --> 00:05:32,000
hauríem de escanejar tota la llista vinculada a arribar fins al final cada vegada.

102
00:05:32,000 --> 00:05:35,000
També podria considerar l'ús d'una gran varietat d'altres tipus de dades,

103
00:05:35,000 --> 00:05:39,000
com ara estructures, per crear cues de elements més complexos.

104
00:05:39,000 --> 00:05:42,000
Pensant de nou al nostre exemple d'una llista d'espera de classe,

105
00:05:42,000 --> 00:05:45,000
aquestes estructures podrien representar als estudiants individuals.

106
00:05:45,000 --> 00:05:48,000
>> El meu nom és Chris Gerber, i això és CS50.

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

108
00:05:51,000 --> 00:05:55,000
I volta - >> Una vegada més.

109
00:05:55,000 --> 00:06:00,000
I tornar true per indicar que - la cua s'ha realitzat correctament.

110
00:06:00,000 --> 00:06:03,000
-% De la capacitat de la cua -

111
00:06:03,000 --> 00:06:06,000
Serà divertit en edició. [Rialles]