డౌ LLOYD: కాబట్టి CS50 లో, మేము కవర్ చేసిన వివిధ డేటా నిర్మాణాలు చాలా కుడి? మేము శ్రేణుల చూసిన, మరియు లింక్ చేసిన జాబితాలు, మరియు హాష్ పట్టికలు, మరియు ప్రయత్నాలు, స్టాక్స్ మరియు క్యూలు. మేము కూడా కొద్దిగా నేర్చుకోవచ్చు చెట్లు మరియు పోగులు గురించి కానీ నిజంగా ఈ అన్ని కేవలం అంతం అప్ ఒక థీమ్ వైవిధ్యాలు ఉండటం. నిజంగా ఉన్నాయి ఈ నాలుగు ప్రాథమిక ఆలోచనలు రకమైన వేరే ప్రతిదీ డౌన్ కాచు చేయవచ్చు. వ్యూహాలను, అనుసంధాన జాబితాలు హాష్ పట్టికలు, మరియు ప్రయత్నాలు. మరియు నేను అక్కడ చెప్పారు వాటిని వ్యత్యాసాలు ఉన్నాయి, కానీ ఈ అందంగా ఉంది చాలా సంగ్రహించేందుకు అన్నారు ప్రతిదీ మేము మాట్లాడటానికి వెళుతున్న C. పరంగా ఈ తరగతి లో కానీ ఎలా ఈ కుడి, అన్ని కొలత చేయండి? మేము రెండింటికీ గురించి మాట్లాడారు చేసిన వాటిని ప్రత్యేక వీడియోల్లో ప్రతి, కానీ సంఖ్యలు చాలా ఉంది చుట్టూ విసిరిన విధానం. సాధారణ చాలా ఉంది ఆలోచనలు చుట్టూ విసిరిన విధానం. యొక్క ప్రయత్నించండి మరియు ఏకీకృతం ఉత్తరం అది కేవలం ఒక స్థానంలో. దీనికి వ్యతిరేకంగా ప్రోస్ బరువు లెట్ కాన్స్, మరియు పరిగణలోకి డేటా నిర్మాణం కుడి డేటా కావచ్చు మీ పరిస్థితి కోసం నిర్మాణం, డేటా ఎటువంటివైనా మీరు నిల్వ చేస్తున్నారు. మీరు తప్పనిసరిగా ఎల్లప్పుడూ అవసరం లేదు సూపర్ ఫాస్ట్ చొప్పించడం, తొలగింపు ఉపయోగించడానికి ఒక trie మరియు లుక్అప్ మీరు నిజంగా ఇన్సర్ట్ మరియు తొలగించడం గురించి పట్టించుకోను చాలా ఎక్కువ. మీరు త్వరగా యాదృచ్ఛిక అవసరం అయితే యాక్సెస్, బహుశా వ్యూహం ఉత్తమం. కాబట్టి యొక్క ఆ పరిశుద్ధం తెలియజేయండి. యొక్క నాలుగు ప్రతి మాట్లాడటానికి లెట్ డేటా నిర్మాణాలు ప్రధాన రకాల మేము గురించి మాట్లాడారు చేసిన, మరియు ఆ వారు మంచి కావచ్చు ఉన్నప్పుడు కేవలం చూడండి, మరియు అవి మంచి కాదు. కాబట్టి యొక్క శ్రేణుల ప్రారంభిద్దాం. చొప్పించడం కాబట్టి, ఆ రకమైన దురదృష్టకరం. 

ఒక శ్రేణి ముగింపు వద్ద చొప్పించడం, సరే మేము వెళ్ళి మేము ఒక అర్రే నిర్మించడం చేస్తుంటే. కానీ మేము ఇన్సర్ట్ అవసరం ఉంటే మధ్యలో అంశాలు, చొప్పించడం తిరిగి అనుకుంటున్నాను విధమైన చాలా ఉంది అక్కడ ఒక మూలకం సరిపోయే బదిలీ. మరియు మేము ఇన్సర్ట్ చూడాలని అలా అయితే ఎక్కడైనా కానీ ఒక శ్రేణి ముగింపు ఆ బహుశా చాలా గొప్పది కాదు. 

అదేవిధంగా, తొలగింపు, తప్ప మేము ఉన్నాము ఒక శ్రేణి ముగింపు నుండి తొలగించడం, బహుశా కూడా ఉంటే ఇంకా గొప్ప కాదు మేము ఖాళీ అంతరాలను వదిలి వద్దు, ఇది సాధారణంగా మేము లేదు. మేము ఒక మూలకం తొలగించాలని, మరియు అప్పుడు విధమైన అది మళ్ళీ సుఖకరమైన చేస్తాయి. అందువలన నుండి కారకాలను తొలగించడం వ్యూహం కూడా చాలా గొప్పది కాదు. 

శోధన అయితే, గొప్ప ఉంది. మేము రాండమ్ యాక్సెస్ కలిగి, స్థిరంగా సమయం లుక్అప్. మేము కేవలం ఏడు చెప్పటానికి, మరియు మేము వెళ్ళి అర్రే పునస్థాపన ఏడు. మేము వెళ్ళండి, 20 సే అర్రే పునస్థాపన 20. మనం అంతటా iterate లేదు. ఆ అందమైన మంచి వార్తలు. 

వ్యూహాలను కూడా క్రమం సాపేక్షంగా సులభం. మేము ఒక విభజన గురించి మాట్లాడారు ప్రతిసారీ ఇటువంటి ఎంపిక విధమైన అల్గోరిథం, చొప్పించడం విధమైన బబుల్ సార్ట్, విలీనం విధమైన, మేము ఎల్లప్పుడూ దీన్ని శ్రేణుల ఉపయోగిస్తారు, శ్రేణుల అందంగా సులభం ఎందుకంటే డేటా నిర్మాణాలకు సాపేక్ష విధమైన, మేము ఇప్పటివరకు చూసిన. 

వారు కూడా చాలా చిన్న ఉన్నాము. అదనపు స్థలాన్ని చాలా ఉన్నాయి కాదు. మీరు ఖచ్చితంగా ఎక్కువ ప్రక్కన సెట్ మీరు మీ డేటా కలిగి అవసరం వంటి, మరియు అది చాలా ఉంది. కాబట్టి వారు అందంగా చిన్న ఉన్నాము మరియు ఆ విధంగా సమర్థవంతంగా. కానీ మరొక ఇబ్బంది, అయితే, వారు పరిమాణం స్థిరంగా ఉంది. మేము ఎలా సరిగ్గా ప్రకటించాలని ఉన్నాయి పెద్ద మేము మా శ్రేణి ఉండాలనుకుంటున్నాను మరియు మేము మాత్రమే అది ఒక షాట్ పొందడానికి. మేము పెరుగుతాయి మరియు ఇది కుదించే కాదు. 

మేము అది పెరుగుతాయి లేదా తగ్గిపోవటం అవసరం ఉంటే, మేము పూర్తిగా కొత్త వ్యూహం డిక్లేర్ అవసరం, యొక్క మూలకాల అన్ని కాపీ రెండవ శ్రేణి లోకి మొదటి శ్రేణి. మరియు మేము ఆ తప్పుడు ఉంటే సమయం, మేము మళ్ళీ దీన్ని అవసరం. కాబట్టి గొప్ప కాదు. కాబట్టి శ్రేణుల మాకు వశ్యత ఇవ్వాలని లేదు అంశాల వేరియబుల్ సంఖ్యలు కలిగి. 

ఒక లింక్ జాబితా తో, చొప్పించడం అందంగా సులభం. మేము కేవలం ముందు పై టాక్. తొలగింపు కూడా అందంగా సులభం. మేము అంశాలు కనుగొనేందుకు కలిగి. ఆ కొన్ని శోధన తలెత్తుతాయి. 

కానీ మీరు మూలకం అనిపిస్తే ఒకసారి మీరు చెయ్యాల్సిన అన్ని కోసం చూస్తున్నారా ఒక పాయింటర్ మార్చండి ఉంది, బహుశా రెండు మీరు కలిగి ఉంటే ఒక రెట్టింపైన జాబితా లింక్ లింక్ జాబితా కాకుండా ఆపై మీరు కేవలం నోడ్ విముక్తురాలిని చేయగలవు. మీరు మారవచ్చు లేదు చుట్టూ ప్రతిదీ. మీరు కేవలం రెండు పాయింటర్లు మార్చడానికి కాబట్టి ఆ అందంగా త్వరగా ఉంది. 

శోధన కుడి, చెడ్డది? మాకు ఒక కనుగొనేందుకు క్రమంలో అనుసందానించబడ్డ జాబితాలో మూలకం, లేదో ఒక్కొక్కటిగా లేదా రెట్టింపైన, లింక్డ్ మేము అది అన్వేషణ సరళ ఉంటుంది. మేము ప్రారంభంలో ప్రారంభించడానికి కలిగి మరియు ముగింపు తరలించడానికి, లేదా ముగింపు తరలింపు వద్ద మొదలు ప్రారంభానికి. మేము ఇకపై రాండమ్ యాక్సెస్ లేదు. మేము ఒక చేస్తున్నా చేస్తే శోధించడం చాలా, బహుశా ఒక లింక్ జాబితా కాదు మాకు చాలా బావుంది. 

వారు నిజంగా కూడా ఉన్నారు క్రమం కష్టం, కుడి? ఏకైక మార్గం మీరు చెయ్యవచ్చు నిజంగా ఒక లింక్ జాబితా క్రమం మీరు నిర్మించేందుకు గా క్రమం ఉంటుంది. కానీ మీరు దానిని క్రమం ఉంటే అది నిర్మించేందుకు, మీరు ఇకపై ఉన్నాము ఇకపై శీఘ్ర ప్రక్షిప్తాలు మేకింగ్. మీరు కేవలం tacking లేదు ముందు పై విషయాలు. మీరు కనుగొనడానికి కలిగి కుడి స్పాట్ ఉంచారు, ఆపై మీ చొప్పించడం కేవలం గురించి చెడు అవుతుంది వ్యూహం లోకి ఇన్సర్ట్. కాబట్టి లింక్ జాబితాలు కాదు డేటా సార్టింగ్ కోసం చాలా గొప్పది. 

వారు కూడా అందంగా చిన్న, పరిమాణం వారీగా ఉన్నారు. రెట్టింపైన కొద్దిగా లింక్డ్ జాబితా ఒక్కొక్కటిగా లింక్ జాబితాలు కంటే పెద్ద, ఇది కొంచెం పెద్దగా శ్రేణుల కంటే, కానీ అది కాదు వృధా స్పేస్ పెద్ద మొత్తం. కనుక స్పేస్ ఒక ప్రీమియం ఉంది, కానీ ఒక నిజంగా తీవ్రమైన ప్రీమియం, ఈ సరైన మార్గం కావచ్చు. 

హాష్ పట్టికలు. ఒక హాష్ పట్టిక చొప్పించడానికి న్యాయబద్ధంగా, సూటిగా ఉంటుంది. ఇది ఒక రెండు దశల ప్రక్రియ ఉంది. మొదటి మేము ద్వారా మా డేటా అమలు చేయాలి ఒక హాష్ ఫంక్షన్ను ఒక హాష్ కోడ్ను పొందడానికి, ఆపై మేము లోకి మూలకం ఇన్సర్ట్ హాష్ కోడ్ స్థానం వద్ద హాష్ పట్టిక. 

లింక్ జాబితా పోలి తొలగింపు, మీరు మూలకం కనుగొనేందుకు ఒకసారి సులభం. మీరు మొదటి దానిని కనుగొనేందుకు కలిగి కానీ అప్పుడు మీరు తొలగిస్తున్నప్పుడు, మీరు కేవలం మార్పిడి అవసరం గమనికలు ఒక జంట, మీరు వేరు కూర్పికం ఉపయోగిస్తున్నారు. మీరు ఛేదించి ఉపయోగిస్తున్నట్లయితే, లేదా మీరు తెలియకపోతే ఉపయోగించి వద్ద అన్ని కూర్పికం మీ హాష్ పట్టిక లో, తొలగింపు నిజానికి నిజంగా సులభం. మీరు చేయవలసిందల్లా హాష్ డేటా, మరియు అప్పుడు ఆ స్థానానికి వెళ్ళండి. మరియు ఊహిస్తూ మీరు లేదు ఏ గుద్దుకోవటం కలిగి మీరు చాలా త్వరగా తొలగించడానికి చేయగలరు. 

ఇప్పుడు, లుక్అప్ ఇక్కడ విషయాలు ఉంది ఒక కొంచెం క్లిష్టమైన పొందుతారు. ఇది మంచి సగటున వార్తలు లింక్ జాబితాలు కంటే. మీరు కూర్పికం ఉపయోగిస్తున్నట్లయితే, మీరు ఇప్పటికీ ఒక లింక్ జాబితా, మీరు ఇప్పటికీ కలిగివుంటాయి శోధన అనుబంధ జాబితా నష్టము. మీరు వేస్తున్నాము ఎందుకంటే కానీ మీ లింక్ జాబితా మరియు 100 లేదా 1000 పైగా అది చీల్చిన లేదా n మీ హాష్ పట్టిక లో అంశాలకు మీరు లింక్ జాబితాలు పరిమాణం n వ దేవుని అన్ని ఒకటి. వారు అన్ని గణనీయంగా చిన్న ఉన్నాము. మీరు n బదులుగా జాబితాలు లింక్ చేసారు పరిమాణం n యొక్క ఒక లింక్ జాబితా. 

కాబట్టి ఈ వాస్తవ ప్రపంచ స్థిరంగా సాధారణంగా మేము ఏ అంశం, సమయం సంక్లిష్టత గురించి మాట్లాడటానికి లేదు, అది నిజానికి ఇక్కడ ఒక వైవిధ్యం లేదు. కాబట్టి లుక్అప్ ఇప్పటికీ సరళ మీరు కూర్పికం ఉపయోగిస్తున్నట్లయితే, అన్వేషణ కానీ జాబితా పొడవు మీరు ద్వారా శోధిస్తున్న పోలిక ద్వారా చాలా, చాలా చిన్నది. మళ్ళీ, సార్టింగ్ మీ ఉంటే ఇక్కడ లక్ష్యం, హాష్ పట్టిక యొక్క బహుశా సరైన మార్గం వెళ్ళడానికి లేదు. సార్టింగ్ ఉంటే కేవలం ఒక వరుసను ఉపయోగిస్తాయి మీకు నిజంగా ముఖ్యం. 

మరియు వారు పరిమాణంలో స్వరసప్తకం అమలు చెయ్యవచ్చు. ఇది ఒక అని చెప్పటానికి హార్డ్ వార్తలు హాష్ పట్టిక, చిన్న లేదా పెద్ద ఇది నిజంగా ఆధారపడి ఎందుకంటే ఎలా పెద్ద మీ హాష్ పట్టిక ఉంది. మీరు మాత్రమే నిల్వ చూడాలని ఉంటే మీ హాష్ పట్టిక లో ఐదు అంశాలు, మరియు మీరు ఒక హాష్ పట్టిక అది 10,000 అంశాలతో, మీరు బహుశా స్పేస్ చాలా వృధా చేస్తున్నాం. కాంట్రాస్ట్ కూడా మీరు చేయవచ్చు ఉండటం చాలా కాంపాక్ట్ హాష్ పట్టికలు కలిగి కానీ చిన్న మీ హాష్ పట్టిక, గెట్స్ ఆ లింక్ జాబితాలు ప్రతి ఇక పొందుతాడు. కాబట్టి నిజంగా నిర్వచించడానికి మార్గమే లేదు సరిగ్గా ఒక హాష్ పట్టిక పరిమాణం, కానీ అది బహుశా సురక్షితంగా ఇది సాధారణంగా చెప్పాలి ఒక లింక్ కంటే పెద్ద చేస్తాడు అదే డేటా నిల్వ జాబితా ఒక trie కంటే కానీ చిన్న. 

మరియు ప్రయత్నాలు నాలుగో ఉంటాయి ఈ నిర్మాణాలు మేము గురించి ఆలోచిస్తున్నాము. ఒక trie లోకి ఇన్సర్ట్ సంక్లిష్టంగా ఉంటుంది. డైనమిక్ చాలా ఉంది మెమరీ కేటాయింపు ముఖ్యంగా ప్రారంభంలో, మీరు నిర్మించడానికి మొదలు పెడుతున్నారు వంటి. కానీ అది స్థిరంగా సమయం. ఇది మాత్రమే మానవ మూలకం ఇక్కడ గమ్మత్తైన చేస్తుంది. నల్ పాయింటర్ ఎదుర్కొనే కలిగి, malloc స్పేస్, బహుశా malloc స్థలం వెళ్ళి అక్కడ నుండి మళ్ళీ. భయపెట్టడం కారకం యొక్క విధమైన డైనమిక్ మెమరీ కేటాయింపు లో గమనికలు క్లియర్ అడ్డంకి ఉంది. కానీ మీరు అది క్లియర్ చేసిన తర్వాత, చొప్పించడం నిజానికి, చాలా సాధారణ వస్తుంది మరియు అది ఖచ్చితంగా స్థిరంగా సమయం. 

తొలగింపు సులభం. మీరు చేయవలసిందల్లా డౌన్ నావిగేట్ ఒక గమనికలు మరియు ఉచితం నోడ్ యొక్క జంట, కాబట్టి ఆ అందంగా బావుంటుంది. శోధన కూడా అందంగా ఫాస్ట్. ఇది మాత్రమే ఆధారంగా మీ డేటా యొక్క పొడవు. మీ డేటా అన్ని చేస్తే అయిదు పాత్ర తీగలను, ఉదాహరణకు, మీరు ఐదు నిల్వ చేస్తున్నారు మీ trie లో పాత్ర తీగలను, అది మాత్రమే అయిదు దశలు మీరు చూస్తున్న ఏమి కనుగొనేందుకు. ఐదు కాబట్టి, కేవలం ఒక స్థిరంగా అంశం మళ్ళీ, చొప్పించడం, తొలగింపు, మరియు శోధన ఇక్కడ సమర్థవంతంగా స్థిరం సమయం ఉంటాయి. 

మరో విషయం మీ trie ఉంది వాస్తవానికి రకమైన ఇప్పటికే కుడి, క్రమబద్ధీకరించబడింది? మేము ఉన్నాము ఎలా ఆటతీరుతో ఇన్సర్ట్ అంశాలు, లేఖ ద్వారా లేఖ వెళ్ళడం ద్వారా కీ అంకెల ద్వారా కీ, లేదా అంకె, సాధారణంగా మీ trie గా ముగుస్తుంది మీరు నిర్మించడానికి వంటి రకమైన క్రమబద్ధీకరించబడింది. ఇది నిజంగా చేస్తుంది లేదు భావం క్రమబద్ధీకరించేందుకు గురించి ఆలోచించడం అదే విధంగా మేము కూడా ఆలోచించడానికి ఇది శ్రేణులను లేదా లింక్ జాబితాలు, లేదా హాష్ పట్టికలు. కానీ కొన్ని భావంలో, మీ మీరు వంటి trie క్రమబద్ధీకరించబడింది. 

ఇబ్బంది, కోర్సు యొక్క, ఉంది ఒక trie వేగంగా భారీ అవుతుంది. ప్రతి జంక్షన్ సమయం నుండి, మీరు వాటిని మీ కీ అంకెలు కలిగి ఉంటే మనం, మీరు ఇతర 10 మీరు ఉంచాడు వెళ్ళే ఇది ప్రతి నోడ్ అర్థం సమాచారాన్ని కలిగి డేటా గురించి మీరు నిల్వ మీరు ఆ నోడ్, ప్లస్ 10 గమనికలు వద్ద. ఇది CS50 IDE న, 80 బైట్లు. కనుక ఇది కనీసం 80 బైట్లు మీరు సృష్టించే ప్రతి నోడ్, మరియు కూడా డేటా లెక్కింపు కాదు. మరియు మీ నోడ్స్ ఉంటే బదులుగా అంకెలు, అక్షరాలను, ఇప్పుడు మీరు 26 గమనికలు ప్రతి స్థానం నుండి. మరియు 26 సార్లు 8 బహుశా 200 బైట్లు లేదా అలాంటిదే. మరియు మీరు రాజధాని మరియు మీరు చేయవచ్చు lowercase-- నేను ఈ వెళుతున్న పేరు కుడి, చూసారా? మీ నోడ్స్ నిజంగా పొందవచ్చు పెద్ద, అందువలన trie కూడా, మొత్తం, చెయ్యవచ్చు చాలా, చాలా పెద్ద పొందడానికి. స్పేస్ ఒక అధిక వద్ద ఉంటే కాబట్టి మీ సిస్టమ్లో ప్రీమియం, ఒక trie సరైన మార్గం ఉండకపోవచ్చని కూడా దాని ఇతర ప్రయోజనాలు అయితే, వెళ్ళి తెరపైకి వస్తాయి. నేను డౌ లాయిడ్ ఉన్నాను. ఈ CS50 ఉంది.