[موسیقی بجانے] 

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

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

دوسری بات، ہم اس کے بارے میں بات کریں گے. ہم کوئز کے بارے میں بات کریں گے. ہم کے بارے میں بات کریں گے آپ کو کلاس میں کر رہے ہیں. تم ٹھیک ہو جائے گا. میں نے آپ کے quizzes ہے کے لئے ہے یہاں سے آخر میں آپ کو، تو تم لوگ لینے کے لئے چاہتے ہیں تو ایک، یہ مکمل طور پر ٹھیک نظر. 

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

ٹھیک ہے، تو کوئز 0. اوسط 58 فی صد تھی. یہ بہت کم تھی، اور تاکہ تم لوگ مطابق میں بہت، بہت اچھی طرح سے کیا اس کے ساتھ. 

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

مجھے یہ لگتا ہے کہ ڈراونا ہے جانتے ہیں میں نے اس کوئز پر 40 فی صد کی طرح ہے. میں اس کلاس میں ناکام کرنے کے لئے جا رہا ہوں. میں وعدہ کرتا ہوں، تم نہیں ہو کلاس میں ناکام رہتے ہیں کے لئے جا رہا. تم بالکل ٹھیک ہو. 

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

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

سامعین: کہاں دفتر کے اوقات ہیں؟ 

ANDI پینگ: دفتری اوقات ، اوہ اچھا سوال tonight--. مجھے لگتا ہے کہ دفتری اوقات آج رات نیلگوں ہرا یا دارالعوام میں ہیں. آپ آن لائن CS50 چیک کریں اور آپ، دفتر کے اوقات پر جائیں ایک شیڈول ہونا چاہئے کہ ان میں سے سب کہاں ہیں آپ کو بتاتا ہے. 

میں آج رات یا تو پتہ یا کل چیتی، ہے اور میں ہم کر سکتے ہیں لگتا ہے اس رات کے لئے العام. مجھے یقین نہیں ہے. اچھا سوال. CS50 پر چیک کریں. 

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

ٹھیک ہے، تو پوٹ. کون جیک کے بارے میں سوال سے محبت اور گئے تمام سوالات پر اپنے کپڑے؟ کوئی نہیں؟ ٹھیک ہے، ٹھیک ہے. 

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

بنیادی طور پر، ایک کے بارے میں سوچنا اشیاء میں سے کسی اسٹیک کے طور پر اسٹیک آپ سب سے اوپر پر چیزیں ڈال، اور کہاں اس کے بعد آپ سب سے باہر پاپ. تو LIFO ہم چاہتے مخفف ہے آخری میں، سب سے پہلے باہر use-- کرنے. اور اس طرح کے سب سے اوپر میں آخری اسٹیک باہر آتا ہے کہ سب سے پہلے میں سے ایک ہے. اور اس طرح دو شرائط ہم منسلک کرنے کے لئے پسند اس کے ساتھ دھکا اور پاپ کہا جاتا ہے. جب آپ پر کچھ دھکا اسٹیک، اور آپ کو واپس اپ پاپ. 

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

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

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

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

مثال کے طور پر، اس خوبصورت تو سوال آپ کا کوئز تھا. بنیادی طور پر ہم کس طرح دھکا کرنا ایک اسٹیک کے سب سے اوپر پر. بہت آسان. تم اسے دیکھو تو، ہم اس کے ذریعے چل گے. [اشراوی] size-- تو جب بھی آپ کو یاد ہے، کسی بھی رسائی کے لئے چاہتے ہیں ایک struct کے اندر پیرامیٹر، آپ struct.parameter کے نام کرتے ہیں. 

اس صورت میں، ے اپنے اسٹیک کے نام. ہم سائز تک رسائی حاصل کرنا چاہتے ہیں اس کے، تو ہم s.size کرتے. سائز نہیں ہے تو کے طور پر جب تک صلاحیت یا جب تک کے برابر یہ صلاحیت سے بھی کم ہے کے طور پر، تو یہاں کام کریں گے. 

تم اندر تک رسائی حاصل کرنا چاہتے ہیں اپنے اسٹیک کے، s.strings تو، اور تم اس نیا نمبر ڈال کرنے کے لئے جا رہے ہیں تم وہاں میں داخل کرنا چاہتے ہیں. صرف ہم چاہتے ہیں کریں گے کا کہنا ہے کہ اسٹیک پر int ن داخل، ہم s.strings کر سکتے ہیں بریکٹ، s.size N برابر. سائز کہاں ہے کیونکہ ہم فی الحال اسٹیک میں ہیں ہم آگے بڑھانے کے لئے جا رہے ہیں اس پر، ہم صرف تک رسائی حاصل سائز ہے جہاں کہیں بھی، اسٹیک کے موجودہ پرپورنتا، اور ہم اس پر int ن دھکا. اور پھر ہم اس بات کو یقینی بنانا چاہتے ہیں ہم بھی (ن) کے سائز incrementing رہے ہیں ہم نے کی تاکہ ہم ٹریک رکھ سکتے ہیں اسٹیک پر ایک اضافی چیز شامل. اب ہم زیادہ سائز ہے. یہ یہاں سے کوئی مطلب ہے سب، کس طرح منطقی طور پر یہ کام کرتا ہے؟ یہ قسم کی جلدی تھی. سامعین: آپ پر جا سکتے ہیں s.stringss.strings [s.size] دوبارہ؟ ANDI پینگ: ضرور، تو کیا کرتا ہے ہمیں اس وقت s.size؟ سامعین: یہ موجودہ سائز ہے. ANDI پینگ: بالکل، تو ہمارے سائز پر ہے کہ موجودہ انڈیکس، اور اسی طرح ہم نئے عددی ڈال کرنا چاہتے ہیں ہم s.size میں داخل کرنا چاہتے ہیں. اس کا کوئی مطلب ہے؟ s.strings کیونکہ، کہ تمام ہے سرنی کا نام ہے. یہ سب تک رسائی حاصل ہے ہماری struct کے اندر صف، اور اسی طرح ہم کرنا چاہتے ہیں تو کہ انڈیکس میں (ن) کی جگہ، ہم صرف اس تک رسائی حاصل کر سکتے ہیں استعمال بریکٹ s.size. ٹھنڈا. 

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

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

سامعین: گا ان سلائڈ اور اس پوری چیز آج ish کے ہو؟ ANDI پینگ: ہمیشہ، جی ہاں. میں ڈال کرنے کی کوشش کرنے جا رہا ہوں اس کے بعد ایک گھنٹے کی طرح. میں داؤد کو کرنا ہو گا، ڈیوڈ کی کوشش کریں گے اس کے بعد ایک گھنٹے کی طرح اسے ڈال. 

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

تو ہم نے اس فون کرنے کی پسند dequeueing اور enqueueing ہے. ہم کچھ شامل کرنا چاہتے ہیں ہمارے قطار میں، ہم ان enqueue. ہم چاہتے تو dequeue، یا لینے کے لئے کچھ دور، ہم dequeue. 

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

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

تو کس طرح ایک feasibly کرتا ایک قطار میں کچھ داخل؟ کیا ہم نے اس جگہ انڈیکس کرنا چاہتے ہیں جہاں ہم میں داخل کرنا چاہتے ہیں. اس کا آغاز ہے اگر آپ قطار اور اس کا اختتام ہے یا اس کا سائز، جہاں ہم کرتے ہیں اگلے چیز کو شامل کرنا چاہتے ہیں؟ 

سامعین: [اشراوی] ANDI پینگ: بالکل، آپ کو شامل کرنے کے لئے چاہتے ہیں پر منحصر ہے آپ کو یہ لکھا ہے. یا تو یہ خالی ہے یا یہ کہ خالی ہے. تو آپ کو شاید یہ شامل کرنا چاہتے ہیں کیونکہ یہاں سائز is-- تو یہ سب مکمل ہیں، آپ چاہتے ہیں حق، حق اسے یہاں شامل کرنے کے لئے؟ 

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

میں بالکل، میں سے ایک پر اس لائن فٹ نہیں کر سکتے کوڈ کی لیکن بنیادی طور پر یہ ٹکڑا ایک لائن پر ہونا چاہئے. 30 سیکنڈ کی طرح خرچ. ایک نظر ڈالیں، اور کیوں دیکھیں یہ ہے کہ طریقہ ہے. 

بہت، بہت ہی اسی طرح struct کی، بہت، بہت گزشتہ کے طور پر اسی طرح کی ساخت شاید کے علاوہ اسٹیک کوڈ کی ایک لائن. اور کوڈ کی ایک لائن ہے فعالیت کا تعین کرتا ہے. اور یہ واقعی فرق ایک اسٹیک سے ایک قطار. 

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

اور اس طرح یہ نہیں تھا کہ اس کا تصور قطار، بلکہ یہ قطار تھا. کے سر یہیں ہے کا کہنا ہے کہ. ہمارے قطار اس طرح دیکھا کا کہنا ہے کہ. ہم کہاں منتقل کرنے کے لئے چاہتا تھا، تو لائن کے آغاز، ہے ہم سر منتقل کر دیا کہنے دو اس طرح اور یہاں سائز. 

اب ہم کچھ اضافہ کرنا چاہتے اس قطار، لیکن تم لوگوں کو دیکھ سکتے ہیں کے طور پر، یہ صرف کے طور پر اتنا آسان نہیں ہے سائز کے بعد جو کچھ بھی شامل پھر ہم سے باہر چلانے کی وجہ سے ہماری اصل صف کی حد. ہم واقعی شامل کرنا چاہتے ہیں جہاں یہاں ہے. یہ ایک قطار کی خوبصورتی ہے کہ اس کے ضعف، ہمارے لئے ہے لائن اس طرح ہے جیسے، لگتا ہے لیکن ایک آنکڑا ڈھانچہ میں ذخیرہ جب، وہ ایک سائیکل کی طرح کے طور پر دے. یہ قسم کی کے ارد گرد wraps سامنے اسی طرح کرنے کے لئے ایک لائن بھی لپیٹ کر سکتے ہیں کے ارد گرد جہاں کہیں بھی آپ پر منحصر بننے کے لئے لائن کے آغاز کرنا چاہتے ہیں. اور اس طرح ہم نے ایک لے تو یہاں نیچے دیکھو، چلو ہم ایک تخلیق کرنے کے لئے کرنا چاہتا تھا کا کہنا ہے کہ تقریب ان enqueue بلایا. ہم نے اس (ق) میں int ن شامل کرنے کے لئے کرنا چاہتا تھا. q.size ہم ہمارے اعداد و شمار ہے کہ فون کروں گا (ق) تو ہمارے queue.size نہیں ہے تو structure-- صلاحیت یا تو برابر یہ صلاحیت سے بھی کم ہے q.strings ہماری ق کے اندر صف ہے. ہم قائم کرنے کے لئے جا رہے ہیں کہ q.heads کے برابر، جو یہیں ہے، کے علاوہ q.size صلاحیت، کی طرف سے معامل جس یہاں ہمیں واپس لپیٹ. 

اس مثال، انڈیکس میں تو سر کے دائیں، 1 ہے؟ سائز کے انڈیکس 0، 1، 2، 3، 4 ہے. تو ہم 1 پلس 4 معامل کر سکتے ہیں 5 جو ہمارے صلاحیت کی طرف سے. کیا کہ ہمیں دیتا ہے؟ انڈیکس کیا ہے اس سے باہر آتا ہے؟ 

سامعین: 0. 

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

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

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

اور اس لئے تم dequeue جب، میں نے بھی یہ باہر pseudocode کے. اگر آپ چاہتے ہیں کے لئے بلا جھجھک اس سے باہر کرنے کی کوشش کرنا کوڈنگ. تم نے صحیح، سر کو منتقل کرنا چاہتے ہیں؟ میں dequeue کرنا چاہتے تھے تو میں سر پر منتقل کرے گا. یہ سر ہو جائے گا. 

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

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

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

سامعین: وہ سب سے منسلک کر رہے ہیں کیونکہ، لیکن آپ کو کافی نہیں جانتے [اشراوی]. 

ANDI پینگ: جی ہاں، بالکل اتنا یاد کہ ایک صف کی پرتیبھا ہم نے اس حقیقت تھا رینڈم رسائی میموری جہاں میں انڈیکس سے قدر کرنا چاہتا تھا تو چھ، میں صرف، انڈیکس چھ کہہ سکتے ہیں مجھے اس کی قیمت دے. arrays کے مطابق کر رہے ہیں اور اس وجہ سے ہے کہ میموری کا ایک ملحق خلا میں ایک جگہ میں، جبکہ لنک کی فہرست کے قسم ہیں تصادفی، کے ارد گرد تمام interspersed کے اور واحد راستہ آپ کو ایک حاصل کر سکتے ہیں آپ کو بتاتا ہے کہ ایک پوائنٹر کے ذریعے ہے کہ اگلے نوڈ ہے جہاں کا پتہ. 

اور اس طرح ایک نتیجہ کے طور پر، صرف ایک ہی طریقہ ایک لنک کی فہرست کے ذریعے تلاش کرنے کے لئے لکیری تلاش ہے. میں کہاں نہیں جانتے کیونکہ لنک کی فہرست میں 12th قیمت، ہے میں مکمل طور پر گزرنا ہے اس سے منسلک فہرست میں سے ایک کے پہلا نوڈ سر سے ایک کی طرف سے، دوسری نوڈ، تیسری نوڈ، میں آخر میں ملتا ہے جب تک تمام طریقے سے نیچے میں دیکھ رہا ہوں کہ نوڈ ہے جہاں پر. اور اس طرح اس معنی میں، تلاش ایک لنک کی فہرست پر ہمیشہ (ن) ہے. یہ ہمیشہ N ہے. یہ لکیری وقت میں ہمیشہ ہے. 

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

تو نوڈ ستارہ پوائنٹر فہرست برابر. یہی ہے جو ہم پیدا کر رہے ہیں کا مطلب ہے کہ اور ایک پوائنٹر پیدا کرنے فہرست کے اندر کہ سب سے پہلے نوڈ. میرے ساتھ ہر کوئی؟ ہم جانے کے لئے تھے تو یہاں واپس، میں ہوگا کی طرف اشارہ ہے کہ ایک پوائنٹر initialized سر جو اس فہرست میں ہے. 

اور پھر آپ، یہاں نیچے حاصل ایک بار پوائنٹر برابر شہوت انگیز null نہیں ہے جبکہ، تاکہ ہم ہیں جس میں لوپ ہے کی traversing بعد ہونے جا رہا کیا کیونکہ ہماری فہرست کے باقی پوائنٹر شہوت انگیز null برابر ہوتا ہے جب؟ ہم جانتے ہیں کہ have-- 

سامعین: [اشراوی] 

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

تو ہے کہ ہم رہے ہیں جس میں لوپ ہے اصل تلاش کرنے جا رہے. اور پوائنٹر آپ کو دیکھ کر کرتے ہیں تو وہاں تیر تقریب کی اس قسم؟ تو پوائنٹر پوائنٹس تو (ن) کے، تو (ن) کے برابر ہے (ن) میں پوائنٹر، تو اس کا مطلب ہے کہ تم اس پوائنٹر ہر ایک کے آخر پر کے لئے تلاش نوڈ قیمت اصل میں برابر ہے اگر آپ کے لئے تلاش کر رہے ہیں تم سچے واپس کرنا چاہتے ہیں. تو بنیادی طور پر، آپ کو ایک نوڈ میں ہیں کہ اگر ، آپ کے لئے تلاش کر رہے ہیں اس قدر ہے آپ کیا گیا ہے جانتے ہیں کہ کامیابی تلاش کرنے کے قابل. 

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

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

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

ٹھیک ہے، تو ہم کس طرح کیا جائے گا صحیح، نوڈ ڈالنے، ایک فہرست میں وجہ سے یاد کیا فوائد کے بارے میں کیا ہیں کی ایک لنک کی فہرست بمقابلہ ہونے سٹوریج کی شرائط میں ایک صف؟ 

سامعین: یہ متحرک ہے، تو یہ آسان ہے to-- 

ANDI پینگ: بالکل، تو یہ، متحرک ہے جس اس کو بڑھانے اور سکڑ کر سکتے ہیں کا مطلب ہے کہ صارف کی ضروریات پر منحصر ہے. اور اس طرح، اس معنی میں، ہمیں ضرورت نہیں ہے غیر ضروری میموری برباد کرنے کے لئے کیونکہ مجھے پچھلی رات میں چاہتا ہوں کتنی اقدار نہیں جانتے تو دکان پر، یہ میرے لئے کوئی مطلب نہیں ہے ایک سرنی کی وجہ سے پیدا کرنے کے لئے میں 10 اقدار کو ذخیرہ کرنا چاہتے ہیں تو اور میں 1،000 کی ایک سرنی، ہے پیدا برباد میموری کا ایک بہت، الاٹ. ہم ایک لنک استعمال کرنا چاہتے ہیں یہی وجہ ہے کہ فہرست متحرک طور پر کرنے کے قابل ہونا تبدیل یا ہمارے سائز سکڑ. 

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

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

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

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

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

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

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

اور پھر ہم چیک کرنے کے لیے جا رہے ہیں نئے برابر شہوت انگیز null برابر ہے کو دیکھنے کے. ہم نے کہا کیا یاد رکھیں؟ malloc کا جو کچھ بھی تم، آپ کو ہمیشہ کیا کرنا چاہئے؟ آپ ہمیشہ دیکھنے کے لئے جانچ پڑتال ضروری ہے یا نہیں کہ شہوت انگیز null ہے. 

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

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

ہم کر رہے ہیں سب ایک نئے پیدا کر رہا ہے نوڈ، شہوت انگیز null پوائنٹر قائم، اور پھر reassigning اس کے سر پر اگر ہم ہم سر میں داخل کرنا چاہتے ہیں جانتے. اور پھر سر جا رہا ہے کہ نئے نوڈ کی طرف اشارہ. اس کے ساتھ ٹھیک ہر کوئی؟ 

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

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

ٹھیک ہے، تو کوڈ یہاں ہو جائے گا. تم لوگوں کو سیکشن کے بعد ایک نظر ڈالیں. یہ ہو جائے گا. 

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

سامعین: یہ اب بھی کریں گے اسی طرح کی ایک عمل ہو کا پوائنٹر بتائے طرح پھر، کہ پوائنٹر بتائے لیکن ہم وہاں تلاش کرنے کے لئے پڑے گا. 

ANDI پینگ: بالکل، بالکل تو آپ کے علاوہ اسی عمل کہاں تلاش کرنے کے لئے ہے کہ آپ کہ نئے پوائنٹر میں جانا چاہتے ہیں، میں میں داخل کرنا چاہتے ہیں تو ٹھیک list-- منسلک کے وسط، ہے کہ ہمارے سے منسلک فہرست کہتے ہیں. ہم اسے یہیں سے داخل کرنا چاہتے ہیں، ہم نے ایک نیا نوڈ بنانے کے لئے جا رہے ہیں. ہم malloc جا رہے ہیں. ہم نے ایک نیا نوڈ بنانے کے لئے جا رہے ہیں. ہم تفویض کرنے جا رہے ہیں یہاں اس نوڈ کی پوائنٹر. 

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

کس طرح آخر میں ڈالنے کے بارے میں؟ میں چاہتا تھا تو میں یہاں شامل کرنے کے لئے چاہتا تھا، تو ایک فہرست کے آخر میں ایک نیا نوڈ شامل کرنے کے لئے، مجھے لگتا ہے کہ ایسا کرنے کے بارے میں کیسے جا سکتا ہے؟ سامعین: تو اس وقت، گزشتہ ایک شہوت انگیز null کی طرف اشارہ کیا. ANDI پینگ: جی ہاں. بالکل، تو یہ ایک فی الحال معلوم کی طرف اشارہ کیا ہے، اور اس لئے میں اس معنی میں، یہ ہے، لگتا ہے ایک فہرست کے آخر میں شامل کرنے کے لئے بہت آسان. تمہیں کیا کرنا ہے یہ سب مقرر کیا گیا ہے شہوت انگیز null اور پھر بوم کے برابر. وہیں، بہت آسان. بہت آسان. 

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

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

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

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

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

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

ٹھیک ہے، تو اب میں ہوں واقعی شاید خرچ کرنے کے لئے 15 سے 20 منٹ یا بلک طرح کے سیکشن میں باقی وقت کے ہیش میزیں کے بارے میں بات. کس طرح تم لوگوں کے بہت سے pset5 رپورٹ پڑھا ہے؟ ٹھیک، اچھا. یہ عام طور پر 50٪ سے زیادہ ہے. ٹھیک ہے. 

تم لوگوں کو دیکھیں گے تو کے طور پر، آپ pset5 میں چیلنج ہو ایک ڈکشنری لاگو کرنے کے لئے ہو جائے گا آپ 140،000 الفاظ پر لوڈ جہاں ہم اور سپیل چیک آپ کو دے کہ متن کے تمام کے خلاف. ہم آپ کو بے ترتیب دے دونگا ادب کے ٹکڑے. ہم آپ کو دے دونگا وڈسی. ہم آپ کو دی لیاڈ دے دونگا. ہم آپ آسٹن، ٹیکساس پاورس دے دونگا. 

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

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

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

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

اور اس طرح یہاں ہم چاہتے تھے تو انگریزی الفاظ ذخیرہ کرنے کے لئے، ہم ممکنہ طور پر صرف کر سکتے ہیں، مجھے نہیں پتہ ، جانتے ہیں کہ تمام پہلے حروف باری ایک بڑی تعداد کی کسی قسم میں. اور اس طرح، مثال کے طور پر، اگر میں چاہتا تھا ایک apple-- کے مترادف ہونا یا 0 کے انڈیکس کے ساتھ، اور بی، 1 کے ساتھ مترادف ہونا ہم 26 اندراجات کر سکتے ہیں کہ صرف محفوظ کر سکتے ہیں کے خط کے تمام ہم کے ساتھ شروع کریں گے کہ حروف. اور پھر ہم کر سکتے ہیں 0 انڈیکس میں سیب. ہم انڈیکس میں کیلے حاصل کر سکتے ہیں 1، 2 انڈیکس میں cantaloupe پر، اور تو اور تو آگے. اور اس طرح میں تلاش کرنے کے لئے کرنا چاہتا تھا تو میری ہیش ٹیبل اور رسائی ایپل، میں ایپل کے ساتھ شروع ہوتا ہے جانتے ہیں ایک ایک، اور میں بالکل پتہ یہ اور ہیش ضروری ہے کہ 0 انڈیکس کیونکہ میز تقریب کے پہلے تفویض. 

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

کس طرح ایک پر سب واضح ہیش کی میز کی تقریب کام کرتا ہے؟ یہ صرف ایک زیادہ پیچیدہ سرنی کی طرح ہے. یہی وجہ ہے کہ یہ سب ہے. ٹھیک ہے. 

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

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

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

اور اس طرح یہاں، میں تو بیری داخل کرنا چاہتا تھا، میں ٹھیک ہے، میں ان پٹ کے لئے جا رہا ہوں، جانتے ہیں یہ میری ہیش تقریب کے ذریعے. میں انڈیکس کے ساتھ ختم کرنے کے لئے جا رہا ہوں 1، اور پھر میں نے حاصل کرنے کے قابل ہو جائے کرنے کے لئے جا رہا ہوں اس کا صرف ایک چھوٹی اپسمچی وشال 140،000 لفظ ڈکشنری آن لائن. اور پھر میں دیکھ سکتے ہیں اس کے 1/26 کے ذریعے. 

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

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

اور پھر ہم جا رہے ہیں ہیش معامل، SIZE واپس. بہت، بہت ہوشیار رہو نظریاتی طور پر، یہاں، کیونکہ آپ ہیش قدر لامحدود ہو سکتا ہے. یہ صرف اور اور پر جا سکتے ہیں. یہ واقعی کچھ ہو سکتا ہے بہت بڑی قیمت، لیکن آپ ہیش ٹیبل کی وجہ سے تمہیں پیدا کیا ہے صرف 26 اشاریہ جات ہے، آپ بات کو یقینی بنانا چاہتے ہیں آپ modulusing تاکہ آپ یہ وہی ہے run-- نہیں آپ queue-- طور پر بات تو آپ کو چلانے کے لئے نہیں ہے کہ آپ ہیش تقریب کے سب سے نیچے. 

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

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

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

میں insert-- کرنا چاہتا تھا، تو ایک کیا ہے مجھے پتہ نہیں ہے، کے ساتھ شروع ہوتا ہے کہ پھل، بیری کے مقابلے میں دیگر بی،، کیلے. 

سامعین: بلیک بیری. 

ANDI پینگ: بلیک بیری، بلیک بیری. کہاں بلیک بیری یہاں جانا ہے؟ ٹھیک ہے، ہم اصل میں حل نہیں ہے یہ ابھی تک، لیکن نظریاتی طور پر ہم یہ ہے کرنا چاہتے تھے تو الفبائی ترتیب میں، کہاں جانا بلیک بیری چاہئے؟ 

سامعین: [اشراوی] 

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

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

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

ANDI پینگ: آپ ہیش تو آپ ہیش ٹیبل function-- آپ یہ کرنا چاہتے ہیں کے طور پر کے طور پر بڑے ہو سکتا ہے. تو اس معنی میں، میں نے سوچا یہ بہت، بہت آسان تھا میرے لئے آسان صرف ترتیب کی بنیاد پر کرنے کے لئے پہلا لفظ کے حروف پر. اور اس طرح صرف 26 کے اختیارات موجود ہے. میں صرف 26 کے اختیارات حاصل کر سکتے ہیں 25 0 کیونکہ وہ صرف کر سکتے ہیں ایک سے زیڈ کے لئے شروع لیکن اگر تم چاہتے تھے ، شاید، زیادہ پیچیدگی کو شامل کرنے یا تیز کرنے کے لئے وقت چلائیں آپ ہیش کی میز، آپ بالکل کئی طرح کی باتیں کر سکتے ہیں. آپ کو آپ کے اپنے بنانے کے کر سکتے ہیں آپ کو دیتا ہے کہ مساوات میں تقسیم آپ الفاظ، تو آپ جب تلاش یہ تیزی سے ہو رہا ہے. 

یہ مکمل طور پر آپ لوگوں پر منحصر ہے تم کس طرح لاگو کرنے کے لئے چاہتے ہیں. صرف بالٹیاں کے طور پر اس کے بارے میں سوچو. میں حاصل کرنے کے لئے چاہتا تھا، تو 26 بالٹیاں، میں جا رہا ہوں ان بالٹیاں میں چیزوں کو حل کرنے کے لئے. لیکن میں نے ایک گروپ ہے جا رہا ہوں ہر ایک بالٹی میں سامان کا، آپ اسے بنانے کے لئے چاہتے ہیں تو تیزی اور زیادہ مؤثر، مجھے ایک سو بالٹیاں کرتے ہیں. 

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

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

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

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

اور اس طرح تم سب یہاں ہے صرف سب سے اوپر نوڈ ہے کہ دوسرے نوڈس، اشارہ ہے کہ بتاتے ہیں زیادہ نوڈس، اور تو اور تو آگے. اور لہذا آپ کو صرف تیز شاخیں ہیں. یہ منظم کرنے کا صرف ایک مختلف طریقہ ہے اعداد و شمار، اور ہم نے اسے ایک درخت فون کی وجہ سے، تم لوگوں کو یہ صرف ہے just-- ایک درخت کی طرح نظر آتے ہیں کے لئے باہر ماڈلنگ. ہم درختوں یہ کہتے ہیں یہی وجہ ہے کہ. 

ہیش ٹیبل ایک ٹیبل کی طرح لگ رہا ہے. ایک پیڑ صرف ایک درخت کی طرح لگتا ہے. یہ سب ایک الگ ہے نوڈس کو منظم کرنے کا طریقہ آپ کی ضروریات کیا ہیں پر منحصر ہے. 

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

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

تو یہاں، میں نے کے لئے تلاش کرنے کے لئے جا رہا ہوں تو 66 کی قیمت میں 55 سے شروع کر سکتے ہیں. یہ 55 سے 66 سے زیادہ ہے؟ جی ہاں یہ ہے، تو میں نے تلاش قرآن جانتے میں (ن) اس درخت کے دائیں پوائنٹر. میں 77 کرنے کے لئے جانا. ٹھیک ہے، سے کم یا 77 سے زیادہ 66 ہے؟ اوہ، اس سے کم ہے، تو آپ کو معلوم ہے، کہ بائیں نوڈ ہونا ضروری ہے. 

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

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

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

سامعین: تم نے صحیح دیکھنا چاہتا ہوں اور [اشراوی] بائیں طرف دیکھو اور دیکھیں زیادہ سے زیادہ تعداد. 

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

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

میں آپ کو اصل ظاہر کرنے کے لئے کے بارے میں ہوں کوڈ، اور یہ کوڈ کا ایک بہت ہے. کوئی ضرورت نہیں ہے باہر پاگل کرنے. ہم اس کے ذریعے بات کریں گے. 

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

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

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

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

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

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

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

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

اور، اوہ اگلے یہاں [اشراوی] میں خط A. ہے تو ہم اس صف میں نظر آتے ہیں. ہم آٹھویں قدر کو تلاش، اور پھر ہم، اوہ، دیکھنے کے لئے نظر ارے، ایک لفظ، بی ایک ایک لفظ ہے؟ یہ ایک لفظ نہیں ہے. ہم تلاش کر رہے رکھنے کے لئے ہے. 

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

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

ٹھنڈا، ٹھیک ہے. تو ب-اے-ٹی، اور پھر آپ کو تلاش کرنے کے لئے جا رہے ہیں. تم جا رہے ہو اگلی بار اوہ، ارے، یہ سچ ہے، کو دیکھنے کے لئے، اس طرح میں نے اس ایک لفظ ہونا ضروری ہے جانتے ہیں. 

چڑیا گھر کے لئے ایک ہی بات. تو یہاں بات تو صحیح اب ہم اب، چڑیا گھر کے لئے تلاش کرنے کے لئے کرنا چاہتا تھا، فی الحال چڑیاگھر ایک نہیں ہے ہماری لغت میں لفظ ، کیونکہ تم لوگ، دیکھ سکتے ہیں کے طور پر ہم نے ایک بولین ہے کہ پہلی جگہ سچ واپس زوم کے آخر میں ہے. ہم Z-اے-اے-ایم ہے. 

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

سامعین: [اشراوی] 

ANDI پینگ: بالکل، ہم یہ اس بات کو یقینی بنانا چاہتے ہیں یہاں، کہ بولین قدر ہے یہ سچ ہے کہ جانچ پڑتال. Z-اے-اے، پھر ہم اس کی جانچ پڑتال کرنے کے لئے جا رہے ہیں، تو ہم بالکل، ارے، چڑیاگھر ایک لفظ ہے. میں بتانے جا رہا ہوں یہ ایک لفظ تو ہے کہ کمپیوٹر ، جب کمپیوٹر چیک کرتا ہے کہ زو ایک لفظ ہے کہ جانتا ہے. 

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

تو تم بالکل یہ بتانے کے لئے ہے کس موڑ پر یہ ایک لفظ ہے؟ کس وقت یہ ایک لفظ نہیں ہے؟ اور کس وقت مجھے کیا کرنا ہے چیزیں تلاش کرنے کی ضرورت، اور کیا وقت میں اگلے جانے کے لئے کی ضرورت ہے؟ اس کا واضح ہر کوئی؟ ٹھنڈا. 

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

ہم اگر آپ ایسا کرتے لیکن مسئلہ پیدا ہوتا ہے کے بعد آتا ہے کہ ایک لفظ ہے کرنا چاہتے ہیں T کی. آپ کو غسل ہے، تو آپ ہیں ایک H صحیح کرنا چاہتے ہیں جا. اور اس طرح ہم ایسا کرنے کے لئے جا رہے ہیں طریقہ ہے ہم نے ایک علیحدہ نوڈ بنانے کے لئے جا رہے ہیں. ہم جو بھی رقم مختص نہیں کر رہے ہیں اس نئی صف کے لئے میموری کی، اور ہم اشارہ میں reassign کرنے جا رہے ہیں. 

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

یہاں، ہم تو جی ہاں کی جانچ پڑتال کر سکتے ہیں. ہم ٹی کے بعد ایک H مارا، اوہ، تو ہم نے اس ایک لفظ ہے جانتے ہیں کہ. بولین سچ واپس جا رہا ہے. ہر کوئی اس کیسے ہوا پر واضح؟ ٹھیک ہے. 

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

اور اس طرح pset4 کے 5-- اوہ، جو کہ غلط ہے. Pset5 غلط ہجے ہے. میں نے پہلے کہا، آپ کو ایک بار، کے لئے جا رہے ہیں ایک بار پھر، ہم سے منبع کوڈ ڈاؤن لوڈ، اتارنا. تین اہم ہونے جا رہا ہے چیزیں آپ کو ڈاؤن لوڈ کیا جائے گا. تم، لغات ڈاؤن لوڈ کریں گے KERS، اور نصوص. 

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

اور تین بلاکس ہم آپ کو دے گا کہ پروگرام کہا جاتا dictionary.c ہیں، dictionary.h، اور speller.c. اور اس طرح تمام dictionary.c ہے کیا آپ کو لاگو کرنے کے لئے کہا رہے ہیں. یہ الفاظ بوجھ. یہ چیک ان جادو، اور اس بات کو یقینی بناتا کہ سب کچھ مناسب طریقے سے ڈالا جاتا ہے. 

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

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

اور اس چیلنج کا بڑا حصہ کے لئے ہے تم لوگوں کو واقعی dictionary.c نظر ثانی کرنے. ہم آپ کو دینے کے لئے جا رہے ہیں ایک ڈکشنری میں 140،000 الفاظ. ہم آپ کو ایک متن دینے کے لئے جا رہے ہیں ان الفاظ ہے کہ فائل، اور ہم آپ کو منظم کرنے کے قابل بننا چاہتا ہوں ایک ہیش میز یا ایک trie میں ہم جادو لئے تم سے پوچھنا کیونکہ جب آپ کو جادو ہو تو تصور check-- ہومر وڈسی طرح کی جانچ پڑتال. یہ بہت بڑا، بہت بڑا امتحان ہے. 

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

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

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

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

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

ہم میں سے سب کو لاگو کرنے کی کوشش کر رہے ہر ممکن حد تک سب سے تیز رفتار کوڈ. ہم نے تم لوگوں کو چیلنج کرنے کی کوشش کرنا چاہتے ہیں ہمارے اور ہم میں سے سب سے زیادہ تیزی سے عمل درآمد کر سکتے ہیں. اور اس طرح یہ واقعی ہے ہم ہیں کہ پہلی بار تم لوگوں سے پوچھ ایک pset کرنا ہے کہ تم واقعی میں جو طریقہ میں کر سکتے ہیں تم چاہتے ہو. 

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

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

سامعین: ہم صرف حوالہ دیتے ہیں کر سکتے ہیں [اشراوی] کا استعمال کرتے ہوئے کی طرف سے؟ 

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

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

اور کیا Zamyla اصل چلتا ہے کے افعال میں سے ہر ایک کے ذریعے آپ کو لاگو کرنے کی ضرورت ہے، اور تو یہ ہے سب کچھ کے لئے کس طرح بہت، بہت واضح. بس اس بات کا یقین تم بنانے کے لئے اشارہ کا ٹریک رکھنے. یہ ایک بہت ہی مشکل pset ہے. 

یہ، کی طرح ہے کیونکہ مشکل نہیں ہے اوہ، تصورات اتنی زیادہ ہیں مشکل، یا آپ کو سیکھنے کے لئے ہے راستہ اتنا نئے نحو آپ نے گزشتہ pset کے لئے کیا ہے کہ. اس pset کے لئے مشکل ہے کیونکہ اتنے اشارہ وہاں ہو، اور پھر یہ ایک بار کے لئے بہت، بہت آسان ہے تم نہیں کر سکیں آپ کے کوڈ میں ایک بگ ہے کہ مسئلے سے ہے جہاں تلاش کرنے کے لئے. 

اور اس طرح مکمل اور میں بالکل ایمان لوگ ہمارے [اشراوی] کو ہرا دیا کرنے کے قابل ہو جائے ہجے. میں واقعی میں کسی بھی لکھا ہے میرا ابھی تک، لیکن میرا لکھنے کے بارے میں ہوں. آپ لکھ رہے ہیں جبکہ تو تمہارا، میرا تحریری گے. میں بنانے کے لئے کوشش کرنے کے لئے جا رہا ہوں میرا تیزی سے تم سے. ہم سب سے تیز رفتار سے ایک ہے جو نظر آئے گا. 

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