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

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

3
00:00:05,000 --> 00:00:07,000
Mae hyn yn CS50, CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Un strwythur data defnyddiol ar gyfer storio casgliad drefnus o elfennau yn ciw.

5
00:00:11,000 --> 00:00:14,000
Mae'n cael ei ddefnyddio pan fydd yr elfennau angen symud

6
00:00:14,000 --> 00:00:16,000
yn yr un drefn wrth iddynt gael eu hychwanegu.

7
00:00:16,000 --> 00:00:20,000
Mae'r cysyniad hwn yn cael ei gyfeirio ato fel FIFO, sydd yn acronym ar gyfer cyntaf i mewn, cyntaf allan.

8
00:00:20,000 --> 00:00:23,000
Er mwyn helpu i ddychmygu hyn, gall fod yn ddefnyddiol i ddarlun

9
00:00:23,000 --> 00:00:25,000
llinell ddesg dalu mewn siop.

10
00:00:25,000 --> 00:00:28,000
Wrth i bobl gyrraedd, maent yn aros yng nghefn y llinell.

11
00:00:28,000 --> 00:00:31,000
Mae'r ariannwr wedyn yn cymryd eu tro yn gwasanaethu cwsmeriaid yn y blaen,

12
00:00:31,000 --> 00:00:34,000
sydd wedyn yn gadael yr un llinell ar y tro.

13
00:00:34,000 --> 00:00:37,000
Mewn gwyddoniaeth gyfrifiadurol, rydym yn cyfeirio i flaen y ciw fel pennaeth

14
00:00:37,000 --> 00:00:39,000
a chefn fel y gynffon.

15
00:00:39,000 --> 00:00:41,000
Un enghraifft o pryd y gallem ddefnyddio hyn mewn cais

16
00:00:41,000 --> 00:00:44,000
yn waitlist gyfer cofrestriadau dosbarth.

17
00:00:44,000 --> 00:00:46,000
Wrth i seddi ar gael yn y dosbarth,

18
00:00:46,000 --> 00:00:50,000
y person ar ben y rhestr aros yn cael ei ddarparu ar y cyfle i gofrestru yn y dosbarth.

19
00:00:50,000 --> 00:00:53,000
>> Gall ciw yn cael ei hadeiladu gan ddefnyddio unrhyw gasgliad

20
00:00:53,000 --> 00:00:57,000
sy'n storio data mewn trefn, fel arae neu restr cysylltiedig.

21
00:00:57,000 --> 00:01:00,000
Ynghyd â'r casgliad i storio'r eitemau yn y ciw,

22
00:01:00,000 --> 00:01:02,000
rydym hefyd angen dull i ychwanegu eitemau ar ddiwedd y ciw,

23
00:01:02,000 --> 00:01:04,000
a elwir yn enqueuing,

24
00:01:04,000 --> 00:01:07,000
ac un arall i symud eitem oddi wrth y pennaeth y ciw,

25
00:01:07,000 --> 00:01:09,000
a elwir yn dequeuing.

26
00:01:09,000 --> 00:01:14,000
Mae'n aml yn ddefnyddiol i gynnwys dull arall i ddychwelyd hyd presennol y ciw

27
00:01:14,000 --> 00:01:17,000
yn ogystal â dull i weld a yw'r ciw yn wag.

28
00:01:17,000 --> 00:01:20,000
Gadewch i ni edrych ar sut y gallwn weithredu ciw o gyfanrifau yn C,

29
00:01:20,000 --> 00:01:23,000
drwy ddefnyddio amrywiaeth eang ar gyfer casglu elfennau.

30
00:01:23,000 --> 00:01:27,000
Yn gyntaf, rydym yn creu strwythur o'r enw ciw i gynnal ein newidynnau.

31
00:01:27,000 --> 00:01:30,000
Byddwn yn defnyddio amrywiaeth 0 sefydlog-maint mynegai o gyfanrifau

32
00:01:30,000 --> 00:01:33,000
i storio yr elfennau.

33
00:01:33,000 --> 00:01:35,000
Byddwn hefyd yn cynnwys pennaeth amrywiol o'r enw

34
00:01:35,000 --> 00:01:39,000
sy'n storio'r mynegai yr elfen sydd ar hyn o bryd ar ben y ciw.

35
00:01:39,000 --> 00:01:42,000
Mae newidyn yn drydydd, a elwir hyd, yn cael eu defnyddio

36
00:01:42,000 --> 00:01:45,000
i gadw golwg ar y nifer o elfennau yn y rhesi.

37
00:01:45,000 --> 00:01:48,000
Fel dewis arall, gallech ystyried defnyddio cynffon amrywiol o'r enw

38
00:01:48,000 --> 00:01:51,000
i dynnu sylw at yr elfen maes olaf yn y casgliad.

39
00:01:51,000 --> 00:01:53,000
Cyn i ni ysgrifennu cod unrhyw mwy,

40
00:01:53,000 --> 00:01:55,000
gadewch i ni roi cynnig ar ein cynllun.

41
00:01:55,000 --> 00:01:58,000
Gadewch i ni ddechrau gydag amrywiaeth gwag o hyd 0,

42
00:01:58,000 --> 00:02:02,000
gyda'r pennaeth osod i 0.

43
00:02:02,000 --> 00:02:11,000
Nawr gadewch i enqueue 4 gwerth - 6, 2, 3, ac 1.

44
00:02:11,000 --> 00:02:14,000
Bydd hyd yn awr yn 4,

45
00:02:14,000 --> 00:02:17,000
a bydd y pennaeth yn aros yn 0.

46
00:02:17,000 --> 00:02:20,000
>> Beth fydd yn digwydd os byddwn yn dequeue gwerth?

47
00:02:20,000 --> 00:02:24,000
Byddwn yn lleihau hyd i 3,

48
00:02:24,000 --> 00:02:28,000
gosod y pennaeth i 1,

49
00:02:28,000 --> 00:02:33,000
ac yn dychwelyd y gwerth 6.

50
00:02:33,000 --> 00:02:36,000
Gallai hynny cod yn edrych fel hyn.

51
00:02:36,000 --> 00:02:38,000
Yma, mae gennym y swyddogaeth dequeue,

52
00:02:38,000 --> 00:02:41,000
sy'n cymryd pwyntydd at y ciw - q - a rhoi syniad inni am yr elfen,

53
00:02:41,000 --> 00:02:44,000
sydd yn int fath.

54
00:02:44,000 --> 00:02:47,000
Yn gyntaf rydym yn gwirio hyd y ciw i wneud yn siŵr ei fod yn fwy na 0,

55
00:02:47,000 --> 00:02:50,000
er mwyn sicrhau bod yna elfen i'w dequeued.

56
00:02:50,000 --> 00:02:54,000
Yna, rydym yn edrych yn yr amrywiaeth elfennau, yn y pen sefyllfa,

57
00:02:54,000 --> 00:02:58,000
ac yn gosod y gwerth elfen i fod yn werth yn y sefyllfa honno.

58
00:02:58,000 --> 00:03:01,000
Yna byddwn yn newid y pennaeth i fod yn y mynegai nesaf

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

60
00:03:04,000 --> 00:03:07,000
Yna, byddwn yn lleihau hyd y ciw erbyn 1.

61
00:03:07,000 --> 00:03:12,000
Yn olaf, byddwn yn dychwelyd wir i ddangos bod y dequeue yn llwyddiannus.

62
00:03:12,000 --> 00:03:19,000
Os byddwn yn dequeue eto, bydd hyd yn 2,

63
00:03:19,000 --> 00:03:24,000
bydd y pennaeth hefyd yn dod yn 2,

64
00:03:24,000 --> 00:03:32,000
a bydd y gwerth yn dychwelyd 2.

65
00:03:32,000 --> 00:03:35,000
>> Beth fydd yn digwydd os byddwn yn enqueue werth arall megis 7?

66
00:03:35,000 --> 00:03:37,000
Fel yr oeddem ar ddiwedd y ciw,

67
00:03:37,000 --> 00:03:47,000
bydd angen i lapio o gwmpas ac yn storio gwerth mewn 0 elfen o'r rhesi.

68
00:03:47,000 --> 00:03:50,000
Fathemategol, gall hyn gael ei gynrychioli gan ychwanegu hyd

69
00:03:50,000 --> 00:03:52,000
at y mynegai y pen

70
00:03:52,000 --> 00:03:55,000
a pherfformio modwlws ddefnyddio cynhwysedd ciw.

71
00:03:55,000 --> 00:04:00,000
Yma hynny yw 2 +2, sydd 4% 4,

72
00:04:00,000 --> 00:04:02,000
sydd yn 0.

73
00:04:02,000 --> 00:04:05,000
Cyfieithu y syniad hwn i cod gennym swyddogaeth hon.

74
00:04:05,000 --> 00:04:08,000
Yma rydym yn gweld y swyddogaeth enqueue,

75
00:04:08,000 --> 00:04:10,000
sy'n cymryd pwyntydd at y ciw - q -

76
00:04:10,000 --> 00:04:14,000
ac yn cymryd yr elfen i'w enqueued, sydd yn gyfanrif.

77
00:04:14,000 --> 00:04:18,000
Rydym nesaf gwirio i wneud yn siŵr bod y cynhwysedd y ciw

78
00:04:18,000 --> 00:04:21,000
yn dal yn fwy na hyd presennol y ciw.

79
00:04:21,000 --> 00:04:24,000
Nesaf, byddwn yn storio'r elfen yn yr amrywiaeth elfennau

80
00:04:24,000 --> 00:04:30,000
ar y mynegai sy'n cael ei benderfynu gan y pennaeth +% hyd cynhwysedd y ciw.

81
00:04:30,000 --> 00:04:33,000
Rydym wedyn yn cynyddu hyd ciw gan 1,

82
00:04:33,000 --> 00:04:39,000
ac yna dychwelyd yn wir i ddangos bod y swyddogaeth enqueue yn llwyddiannus.

83
00:04:39,000 --> 00:04:42,000
>> Yn ychwanegol at y ddwy swyddogaeth yr ydym wedi crybwyll,

84
00:04:42,000 --> 00:04:44,000
mae dau swyddogaethau ychwanegol.

85
00:04:44,000 --> 00:04:46,000
Gyntaf yn y swyddogaeth isempty,

86
00:04:46,000 --> 00:04:48,000
sy'n cymryd pwyntydd at y ciw

87
00:04:48,000 --> 00:04:51,000
ac yn gwirio bod hyd yn 0.

88
00:04:51,000 --> 00:04:53,000
Yr ail yw'r swyddogaeth hyd,

89
00:04:53,000 --> 00:04:55,000
sydd hefyd yn arwydd o'r ciw

90
00:04:55,000 --> 00:04:58,000
ac yn dychwelyd hyd presennol o'r strwythur.

91
00:04:58,000 --> 00:05:03,000
Mae'r trosolwg byr hwn wedi dangos un achos gweithredu posibl mewn ciw.

92
00:05:03,000 --> 00:05:06,000
Un o'r cyfyngiadau i'r gweithredu

93
00:05:06,000 --> 00:05:08,000
yw bod y ciw Mae maint mwyaf sefydlog.

94
00:05:08,000 --> 00:05:11,000
Os ydym yn ceisio ychwanegu elfennau mwy nag y gall y ciw dal,

95
00:05:11,000 --> 00:05:14,000
efallai y bydd angen i anwybyddu'r cais a gollwng yr elfen,

96
00:05:14,000 --> 00:05:17,000
neu efallai y byddwn yn well i ddychwelyd rhyw fath o wall.

97
00:05:17,000 --> 00:05:20,000
Gan ddefnyddio rhestr cysylltiedig yn hytrach nag arae

98
00:05:20,000 --> 00:05:22,000
fyddai'n ei gwneud yn haws i faint ddynamig y ciw.

99
00:05:22,000 --> 00:05:26,000
Fodd bynnag, gan nad oes gennym fynediad uniongyrchol i elfennau o restr cysylltiedig,

100
00:05:26,000 --> 00:05:28,000
os nad ydym yn cadw golwg ar y gynffon,

101
00:05:28,000 --> 00:05:32,000
byddai'n rhaid i ni sganio y rhestr gyfan sy'n gysylltiedig i gyrraedd y diwedd bob tro.

102
00:05:32,000 --> 00:05:35,000
Gallem hefyd ystyried defnyddio amrywiaeth o fath arall data,

103
00:05:35,000 --> 00:05:39,000
fel structs, i greu rhesi o elfennau mwy cymhleth.

104
00:05:39,000 --> 00:05:42,000
Gan feddwl yn ôl at ein enghraifft o waitlist dosbarth,

105
00:05:42,000 --> 00:05:45,000
gallai'r rhain strwythurau cynrychioli myfyrwyr unigol.

106
00:05:45,000 --> 00:05:48,000
>> Fy enw i yw Chris Gerber, ac mae hyn yn CS50.

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

108
00:05:51,000 --> 00:05:55,000
A ffurflenni - >> Un mwy o amser.

109
00:05:55,000 --> 00:06:00,000
Ac yn dychwelyd yn wir i ddangos bod - y ciw yn llwyddiannus.

110
00:06:00,000 --> 00:06:03,000
-% Cynhwysedd y ciw -

111
00:06:03,000 --> 00:06:06,000
Mae'n mynd i fod yn hwyl yn golygu. [Chwerthin]