1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Biðröð]

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

3
00:00:05,000 --> 00:00:07,000
Þetta er CS50, CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Einn gagnlegur gögn uppbygging til að geyma að panta safn frumefni er biðröð.

5
00:00:11,000 --> 00:00:14,000
Það er notað þegar atriði þarf að vera fjarri

6
00:00:14,000 --> 00:00:16,000
í sömu röð og þeir voru við.

7
00:00:16,000 --> 00:00:20,000
Þetta hugtak er nefnt FIFO, sem er skammstöfun fyrir fyrst inn, fyrst út.

8
00:00:20,000 --> 00:00:23,000
Til að hjálpa sjón það, getur það verið gagnlegt að mynd

9
00:00:23,000 --> 00:00:25,000
a stöðva línu á verslun.

10
00:00:25,000 --> 00:00:28,000
Eins og fólk kemur, bíða þeir á bak við línuna.

11
00:00:28,000 --> 00:00:31,000
Gjaldkeri tekur þá skiptast þjóna viðskiptavinum í framan,

12
00:00:31,000 --> 00:00:34,000
sem hætta síðan línuna einn í einu.

13
00:00:34,000 --> 00:00:37,000
Í tölvunarfræði, átt við að framan biðröð og höfuð

14
00:00:37,000 --> 00:00:39,000
og aftur og hali.

15
00:00:39,000 --> 00:00:41,000
Dæmi um hvenær við gætum notað þetta í forriti

16
00:00:41,000 --> 00:00:44,000
er waitlist fyrir skráninga bekknum.

17
00:00:44,000 --> 00:00:46,000
Sem sæti verða í boði í bekknum,

18
00:00:46,000 --> 00:00:50,000
sá í höfuðið á biðlista er veitt tækifæri til að innritast í bekknum.

19
00:00:50,000 --> 00:00:53,000
>> A biðröð getur verið smíðaður með hvaða safn

20
00:00:53,000 --> 00:00:57,000
sem geymir gögn í því skyni, svo sem fylki eða tengda listanum.

21
00:00:57,000 --> 00:01:00,000
Ásamt safn til að geyma hluti í biðröð,

22
00:01:00,000 --> 00:01:02,000
við þurfum líka aðferð til að bæta hlutum við lok biðröð,

23
00:01:02,000 --> 00:01:04,000
sem heitir enqueuing,

24
00:01:04,000 --> 00:01:07,000
og aðra til að fjarlægja hlut úr höfði biðröð,

25
00:01:07,000 --> 00:01:09,000
sem heitir dequeuing.

26
00:01:09,000 --> 00:01:14,000
Það er oft gagnlegt að fela aðra aðferð til að skila núverandi lengd biðröð

27
00:01:14,000 --> 00:01:17,000
og aðferð til að athuga hvort biðröð er tóm.

28
00:01:17,000 --> 00:01:20,000
Við skulum líta á hvernig við gætum innleiða biðröð heiltalna í C,

29
00:01:20,000 --> 00:01:23,000
nota fylki til innheimtu frumefni.

30
00:01:23,000 --> 00:01:27,000
Fyrst skaltu búa við skipulag sem kallast biðröð til að halda breytur okkar.

31
00:01:27,000 --> 00:01:30,000
Við munum nota fasta stærð 0 vísitölu fjölbreytta heiltölur

32
00:01:30,000 --> 00:01:33,000
að geyma atriði.

33
00:01:33,000 --> 00:01:35,000
Við munum einnig breytilega heitir höfuð

34
00:01:35,000 --> 00:01:39,000
sem geymir vísitölu frumefni sem er nú í forsvari fyrir biðröð.

35
00:01:39,000 --> 00:01:42,000
Þriðja breyta, length, verður notuð

36
00:01:42,000 --> 00:01:45,000
til að halda utan um fjölda staka í fylki.

37
00:01:45,000 --> 00:01:48,000
Sem val, þú getur íhuga að nota breytu sem heitir hala

38
00:01:48,000 --> 00:01:51,000
að benda á síðasta sviði þáttur í fylki.

39
00:01:51,000 --> 00:01:53,000
Áður en við að skrifa einhverjar fleiri kóða,

40
00:01:53,000 --> 00:01:55,000
skulum prófa hönnun okkar.

41
00:01:55,000 --> 00:01:58,000
Við skulum byrja með tóman fjölda lengd 0,

42
00:01:58,000 --> 00:02:02,000
með höfuð stillt á 0.

43
00:02:02,000 --> 00:02:11,000
Nú e, skulum 4 gildi - 6, 2, 3, og 1.

44
00:02:11,000 --> 00:02:14,000
Lengd verður nú að vera 4,

45
00:02:14,000 --> 00:02:17,000
og höfuð mun gista á 0.

46
00:02:17,000 --> 00:02:20,000
>> Hvað gerist ef við dequeue gildi?

47
00:02:20,000 --> 00:02:24,000
Við munum draga úr lengd í 3,

48
00:02:24,000 --> 00:02:28,000
setja höfuð á 1,

49
00:02:28,000 --> 00:02:33,000
og skila gildi 6.

50
00:02:33,000 --> 00:02:36,000
Sá kóði getur litið svona út.

51
00:02:36,000 --> 00:02:38,000
Hér höfum við dequeue virka,

52
00:02:38,000 --> 00:02:41,000
sem tekur bendi á í biðröð - Q - og bendi á frumefni,

53
00:02:41,000 --> 00:02:44,000
sem er tegund int.

54
00:02:44,000 --> 00:02:47,000
Fyrst við athugum lengd biðröð til að ganga úr skugga um að það er meira en 0,

55
00:02:47,000 --> 00:02:50,000
til að tryggja að það er þáttur í að dequeued.

56
00:02:50,000 --> 00:02:54,000
Þá erum við að horfa á þætti fylking, í sömu stöðu höfuð,

57
00:02:54,000 --> 00:02:58,000
og setja the gildi af frumefni að gildi á þeirri stöðu.

58
00:02:58,000 --> 00:03:01,000
Þá erum við að breyta höfuð að vera næsta vísitölu

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

60
00:03:04,000 --> 00:03:07,000
Við draga þá lengd biðröð eftir 1.

61
00:03:07,000 --> 00:03:12,000
Að lokum, aftur við rétt til að sýna að dequeue tókst.

62
00:03:12,000 --> 00:03:19,000
Ef við dequeue aftur lengd verða 2,

63
00:03:19,000 --> 00:03:24,000
höfuð mun einnig verða 2,

64
00:03:24,000 --> 00:03:32,000
og skilagildi verða 2.

65
00:03:32,000 --> 00:03:35,000
>> Hvað gerist ef við e, annað gildi, svo sem 7?

66
00:03:35,000 --> 00:03:37,000
Þegar við vorum í lok biðröð,

67
00:03:37,000 --> 00:03:47,000
við verðum að vefja um og geyma verðmæti í 0 þáttur fylkisins.

68
00:03:47,000 --> 00:03:50,000
Stærðfræðilega má þetta vera fulltrúa með því að bæta lengd

69
00:03:50,000 --> 00:03:52,000
við vísitölu höfuð

70
00:03:52,000 --> 00:03:55,000
og framkvæma stuðull með biðröðina getu.

71
00:03:55,000 --> 00:04:00,000
Hér er að 2 +2, sem er 4% 4,

72
00:04:00,000 --> 00:04:02,000
sem er 0.

73
00:04:02,000 --> 00:04:05,000
Þýðing þessa hugmynd að kóða við höfum þessa aðgerð.

74
00:04:05,000 --> 00:04:08,000
Hér sjáum við e, virka,

75
00:04:08,000 --> 00:04:10,000
sem tekur bendi á biðröð - Q -

76
00:04:10,000 --> 00:04:14,000
og tekur þátturinn að enqueued, sem er heiltala.

77
00:04:14,000 --> 00:04:18,000
Við athuga næst að tryggja að getu biðröð

78
00:04:18,000 --> 00:04:21,000
er enn meiri en núverandi lengd biðröð.

79
00:04:21,000 --> 00:04:24,000
Næst geyma við þáttur í þætti fylki

80
00:04:24,000 --> 00:04:30,000
á vísitölunni, sem er ákvörðuð út frá höfuð + lengd% getu biðröð.

81
00:04:30,000 --> 00:04:33,000
Við aukið þá biðröð lengd um 1,

82
00:04:33,000 --> 00:04:39,000
og síðan aftur rétt til að sýna að e, virka tókst.

83
00:04:39,000 --> 00:04:42,000
>> Í viðbót við tvo valkosti við höfum getið,

84
00:04:42,000 --> 00:04:44,000
Það eru tvær aðrar aðgerðir.

85
00:04:44,000 --> 00:04:46,000
Fyrst er isempty virka,

86
00:04:46,000 --> 00:04:48,000
sem tekur bendi á í biðröð

87
00:04:48,000 --> 00:04:51,000
og staðfestir að lengd 0.

88
00:04:51,000 --> 00:04:53,000
Annað er lengd virka,

89
00:04:53,000 --> 00:04:55,000
sem tekur einnig bendi til biðröð

90
00:04:55,000 --> 00:04:58,000
og skilar núverandi lengd frá strúktúr.

91
00:04:58,000 --> 00:05:03,000
Þetta stutt yfirlit hefur sýnt ein hugsanleg framkvæmd af biðröð.

92
00:05:03,000 --> 00:05:06,000
Ein af takmörkunum við þessa framkvæmd

93
00:05:06,000 --> 00:05:08,000
er að biðröð hefur fasta hámarks stærð.

94
00:05:08,000 --> 00:05:11,000
Ef við reynum að bæta við fleiri þáttum en biðröð hægt er að halda,

95
00:05:11,000 --> 00:05:14,000
við gætum þurft að hunsa beiðnina og sleppa þáttur,

96
00:05:14,000 --> 00:05:17,000
eða við gætum vilja til að skila einhvers konar villa.

97
00:05:17,000 --> 00:05:20,000
Notkun tengd lista frekar en fylki

98
00:05:20,000 --> 00:05:22,000
myndi gera það auðveldara að dynamically stærð biðröð.

99
00:05:22,000 --> 00:05:26,000
En þar sem við höfum ekki beinan aðgang að þætti í tengda listanum,

100
00:05:26,000 --> 00:05:28,000
Ef við gerum ekki viðurværi rekja spor einhvers af the hali,

101
00:05:28,000 --> 00:05:32,000
yrðum við að skanna allt tengda listanum til að fá að enda hvert skipti.

102
00:05:32,000 --> 00:05:35,000
Við gætum líka íhuga að nota fjölda annars gögn tegund,

103
00:05:35,000 --> 00:05:39,000
eins structs, til að búa til biðraðir á flóknari atriði.

104
00:05:39,000 --> 00:05:42,000
Hugsun aftur til okkar dæmi um tegund waitlist,

105
00:05:42,000 --> 00:05:45,000
þessara stofnana gæti tákna einstaka nemendur.

106
00:05:45,000 --> 00:05:48,000
>> Mitt nafn er Chris Gerber, og þetta er CS50.

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

108
00:05:51,000 --> 00:05:55,000
Og aftur - >> einu sinni enn.

109
00:05:55,000 --> 00:06:00,000
Og aftur rétt til að sýna að - biðröð tókst.

110
00:06:00,000 --> 00:06:03,000
-% Getu í biðröð -

111
00:06:03,000 --> 00:06:06,000
Það er að fara að vera gaman í breytingu. [Hlátur]