ڈوگ لایڈ تو CS50 میں، ہم احاطہ کرتا ہے مختلف اعداد و شمار کے ڈھانچے کی ایک بہت، ٹھیک ہے؟ ہم arrays دیکھا، اور سے منسلک ہے فہرستوں، اور ہیش میزیں، اور کوشش کرتا ہے، پوٹ اور قطار. ہم نے بھی ایک چھوٹا سا پتہ چل جائے گا درختوں اور ڈھیر کے بارے میں، لیکن واقعی یہ سب صرف ختم ایک موضوع پر مختلف حالتوں ہونے. واقعی موجود ہیں ان چار بنیادی تصورات کی قسم اور ہے کہ سب کچھ کرنے کے لئے نیچے ابلنا کر سکتے ہیں. لڑیاں، منسلک کی فہرست، ہیش میزیں، اور کوشش کرتا ہے. اور جیسے میں نے کہا، وہاں ان پر مختلف حالتوں ہیں، لیکن یہ خوبصورت ہے بہت مختصر کرنے کے لئے جا رہا سب کچھ ہم بات کرنے کے لئے جا رہے ہیں سی کے لحاظ سے اس کی کلاس میں کے بارے میں لیکن کس طرح ان کا حق، تمام پیمانہ ہے؟ ہم پیشہ اور cons کے بارے میں بات کی ہے ان پر الگ الگ ویڈیوز میں سے ہر ایک کی، لیکن تعداد کے ایک بہت کچھ ہے ارد گرد پھینک دیا ہو. جنرل کی ایک بہت کچھ ہے خیالات کے ارد گرد پھینک دیا ہو. کی کوشش کرتے ہیں اور مضبوط ہیں یہ صرف ایک جگہ میں. کے خلاف پیشہ وزن دو CONS، اور پر غور جس آنکڑا ڈھانچہ صحیح اعداد و شمار ہو سکتا ہے آپ کی مخصوص صورتحال کے لئے ڈھانچہ، ڈیٹا کی جو بھی قسم آپ ذخیرہ کرنے کر رہے. آپ کو لازمی طور ہمیشہ کی ضرورت نہیں ہے ، سپر روزہ اندراج، منسوخی کا استعمال ایک trie کی اور تلاش اگر آپ واقعی ڈالنے اور خارج کرنے کے بارے میں پرواہ نہیں کرتے بہت زیادہ. آپ کو صرف فوری طور پر بے ترتیب کی ضرورت ہو تو رسائی، شاید ایک سرنی بہتر ہے. تو کہ کشید دو. کے چار میں سے ہر ایک کے بارے میں بات کرتے ہیں ڈیٹا ڈھانچے کے اہم اقسام ہم کے بارے میں بات کی تھی، اور ہے کہ وہ اچھے ہو سکتا ہے جب صرف دیکھنے، اور جب وہ اتنا اچھا نہیں ہو سکتا. تو arrays کے ساتھ شروع کر دیں. اندراج تو، اس قسم کے برا ہے. 

ایک صف کے آخر میں اضافے، ٹھیک ہے ہم جا کے طور پر ہم ایک سرنی کی تعمیر کر رہے ہیں تو. لیکن ہم داخل کرنے کی ضرورت ہے وسط میں عناصر، اندراج پر واپس لگتا قسم، ایک بہت کچھ ہے وہاں میں ایک عنصر فٹ ہونے کے لئے منتقل. اور ہم کرنے کے لئے جا رہے ہیں اگر ایسا ہے تو کہیں لیکن ایک صف کے آخر، کہ شاید اتنی بڑی نہیں ہے. 

اسی طرح، منسوخی، جب تک ہم ہیں ایک صف کے آخر سے خارج کرنے، شاید یہ بھی تو اچھا نہیں ہے ہم خالی فرق چھوڑنے کے لئے نہیں کرنا چاہتے، جو عام طور پر ہم ایسا نہیں کرتے. ہم ایک عنصر کو خارج کرنا چاہتے، اور پھر قسم کے اسے دوبارہ چوست بنانے. اور اس کی طرف سے عناصر کو خارج ایک سرنی، بھی اتنی بڑی نہیں. 

تلاش، اگرچہ، بہت اچھا ہے. ہم بے ترتیب رسائی حاصل ہے، مسلسل وقت نظر دوڑائیں. ہم صرف سات کہتے ہیں، اور ہمیں جانا نقل مکانی کے لئے صف سات. ہم پر جانے کے ساتھ، 20 کا کہنا ہے کہ نقل مکانی کے لئے صف 20. ہم اس پار iterate کرنے کی ضرورت نہیں ہے. یہ بہت اچھی بات ہے. 

Arrays بھی الگ الگ کرنے کے لئے نسبتا آسان ہے. ہم چھنٹائی کے بارے میں بات ہر وقت اس طرح کے انتخاب کی طرح کے طور پر الگورتھم،، اندراج کی طرح، بلبلا طرح، ضم قسم، ہم نے ہمیشہ ایسا کرنے کی arrays کے استعمال، arrays کے لئے بہت آسان ہے کیونکہ ڈیٹا ڈھانچے کے رشتہ دار ترتیب، ہم نے اب تک دیکھا ہے. 

انہوں نے یہ بھی نسبتا چھوٹے ہیں. اضافی جگہ کی ایک بہت نہیں ہے. آپ کو صرف بالکل کے طور پر زیادہ سے زیادہ مقرر آپ کے ڈیٹا منعقد کرنے کی ضرورت کے طور پر، اور یہ کہ یہ بہت زیادہ ہے. تو وہ بہت چھوٹے ہیں اور اس راہ میں موثر. لیکن ایک اور منفی پہلو، اگرچہ، وہ سائز میں طے کر رہے ہیں ہے. ہم کس طرح کا اعلان ہے بڑے ہم، ہمارے صف بننا چاہتا ہوں اور ہم صرف اس پر ایک شاٹ حاصل. ہم اگاتے ہیں اور یہ سکڑ نہیں کر سکتے ہیں. 

ہم اس میں اضافہ یا چھوٹا کرنے کی ضرورت ہو تو، ہم ایک مکمل طور پر نئی صف کا اعلان کرنے کی ضرورت ہے، کے عناصر کی تمام کاپی دوسری صف میں پہلی صف. اور ہم اس miscalculated تو وقت، ہم اسے دوبارہ کرنے کی ضرورت ہے. اتنی بڑی نہیں. تو arrays ہمیں لچک نہیں دیتے عناصر کے متغیر تعداد حاصل کرنے. 

ایک لنک کی فہرست کے ساتھ، اندراج بہت آسان ہے. ہم صرف سامنے پر سمت. منسوخی بھی بہت آسان ہے. ہم عناصر کو تلاش کرنے کے لئے ہے. کہ کچھ تلاش شامل. 

لیکن تم عنصر مل گیا ہے ایک بار آپ کو ایسا کرنے کی ضرورت ہے، سب کے لئے تلاش کر رہے ہیں ایک پوائنٹر تبدیل، ممکنہ طور پر دو اگر آپ کے پاس ایک دوگنا list-- منسلک لنک کی فہرست، rather-- اور پھر آپ صرف نوڈ آزاد کر سکتے ہیں. آپ کو منتقل کرنے کی ضرورت نہیں ارد گرد سب کچھ. آپ کو صرف، دو اشارہ تبدیل تاکہ بہت تیز رفتار ہے. 

تلاش حق، اگرچہ برا ہے؟ ہمیں ایک تلاش کرنے کے لئے کے لئے ایک لنک کی فہرست میں عنصر، چاہے اکیلے یا دوگنا، منسلک ہم اسے لکیری تلاش کرنے کے لئے ہے. ہم شروع میں شروع کرنے کے لئے ہے اور آخر میں منتقل، یا آخر اس اقدام سے شروع شروع کرنے کے لئے. ہم اب بے ترتیب تک رسائی نہیں ہے. ہم کر رہے ہیں تو تلاش کے بہت، شاید ایک لنک کی فہرست نہیں ہے ہمارے لئے بہت اتنا اچھا. 

انہوں نے سچ میں بھی ہیں الگ الگ کرنے کے لئے مشکل، ٹھیک ہے؟ واحد راستہ آپ کر سکتے ہیں واقعی ایک لنک کی فہرست ترتیب آپ اس کی تعمیر کے طور پر حل کرنے کے لئے ہے. لیکن آپ کے طور پر الگ الگ تو اس کی تعمیر، آپ کو اب کوئی ہو اب فوری اضافے بنانے. تم بس tacking کی نہیں کر رہے ہیں سامنے پر چیزیں. آپ کو تلاش کرنے کی ضرورت ہے صحیح جگہ ڈال کرنے کے لئے، اور پھر اپنے اندراج صرف کے بارے میں کے طور پر برا بن جاتا ہے ایک صف میں ڈالنے کے طور پر. تو منسلک کی فہرست نہیں ہیں ڈیٹا چھانٹ رہا ہے کے لئے بہت اچھا. 

انہوں نے یہ بھی خوبصورت چھوٹے، سائز وار ہیں. دوگنا تھوڑا منسلک فہرست اکیلے منسلک کی فہرست کے مقابلے میں وسیع تر، جس میں تھوڑا سا بڑے ہیں arrays کے مقابلے میں، لیکن یہ نہیں ہے ضائع شدہ جگہ کی ایک بڑی رقم. تو جگہ ایک پریمیم میں ہے، لیکن نہیں بہت شدید پریمیم، اس کے جانے کے لئے صحیح طریقہ ہو سکتا ہے. 

ہیش میزیں. ایک ہیش ٹیبل میں اضافے منصفانہ سیدھا ہے. یہ ایک دو قدم عمل ہے. سب سے پہلے ہم ذریعے ہمارے اعداد و شمار کو چلانے کے لئے کی ضرورت ہے ایک ہیش تقریب ایک ہیش کوڈ حاصل کرنے کے لئے، اور پھر ہم میں عنصر داخل اس ہیش کوڈ جگہ پر ہیش کی میز. 

لنک کی فہرست کے لئے اسی طرح کی منسوخی،، آپ کے عنصر تلاش ایک بار کے لئے آسان ہے. تم، سب سے پہلے اس کو تلاش کرنا پڑے لیکن پھر آپ اسے حذف جب، آپ کو صرف تبادلہ کرنے کی ضرورت اشارہ کے ایک جوڑے، اگر آپ کو علیحدہ جکڑا جانا؟ استعمال کر رہے ہیں. آپ کی تحقیقات کا استعمال کرتے ہوئے کر رہے ہیں تو، یا تم نہیں ہو تو کا استعمال کرتے ہوئے تمام جکڑا جانا ؟. آپ ہیش ٹیبل میں، منسوخی اصل میں واقعی آسان ہے. آپ کو ایسا کرنے کی ضرورت ہے تمام ہیش ہے اعداد و شمار، اور پھر اس جگہ پر جانے. سنبھالنے اور آپ ایسا نہیں کرتے ، کسی بھی collisions سے ہے آپ کو بہت جلد خارج کرنے کے قابل ہو جائے گا. 

اب، نظر دوڑائیں جہاں چیزیں ایک چھوٹا سا زیادہ پیچیدہ ہو. یہ بہتر اوسط پر ہے منسلک کی فہرست کے مقابلے میں. آپ جکڑا جانا؟ استعمال کر رہے ہیں، اگر آپ اب بھی ایک سے منسلک فہرست ہے، جس سے آپ کو اب بھی کا مطلب ہے تلاش ایک سے منسلک فہرست نقصان. آپ لے رہے ہیں کی وجہ سے لیکن آپ لنک فہرست اور 100 یا 1،000 سے زیادہ اس تیز یا ن آپ ہیش ٹیبل میں عناصر، تم منسلک کی فہرست سائز n- ویں سب ایک ہیں. وہ سب کافی چھوٹے ہیں. تم (ن) کے بجائے فہرستوں سے منسلک ہے سائز (ن) کے ایک لنک کی فہرست کے. 

اور اس طرح یہ حقیقی دنیا مسلسل عام طور پر ہم جس عنصر، وقت کی پیچیدگی کے بارے میں بات نہ کرو، یہ اصل میں یہاں ایک فرق پڑتا ہے. تو تلاش اب بھی لکیری ہے آپ جکڑا جانا؟ استعمال کر رہے ہیں تلاش، لیکن فہرست کی طوالت آپ کے ذریعے تلاش کر رہے ہیں مقابلے کی طرف سے بہت، بہت مختصر ہے. ایک بار پھر، آپ چھنٹائی ہے یہاں مقصد، ہیش کی میز کی شاید صحیح طریقے سے جانے کے لئے نہیں. چھنٹائی تو بس ایک سرنی کا استعمال کرتے ہیں آپ کے لئے بہت اہم ہے. 

اور وہ سائز کے پہلوؤں کو چلا سکتے ہیں. یہ ایک چاہے کہنا مشکل ہے ہیش ٹیبل، چھوٹے یا بڑے ہے یہ واقعی پر منحصر ہے کیونکہ کتنے بڑے آپ ہیش کی میز ہے. آپ کو صرف ذخیرہ کرنے جا رہے ہیں تو آپ ہیش ٹیبل میں پانچ عناصر، اور آپ کو ایک ہیش کی میز ہے اس میں 10،000 عناصر کے ساتھ، آپ کو شاید جگہ کی ایک بہت برباد کر رہے ہو. کے برعکس بھی آپ کر سکتے ہیں کیا جا رہا ہے ، بہت کمپیکٹ ہیش میزیں ہے لیکن چھوٹے اپنے ہیش میز، ہو جاتا ہے ان سے منسلک کی فہرست میں سے ہر ایک اب ہو جاتا ہے. اور اس طرح واقعی کی وضاحت کرنے کے لئے کوئی راستہ نہیں ہے بالکل ایک ہیش ٹیبل کے سائز، لیکن یہ شاید محفوظ ہے یہ عام طور پر کا کہنا ہے کہ ایک لنک سے بڑا ہونے جا رہا ایک ہی ڈیٹا ذخیرہ فہرست، ایک trie کے مقابلے میں لیکن چھوٹے. 

اور کوشش کرتا ہے چوتھے نمبر پر ہیں ان ڈھانچے کے کہ ہم کے بارے میں بات کر رہے ہیں. ایک trie میں داخل پیچیدہ ہے. متحرک کی ایک بہت کچھ ہے میموری مختص کرنے، خاص طور پر شروع میں، آپ کو تعمیر کرنے کے لئے شروع کر رہے ہیں کے طور پر. لیکن یہ مسلسل وقت ہے. یہ صرف انسانی عنصر ہے یہاں یہ مشکل ہے کہ. شہوت انگیز null پوائنٹر کا سامنا کرنے کے لئے، malloc کے خلائی،، ممکنہ طور پر malloc کے خلا وہاں جانا وہاں سے ایک بار پھر. کی دھمکیوں عنصر کی قسم متحرک میموری مختص کرنے میں اشارہ صاف کرنے کے لئے رکاوٹ ہے. لیکن تم نے اس کی منظوری دے دی ہے ایک بار، اندراج اصل میں، بہت آسان آتا ہے اور یہ یقینی طور پر مسلسل وقت ہے. 

منسوخی کے لئے آسان ہے. آپ کو ایسا کرنے کی ضرورت ہے تمام نیچے تشریف ہے اشارہ اور مفت نوڈ کے جوڑے، تاکہ بہت اچھا ہے. تلاش بھی بہت تیز ہے. یہ صرف پر مبنی ہے آپ کے ڈیٹا کی لمبائی. آپ کے اعداد و شمار کے تمام ہے تو پانچ کردار ڈور، مثال کے طور پر، آپ کو پانچ ذخیرہ کرنے کر رہے آپ کے trie میں کردار ڈور، یہ صرف پانچ اقدامات آپ کے لئے تلاش کر رہے ہیں تلاش. پانچ تو، صرف ایک مستقل عنصر ہے ایک بار پھر، اندراج، منسوخی، اور تلاش یہاں مؤثر طریقے سے، تمام مسلسل وقت ہے. 

ایک اور بات آپ trie کے ہے اصل قسم پہلے سے ہی صحیح، حل؟ ہم ہیں کہ کس طرح کی وجہ سے ڈالنے عناصر، کے خط کی طرف سے خط جا کر کلید کے ہندسوں کی طرف سے اہم، یا عددی، عام طور پر، آپ trie کے ہونے کی وجہ سے ختم ہو جاتی ہے تم اس کی تعمیر کے طور پر قسم کے مطابق. یہ واقعی کرتا ہے نہیں ہے احساس چھنٹائی کے بارے میں سوچنا اسی طرح میں ہم کے بارے میں سوچنا یہ arrays کے، یا منسلک کی فہرست کے ساتھ، یا ہیش میزیں. لیکن کچھ معنوں میں، آپ آپ کے طور پر جانا trie کے مطابق ہے. 

منفی پہلو، کورس کی، یہ ہے کہ ایک trie تیزی سے بھاری ہو جاتا ہے. ہر جنکشن نقطہ نظر سے، آپ کو ہو سکتا ہے آپ کی چابی ہندسوں پر مشتمل ہے تو have--، آپ کو دوسرے 10 ہے جگہوں پر آپ، جا سکتے ہیں جو ہر نوڈ کا مطلب ہے کہ میں معلومات پر مشتمل ڈیٹا کے بارے میں آپ کو محفوظ کرنا چاہتے ہیں اس نوڈ، کے علاوہ 10 سے اوپر اشارہ. جس، CS50 IDE پر، 80 بائٹس ہے. تو اس کے لئے کم از کم 80 بائٹس ہے آپ کو بنانے کے کہ ہر نوڈ، اور یہ کہ بھی ڈیٹا گنتی نہیں ہے. اور اپنے مراکز ہیں بجائے ہندسوں کے خط، اب آپ 26 اشارہ ہے ہر جگہ سے. اور 26 مرتبہ 8 شاید 200 بائٹس، یا کچھ اس طرح. اور آپ کو دارالحکومت ہے اور آپ کر سکتے ہیں lowercase-- میں اس کے ساتھ جا رہا ہوں جہاں حق، دیکھ رہے ہو؟ آپ نوڈ واقعی حاصل کر سکتے ہیں بڑے، اور اس سے Trie خود، مجموعی طور پر، کر سکتے ہیں بھی، بہت بڑا ملتا ہے. جگہ ایک اعلی پر ہے تو آپ کے سسٹم پر پریمیم، ایک trie کے لئے صحیح راستہ نہیں ہو سکتا یہاں تک کہ اس کے دوسرے فوائد اگرچہ، جانا کھیل میں آتے ہیں. میں ڈوگ لایڈ ہوں. یہ CS50 ہے.