[Powered by Google Translate] [Ciw] [Chris Gerber, Prifysgol Harvard] Mae hyn yn CS50, CS50.TV] Un strwythur data defnyddiol ar gyfer storio casgliad drefnus o elfennau yn ciw. Mae'n cael ei ddefnyddio pan fydd yr elfennau angen symud yn yr un drefn wrth iddynt gael eu hychwanegu. Mae'r cysyniad hwn yn cael ei gyfeirio ato fel FIFO, sydd yn acronym ar gyfer cyntaf i mewn, cyntaf allan. Er mwyn helpu i ddychmygu hyn, gall fod yn ddefnyddiol i ddarlun llinell ddesg dalu mewn siop. Wrth i bobl gyrraedd, maent yn aros yng nghefn y llinell. Mae'r ariannwr wedyn yn cymryd eu tro yn gwasanaethu cwsmeriaid yn y blaen, sydd wedyn yn gadael yr un llinell ar y tro. Mewn gwyddoniaeth gyfrifiadurol, rydym yn cyfeirio i flaen y ciw fel pennaeth a chefn fel y gynffon. Un enghraifft o pryd y gallem ddefnyddio hyn mewn cais yn waitlist gyfer cofrestriadau dosbarth. Wrth i seddi ar gael yn y dosbarth, y person ar ben y rhestr aros yn cael ei ddarparu ar y cyfle i gofrestru yn y dosbarth. 

Gall ciw yn cael ei hadeiladu gan ddefnyddio unrhyw gasgliad sy'n storio data mewn trefn, fel arae neu restr cysylltiedig. Ynghyd â'r casgliad i storio'r eitemau yn y ciw, rydym hefyd angen dull i ychwanegu eitemau ar ddiwedd y ciw, a elwir yn enqueuing, ac un arall i symud eitem oddi wrth y pennaeth y ciw, a elwir yn dequeuing. Mae'n aml yn ddefnyddiol i gynnwys dull arall i ddychwelyd hyd presennol y ciw yn ogystal â dull i weld a yw'r ciw yn wag. Gadewch i ni edrych ar sut y gallwn weithredu ciw o gyfanrifau yn C, drwy ddefnyddio amrywiaeth eang ar gyfer casglu elfennau. Yn gyntaf, rydym yn creu strwythur o'r enw ciw i gynnal ein newidynnau. Byddwn yn defnyddio amrywiaeth 0 sefydlog-maint mynegai o gyfanrifau i storio yr elfennau. Byddwn hefyd yn cynnwys pennaeth amrywiol o'r enw sy'n storio'r mynegai yr elfen sydd ar hyn o bryd ar ben y ciw. Mae newidyn yn drydydd, a elwir hyd, yn cael eu defnyddio i gadw golwg ar y nifer o elfennau yn y rhesi. Fel dewis arall, gallech ystyried defnyddio cynffon amrywiol o'r enw i dynnu sylw at yr elfen maes olaf yn y casgliad. Cyn i ni ysgrifennu cod unrhyw mwy, gadewch i ni roi cynnig ar ein cynllun. Gadewch i ni ddechrau gydag amrywiaeth gwag o hyd 0, gyda'r pennaeth osod i 0. Nawr gadewch i enqueue 4 gwerth - 6, 2, 3, ac 1. Bydd hyd yn awr yn 4, a bydd y pennaeth yn aros yn 0. 

Beth fydd yn digwydd os byddwn yn dequeue gwerth? Byddwn yn lleihau hyd i 3, gosod y pennaeth i 1, ac yn dychwelyd y gwerth 6. Gallai hynny cod yn edrych fel hyn. Yma, mae gennym y swyddogaeth dequeue, sy'n cymryd pwyntydd at y ciw - q - a rhoi syniad inni am yr elfen, sydd yn int fath. Yn gyntaf rydym yn gwirio hyd y ciw i wneud yn siŵr ei fod yn fwy na 0, er mwyn sicrhau bod yna elfen i'w dequeued. Yna, rydym yn edrych yn yr amrywiaeth elfennau, yn y pen sefyllfa, ac yn gosod y gwerth elfen i fod yn werth yn y sefyllfa honno. Yna byddwn yn newid y pennaeth i fod yn y mynegai nesaf % Y capasiti. Yna, byddwn yn lleihau hyd y ciw erbyn 1. Yn olaf, byddwn yn dychwelyd wir i ddangos bod y dequeue yn llwyddiannus. Os byddwn yn dequeue eto, bydd hyd yn 2, bydd y pennaeth hefyd yn dod yn 2, a bydd y gwerth yn dychwelyd 2. 

Beth fydd yn digwydd os byddwn yn enqueue werth arall megis 7? Fel yr oeddem ar ddiwedd y ciw, bydd angen i lapio o gwmpas ac yn storio gwerth mewn 0 elfen o'r rhesi. Fathemategol, gall hyn gael ei gynrychioli gan ychwanegu hyd at y mynegai y pen a pherfformio modwlws ddefnyddio cynhwysedd ciw. Yma hynny yw 2 +2, sydd 4% 4, sydd yn 0. Cyfieithu y syniad hwn i cod gennym swyddogaeth hon. Yma rydym yn gweld y swyddogaeth enqueue, sy'n cymryd pwyntydd at y ciw - q - ac yn cymryd yr elfen i'w enqueued, sydd yn gyfanrif. Rydym nesaf gwirio i wneud yn siŵr bod y cynhwysedd y ciw yn dal yn fwy na hyd presennol y ciw. Nesaf, byddwn yn storio'r elfen yn yr amrywiaeth elfennau ar y mynegai sy'n cael ei benderfynu gan y pennaeth +% hyd cynhwysedd y ciw. Rydym wedyn yn cynyddu hyd ciw gan 1, ac yna dychwelyd yn wir i ddangos bod y swyddogaeth enqueue yn llwyddiannus. 

Yn ychwanegol at y ddwy swyddogaeth yr ydym wedi crybwyll, mae dau swyddogaethau ychwanegol. Gyntaf yn y swyddogaeth isempty, sy'n cymryd pwyntydd at y ciw ac yn gwirio bod hyd yn 0. Yr ail yw'r swyddogaeth hyd, sydd hefyd yn arwydd o'r ciw ac yn dychwelyd hyd presennol o'r strwythur. Mae'r trosolwg byr hwn wedi dangos un achos gweithredu posibl mewn ciw. Un o'r cyfyngiadau i'r gweithredu yw bod y ciw Mae maint mwyaf sefydlog. Os ydym yn ceisio ychwanegu elfennau mwy nag y gall y ciw dal, efallai y bydd angen i anwybyddu'r cais a gollwng yr elfen, neu efallai y byddwn yn well i ddychwelyd rhyw fath o wall. Gan ddefnyddio rhestr cysylltiedig yn hytrach nag arae fyddai'n ei gwneud yn haws i faint ddynamig y ciw. Fodd bynnag, gan nad oes gennym fynediad uniongyrchol i elfennau o restr cysylltiedig, os nad ydym yn cadw golwg ar y gynffon, byddai'n rhaid i ni sganio y rhestr gyfan sy'n gysylltiedig i gyrraedd y diwedd bob tro. Gallem hefyd ystyried defnyddio amrywiaeth o fath arall data, fel structs, i greu rhesi o elfennau mwy cymhleth. Gan feddwl yn ôl at ein enghraifft o waitlist dosbarth, gallai'r rhain strwythurau cynrychioli myfyrwyr unigol. 

Fy enw i yw Chris Gerber, ac mae hyn yn CS50. [CS50.TV] A ffurflenni - >> Un mwy o amser. Ac yn dychwelyd yn wir i ddangos bod - y ciw yn llwyddiannus. -% Cynhwysedd y ciw - Mae'n mynd i fod yn hwyl yn golygu. [Chwerthin]