>> KEVIN شمد: کبھی کبھی، تعمیر جب ایک پروگرام آپ کو استعمال کرنے کے لئے چاہتے ہو سکتا ہے ایک
ایک ڈکشنری کے طور پر جانا جاتا ہے کے اعداد و شمار کے ڈھانچے.
ہیں جس کی لغت نقشے چابیاں، عام طور پر ڈور، اقدار، ints کے،
حروف، کچھ اعتراض پوائنٹر، ہم چاہتے ہیں جو کچھ بھی.
یہ صرف عام لغات کی طرح ہے تعریف کے ذریعے اس کا نقشہ الفاظ.
>> لغات کے ساتھ ہمیں فراہم معلومات جمع کرنے کی صلاحیت
کچھ کے ساتھ منسلک اور بعد میں اس کو نظر آتے ہیں.
تو کس طرح ہم اصل پر عمل درآمد کرتے C کوڈ، کا کہنا ہے کہ، میں پیدا ہے کہ ہم کر سکتے ہیں
ہمارے پروگراموں میں سے ایک میں استعمال کرتے ہیں؟
ٹھیک ہے، کے طریقوں میں سے ایک بہت ہیں ہم ایک لغت پر عمل درآمد کر سکتے ہیں.
>> ایک کے لئے، ہم ایک صف کا استعمال کر سکتا ہے کہ ہم متحرک طور پر دوبارہ سائز یا ہم ایک استعمال کر سکتے ہیں
لنک کی فہرست، ہیش کی میز یا ایک بائنری درخت.
لیکن ہم کا انتخاب کرتے ہیں جو کچھ بھی، ہمیں چاہئے کارکردگی کا احساس ہو اور
عمل کی کارکردگی.
ہم نے استعمال کیا الگورتھم بارے میں سوچنا چاہیے داخل کریں اور میں اشیاء کو تلاش کرنے کے لئے
ہمارے اعداد و شمار کا ڈھانچہ.
>> اب کے لئے، کہ ہم فرض کرتے ہیں چابیاں کے طور پر ڈور کے استعمال کرنا چاہتے ہیں.
ایک امکان کے بارے میں بات کرتے ہیں، ایک آنکڑا ڈھانچہ ایک trie کہا جاتا ہے.
تو یہاں ایک بصری نمائندگی ہے ایک trie کی.
>> تصویر، ایک trie سے پتہ چلتا ہے کے ساتھ ایک درخت کے اعداد و شمار کی ساخت ہے
نوڈس کے ساتھ مل کر منسلک.
ہم ایک جڑ کی واضح طور پر ہے کہ دیکھ کچھ لنکس تک ساتھ نوڈ
دیگر مراکز.
لیکن ہر نوڈ کس پر مشتمل ہے؟
ہم چابیاں ذخیرہ کرنے کر رہے ہیں کہ اگر فرض صرف اکشراتمک حروف، اور اس کے ساتھ
ہم بڑے حروف تہجی کی پرواہ نہیں کرتے، یہاں ایک نوڈ کی تعریف ہے
کافی.
>> جس کی قسم ایک اعتراض struct ہے نوڈ کے دو حصے ہیں
اعداد و شمار اور بچوں کو بلایا.
ہم نے ایک تبصرہ کے طور پر اعداد و شمار کے ایک حصے کے کے چھوڑ دیا ایک جزو کی طرف سے تبدیل کیا جائے گا
struct نوڈ ہے جب اعلان سی کے ایک پروگرام میں شامل کر لیا.
ایک نوڈ کے اعداد و شمار حصہ ہو سکتا ہے اس بات کی نشاندہی کرنے کے لئے بولین قدر یا
نہیں نوڈ تکمیل کی نمائندگی کرتا ہے ایک ڈکشنری کلید کے یا یہ ایک ہو سکتا ہے
تعریف کی نمائندگی تار لغت میں ایک لفظ کے.
>> ہم اس بات کی نشاندہی کرنے کے لئے ایک جذباتیہ استعمال کریں گے اعداد و شمار کے ایک نوڈ میں موجود ہے جب.
26 عناصر ہیں ہماری بچوں کی صف، ایک انڈیکس
الفبایی کردار فی.
ہم اہمیت دیکھیں گے جلد ہی اس کے.
>> کی جڑ نوڈ کا ایک بہت قریب نظر حاصل کرتے ہیں ہمارے میں ڈایا گرام، جس میں کوئی اعداد و شمار نہیں ہے
کی طرف اشارہ کے طور پر، اس کے ساتھ منسلک میں جذباتیہ کی غیر موجودگی
اعداد و شمار کے حصہ.
کے کچھ حصوں کی طرف سے فراہم تیر بچوں کی صف غیر نوڈ کی نمائندگی کرتے ہیں
دیگر نوڈس اشارہ.
مثال کے طور پر، تیر کی طرف سے فراہم بچوں کے دوسرے عنصر
خط B کی نمائندگی کرتا ہے ایک ڈکشنری کلید میں.
اور بڑے خاکہ میں ہم ایک بی کے ساتھ یہ لیبل
>> ، بڑے خاکہ میں نوٹ کریں کہ جب ہم دوسرے نوڈ پوائنٹر کو اپنی طرف متوجہ، اس
کوئی فرق نہیں پڑتا جہاں نوک تیر کہ دوسرے نوڈ سے ملاقات کی.
ہمارے نمونے لغت trie کے پر مشتمل ہے دو الفاظ، اور زوم.
کی ایک مثال کے ذریعے چلنے دو ایک چابی کے لئے اعداد و شمار کو دیکھ.
>> ہم تلاش کرنے کے لئے کرنا چاہتا تھا مان اہم غسل کے لئے قیمت کے مطابق.
ہم اپنی نظر کو شروع کریں گے جڑ نوڈ میں.
پھر ہم ہمارے کے پہلے حرف کو لے جائیں گے ، اہم بی، اور اسی کی تلاش
ہمارے بچوں کی صف میں جگہ.
بالکل 26 مقامات رہے ہیں کہ نوٹس صف، میں سے ہر ایک خط کے لئے ایک میں
حروف.
اور ہم دھبوں کی نمائندگی پڑے گا آرڈر میں حروف تہجی کے خط.
>> ہم، پھر دوسری انڈیکس میں دیکھتا ہوں عام طور پر بی لئے انڈیکس ایک،، تو ہم
کچھ الفبایی کردار سی ہم اسی جگہ کا تعین کر سکتے ہیں
کا استعمال کرتے ہوئے بچوں کی صف میں اس طرح ایک حساب.
ہم نے ایک بڑی بچوں کے استعمال کیا جا سکتا ہم نظر تک کی پیشکش کرنا چاہتے تھے صف تو
حروف کی ایک وسیع رینج کے ساتھ چابیاں، اس طرح پورے طور پر
ASCII کیریکٹر سیٹ.
>> اس صورت میں، پوائنٹر ہمارے بچوں کی صف میں
انڈیکس ایک خالی نہیں ہے.
تو ہم تلاش جاری رکھیں گے اہم غسل کو.
ہم نے کبھی شہوت انگیز null پوائنٹر کا سامنا کرنا پڑا ہے تو بچوں میں مناسب جگہ پر
صف ہم نوڈس طے کرتے ہوئے، تو ہم کہ ہم کہنا پڑے گا
کہ چابی کے لئے کچھ بھی نہیں ملا.
>> اب، ہم دوسرے خط کے لے جائیں گے ہمارے اہم، ایک، اور جاری رکھیں مندرجہ ذیل
اس طرح اشارہ ہم تک ہمارے اہم کے آخر تک پہنچنے.
ہم بغیر چابی کے آخر تک پہنچ جائیں تو کسی مردہ ختم مار، شہوت انگیز null اشارہ،
صورت یہاں ہے، تو ہم صرف ایک اور بات کی جانچ پڑتال کرنے کے لئے ہے.
اس کی کلید ہے اصل میں لغت میں؟
>> اگر ایسا ہے تو، ہم ایک اچھی طرح سے، ایک قدر کو تلاش کرنا چاہئے ہماری خاکہ میں جذباتیہ آئکن جہاں
لفظ ختم ہو جاتی ہے.
کے ساتھ محفوظ کیا کچھ اور ہے تو کے اعداد و شمار، تو ہم اسے واپس آ سکتے ہیں.
مثال کے طور پر، اہم چڑیا گھر میں نہیں ہے ہم کر سکتے ہیں، اگرچہ لغت،
کبھی بغیر اس چابی کے آخر تک پہنچ ، شہوت انگیز null پوائنٹر مارنے جبکہ ہم
trie کے ذریعے iterate.
>> ہم، اہم غسل نظر کرنے کی کوشش کی تو آخری نوڈ کی صف انڈیکس دوسری،
، خط H کرنے کے لئے کرے گا اسی شہوت انگیز null پوائنٹر منعقد کیا ہے.
تو غسل لغت میں نہیں ہے.
اور اس طرح ایک trie چابیاں کہ میں منفرد ہے واضح طور پر میں ذخیرہ کبھی نہیں رہے ہیں
آنکڑا ڈھانچہ.
تو ہم کس طرح کچھ داخل ہے ایک trie میں؟
>> کی کلید داخل ہیں ہمارے trie میں چڑیا گھر.
یاد رکھیں کہ ایک نوڈ میں ایک حرکت کا سامنا ایک سادہ کرنے کے لئے کوڈ میں کے مطابق کر سکتے ہیں
کہ چڑیا گھر کی نشاندہی کرنے کے بولین قیمت لغت میں ہے یا یہ کر سکتے ہیں
مزید معلومات کے مطابق کہ ہم اہم چڑیا گھر کے ساتھ منسلک کرنا چاہتے ہیں،
کی تعریف کی طرح لفظ یا کچھ اور.
کچھ طریقوں سے، عمل کو شامل کرنے کے ایک trie میں کچھ اسی طرح کی ہے
ایک trie میں کچھ تلاش.
>> ہم، پھر جڑ نوڈ کے ساتھ شروع کریں گے مندرجہ ذیل اشارہ کے مطابق
ہمارے اہم کے خط.
خوش قسمتی سے، ہم اشارہ کی پیروی کرنے کے قابل تھے ہم تک تمام راستہ
کلید کے اختتام.
چڑیاگھر لفظ کے ایک سابقہ ​​ہے کے ایک رکن ہے جس میں زوم،
ڈکشنری، ہم کرنے کی ضرورت نہیں کسی بھی نئے مراکز مختص.
>> ہم اس بات کی نشاندہی کرنے کے لئے نوڈ پر نظر ثانی کر سکتے ہیں کے نتیجے میں حروف کی راہ
اس سے ہماری لغت میں ایک اہم کی نمائندگی کرتا ہے.
اب، داخل کرنے کی کوشش کریں trie کے میں اہم غسل.
ہم جڑ نوڈ میں شروع کریں گے اور پھر اشارہ پر عمل کریں.
لیکن اس صورت حال میں، ہم نے ایک مردہ مارا ہم پر حاصل کرنے کے قابل ہونے سے پہلے ختم
کلید کے اختتام.
اب، ہم کچھ نئے مختص کرنے کی ضرورت ہو گی نوڈس ایک نیا مختص کرنے کی ضرورت ہو گی
ہر باقی کے لئے نوڈ ہمارے اہم خط.
>> اس صورت میں، ہم صرف ضرورت ایک نیا نوڈ مختص کرنے کی.
پھر ہم ایچ انڈیکس بنانے کے لئے کی ضرورت ہو گی اس نئے نوڈ کا حوالہ.
ایک بار پھر، ہم نوڈ میں ترمیم کرسکتے ہیں ظاہر ہوتا ہے کہ حروف کی راہ
اس کے نتیجے میں ایک کی نمائندگی کرتا ہے ہماری لغت میں اہم.
کی asymptotic کے بارے میں بات کرتے ہیں ان کے لئے ہمارے طریقہ کار کی پیچیدگی
دو آپریشن.
>> ہم محسوس ہے کہ دونوں صورتوں میں نمبر کی ہماری الگورتھم گیا تھا لیا اقدامات
کی تعداد کے متناسب مطلوبہ الفاظ میں حروف.
یہ ٹھیک ہے.
آپ کو ایک میں ایک لفظ تلاش کرنے کے لئے چاہتے ہیں تو trie کے آپ صرف کے ذریعے iterate کرنے کی ضرورت ہے
حروف ایک ایک کر کے آپ جب تک یا تو لفظ کے آخر یا تک پہنچنے
trie میں ایک مردہ آخر مارا.
>> اور تم ایک کلید داخل کرنا چاہتے ہیں جب کا استعمال کرتے ہوئے ایک trie میں قیمت جوڑی
ضابطے کی ہم، بدترین کیس پر تبادلہ خیال اگر آپ کو ایک نیا نوڈ مختص ہوگا
ہر ایک خط کے لئے.
اور ہم اس مختص فرض کریں گے ایک مسلسل وقت آپریشن ہے.
ہم اہم لمبائی ہے فرض ہے کہ اگر ایسا ہے تو ایک مقررہ مسلسل، دونوں کی طرف سے جکڑے ہوئے
اندراج اور نظر مسلسل ہیں ایک trie کے لئے وقت آپریشن.
>> ہم اس مفروضہ نہیں ہے تو اس اہم لمبائی ایک مقررہ طرف سے جکڑے ہوئے ہے
مسلسل، تو اندراج اور دیکھو، بدترین صورت میں، میں لکیری ہیں
کلید کی لمبائی.
اشیاء کی تعداد ذخیرہ نوٹس ہے کہ trie میں نظر کو متاثر نہیں کرتا
یا اندراج کے وقت.
یہ صرف کی طرف سے متاثر ہے کلید کی لمبائی.
>> کے برعکس، کا کہنا ہے کہ، کے لئے اندراجات انہوں نے مزید کہا، ایک ہیش ٹیبل بنانے کے لئے جاتا ہے
مستقبل سست نظر.
یہ سب سے پہلے میں کشش کی آواز، کر سکتے ہیں ہم اس بات کو ذہن میں رکھنا چاہئے کہ ایک
سازگار asymptotic پیچیدگی نہیں ہے مطلب ہے کہ عملی طور پر اعداد و شمار کے
ساخت ضروری ہے نندا سے باہر.
ہم نے ذخیرہ کرنے کے لئے غور کریں کہ ضروری ہے سب سے زیادہ میں ہم نے کی ضرورت ہے ایک trie، میں لفظ
کیس، مراکز کی ایک بڑی تعداد متناسب لفظ خود کی لمبائی.
>> کوشش کرتا ہے خلا کی ایک بہت استعمال کرتے ہیں.
یہ ایک ہیش کی میز پر اس کے برعکس ہے، ہم صرف ایک نئے نوڈ کی ضرورت ہے
کچھ کلیدی قدر جوڑی ذخیرہ.
اب، پھر اصول میں، بڑی جگہ کی کھپت ایک بڑا نہیں لگتا
خاص طور پر دیا، نمٹنے کے کہ جدید کمپیوٹر گیگا بائٹس ہے اور
میموری کی گیگا بائٹس.
لیکن یہ ہم اب بھی پتہ چلا ہے کہ میموری کے استعمال اور اس کے بارے میں فکر کرنے کی
کے لئے تنظیم کارکردگی، کے بعد سے جدید کمپیوٹرز
کے تحت جگہ میں میکانزم ہے میموری رسائی کی رفتار تیز کرنے ڈاکو.
>> لیکن ان کے طریقہ کار سب سے بہترین ہے جب کام میموری رسائی کمپیکٹ میں بنائے جاتے ہیں
خطے یا علاقوں.
اور ایک trie کے مراکز رہائش پذیر کر سکتے ہیں کہ ڈھیر میں کہیں بھی.
لیکن یہ تجارت آف ہیں ہم غور کرنا ضروری ہے.
>> ایک ڈیٹا کا انتخاب کرتے وقت، یاد رکھیں کہ ایک خاص کام کے لئے ڈھانچہ، ہم
کے بارے میں سوچنا چاہئے کس قسم کی آپریشن کے اعداد و شمار کے ڈھانچے کی ضرورت ہے
حمایت اور کس طرح زیادہ سے زیادہ کارکردگی ان میں سے ہر ایک کی
ہم سے آپریشن کے معاملات.
یہ آپریشن بھی کر سکتے ہیں بس سے باہر توسیع
بنیادی نظر اپ اور اندراج.
ہم نے ایک قسم کو لاگو کرنے کے لئے کرنا چاہتا تھا مان آٹو مکمل فعالیت کے، زیادہ سے زیادہ
کی طرح گوگل تلاش کے انجن کی ہے.
یہ ہے کہ، تمام چابیاں واپس اور ممکنہ طور پر اقدار جس میں
ایک دیا سابقہ ​​ہے.
>> ایک trie منفرد مفید ہے اس آپریشن کے لئے.
اس کے ذریعے iterate کرنے کے لئے براہ راست ہر کردار کے لئے trie کے
سابقہ.
صرف ایک نظر کے آپریشن کی طرح ہم اشارہ کی پیروی کر سکتے
کردار سے کردار.
اس کے بعد، ہم کے اختتام پر پہنچنے کے بعد سابقہ، ہم کے ذریعے iterate کر سکتے ہیں
اعداد و شمار کے ڈھانچے کے باقی حصے چابیاں کے کسی بھی باہر کے بعد
اس نقطہ سابقہ ​​ہے.
>> اس لسٹنگ کو حاصل کرنے کے لئے بھی آسان ہے کے بعد حروف تہجی کی ترتیب میں
بچوں کی صف کے عناصر حروف تہجی کے مطابق ہیں.
تو امید ہے کہ آپ غور کریں گے دینے کی کوشش کی کوشش کرتا ہے.
میں کیون شمد ہوں، اور اس CS50 ہے.
>> آہ، یہ آغاز ہے کمی کی.
میں معافی چاہتا ہوں.
معذرت.
>> چار ہڑتال.
میں جا رہا ہوں.
معذرت.
شخص بنانے کے لئے معذرت جو اس پاگل جانے کے ترمیم کرنے کے لئے ہے.
>> معذرت.
معذرت.
>> اسپیکر 1: اچھا کیا.
یہ واقعی میں بہت اچھا کیا گیا تھا.