[Powered by Google Translate] [Eilės] [Chris Gerber, Harvardo universiteto] Tai CS50, CS50.TV] Vienas iš naudingiausių duomenų struktūra saugoti tvarkingas elementų kolekciją eilė. Jis naudojamas, kai reikia pašalinti elementai ta pačia tvarka, kaip jie buvo įtraukti. Ši koncepcija yra nurodytas kaip FIFO, kuris pirmą santrumpa in, first out. Norėdami padėti vizualizuoti tai, ji gali būti naudinga į paveikslėlį patikros linija parduotuvėje. Kaip žmonės atvyksta, jie laukia nugaros linijos. Kasininkas, tada paeiliui aptarnauti klientus priekyje, kurie paskui išeiti iš linijos vienu metu,. Informatikos, mes vadiname eilės priekyje, galvos ir uodegos atgal. Pavyzdžiui, kai mes galime naudoti šią paraiškos yra, klasės mokinių waitlist. Kadangi vietų tampa prieinamos klasėje, laukiančiųjų sąraše galvos asmuo suteikė galimybę stoti į klasę. 

Eilė gali būti formuojama naudojant jokios kolekcijos , kuris saugo duomenis, kad, pavyzdžiui, masyvo ar susietą sąrašą. , Kartu su surinkimo saugoti elementus eilėje, mes taip pat turime metodą įtraukti klausimus į eilės galą, kuris yra vadinamas enqueuing o kita pašalinti elementą iš eilės galvą, kuris yra vadinamas dequeuing. Ji dažnai yra naudinga įtraukti kitą būdą grįžti dabartinę ilgis eilėje taip pat metodą, siekiant patikrinti, ar eilė tuščia. Pažvelkime, kaip mes galime įgyvendinti sveikųjų skaičių eilę, C, naudojant įvairių elementų surinkimo. Pirma, mes sukurti struktūrą, vadinamas eilė laikyti savo kintamuosius. Mes naudosime fiksuoto dydžio 0 indekso masyvas sveikųjų skaičių saugoti elementus. Mes taip pat bus kintamasis vadinamas galvą , kuris saugo elemento, kuris šiuo metu yra eilės vadovo indeksą. Trečioji kintamasis, vadinamas ilgio, bus naudojama sekti masyvo elementų skaičių. Kaip alternatyva, Jūs galite apsvarstyti naudojant kintamasis vadinamas uodega , kad rodytų į paskutinę lauko elemento masyve. Prieš mes rašome, bet daugiau kodą, leiskite išbandyti savo dizainą. Pradėkime su Tuščio masyvo ilgio 0, su galva nustatyta į 0. Dabar tegul į eilę 4 vertės - 6, 2, 3, ir 1. Ilgis nuo šiol bus 4, ir galva liks 0. 

Kas atsitiks, jei mes dequeue vertę? Mes sumažinti ilgis 3, galvą į 1, ir grąžinti reikšmę 6. Kad kodas gali atrodyti taip. Čia mes turime dequeue funkciją, kuris trunka žymiklį į eilę - Q - ir žymiklį į elementą, kuris yra tipas int. Pirmiausia mes patikrinti ilgis eilėje, įsitikinkite, kad tai daugiau nei 0, siekiant užtikrinti, kad yra elementas, į kurį dequeued. Tada mes žiūrime į elementų masyve, galvos padėties, ir nustatykite elemento vertę toje vietoje vertė. Tada mes pakeisime galvą į kitą indeksas % Pajėgumų. Mes tada sumažinti eilės ilgis 1. Galiausiai, mes grįžti tiesa, nurodyti, kad dequeue buvo sėkmingas. , Jei mes dequeue dar kartą, ilgis bus 2, vadovas taip pat taps 2, ir grąžina vertė bus 2. 

Kas atsitiks, jei mes į eilę kitą vertę pvz 7? Kaip mes buvome į eilės galą, mums reikės, į kuriuos vyniojami aplink ir laikyti elementą 0 masyvo vertę. Matematiškai tai galima pavaizduoti pridedant ilgį galvos indeksas modulius, naudojant eilės pajėgumus ir atlikti. Čia, kad 2 +2, o tai yra 4% 4, kuris yra 0. Pavertus šią idėją koduoti, mes turime šią funkciją. Čia mes matome, kad į eilę funkciją, kuris trunka žymiklį į eilę - Q - ir trunka būti enqueued elementas, kuris yra sveikasis skaičius. Mums kitą kartą įsitikinkite, kad eilėje pajėgumas vis dar yra didesnis nei dabartinio ilgio eilės. Be to, mes saugome elementų masyvo elementas indekso, kuris yra nustatomas pagal galvos + ilgis% eilėje talpa. Mes tada padidinti ilgio eilės į 1, ir tada grįžti tiesa rodo, kad į eilę funkcija buvo sėkmingas. 

Be to, mes minėtų dviejų funkcijų, yra dvi papildomos funkcijos. Pirmasis yra funkcija isEmpty, , kuris trunka žymeklį į eilę ir tikrina, kad ilgis yra 0. Antrasis yra ilgis, funkcija, , kuri taip pat atsižvelgiama žymiklį į eilę ir grąžina dabartinį ilgis nuo struct. Ši trumpa parodė vieną galimybę įgyvendinti eilę. Vienas iš šio įgyvendinimo apribojimų yra tai, kad eilė turi nustatytą maksimalų dydį. Jei mes stengiamės pridėti daugiau elementų, nei eilė gali turėti, mums gali reikėti prašymą ignoruoti ir upuść elementą, arba mes galime nori grįžti šiek tiek klaidų. Naudojant susietą sąrašą, o ne masyvo būtų lengviau dinamiškai dydžio eilės. Tačiau, kadangi mes ne turėti tiesioginę prieigą prie susietą sąrašo elementų, jei mes neturime sekti uodegos, gauti iki galo, kiekvieną kartą, mes turėtume nuskaityti visą susietą sąrašą. Mes taip pat galėtų apsvarstyti galimybę naudoti kitą duomenų tipą, masyvo, pavyzdžiui kaip structs, sukurti daugiau sudėtingų elementų eiles. Mintys atgal mūsų klasės waitlist pavyzdys, šios struktūros galėtų atstovauti atskirus studentus. 

Mano vardas yra Chris Gerber, ir tai yra CS50. [CS50.TV] Ir grįžta -> One More Time. Ir grįžti tiesa, kad rodo, kad eilė buvo sėkmingas. -% Eilėje talpa - Jis bus įdomus redaguoti. [Juokas]