டக் LLOYD: எனவே CS50, நாம் மூடப்பட்ட வெவ்வேறு தரவு கட்டமைப்புகள் நிறைய, சரியா? நாம் வரிசைகளின் பார்த்த, மற்றும் இணைக்கப்பட்ட பட்டியல்கள், மற்றும் புல அட்டவணைகள், மற்றும் முயற்சிகளின், அடுக்குகள் மற்றும் வரிசைகளை. நாம் இன்னும் சிறிது கற்றுக்கொள்ள வேண்டும் மரங்கள் மற்றும் குவியல்களின் பற்றி, ஆனால் உண்மையில் இந்த அனைத்து முடிவுக்கு வரை ஒரு தீம் மீது வேறுபாடுகள் இருப்பது. உண்மையில் உள்ளன இந்த நான்கு அடிப்படை யோசனைகளை வகையான வேறு என்று எல்லாம் கீழே கொதிக்க முடியும். வரிசைகள், தொடர்புடைய பட்டியல்கள் புல அட்டவணைகள், மற்றும் முயற்சிகளின். மற்றும் போன்ற நான் அங்கு கூறினார் அவர்கள் மீது வேறுபாடுகள் உள்ளன, ஆனால் இந்த அழகான ஆகிறது மிகவும் சுருக்கமாக போகிறது எல்லாம் நாம் பேச போகிறோம் சி அடிப்படையில் இந்த வர்க்கத்தின் பற்றி ஆனால் எப்படி இந்த வலது, அனைத்து நடவடிக்கை வரை செய்ய? நாம் நன்மை தீமைகள் பற்றி பேசினார் அவர்கள் மீது தனி வீடியோக்கள் உள்ள ஒவ்வொரு, ஆனால் எண்கள் நிறைய இருக்கிறது சுற்றி தூக்கி. பொது நிறைய இருக்கிறது எண்ணங்கள் சுற்றி தூக்கி. முயற்சி மற்றும் திரட்டி நாம் அது ஒரு இடத்தில் ஒரு. எதிராக நன்மை எடையை நாம் தீமைகள், மற்றும் பரிசீலிக்க இது தரவு கட்டமைப்பு வலது தரவு இருக்கலாம் உங்கள் குறிப்பிட்ட சூழ்நிலையில் அமைப்பு, தரவு என்ன வகையான நீங்கள் சேமித்து. நீங்கள் அவசியம் எப்போதும் தேவையில்லை , வேகமான, புகுத்தியது, நீக்கல் பயன்படுத்த ஒரு trie மற்றும் தேடல் நீங்கள் என்றால் உண்மையில் சேர்க்கைக்கு மற்றும் நீக்குதல் பற்றி கவலை இல்லை அதிகம். நீங்கள் விரைவில் சீரற்ற வேண்டும் என்றால் அணுகல், ஒருவேளை ஒரு வரிசை நன்றாக உள்ளது. எனவே அந்த நொதிக்க அனுமதிக்க. நான்கு ஒவ்வொரு பற்றி பேசலாம் தரவு கட்டமைப்புகள் முக்கிய வகையான நாம் பற்றி பேசினார், மற்றும் என்று அவர்கள் நன்றாக இருக்கும் போது தான் பார்க்க, மற்றும் அவர்கள் மிகவும் நல்ல இருக்க வேண்டும். எனவே வரிசைகள் கொண்ட ஆரம்பிப்போம். செருகும் எனவே, அந்த கெட்ட வகையான தான். 

ஒரு வரிசை இறுதியில் செருகும், சரி தான் நாம் சென்று நாம் ஒரு வரிசை கட்டி என்றால். ஆனால் நாம் நுழைக்க வேண்டும் என்றால் நடுவில் உறுப்புகள், செருகும் திரும்ப நினைத்தால் வகையான, நிறைய இருக்கிறது அங்கு உள்ள ஒரு உறுப்பு பொருந்தும் மாற்றுவதால். மற்றும் நாம் சேர்க்க போகிறோம் ஆமெனில் எங்கும் ஆனால் ஒரு வரிசைக்கு இறுதியில், என்று அநேகமாக பெரிய இல்லை. 

இதேபோல், நீக்கல், வரை நாம் இருக்கிறோம் ஒரு வரிசைக்கு இறுதியில் நீக்குதல், ஒருவேளை என்றால் இவ்வளவு பெரிய அல்ல நாங்கள் காலியாக இடைவெளிகளை விட்டு விரும்பவில்லை, இது வழக்கமாக நாங்கள் இல்லை. நாம் ஒரு உறுப்பு நீக்க வேண்டும், மற்றும் பின்னர் வகையான அதை மீண்டும் கதகதப்பான செய்ய. அதனால் கூறுகளை நீக்குவதற்கு ஒரு வரிசை, மேலும் மிக பெரிய இல்லை. 

தேடல், எனினும், நன்றாக இருக்கிறது. நாம் சீரற்ற அணுகல், நிலையான நேர தேடல். நாம் வெறும் ஏழு என்று, நாம், சென்று வரிசை இடமாற்றம் ஏழு. நாம் சென்று கொண்டு, 20 சொல்கிறோம் வரிசை இடமாற்றம் 20. நாம் முழுவதும் மீண்டும் கூறு இல்லை. அந்த அழகான நல்லது. 

அணிகளை மேலும் வரிசைப்படுத்த ஒப்பீட்டளவில் எளிதானது. நாம் ஒரு வரிசையாக்க பற்றி பேசினார் ஒவ்வொரு முறையும் போன்ற தேர்வு வகையான போன்ற வழிமுறை, செருகும் வரிசையாக்கம், குமிழி வரிசையாக்கம், ஒன்றாக்க வகையான, நாங்கள் எப்போதும் அதை செய்ய வரிசைகள் பயன்படுத்தப்படும், வரிசைகள் கொள்ள மிகவும் எளிதாக இருக்கும், ஏனெனில் தரவு கட்டமைப்புகள் உறவினர் வகையான, நாம் இதுவரை பார்த்த. 

அவர்கள் ஒப்பீட்டளவில் சிறிய இருக்கிறோம். கூடுதல் இடத்தை ஒரு நிறைய இல்லை. நீங்கள் சரியாக எவ்வளவு ஒதுக்கி நீங்கள் உங்கள் தரவு நடத்த வேண்டும் என்று, மற்றும் அது மிகவும் அதிகம். எனவே அவர்கள் மிகவும் சிறிய இருக்கிறோம் மற்றும் அந்த வழியில் திறமையான. ஆனால் மற்றொரு எதிர்மறையாக, எனினும், அவர்கள் அளவு சரி என்று ஆகிறது. நாம் எப்படி சரியாக அறிவிக்க வேண்டும் பெரிய நாங்கள் எங்கள் வரிசையில் இருக்க வேண்டும், மற்றும் நாம் மட்டும் அதை ஒரு ஷாட் கிடைக்கும். நாம் வளர அதை சுருக்கி முடியாது. 

நாம் அது வளர அல்லது சுருக்க வேண்டும் என்றால், நாம் ஒரு முற்றிலும் புதிய வரிசை அறிவிக்க வேண்டும், கூறுகள் அனைத்து நகலெடுக்க இரண்டாவது வரிசை முதல் வரிசை. நாம் அந்த தவறாக மதிப்பீடு என்றால் நேரம், நாம் மீண்டும் அதை செய்ய வேண்டும். மிகவும் பெரிய இல்லை. எனவே வரிசைகள் வளைந்து கொடுத்து உறுப்புகள் மாறி எண்கள் வேண்டும். 

ஒரு இணைக்கப்பட்ட பட்டியலில் மூலம், செருகும் அழகான எளிது. நாம் தான் முன் மீது பிசுப்பு. நீக்கல் கூட அழகாக எளிது. நாம் கூறுகள் கண்டுபிடிக்க வேண்டும். என்று சில தேடி உள்ளடக்கியது. 

ஆனால் நீங்கள் உறுப்பு காணப்படவில்லை முறை நீங்கள் என்ன செய்ய வேண்டும், அனைத்து தேடும் ஒரு சுட்டிக்காட்டி மாற்ற ஆகிறது, இது இரண்டு நீங்கள் இருந்தால் ஒரு ஒரு இரட்டை பட்டியலில் இணைக்கப்பட்ட இணைக்கப்பட்ட பட்டியலில், மாறாக பின்னர் நீங்கள் முனை விடுவிக்க முடியும். நீங்கள் மாற்ற வேண்டும் இல்லை சுற்றி எல்லாம். நீங்கள், இரண்டு சுட்டிகள் மாற்ற அதனால் அழகான விரைவு தான். 

தேடல் சரி, என்றாலும் மோசமாக உள்ளது? எங்களுக்கு ஒரு கண்டுபிடிக்க பொருட்டு ஒரு இணைக்கப்பட்ட பட்டியலில் உறுப்பு, என்பதை தனியாகவோ அல்லது இரட்டை, இணைக்கப்பட்ட நாம் அதை தேட ஒருபடி வேண்டும். நாம் ஆரம்பத்தில் தொடங்க வேண்டும் மற்றும் இறுதி நகர்த்த, அல்லது இறுதி நடவடிக்கை மணிக்கு தொடங்கும் தொடக்கத்தில். நாம் இனி சீரற்ற அணுகல் இல்லை. நாங்கள் ஒரு செய்கிறீர்கள் என்றால் எனவே தேடி நிறைய, ஒருவேளை ஒரு இணைக்கப்பட்ட பட்டியலில் இல்லை எங்களுக்கு மிகவும் நல்லது. 

அவர்கள் உண்மையில் தான் இருக்கிறோம் வரிசைப்படுத்த கடினமாக, சரியான? ஒரே வழி நீங்கள் உண்மையில் ஒரு இணைக்கப்பட்ட பட்டியலில் தீர்த்துக்கொள்ள நீங்கள் அதை அமைக்க அதை வரிசைப்படுத்த. ஆனால் நீங்கள் அதை தீர்த்துக்கொள்ள என்றால் கட்டமைக்க, நீங்கள் இனி இருக்கிறீர்கள் இனி விரைவான புகுத்தல் செய்யும். நீங்கள் tacking முன் மீது விஷயங்கள். நீங்கள் கண்டுபிடிக்க வேண்டும் சரியான இடத்தில் அதை வைத்து, பின்னர் உங்கள் செருகும் பற்றி போன்ற மோசமான ஆகிறது ஒரு வரிசைக்கு செருகுவது போன்ற. எனவே தொடர்புடைய பட்டியல்கள் இல்லை தரவை வரிசையாக்கம் மிகவும் நன்றாக. 

அவர்கள் அழகான சிறிய, அளவு வாரியான இருக்கிறோம். இரட்டை சற்று இணைக்கப்பட்ட பட்டியலில் தனித்தனி இணைக்கப்பட்ட பட்டியல்கள் விட பெரிய, இது சற்று பெரியதாக இருக்கும் அணிகளை விட, ஆனால் அது இல்லை வீணாகி இடத்தில் ஒரு பெரிய அளவு. எனவே, விண்வெளி ஒரு பிரீமியம் உள்ளது, ஆனால் ஒரு உண்மையில் தீவிர பிரீமியம், இந்த செல்ல சரியான வழி இருக்க வேண்டும். 

அட்டவணைகள் புல. ஒரு ஹாஷ் அட்டவணை செருகும் மிகவும் நேர்மையானவன். இது ஒரு இரண்டு படி செயல்முறை தான். முதலில் நாம் மூலம் எங்கள் தரவு இயக்க வேண்டும் ஒரு ஹாஷ் சார்பு ஒரு ஹாஷ் குறியீடு பெற, பின்னர் நாம் ஒரு உறுப்பு நுழைக்க என்று ஹாஷ் குறியீடு இடத்தில் ஹாஷ் அட்டவணை. 

இணைக்கப்பட்ட பட்டியலில் ஒத்த நீக்கல், நீங்கள் உறுப்பு கண்டுபிடிக்க முறை எளிதானது. நீங்கள் முதலில் அதை கண்டுபிடிக்க ஆனால் அதை நீக்க போது, நீங்கள் பரிமாறி வேண்டும் சுட்டிகள் ஒரு ஜோடி, நீங்கள் தனி பிணைப்பு பயன்படுத்தி வருகிறோம். நீங்கள் ஆய்வு பயன்படுத்துகிறீர்கள் என்றால், அல்லது நீங்கள் இல்லை என்றால் பயன்படுத்தி அனைத்து பிணைப்பு உங்கள் புல அட்டவணையில், நீக்கல் உண்மையில் மிகவும் எளிது. நீங்கள் செய்ய வேண்டிய அனைத்து புல ஆகிறது தரவு, பின்னர் அந்த இடத்திற்கு போக வைக்கிறது. மற்றும் அனுமானித்து நீங்கள் இல்லை எந்த மோதல்கள் நீங்கள் மிக விரைவில் நீக்க முடியும். 

இப்போது, தேடல் அமைந்துள்ள விஷயங்கள் ஆகிறது இன்னும் கொஞ்சம் சிக்கலான கிடைக்கும். அது நன்றாக சராசரியாக இருக்கிறது தொடர்புடைய பட்டியல்கள் விட. நீங்கள் பிணைப்பு பயன்படுத்துகிறீர்கள் என்றால், நீங்கள் இன்னும் ஒரு இணைக்கப்பட்ட பட்டியலில் இல்லை இது நீங்கள் இன்னும் வேண்டும் என்பதாகும் தேடல் ஒரு இணைக்கப்பட்ட பட்டியலில் கேடு. நீங்கள் எடுத்து வருகிறோம் ஏனெனில் ஆனால் உங்கள் இணைக்கப்பட்ட பட்டியல் மற்றும் 100 அல்லது 1,000 க்கும் மேற்பட்ட அது பிளக்கும் அல்லது n உங்கள் புல அட்டவணையில் உறுப்புகள், நீங்கள் இருக்கிறீர்கள் தொடர்புடைய பட்டியல்கள் அளவு வானளாவிய அனைத்து ஒன்று. அவர்கள் அனைத்து கணிசமாக சிறிய இருக்கிறோம். நீங்கள் n பதிலாக பட்டியல்கள் இணைக்கப்பட்ட அளவு n ஒரு இணைக்கப்பட்ட பட்டியலில். 

எனவே இந்த உண்மையான உலக நிலையான பொதுவாக நாம் எந்த காரணி, சிக்கலான நேரத்தை பற்றி பேச வேண்டாம், அது உண்மையில் இங்கே ஒரு வித்தியாசம். எனவே பார்வை இன்னும் ஒருபடி ஆகிறது நீங்கள் பிணைப்பு பயன்படுத்தி என்றால், தேடல் ஆனால் பட்டியல் நீளம் நீங்கள் மூலம் தேடி ஒப்பீடு மிக, மிக குறுகிய உள்ளது. மீண்டும், வகைப்படுத்தல் உங்கள் என்றால் இங்கே இலக்கு, ஹாஷ் அட்டவணை ஒருவேளை சரியான வழியில் செல்ல முடியாது. வரிசைப்படுத்த என்றால் ஒரு வரிசை பயன்படுத்த நீங்கள் மிகவும் முக்கியம் ஆகும். 

அவர்கள் அளவு வரம்பு இயக்க முடியும். இது ஒரு என்பதை சொல்ல கடினமாக ஹாஷ் அட்டவணை, சிறிய அல்லது பெரிய ஆகிறது அது உண்மையில் சார்ந்தது என்பதால் எவ்வளவு பெரிய உங்கள் ஹாஷ் அட்டவணை உள்ளது. நீங்கள் மட்டும் சேமித்து வேண்டும் போகிறோம் என்றால் உங்கள் புல அட்டவணையில் ஐந்து கூறுகளை, மற்றும் நீங்கள் ஒரு ஹாஷ் அட்டவணை அது 10,000 உறுப்புகள், ஒருவேளை நீங்கள் நிறைய இடம் வீணடிக்காதீர்கள். மாறாக நீங்கள் இருப்பது , மிக சிறிய புல அட்டவணைகள் வேண்டும் ஆனால் சிறிய உங்கள் ஹாஷ் அட்டவணை, பெறுகிறது அந்த தொடர்புடைய பட்டியல்கள் ஒவ்வொரு இனி பெறுகிறார். அதனால் உண்மையில் வரையறுக்க வழி இல்லை சரியாக ஒரு ஹாஷ் அட்டவணை அளவு, ஆனால் அது ஒருவேளை பாதுகாப்பானது இது பொதுவாக, தான் சொல்ல ஒரு இணைக்கப்பட்ட விட பெரிய இருக்க போகிறது அதே தரவு சேமித்து பட்டியல், ஒரு trie விட ஆனால் சிறிய. 

மற்றும் முயற்சிகளின் நான்காவது உள்ளன இந்தக் கட்டமைப்புகளின் என்று நாம் பற்றி பேசுகிறீர்கள். ஒரு trie ஒரு சேர்க்கப்படுகின்றது சிக்கலாக உள்ளது. மாறும் நிறைய இருக்கிறது நினைவக ஒதுக்கீடு, குறிப்பாக தொடக்கத்தில், நீங்கள் கட்ட தொடங்கி நீங்கள் போன்ற. ஆனால் அது தொடர்ந்து நேரம். இது தான் மனித உறுப்பு இங்கே இது தந்திரமான செய்கிறது என்று. பூஜ்ய சுட்டிக்காட்டி எதிர்கொள்ள கொண்ட, malloc, விண்வெளி, சாத்தியமான malloc இடத்தில் அங்கு சென்று அங்கு இருந்து மீண்டும். அச்சுறுத்துவதன் காரணி வகையான மாறும் நினைவக ஒதுக்கீடு சுட்டிகள் அழிக்க தடையாக உள்ளது. ஆனால் நீங்கள் அதை அகற்றப்படும் ஒருமுறை, செருகும் உண்மையில், மிக எளிய வருகிறது அது நிச்சயமாக நிலையான நேரம். 

நீக்கல் எளிதானது. நீங்கள் செய்ய வேண்டிய அனைத்து செல்லவும் ஒரு சுட்டிகள் மற்றும் இலவச முனை ஜோடி, அதனால் நல்ல விஷயம். தேடல் கூட அழகாக வேகமாக உள்ளது. அது மட்டும் அடிப்படையாக உங்கள் தரவு நீளம். உங்கள் தரவு அனைத்தையும் இருந்தால், அதனால் ஐந்து பாத்திரம் சரங்களை, உதாரணமாக, நீங்கள் ஐந்து சேமித்து உங்கள் trie பாத்திரம் சரங்களை, அது மட்டும் ஐந்து படிகள் எடுக்கிறது நீங்கள் தேடும் என்ன கண்டுபிடிக்க. ஐந்து அதனால், ஒரு நிலையான காரணியாக உள்ளது மீண்டும், புகுத்தியது, நீக்கல், மற்றும் தேடல் இங்கே திறம்பட, அனைத்து நிலையான நேரம் உள்ளன. 

மற்றொரு விஷயம் உங்கள் trie உள்ளது உண்மையில் வகையான ஏற்கனவே சரியான, வரிசைப்படுத்தப்பட்ட? நாங்கள் இருக்கிறோம் எப்படி நல்லொழுக்கம் மூலம் சேர்க்கைக்கு உறுப்புகள், கடிதம் மூலம் கடிதம் செல்வதன் மூலம் முக்கிய ஐக்கிய முக்கிய, அல்லது ஐக்கிய, பொதுவாக, உங்கள் trie இருப்பது நிறைவடைகிறது நீங்கள் அதை உருவாக்க வகையான பேசி தீர்க்கப்படும். அது உண்மையில் செய்கிறது உணர்வு வரிசையாக்க பற்றி யோசிக்க அதே வழியில் நாம் யோசிக்க அது வரிசைகள், அல்லது இணைக்கப்பட்ட பட்டியல்கள், அல்லது புல அட்டவணைகள். ஆனால் சில சமயங்களில், உங்கள் நீங்கள் செல்ல போல் trie பிரிக்கப்பட்டுள்ளது. 

எதிர்மறையாக, நிச்சயமாக, என்று ஆகிறது ஒரு trie வேகமாக பெரிய ஆகிறது. ஒவ்வொரு சந்தியிலும் புள்ளியில் இருந்து, நீங்கள் போகலாம் உங்கள் முக்கிய இலக்கங்களைக் கொண்டிருக்கிறது என்றால் உன்னுடைய, நீங்கள் மற்ற 10 இடங்களில் நீங்கள், செல்ல முடியும் ஒவ்வொரு கணு என்று அர்த்தம் தகவல்களை கொண்டுள்ளது தரவு பற்றி நீங்கள் சேமிக்க விரும்பும் அந்த முனை, பிளஸ் 10 சுட்டிகள் மணிக்கு. எந்த CS50, எஸ்டி மீது, 80 பைட்டுகள் ஆகும். எனவே அது குறைந்தது 80 பைட்டுகள் தான் நீங்கள் உருவாக்க என்று ஒவ்வொரு கணு, என்று கூட தரவு எண்ணும் இல்லை. மேலும், உங்கள் முனைகளில் உள்ளன என்றால் அதற்கு பதிலாக இலக்கங்கள் கடிதங்கள், இப்போது நீங்கள் 26 சுட்டிகள் வேண்டும் ஒவ்வொரு இடம் இருந்து. மேலும் 26 முறை 8 ஒருவேளை 200 பைட்டுகள், அல்லது அந்த மாதிரி ஏதாவது. நீங்கள் மூலதனம் வேண்டும் நீங்கள் முடியும் ஸ்மால் நான் இந்த போகிறேன் எங்கே வலது, பார்க்க? உங்கள் முனைகளில் உண்மையில் பெற முடியும் பெரிய, அதனால் trie, தன்னை, ஒட்டுமொத்த, முடியும் கூட, உண்மையில் பெரிய பெற. விண்வெளி ஒரு உயர் உள்ளது என்றால் உங்கள் கணினியில் பிரீமியம், ஒரு trie சரியான வழி இருக்க வேண்டும் கூட அதன் மற்ற நன்மைகள் இருந்தாலும், போக நாடகம் வரும். நான் டக் லாயிட் இருக்கிறேன். இந்த CS50 உள்ளது.