DOUG لويد: حتى في CS50، لقد المغطاة الكثير من بنيات بيانات مختلفة، الصحيح؟ لقد رأينا المصفوفات، وربطها القوائم والجداول التجزئة، ومحاولات المداخن وقوائم الانتظار. سنقوم أيضا معرفة قليلا حول الأشجار وأكوام، ولكن في الحقيقة كل هذه فقط في نهاية حتى يتم الاختلافات على موضوع. هناك حقا هذه نوع من أربعة الأفكار الأساسية أن كل شيء يمكن أن تختزل إلى. المصفوفات، القوائم المتصلة، الجداول التجزئة، ومحاولات. وكما قلت، هناك اختلافات عليها، ولكن هذه هي جميلة يحدث كثيرا أن نلخص كل شيء ونحن في طريقنا للحديث حول في هذه الفئة من حيث C. ولكن كيف تفعل كل هذه ترقى، أليس كذلك؟ لقد تحدثنا عن إيجابيات وسلبيات كل في أشرطة الفيديو منفصلة عليهم، ولكن هناك الكثير من الأرقام الحصول على القيت حولها. هناك الكثير من عام أفكار الحصول ألقيت حولها. دعونا نحاول وتعزيز ذلك في مكان واحد فقط. دعونا الموازنة بين الايجابيات ضد السلبيات، والنظر بنية البيانات التي قد تكون البيانات الصحيح هيكل لموقفك، أي نوع من البيانات التي تقوم بتخزين. أنت لا تحتاج بالضرورة دائما ل استخدام بسرعة فائقة الإدراج أو الحذف، وبحث من TRIE إذا كنت حقا لا يهمني حول إدراج وحذف أكثر مما ينبغي. إذا كنت بحاجة فقط بسرعة عشوائي وصول، ربما مجموعة أفضل. لذلك دعونا استخلاص ذلك. دعونا نتحدث عن كل واحد من أربعة أنواع رئيسية من هياكل البيانات التي تحدثنا عنها، و انظر فقط في حين أنها قد تكون جيدة، وعندما أنها قد لا تكون على ما يرام. لذلك دعونا نبدأ مع المصفوفات. لذلك الإدراج، وهذا النوع من سيئة. 

الإدراج في نهاية مجموعة على ما يرام، إذا نحن بناء مجموعة ونحن نمضي. ولكن إذا كنا بحاجة إلى إدراج العناصر في الوسط بذاكرتي إلى الإدراج نوع، وهناك الكثير التحول إلى احتواء عنصر في هناك. وإذا كان الأمر كذلك ونحن في طريقنا لإدراج في أي مكان ولكن في نهاية صفيف، وهذا ربما ليست كبيرة. 

وبالمثل، الحذف، إلا أننا حذف من نهاية صفيف، وربما أيضا ليست كبيرة إذا نحن لا نريد أن ترك فجوات فارغة، التي عادة ما نقوم به لا. نحن نريد لإزالة عنصر، و ثم نوع من جعله دافئ مرة أخرى. وحتى حذف عناصر من صفيف، أيضا ليست كبيرة. 

البحث، رغم ذلك، هو عظيم. لدينا الوصول العشوائي، بحث مستمر الوقت. نقول فقط سبعة، ونذهب لمجموعة نقل سبعة. نقول 20، مع العودة إلى مجموعة نقل 20. ليس لدينا تكرار عبر. هذا أمر جيد جدا. 

المصفوفات هي أيضا من السهل نسبيا لفرز. في كل مرة تحدثنا عن الفرز الخوارزمية، مثل اختيار نوع، الإدراج النوع، فقاعة النوع، ودمج النوع، وكنا دائما صفائف للقيام بذلك، لصفائف من السهل جدا ل نوع، نسبة إلى هياكل البيانات رأيناه حتى الآن. 

انهم أيضا صغيرة نسبيا. ليس هناك الكثير من مساحة إضافية. كنت مجرد مجموعة جانبا تماما كما بكثير كما تحتاج إلى عقد البيانات الخاصة بك، وهذا الى حد كبير. حتى انهم صغيرة جدا وكفاءة في هذا الطريق. ولكن الجانب السلبي آخر، على الرغم من غير أنها ثابتة في الحجم. علينا أن نعلن بالضبط كيف كبير نريد أن يكون لدينا مجموعة، ونحن فقط على طلقة واحدة في ذلك. ونحن لا يمكن أن ينمو ويتقلص ذلك. 

إذا نحن بحاجة إلى النمو أو الانكماش، ونحن حاجة إلى أن يعلن مجموعة جديدة تماما، نسخ كافة عناصر مجموعة الأولى في مجموعة الثانية. وإذا كان لنا أن أخطأت الوقت، علينا أن نفعل ذلك مرة أخرى. ليس عظيما جدا. حتى صفائف لا تعطينا مرونة لديك أرقام مختلفة من العناصر. 

مع قائمة مرتبطة، الإدراج من السهل جدا. نحن تك فقط على الجبهة. الحذف هو أيضا من السهل جدا. علينا أن نجد العناصر. التي تنطوي على بعض البحث. 

ولكن مرة واحدة كنت قد وجدت عنصر كنت تبحث عن، كل ما عليك القيام به هو تغيير مؤشر، ربما اثنين إذا كان لديك مرتبط list-- على نحو مضاعف قائمة مرتبطة، rather-- وبعد ذلك يمكنك فقط تحرير العقدة. لم يكن لديك لتحويل كل شيء حولها. كنت مجرد تغيير اثنين من المؤشرات، ولهذا سريع جدا. 

بحث سيء الرغم من ذلك، أليس كذلك؟ حتى يتسنى لنا العثور على عنصر في قائمة مرتبطة، سواء منفردة أو مزدوجة مرتبطة، علينا أن خطي بحث عنها. علينا أن نبدأ في بداية و نقل النهاية، أو البدء في هذه الخطوة نهاية إلى بداية. ليس لدينا وصول عشوائي بعد الآن. إذا كان الأمر كذلك نقوم به الكثير من البحث، وربما قائمة مرتبطة يست تماما على ما يرام بالنسبة لنا. 

كما أنهم حقا من الصعب فرز، أليس كذلك؟ الطريقة الوحيدة التي يمكن فرز حقا قائمة مرتبطة هو لفرز على النحو الذي بناء عليه. ولكن إذا قمت بفرز كما كنت بناء عليه، لم يعد كنت جعل الإدراج بسرعة بعد الآن. كنت لا مجرد تغير اتجاهها أشياء على الجبهة. لديك للعثور على المكان الصحيح لوضعها، ثم بك الإدراج يصبح مجرد عن السوء كما إدخالها في صفيف. حتى القوائم المرتبطة يست كبيرة جدا لفرز البيانات. 

انهم أيضا صغيرة جدا، بحجم الحكمة. قائمة مرتبطة مضاعف قليلا أكبر من القوائم المرتبطة منفردة، التي هي أكبر قليلا من المصفوفات، ولكنها ليست كمية كبيرة من مساحة مهدرة. حتى إذا كان الفضاء بأسعار أعلى من أسعارها، ولكن ليس قسط مكثفة حقا، هذا قد يكون الطريق الصحيح للذهاب. 

الجداول التجزئة. الإدراج في جدول تجزئة غير واضحة إلى حد ما. انها عملية من خطوتين. أولا نحن بحاجة لتشغيل البيانات من خلال وظيفة تجزئة للحصول على رمز التجزئة، وبعد ذلك إدراج العنصر في جدول تجزئة في ذلك المكان رمز التجزئة. 

حذف، على غرار قائمة مرتبطة، من السهل بمجرد العثور على العنصر. عليك أن تجد لأول مرة، ولكن بعد ذلك عندما قمت بحذفه، تحتاج فقط لتبادل اثنين من المؤشرات، إذا كنت تستخدم تسلسل منفصل. إذا كنت تستخدم التحقيق، أو إذا كنت لا باستخدام تسلسل على الإطلاق في جدول التجزئة الخاصة بك، الحذف هو في الواقع من السهل حقا. كل ما عليك القيام به هو تجزئة البيانات، ومن ثم انتقل إلى هذا الموقع. وعلى افتراض انك لا لديك أي اصطدام، عليك أن تكون قادرا على حذف بسرعة كبيرة. 

الآن، والبحث هو حيث الأشياء الحصول على أكثر من ذلك بقليل تعقيدا. انها في المتوسط ​​على نحو أفضل من القوائم المرتبطة. إذا كنت تستخدم تسلسل، لا يزال لديك قائمة مرتبطة، مما يعني أنك لا تزال لديها البحث يضر قائمة مرتبطة. ولكن لأنك تتناولين مرتبطة بك قائمة وتقسيمه أكثر من 100 أو 1000 أو ن العناصر في جدول التجزئة الخاصة بك، وكنت القوائم المرتبطة كلها واحدة نطة الحجم. انهم جميعا أصغر بكثير. لقد ن القوائم المرتبطة بدلا واحدة قائمة مرتبطة حجم ن. 

وحتى هذا العالم الحقيقي ثابت عامل، ونحن عموما لا نتحدث عن التعقيد في الوقت، لا يحدث فارقا حقيقيا ملموسا هنا. لذلك البحث لا يزال الخطية بحث إذا كنت تستخدم تسلسل، ولكن طول قائمة كنت تبحث عن طريق جدا، قصيرة جدا بالمقارنة. مرة أخرى، إذا الفرز الخاص بك هو الهدف هنا، تجزئة الجدول ربما لا يكون الطريق الصحيح للذهاب. مجرد استخدام صفيف إذا الفرز هو المهم حقا بالنسبة لك. 

ويمكن تشغيل سلسلة من الحجم. من الصعب القول ما إذا كان جدول تجزئة صغير أو كبير، لأنه حقا يتوقف على كيف كبيرة جدول التجزئة الخاص بك هو. إذا كنت لن يؤدي الا الى أن تخزين خمسة عناصر في جدول التجزئة الخاصة بك، وكان لديك جدول التجزئة مع 10،000 العناصر فيه، ربما كنت إضاعة الكثير من الفضاء. على النقيض من كونها يمكنك أيضا تحتوي على جداول التجزئة مدمجة للغاية، ولكن أصغر جدول التجزئة الخاص يحصل، ويعد كل من تلك القوائم المرتبطة يحصل على. وحتى لا يكون هناك حقا أي وسيلة لتحديد بالضبط حجم جدول التجزئة، ولكن من المحتمل أن يكون آمنا القول انها عموما سيكون أكبر من ربط قائمة تخزين نفس البيانات، ولكن أصغر من TRIE. 

ويحاول هي رابع من هذه الهياكل التي كنا نتحدث عنها. إدراج في TRIE معقد. هناك الكثير من الديناميكية تخصيص الذاكرة، خصوصا في البداية، كما كنت البدء في بناء. ولكن حان الوقت المستمر. انها العنصر البشري فقط هنا أن يجعل الأمر معقدا. وبعد لقاء مؤشر فارغة، malloc الفضاء، الذهاب إلى هناك، الفضاء ربما malloc من هناك مرة أخرى. هذا النوع من عامل التخويف من المؤشرات في تخصيص الذاكرة الديناميكية هو عقبة واضحة. ولكن بمجرد أن مسح عليه، الإدراج في الواقع يأتي بسيط جدا، وبالتأكيد هو وقت ثابت. 

حذف أمرا سهلا. كل ما عليك القيام به هو التنقل لأسفل زوجان من المؤشرات وتحرير العقدة، لذلك هذا امر جيد جدا. بحث هو أيضا سريع جدا. أنها تقوم فقط على طول البيانات الخاصة بك. إذا كان الأمر كذلك جميع البيانات الخاصة بك هو خمس سلاسل الأحرف، على سبيل المثال، كنت تخزين خمسة سلاسل الأحرف في TRIE الخاص بك، يستغرق سوى خمس خطوات ل تجد ما تبحث عنه. خمسة هو مجرد عامل ثابت، لذلك مرة أخرى، الإدراج أو الحذف، وبحث هنا كل وقت ثابت وفعال. 

شيء آخر هو أن TRIE الخاص بك هو في الواقع فرز النوع من قبل، أليس كذلك؟ بحكم كيف نحن عناصر إدخالها عن طريق الذهاب الرسالة حرف الرئيسية، أو أرقام برقم المفتاح، عادة، TRIE ينتهي به الأمر نوع من مرتبة كما كنت بناء عليه. فإنه لا يجعل حقا الشعور للتفكير في الفرز في نفس الطريقة التي نفكر بها مع المصفوفات، أو القوائم المرتبطة، أو الجداول التجزئة. ولكن في بعض المعنى، بك يتم فرز TRIE كما تذهب. 

الجانب السلبي، بطبيعة الحال، هو أن وTRIE يصبح بسرعة هائلة. من كل نقطة تقاطع، كنت قد have-- إذا يتكون المفتاح الخاص من الأرقام، لديك 10 آخرين الأماكن التي يمكن أن تذهب، التي يعني أن كل عقدة يحتوي على معلومات حول البيانات التي تريد تخزين في تلك العقدة، بالإضافة إلى 10 مؤشرات. التي، على IDE CS50، هو 80 بايت. لذلك فمن لا يقل عن 80 بايت كل عقدة التي تقوم بإنشائها، وهذا ليس حتى عد البيانات. وإذا العقد الخاصة بك الرسائل بدلا من الأرقام، الآن لديك 26 مؤشرات من كل مكان. و26 مرة 8 هو على الارجح 200 بايت، أو شيء من هذا القبيل. وكان لديك رأس المال وlowercase-- يمكنك رؤية أين أنا ذاهب مع هذا، أليس كذلك؟ يمكن أن العقد الخاص بك الحصول على حقا كبير، وبالتالي فإن TRIE نفسها، وعموما، يمكن لل الحصول كبيرة حقا، أيضا. حتى إذا كان الفضاء هو في أعلى مستوى علاوة على النظام الخاص بك، وTRIE قد لا تكون الطريقة الصحيحة ل الذهاب، على الرغم من الفوائد الأخرى ل حيز اللعب. أنا دوغ ويد. هذا هو CS50.