داگ لوید: بنابراین در CS50، ما تحت پوشش ام بسیاری از ساختمان های داده مختلف، درست؟ ما آرایه دیده ام، و در ارتباط لیست ها، و جداول هش، و تلاش می کند، پشته و صف. ما همچنین یک کمی یاد بگیرند در مورد درختان و انبوه، اما واقعا این همه فقط پایان تا که تغییرات در یک موضوع. واقعا وجود دارد این نوع از چهار ایده های اساسی که هر چیز دیگری می تواند به جوش پایین. آرایه ها، لیست های پیوندی، جداول هش، و تلاش می کند. و مثل من گفت، وجود دارد تغییرات بر روی آنها، اما این است که بسیار بسیار رفتن به طور خلاصه همه چیز ما قصد داریم به بحث درباره در این کلاس در شرایط زبان C اما چگونه این همه را اندازه گیری تا، درست است؟ ما در مورد جوانب مثبت و منفی صحبت کردیم هر فیلم جداگانه در بر روی آنها، اما بسیاری از اعداد وجود دارد گشتن پرتاب می شود. در بسیاری از کلی وجود دارد افکار گشتن پرتاب می شود. بیایید امتحان کنید و تحکیم آن را به یک مکان. بیایید وزن جوانب مثبت در برابر منفی، و در نظر گرفتن که ساختار داده ممکن است داده های سمت راست ساختار برای وضعیت خاص خود، هر نوع از داده های شما در حال ذخیره سازی. شما لزوما همیشه نیاز به استفاده از فوق العاده سریع درج، حذف، و مراجعه از یک درخت پیشوندی اگر شما واقعا در مورد قرار دادن و حذف اهمیتی نمی خیلی زیاد. اگر شما نیاز به فقط به سرعت به صورت تصادفی دسترسی، شاید یک آرایه بهتر است. بنابراین اجازه دهید که تقطیر. اجازه دهید در مورد هر یک از چهار صحبت انواع عمده ای از ساختمان داده که ما در مورد صحبت کردیم، و فقط زمانی که آنها ممکن است خوب، و زمانی که آنها ممکن است خیلی خوب است. بنابراین با آرایه شروع کنیم. بنابراین درج، که این نوع از بد است. 

درج در پایان یک آرایه خوب است، اگر ما در حال ساخت یک آرایه به عنوان ما به. اما اگر ما نیاز به وارد کردن عناصر را به وسط، فکر می کنم به درج مرتب سازی بر اساس، بسیاری وجود دارد از تغییر به تناسب یک عنصر در آن وجود دارد. و به این ترتیب اگر ما قصد داریم به قرار دادن در هر نقطه اما در پایان یک آرایه، که احتمالا آنقدر بزرگ نیست. 

به طور مشابه، حذف، مگر اینکه ما حذف از پایان یک آرایه، است که احتمالا نه چندان بزرگ اگر ما نمی خواهیم به ترک شکاف خالی، که معمولا ما نمی کنند. ما می خواهیم به حذف یک عنصر، و پس از آن از آن را دوباره گرم و نرم. و به این ترتیب حذف عناصر یک آرایه، نیز نه چندان بزرگ است. 

گرین کارت آمریکا، هر چند، بزرگ است. در حال حاضر دسترسی تصادفی، گرین کارت آمریکا زمان ثابت. ما فقط می گویند هفت، و ما به به آرایه جابجایی هفت. ما می گویند 20، با رفتن به آرایه جابجایی 20. ما لازم نیست به تکرار در سراسر. این خیلی خوب است. 

آرایه نیز نسبتا آسان برای مرتب کردن هستند. هر بار که ما در مورد یک مرتب سازی صحبت الگوریتم، مانند مرتب سازی انتخابی، مرتب سازی بر درج، مرتب سازی حبابی، ادغام مرتب سازی بر اساس، ما همیشه آرایه استفاده به انجام آن، چون آرایه ها بسیار آسان برای مرتب سازی بر اساس، نسبت به ساختارهای داده ما تا کنون دیده ام. 

آنها نیز نسبتا کوچک است. در بسیاری از فضای اضافی وجود ندارد. شما فقط خود را کنار بگذارند دقیقا به همان اندازه عنوان شما نیاز به نگه داده های خود، و تقریبا آن. به طوری که آنها بسیار کوچک و کارآمد در آن راه. اما زیان دیگر، هر چند، این است که آنها در اندازه ثابت. ما باید به اعلام دقیقا چگونه بزرگ ما می خواهیم ما را به عنوان آرایه، و ما فقط یک شات در آن را دریافت. ما نمی توانیم رشد و کوچک آن است. 

اگر ما نیاز به رشد و یا کوچک آن، ما نیاز به آرایه کاملا جدید، کپی از تمام عناصر از اولین آرایه به آرایه دوم. و اگر ما اشتباه محاسبه است که زمان، ما نیاز به آن را دوباره. نه چندان بزرگ. بنابراین آرایه به ما انعطاف پذیری را نمی دهد به شماره متغیر از عناصر. 

با یک لیست پیوندی، درج بسیار آسان است. ما فقط بر روی جلو رویه. حذف نیز بسیار آسان است. ما باید برای پیدا کردن عناصر. که شامل برخی از جستجو. 

اما هنگامی که شما این عنصر را پیدا کرده ام شما دنبال آن هستید، همه شما باید انجام دهید تغییر یک اشاره گر، احتمالا دو اگر شما مرتبط list-- مضاعف لیست پیوندی، rather-- و سپس شما فقط می توانید گره. شما لازم نیست که به تغییر همه چیز در اطراف. شما فقط تغییر دو اشاره گر، به طوری که خیلی سریع است. 

گرین کارت آمریکا بد است هر چند، درست است؟ به منظور برای ما برای پیدا کردن یک عنصر در یک لیست پیوندی، آیا به تنهایی و یا مضاعف مرتبط، ما باید به خطی آن را جستجو کنید. ما باید برای شروع در ابتدا و حرکت پایان، و یا شروع در پایان حرکت به ابتدا. ما با دسترسی تصادفی دیگر ندارد. بنابراین اگر ما در حال انجام یک بسیاری از جستجو، شاید یک لیست پیوندی است کاملا برای ما خوب. 

آنها همچنین واقعا مشکل مرتب سازی بر اساس، درست است؟ تنها راهی که شما می توانید واقعا مرتب سازی بر اساس یک لیست پیوندی است برای مرتب کردن آن را به عنوان شما آن را ساخت. اما اگر شما آن را مرتب به شما به عنوان ساخت آن شما دیگر ساخت درج سریع نیست. شما نه تنها ضمیمه چیز را بر روی جلو. شما باید برای پیدا کردن نقطه سمت راست آن را قرار داده، و پس از آن خود را درج می شود فقط در مورد به عنوان بد به عنوان قرار دادن به یک آرایه. بنابراین لیست های پیوندی نیست آنقدر بزرگ برای مرتب سازی داده ها. 

آنها همچنین بسیار کوچک، اندازه عاقلانه است. لیست پیوندی مضاعف کمی بزرگتر از لیست تنهایی مرتبط، که کمی بزرگتر از آرایه، اما آن را نمی مقدار زیادی از فضای هدر رفته. بنابراین اگر فضا است در حق بیمه، اما یک حق بیمه واقعا شدید، این ممکن است راه حق. 

جداول هش. درج در یک جدول هش نسبتا ساده است. این یک فرآیند دو مرحله ای است. در ابتدا ما نیاز به اجرای داده ما را از طریق یک تابع هش برای دریافت کد هش، و سپس ما این عنصر به قرار دادن جدول هش در آن محل کد هش. 

حذف، شبیه به لیست پیوندی، آسان است هنگامی که شما پیدا کردن عنصر. شما باید برای پیدا کردن آن برای اولین بار، اما پس از آن زمانی که شما آن را حذف کنید، شما فقط نیاز به تبادل یک زن و شوهر از اشاره گر، اگر شما با استفاده زنجیری جداگانه. اگر شما با استفاده پروبینگ، و یا اگر شما نیست با استفاده از زنجیری در همه در جدول هش خود را، حذف است که در واقع بسیار آسان است. همه شما باید انجام دهید این است که مقدار هش داده، و سپس به آن مکان بروید. و با فرض شما نمی هر گونه برخورد، شما قادر خواهید بود به سرعت حذف کنید. 

در حال حاضر، مراجعه که در آن همه چیز است کمی پیچیده تر است. این به طور متوسط ​​بهتر است از لیست های پیوندی. اگر شما با استفاده زنجیری، شما هنوز هم یک لیست پیوندی، که بدان معنی است شما هنوز هم جستجو آسیب بزند یک لیست پیوندی. اما از آنجا که شما در حال گرفتن خود را در ارتباط لیست و تقسیم آن بیش از 100 یا 1،000 و یا n عنصر در جدول هش خود را، شما لیست های پیوندی همه یک n ام به اندازه. همه آنها قابل ملاحظه ای کوچکتر است. شما به جای N لیست مرتبط یک لیست پیوندی با اندازه n. 

و این در دنیای واقعی ثابت عامل، که به طور کلی ما در مورد پیچیدگی زمانی در صحبت نمی کند، در واقع تفاوت را در اینجا. بنابراین گرین کارت آمریکا است که هنوز هم خطی جستجو اگر شما با استفاده زنجیری، اما طول از لیست شما در حال جستجو از طریق بسیار، بسیار در مقایسه کوتاه است. باز هم، اگر مرتب سازی خود را است هدف در اینجا، هش جدول احتمالا راه حق. فقط یک آرایه استفاده کنید اگر مرتب سازی که واقعا برای شما مهم است. 

و آنها می توانند زمینه هایی از اندازه را اجرا کنید. این سخت است برای گفتن که آیا یک جدول هش کوچک یا بزرگ است، چون واقعا بستگی دارد چقدر بزرگ جدول هش شما است. اگر شما تنها به ذخیره سازی شود که پنج عنصر در جدول هش خود را، و شما باید یک جدول هش با 10،000 عناصر در آن، شما احتمالا هدر رفتن مقدار زیادی از فضا. مقابل شما همچنین می توانید بودن جداول هش بسیار جمع و جور، اما کوچکتر جدول هش شما می شود، دیگر هر یک از این لیست های پیوندی می شود. و به این ترتیب واقعا هیچ راه برای تعریف وجود دارد دقیقا به اندازه یک جدول هش، اما احتمالا امن به طور کلی رفتن به بزرگتر از یک مرتبط لیست ذخیره سازی داده های مشابه، اما کوچکتر از یک درخت پیشوندی. 

و تلاش می کند که چهارمین هستند از این سازه ها که ما شده ایم صحبت کردن در مورد. قرار دادن به یک درخت پیچیده است. در بسیاری از پویا وجود دارد تخصیص حافظه، به خصوص در آغاز، عنوان شما شروع به ساخت. اما زمان ثابت آن است. این تنها عنصر انسانی است در اینجا است که باعث می شود آن روی حیله و تزویر. نیاز به برخورد اشاره گر تهی، از malloc فضا، رفتن وجود دارد، فضای احتمالا از malloc از آنجا دوباره. مرتب کردن بر اساس عامل ارعاب اشاره گرها در تخصیص حافظه پویا مانع برای روشن است. اما هنگامی که شما آن را پاک کرده اید، درج در واقع می آید کاملا ساده است، و قطعا آن زمان ثابت است. 

حذف آسان است. همه شما باید انجام دهید این است که حرکت یک زن و شوهر از اشاره گرها و رایگان گره، به طوری که خیلی خوب است. گرین کارت آمریکا نیز بسیار سریع می باشد. آن را تنها در بر طول داده خود را. بنابراین اگر تمام اطلاعات خود را است پنج رشته های کاراکتری، برای مثال، شما در حال ذخیره سازی پنج رشته های کاراکتری در درخت خود را، تنها پنج گام برای رسیدن به طول می کشد پیدا کردن آنچه شما دنبال آن هستید. پنج فقط یک ضریب ثابت است، بنابراین دوباره، درج، حذف، و مراجعه به در اینجا همه زمان ثابت، به طور موثر. 

یکی دیگر از چیزی است که درخت خود را است در واقع نوع طبقه بندی شده اند در حال حاضر، درست است؟ به موجب چگونه ما عناصر قرار دادن، با رفتن حروف از کلیدی، و یا اعداد رقمی از کلید، به طور معمول، درخت خود را پایان می رسد تا نوع طبقه بندی شده اند که شما آن را ساخت. آن را واقعا نمی سازد حس به فکر می کنم در مورد مرتب سازی در همان راه ما در مورد فکر می کنم آن را با آرایه ها، و یا لیست های پیوندی، و یا جداول هش. اما در بعضی جهات، خود را درخت طبقه بندی شده اند که شما بروید. 

در حرکت نزولی، البته، این است که یک درخت پیشوندی به سرعت در حال بزرگ می شود. از هر نقطه اتصال، شما ممکن است have-- اگر کلید خود را متشکل از رقم، شما باید 10 دیگر مکان شما می توانید بروید که بدان معنی است که هر گره حاوی اطلاعات در مورد داده های شما می خواهید برای ذخیره که در آن گره، به علاوه 10 اشاره گر. که، در CS50 IDE، 80 بایت است. پس از آن حداقل 80 بایت برای هر گره که شما ایجاد می کنید، و حتی شمارش داده نمی شود. و اگر گره خود را حروف به جای رقم، در حال حاضر شما باید 26 اشاره گر از هر محل. و 26 بار 8 است که احتمالا 200 بایت، یا چیزی شبیه به آن. و شما باید سرمایه شما می توانید lowercase-- و ببینید که در آن من قصد دارم با این، درست است؟ گره خود را می توانید واقعا بزرگ، و این درخت به به خودی خود، به طور کلی، می توانید واقعا بزرگی است. بنابراین اگر فضا به بالا حق بیمه بر روی سیستم شما، یک درخت پیشوندی ممکن است راه درست را به نیست ، حتی اگر مزایای دیگر آن به بازی آمد. من داگ لوید هستم. این CS50 است.