કેપી સ્ચમિડ: ક્યારેક, બનાવી રહ્યા હોય એક કાર્યક્રમ, તમે ઉપયોગ કરવા માંગો છો શકે એક એક શબ્દકોશ તરીકે ઓળખાય માહિતી બંધારણ. છે, કે જે શબ્દકોશ નકશા કી, સામાન્ય રીતે શબ્દમાળાઓ, કિંમતો માટે, ints, અક્ષરો, અમુક પદાર્થ માટે નિર્દેશક, અમે જે કરવા માંગો છો. તે માત્ર સામાન્ય શબ્દકોશો જેવું છે વ્યાખ્યાઓ એવી નકશો શબ્દો. 

શબ્દકોશો પાંચ મદદ મળે છે પાસવર્ડ વાપરવા ક્ષમતા કંઈક સાથે સંકળાયેલ અને બાદમાં તે જુઓ. તેથી અમે કેવી રીતે વાસ્તવમાં અમલમાં છે એક સી કોડ કહે છે, માં શબ્દકોશ કે અમે કરી શકો છો અમારા કાર્યક્રમો ઉપયોગ? વેલ, ઘણી બધી રીતે હોય છે કે અમે એક શબ્દકોશ અમલ કરી શકે છે. 

એક, અમે એક એરે ઉપયોગ કરી શકે છે કે અમે ગતિશીલ રીતે ફરીથી કદ અથવા આપણે એક ઉપયોગ કરી શકે છે સંલગ્ન યાદી, હેશ કોષ્ટક અથવા દ્વિસંગી વૃક્ષ. પરંતુ અમે પસંદ ગમે, અમે જોઈએ કાર્યક્ષમતા માઇન્ડફુલ અને અમલીકરણ કામગીરી. અમે ઉપયોગ અલગોરિધમ અંગે વિચારવું જોઇએ દાખલ કરો અને માં વસ્તુઓ જોવા માટે અમારી માહિતી માળખું. 

હવે માટે, ચાલો કે આપણે એમ માની લઈએ દો કીઓ તરીકે શબ્દમાળાઓ ઉપયોગ કરવા માંગો છો. માતાનો એક શક્યતા વિશે વાત કરો, એ માહિતી બંધારણ એક trie છે. અહીં એક દ્રશ્ય રજૂઆત છે એક trie છે. 

ચિત્ર, એક trie સૂચવે છે સાથે વૃક્ષ માહિતી માળખું છે ગાંઠો સાથે કડી થયેલ છે. અમે રુટ સ્પષ્ટ છે તે જુઓ કેટલીક કડીઓ સુધી વિસ્તૃત સાથે નોડ અન્ય ગાંઠો. પરંતુ દરેક નોડને કયા ધરાવે છે? આપણે કી સ્ટોર કરી રહ્યાં ધારે તો માત્ર આલ્ફાબેટીક અક્ષરો, અને સાથે અમે કેપિટલાઈઝેશન વિશે પડી નથી, અહીં નોડ એક વ્યાખ્યા છે કે પૂરતો છે. 

પ્રકાર જેની એક પદાર્થ સ્ટ્રક્ટ છે નોડ બે ભાગો છે માહિતી અને બાળકો છે. અમે એક ટિપ્પણી તરીકે માહિતી ભાગ છોડી દીધું છે એક ઘટક દ્વારા બદલાશે સ્ટ્રક્ટ નોડ છે ત્યારે જાહેરાત એક સી કાર્યક્રમ સમાવેશ કર્યો છે. નોડ ની માહિતી ભાગ એક હોઈ શકે છે સૂચવવા માટે બુલિયન કિંમત કે નથી નોડ પૂર્ણ રજૂ એક શબ્દકોશ કીનું અથવા તે હોઈ શકે છે વ્યાખ્યા રજૂ શબ્દમાળા શબ્દકોશમાંનાં એક શબ્દ. 

અમે તે દર્શાવવા માટે હસતો ચહેરો ઉપયોગ કરશો માહિતી નોડ માં હાજર હોય. માં 26 તત્વો છે અમારા બાળકો એરે, માત્ર એક ઇન્ડેક્સ વર્ણમાળાનો અક્ષર દીઠ. અમે મહત્વ જોશો ટૂંક સમયમાં આ કુલ. 

માતાનો રુટ નોડ નજીકથી દૃશ્ય જોવા દો અમારા આકૃતિ માં, જે કોઈ માહિતી છે આ દ્વારા સૂચવાયેલ, એ સાથે સંકળાયેલ ધ હૂએ હસતો ચહેરો ગેરહાજરીમાં માહિતી ભાગ. ના ભાગો ફેલાયેલ આ તીર બાળકો એરે બિન નોડ પ્રતિનિધિત્વ અન્ય ગાંઠો પોઇન્ટર. ઉદાહરણ તરીકે, તીર ફેલાયેલ બાળકો ના બીજા તત્વ પત્ર બી રજૂ એક શબ્દકોશ કી માં. અને મોટા આકૃતિ માં અમે બી સાથે લેબલ 

, મોટા આકૃતિ માં નોંધ કરો કે જ્યારે અમે અન્ય નોડ માટે નિર્દેશક ડ્રો, તે તો કોઈ વાંધો નથી કે જ્યાં ARROWHEAD અન્ય નોડ મળે છે. અમારા નમૂના શબ્દકોશ trie સમાવે બે શબ્દો, અને ઝૂમ. માતાનો એક ઉદાહરણ લઈ જવામાં દો કી માટે માહિતી શોધી. 

અમે જોવા માગતા હતા ધારો પાંચ કી સ્નાન માટે કિંમત અનુલક્ષીને. અમે અમારા દેખાવ શરૂ કરીશું રુટ નોડ. પછી અમે અમારી પ્રથમ અક્ષર લેવા પડશે , કી બી, અને લાગતાવળગતા શોધવા અમારા બાળકો એરે શોધવામાં. બરાબર 26 ફોલ્લીઓ છે નોંધ કરો કે એરે, દરેક અક્ષર માટે એક મૂળાક્ષર. અને આપણે સ્થળો પ્રતિનિધિત્વ પડશે ક્રમમાં મૂળાક્ષર અક્ષરો. 

અમે પછી બીજા ઇન્ડેક્સ જોવા મળશે સામાન્ય રીતે બી માટે ઇન્ડેક્સ એક છે, તો કેટલાક વર્ણમાળાનો અક્ષર સી અમે તે સંબંધિત સ્થળ નક્કી કરી શકે મદદથી બાળકો એરે આ જેવી ગણતરી. અમે એક મોટા બાળકો ઉપયોગ કરી શકે અમે દેખાવ અપ ઓફર કરવા માગે છે એરે જો અક્ષરો મોટા વિસ્તારની સાથે કીઓ, જેમ કે સમગ્ર તરીકે તે ASCII અક્ષર સુયોજિત કરો. 

આ કિસ્સામાં, આ નિર્દેશક અમારા બાળકો એરે પર ઈન્ડેક્સ એક નલ નથી. તેથી અમે જોઈ ચાલુ રાખીશું કી સ્નાન છે. અમે ક્યારેય નલ નિર્દેશક આવી તો બાળકો માં યોગ્ય સ્થળે એરે અમે ગાંઠો કાપવામાં જ્યારે, પછી અમે તે અમે કહીએ છીએ પડશે તે કી માટે કંઈ મળી શકે છે. 

હવે, અમે બીજા પત્ર લેવા પડશે અમારા કી, એ, અને ચાલુ રાખો નીચેના આ રીતે પોઇન્ટર અમે સુધી અમારા કી ઓવરને પહોંચે છે. અમે વગર કીનું પુર્ણ કરે તો કોઈપણ મૃત અંત હિટ નલ પોઇન્ટર, આ કેસ અહીં છે, તો પછી અમે માત્ર વધુ એક વસ્તુ તપાસો. આ કી છે ખરેખર શબ્દકોશમાંનાં? 

જો એમ હોય તો, અમે સારી રીતે, નીચેની કોડ શોધવા જોઈએ અમારા આકૃતિ માં હસતો ચહેરો ચિહ્ન જ્યાં શબ્દ અંત થાય છે. સાથે સંગ્રહ બીજું કંઈક છે તો ડેટા, પછી અમે તેને પાછા આવી શકો છો. ઉદાહરણ તરીકે, કી ઝૂ નથી અમે કરી શકે છે, તેમ છતાં શબ્દકોશ, ક્યારેય વગર આ કીનો અંતે પહોંચી , એક નલ નિર્દેશક હિટ જ્યારે અમે આ trie દ્વારા ફરી વળવું. 

અમે, કી સ્નાન જોવા પ્રયાસ કર્યો, તો આ છેલ્લા નોડ એરે ઇન્ડેક્સમાં બીજું, , અક્ષર એચ માટે કરશે અનુરૂપ એક નલ નિર્દેશક રાખવામાં આવ્યા છે. તેથી સ્નાન શબ્દકોશમાંનાં નથી. અને તેથી એક trie કે કીઓ અનન્ય છે બાહ્ય રીતે સંગ્રહિત ક્યારેય થતો નથી ડેટા માળખું. તેથી અમે કેવી રીતે કંઈક દાખલ કરો એક trie માં? 

માતાનો કી દાખલ કરો અમારા trie માં પ્રાણી સંગ્રહાલય. યાદ રાખો કે એક ગાંઠ પર એક હસતો ચહેરો સરળ માટે કોડમાં અનુલક્ષે શકે કે ઝૂ સૂચવવા માટે બુલિયન કિંમત શબ્દકોશમાંનાં છે અથવા તે કરી શકે વધુ માહિતી માટે પત્રવ્યવહાર કે અમે કી ઝૂ સાથે સંગત કરવા માંગો છો, આ વ્યાખ્યા જેવી શબ્દ અથવા કંઈક બીજું. કેટલીક રીતે, આ પ્રક્રિયામાં સામેલ કરવા એક trie માં કંઈક જેવું જ છે એક trie માં કંઈક જોઈ. 

અમે ફરી રુટ નોડ સાથે શરૂ કરી શકશો નીચેના પોઇન્ટર અનુલક્ષીને અમારા કીનું અક્ષરો. સદભાગ્યે, અમે પોઇન્ટર અનુસરવા સક્ષમ હતા અમે પહોંચી ત્યાં સુધી બધી રીતે કીનું અંત થાય છે. ઝૂ જો શબ્દના આ ઉપસર્ગ છે આ સભ્ય છે કે જે ઝૂમ, શબ્દકોશ, અમે જરૂર નથી કોઈપણ નવા ગાંઠો ફાળવી. 

અમે દર્શાવવા માટે નોડ ફોન્ટને કે માટે અગ્રણી અક્ષરો પાથ તે અમારા શબ્દકોશ માં કી રજૂ કરે છે. હવે, દાખલ પ્રયાસ કરો આ આ trie માં કી સ્નાન કરે છે. અમે રુટ નોડ શરૂ કરી શકશો અને ફરીથી પોઇન્ટર અનુસરો. પરંતુ આ સ્થિતિમાં, અમે એક મૃત હિટ અમે મળી તે પહેલા અંત કી અંત થાય છે. હવે, અમે કેટલાક નવા ફાળવણી કરવાની જરૂર પડશે ગાંઠો એક નવી ફાળવણી કરવાની જરૂર પડશે દરેક બાકીના માટે નોડ અમારા કી પત્ર. 

આ કિસ્સામાં, અમે માત્ર જરૂર એક નવા નોડ ફાળવી. પછી અમે એચ અનુક્રમણિકા બનાવવા માટે જરૂર પડશે આ નવા નોડ સંદર્ભ આપે છે. ફરી એકવાર, અમે નોડ ફોન્ટને સૂચવે છે કે અક્ષરો પાથ તે માટે અગ્રણી એક રજૂ કરે છે અમારા શબ્દકોશ કી. ચાલો અનંત સ્પર્શી વિશે કારણ દો આ માટે અમારા કાર્યવાહી જટિલતા બે ઓપરેશન. 

અમે નોંધ્યું છે કે બંને કિસ્સાઓમાં સંખ્યા અમારી અલ્ગોરિધમનો હતી લેતા શીખશે ની સંખ્યાના પ્રમાણમાં મુખ્ય શબ્દ અક્ષરો. તે સાચું છે. તમે એક શબ્દ લુકઅપ માંગો છો trie તમે માત્ર દ્વારા ભારપૂર્વક કહેવું છે જરૂર અક્ષરો એક પછી એક તમે ત્યાં સુધી ક્યાં આ શબ્દ ઓવરને અંતે અથવા પહોંચે આ trie એક મૃત ઓવરને નહીં. 

અને તમે એક કી દાખલ કરવા માગતી હોય મદદથી એક trie માં કિંમત જોડી પ્રક્રિયા અમે, સૌથી ખરાબ કિસ્સામાં ચર્ચા જો તમે નવી નોડ ફાળવણી હશે દરેક અક્ષર માટે. અને અમે તે ફાળવણી ધારી પડશે સતત સમય ઓપરેશન ધરાવે છે. અમે કી લંબાઈ કે ધારે તેથી જો ચોક્કસ સતત, બંને દ્વારા ઘેરાયેલો નિવેશ અને જુઓ સતત છે એક trie માટે સમય કામગીરી. 

અમે આ ધારણા ન હોય તો કે કી લંબાઈ નિશ્ચિત દ્વારા ઘેરાયેલું છે સતત, પછી નિવેશ અને જુઓ, સૌથી ખરાબ કિસ્સામાં, માં રેખીય છે કી લંબાઈ. વસ્તુઓની સંખ્યા સંગ્રહ નોંધ કરો કે આ trie માં દેખાવ ઉપર અસર કરતું નથી અથવા દાખલ સમય. તે માત્ર ત્યારે જ અસર છે કી લંબાઈ. 

તેનાથી વિપરીત કહે છે, માટે પ્રવેશો ઉમેરી રહ્યા છે, હેશ કોષ્ટક બનાવવા માટે કરે છે ભવિષ્યમાં ધીમી જુઓ. આ પ્રથમ અપીલ સાઉન્ડ, શકે છે અમે ધ્યાનમાં રાખવી જોઈએ કે અનુકૂળ અનંત સ્પર્શી જટિલતા નથી અર્થ એ છે કે વ્યવહારમાં ડેટા માળખું જરૂરી છે ઠપકો બહાર. અમે પણ સંગ્રહવા માટે માને છે કે જ જોઇએ સૌથી ખરાબ અમે જરૂર એક trie, શબ્દ કેસ, ગાંઠો છે પ્રમાણસર શબ્દ જ લંબાઈ છે. 

પ્રયાસો જગ્યા ઘણો ઉપયોગ કરે છે. તે હેશ ટેબલ વિપરીત છે, અમે માત્ર એક નવા નોડ જરૂર છે અમુક કી કિંમતની જોડી સ્ટોર કરે છે. હવે, ફરી સિદ્ધાંત મુજબ, મોટા જગ્યા વપરાશ મોટા જેમ તેમ લાગતું નથી ખાસ કરીને આપવામાં આવે છે, લેનાર આધુનિક કમ્પ્યુટર્સ ગીગાબાઇટ્સ હોય છે અને મેમરી ગીગાબાઇટ્સ. પરંતુ તે અમે હજુ પણ છે કે બહાર કરે છે મેમરી વપરાશ અને ચિંતા ખાતર સંસ્થા કામગીરી, કારણ કે આધુનિક કોમ્પ્યુટર્સ આ હેઠળ જગ્યાએ પદ્ધતિઓ છે મેમરી ઍક્સેસ ઝડપ હૂડ. 

પરંતુ આ પદ્ધતિઓ શ્રેષ્ઠ જ્યારે કામ મેમરી વપરાતી ઘટનાઓ સઘન કરવામાં આવે છે પ્રદેશો અથવા વિસ્તારો. અને એક trie ના ગાંઠો રહેલી શકે કે ઢગલો ગમે ત્યાં. પરંતુ આ વેપાર ન હોય અમે ધ્યાનમાં લેવું જ જોઈએ છે. 

એક માહિતી પસંદગી કરતી વખતે, યાદ રાખો કે ચોક્કસ કાર્ય માટે માળખું, અમે વિશે વિચારો જોઈએ તે પ્રકારના કામગીરી ડેટા માળખું જરૂર છે આધાર અને કેટલી કામગીરી તે દરેક અમારા માટે કામગીરી બાબતો. આ કામગીરી પણ કરી શકે છે માત્ર પછી વિસ્તરેલી મૂળભૂત દેખાવ અને નિવેશ. અમે એક પ્રકારની અમલ કરવા માગે ધારો સ્વતઃપૂર્ણ વિધેય, ખૂબ જેમ Google શોધ એન્જિન કરે છે. તે છે, બધી કીઓ આવો અને સંભવિત મૂલ્યો આપેલ ઉપસર્ગ છે. 

એક trie અનન્ય ઉપયોગી છે આ ક્રિયા માટે. તે દ્વારા ભારપૂર્વક કહેવું છે સરળ છે દરેક પાત્ર માટે trie ઉપસર્ગ. જસ્ટ, એક જોવા જેવી કામગીરી અમે પોઇન્ટર પાલન કરી શકે છે અક્ષર દ્વારા પાત્ર. પછી, અમે અંત આવે ત્યારે ઉપસર્ગ, અમે મારફતે ફરી વળવું શકે આ માહિતી માળખું બાકી વધે કીઓ કોઈપણ બહાર થી આ બિંદુએ ઉપસર્ગ છે. 

આ યાદી મેળવવા માટે પણ સરળ છે કારણ અનુસાર ક્રમમાં આ બાળકો એરે તત્વો મૂળાક્ષરોની આદેશ હોય છે. તેથી આશા છે કે તમે ધ્યાનમાં પડશે આપવા પ્રયાસ કરે છે. હું કેપી સ્ચમિડ છું, અને આ CS50 છે. 

આહ, આ શરૂઆત છે આ ઘટાડો. હું દિલગીર છું. માફ કરશો. માફ કરશો. માફ કરશો. 

ચાર પ્રહાર. હું બહાર છું. માફ કરશો. માફ કરશો. માફ કરશો. વ્યક્તિ બનાવવા માટે માફ કરશો જે આ ઉન્મત્ત જાઓ ફેરફાર કરવા માટે છે. 

માફ કરશો. માફ કરશો. માફ કરશો. માફ કરશો. 

1 વક્તા: સારી રીતે થાય છે. કે ખરેખર સારી રીતે કરવામાં આવી હતી.