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

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

3
00:00:05,000 --> 00:00:07,000
Ini adalah CS50, CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Salah berguna data struktur untuk menyimpan koleksi diperintahkan unsur adalah barisan.

5
00:00:11,000 --> 00:00:14,000
Ia digunakan apabila unsur-unsur perlu dibuang

6
00:00:14,000 --> 00:00:16,000
dalam perintah yang sama kerana mereka telah ditambah.

7
00:00:16,000 --> 00:00:20,000
Konsep ini disebut sebagai FIFO, yang merupakan singkatan bagi pertama dalam, mula-mula keluar.

8
00:00:20,000 --> 00:00:23,000
Untuk membantu menggambarkan ini, ia mungkin berguna untuk gambar

9
00:00:23,000 --> 00:00:25,000
garis checkout di kedai.

10
00:00:25,000 --> 00:00:28,000
Sebagai orang tiba, mereka menunggu di belakang garisan.

11
00:00:28,000 --> 00:00:31,000
Juruwang kemudian mengambil giliran berkhidmat pelanggan di bahagian hadapan,

12
00:00:31,000 --> 00:00:34,000
yang kemudian keluar satu baris pada satu masa.

13
00:00:34,000 --> 00:00:37,000
Dalam bidang sains komputer, kita merujuk kepada hadapan barisan sebagai ketua

14
00:00:37,000 --> 00:00:39,000
dan belakang sebagai ekor.

15
00:00:39,000 --> 00:00:41,000
Satu contoh apabila kita mungkin menggunakan ini dalam permohonan

16
00:00:41,000 --> 00:00:44,000
adalah senarai tunggu untuk pendaftaran kelas.

17
00:00:44,000 --> 00:00:46,000
Sebagai tempat duduk menjadi didapati di dalam kelas,

18
00:00:46,000 --> 00:00:50,000
orang di kepala senarai menunggu disediakan peluang untuk mendaftar di dalam kelas.

19
00:00:50,000 --> 00:00:53,000
>> Beratur boleh dibina menggunakan mana-mana koleksi

20
00:00:53,000 --> 00:00:57,000
yang menyimpan data dalam perintah, seperti pelbagai atau senarai berpaut.

21
00:00:57,000 --> 00:01:00,000
Bersama-sama dengan koleksi untuk menyimpan item dalam barisan,

22
00:01:00,000 --> 00:01:02,000
kita juga memerlukan satu kaedah untuk menambah item pada akhir barisan,

23
00:01:02,000 --> 00:01:04,000
yang dipanggil enqueuing,

24
00:01:04,000 --> 00:01:07,000
dan satu lagi untuk membuang item dari kepala barisan,

25
00:01:07,000 --> 00:01:09,000
yang dipanggil dequeuing.

26
00:01:09,000 --> 00:01:14,000
Ia sering berguna untuk memasukkan kaedah lain untuk mengembalikan panjang semasa barisan

27
00:01:14,000 --> 00:01:17,000
serta kaedah untuk memeriksa jika barisan kosong.

28
00:01:17,000 --> 00:01:20,000
Mari kita melihat bagaimana kita boleh melaksanakan beratur integer dalam C,

29
00:01:20,000 --> 00:01:23,000
menggunakan array untuk koleksi unsur.

30
00:01:23,000 --> 00:01:27,000
Pertama, kita mewujudkan satu struktur yang dipanggil beratur untuk memegang pembolehubah kami.

31
00:01:27,000 --> 00:01:30,000
Kami akan menggunakan saiz tetap 0 indeks pelbagai integer

32
00:01:30,000 --> 00:01:33,000
untuk menyimpan unsur-unsur.

33
00:01:33,000 --> 00:01:35,000
Kami juga akan termasuk kepala ubah yang dipanggil

34
00:01:35,000 --> 00:01:39,000
yang menyimpan indeks unsur yang kini berada di kepala barisan.

35
00:01:39,000 --> 00:01:42,000
Satu pembolehubah ketiga, dipanggil panjang, akan digunakan

36
00:01:42,000 --> 00:01:45,000
menjejaki bilangan elemen dalam array.

37
00:01:45,000 --> 00:01:48,000
Sebagai alternatif, anda boleh mempertimbangkan untuk menggunakan ekor pembolehubah yang dipanggil

38
00:01:48,000 --> 00:01:51,000
untuk menunjukkan elemen bidang terakhir dalam array.

39
00:01:51,000 --> 00:01:53,000
Sebelum kita menulis kod apa-apa lagi,

40
00:01:53,000 --> 00:01:55,000
mari kita mencuba reka bentuk kami.

41
00:01:55,000 --> 00:01:58,000
Mari kita mulakan dengan pelbagai kosong 0 panjang,

42
00:01:58,000 --> 00:02:02,000
dengan kepala disetkan kepada 0.

43
00:02:02,000 --> 00:02:11,000
Sekarang mari kita enqueue 4 nilai - 6, 2, 3, dan 1.

44
00:02:11,000 --> 00:02:14,000
Panjang sekarang akan menjadi 4,

45
00:02:14,000 --> 00:02:17,000
dan kepala akan kekal pada 0.

46
00:02:17,000 --> 00:02:20,000
>> Apakah yang akan berlaku jika kita dequeue nilai?

47
00:02:20,000 --> 00:02:24,000
Kami akan mengurangkan panjang hingga 3,

48
00:02:24,000 --> 00:02:28,000
tetapkan kepala 1,

49
00:02:28,000 --> 00:02:33,000
dan memulangkan nilai 6.

50
00:02:33,000 --> 00:02:36,000
Kod yang mungkin kelihatan seperti ini.

51
00:02:36,000 --> 00:02:38,000
Di sini kita mempunyai fungsi dequeue,

52
00:02:38,000 --> 00:02:41,000
yang mengambil penunjuk beratur - q - dan penunjuk kepada elemen,

53
00:02:41,000 --> 00:02:44,000
yang merupakan jenis int.

54
00:02:44,000 --> 00:02:47,000
Mula-mula kita memeriksa panjang barisan untuk pastikan ia adalah lebih daripada 0,

55
00:02:47,000 --> 00:02:50,000
untuk memastikan bahawa terdapat elemen untuk dequeued.

56
00:02:50,000 --> 00:02:54,000
Kemudian kita lihat dalam pelbagai unsur, di kepala kedudukan,

57
00:02:54,000 --> 00:02:58,000
dan menetapkan nilai unsur untuk menjadi nilai pada kedudukan itu.

58
00:02:58,000 --> 00:03:01,000
Kemudian kita menukar kepala menjadi indeks seterusnya

59
00:03:01,000 --> 00:03:04,000
% Kapasiti.

60
00:03:04,000 --> 00:03:07,000
Kami kemudian mengurangkan panjang baris gilir oleh 1.

61
00:03:07,000 --> 00:03:12,000
Akhirnya, kita kembali benar untuk menunjukkan bahawa dequeue berjaya.

62
00:03:12,000 --> 00:03:19,000
Jika kita dequeue lagi, panjang akan menjadi 2,

63
00:03:19,000 --> 00:03:24,000
kepala juga akan menjadi 2,

64
00:03:24,000 --> 00:03:32,000
dan nilai pulangan akan 2.

65
00:03:32,000 --> 00:03:35,000
>> Apakah yang akan berlaku jika kita enqueue nilai lain seperti 7?

66
00:03:35,000 --> 00:03:37,000
Seperti yang kita berada di akhir barisan,

67
00:03:37,000 --> 00:03:47,000
kita akan perlu untuk membalut di sekitar dan menyimpan nilai 0 elemen array.

68
00:03:47,000 --> 00:03:50,000
Secara matematik, ini boleh diwakili oleh menambah panjang

69
00:03:50,000 --> 00:03:52,000
indeks kepala

70
00:03:52,000 --> 00:03:55,000
dan melaksanakan modulus menggunakan kapasiti beratur.

71
00:03:55,000 --> 00:04:00,000
Di sini bahawa 2 +2, yang merupakan 4% 4,

72
00:04:00,000 --> 00:04:02,000
yang adalah 0.

73
00:04:02,000 --> 00:04:05,000
Menterjemahkan idea ini kod kita mempunyai fungsi ini.

74
00:04:05,000 --> 00:04:08,000
Di sini kita lihat fungsi enqueue,

75
00:04:08,000 --> 00:04:10,000
yang mengambil penunjuk beratur - q -

76
00:04:10,000 --> 00:04:14,000
dan mengambil unsur enqueued, yang merupakan integer.

77
00:04:14,000 --> 00:04:18,000
Kami seterusnya periksa untuk memastikan bahawa kapasiti barisan

78
00:04:18,000 --> 00:04:21,000
adalah masih lebih besar daripada panjang semasa beratur.

79
00:04:21,000 --> 00:04:24,000
Seterusnya, kami menyimpan unsur dalam pelbagai elemen

80
00:04:24,000 --> 00:04:30,000
pada indeks yang ditentukan oleh ketua + panjang% kapasiti barisan.

81
00:04:30,000 --> 00:04:33,000
Kami kemudian meningkatkan panjang baris gilir sebanyak 1,

82
00:04:33,000 --> 00:04:39,000
dan kemudian kembali kenyataan untuk menunjukkan bahawa fungsi enqueue berjaya.

83
00:04:39,000 --> 00:04:42,000
>> Di samping itu kepada dua fungsi yang kami telah sebutkan,

84
00:04:42,000 --> 00:04:44,000
terdapat dua fungsi tambahan.

85
00:04:44,000 --> 00:04:46,000
Pertama adalah fungsi isempty,

86
00:04:46,000 --> 00:04:48,000
yang mengambil penunjuk beratur

87
00:04:48,000 --> 00:04:51,000
dan mengesahkan bahawa panjang adalah 0.

88
00:04:51,000 --> 00:04:53,000
Kedua ialah fungsi panjang,

89
00:04:53,000 --> 00:04:55,000
yang juga mengambil penunjuk beratur

90
00:04:55,000 --> 00:04:58,000
dan mengembalikan panjang semasa dari struct.

91
00:04:58,000 --> 00:05:03,000
Ini gambaran singkat telah menunjukkan satu pelaksanaan kemungkinan barisan.

92
00:05:03,000 --> 00:05:06,000
Satu batasan pelaksanaan ini

93
00:05:06,000 --> 00:05:08,000
adalah bahawa barisan mempunyai saiz maksimum tetap.

94
00:05:08,000 --> 00:05:11,000
Jika kita cuba untuk menambah lebih banyak unsur-unsur daripada barisan boleh memegang,

95
00:05:11,000 --> 00:05:14,000
kita mungkin perlu untuk mengabaikan permintaan dan menggugurkan elemen,

96
00:05:14,000 --> 00:05:17,000
atau kita boleh memilih untuk mengembalikan beberapa jenis kesilapan.

97
00:05:17,000 --> 00:05:20,000
Menggunakan senarai dikaitkan bukannya array

98
00:05:20,000 --> 00:05:22,000
akan membuat ia lebih mudah kepada saiz dinamik barisan.

99
00:05:22,000 --> 00:05:26,000
Walau bagaimanapun, kerana kita tidak mempunyai akses langsung kepada unsur-unsur senarai berkaitan,

100
00:05:26,000 --> 00:05:28,000
jika kita tidak menjejaki ekor,

101
00:05:28,000 --> 00:05:32,000
kita akan perlu untuk mengimbas senarai keseluruhan dikaitkan untuk sampai ke akhir setiap kali.

102
00:05:32,000 --> 00:05:35,000
Kita juga boleh mempertimbangkan untuk menggunakan pelbagai jenis data yang lain,

103
00:05:35,000 --> 00:05:39,000
itu sebagai structs, untuk mewujudkan barisan unsur-unsur yang lebih kompleks.

104
00:05:39,000 --> 00:05:42,000
Memikirkan kembali contoh senarai tunggu kelas kami,

105
00:05:42,000 --> 00:05:45,000
struktur ini boleh mewakili pelajar individu.

106
00:05:45,000 --> 00:05:48,000
>> Nama saya Chris Gerber, dan ini adalah CS50.

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

108
00:05:51,000 --> 00:05:55,000
Dan pulangan - >> Satu masa yang lebih.

109
00:05:55,000 --> 00:06:00,000
Dan kembalilah benar untuk menunjukkan bahawa barisan berjaya.

110
00:06:00,000 --> 00:06:03,000
-% Kapasiti barisan -

111
00:06:03,000 --> 00:06:06,000
Ia akan menjadi menyeronokkan di sunting. [Ketawa]