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

سامعین: ہم کو متحرک طور پر اس کا سائز تبدیل کر سکتے ہیں. 

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

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

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

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

سامعین: یہ ایک سے زیادہ منتقل کرتا ہے. 

اسپیکر 1: یہ ایک سے زیادہ منتقل کرتا ہے. اور، زیادہ عین مطابق ہو یہ پتہ ذخیرہ کیا جائے گا ہونا مراد ہے کہ نوڈ کے semantically بنانا اس کے لئے اگلے، ٹھیک ہے؟ تو اس کے لئے نہیں جا رہا ہے ضروری کچھ بھی منتقل. یہ صرف جا رہا ہے ہے جس میں، ایک قدر ذخیرہ ایڈریس جا رہا کسی دوسرے نوڈ کی، ہم struct کہا ہے یہی وجہ ہے کہ نوڈ ستارہ، ستارہ denoting کے ایک پوائنٹر یا ایک ایڈریس. ٹھیک ہے، تو اب آپ کو ہم فرض ہے کہ اگر ہمارے لئے دستیاب اس ن، اور چلو کسی اور ہے کہ فرض integers کے ایک پورے گچرچھی ڈالا ایک لنک کی فہرست میں. اور اس سے منسلک فہرست ہے کچھ نقطہ کی طرف سے کی طرف اشارہ ہے کہ ایک متغیر کہا جاتا فہرست ایک پیرامیٹر کے طور پر یہاں میں منظور، میں کس طرح آن لائن کے بارے میں جانا 14 تلاش کے عمل درآمد؟ دوسرے الفاظ میں، میں لاگو کرنے ہوں تو جس کا مقصد زندگی میں تقریب پھر اسے ایک int اور لینے کے لئے ہے ایک لنک کی فہرست کے آغاز، اس سے منسلک فہرست میں ایک پوائنٹر ہے. پہلے کی طرح، میں داؤد جو لگتا ہے ہمارے رضاکار، پیر کو تھا وہ کی طرف اشارہ کیا گیا تھا پوری منسلک فہرست، ہم گزر رہے ہیں، اگرچہ کے طور پر ہے ڈیوڈ یہاں ہماری دلیل کے طور پر میں. ہم کس طرح اس فہرست پار کرنیوالوں کے بارے میں جانا ہے؟ ٹھیک ہے، یہ پتہ چلا ہے کہ اگرچہ اشارہ، ہم سے اب نسبتا نئے ہیں ہم نسبتا ایسا کر سکتے ہیں straightforwardly. 

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

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

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

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

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

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

سامعین: دائیں جانب. 

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

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

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

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

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

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

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

کیوں یہ کافی نہیں ہے صرف سائز ہے کرنے کے لئے؟ ٹھیک ہے، پر وہی نمبر دھکا دو. تو میں نے کو enqueued، یا دھکیل دیا pushed--. اب میں پھر 50 ان enqueue، کریں گے اور 51، اور پھر 61، اور ڈاٹ ڈاٹ ڈاٹ. تاکہ ان enqueue ہے. میں اس وقت 61، پھر 50، 51 کو enqueued. اور یہ کہ ایک جیسی لگتی ہے اس طرح اب تک ایک اسٹیک کرنے کے لئے، سوائے میں ایک تبدیلی کرنے کے لئے کی ضرورت ہے. میں اس کے سائز کو اپ ڈیٹ کرنے کی ضرورت ہے، تو میں نے جانا اب سے تین دو سے ایک صفر سے. میں کیسے dequeue کرتے ہیں؟ کیا dequeue کے ساتھ کیا ہوتا ہے؟ کون سب سے پہلے اس فہرست سے باہر آنا چاہئے یہ ایپل اسٹور میں لائن ہے تو؟ تو 50. تو اس قسم کے trickier اس وقت ہے. آخری بار جبکہ سپر تھا آسان صرف، سائز مائنس ایک کرنا میں مؤثر طریقے سے میری صف کے آخر میں حاصل کرنے نمبر کہاں ہیں، اس 61 کو ہٹاتا ہے. لیکن میں 61 دور کرنے کے لئے نہیں کرنا چاہتا. میں، 50 لے جانا چاہتا ہوں جو 5:00 بجے وہاں تھا کے لئے سائن اپ لائن نئے آئی فون یا whatnot. اور اس طرح میں، 50 سے چھٹکارا حاصل کرنے کے لئے صرف صحیح، ایسا نہیں کر سکتے؟ مجھے پسند ہے 50 باہر پار کر سکتے ہیں. لیکن ہم صرف ہم نے کہا تو مقعد کی ضرورت نہیں ہے کے طور پر باہر فیرنا یا ڈیٹا کو چھپانے کے لئے. یہ ہے جہاں ہم صرف بھول سکتا. 

لیکن میں اب میری سائز تبدیل تو دو، یہ کافی معلومات ہے میری قطار میں چل رہا ہے معلوم کرنے کے لئے؟ سچ میں نہیں. میرے سائز، دو کی طرح لیکن قطار جہاں شروع ہوتا ہے، خاص طور پر میں اب بھی ہے تو یاد میں ان اسی تعداد. 50، 51، 61. تو میں نے یاد کرنے کی ضرورت اب سامنے ہے جہاں. اور اس میں تجویز کے طور پر وہاں، ہم صرف کہا جاتا ہے گے جن ابتدائی n- ویں سامنے، قیمت کیا ہونا چاہیے؟ زیرو، فہرست کے آغاز. لیکن اب اس کے علاوہ میں سے decrementing سائز، ہم صرف سامنے اضافہ. اب یہاں ایک اور مسئلہ ہے. لہذا میں جا رہو بار. اس کی تعداد ہے فرض کریں طرح 121، 124، اور اس کے بعد، dammit، میں جگہ سے باہر ہوں. لیکن میں نہیں ہوں، ایک منٹ رکو. کہانی میں اس وقت تو، سائز ایک، دو ہے کہ فرض، تین، چار، تو لگتا ہے کہ سائز، سامنے سے ایک ہے، چار ہے تو 51 سامنے پر ہے. میں یہاں کوئی دوسرا نمبر ڈال کرنا چاہتے ہیں، لیکن، dammit، میں جگہ سے باہر ہوں. لیکن میں نے دائیں، واقعی نہیں ہوں؟ میں کہاں کچھ ڈال سکتے ہیں 171 کی طرح اضافی قیمت،؟ جی ہاں، میں کر سکتا ہوں صرف کی قسم صحیح، واپس وہاں جانا ہے؟ اور پھر 50 سے تجاوز، یا صرف 171 کے ساتھ یہ ادلیکھت. اور آپ کو کیوں سوچ رہے ہیں تو ہماری تعداد، اتنا بے ترتیب ہے ان عام کمپیوٹر لے جایا جاتا ہے CS50 کے بعد ہارورڈ میں سائنس کے کورسز. لیکن یہ ایک اچھی اصلاح تھا، اب کیونکہ میں جگہ برباد کر نہیں کر رہا ہوں. میں اب بھی یاد کرنے کے لئے ہے کتنا بڑا اس بات کل ہے. یہ پانچ کل ہے. میں نے نہیں کرنا چاہتے کیونکہ 51 overwriting شروع. تو اب میں اب بھی جگہ سے باہر ہوں، اسی مسئلے کے طور پر سامنے. لیکن تم کس طرح اب دیکھ سکتے ہیں آپ کے کوڈ میں، آپ کو شاید ایک چھوٹا سا زیادہ لکھنا ہے پیچیدگی ایسا کرنے کے لئے. اور حقیقت میں، کیا آپریٹر C میں شاید کی اجازت دیتا ہے آپ جادوئی اس circularity ہے؟ جی ہاں modulo آپریٹر، فیصد علامت. تو ایک قطار کے بارے میں قسم کی ٹھنڈی ہے کیا، ہم ڈرائنگ arrays کے رکھنے اگرچہ اس طرح براہ راست لائنوں کے طور پر، اگر آپ قسم کی مشین curving کے طور پر اس کے بارے میں سوچنا کے ارد گرد ایک دائرے کے طور پر، تو صرف intuitively پر اس قسم کی ذہنی کام میں مزید cleanly تھوڑا سا لگتا ہے. اگر آپ اب بھی لاگو کرنے کے لئے پڑے گا کوڈ میں اس ذہنی ماڈل. ایسا نہیں ہے کہ مشکل، بالآخر،، لاگو کرنے کے لئے لیکن ہم اب بھی بلکہ، size-- کھو ہم ایسا جب تک کی صلاحیت، کا سائز تبدیل کرنے. 

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

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

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

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

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

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

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

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

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

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

تو اس قسم کے پاگل لگتا ہے، اور یہ ہے. یہ ایک contrived مثال ہے، لیکن یہ نمائندہ ہے حملہ ویکٹر کے ایک طبقے کی، پروگرام پر حملہ کرنے کا ایک طریقہ. سب ٹھیک ہے اور صارف تو اچھا ہے 11 حروف ہے کہ ایک لفظ میں اقسام کم، کے علاوہ الٹا سلیش صفر یا. کیا ہے کے مقابلے میں صارف کی اقسام زیادہ تو 11 یا 12 یا 20 یا 50 حروف؟ ایسا کرنے کے لئے جا رہے اس پروگرام کیا ہے؟ ممکنہ طور پر seg غلطی. یہ جا رہا ہے آنکھ بند کر کے اپ بار میں سب کچھ کاپی کرنے کے لئے ہے جس میں اس کی لمبائی، کرنے کے لئے لفظی بار میں سب کچھ، پتہ میں سی لیکن C کی طرف اشارہ صرف اس preemptively 12 بائٹس کے طور پر دیا ہے. لیکن کوئی اضافی جانچ پڑتال. حالات تو کوئی نہیں ہے. یہاں کی جانچ پڑتال کوئی خرابی نہیں ہے. 

اور اس طرح یہ پروگرام کیا ہے کیا جا رہا ہے صرف آنکھ بند کر دوسرے سے ایک چیز کاپی. اور ہم اس کو اپنی طرف متوجہ ہے ایک تصویر کے طور پر، یہاں ہے میموری کی جگہ کے صرف ایک SLIVER. تو ہم، نچلے حصے میں محسوس مقامی متغیر بار ہے. store-- جا رہا ہے کہ اس پوائنٹر تو ہے کہ مقامی دلیل بلکہ سٹرنگ بار ذخیرہ کرنے کے لئے جا رہا. اور پھر صرف محسوس اس کے اوپر ایک اسٹیک میں، کیونکہ تم سے پوچھنا ہر وقت اسٹیک پر میموری کے لئے، یہ تھوڑا سا ہے pictorially کا اس کے اوپر، ہم وہاں 12 بائٹس مل گیا ہے کہ نوٹس. سب سے اوپر بائیں ایک سی بریکٹ صفر ہے سب سے نیچے دائیں ایک سی بریکٹ 11. یہ صرف کمپیوٹرز ہے اسے باہر رکھ کے جا. تو صرف intuitively، بار سے زیادہ ہے تو سمیت مجموعی میں 12 حروف، کے مقابلے میں کہاں ہے الٹا سلیش صفر، 12 یا سی بریکٹ 12 جانے کے لئے جا رہے ہیں؟ یا بلکہ جہاں کے 12th ہے کردار یا کردار کی 13th، جا سووان کردار تصویر میں ختم کرنے کے لئے؟ اوپر یا نیچے؟ 

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

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

دوسرے الفاظ میں، اگر صارف، فوری طور پر ٹائپ کر رہا ہے صرف کچھ نہیں ہے ہیلو، معصوم کی طرح لیکن یہ برابر ہے کہ کوڈ اصل ہے اس رکن کی تمام فائلوں کو حذف کرنے کے لئے؟ یا مجھ سے ان کے پاس ورڈ کو ای میل؟ یا لاگنگ کو شروع ان keystrokes کے، ٹھیک ہے؟ ایک راستہ ہے،، آج شرط دو وہ خوش نہ صرف میں ٹائپ کر سکتے ہیں کہ دنیا یا ان کے نام، وہ بنیادی طور پر کر سکتے ہیں کوڈ، zeros کی میں منتقل اور لوگ، کہ کمپیوٹر کوڈ اور ایک ایڈریس دونوں کے لئے غلطیوں. سہی تو کسی حد تک abstractly، تو کافی معاندانہ کوڈ میں صارف اقسام ہم یہاں کے طور پر عام کریں گے کہ اے ایک حملے یا مخالف ہے. تو بری چیزیں. ہم کے بارے میں پرواہ نہیں کرتے تعداد یا zeros یا لوگ آج، آپ کو اس طرح ختم ہے کہ اس سرخ سیکشن overwriting کی، بائٹس کی اس ترتیب محسوس. اے 835 سی صفر آٹھ صفر. اور اب یہاں وکیپیڈیا مضمون کے طور پر اب آپ اصل میں شروع تو، تجویز پیش کی ہے آپ کے کمپیوٹر میں بائٹس لیبل میموری، وکی پیڈیا کا مضمون ہے تجویز ہے، کہ کیا پتہ تو کہ سب سے اوپر بائیں بائٹ کی 80 C 0 3508 ہے. 

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

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

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

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

بالکل، میں چاہتا ہوں بائیں بچے تلاش، اس تصویر کے بائیں ذیلی درخت. اور حقیقت میں، مجھے کے ذریعے دو یہاں نیچے تصویر صرف ایک لمحے کے لئے، کے بعد میں نے اس سے باہر فیرنا نہیں کر سکتے. میں 55 میں یہاں شروع، اور اگر میں جانتا ہوں کہ قیمت 44 کرنے کے لئے ہے میں دیکھ رہا ہوں بائیں، اس طرح ہے کی میں فون بک پھاڑنا طرح نصف یا نصف میں درخت پھاڑنا. میں اب کے بارے میں دیکھ بھال کرنا ہے درخت کے اس پورے آدھے. اور ابھی تک، دلچسپ کے لحاظ سے ساخت، یہاں اس سے زیادہ اس بات ، 33 کے ساتھ شروع ہوتا ہے کہ خود ایک بائنری تلاش درخت ہے. میں اس سے پہلے لفظ پنراورتی کہا یقینا یہ ایک آنکڑا ڈھانچہ ہے کہ تعریف کی طرف سے پنراورتی ہے. آپ کو اس ہے کہ ایک درخت ہو سکتا ہے بڑے، لیکن اپنے بچوں میں سے ہر ایک چھوٹے صرف ایک چھوٹا سا ایک درخت کی نمائندگی کرتا ہے. بجائے اس کے دادا ہونے یا دادی، اب یہ صرف ماں ہے or-- میں ماں say-- نہیں کر سکتے ہیں یا والد صاحب، کہ عجیب ہو گا. کی بجائے دو بچوں بھائی اور بھائی کی طرح ہو جائے گا. خاندان کے درخت کی ایک نئی نسل. لیکن ساخت، یہ ایک ہی خیال ہے. اور اس میں ایک تقریب ہے باہر کر دیتا ہے جس کے ساتھ میں ایک بائنری تلاش کر سکتے ہیں درخت. یہ تلاش کہا جاتا ہے. میں درخت تیر بائیں سمت میں (ن) کے لئے تلاش (ن) کی قیمت سے زیادہ ہے اور اگر کہ میں اس وقت پر ہوں. ایک لمحے پہلے کہانی میں 55. میں نامی ایک تقریب ہے تلاش ہے کہ میں صرف کر سکتے ہیں (ن) اس کو منتقل کرنے اور تکراری تلاش ذیلی درخت اور صرف واپسی جو کچھ بھی اس کا جواب. ورنہ میں یہاں کچھ حتمی بنیاد کیس مل گیا ہے. 

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

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

اس طرح کے اکشمتا یہاں ہے. کس طرح intuitively پر تم کروگی جرمن پرچم سکیڑیں ایک فائل کے طور پر اس پر عمل درآمد ہے؟ کیا معلومات کی طرح ہم نہیں کر سکتے حکم میں ڈسک پر محفوظ کرنے کی زحمت طرح سے ہماری فائل کے سائز کو کم کرنے کے لئے ایک kilobyte، کچھ کرنے کے لئے ایک میگا بائٹ چھوٹے؟ جس فالتوپن جھوٹ یہاں واضح ہو کرنے کے لئے؟ آپ کیا کر سکتے ہیں؟ جی ہاں؟ بالکل. کیوں نہیں بجائے یاد ہر رفو پکسل کا رنگ خصوصا آپ PSET4 میں کر رہے ہیں کی طرح بٹ نقشہ فائل کی شکل کے ساتھ، کیوں آپ کو صرف کی نمائندگی نہیں کرتے مثال کے طور پر پکسلز کی leftmost کالم، سیاہ پکسلز کے ایک گروپ، ایک گروپ سرخ رنگ کے، اور پیلے رنگ کا ایک گروپ، اور پھر صرف کسی نہ کسی طرح انکوڈ دوبارہ کا خیال یہ 100 اوقات یا اس 1،000 بار دہرائیں؟ جہاں 100 یا 1،000 ہے صرف ایک عددی، آپ تو صرف ایک بڑی تعداد کے ساتھ دور حاصل کر سکتے ہیں بجائے سینکڑوں یا ہزاروں کی کی اضافی پکسلز. اور بے شک، کہ ہم کس طرح ہے جرمن پرچم سکیڑیں کر سکتے ہیں. اور فرانسیسی پرچم کے بارے میں اب کیا ہوگا؟ کسی قسم کی اور ایک چھوٹا سا ذہنی ورزش، جو پرچم ڈسک پر زیادہ اکٹھا کیا جا سکتا ہے؟ جرمن پرچم یا فرانسیسی پرچم، ہم اس نقطہ نظر لے تو کیا ہوگا؟ جرمن پرچم، کیونکہ وہاں زیادہ افقی فالتوپن. اور ڈیزائن کی طرف سے، بہت سے تصویری فائل فارمیٹس واقعی کے طور پر اسکین لائنوں کام کرتے ہیں افقی. وہ کام کر سکتے ہیں عمودی طور پر، صرف انسانیت فیصلہ سال پہلے ہم کریں گے عام طور پر چیزوں کو صف کے بارے میں سوچنا کالم کی طرف سے صف کی بجائے کالم کی طرف سے. تو یقینا تم تھے تو فائل کو دیکھنے کے لئے ایک جرمن پرچم اور ایک فرانسیسی کا سائز پرچم، اتنی دیر تک حل ہے اسی، اسی کی چوڑائی اور اونچائی، اس میں سے ایک یہاں، بڑا ہونے جا رہا ہے آپ کی وجہ سے اپنے تین بار دوبارہ کرنا پڑے. آپ کو نیلے رنگ، دوبارہ کی وضاحت کرنا پڑے اپنے آپ کو، سفید، سرخ، اپنے آپ کو دہرانے اپنے آپ کو دہرانے. آپ کو صرف تمام نہیں جا سکتا درست کرنے کے لئے راستہ. اور ایک ایک طرف کے طور پر، بنانے کے لئے سمپیڑن صاف ان ہیں تو، ہر جگہ ہے ایک video-- سے چار فریم آپ ایک فلم یاد ہے کہ ہو سکتا ہے یا ویڈیو عام طور پر ہے فی سیکنڈ 29 یا 30 فریم کی طرح. یہ ایک چھوٹا سا فلپ کتاب کی طرح ہے جہاں آپ صرف تصویر، تصویر، تصویر، تصویر کو دیکھنے کے، تصویر صرف سپر روزہ تو اس کی طرح لگتا ہے سکرین پر اداکاروں آگے بڑھ رہے ہیں. یہاں ایک bumblebee کی پر ہے پھولوں کی ایک گروپ کے سب سے اوپر. اور اس قسم کی ہو سکتا ہے، اگرچہ پہلی نظر میں دیکھنے کے لئے مشکل، میں آگے بڑھ صرف ایک ہی چیز اس فلم مکھی ہے. 

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

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

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

میں نے؟ میں نے؟ یا کیا about-- یا میں؟ شاید یہ صرف دو ای کا حق تھا؟ تو یہ مسئلہ ہے مورس کے ساتھ decodability کی کوڈ، جس کے تحت جب تک آپ کو پیغام بھیجنے شخص اصل میں تم میں سے الگ الگ کر سکتے وقفہ دیکھیں یا حروف کے درمیان فرق سن، یہ صرف کرنے کے لئے کافی نہیں ہے zeros اور ہیں کی ایک ندی بھیج، یا نقطوں کی اور ڈیش، ابہام نہیں ہے کیونکہ. ای ایک نقطہ ہے، لہذا آپ کو تو دو بندیاں دیکھیں یا دو بندیاں سن، شاید یہ دو ای کا ہے یا شاید یہ ایک میں ہے تو ہم نے ایک ہے کہ ایک نظام کی ضرورت ہے اس سے بھی زیادہ ہوشیار تھوڑا. تو ایک شخص کا نام ہے Huffman سال پہلے بالکل اس کے ساتھ آئے تھے. تو ہم صرف جا رہے ہیں ایک فوری نظر لینے کے لئے کس طرح درخت اس کے متعلق ہیں. یہ کچھ ہے کہ مان لیں آپ بھیجنا چاہتے بیوکوف پیغام، صرف ایک، B کے پر مشتمل، سی ڈی کی اور ای، لیکن فالتوپن کے ایک بہت کچھ یہاں ہے. یہ انگریزی ہونا مراد نہیں ہے. یہ مرموز نہیں ہے. یہ صرف ایک پاگل پیغام ہے تکرار کے بہت سے. آپ اصل میں باہر شمار تو تمام ایک کے، B کی، سی، D 'ے، اور ای، یہاں ہے تعدد. حروف کی 20٪ ہیں ایک کے، حروف کی 45٪ E کی، اور تین دیگر تعدد ہیں. ہم دستی وہاں شمار اور صرف ریاضی کیا. 

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

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

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

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

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

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

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

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

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

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

تو اس کی ساخت ہے. اور یہ ہماری آخری ہے آج کے لئے ڈھانچہ، جو ایک trie کہا جاتا ہے کچھ ہے. کسی وجہ کے لئے مختصر ہے جس T-R-میں-E، حاصل کرنے کے لئے، لیکن یہ trie کے کہا جاتا ہے. تو ایک trie ایک اور دلچسپ ہے ان خیالات کی ایک بہت کے ٹولے کی شکل. یہ ہم نے پہلے دیکھا ہے جس میں ایک درخت، ہے. یہ ایک بائنری تلاش درخت نہیں ہے. یہ بچوں کی کسی بھی تعداد کے ساتھ ایک درخت ہے لیکن ایک trie میں بچوں میں سے ہر ایک ایک صف ہے. سائز کے ایک صف،، 26 یا شاید 27 کا کہنا ہے کہ آپ hyphenated ناموں کی حمایت کرنا چاہتے ہیں تو یا لوگوں کے ناموں میں apostrophes. 

اور اس طرح یہ ایک آنکڑا ڈھانچہ ہے. اور آپ سب سے اوپر کی طرف سے نظر آتے ہیں تو سب سے نیچے، طرح اگر آپ ، وہاں سب سے نوڈ، ایم دیکھو وہاں کہ leftmost بات کی طرف اشارہ کرتے ہوئے، جو اس کے بعد ایک، ایکس، W، E، L، ایل یہ ہے صرف ایک آنکڑا ڈھانچہ ہے کہ منمانے لوگوں کے نام محفوظ ہے. اور میکسویل صرف مندرجہ ذیل کی طرف سے محفوظ کیا جاتا ہے سرنی سرنی سرنی کے راستے. ایک trie کے بارے میں لیکن حیرت انگیز ہے ، کہ ایک لنک کی فہرست جبکہ اور یہاں تک کہ ایک صف، ہم نے کبھی ملا ہے سب سے بہتر ہے لکیری وقت یا لوگارتمی وقت تلاش کر رہے کسی کو. ایک trie کی اس آنکڑا ڈھانچہ، تو میں میرے اعداد و شمار کے ڈھانچے میں ایک نام ہے اور میں میکسویل کے لئے تلاش کر رہا ہوں، میں ہوں بہت تیزی سے اس کو تلاش کرنے کے لئے جا. میں صرف ایم-اے-ایکس ڈبلیو ای ایل ایل کے لئے نظر آتے ہیں. تو یہ آنکڑا ڈھانچہ، اس کے برعکس کی طرف سے، ایک وہاں ہے تو (ن)، ایک ملین ہے یہ آنکڑا ڈھانچہ میں ملین ناموں، میکسویل اب بھی کی جا رہی ہے دریافت صرف ایم-اے-ایکس ڈبلیو ای ایل ایل کے بعد اقدامات. اور David-- ڈی-اے-وی میں ڈی اقدامات. دوسرے الفاظ میں، کی تعمیر کی طرف ہے کہ ایک آنکڑا ڈھانچہ ملا یہ arrays کے تمام، جن میں سے سب خود، بے ترتیب تک رسائی کی حمایت میں نے لوگوں کی طرف دیکھ کر شروع کر سکتے ہیں ہے کہ وقت کی رقم کا استعمال کرتے ہوئے نام نہ تعداد کے متناسب آنکڑا ڈھانچہ میں چیزوں کی، کی طرح ایک ملین موجودہ نام. اسے تلاش کرنے کے مجھ سے لیتا ہے وقت کی رقم ایم-اے-ایکس ڈبلیو ای ایل ایل یہ آنکڑا ڈھانچہ میں ہے متناسب نہ کرنے آنکڑا ڈھانچہ کا سائز، لیکن نام کی لمبائی. اور حقیقت پسندانہ ناموں ہم تلاش کر رہے ہیں کبھی نہیں طویل پاگل جا رہے ہیں. شاید کسی ایک 10 کردار ہے ، 20 کردار نام کا نام. یہ درست ہے، یقینی طور پر محدود ہے؟ زمین پر ایک انسانی نہیں ہے جو سب سے طویل ممکن نام ہے، لیکن اس کا نام ایک مسلسل جاری ہے قیمت کی حد کے، ٹھیک ہے؟ یہ کسی بھی معنی میں سے مختلف نہیں ہے. تو اس طرح میں، ہم نے ایک آنکڑا ڈھانچہ حاصل جو مسلسل وقت نظر اپ ہے. یہ اقدامات کی ایک بڑی تعداد لے کرتا ہے ان پٹ کی لمبائی پر منحصر، کا نام نہیں بلکہ تعداد آنکڑا ڈھانچہ میں. ہم نام کی تعداد دگنی تو ایک ارب سے دو سے اگلے سال، تلاش میکسویل لے جا رہا ہے سات اقدامات کے عین مطابق ایک ہی نمبر اسے تلاش کرنے. اور اس طرح ہم حاصل ہے لگ رہے ہو وقت چل رہا ہے کے بارے میں ہمارے مقدس grail. 

اتنی جلدی اعلانات کے ایک جوڑے. کوئز صفر آ رہا ہے. کورس کی ویب سائٹ پر اس پر مزید دن کے اگلے دو سے زیادہ. پیر کے روز یہ ایک چھٹی ہے lecture-- یہاں ہارورڈ میں پیر کو. یہ، نیو ہیون میں نہیں ہے تو ہم کلاس لے رہے ہیں پیر کو لیکچر کے لئے نیو ہیون سے. سب کچھ فلمایا جائے گا اور ہمیشہ کی طرح براہ راست سلسلہ لیکن آج ختم دو ایک 30 دوسری کلپ کے ساتھ نام نہاد "گہری خیالات" Daven Farnham، کی طرف سے جو Saturday کی طرف سے گزشتہ سال سے حوصلہ افزائی ہوئی رات لائیو کے "گہرے خیالات" جیک ہاتھ، کی طرف سے جو اب احساس کرنا چاہیے. 

فلم: اور اب، "گہرے Daven Farnham طرف خیالات ". ہیش کی میز. 

اسپیکر 1: ٹھیک ہے، کہ اب کے لئے ہے. ہم اگلے ہفتے آپ کو نظر آئے گا. 

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

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

IAN: واہ، واہ، واہ، کٹ، کٹ، کٹ، کاٹ. ڈوگ، آپ کو صرف یس دا نہیں کر سکتے ہیں، یس دا، یس دا، ضم طرح کے ذریعے اپنا راستہ. 

ڈوگ: میں صرف کیا. ٹھیک ہے. ہم کو جانا اچھا ہو. صرف رولنگ رکھ دو. تو ویسے بھی، 

IAN: آپ کی وضاحت کرنے کے لئے ہے یہ زیادہ مکمل طور پر اس کے مقابلے میں. یہ صرف کافی نہیں ہے. ڈوگ: ایان، ہم ایسا نہیں کرتے ایک کے لئے واپس جانے کی ضرورت. ٹھیک ہے. تو ویسے بھی، ہم merge-- ساتھ جاری رکھتے ہیں تو ایان، ہم فلم کے وسط میں ہیں. 

IAN: مجھے معلوم ہے. اور ہم صرف یس دا نہیں کر سکتے ہیں، یس دا، پورے عمل کے ذریعے یس دا،. تم کس طرح کی وضاحت کرنے کے لئے ہے دونوں فریقوں کو مل ضم حاصل. 

ڈوگ لیکن ہم نے پہلے ہی ہے وضاحت کس طرح دو sides-- 

IAN: تم بس دکھایا گیا ہے انہیں ایک ضم سرنی. ڈوگ: وہ عمل معلوم. وہ بھی ٹھیک ہیں. ہم اس پر دس بار چلا گیا ہے. 

IAN: آپ کو صرف صحیح اس پر چھوڑا. ہم ایک کے پاس واپس جا رہے ہیں، آپ اس سے زیادہ آپ یس دا، یس دا نہیں کر سکتے ہیں. واپس ایک ٹھیک،. 

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

IAN: ٹھیک. آپ تیار ہیں؟ عظیم. ایکشن.