DOUG لويد: كل الحق، حتى هذه النقطة كنت
ربما مألوفة جدا مع المصفوفات والقوائم المرتبطة
وهو الابتدائي اثنين هياكل البيانات التي قمت
تحدث عن لحفظ مجموعات من بيانات من أنواع البيانات مماثلة نظمت.
>> الآن نحن بصدد الحديث حول زوجين من الاختلافات
على المصفوفات والقوائم المرتبطة.
في هذا الفيديو ونحن في طريقنا للحديث عن مداخن.
على وجه التحديد ونحن في طريقنا للحديث حول تسمى بنية بيانات كومة.
نذكر من المناقشات السابقة حول مؤشرات والذاكرة،
أن المكدس هو أيضا اسم لجزء من الذاكرة
حيث أعلن ثابت ذاكرة memory-- أنك
اسم، المتغيرات التي سمها، وآخرون إلى ذلك وظيفة الإطارات التي نحن أيضا
وجود إطارات مكدس الاستدعاءات.
لذلك هذا هو بنية بيانات مكدس ليس قطعة مكدس الذاكرة.
حسنا.
>> ولكن ما هو كومة؟
حتى انها مجرد حد كبير نوع خاص من هيكل
التي تحافظ على البيانات بطريقة منظمة.
وهناك اثنان جدا طرق شائعة لتنفيذ
مداخن باستخدام هياكل البيانات اثنين أننا بالفعل على دراية،
المصفوفات والقوائم المرتبطة.
ما الذي يجعل خاص كومة هو الطريقة التي نضع المعلومات
في كومة، والطريقة التي إزالة المعلومات من المكدس.
وعلى وجه الخصوص مع أكوام القاعدة ليست سوى أكثر
في الآونة الأخيرة عنصر إضافي يمكن إزالتها.
>> حتى التفكير في الامر كما لو انها المكدس.
نحن تتراكم المعلومات على رأس نفسه،
وفقط الشيء في الجزء العلوي من كومة يمكن إزالتها.
ونحن لا يمكن إزالة الشيء تحت لأن كل شيء آخر من شأنه
الانهيار والسقوط.
لذلك نحن حقا على بناء مكدس لن يكون لدينا لإزالة قطعة قطعة.
وبسبب هذا نشير عادة إلى كومة كهيكل LIFO،
تستمر في، انتهت الأولى.
LIFO، تستمر في، لأول مرة.
>> ذلك لأن هذا التقييد على كيف يمكن إضافة معلومات ل
وإزالتها من كومة، وهناك حقا اثنين فقط من الأشياء التي يمكن القيام به مع كومة.
يمكننا أن ندفع، وهو المصطلح الذي نستخدمه لإضافة
عنصر جديد إلى أعلى كومة، أو في حالة عدم وجود كومة
ونحن خلق من العدم، خلق المكدس في المقام الأول
سيكون دفع.
ثم البوب، وهذا النوع من CS المصطلح الذي نستخدمه لإزالة مؤخرا
وأضاف عنصرا من أعلى المكدس.
>> لذلك نحن في طريقنا للبحث في كل تطبيقات، سواء مجموعة تستند
وقائمة مرتبطة القائمة.
ونحن في طريقنا ل تبدأ مع مجموعة مقرها.
لذلك ها هي الفكرة الأساسية لما بنية البيانات كومة مجموعة مقرها
قد تبدو.
لدينا تعريف مكتوب هنا.
داخل ذلك لدينا اثنين من أعضاء أو حقول البنية.
لدينا مجموعة.
ومرة أخرى أنا باستخدام تعسفية قيمة نوع البيانات.
>> ولذلك فإن هذا يمكن أن يكون أي نوع البيانات، شار صحيح أو بعض البيانات الأخرى
اكتب قمت بإنشائه سابقا.
لذلك لدينا مجموعة واسعة من القدرات الحجم.
القدرة يجري رطل تعريف ثابت، ربما في مكان آخر في ملفنا.
لذلك نلاحظ بالفعل مع هذا الخصوص تنفيذ أننا ثاب
أنفسنا كما كان عادة الحال مع المصفوفات،
لا يمكننا تغيير حجم حيوي، حيث هناك عدد معين
عناصر الحد الأقصى الذي يمكن أن نضع في كومة دينا.
في هذه الحالة فإنه من عناصر القدرات.
>> نحن أيضا تتبع الجزء العلوي من كومة.
ما العنصر هو الأكثر وأضاف في الآونة الأخيرة إلى المكدس؟
ولذا فإننا تتبع ذلك في متغير يسمى القمة.
وكل هذا يحصل ملفوفة معا إلى نوع بيانات جديدة تسمى كومة.
ومرة واحدة ونحن خلقت هذا النوع من البيانات الجديد
يمكننا التعامل معها مثل أي نوع بيانات آخر.
يمكن أن نعلن كومة الصورة، تماما مثل يمكننا أن نفعل الباحث السينية، أو حرف Y.
وعندما نقول كومة الصورة، وأيضا ما يحدث
ونحصل على مجموعة من ذاكرة جانبا بالنسبة لنا.
>> وبهذه الصفة حالة لقد قررت على ما يبدو
10 لأني قد حصلت على متغير واحد من نوع كومة
الذي يحتوي على تذكر حقلين.
مجموعة، في هذه الحالة سوف أن تكون مجموعة من الأعداد الصحيحة
كما هو الحال في معظم الأمثلة التي ذكرتها.
ومتغير عدد صحيح آخر قادر على تخزين القمة،
وأضاف في الآونة الأخيرة عنصر إلى المكدس.
حتى واحد كومة واحدة من ما كنا تعريف فقط يشبه هذا.
انها تحتوي على مربع مجموعة من 10 ما
ستكون صحيحة في هذه الحالة و متغير آخر صحيح هناك في الأخضر
للإشارة إلى الجزء العلوي من كومة.
>> لتعيين أعلى كومة نحن نقول فقط s.top.
هذه هي الطريقة التي الوصول إلى مجال أذكر هيكل.
s.top يساوي 0 بفعالية هل هذا المكدس لدينا.
ذلك مرة أخرى لدينا اثنين من العمليات أننا يمكن أن تؤدي الآن.
يمكننا أن ندفع ونحن يمكن البوب.
دعونا نبدأ مع دفع.
مرة أخرى، ودفع هو إضافة جديدة عنصر إلى أعلى المكدس.
>> فماذا علينا أن نفعل في هذه المجموعة التنفيذ استنادا؟
كذلك في العام دفع ظيفة يسير
في حاجة إلى قبول مؤشر إلى المكدس.
الآن تأخذ ثانية وتفكر في ذلك.
لماذا نريد لقبول مؤشر إلى المكدس؟
نذكر من أشرطة الفيديو السابقة على نطاق ومؤشرات متغير،
ماذا سيحدث إذا أرسلنا فقط مكدس، ق بالأحرى في كمعلمة؟
ما من شأنه في الواقع أن تنتقل إلى هناك؟
نتذكر أننا بصدد إنشاء نسخة عندما كنا نقله إلى وظيفة
ما لم نستخدم المؤشرات.
وحتى هذه الوظيفة دفع الاحتياجات لقبول مؤشر إلى المكدس
ذلك أننا تغيير الواقع مكدس نعتزم تغيير.
>> دفع الشيء الآخر ربما يريد استعرض عنصرا بيانات القيمة النوع.
في هذه الحالة، مرة أخرى، صحيح أن ونحن في طريقنا لإضافة إلى الجزء العلوي من كومة.
لذلك لدينا لدينا المعلمتين.
ما نحن ذاهبون لل القيام به الآن داخل دفع؟
حسنا، ببساطة، نحن ذاهبون لمجرد إضافة هذا العنصر إلى أعلى المكدس
ثم قم بتغيير حيث أعلى المكدس، التي ق دوت قيمة أعلى.
لذلك هذا هو ما وظيفة الإعلان عن دفعة
قد تبدو وكأنها في القائم على مجموعة التنفيذ.
>> مرة أخرى هذه ليست قاعدة جامدة وسريعة هل يمكن أن تغيير هذه ولها
انها تختلف في طرق مختلفة.
ربما يتم التصريح الصورة عالميا.
وهكذا لا تحتاج حتى لتمرير أنها كمعلمة.
هذا هو مرة أخرى مجرد الحالة العامة للدفع.
وهناك مختلفة طرق لتنفيذ ذلك.
ولكن في هذه الحالة لدينا دفع على وشك أن يتزوج
حجتين، مؤشر إلى المكدس و عنصر بيانات القيمة نوع، صحيح
في هذه الحالة.
>> لذلك أعلنا الصورة، ونحن وقال s.top يساوي 0.
الآن دعونا دفع عدد 28 إلى المكدس.
حسنا ماذا يعني ذلك؟
حسنا حاليا أعلى المكدس هو 0.
وهكذا ما هو الأساس سيحدث هو
ونحن في طريقنا إلى التمسك عدد 28 في مجموعة 0 موقع.
واضحة جدا، والحق، أن وكان أعلى ونحن الآن على ما يرام.
ثم نحن بحاجة إلى تغيير ما والجزء العلوي من كومة أن يكون.
لذا في المرة القادمة ندفع عنصرا في،
ونحن في طريقنا لتخزينه في موقع مجموعة، وربما ليست 0.
نحن لا نريد للكتابة ما وضعت للتو هناك.
ولذا فإننا سوف تتحرك فقط الجزء العلوي إلى 1.
التي ربما من المنطقي.
>> الآن إذا أردنا أن وضع عنصر آخر إلى المكدس، ويقول نحن نريد لدفع 33،
كذلك نحن الآن مجرد الذهاب الى اتخاذ 33 ووضعها في مجموعة رقم موقع
1، ثم قم بتغيير رأس لدينا كومة أن تكون مجموعة موقع رقم اثنين.
حتى إذا كان في المرة القادمة نريد ل دفع عنصر إلى المكدس،
انها سوف توضع في مجموعة موقع 2.
ودعونا نفعل ذلك المزيد من مرة واحدة.
سنقوم دفع 19 الخروج من المداخن.
سوف نضع 19 في مجموعة موقع 2 وتغيير الجزء العلوي من كومة دينا
أن تكون مجموعة موقع 3 إذا كان الأمر كذلك فإننا في المرة القادمة
تحتاج إلى جعل دفع نحن على ما يرام.
>> حسنا، هذا ما دفع باختصار.
ماذا عن تفرقع؟
لذلك ظهرت هو نوع من النظير لدفع.
انها كيف يمكننا إزالة البيانات من المكدس.
واحتياجات البوب ​​العامة للقيام بما يلي.
عليها أن تقبل مؤشر إلى كومة، ومرة ​​أخرى في الحالة العامة.
في بعض الحالات الأخرى التي قد أعلنت مكدس على الصعيد العالمي،
وفي هذه الحالة لا تحتاج لتمريرها في لأنه يحتوي بالفعل الوصول إليها
كمتغير العالمي.
ولكن بعد ذلك ماذا تفعل يتعين علينا القيام به؟
كذلك كنا تزايد الجزء العلوي من المكدس في دفع،
لذلك نحن ربما تريد الذهاب الى لإنقاص الجزء العلوي من كومة
في موسيقى البوب، أليس كذلك؟
وبعد ذلك بالطبع نحن أيضا تريد الذهاب
لإرجاع القيمة أننا إزالته.
إذا نحن مضيفا العناصر، ونحن نريد للحصول على العناصر في وقت لاحق على،
ونحن ربما في الواقع تريد تخزينها لذلك نحن
لا مجرد حذفها من كومة ثم لا تفعل شيئا معهم.
عموما إذا نحن دفع وظهرت هنا
نحن نريد لتخزين هذه المعلومات بطريقة ذات مغزى
وذلك لا يجعل بمعنى أن مجرد تجاهل ذلك.
لذلك ينبغي على هذه الوظيفة ربما إرجاع قيمة بالنسبة لنا.
>> لذلك هذا هو ما إعلانا لالبوب قد تبدو وكأنها هناك في أعلى اليسار.
هذه ترجع الدالة بيانات القيمة النوع.
مرة أخرى كنا باستخدام الأعداد الصحيحة طوال الوقت.
ويقبل مؤشر إلى كومة كما الحجة الوحيدة، أو المعلمة وحيد.
فما هو البوب ​​تنوي القيام به؟
دعونا نقول أننا نريد الآن البوب ​​عنصرا الخروج من الصورة.
لذلك تذكر قلت أن الأكوام مشاركة في، لأول مرة، وهياكل البيانات LIFO.
العنصر الذي هو ذاهب ل يمكن إزالتها من المكدس؟
هل اعتقد 19؟
لأنك كنت على حق.
19 كان العنصر الأخير أضفنا إلى كومة عندما كنا دفع العناصر على،
وذلك يحدث لأول العنصر الذي يحصل على إزالتها.
كما لو قلنا 28، و ثم وضعنا 33 على أعلى من ذلك،
ونضع 19 على رأس ذلك.
العنصر الوحيد الذي يمكن أن تقلع هو 19.
>> الآن في الرسم البياني هنا ما فعلته هو نوع من حذف 19 من المصفوفة.
هذا ليس واقعيا ما نحن في طريقنا للقيام به.
نحن ذاهبون لمجرد نوع من يدعي أنه ليس هناك.
انها لا تزال هناك في هذا الموقع الذاكرة،
لكننا ذاهبون لمجرد تجاهله عن طريق تغيير الجزء العلوي من كومة دينا
من كونها 3-2.
حتى لو كنا لدفع الآن عنصر آخر إلى المكدس،
فإنه سيكتب أكثر من 19.
>> ولكن دعونا لا تذهب من خلال عناء حذف 19 من المكدس.
يمكننا أن نتظاهر فقط لم يكن هناك.
لأغراض كومة انها ذهبت إذا نغير أعلى لتكون 2 بدلا من 3.
كل الحق، حتى أن كان الى حد كبير.
هذا كل ما عليك القيام به لموسيقى البوب ​​عنصر خارج.
دعونا نفعل ذلك مرة أخرى.
حتى لقد تمييزه باللون الأحمر هنا ل تشير إلى أننا نحرز مكالمة أخرى.
ونحن في طريقنا للقيام بنفس الشيء.
>> فما الذي سيحدث؟
حسنا، نحن ذاهبون لتخزين 33 في العاشر ونحن في طريقنا
لتغيير الجزء العلوي من كومة إلى 1.
بحيث إذا كنا الآن لدفع ل عنصر في كومة التي نحن
تنوي القيام به في الوقت الراهن، ماذا سيحدث
ونحن في طريقنا الكتابة الفوقية مجموعة موقع رقم 1.
ذلك أن 33 التي كانت نوعا من اليسار وراء ذلك نحن تظاهرت فقط
ليس هناك بعد الآن، ونحن ذاهبون فقط لهزم ووضعها هناك 40 بدلا من ذلك.
وبعد ذلك بالطبع، منذ قدمنا ​​دفعة،
ونحن في طريقنا إلى زيادة في أعلى المكدس 1-2
بحيث إذا نحن الآن إضافة عنصر آخر أنها سوف
انتقل إلى مجموعة موقع رقم اثنين.
>> الآن القوائم المرتبطة هي آخر طريقة لتنفيذ رزمة.
وإذا كان هذا التعريف على الشاشة هنا تبدو مألوفة بالنسبة لك،
ذلك لأنه يبدو تقريبا بالضبط نفس الشيء، في الواقع،
انها الى حد كبير هو بالضبط نفس قائمة مرتبطة منفردة،
إذا كنت تذكر من مناقشتنا ل القوائم المرتبطة منفردة في فيديو آخر.
والقيد الوحيد هنا هو بالنسبة لنا والمبرمجين،
نحن لا يسمح لل إدراج أو حذف عشوائيا
من القائمة المرتبطة منفردة الذي يمكننا القيام به سابقا.
يمكننا الآن سوى إدراج وحذف من الجبهة أو أعلى مرتبطة
القائمة.
هذا هو حقا فقط الفرق بالرغم من ذلك.
هذا هو خلاف ذلك قائمة مرتبطة منفردة.
انها فقط التقييد استبدال على أنفسنا
كما أن المبرمجين يتغير قبل أن تتحول إلى كومة.
>> القاعدة هنا هي أن تحافظ دائما على المؤشر إلى رأس قائمة مرتبطة.
هذا هو بالطبع عموما قاعدة مهمة لأول مرة.
لقائمة مرتبطة منفردة على أي حال كنت تحتاج مؤشر فقط في الرأس
من أجل أن يكون هذا سلسلة تكون قادرة على الرجوع
إلى كل عنصر آخر في القائمة المرتبطة.
ولكن هذا لا سيما المهم مع كومة.
وهكذا عموما كنت تريد الذهاب الى الواقع
هذا مؤشر على أن يكون المتغير العالمي.
انه سيكون على الارجح الى حتى يكون أسهل بهذه الطريقة.
فما هي النظير من الشد والبوب؟
الصحيح.
لذلك دفع مرة أخرى يضيف عنصر جديد إلى المكدس.
في قائمة مرتبط يعني أننا ذاهبون لدينا
لإنشاء عقدة جديدة نحن الذهاب لإضافة إلى القائمة المرتبطة،
ثم اتبع الخطوات المتأنية أن قمنا بوضع سابقا
في القوائم المرتبطة منفردة لإضافته إلى سلسلة دون كسر سلسلة
وفقدان أو اليتم أي عناصر القائمة المرتبطة.
وهذا أساسا ما أن فقاعة صغيرة من النص يلخص هناك.
ودعونا نلقي نظرة في ذلك كما رسم تخطيطي.
>> حتى هنا قائمة مرتبطة لدينا.
أنه يحتوي على أربعة عناصر في نفس الوقت.
وأكثر تماما هنا لدينا كومة التي تحتوي على أربعة عناصر.
ودعونا نقول أننا نريد الآن ل دفع بند جديد على هذا المكدس.
ونحن نريد أن دفع جديد البند قيمتها البيانات هو 12.
حسنا ماذا نحن فاعلون؟
حسنا أولا نحن في طريقنا لل مساحة malloc، حيوي
تخصيص مساحة لعقدة جديدة.
وبالطبع فور نحن إجراء مكالمة إلى malloc نحن دائما
تأكد من التحقق من وجود باطل، لأنه إذا وصلنا لاغية العودة
كان هناك نوع من المشكلة.
نحن لا نريد أن dereference أن اغية سوف المؤشر أو كنت تعاني من خطأ ثوانى.
هذا ليس جيدا.
لذلك قمنا malloced من العقدة.
سوف نفترض لدينا النجاح هنا.
ونحن في طريقنا إلى وضع 12 في حقل البيانات من تلك العقدة.
الآن هل يتذكر أي من المؤشرات لدينا الخطوات المقبلة لذلك نحن لا كسر السلسلة؟
لدينا عدة خيارات هنا ولكن الوحيد الذي سيكون آمنة
هو وضع الأخبار المؤشر بجانب نقطة في الرأس القديم من القائمة
أو ماذا سيكون قريبا رئيس القديم من القائمة.
والآن بعد أن كل من سلسلت العناصر معا،
يمكننا فقط نقل قائمة إلى نقطة إلى نفس المكان الذي يفعل جديدة.
ونحن لدينا الآن دفعت فعليا عنصر جديد على الجزء الأمامي من المكدس.
>> لموسيقى البوب ​​ونحن نريد فقط ل حذف هذا العنصر الأول.
وذلك أساسا ما يتعين علينا القيام به هنا،
كذلك علينا أن نجد العنصر الثاني.
في نهاية المطاف التي ستصبح الجديد يتوجه بعد أن حذف أول واحد.
لذلك نحن بحاجة فقط لتبدأ من بداية، خطوة واحدة إلى الأمام.
مرة واحدة لقد حصلت على عقد على واحدة إلى الأمام من حيث نحن حاليا
نحن يمكن حذف أول واحد بأمان وبعد ذلك يمكننا فقط نقل رئيس
للإشارة إلى ما كان ولاية ثانية ثم الآن
هو الأول بعد أن لقد تم حذف العقدة.
>> ذلك مرة أخرى، مع نظرة في ذلك كما رسم تخطيطي نحن
تريد لموسيقى البوب ​​الآن العنصر الخروج من هذا المكدس.
فماذا نفعل؟
حسنا نحن أولا الذهاب الى خلق مؤشر الجديد الذي يجري
للإشارة إلى نفس المكان رئيسا.
ونحن في طريقنا لنقلها موقف واحد إلى الأمام بالقول متساوين بالسفر
بالسفر المقبل على سبيل المثال، والتي من شأنها دفع مؤشر بالسفر واحد
موقف الأمام.
والآن بعد أن حصلنا على الاستمرار على العنصر الأول
من خلال مؤشر يسمى القائمة، و العنصر الثاني من خلال مؤشر يسمى
بالسفر، ونحن يمكن حذفها بأمان أن العنصر الأول من المكدس
دون أن تفقد بقية من سلسلة لأننا
لديك وسيلة للإشارة إلى العنصر الثاني
إلى الأمام عن طريق ل دعا مؤشر بالسفر.
>> وحتى الآن نستطيع أن نحرر هذه العقدة.
يمكننا أن القائمة تحرير.
وبعد ذلك كل ما نحتاج أن نفعله الآن هو قائمة الانتقال للإشارة إلى نفس المكان
أن بالسفر لا، ونحن نوع من الخلف حيث بدأنا قبل أن دفعت 12
على في المقام الأول، والحق.
وهذا هو بالضبط ما كنا عليه.
كان لدينا هذا العنصر أربعة المكدس.
أضفنا الخامس.
دفعنا خمس عنصر على، ومن ثم نحن
برزت في الآونة الأخيرة أن معظم وأضاف العنصر التراجع.
>> هذا هو حقا الى حد كبير كل ما في المداخن.
يمكنك تنفيذها في المصفوفات.
يمكنك تنفيذها في القوائم المرتبطة.
هناك، بطبيعة الحال، وغيرها طرق لتنفيذها كذلك.
في الأساس السبب سوف نستخدم مداخن هو الحفاظ على البيانات في مثل هذه الطريقة
وأضاف أن معظم مؤخرا العنصر هو أول شيء نحن
تريد الذهاب الى الحصول على العودة.
أنا دوغ ويد، وهذا هو cs50.