KEVIN Schmid در: گاهی اوقات، زمانی که ساختمان برنامه، در صورت تمایل به استفاده از یک ساختمان داده شناخته شده به عنوان یک فرهنگ لغت. نقشه فرهنگ لغت کلید، که معمولا رشته ها، به ارزش ها، نوع داده int، کاراکتر، یک اشاره گر به برخی از شیء، هر آنچه که ما می خواهیم. درست مثل واژه نامه عادی کلماتی را که نقشه را از طریق تعاریف. 

واژهنامهها ما با ارائه توانایی ذخیره اطلاعات مرتبط با چیزی و آن نگاه کنید تا بعد. پس چگونه ما در واقع پیاده سازی یک فرهنگ لغت را، مثلا، کد C که ما می توانیم استفاده از در یکی از برنامه های ما؟ خوب، هستند بسیاری از راه های وجود دارد که ما می تواند یک فرهنگ لغت پیاده سازی. 

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

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

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

جسمی که نوع ساختار است گره دارای دو بخش است به نام داده ها و کودکان. ما بخشی از داده به عنوان یک نظر را ترک کرده ام به یک جزء جایگزین اعلامیه وقتی که یک ساختار است ثبت شده در یک برنامه C. بخش داده ها از یک گره ممکن است یک مقدار بولی نشان می دهد که آیا نه گره نشان دهنده تکمیل یک کلید واژه یا آن را ممکن است رشته ای تعریف از یک کلمه در فرهنگ لغت. 

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

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

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

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

ما در شاخص دوم نگاه پس از آن، شاخص یک، برای B. به طور کلی، اگر ما برخی از حروف الفبا که ما شخصیت C می تواند نقطه مربوطه تعیین در آرایه کودکان با استفاده از یک محاسبه مانند این. ما می توانستیم کودکان بزرگتر استفاده کرده اند آرایه اگر ما می خواستیم برای ارائه نگاه کردن از کلید های با طیف وسیع تری از شخصیت ها، مانند کل شخصیت ASCII تنظیم شده است. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

آن آسان است برای به دست آوردن این لیست به ترتیب حروف الفبا از عناصر آرایه کودکان ها بر اساس حروف الفبا مرتب می شوند. پس امیدوارم شما در نظر دادن تلاش می کند را امتحان کنید. I کوین Schmid در هستم، و این CS50 است. 

آه، این آغاز است از کاهش. من متاسفم. متأسفم. متأسفم. متأسفم. 

اعتصاب چهار. من هستم. متأسفم. متأسفم. متأسفم. با عرض پوزش برای ساخت شخصی که به ویرایش این دیوانه. 

متأسفم. متأسفم. متأسفم. متأسفم. 

SPEAKER 1: خوب انجام می شود. که واقعا به خوبی انجام شد.