KEVIN შმიდი: ზოგჯერ, როდესაც მშენებლობის პროგრამა, დაგვჭირდება გამოიყენოს მონაცემები სტრუქტურა ცნობილია, როგორც ლექსიკონი. ლექსიკონი რუკები გასაღებები, რომლებიც როგორც წესი, strings, რომ ღირებულებები, ints, სიმბოლო, მომცეთ ზოგიერთი ობიექტი, რაც ჩვენ გვინდა. უბრალოდ მოსწონს ჩვეულებრივი ლექსიკონები რომ რუკაზე სიტყვა მეშვეობით განმარტებები. 

ლექსიკონები მოგვაწოდოთ უნარი ინფორმაციის შესანახად უკავშირდება რაღაც და გამოიყურება ის შემდეგ. ასე რომ, თუ ჩვენ რეალურად განახორციელოს ლექსიკონი, ვთქვათ, C კოდი რომ ჩვენ შეგვიძლია გამოყენება ჩვენი პროგრამებს? ისე, არსებობს ბევრი გზა, რომელიც ჩვენ შეგვიძლია განახორციელოს ლექსიკონი. 

ერთი, ჩვენ შეგვიძლია გამოვიყენოთ მასივი, რომ ჩვენ დინამიურად ხელახლა ზომა და ჩვენ შეგვიძლია გამოვიყენოთ დაკავშირებული სიაში, hash table ან ორობითი ხე. მაგრამ რაც ჩვენ ვირჩევთ, ჩვენ უნდა იყოს მავიწყდება ეფექტურობა და შესრულების განხორციელება. ჩვენ უნდა ვიფიქროთ იმაზე ალგორითმი გამოიყენება ჩადეთ და ეძებოთ ნივთები შევიდა ჩვენი მონაცემები სტრუქტურას. 

ახლა, მოდით ვივარაუდოთ, რომ ჩვენ გსურთ გამოიყენოთ სტრიქონები, როგორც გასაღებები. მოდით ვისაუბროთ ერთი შესაძლებლობა, მონაცემები სტრუქტურა მოუწოდა trie. ასე რომ აქ ვიზუალური წარმომადგენლობა საქართველოს trie. 

როგორც სურათზე ჩანს, trie ხე მონაცემები სტრუქტურა კვანძების გაერთიანებულს. ჩვენ ვხედავთ, რომ იქ ნათლად root კვანძის ზოგიერთი ბმულები გაგრძელების სხვა კვანძების. მაგრამ რას თითოეული კვანძის შედგება? თუ დავუშვებთ, რომ ჩვენ შენახვის გასაღებები მხოლოდ ანბანის გმირები და ჩვენ არ აინტერესებს კაპიტალიზაცია, აქ არის განმარტება კვანძში, რომ იქნება საკმარისი. 

ობიექტი, რომლის ტიპის struct კვანძის აქვს ორ ნაწილად ე.წ. მონაცემები და ბავშვები. ჩვენ დაუტოვებიათ მონაცემების ნაწილი, როგორც კომენტარი უნდა შეიცვალოს კომპონენტი დეკლარაცია როდესაც struct კვანძის არის ჩართული C პროგრამა. მონაცემების ნაწილი კვანძის შეიძლება იყოს ლოგიკური მნიშვნელობა მიუთითებს იმაზე, თუ არ კვანძის წარმოადგენს დასრულების საქართველოს ლექსიკონი გასაღები ან ეს შეიძლება იყოს string წარმოადგენს განმარტება სიტყვის ლექსიკონი. 

ჩვენ ვიყენებთ smiley face მიუთითოს როდესაც ალფანუმერული მონაცემების იმყოფება კვანძში. არსებობს 26 ელემენტები ჩვენს ბავშვები მასივი, ერთი მაჩვენებელი ერთ ანბანურ ასოს. ჩვენ დავინახავთ, რა მნიშვნელობა ამ მალე. 

მოდით კიდევ უფრო ახლოს, რომ root node ჩვენი სქემა, რომელსაც არ აქვს მონაცემები მასთან, როგორც მიერ მითითებულ არარსებობის smiley სახე მონაცემები ნაწილი. ისრებით გაგრძელების ნაწილები ბავშვები array წარმოადგენს არასამთავრობო კვანძის მითითებას სხვა კვანძების. მაგალითად, arrow გაგრძელების მეორე ელემენტს ბავშვები წარმოადგენს წერილი B ლექსიკონში გასაღები. და დიდი სქემა ჩვენ წარწერა იგი B. 

გაითვალისწინეთ, რომ დიდი სქემა, როდესაც ჩვენ მიაპყროს მომცეთ სხვა კვანძის, ეს არ აქვს მნიშვნელობა, სადაც arrowhead ხვდება, რომ სხვა კვანძის. ჩვენი ნიმუში ლექსიკონი trie შეიცავს ორი სიტყვა, რომ და ზუმი. მოდით გავლა მაგალითი ეძებს up მონაცემების გასაღები. 

ვარაუდობენ, გვინდოდა ეძებოთ შესაბამისი ღირებულება გასაღები აბანო. ჩვენ დავიწყებთ look up ზე root node. მაშინ ჩვენ პირველ წერილში ჩვენი გასაღები, B, და იპოვოს შესაბამისი რაშია ჩვენი ბავშვები მასივი. გაითვალისწინეთ, რომ არსებობს ზუსტად 26 წერტილებით მასივი, ერთი თითოეული წერილი ანბანი. და გვექნება ლაქების წარმოადგენს წერილები ანბანი მიზნით. 

ჩვენ შევხედოთ მეორე ინდექსი შემდეგ, index ერთი, B. ზოგადად, თუ ჩვენ აქვს გარკვეული ანბანურ ასოს C ჩვენ შეიძლება დადგინდეს შესაბამისი spot ბავშვების მასივი გამოყენებით გაანგარიშება მოსწონს ეს. ჩვენ შეგვეძლო გამოიყენება დიდი ბავშვები array თუ გვინდოდა გთავაზობთ look up of გასაღებები ფართო სპექტრის პერსონაჟები, როგორიცაა მთელი ASCII ხასიათი მითითებული. 

ამ შემთხვევაში, მომცეთ ჩვენი ბავშვები მასივი ზე index ერთი არ null. ასე რომ, ჩვენ გავაგრძელებთ ეძებს up გასაღები აბანო. თუ ჩვენ ოდესმე შეექმნა null მაჩვენებელი დათქმულ ადგილზე ბავშვები array მაშინ, როცა ჩვენ გადიოდა კვანძების, მაშინ ჩვენ უნდა ვთქვათ, რომ ჩვენ ვერაფერი რომ გასაღები. 

ახლა, ჩვენ მიიღოს მეორე წერილი ჩვენი გასაღები, და კვლავაც შემდეგი პოინტერები ამ გზით, სანამ ჩვენ მიაღწიონ ბოლომდე ჩვენი გასაღები. თუ მივაღწევთ ბოლოს გასაღები გარეშე hitting ნებისმიერი მკვდარი მთავრდება, null პოინტერები, როგორც არის საქმე აქ, მაშინ ჩვენ მხოლოდ უნდა შეამოწმოთ კიდევ ერთი რამ. ეს არის გასაღები ფაქტიურად ლექსიკონი? 

თუ ასეა, ჩვენ უნდა ვიპოვოთ ღირებულება, ისევე, smiley face icon ჩვენი სქემა, სადაც სიტყვა მთავრდება. იმ შემთხვევაში, თუ არსებობს რაღაც ინახება მონაცემები, მაშინ ჩვენ შეგვიძლია დაბრუნება. მაგალითად, გასაღები ზოოპარკში არ არის ლექსიკონი, მიუხედავად იმისა, რომ ჩვენ შეგვეძლო მიაღწია ბოლომდე გასაღები გარეშე ოდესმე დარტყმის null მაჩვენებელი, ხოლო ჩვენ iterate მეშვეობით trie. 

იმ შემთხვევაში, თუ ჩვენ შევეცადეთ ეძებოთ გასაღები აბანო, მეორე ბოლო კვანძის მასივი ინდექსი, შესაბამისი წერილი H, რომ გაიმართა null მაჩვენებელი. ასე რომ აბანო არ არის ლექსიკონში. და ასე trie არის უნიკალური, რომ გასაღებები არასოდეს მკაფიოდ ინახება მონაცემთა სტრუქტურას. ასე როგორ უნდა ჩადეთ რამე შევიდა trie? 

მოდით ჩადეთ გასაღები zoo ჩვენს trie. გახსოვდეთ, რომ smiley face ერთი კვანძის შეიძლება შეესაბამებოდეს კოდის მარტივი ლოგიკური მნიშვნელობა მიუთითებს, რომ ზოოპარკში არის ლექსიკონი ან ეს შეიძლება შეესაბამება უფრო მეტი ინფორმაცია, რომელიც ჩვენ სურთ გაერთიანდნენ გასაღები ზოოპარკში, მოსწონს განმარტება სიტყვა ან რაღაც. გარკვეულწილად, პროცესი ჩასასმელად რაღაც შევიდა trie მსგავსი ეძებს up რაღაც trie. 

ჩვენ იწყება root node ერთხელ, შემდეგ მითითებას შესაბამისი წერილები ჩვენი გასაღები. საბედნიეროდ, ჩვენ შევძელით, რომ დაიცვას პოინტერები ყველა გზა, სანამ მივაღწიეთ ბოლოს გასაღები. მას შემდეგ, რაც ზოოპარკი პრეფიქსი სიტყვა zoom, რომელიც წევრი ლექსიკონი, ჩვენ არ უნდა გამოყოფს რაიმე ახალი კვანძების. 

ჩვენ შეგვიძლია ცვლილებები კვანძის მიუთითებს იმაზე, რომ გზა გმირები მიმავალი იგი წარმოადგენს გასაღები ჩვენი ლექსიკონი. ახლა, მოდით ვცდილობთ ჩასმა გასაღები BATH შევიდა trie. ჩვენ იწყება root node და დაიცვას პოინტერები ერთხელ. მაგრამ ამ სიტუაციაში, ჩვენ მოხვდა მკვდარი დასრულდება სანამ ჩვენ შეუძლია მიიღოს ბოლოს გასაღები. ახლა, ჩვენ უნდა გამოყოს გარკვეული ახალი კვანძების უნდა გამოყოს ერთი ახალი კვანძის, თითოეული დარჩენილი წერილი ჩვენი გასაღები. 

ამ შემთხვევაში, ჩვენ უბრალოდ უნდა გამოყოს ერთი ახალი კვანძში. მაშინ ჩვენ უნდა მიიღოს H ინდექსი მინიშნება ამ ახალ კვანძში. კიდევ ერთხელ, ჩვენ შეგვიძლია ცვლილებები კვანძის მიუთითებს, რომ გზა გმირები რასაც იგი წარმოადგენს გასაღები ჩვენი ლექსიკონი. მოდით მიზეზი შესახებ asymptotic სირთულის ჩვენი პროცედურები ამ ორი ოპერაცია. 

შევნიშნავთ, რომ ორივე შემთხვევაში ნომერი ნაბიჯები ჩვენი ალგორითმი აიღო იყო პროპორციული ნომერი წერილები სიტყვით. ეს უფლება. როდესაც გსურთ ეძებოთ სიტყვა trie თქვენ უბრალოდ უნდა iterate მეშვეობით წერილები სათითაოდ სანამ არ ან მიაღწევს ბოლოს სიტყვა ან მოხვდა ჩიხი წელს trie. 

და როდესაც გსურთ ჩადეთ გასაღები ღირებულება წყვილი შევიდა trie გამოყენებით პროცედურა განვიხილეთ, უარეს შემთხვევაში ექნება თქვენ გამოყოფის ახალი კვანძის თითოეული წერილი. და ჩვენ ვივარაუდოთ, რომ განაწილების არის მუდმივი დროს ოპერაცია. ასე რომ, თუ ჩვენ ვივარაუდოთ, რომ გასაღები სიგრძე ესაზღვრება ფიქსირებული მუდმივი, როგორც ჩანართი და ეძებოთ მუდმივი დროის ოპერაციების trie. 

იმ შემთხვევაში, თუ ჩვენ არ მიიღოს ამ მოსაზრებას, რომ გასაღები სიგრძეზე ესაზღვრება ფიქსირებული მუდმივი, მაშინ Insertion და მოუთმენლად up, უარეს შემთხვევაში, მათ წრფივი წელს ხანგრძლივობა გასაღები. გაითვალისწინეთ, რომ ნომერი, საქონლის შენახვა ამ trie არ იმოქმედებს look up ან ჩასმის დროს. ეს მხოლოდ იმოქმედა მიერ ხანგრძლივობა გასაღები. 

პირიქით, დასძინა entries, ვთქვათ, hash table tends რათა მომავალი ეძებოთ ნელა. მიუხედავად იმისა, რომ ეს შეიძლება გასწავლოთ მიმზიდველი, პირველ რიგში, ჩვენ უნდა გვახსოვდეს, რომ ხელსაყრელი asymptotic სირთულის არ იმას, რომ პრაქტიკაში მონაცემები სტრუქტურა აუცილებლად მიღმა reproach. ჩვენ უნდა გავითვალისწინოთ, რომ შესანახად სიტყვა trie ჩვენ გვჭირდება, უარეს შემთხვევაში, რიგი კვანძების პროპორციული სიგრძეზე სიტყვა თავად. 

ლელო ტენდენცია გამოიყენოთ უამრავი სივრცეში. ეს არის ის, განსხვავებით hash მაგიდა, სადაც ჩვენ მხოლოდ უნდა ერთი ახალი კვანძის შესანახად ზოგიერთი გასაღები ღირებულება წყვილი. ახლა, ისევ თეორიულად, დიდი სივრცე მოხმარება არ ჩანს, როგორც დიდი გამკლავება, განსაკუთრებით იმის გათვალისწინებით, რომ თანამედროვე კომპიუტერი აქვს გბ და გიგაბაიტი მეხსიერება. მაგრამ აღმოჩნდება, რომ ჩვენ ჯერ კიდევ გვაქვს ფიქრი მეხსიერების გამოყენების და ორგანიზაციის გულისთვის შესრულება, რადგან თანამედროვე კომპიუტერები აქვს მექანიზმები ფარგლებში hood დააჩქაროს მეხსიერების ხელმისაწვდომობის. 

თუმცა დღეს ეს მექანიზმები იმუშავებს საუკეთესო, როდესაც მეხსიერების წვდომის კეთდება კომპაქტ რეგიონებში და რაიონებში. და კვანძების trie ვერ ცხოვრობენ სადმე, რომ ბევრი. მაგრამ ეს არის ვაჭრობის ღ რომ ჩვენ უნდა განიხილოს. 

გვახსოვდეს, რომ, როდესაც ვირჩევთ მონაცემები სტრუქტურა გარკვეული ამოცანა, ჩვენ უნდა ვიფიქროთ, თუ რა სახის ოპერაციების მონაცემები სტრუქტურა საჭიროებს მხარდაჭერა და რამდენად შესრულება თითოეული იმ ოპერაციების საკითხებში ჩვენთვის. ეს ოპერაციები შეიძლება კი სცილდება მხოლოდ ძირითადი look up და ჩასმა. ვარაუდობენ, გვინდოდა განახორციელოს ერთგვარი ავტო სრული ფუნქციონირება, ბევრი როგორიცაა Google საძიებო აკეთებს. რომ არის, დაბრუნდეს ყველა გასაღებები და პოტენციურად ფასეულობებს, რომელიც აქვს მოცემული პრეფიქსი. 

Trie არის ცალსახად სასარგებლო ეს ოპერაცია. ეს არის პირდაპირი iterate მეშვეობით trie თითოეული ხასიათი პრეფიქსი. ისევე ეძებოთ ოპერაცია, ჩვენ შეგვიძლია დაიცვას პოინტერები ხასიათი ხასიათი. მაშინ, როდესაც ჩვენ მივიდეს ბოლომდე პრეფიქსი, ჩვენ შეგვიძლია iterate მეშვეობით დარჩენილი ნაწილის მონაცემები სტრუქტურა რადგან ნებისმიერ გასაღებები მიღმა ამ ეტაპზე აქვს პრეფიქსი. 

ეს ასევე ადვილია მიიღონ ამ ჩამონათვალი ანბანის მიხედვით წლიდან ელემენტები ბავშვები მასივი უბრძანა ალფავიტის. ასე რომ იმედია თქვენ განიხილოს გაცემას ცდილობს ცდილობენ. მე Kevin შმიდი, და ეს არის CS50. 

Ah, ეს არის დასაწყისი ვარდნა. მე ბოდიში. უკაცრავად. უკაცრავად. უკაცრავად. 

გაფიცვის ოთხ. მე გარეთ. უკაცრავად. უკაცრავად. უკაცრავად. უკაცრავად მიღების პირი, რომელიც უნდა შეცვალონ ამ გიჟები. 

უკაცრავად. უკაცრავად. უკაცრავად. უკაცრავად. 

დინამიკები 1: კარგად გაკეთდეს. ეს ნამდვილად კარგად გაკეთდეს.