KEVIN Schmid: Weithiau, wrth adeiladu rhaglen, efallai y byddwch am i ddefnyddio strwythur data a elwir fel geiriadur. Geiriadur allweddi mapiau, sy'n cael eu llinynnau fel arfer, i werthoedd, ints, chars, pwyntydd i ryw gwrthrych, beth bynnag yr ydym ei eisiau. Mae'n union fel geiriaduron cyffredin geiriau sy'n map trwy diffiniadau. 

Geiriaduron rhoi i ni y gallu i storio gwybodaeth gysylltiedig gyda rhywbeth ac yn edrych i fyny yn ddiweddarach. Felly, sut rydym yn mewn gwirionedd yn gweithredu geiriadur mewn, dyweder, C cod y gallwn defnyddio yn un o'n rhaglenni? Wel, mae yna lawer o ffyrdd y gallem weithredu geiriadur. 

Ar gyfer un, gallem ddefnyddio amrywiaeth ein bod yn ddeinamig newid maint neu gallem ddefnyddio rhestr gysylltiedig, bwrdd hash neu goeden deuaidd. Ond beth bynnag yr ydym yn dewis, dylem fod yn ymwybodol o'r effeithlonrwydd ac perfformiad y gweithredu. Dylem feddwl am yr algorithm a ddefnyddir i fewnosod ac yn edrych eitemau i fyny i mewn ein strwythur data. 

Am y tro, gadewch i ni gymryd yn ganiataol ein bod yn am ddefnyddio llinynnau fel allweddi. Gadewch i ni siarad am un posibilrwydd, strwythur data a elwir yn trie. Felly dyma cynrychiolaeth weledol o trie. 

Fel y mae'r llun yn awgrymu, yn trie yn strwythur data coeden gyda nodau cysylltu â'i gilydd. Rydym yn gweld fod yna clir gwreiddyn nod gyda rhai cysylltiadau yn ymestyn i nodau eraill. Ond beth mae pob nod yn ei gynnwys? Os byddwn yn cymryd yn ganiataol ein bod yn storio allweddi gyda chymeriadau yr wyddor yn unig, a nid ydym yn poeni am gyfalafu, dyma diffiniad o nod y yn ddigon. 

Mae gwrthrych y mae ei fath yn strwythur Mae gan nod dwy ran a elwir data a phlant. Rydym wedi gadael y rhan data fel sylw i gael ei ddisodli gan elfen datganiad pan fydd nod strwythur yn hymgorffori mewn rhaglen C. Efallai y bydd y rhan data o nod fod yn Gwerth boolean i nodi p'un a nid yw'r nod yn cynrychioli cwblhau allwedd geiriadur neu gallai fod yn llinyn cynrychioli'r diffiniad gair yn y geiriadur. 

Byddwn yn defnyddio'r wyneb hapus i nodi pan fydd data yn bresennol mewn nod. Mae 26 o elfennau yn ein plant amrywiaeth, un mynegai bob cymeriad yr wyddor. Cawn weld arwyddocâd o hyn yn fuan. 

Gadewch i ni gael golwg agosach o'r nod gwraidd yn ein diagram, sydd heb unrhyw ddata gysylltiedig ag ef, fel y nodir gan y absenoldeb yr wyneb sy'n gwenu yn y cyfran data. Mae'r saethau yn ymestyn o rannau o yr amrywiaeth plant yn cynrychioli'r di-nod awgrymiadau i nodau eraill. Er enghraifft, mae'r saeth yn ymestyn o ail elfen blant cynrychioli'r llythyr B mewn cywair geiriadur. Ac yn y diagram mwy o faint rydym yn labelu 'i ag a B. 

Noder bod yn y diagram mawr, pan fyddwn yn tynnu pwyntydd i nod arall, mae'n Nid yw o bwys os yw'r pen saeth yn cyfarfod y nod eraill. Mae ein trie geiriadur sampl yn cynnwys dau air, hynny a chwyddo. Gadewch i ni gerdded trwy enghraifft o edrych i fyny data ar gyfer allwedd. 

Gadewch i ni dybio ein bod yn awyddus i edrych ar y cyfatebol gwerth ar gyfer y bath allweddol. Byddwn yn dechrau ein golwg i fyny yn y nôd gwraidd. Yna, byddwn yn cymryd y llythyr cyntaf ein allweddol, B, ac yn dod o hyd i'r cyfatebol gweld yn ein amrywiaeth plant. Sylwch fod yna yn union 26 o smotiau yn yr arae, un ar gyfer pob llythyren o'r wyddor. A byddwn yn cael y smotiau yn cynrychioli llythrennau'r wyddor mewn trefn. 

Byddwn yn edrych ar yr ail mynegai yna, mynegai un, ar gyfer B. Yn gyffredinol, os ydym gael rhywfaint o wyddor gymeriad C rydym Gallai benderfynu ar y fan a'r lle cyfatebol yn yr arae plant yn defnyddio cyfrifiad fel hyn. Gallem fod wedi defnyddio blant mwy amrywiaeth os ydym am gynnig edrych i fyny o allweddi gydag ystod ehangach o gymeriadau, megis y cyfan Cymeriad ASCII a osodwyd. 

Yn yr achos hwn, y pwyntydd yn ein amrywiaeth plant yn Nid yw mynegai un yn null. Felly, byddwn yn parhau yn edrych i fyny y bath allweddol. Os ydym erioed wedi dod ar draws pwyntydd null yn y fan a'r lle priodol yn y plant amrywiaeth wrth i ni gerdded trwy'r nodau, Yna, bydd rhaid i ni ddweud ein bod yn Ni allai ddod o hyd i unrhyw beth am y allweddol. 

Yn awr, byddwn yn cymryd yr ail lythyr o ein allweddol, A, ac yn parhau yn dilyn awgrymiadau yn y ffordd hon nes i ni cyrraedd diwedd ein allweddol. Os byddwn yn cyrraedd diwedd y allweddol heb daro unrhyw dod i ben marw, awgrymiadau null, fel sy'n digwydd yma, yna dim ond rhaid i wirio un peth arall. Yn allweddol hwn mewn gwirionedd yn yn y geiriadur? 

Os felly, dylem ddod o hyd i werth, yn dda a gwenu icon wyneb yn ein diagram lle y gair yn dod i ben. Os oes rhywbeth arall storio gyda y data, yna gallwn ddychwelyd. Er enghraifft, nid yw'r sw allweddol yn y geiriadur, er y gallem gael cyrraedd diwedd allwedd hon heb erioed taro pwyntydd null, er ein bod ailadrodd drwy'r trie. 

Os byddwn yn ceisio edrych ar y bath allweddol, y ail i mynegai array nod llynedd, sy'n cyfateb i'r llythyren H, byddai wedi cynnal pwyntydd null. Felly nid bath yn y geiriadur. Ac felly mae trie yn unigryw gan fod yr allweddi byth yn cael eu storio yn benodol yn strwythur data. Felly sut rydym yn rhoi rhywbeth i mewn i trie? 

Gadewch i mewnosoder y allweddol sw yn ein trie. Cofiwch fod wyneb hapus mewn nod Gallai ohebu yn cod i syml Gwerth boolaidd i ddangos bod sw yn y geiriadur neu y gallai yn cyfateb i gael rhagor o wybodaeth ein bod yn yn dymuno cysylltu â sw allweddol, fel y diffiniad o'r gair neu rywbeth arall. Mewn rhai ffyrdd, mae'r broses i fewnosod rhywbeth i mewn i trie yn debyg i edrych i fyny rhywbeth mewn trie. 

Byddwn yn dechrau gyda'r nod gwraidd eto, pwyntiau canlynol yn cyfateb i y llythrennau ein allweddol. Yn ffodus, roeddem yn gallu dilyn awgrymiadau yr holl ffordd nes i ni gyrraedd y diwedd y cyfnod allweddol. Gan fod sw yn rhagddodiad o'r gair chwyddo, sy'n aelod o'r geiriadur, nid oes angen i ni dyrannu unrhyw nodau newydd. 

Gallwn addasu'r nod i ddangos bod y llwybr o gymeriadau yn arwain at mae'n cynrychioli allweddol yn ein geiriadur. Yn awr, gadewch i ni geisio gosod y BATH allweddol i mewn i'r trie. Byddwn yn dechrau ar y nod gwraidd a dilyn awgrymiadau eto. Ond yn y sefyllfa hon, rydym yn taro marw ben cyn ein bod yn gallu cyrraedd y diwedd y cyfnod allweddol. Yn awr, bydd angen i ni ddyrannu rhywfaint newydd Bydd angen i nodau i ddyrannu un newydd nod ar gyfer bob un sy'n parhau llythyr o'n allweddol. 

Yn yr achos hwn, rydym yn unig mae angen i ddyrannu un nod newydd. Yna, bydd angen i ni wneud y mynegai H cyfeirio at y nod newydd. Unwaith eto, gallwn addasu'r nod i yn dangos bod y llwybr o gymeriadau gan arwain at ei fod yn cynrychioli allweddol yn ein geiriadur. Gadewch i resymu am y asymptotic cymhlethdod ein gweithdrefnau ar gyfer y rhain dau gweithrediadau. 

Rydym yn sylwi bod yn y ddau achos y nifer o'r camau ein algorithm gymerodd ei gymesur â nifer y llythyrau yn y gair allweddol. Mae hynny'n iawn. Pan fyddwch am i chwilio am air mewn trie 'ch jyst angen i chi ailadrodd drwy llythyrau o un i un nes i chi naill ai cyrraedd diwedd y gair neu'r taro pen marw yn y trie. 

A phan fyddwch yn dymuno mewnosod allweddol gwerth pâr i mewn i trie gan ddefnyddio'r weithdrefn buom yn ei drafod, yr achos gwaethaf bydd rhaid i chi ddyrannu nod newydd ar gyfer pob llythyren. A byddwn yn cymryd yn ganiataol dyraniad hwnnw yn weithrediad amser cyson. Felly, os ydym yn tybio bod hyd allweddol yw ffinio gan cyson sefydlog, yn mewnosod ac yn edrych i fyny yn gyson gweithrediadau amser am trie. 

Os nad ydym yn gwneud y dybiaeth hon y hyd allweddol wedi'i ffinio gan sefydlog gyson, yna mewnosod ac yn edrych i fyny, yn yr achos gwaethaf, yn cael eu llinellol yn y hyd y allweddol. Sylwch fod y nifer o eitemau eu storio yn y trie nid yw'n effeithio ar y golwg i fyny neu amser fewnosod. Dim ond ei heffeithio gan y hyd y allweddol. 

Ar y llaw arall, gan ychwanegu cofnodion at, dyweder, tabl hash yn tueddu i wneud yn y dyfodol yn edrych i fyny yn arafach. Er y gall hyn ymddangos yn apelio ar y dechrau, dylem gadw mewn cof bod y Nid yw cymhlethdod asymptotic ffafriol yn yn golygu bod yn ymarferol mae'r data strwythur o reidrwydd y tu hwnt i waradwydd. Rhaid inni hefyd ystyried bod i storio gair mewn trie ei angen arnom, yn y gwaethaf achos, mae nifer o nodau cyfrannol i hyd y gair ei hun. 

Ceisiau yn tueddu i ddefnyddio llawer o le. Dyna yn wahanol i tabl hash, lle mai dim ond angen un nod newydd i ni storio rhywfaint pâr o werth allweddol. Nawr, unwaith eto mewn theori, gofod mawr Nid yw yfed yn ymddangos fel mawr delio, yn enwedig gan fod modern gyfrifiaduron gigabeit a gigabeit o gof. Ond mae'n troi allan bod gennym i chi boeni am y defnydd cof a sefydliad er mwyn perfformiad, gan gyfrifiaduron modern fecanweithiau ar waith o dan y chwfl i gyflymu mynediad cof. 

Ond dulliau hyn yn gweithio orau pan mynedfeydd cof yn cael eu gwneud yn gryno rhanbarthau neu ardaloedd. A gallai y nodau o trie yn byw yn unrhyw le yn y domen. Ond mae'r rhain yn masnach-offs y mae'n rhaid inni eu hystyried. 

Cofiwch fod, wrth ddewis data strwythur ar gyfer tasg benodol, rydym yn Dylai feddwl am ba fath o gweithrediadau angen i'r strwythur data i cymorth a faint perfformiad pob un o'r rhai a materion gweithrediadau i ni. Gall y rhain gweithrediadau hyd yn oed ymestyn y tu hwnt i edrych sylfaenol i fyny a gosod. Gadewch i ni dybio ein bod yn awyddus i weithredu math ymarferoldeb auto-gwblhau, mae llawer fel peiriant chwilio Google yn ei wneud. Hynny yw, dychwelyd yr holl allweddi a a allai fod gwerthoedd sy'n cael rhagddodiad penodol. 

Mae trie yn unigryw ddefnyddiol gyfer y gwaith hwn. Mae'n syml i ailadrodd drwy y trie ar gyfer pob cymeriad y rhagddodiad. Yn union fel llawdriniaeth yn edrych i fyny, gallem ddilyn awgrymiadau cymeriad drwy gymeriad. Yna, pan fyddwn yn cyrraedd ar ddiwedd y rhagddodiad, gallem ailadrodd drwy'r rhan sy'n weddill o'r strwythur data gan fod unrhyw o'r allweddi y tu hwnt i y pwynt hwn yn cael y rhagddodiad. 

Mae hefyd yn hawdd i gael y rhestr hon yn nhrefn yr wyddor ers y elfennau o'r array plant yn cael eu harchebu yn nhrefn yr wyddor. Felly, gobeithio y byddwch yn ystyried rhoi ceisio cais. Rwy'n Kevin Schmid, ac mae hyn yn CS50. 

Ah, mae hyn yn ddechrau y dirywiad. Mae'n ddrwg gen i. Mae'n ddrwg gennym. Mae'n ddrwg gennym. Mae'n ddrwg gennym. 

Streic pedwar. Rwyf allan. Mae'n ddrwg gennym. Mae'n ddrwg gennym. Mae'n ddrwg gennym. Mae'n ddrwg gennym ar gyfer gwneud y person sy'n wedi i olygu hyn yn mynd crazy. 

Mae'n ddrwg gennym. Mae'n ddrwg gennym. Mae'n ddrwg gennym. Mae'n ddrwg gennym. 

SIARADWR 1: Da iawn. Mae hynny'n ei wneud yn dda iawn.