[Powered by Google Translate] [القسم 7] [أقل راحة]
[نيت Hardison] [جامعة هارفارد]
[هذا CS50.] [CS50.TV]
>> مرحبا بكم في القسم 7.
بفضل إعصار ساندي
بدلا من وجود القسم العادي من هذا الأسبوع،
نحن نفعل ذلك من خلال المشي، من خلال قسم من الأسئلة.
انا ذاهب الى أن بعد طول مع مشكلة تعيين 6 مواصفات،
ويمر على جميع الأسئلة في
مقطع من قسم شؤون.
إذا كان هناك أي أسئلة،
الرجاء نشر هذه على ناقش CS50.
>> بخير. دعونا نبدأ.
الآن أنا أبحث في الصفحة 3 من مشكلة مواصفات مجموعة.
ونحن في طريقنا للبدء أولا نتحدث عن الأشجار الثنائية
منذ تلك ديهم الكثير من الأهمية لمجموعة مشكلة هذا الأسبوع -
ترميز هوفمان شجرة.
كان واحدا من هياكل البيانات الأولى تحدثنا عن CS50 على الصفيف.
تذكر أن مجموعة هو سلسلة من العناصر -
جميع من نفس النوع - تخزينها بجوار بعضها البعض في الذاكرة.
إذا كان لدي مجموعة صحيحا أستطيع أن أوجه استخدام هذا النمط صناديق أرقام صحيحة، -
دعنا نقول لدي 5 في المربع الأول، ولدي 7 في الثانية،
ثم لدي 8، 10، و 20 في المربع النهائي.
تذكر، وهما حقا جيدة الأشياء عن هذه المجموعة
هي أن لدينا هذا الوصول المستمر لمرة وإلى أي عنصر معين
في الصفيف إذا علمنا مؤشره.
على سبيل المثال، إذا كنت ترغب في الاستيلاء على العنصر الثالث في مجموعة -
في مؤشر 2 باستخدام نظامنا الفهرسة الصفرية -
I حرفيا فقط لتفعل عملية حسابية بسيطة الرياضية،
قفز إلى هذا الموقف في الصفيف،
سحب ال 8 التي تم تخزينها هناك،
وأنا على ما يرام.
>> واحدة من أشياء سيئة عن هذه المجموعة - التي تحدثنا عنها
عندما ناقشنا القوائم المرتبطة -
هو أنه إذا كنت تريد إدراج عنصر في هذه المجموعة،
انا ذاهب الى القيام به بعض التحول حولها.
على سبيل المثال، هذه المجموعة هنا
في ترتيب فرزها - غير مصنفة -
5 و 7 ثم، ثم 8، ثم 10، ثم 20 -
ولكن إذا كنت تريد إدراج الرقم 9 في هذه المجموعة،
أنا ذاهب لدينا لتحويل بعض العناصر من أجل جعل الفضاء.
يمكننا رسم هذا هنا.
انا ذاهب الى أن تقوم بتحريك 5، 7، ثم 8؛
خلق فجوة أين يمكنني وضع 9،
وبعد ذلك يمكن لل10 و 20 انتقل إلى يمين 9.
هذا هو نوع من الألم لأنه في أسوأ سيناريو -
في وقت نواجه فيه الحاجة إلى إدراج إما في بداية أو في نهاية
من الصفيف، وهذا يتوقف على مستوى قيامنا تحويل -
ونحن قد ينتهي بعد لتحويل كل العناصر
اننا حاليا في تخزين الصفيف.
>> الأمر كذلك، فما هو السبيل للتغلب على هذه؟
هو السبيل للتغلب على هذه الطريقة للذهاب الى لدينا قائمة مرتبطة-حيث -
بدلا من تخزين العناصر 5 و 7 و 8 و 10 و 20 جميع بجانب بعضها البعض في الذاكرة -
ما فعلته هو بدلا تخزينها نوع من أينما كنا نريد لتخزينها
في هذه العقد القائمة المرتبطة والتي أنا استخلاص هنا، النوع المخصص.
وبعد ذلك توصيلها معا باستخدام هذه المؤشرات القادمة.
الأول يمكن أن يكون مؤشر في الفترة من 5 إلى 7،
مؤشر من 7 إلى 8،
مؤشر من 8 إلى 10،
وأخيرا، مؤشر من 10 إلى 20،
ثم مؤشر فارغة في ال 20 مشيرا إلى أن لا يوجد شيء اليسار.
المفاضلة التي لدينا هنا
الآن هو أن إذا كنا نريد لإدراج رقم 9 الى قائمتنا فرزها،
كل ما عليك القيام به هو إنشاء عقدة جديدة مع 9،
سلك ليصل إلى الإشارة إلى المكان المناسب،
ومن ثم إعادة الأسلاك 8 إلى نقطة وصولا الى 9.
هذا سريع جدا، على افتراض أننا نعرف بالضبط أين نريد أن إدراج 9.
ولكن المفاضلة في مقابل ذلك هو أن فقدنا الآن وصول مستمر في الوقت
إلى أي عنصر معين في بنية البيانات المتوفرة لدينا.
على سبيل المثال، إذا كنت تريد العثور على العنصر الرابع في هذه القائمة المرتبطة،
انا ذاهب الى أن تبدأ في بداية القائمة
والعمل في طريقي من خلال العد عقدة تلو عقدة حتى أجد واحدة الرابع.
>> من أجل الحصول على أفضل أداء من الوصول قائمة مرتبطة -
ولكن أيضا الاحتفاظ بعض الفوائد التي كانت لدينا
من حيث الوقت الإدراج من قائمة مرتبطة -
شجرة ثنائية سوف تحتاج إلى استخدام الذاكرة أكثر من ذلك بقليل.
على وجه الخصوص، بدلا من الاضطرار مؤشر واحد فقط في عقدة شجرة ثنائية -
مثل القائمة المرتبطة عقدة لا -
ونحن في طريقنا لإضافة مؤشر الثاني إلى عقدة شجرة ثنائية.
بدلا من الاضطرار مؤشر واحد فقط إلى العنصر التالي،
نحن ستكون لدينا مؤشر إلى اليسار الطفل وطفل الحق.
>> دعونا رسم صورة لنرى ما الذي يبدو في الواقع مثل.
مرة أخرى، انا ذاهب الى استخدام هذه الصناديق والسهام.
وهناك عقدة شجرة ثنائية تبدأ مع مربع واحد فقط بسيطة.
انها ستكون لدينا مساحة للقيمة،
وبعد ذلك يحدث أيضا أن يكون لها مساحة للطفل الأيسر والطفل الصحيح.
أنا ذاهب لتسمية لهم هنا.
ونحن في طريقنا لجعل الطفل الأيسر، ثم نحن ستكون لدينا الحق للطفل.
هناك العديد من الطرق المختلفة للقيام بذلك.
في بعض الأحيان لالفضاء والراحة،
أنا فعلا مثل رسم أفعله هنا على الجزء السفلي
حيث أنا ذاهب ليكون في أعلى قيمة،
ومن ثم حق الطفل على اليمين أسفل،
والطفل الأيسر على اليسار من الأسفل.
العودة إلى أعلى هذا المخطط،
لدينا قيمة في أعلى جدا،
ثم لدينا مؤشر اليسار الطفل، ومن ثم لدينا مؤشر الماوس الأيمن الأطفال.
>> مشكلة في مواصفات مجموعة،
نتحدث عن رسم العقدة التي لديها قيمة 7،
ثم مؤشر اليسار الأطفال الذي فارغة، ومؤشر الماوس الأيمن الأطفال الذي فارغة.
يمكن أن نكتب إما NULL رأس المال في الفضاء ل
يمكن كل من اليسار والطفل الطفل الحق، أو وضعنا هذه القطع قطري
من خلال كل من مربعات للإشارة إلى أنه من فارغة.
انا ذاهب للقيام بذلك لمجرد أن هذا أكثر بساطة.
ما تراه هنا طريقتان لإنشاء المخططات شجرة ثنائية بسيطة جدا العقدة
حيث لدينا قيمة 7 و الطفل مؤشرات فارغة.
>> الجزء الثاني من المحادثات حول كيفية مواصفات لدينا مع القوائم المرتبطة -
تذكر، كان لدينا فقط على التمسك العنصر الأول في قائمة جدا
أن نتذكر القائمة بأكملها -
وبالمثل، مع شجرة ثنائية، لدينا فقط لعقد واحد على مؤشر إلى شجرة
من أجل الحفاظ على السيطرة على بنية البيانات بالكامل.
ويسمى هذا العنصر الخاص للشجرة عقدة جذر الشجرة.
على سبيل المثال، إذا كانت هذه عقدة واحدة - هذه العقدة التي تحتوي على قيمة 7
مع مؤشرات فارغة اليسار واليمين للأطفال و-
وكانت قيمة فقط في شجرة لدينا،
ثم وهذا سيكون لدينا عقدة الجذر.
انها بداية شجرة لدينا.
يمكننا أن نرى هذا بشكل أكثر وضوحا قليلا مرة واحدة نبدأ إضافة المزيد من العقد إلى شجرة لدينا.
اسمحوا لي سحب ما يصل صفحة جديدة.
>> الآن ونحن في طريقنا لرسم الشجرة التي لديها 7 في الجذر،
و 3 داخل الطفل الأيسر، و 9 داخل الطفل الصحيح.
مرة أخرى، وهذا هو بسيط جدا.
لدينا 7، رسم عقدة ل3، عقدة لمدة 9،
وانا ذاهب لضبط المؤشر الأيسر للطفل من 7 للإشارة إلى العقدة التي تحتوي على 3،
والمؤشر حق الطفل من العقدة التي تحتوي على 7 إلى العقدة التي تحتوي على 9.
الآن، منذ 3 و 9 لم يكن لديك أي أطفال،
ونحن في طريقنا لتعيين كافة مؤشرات الطفل على أن تكون فارغة.
هنا، جذر شجرة لدينا يتوافق مع عقدة تحتوي على رقم 7.
يمكنك أن ترى أن كل ما لدينا إذا هو مؤشر إلى أن العقدة الجذر،
يمكننا المشي من خلال شجرة ثم لدينا والوصول العقد التابعة على حد سواء -
كلا 3 و 9.
لا حاجة للحفاظ على مؤشرات إلى كل عقدة واحدة على الشجرة.
بخير. الآن ونحن في طريقنا لإضافة عقدة أخرى إلى هذا المخطط.
ونحن في طريقنا لإضافة عقدة تحتوي على 6،
ونحن في طريقنا لإضافة هذا الطفل والحق في العقدة التي تحتوي على 3.
للقيام بذلك، وانا ذاهب لمحو أن مؤشر فارغة في عقدة-3
والأسلاك ليصل إلى الإشارة إلى عقدة تحتوي على 6. بخير.
>> في هذه المرحلة، دعونا نذهب أكثر قليلا من المصطلحات.
للبدء، والسبب في أن هذا ما يسمى شجرة ثنائية على وجه الخصوص
هو أن لديها مؤشرات طفل في الثانية.
هناك أنواع أخرى من الأشجار التي لديها مؤشرات أكثر الأطفال.
على وجه الخصوص، هل ل'محاولة' في مجموعة مشكلة 5.
هل كان لديك ستلاحظ أن في ذلك محاولة، 27 مؤشرات مختلفة للأطفال مختلفة -
واحد لكل من 26 حرفا في الأبجدية الإنجليزية،
ثم الفاصلة العليا ل27 -
لذلك، وهذا مماثل لنوع من الأشجار.
ولكن هنا، منذ ذلك ثنائي، لدينا فقط مؤشرات الطفل اثنين.
>> بالإضافة إلى هذه العقدة الجذر الذي تحدثنا عنه،
لقد تم أيضا إلقاء حول هذا المصطلح "الطفل".
ماذا يعني ذلك للعقدة واحدة في أن يكون طفلا من عقدة أخرى؟
وهذا يعني حرفيا أن عقدة الطفل هو الطفل من عقدة أخرى
إذا كان ذلك عقدة أخرى لديها واحد من المؤشرات التابعة لها للإشارة إلى تعيين تلك العقدة.
لوضع هذا في شروط أكثر واقعية،
إذا أشار 3 إلى واحد من المؤشرات الطفل من 7، ثم 3 هو طفل من 7.
إذا كان لنا أن معرفة ما هي الأطفال من 7 -
حسنا، نحن نرى أن 7 ومؤشر إلى 3 و مؤشر إلى 9،
9 بحيث و 3 أطفال من 7.
لا يوجد لديه تسعة أطفال بسبب مؤشرات التابعة لها لاغية،
و 3 لديه طفل واحد فقط، و 6.
ستة أطفال أيضا لا لأن كلا من المؤشرات التي تعتبر لاغية، والتي سوف نستخلص الآن.
>> بالإضافة إلى ذلك، نتحدث أيضا عن والدي عقدة معينة،
وهذا هو، كما كنت تتوقع، عكس هذا الوصف الطفل.
كل عقدة لديه أحد الوالدين فقط - بدلا من اثنين كما قد تتوقع مع البشر.
على سبيل المثال، فإن الوالد من 3 هو 7.
والد 9 هو أيضا 7، والوالد من 6 هو 3. ليس كثيرا لذلك.
لدينا أيضا حيث الحديث عن الأجداد والأحفاد،
وبشكل عام كنا نتحدث عن الأجداد
والمتحدرين من عقدة معينة.
والجد من عقدة - أو الأجداد، بدلا من عقدة -
هي كافة العقد التي تقع على الطريق من جذورها إلى تلك العقدة.
على سبيل المثال، إذا أنا أبحث في ال 6 عقدة،
ثم أسلاف ستكون كل 3 و 7.
أسلاف 9، على سبيل المثال، هي - إذا أنا أبحث في ال 9 عقدة -
ثم الجد من 9 هو فقط 7.
ونسل هي بالضبط عكس ذلك.
إذا كنت تريد أن ننظر إلى كل من أحفاد 7،
ثم لا بد لي من النظر في كافة العقد تحته.
لذلك، لدي 3، 9، و 6 عن باعتبارهم من نسل من 7.
>> على المدى النهائي الذي سنتحدث عنه هو هذه الفكرة من كونها الأخوة.
الأشقاء - نوع من بعد طول هذه الشروط على الأسرة -
هي العقد التي تكون في نفس المستوى في الشجرة.
حتى و 3 و 9 إخوة لأنهم على نفس المستوى في الشجرة.
ديهما نفس الأم، 7.
ال 6 لا يوجد لديه أشقاء ل9 لا يوجد اي الأطفال.
و 7 لا يوجد اي الأشقاء لأنه جذر شجرة لدينا،
وليس هناك سوى نفس الوقت كان 1 الجذر.
لمدة 7 لالأشقاء ويجب أن تكون هناك عقدة فوق 7.
وهناك يجب أن يكون أحد الوالدين من 7، الذي الحالة 7 لن يكون جذر الشجرة.
فهذا هو الأصل الجديد من 7 أيضا لإنجاب طفل،
وسوف يكون هذا الطفل ثم الأخوة من 7.
>> بخير. الانتقال.
عندما بدأنا مناقشاتنا الثنائية من الأشجار،
تحدثنا عن الطريقة التي كانوا في طريقهم لاستخدامها ل
كسب ميزة على حد سواء المصفوفات والقوائم المرتبطة.
والطريقة ونحن في طريقنا للقيام بذلك هي مع هذه الخاصية الطلب.
نقول أن أمر شجرة ثنائية، وفقا لمواصفات،
إذا لكل عقدة في شجرة لدينا، كل من نسله على اليسار -
الطفل الأيسر وجميع أحفاد الطفل اليسار -
يكون أقل القيم، وجميع من العقد على حق -
الطفل والحق كل نسل الطفل الحق في -
يكون العقد أكبر من قيمة العقدة الحالية التي نحن نبحث في.
فقط لبساطة، ونحن في طريقنا لنفترض أن ليس هناك أي عقد مكررة في شجرة لدينا.
على سبيل المثال، في هذه الشجرة ونحن لن تتعامل مع القضية
حيث لدينا قيمة 7 في الجذر
ثم لدينا أيضا قيمة 7 مكان آخر في الشجرة.
في هذه الحالة، سوف تلاحظ أن أمر الواقع هذه الشجرة.
لدينا قيمة 7 في جذورها.
كل شيء على يسار 7 -
إذا كنت التراجع عن كل هذه علامات قليلا هنا -
كل شيء على يسار 7 - 3 و 6 و-
هذه القيم على حد سواء أقل من 7، وكل شيء إلى اليمين - - الذي هو مجرد هذه 9
هو أكبر من 7.
>> ليست هذه هي شجرة تحتوي على أمر هذه القيم فقط،
ولكن دعونا رسم أكثر عدد قليل منها.
هناك في الواقع مجموعة كاملة من الطرق التي يمكننا أن نفعل هذا.
انا ذاهب الى استخدام الاختزال فقط للحفاظ على الأشياء البسيطة حيث -
بدلا من استخلاص كله مربعات و-السهام -
انا فقط لرسم الأرقام وربطها إضافة السهام.
للبدء، وسنقوم مجرد كتابة شجرة لدينا الأصلي مرة أخرى حيث كان لدينا 7، وبعد ذلك 3،
وأشار ثم 3 عودة إلى الحق في 6،
وكان 7 ألف طفل الحق الذي كان 9.
بخير. ما طريقة أخرى أن نتمكن من كتابة هذه الشجرة؟
بدلا من أن يكون وجود 3 الطفل الأيسر من 7،
يمكن أن لدينا أيضا ال 6 يكون الطفل الأيسر من 7،
وثم 3 يكون الطفل الأيسر من 6.
والتي تبدو وكأنها هذه الشجرة هنا حيث كنت قد حصلت على 7،
6 ثم، ثم 3، و9 على اليمين.
ونحن أيضا لا يكون لدينا (7)، لدينا عقدة الجذر.
يمكن أن لدينا أيضا (6)، لدينا عقدة الجذر.
ماذا تشبه؟
إذا نحن في طريقنا للحفاظ على هذه الخاصية أمر،
كل شيء على يسار ال 6 يجب أن يكون أقل من ذلك.
هناك احتمال واحد فقط، وهذا هو 3.
ولكن بعد ذلك الطفل حق 6، لدينا اثنين من الاحتمالات.
أولا، يمكن أن لدينا 7 و ثم 9،
أو يمكن أن استدراجه - مثل أنا على وشك القيام به هنا -
حيث لدينا 9 كما الطفل الأيمن من 6،
وبعد ذلك (7)، الطفل الأيسر من 9.
>> الآن، 7 و 6 ليست فقط القيم الممكنة لجذر.
يمكن أن لدينا أيضا 3 يكون في الجذر.
ماذا يحدث إذا (3) هي في جذور؟
هنا، الامور قليلا للاهتمام.
ثلاثة ليس لديها أي القيم التي هي أقل من ذلك،
بحيث الجانب الأيسر بأكمله من شجرة هو مجرد الذهاب لاغية.
هناك لن يكون أي شيء هناك.
إلى اليمين، يمكن أن قائمة الأشياء في ترتيب تصاعدي.
يمكن أن لدينا 3، ثم 6، ثم 7، ثم 9.
أو، يمكن أن نفعل 3، ثم 6، ثم 9، ثم 7.
أو، يمكن أن نفعل 3، ثم 7، ثم 6، ثم 9.
أو، 3، 7 - لا في الواقع، لا يمكننا القيام ج 7 بعد الآن.
هذا لدينا شيء واحد هناك.
يمكننا أن نفعل 9، ثم من ال 9 يمكننا القيام به ثم 6 و 7.
أو، يمكننا أن نفعل 3، ثم 9، ثم 7، ثم 6.
>> شيء واحد أن ألفت انتباهكم إلى هنا
أن هذه الأشجار هي غريبة قليلا المظهر.
على وجه الخصوص، إذا نظرنا إلى الأشجار 4 على الجانب الأيمن -
أنا دائرة لهم، وهنا -
هذه الأشجار تبدو تماما تقريبا مثل قائمة مرتبطة.
كل عقدة لديه طفل واحد فقط،
وذلك ليس لدينا أي من هذه البنية شجرة تشبه التي نراها، على سبيل المثال،
في هذا شجرة واحدة وحيدة أكثر من هنا على اليسار السفلي.
وتسمى هذه الأشجار في الواقع تتحول الأشجار الثنائية،
وسوف نتحدث عن هذه أكثر في المستقبل -
خاصة إذا كنت تذهب على أن يأخذ علوم الحاسب الآلي المقررات الأخرى.
هذه الأشجار هي تتدهور.
انهم ليسوا مفيدة جدا لأنه، في الواقع، هذا الهيكل يفسح المجال
لبحث مرات مماثلة لتلك التي على قائمة مرتبطة.
نحن لا تحصل على الاستفادة من ذاكرة إضافية - وهذا مؤشر إضافي -
بسبب بنية سيئة جودنا في هذا السبيل.
بدلا من المضي قدما واستخلاص الأشجار الثنائية التي لديها 9 في الجذر،
كما هو الحال النهائية التي سيكون لدينا،
نحن بدلا من ذلك، في هذه المرحلة، بصدد الحديث قليلا عن هذا المصطلح الأخرى
التي نستخدمها عندما نتحدث عن الأشجار، وهو ما يسمى الارتفاع.
>> ارتفاع شجرة هي المسافة من الجذر إلى العقدة الأكثر بعيد المنال،
أو بالأحرى عدد من القفزات التي عملتم لجعل ل
تبدأ من الجذر ثم ينتهي في عقدة معظم البعيد في الشجرة.
إذا كان لنا أن نلقي نظرة على بعض من هذه الأشجار التي كانت لدينا رسمها هنا،
يمكننا أن نرى أن إذا أخذنا هذه الشجرة في أعلى الزاوية اليسرى ونبدأ في 3،
ثم لدينا لجعل 1 هوب للوصول الى 6، قفزة ثانية لتصل إلى 7،
وهوب الثالث لتصل إلى 9.
لذا، فإن ارتفاع هذه الشجرة هو 3.
يمكننا أن نفعل نفس العملية للأشجار الأخرى المبينة في هذا الأخضر،
ونحن نرى أن ارتفاع كل هذه الأشجار هي في الواقع أيضا 3.
هذا جزء من ما يجعلها تتحول -
أن طولهم واحد فقط أقل من عدد العقد في الشجرة بأكملها.
إذا نظرنا إلى هذه الشجرة الأخرى التي المحاصرة مع الأحمر، من ناحية أخرى،
ونحن نرى أن معظم أوراق العقد البعيد هي 6 و 9 و-
ويجري يترك تلك العقد التي ليس لها أطفال.
لذلك، من أجل الحصول على الجذر من العقدة إلى 6 أو 9 إما ل،
لدينا لجعل واحدة هوب للوصول الى (7) وبعد ذلك قفزة ثانية للحصول على ل9،
وبالمثل، فقط هوب الثاني من 7 إلى الوصول إلى 6.
لذا، فإن ارتفاع هذه الشجرة إلى هنا هو 2 فقط.
يمكنك العودة وذلك لجميع الأشجار الأخرى التي ناقشناها سابقا
ابتداء من 7 و 6 و،
وسوف تجد أن ارتفاع كل هذه الأشجار هي أيضا 2.
>> أمرت السبب كنا نتحدث عن الأشجار الثنائية
والسبب في انهم بارد لأن يمكنك البحث من خلالها في
بطريقة مماثلة جدا لتبحث على مجموعة فرزها.
هذا هو المكان الذي نتحدث عن الحصول على هذا الوقت البحث المحسنة
خلال قائمة بسيطة مرتبطة.
مع قائمة مرتبطة - إذا كنت ترغب في العثور على عنصر معين -
كنت في الذهاب الأفضل أن تفعل نوعا من البحث الخطي
حيث تبدأ في بداية قائمة وهوب واحد من جانب واحد -
عقدة واحدة من عقدة واحدة -
من خلال القائمة بأكملها حتى تجد ما كنت تبحث عنه.
في حين، إذا كان لديك شجرة الثنائية التي يتم تخزينها في هذا الشكل لطيف،
يمكنك في الواقع الحصول على أكثر من بحث ثنائية مستمرة
حيث يمكنك فرق تسد
وبحث خلال النصف المناسبة من شجرة في كل خطوة.
دعونا نرى كيف يعمل.
>> اذا كان لدينا - مرة أخرى، والعودة إلى شجرة لدينا الأصلي -
نبدأ في الساعة 7، لدينا 3 على اليسار و 9 على اليمين،
وتحت ال 3 لدينا 6.
إذا كنا نريد للبحث عن الرقم 6 في هذه الشجرة، علينا أن نبادر في جذورها.
وقارنا القيمة التي تبحث عنها، ويقول 6،
إلى القيمة المخزنة في العقدة التي نحن نبحث حاليا في، 7،
وجدت أن 6 هو في الواقع أقل من 7، لذلك كنا نقل إلى اليسار.
إذا كانت القيمة من 6 كان أكبر من 7، وانتقلنا بدلا من ذلك إلى اليمين.
لأننا نعلم أن - بسبب هيكل شجرة لدينا ثنائي أمر -
كافة القيم أقل من 7 سوف تكون مخزنة على يسار 7،
ليس هناك حاجة لعناء حتى النظر من خلال الجانب الأيمن من الشجرة.
مرة واحدة ونحن نتحرك إلى اليسار، ونحن الآن في عقدة تحتوي على 3،
يمكننا أن نفعل ذلك مرة أخرى حيث المقارنة نفسها قارنا 3 و 6 و.
ونجد أنه في حين أن 6 - قيمة ونحن نبحث عن - أكبر من 3،
يمكننا أن نذهب إلى الجانب الأيمن من العقدة التي تحتوي على 3.
ليس هناك الجانب الأيسر هنا، حتى أننا يمكن أن تجاهلوا ذلك.
ولكننا نعرف فقط ذلك لأننا نبحث في الشجرة نفسها،
ويمكننا أن نرى أن الشجرة لا يوجد لديه أطفال.
>> كما انها سهلة جدا للبحث عن 6 في هذه الشجرة إذا نفعله بأنفسنا كبشر،
ولكن دعونا اتبع هذه العملية ميكانيكيا مثل الكمبيوتر ستفعل
لفهم حقا الخوارزمية.
في هذه المرحلة، ونحن نبحث الآن في العقدة التي تحتوي على 6،
ونحن نبحث عن القيمة 6،
لذلك، في الواقع، وجدنا العقدة المناسبة.
وجدنا قيمة 6 في شجرة لدينا، ونحن يمكن أن يوقف البحث.
في هذه المرحلة، اعتمادا على ما يجري،
نستطيع أن نقول، نعم، وجدنا قيمة 6، كان موجودا في شجرة لدينا.
أو، إذا نحن نخطط لإدراج عقدة أو تفعل شيئا، يمكننا أن نفعل ذلك في هذه المرحلة.
>> دعونا نفعل عمليات البحث أكثر زوجين فقط لنرى كيف يعمل هذا.
دعونا ننظر إلى ما يحدث إذا كان لنا أن نحاول والبحث عن القيمة 10.
إذا كان لنا أن البحث عن القيمة 10، ونبدأ في جذورها.
كنا نرى أن 10 هو أكبر من 7، لذلك كنا التحرك إلى اليمين.
كنا نصل إلى المقارنة 9 و 9 إلى ال 10، ويرى في 9 هو في الواقع أقل من 10.
ذلك مرة أخرى، كنا محاولة نقل إلى اليمين.
ولكن في هذه النقطة، لكنا نلاحظ أننا في عقدة فارغة.
لا يوجد شيء هناك. لا يوجد شيء حيث ينبغي أن تكون ال 10.
هذا هو المكان الذي يمكن أن يقدم تقريرا الفشل - أن هناك في الواقع لا 10 في الشجرة.
وأخيرا، دعونا نذهب من خلال الحالة التي نحاول أن ننظر بنسبة 1 في الشجرة.
هذا هو على غرار ما يحدث إذا نظرنا حتى 10، باستثناء بدلا من الذهاب إلى اليمين،
ونحن في طريقنا للذهاب إلى اليسار.
نبدأ في 7 و نرى أن 1 هو أقل من 7، لذلك نحن نتحرك إلى اليسار.
نصل إلى 3 و نرى أن 1 أقل من 3، لذلك مرة أخرى ونحن نحاول التحرك إلى اليسار.
عند هذه النقطة لدينا عقدة فارغة، مرة أخرى حتى نتمكن من تقديم تقرير الفشل.
>> إذا كنت تريد معرفة المزيد عن الأشجار الثنائية،
هناك مجموعة كاملة من المشاكل الصغيرة المتعة التي يمكنك القيام به معها.
أقترح ممارسة الرسم للخروج من هذه المخططات واحدة تلو الأخرى
ومتابعة كافة الخطوات المختلفة،
لأن هذا في متناول اليدين عظمى
ليس فقط عندما كنت تفعل ترميز هوفمان مشكلة مجموعة
ولكن أيضا في الدورات المقبلة -
مجرد تعلم كيفية استخلاص هذه الهياكل البيانات والتفكير في المشاكل
مع القلم والورقة أو، في هذه الحالة، وتطلب الشركة والقلم.
>> في هذه المرحلة على الرغم من أننا في طريقنا للانتقال إلى القيام ببعض الممارسات الترميز
وتلعب هذه الأشجار فعلا مع ثنائي ونرى.
انا ذاهب للعودة الى جهاز الكمبيوتر الخاص بي.
لهذا الجزء من هذا الباب، بدلا من استخدام CS50 CS50 تشغيل أو مسافات،
انا ذاهب الى استخدام الجهاز.
>> بعد طول مشكلة مع مواصفات مجموعة،
وأرى أن من المفترض أن تفتح الجهاز،
انتقل إلى مجلد Dropbox بلدي، إنشاء مجلد يسمى القسم 7،
ثم قم بإنشاء ملف يسمى binary_tree.c.
هنا نذهب. أنا عندي الجهاز مفتوح مسبقا.
أنا ذاهب سحب ما يصل محطة.
انا ذاهب للذهاب إلى مجلد Dropbox، وجعل دليل يسمى section7،
ونرى أنه من فارغة تماما.
الآن انا ذاهب لفتح binary_tree.c.
بخير. هنا نذهب - ملف فارغ.
>> دعونا نعود إلى مواصفات.
مواصفات يسأل لإنشاء تعريف نوع جديد
لعقدة شجرة ثنائية تحتوي على قيم الباحث -
تماما مثل القيم التي نحن في وجه المخططات لدينا من قبل.
ونحن في طريقنا لاستخدام هذا المتداول typedef أن فعلناه هنا
يجب عليك أن تدرك من مجموعة مشكلة 5 -
إذا لم لك الطريق جدول التجزئة من قهر وبرنامج سبيلر.
يجب أن ندرك أيضا أنه من قسم الأسبوع الماضي
حيث تحدثنا عن القوائم المرتبطة.
ونحن قد حصلت على هذا typedef من عقدة البنية،
ولقد أعطيت لنا هذه العقدة اسم هذه البنية عقدة البنية مسبقا
حتى نتمكن من الرجوع إليها منذ ذلك الحين سنقوم تريد أن يكون عقدة مؤشرات البنية
كجزء من البنية لدينا، ولكن لدينا طوق ثم وهذا -
أو بالأحرى، محاطة هذا - في typedef
بحيث، في وقت لاحق في التعليمات البرمجية، يمكننا الرجوع إلى هذه البنية وعقدة فقط بدلا من عقدة البنية.
>> هذه ستكون مشابهة جدا لتعريف قائمة منفردة مرتبطة التي شهدناها الأسبوع الماضي.
للقيام بذلك، دعونا نبدأ من خلال كتابة خارج المتداول.
ونحن نعلم أن علينا أن يكون لها قيمة عدد صحيح،
وهكذا لن نضع في قيمة الباحث، ومن ثم بدلا من أن مؤشر واحد فقط إلى العنصر التالي -
كما فعلنا مع منفردة مرتبطة القوائم -
نحن ستكون لدينا مؤشرات الطفل اليمنى واليسرى.
هذا بسيط جدا جدا - البنية الطفل عقدة * اليسرى.
والبنية عقدة * الطفل اليمنى. بارد.
التي تبدو وكأنها بداية جيدة جدا.
دعونا نعود إلى مواصفات.
>> الآن نحن بحاجة إلى أن يعلن * عقدة العالمية المتغيرة لجذر شجرة.
ونحن في طريقنا لجعل هذا العالم مثلما قدمنا ​​المؤشر الأول في قائمتنا العالمية مرتبطة أيضا.
وكان هذا حتى في الوظائف التي نكتب
ليس لدينا للحفاظ على تمرير حول هذا الجذر -
على الرغم سنرى أنه إذا كنت لا تريد أن أكتب هذه المهام بشكل متكرر،
قد يكون من الأفضل أن لا تمر حتى حولها باعتبارها العالمي في المقام الأول
وبدلا من ذلك تهيئة محليا في وظيفة الرئيسي الخاص بك.
ولكن، سوف نفعل ذلك على الصعيد العالمي لبدء.
مرة أخرى، سوف نقدم اثنين من مسافات، وانا ذاهب لاعلان الجذر * العقدة.
فقط للتأكد من أنني لا اترك هذا غير مهيأ، وانا ذاهب لتعيين أنه يساوي قيمة خالية.
الآن، في المهمة الرئيسية - التي سوف نكتب بسرعة حقا هنا -
الباحث الرئيسي (الباحث argc، تشار * argv CONST []) -
وانا ذاهب لبدء إعلان مجموعة بلدي argv كما CONST فقط لكي أعرف
إن هذه الحجج هي حجج أنني ربما لا تريد تعديلها.
إذا كنت ترغب في تعديلها يجب أن تكون القرارات ربما نسخ منها.
سترى هذا كثيرا في التعليمات البرمجية.
أنه بخير اي من الاتجاهين. أنه بخير لترك الأمر كما - حذفت CONST إذا كنت ترغب.
عادة أضع في ذلك فقط أن أذكر نفسي
أنني ربما لا ترغب في تعديل تلك الحجج.
>> كما هو الحال دائما، وانا ذاهب لتضمين هذا الخط عودة 0 في نهاية الرئيسي.
هنا، وسوف بلدي تهيئة عقدة الجذر.
كما هو عليه الآن، لقد حصلت على المؤشر الذي تم ضبطه إلى فارغة،
حتى انها لافتا في شيء.
من أجل البدء في بناء الواقع العقدة،
I تحتاج أولا إلى تخصيص ذاكرة لذلك.
انا ذاهب للقيام بذلك بجعل الذاكرة على الكومة باستخدام malloc.
أنا ذاهب لتعيين الجذر يساوي نتيجة malloc،
وانا ذاهب الى استخدام عامل التشغيل sizeof لحساب حجم عقدة.
السبب الذي يمكنني استخدام sizeof عقدة بدلا من، لنقل،
القيام بشيء من هذا القبيل - malloc (4 + 4 +4) أو malloc 12 -
هو لأنني أريد قانون بلدي لتكون متوافقة قدر الإمكان.
أريد أن أكون قادرا على اتخاذ هذا الملف ج.، ترجمة على الجهاز،
وثم ترجمة ذلك على ماك 64-بت بلدي -
أو على بنية مختلفة تماما -
وأريد هذا جميعا أن نعمل نفس الشيء.
>> إذا أنا وضع افتراضات حول حجم المتغيرات -
حجم وكثافة العمليات أو حجم مؤشر -
ثم أنا أيضا جعل افتراضات حول أنواع أبنية
التي يمكن أن قانون بلدي بنجاح ترجمة عند تشغيل.
دائما استخدام sizeof بدلا من تلخيص مجالات البنية يدويا.
والسبب الآخر هو أنه قد يكون هناك أيضا الحشو أن يضع المترجم في البنية.
حتى تلخيص فقط الحقول الفردية ليست شيئا كنت تريد أن تفعل عادة،
لذلك، حذف ذلك السطر.
الآن، لتهيئة حقا هذه العقدة الجذر،
انا ذاهب الى أن سد العجز في القيم لكل من حقولها المختلفة.
على سبيل المثال، لأعرف قيمة أريد أن تهيئة إلى 7،
والآن انا ذاهب لوضع الطفل الأيسر لاغية
والطفل أيضا الحق في أن يكون باطلا. عظيم!
لقد فعلنا ذلك الجزء من المواصفات.
>> مواصفات أسفل في أسفل الصفحة 3 يطلب مني لخلق المزيد من ثلاث عقد -
واحدة تحتوي على 3، واحدة تحتوي على 6، واحد مع 9 -
والأسلاك ثم لهم بحيث يبدو تماما مثل مخطط الشجرة لدينا
أن كنا نتحدث عن السابق.
دعونا نفعل ذلك بسرعة كبيرة هنا.
سترى بسرعة حقا بأنني ذاهب للبدء في كتابة مجموعة من التعليمات البرمجية المتكررة.
أنا ذاهب لخلق عقدة * وانا ذاهب الى نسميها الثلاثة.
انا ذاهب الى تعيين يساوي malloc (sizeof (عقدة)).
انا ذاهب الى تعيين ثلاثة> القيمة = 3.
ثلاثة -> left_child = NULL؛ الثلاث -> الحق NULL = _child؛ كذلك.
التي تبدو مشابهة جدا لتهيئة الجذر، وهذا هو بالضبط ما
انا ذاهب الى القيام به إذا كنت بدء تهيئة 6 و 9 أيضا.
سوف أفعل ذلك حقا هنا بسرعة - في الواقع، انا ذاهب الى القيام نسخة ولصق قليلا،
وتأكد من أن I - على ما يرام.
الآن، وأنا قد حصلت عليه نسخ وأستطيع أن تمضي قدما وتعيين هذا يساوي 6.
يمكنك أن ترى أن هذا يأخذ لحظة وليس كفاءة فائقة.
في قليلا فقط، وسوف نكتب وظيفة من شأنها أن تفعل هذا بالنسبة لنا.
أريد أن يحل محل هذا مع 9، الاستعاضة عن ذلك مع 6.
>> الآن لدينا كل من العقد وخلق لدينا تهيئة.
لدينا لدينا الجذر تعيين يساوي 7، أو التي تحتوي على قيمة 7،
لدينا عقدة تحتوي على 3، لدينا عقدة تحتوي على 6، والتي تحتوي على عقدة لدينا 9.
في هذه المرحلة، كل ما عليك القيام به هو كل شيء حتى الأسلاك.
السبب في أنني تهيئة جميع المؤشرات إلى أن مجرد فارغة لذلك أنا تأكد من أن
ليس لدي أي مؤشرات غير مهيأ هناك عن طريق الصدفة.
وأيضا منذ ذلك الحين، في هذه المرحلة، وليس لدي سوى للاتصال العقد في الواقع مع بعضها البعض -
لتلك التي كنت متصلا بالفعل إلى أنها - أنا لا يجب أن تمر عبر وجعل
التأكد من أن جميع بلا قيم هي في وجود في الأماكن المناسبة.
>> ابتداء من الجذر، وأنا أعلم أن الطفل الجذر اليسار هو 3.
وأنا أعلم أن الطفل الجذر الحق هو 9.
بعد ذلك، والطفل الوحيد الذي لم يقم أنا ما يدعو للقلق
هو الطفل 3 اليمنى، والتي هي 6.
عند هذه النقطة، يبدو كل شيء جيد جدا.
سنقوم بحذف بعض من هذه الخطوط.
الآن كل شيء يبدو جيدا جدا.
دعونا نعود لمواصفات لدينا ونرى ما يتعين علينا القيام به المقبل.
>> في هذه المرحلة، لدينا لكتابة دالة يسمى 'يحتوي'
مع نموذج أولي من 'يحتوي BOOL (الباحث القيمة).
وهذا يتضمن وظيفة هو الذهاب الى العودة الحقيقية
فإذا قال شجرة لدينا متغير من الجذر العالمية
يحتوي على القيمة تمريرها إلى الدالة وغير ذلك كاذب.
دعونا نمضي قدما ونفعل ذلك.
هذا سيكون تماما مثل البحث الذي قمنا به باليد على جهاز آي باد قليلا قبل.
دعونا في إعادة تكبير قليلا وانتقل لأعلى.
ونحن في طريقنا لوضع هذه الوظيفة وظيفة الحق فوق هدفنا الرئيسي
بحيث لم يكن لدينا للقيام بأي نوع من النماذج.
لذلك، يحتوي BOOL (الباحث القيمة).
هناك نذهب. هناك إعلاننا النمطي.
فقط للتأكد من أن هذا سيتم ترجمة،
انا ذاهب الى المضي قدما وانها مجرد مجموعة يساوي عودة كاذبة.
الآن هذه الوظيفة فقط لن تفعل أي شيء ويقدم دائما أن
القيمة التي نبحث عنها ليست في الشجرة.
>> في هذه المرحلة، هو على الأرجح فكرة جيدة -
لقد كتبنا منذ مجموعة كاملة من التعليمات البرمجية، ونحن لم يحاكم حتى اختباره حتى الآن -
للتأكد من أن يقوم بإعداد جميع.
هناك اثنين من الأشياء التي يتعين علينا القيام به للتأكد من أن هذا سيتم ترجمة الواقع.
أولا، معرفة ما إذا كنا باستخدام أية وظائف المكتبات في أي أننا لم تدرج بعد.
وظائف استخدمنا حتى الآن malloc،
ثم قمنا أيضا تم استخدام هذا النوع - هذا النوع غير قياسي يسمى 'bool' -
يتم تضمين التي في ملف الرأس BOOL القياسية.
نحن بالتأكيد نريد أن تشمل bool.h القياسية لنوع BOOL،
ونريد أيضا أن تدرج # lib.h القياسية لمكتبات القياسية
التي تشمل malloc، ومجانا، وذلك كله.
لذلك، تصغير، ونحن في طريقنا إلى الإقلاع عن التدخين.
دعونا نحاول وتأكد من أن هذا فعلا الترجمة.
ونحن نرى أن تفعل ذلك، لذلك نحن على الطريق الصحيح.
>> دعونا فتح binary_tree.c مرة أخرى.
يقوم بإعداد. دعونا نذهب إلى أسفل والتأكد من أننا إدراج بعض المكالمات للعمل لدينا يحتوي على -
فقط للتأكد من أن هذا هو كل شيء حسن وجيد.
على سبيل المثال، عندما فعلنا بعض عمليات البحث في شجرة لدينا في وقت سابق،
حاولنا بحث عن القيم 6، 10، و 1، وكنا نعرف أن 6 كان في الشجرة،
كان 10 وليس في الشجرة، و 1 لم يكن في الشجرة سواء.
دعونا نستخدم تلك المكالمات عينة باعتبارها وسيلة لمعرفة ما إذا كان أو لا
لدينا يحتوي على وظيفة تعمل.
من أجل القيام بذلك، أنا ذاهب إلى استخدام الدالة printf،
ونحن في طريقنا للطباعة نتيجة الدعوة إلى يتضمنها.
انا ذاهب الى وضعها في سلسلة "يحتوي على (D٪) = بسبب
ونحن في طريقنا إلى سد العجز في القيمة التي نحن في طريقنا للبحث عن،
و=٪ S \ N "واستخدام ذلك كسلسلة تنسيق لدينا.
ونحن في طريقنا لمجرد أن نرى - حرفيا طباعة على الشاشة -
ما يشبه استدعاء دالة.
هذه ليست في الواقع استدعاء دالة.
هذا هو مجرد سلسلة مصممة لتبدو وكأنها استدعاء دالة.
>> الآن، ونحن في طريقنا إلى سد العجز في القيم.
ونحن في طريقنا لمحاولة يحتوي على 6،
ثم ما نحن بصدد القيام به هنا هو استخدام هذا المشغل الثلاثي.
دعونا نرى - يحتوي على 6 - حتى الآن، لقد الواردة 6 و إذا تحتوي على 6 صحيحا،
السلسلة التي نحن في طريقنا لإرسالها إلى الطابع تنسيق٪ S
ستكون السلسلة "الحقيقية".
دعونا تمرير أكثر من قليلا.
خلاف ذلك، ونحن نريد لإرسال سلسلة "كاذبة" إذا يحتوي على 6 بإرجاع FALSE.
هذا هو أحمق قليلا المظهر، ولكن الرقم الأول قد كذلك توضيح
ما المشغل الثلاثي يبدو أننا لم يطلعوا عليه لحظة.
سيكون هذا لطيف، طريقة سهلة لمعرفة ما اذا كان لدينا يحتوي على وظيفة تعمل.
انا ذاهب للتمرير إلى أكثر إلى اليسار،
وانا ذاهب لنسخ ولصق هذا الخط عدة مرات.
تغيرت بعض هذه القيم حولها،
ولذلك فإن هذا سيكون 1، وهذا سيكون 10.
>> في هذه المرحلة لدينا وظيفة يحتوي على لطيفة.
لدينا بعض الاختبارات، وسنرى ما إذا كان هذا جميع الأعمال.
عند هذه النقطة لقد كتبنا رمز بعض أكثر.
الوقت لإنهاء وتأكد من أن كل شيء لا يزال يجمع.
إنهاء خارج، والآن دعونا نحاول جعل شجرة ثنائية مرة أخرى.
حسنا، يبدو أننا قد حصلت على خطأ،
ونحن قد حصلت على هذا الإعلان صراحة وظيفة مكتبة printf.
يبدو أننا في حاجة للذهاب في وتشمل # standardio.h.
ومع ذلك، ينبغي تجميع كل شيء. نحن جميعا جيدة.
الآن دعونا حاول تشغيل شجرة ثنائية ونرى ما سيحدث.
نحن هنا،. / binary_tree،
ونحن نرى أنه، كما كنا نتوقع -
لأننا لم تنفذ حتى الآن يحتوي على،
أو بدلا من ذلك، قد وضعت للتو في المقابل كاذبة -
ونحن نرى أن مجرد انها كاذبة العودة لجميع من لهم،
بحيث انها جميعها تعمل في معظمها جيدة إلى حد ما.
>> دعونا نعود في الواقع وتنفيذ يحتوي على هذه النقطة.
أنا ذاهب إلى التمرير لأسفل، في التكبير، و-
تذكر، وكان الخوارزمية التي استخدمناها أن بدأنا في عقدة الجذر
وبعد ذلك في كل عقدة التي نواجهها، ونحن نفعل مقارنة،
وبناء على هذه المقارنة أن ننتقل إما إلى اليسار أو الطفل للطفل الحق.
هذا هو الذهاب الى نظرة مشابهة جدا لثنائي رمز البحث التي كتبنا في وقت سابق من هذا المصطلح.
عندما نبدأ قبالة، ونحن نعلم أننا نريد أن نتمسك العقدة الحالية
أننا نبحث في، والعقدة الحالية ستكون تهيئة إلى عقدة الجذر.
والآن، ونحن في طريقنا للحفاظ يمر الشجرة،
وتذكر أن لدينا حالة وقف -
عندما عملنا في الواقع من خلال المثال باليد -
عندما واجهناها كانت عقدة فارغة،
لا عندما نظرنا في طفل فارغة،
بل عندما انتقلنا فعلا إلى عقدة في شجرة
ووجدت أننا في عقدة فارغة.
ونحن في طريقنا لتكرار حتى الحالي لا تساوي قيمة خالية.
وما نحن ذاهبون للقيام؟
ونحن في طريقنا لمعرفة ما إذا (الحالي - قيمة ==> القيمة)،
ثم نحن نعلم أن لدينا فعلا وجدت العقدة التي نحن تبحث عنه.
حتى هنا، يمكننا العودة الحقيقية.
خلاف ذلك، ونحن نريد أن نرى ما إذا كان أو لم يكن هو قيمة أقل من القيمة.
إذا قيمة العقدة الحالية هي أقل من القيمة التي تبحث عنها،
ونحن في طريقنا للتحرك إلى اليمين.
لذلك، الحالي = الحالي -> right_child، وغير ذلك، ونحن في طريقنا للانتقال إلى اليسار.
= الحالي الحالي -> left_child؛ بسيط جدا.
>> ربما كنت تعترف الحلقة التي تبدو مشابهة جدا لهذا من
البحث الثنائية في وقت سابق من هذا المصطلح، إلا بعد ذلك كنا نتعامل مع منتصف، وانخفاض وارتفاع.
هنا، علينا فقط أن ننظر إلى القيمة الحالية،
لذلك فمن طيفة وبسيطة.
دعونا نتأكد من هذا الرمز هو العمل.
أولا، تأكد من أنه يجمع. يبدو أنه لا.
دعونا نحاول تشغيله.
وبالفعل، فإنه يطبع من كل ما كنا نتوقع.
يجدها 6 في الشجرة، لا العثور على 10 لأن 10 ليست في الشجرة،
ولا العثور على 1 إما لأن 1 أيضا ليس في الشجرة.
بارد الاشياء.
>> بخير. دعونا نعود لمواصفات لدينا ونرى ما هي الخطوة التالية.
الآن، انها تريد إضافة المزيد من العقد إلى شجرة لدينا.
انها تريد لإضافة 5، 2، و 8، وتأكد من أن لدينا يحتوي على رمز
لا يزال يعمل كما هو متوقع.
دعونا نذهب نفعل ذلك.
في هذه المرحلة، بدلا من القيام بذلك نسخة مزعج ولصق مرة أخرى،
دعونا كتابة دالة لإنشاء عقدة في الواقع.
إذا كان لنا أن انتقل لأسفل على طول الطريق الرئيسي ل، ونحن نرى أن كنا نفعل ذلك
مشابهة جدا رمز مرارا وتكرارا في كل مرة أننا نريد لإنشاء عقدة.
>> دعونا كتابة دالة التي من شأنها فعلا بناء عقدة بالنسبة لنا وإعادته.
انا ذاهب الى نسميها build_node.
انا ذاهب لبناء عقدة مع قيمة معينة.
تكبير هنا.
أول شيء أنا بصدد القيام به هو خلق مساحة للفي الواقع عقدة على الكومة.
لذلك، عقدة * ن = malloc (sizeof (عقدة))، ن -> قيمة = القيمة؛
ثم هنا، وانا ذاهب فقط لتهيئة كافة الحقول لتكون القيم المناسبة.
وفي النهاية، سوف نعود لدينا عقدة.
بخير. شيء واحد هو أن نلاحظ أن هذه الوظيفة هنا
هو الذهاب الى العودة مؤشر إلى الذاكرة التي تم تخصيصها كومة.
ما هو الجميل في هذا هو أن هذه العقدة الآن -
علينا أن نعلن ذلك على كومة لأنه إذا أعلنا ذلك على المكدس
ونحن لن تكون قادرة على القيام بذلك في هذه الوظيفة مثل هذا.
ومن شأن ذلك أن الذاكرة الخروج من نطاق
وسيكون باطلا إذا حاولنا الوصول إليه في وقت لاحق.
نحن نعلن منذ كومة-تخصيص الذاكرة،
نحن ستكون لدينا لرعاية تحرير في وقت لاحق
لبرنامجنا للا يتسرب أي الذاكرة.
كنا التسيير على أن لكل شيء آخر في التعليمات البرمجية
فقط للتبسيط في ذلك الوقت،
ولكن إذا كنت من أي وقت مضى وظيفة الكتابة التي تبدو مثل هذا
حيث كنت قد حصلت - بعض تسميتها malloc أو داخل realloc -
تريد للتأكد من أن كنت وضعت بعض النوع من التعليقات هنا أن يقول:
مهلا، أنت تعرف، والعودة عقدة كومة تخصيصها تهيئة مع قيمة تم تمريرها في.
ثم كنت تريد للتأكد من أن كنت وضعت في نوع من المذكرة التي تقول
يجب على المتصل تحرير الذاكرة إرجاعها.
وبهذه الطريقة، إذا كان شخص ما من أي وقت مضى يذهب ويستخدم تلك الوظيفة،
أنهم يعرفون أن كل ما نعود من تلك الوظيفة
وعند نقطة ما يجب أن يتم اطلاق سراحهم.
>> على افتراض أن كل شيء على ما يرام وجيدة هنا،
يمكننا أن نذهب إلى أسفل في نظامنا واستبدال كل هذه الخطوط هنا
مع دعوات لدينا وظيفة العقدة الإنشاء.
دعونا نفعل ذلك بسرعة حقا.
والجزء الأول أننا لن يحل محل هذا الجزء هو أسفل هنا
في الجزء السفلي حيث أننا سلك فعليا حتى العقد للإشارة إلى بعضها البعض،
لأن ذلك لا نستطيع أن نفعل في وظيفتنا.
ولكن، دعونا نفعل الجذر = build_node (7)؛ العقدة = * ثلاثة build_node (3)؛
* ستة عقدة = build_node (6)؛ العقدة * تسعة = build_node (9)؛
والآن، ونحن أيضا عن رغبته في إضافة العقد ل-
* خمسة عقدة = build_node (5)؛ العقدة * ثمانية = build_node (8)؛
وما هو عقدة أخرى؟ دعونا نرى هنا. أردنا أن تضيف أيضا 2 -
* اثنين = عقدة build_node (2)؛
بخير. في هذه المرحلة، ونحن نعلم أننا قد حصلت على 7، 3، 9، و 6 في
كل ما يصل السلكية مناسب، ولكن ماذا عن 5، 8، و 2 من؟
للحفاظ على كل شيء في الترتيب المناسب،
ونحن نعلم أن الأطفال الثلاثة، وهو الحق هو 6.
لذا، إذا نحن في طريقنا لإضافة 5،
ال 5 ينتمي أيضا في الجانب الأيمن من شجرة منها 3 هو الجذر،
5 حتى ينتمي والطفل الأيسر من 6.
يمكننا القيام بذلك عن طريق قائلا، ستة -> left_child = الخمسة؛
ومن ثم ال 8 وينتمي الطفل الأيسر من 9، 9 حتى -> left_child = 8؛
وثم 2 هو الطفل الأيسر من 3، ولذا فإننا يمكن أن نفعل ذلك هنا حتى - اليك -> left_child = اثنين؛
إذا كنت لا تتبع تماما إلى جانب ذلك، أقترح عليك استدراجه من نفسك.
>> بخير. دعونا حفظ هذا. دعونا نذهب الى هناك وتأكد من أنه لا يجمع،
ومن ثم يمكننا أن نضيف في المكالمات يحتوي دينا.
كل شيء يبدو وكأنه لا يزال يجمع.
دعونا نذهب في وإضافة في بعض يحتوي المكالمات.
مرة أخرى، انا ذاهب للقيام قليلا من النسخ واللصق.
الآن دعونا بحث عن 8، 5، و 2. بخير.
دعونا نتأكد من أن هذا يبدو كل شيء لا تزال جيدة. عظيم! حفظ والإقلاع عن التدخين.
الآن دعونا جعل وتجميع، والآن دعونا تشغيل.
من نتائج، يبدو أن كل شيء يعمل فقط لطيفة وجيدة.
عظيم! حتى الآن لدينا الدالة مكتوبة على لدينا.
دعونا نمضي قدما وبدء العمل على كيفية إدراج العقد في الشجرة
منذ ذلك الحين، ونحن نفعل ذلك الآن، الأمور ليست جميلة جدا.
>> إذا عدنا للمواصفات،
ما يطلب منا كتابة دالة يسمى إدراج - مرة أخرى، إرجاع BOOL
لأم لا يمكننا إدراج فعلا عقدة في شجرة -
ومن ثم يتم تحديد القيمة لتضاف الى الشجرة كما
والحجة الوحيدة لإدراج دالة لدينا.
سوف نعود صحيح لو تمكنا من إدراج قيمة في الواقع تحتوي على عقدة في الشجرة،
وهو ما يعني أننا، واحد، كان ذاكرة كافية،
ومن ثم اثنين، تلك العقدة لم تكن موجودة من قبل في الشجرة منذ -
نتذكر، ونحن لن يكون لها قيم مكررة في شجرة، فقط لجعل الامور بسيطة.
بخير. عودة إلى التعليمات البرمجية.
فتحه. تكبير قليلا، انتقل بعد ذلك إلى أسفل.
لنضع إدراج دالة الحق فوق يحتوي عليها.
مرة أخرى، فإنه سيكون من دعا إدراج BOOL (الباحث القيمة).
إعطائها مساحة أكثر من ذلك بقليل، وبعد ذلك، كإعداد افتراضي،
دعونا نضع في المقابل كاذبة في النهاية.
الآن إلى أسفل في قاع، دعونا نمضي قدما وبدلا من بناء يدويا العقد
في أنفسنا والأسلاك الرئيسية لهم حتى للإشارة إلى بعضها البعض مثل نقوم به،
سوف نعتمد على إدراج دالة لدينا للقيام بذلك.
لن نعتمد على إدراج دالة لدينا لبناء شجرة بأكملها من الصفر فقط حتى الآن،
بل سوف نتخلص من هذه الخطوط - we'll التعليق خارج هذه الأسطر -
أن بناء العقد 5، 8، و 2.
وبدلا من ذلك، سنقوم بإدراج المكالمات إلى إدراج دالة لدينا
للتأكد من أن الذي يعمل في الواقع.
هنا نذهب.
>> الآن لدينا تعليق الخروج هذه الخطوط.
ليس لدينا سوى 7، 3، 9، و 6 في شجرة لدينا في هذه المرحلة.
للتأكد من أن هذا هو كل عمل،
يمكننا تصغير، وجعل شجرة لدينا ثنائي،
تشغيله، ويمكننا أن نرى أن يحتوي تقول لنا الآن أننا على حق تماما -
5، 8، و 2 لم تعد موجودة في الشجرة.
العودة إلى رمز،
وكيف نحن ذاهبون لإدراج؟
تذكر ما فعلناه عندما كنا في الواقع إدراج 5، 8، و 2 سابقا.
لعبنا هذه المباراة Plinko حيث بدأنا في الجذر،
ذهب إلى أسفل شجرة واحدة تلو الأخرى من جانب واحد
حتى وجدنا الفجوة المناسبة،
السلكية وبعد ذلك نحن في عقدة في البقعة المناسبة.
ونحن في طريقنا لفعل الشيء نفسه.
هذا هو في الأساس مثل كتابة التعليمات البرمجية التي كنا في وظيفة يحتوي على
العثور على المكان الذي يجب أن تكون العقدة،
ثم ونحن في طريقنا فقط لإدراج عقدة هناك.
لنبدأ القيام بذلك.
>> لذلك لدينا عقدة الجذر = * الحالي، ونحن في طريقنا لمجرد اتباع يحتوي على رمز
حتى نجد أنه لا يعمل تماما بالنسبة لنا.
ونحن في طريقنا للذهاب من خلال شجرة في حين أن العنصر الحالي هو غير فارغة،
وإذا وجدنا أن قيمة الحالي هو يساوي القيمة التي نحاول إدراج -
حسنا، هذا هو واحد من الحالات التي لم نتمكن من إدراج فعلا عقدة
في شجرة لأن هذا يعني لدينا قيمة مكررة.
هنا ونحن في طريقنا للعودة في الواقع زائفة.
الآن، الا اذا قيمة الحالي هو أقل من القيمة،
نحن نعرف الآن أن نتحرك إلى اليمين
لأن القيمة ينتمي في النصف الأيمن من الشجرة الحالي.
خلاف ذلك، ونحن في طريقنا للانتقال إلى اليسار.
وهذا في الأساس لدينا تعمل على حق هناك.
>> عند هذه النقطة، مرة واحدة لقد أكملنا هذه الحلقة من الوقت،
المؤشر الحالي لدينا سوف يتم الإشارة إلى قيمة خالية
إذا لم الدالة عادوا بالفعل.
نحن لها بالتالي الحالي في المكان الذي نريد إدراج عقدة جديدة.
ما زال يتعين القيام به هو بناء في الواقع عقدة جديدة،
والتي يمكن أن نقوم به بسهولة جدا.
يمكننا استخدام لدينا عقدة بناء فائقة مفيد وظيفة،
وشيء لم نفعل سابقا -
نحن فقط نوع من تولى أمرا مفروغا منه ولكن الآن سنفعل فقط للتأكد من -
سنقوم اختبار للتأكد من أن القيمة التي تم إرجاعها بواسطة عقدة جديدة في الواقع
غير فارغة، لأننا لا نريد لبدء الوصول إلى تلك الذاكرة إذا كان لاغيا.
يمكننا اختبار للتأكد من أن عقدة جديدة لا تساوي فارغة.
أو بدلا من ذلك، يمكننا أن نرى فقط إذا كان هو في الواقع باطلة،
وإذا كانت فارغة، ثم يمكن أن نعود فقط كاذبة في وقت مبكر.
>> في هذه المرحلة، علينا أن سلك عقدة جديدة إلى المركز المناسب لها في الشجرة.
إذا نظرنا إلى الوراء في الرئيسية وأين كنا فعلا الأسلاك في القيم من قبل،
ونحن نرى أن الطريقة كنا نفعل عندما كنا نرغب في وضع 3 في شجرة
ونحن الوصول إلى الطفل الأيسر من جذورها.
كان لدينا عندما نضع 9 في الشجرة، للوصول إلى حق الطفل جذورها.
كان علينا أن يكون مؤشر إلى الوالدين من أجل وضع قيمة جديدة في الشجرة.
التمرير مرة أخرى إلى إدراج، وهذا لن تعمل تماما هنا
لأننا لم يكن لديك مؤشر الرئيسي.
ما نريد أن تكون قادرة على القيام به هو، في هذه المرحلة،
تحقق قيمة الأصل وانظر - حسنا، يا الهي،
إذا قيمة الأصل هو أقل من القيمة الحالية،
ثم يجب الطفل الأم الحق يكون عقدة جديدة؛
خلاف ذلك، يجب الطفل الأم اليسار يكون عقدة جديدة.
ولكن، لم يكن لدينا هذا المؤشر الرئيسي تماما حتى الآن.
>> من أجل الحصول على ذلك، ونحن في طريقنا في الواقع لدينا لتتبع ذلك ونحن نمضي من خلال شجرة
والعثور على بقعة مناسبة في حلقة اعلاه.
يمكننا القيام بذلك عن طريق التمرير لأعلى مرة أخرى إلى أعلى إدراج دالة لدينا
وتتبع مؤشر متغير آخر يسمى الأصل.
ونحن في طريقنا لتعيين أنه يساوي فارغة في البداية،
ثم في كل مرة نذهب من خلال الشجرة،
ونحن في طريقنا لتعيين المؤشر الرئيسي لتتناسب مع مؤشر الحالية.
تعيين الأصل تساوي الحالي.
بهذه الطريقة، في كل مرة نمر بها،
ونحن في طريقنا لضمان أن ما يحصل مؤشر الحالية زيادة
المؤشر الرئيسي يلي ذلك - فقط مستوى واحد أعلى من المؤشر الحالي في الشجرة.
أن جميع تبدو جيدة.
>> أعتقد أن الشيء الوحيد الذي سنقوم ترغب في ضبط هذا هو بناء فارغة عقدة العودة.
من أجل الحصول على عقدة لبناء الواقع بنجاح العودة فارغة،
سيكون لدينا لتعديل هذا الرمز،
لأن هنا، ونحن لم اختبارها للتأكد من أن malloc عاد مؤشر صالح.
لذا، إذا (ن = NULL!)، ثم -
إذا malloc عاد مؤشر صالحة، ثم سنقوم تهيئة ذلك؛
خلاف ذلك، سوف نعود فقط والتي في نهاية المطاف العودة فارغة بالنسبة لنا.
الآن يبدو كل شيء جيد جدا. دعونا نتأكد من هذا الواقع يجمع.
جعل شجرة ثنائية، وأوه، لقد حصلت على بعض الاشياء يجري هنا.
>> ونحن قد حصلت على وظيفة إعلان ضمني بناء العقدة.
مرة أخرى، مع هذه المجمعات، ونحن في طريقنا للبدء في الأعلى.
ما يعني أنه يجب أن ادعو بناء العقدة قبل لقد أعلن فعلا.
دعونا نعود إلى رمز بسرعة حقا.
انتقل لأسفل، والمؤكد، وأعلن مهامي إدراج
أعلاه وظيفة العقدة إنشاء،
ولكنني أحاول أن استخدام بناء عقدة داخل إدراج.
انا ذاهب للذهاب في ونسخة - ثم لصق وظيفة العقدة بناء الطريق حتى هنا في الأعلى.
وبهذه الطريقة، نأمل أن تعمل. دعونا نعطي هذا آخر الذهاب.
الآن يقوم بإعداد جميع. كل شيء جيد.
>> ولكن في هذه المرحلة، ونحن في الواقع لم يسمى وظيفتنا إدراج.
نحن نعرف فقط أنه يجمع، لذلك دعونا نذهب في بعض المكالمات ووضع فيها
دعونا نفعل ذلك في وظيفة الرئيسية لدينا.
هنا، نحن من علق 5، 8، و 2،
ومن ثم لم نكن سلك عنها هنا إلى أسفل.
دعونا جعل بعض المكالمات لإدراج،
ودعونا أيضا استخدام نفس النوع من الاشياء التي كنا
عندما قدمنا ​​هذه الدعوات printf للتأكد من أن كل شيء لم يحصل إدراج بشكل صحيح.
أنا ذاهب إلى نسخ ولصق،
وبدلا من يحتوي نحن في طريقنا للقيام إدراج.
وبدلا من 10، 6، و 1، ونحن في طريقنا لاستخدام 5، 8، و 2.
وينبغي إدراج هذه نأمل 5، 8، و 2 في الشجرة.
ترجمة. كل شيء جيد. الآن سنقوم بتشغيل برنامجنا في الواقع.
>> عاد كل شيء زائف.
لذلك، لم 5، 8، و 2 لا تذهب، ويبدو أن لا يحتوي على العثور عليها أيضا.
ما الذي يحدث؟ دعونا تصغير.
كانت المشكلة الأولى التي يبدو أن إدراج عودة كاذبة،
ويبدو أن هذا هو لأننا في ترك الدعوة عودتنا كاذبة،
ونحن في الواقع لم يعد صحيحا.
يمكننا إعداد ذلك.
والمشكلة الثانية هي، الآن حتى لو كنا نفعل - حفظ هذا، إنهاء هذا،
جعل تشغيل مرة أخرى، وأنه ترجمة، ثم تشغيله -
ونحن نرى أن هناك شيئا آخر يحدث هنا.
ومازال 5 و 8، و 2 لم يتم العثور في الشجرة.
الأمر كذلك، فما الذي يحدث؟
>> دعونا نلقي نظرة على هذا في التعليمات البرمجية.
دعونا نرى ما اذا كنا نستطيع هذا الرقم.
نبدأ مع الوالد لا يتم فارغة.
وضعنا المؤشر الحالي يساوي مؤشر الجذر،
ونحن في طريقنا للعمل طريقنا إلى أسفل من خلال الشجرة.
إذا كانت العقدة الحالية ليست فارغة، ثم نحن نعلم أننا يمكن أن تتحرك إلى أسفل قليلا.
وضعنا المؤشر الرئيسي لدينا ليكون مساويا لمؤشر الحالية،
التحقق من قيمة - إذا كانت القيم هي نفسها عدنا كاذبة.
إذا كانت القيم هي أقل انتقلنا إلى اليمين؛
خلاف ذلك، انتقلنا إلى اليسار.
ثم نبني عقدة. أنا تكبير قليلا.
وهنا، ونحن في طريقنا لمحاولة سلك عن القيم أن تكون هي نفسها.
ما الذي يحدث؟ دعونا نرى ما اذا كان ربما Valgrind يمكن أن تعطينا لمحة.
>> أود أن استخدام Valgrind فقط لأن Valgrind بسرعة حقا يدير
ويخبرك إذا كان هناك أي أخطاء الذاكرة.
عندما ندير Valgrind على المدونه،
كما ترون الحق here--Valgrind./binary_tree--and ضرب أدخل.
ترى أن لم يكن لدينا أي خطأ الذاكرة، بحيث يبدو مثل كل شيء على ما يرام حتى الآن.
لدينا بعض التسريبات الذاكرة، التي نعرف، لأننا لسنا
يحدث لتحرير أي من العقد لدينا.
دعونا نحاول تشغيل GDB لمعرفة ما يجري في الواقع على.
سنفعل GDB / binary_tree. تمهيد الامر على ما يرام.
دعونا تعيين نقطة فاصل على إدراج.
دعونا تشغيل.
يبدو أننا في الواقع لا يسمى إدراج.
يبدو أن المشكلة هي أن مجرد تغيير عندما كنت هنا في أسفل الرئيسية -
كل هذه المكالمات من printf يحتوي على -
لم أكن في الواقع تغيير هذه الدعوة إدراج.
الآن دعونا يعطي هو محاولة. دعونا ترجمة.
جميع تبدو جيدة هناك. الآن دعونا نحاول تشغيله، ونرى ما سيحدث.
بخير! كل شيء يبدو جيدا جدا هناك.
>> الشيء النهائية للتفكير هو، هل هناك أي حالات لهذا حافة إدراج؟
وتبين أن، أيضا، حالة واحدة أن يكون حافة دائما مثيرة للاهتمام للتفكير
هو، ماذا يحدث إذا شجرة الخاص بك فارغة واستدعاء هذه الدالة إدراج؟
وسوف يعمل؟ حسنا، دعونا محاولة إعطائها.
- binary_tree ج -
الطريق ونحن في طريقنا لاختبار هذا، ونحن في طريقنا للذهاب الى وظيفتنا الرئيسية،
وبدلا من الأسلاك هذه العقد حتى مثل هذا،
ونحن في طريقنا لمجرد التعليق خارج الشيء بأكمله،
وبدلا من الأسلاك حتى العقد أنفسنا،
يمكننا فعلا اذهبوا الى الامام وحذف كل هذا.
ونحن في طريقنا لجعل كل شيء دعوة للإدراج.
لذلك، دعونا نفعل - بدلا من 5، 8، و 2، ونحن في طريقنا لإدراج 7، 3، و 9.
وبعد ذلك سوف نريد أيضا لإدراج (6)، أيضا.
حفظ. الإقلاع عن التدخين. جعل شجرة ثنائية.
يقوم بإعداد جميع.
يمكننا فقط تشغيله كما هو ونرى ما سيحدث،
لكنه سيحتاج أيضا إلى أن تكون مهمة حقا للتأكد من أن
ليس لدينا أي أخطاء الذاكرة،
وبما أن هذا هو واحد من الحالات تفوقنا التي نعرفها عنه.
>> دعونا تأكد من أنه يعمل بشكل جيد تحت Valgrind،
الذي سوف نقوم به فقط عن طريق تشغيل Valgrind / binary_tree.
يبدو في الواقع لدينا خطأ واحد من سياق -
لدينا هذا الخطأ تجزئة.
ماذا حدث؟
يقول لنا الواقع Valgrind حيث هو.
تصغير قليلا.
يبدو أنه يحدث في إدراج دالة لدينا،
حيث لدينا غير صالحة للقراءة من حجم 4 في إدراج، خط 60.
دعونا نعود ونرى ما يجري هنا.
تصغير سريع حقا.
أريد أن تأكد من أنه لا يذهب إلى حافة الشاشة حتى نتمكن من رؤية كل شيء.
سحب في أن قليلا. بخير.
انتقل لأسفل، والمشكلة هنا هي الحق.
ماذا يحدث إذا كان لنا أن ننكب وعقدة الحالية لدينا بالفعل فارغة،
عقدة لدينا الأم باطل، إذا كان الأمر كذلك فإننا البصر على أعلى جدا هنا الحق، -
إذا كانت هذه حلقة في حين لم ينفذ فعليا
لأن القيمة الحالية لدينا باطل - باطل الجذر لدينا حتى الحالي باطل -
ثم لدينا الوالد لم يحصل على تعيين الحالي أو إلى قيمة صالحة،
لذلك، سوف تكون الأم أيضا فارغة.
علينا أن نتذكر أن للتحقق من
بحلول الوقت الذي نبدأ هنا، ونبدأ الوصول إلى قيمة الأصل.
لذلك، ماذا يحدث؟ حسنا، إذا كان الوالد هو باطل -
إذا كان (الوالد == NULL) - ثم نحن نعلم أن
يجب أن لا يكون هناك أي شيء في الشجرة.
يجب أن تكون محاولة لإدراجها في جذورها.
يمكننا أن نفعل ذلك فقط من خلال وضع الجذر يساوي عقدة جديدة.
ثم في هذه المرحلة، ونحن لا نريد في الواقع أن يذهب من خلال هذه الأشياء الأخرى.
بدلا من ذلك، والحق هنا، يمكننا أن نفعل إما آخر، IF-آخر،
أو يمكن أن الجمع بين كل شيء هنا في آخر،
ولكن هنا سنستخدم فقط آخر، وتفعل ذلك بهذه الطريقة.
الآن، ونحن في طريقنا لاختبار للتأكد من أن الأم لدينا ليست فارغة
قبل ذلك في الواقع محاولة للوصول إلى الحقول الخاصة به.
وسيساعدنا هذا خطأ تجنب تجزئة.
لذلك، فإننا الإقلاع عن التدخين، تصغير، تجميع، تشغيل.
>> عدم وجود أخطاء، ولكن لا يزال لدينا مجموعة من التسرب في الذاكرة
لأننا لم سراح أي من العقد لدينا.
ولكن، إذا كان لنا أن ترتفع هنا ونحن ننظر إلى النسخة المطبوعة لدينا،
ونحن نرى أنه، حسنا، يبدو كل إدراج لدينا كانوا عائدين الحقيقية، وهو أمر جيد.
يدرج كلها صحيحة،
وبعد ذلك مناسبا يحتوي على المكالمات صحيح أيضا.
>> عمل جيد! يبدو أننا قد كتبت بنجاح إدراج.
هذا كل ما لدينا لهذا الأسبوع مشكلة مواصفات مجموعة.
أحد التحديات متعة للتفكير هو كيف لك أن تذهب فعلا في
والافراج عن كل من العقد في هذه الشجرة.
يمكننا أن نفعل ذلك بعدة طرق مختلفة،
ولكن سأترك ذلك متروك لكم لتجربة،
وباعتبارها تحديا متعة، ومحاولة التأكد من أن يمكنك التأكد من
أن هذا التقرير Valgrind إرجاع أية أخطاء والتسريبات لا.
>> حظا سعيدا في هذا الأسبوع مجموعة هوفمان مشكلة الترميز،
وسنرى في الأسبوع القادم!
[CS50.TV]