דאג LLOYD: אז בCS50, אנחנו כבר כיסינו הרבה מבני נתונים שונים, נכון? ראינו מערכים, וצמוד רשימות, ושולחנות חשיש, ומנסה, ערימות ותורים. אנחנו גם ללמוד קצת על עצים וערימות, אבל באמת כל אלה רק בסופו דבר להיות וריאציות על נושא. יש באמת אלה סוג של ארבעה רעיונות בסיסיים כל מה שאחר לא יכול להצטמצם ל. מערכים, רשימות מקושרות, שולחנות חשיש, ומנסה. וכמו שאמרתי, יש וריאציות על אותם, אבל זה די הרבה הולך לסכם כל מה שאנחנו הולכים לדבר על זה בכיתה במונחים של ג אבל איך עושים אלה כל המידה, נכון? דברנו על היתרונות וחסרונות של כל אחד בקטעי וידאו נפרדים עליהם, אבל יש הרבה מספרים מקבל נזרק מסביב. יש הרבה של כללי מחשבות שנזרקו מסביב. בואו ננסה ולגבש אותו למקום אחד בלבד. בואו לשקול את היתרונות מול החסרונות, ולשקול שמבנה הנתונים יכול להיות נתונים תקין מבנה למצב הספציפי שלך, כל סוג של נתונים שאתה אחסון. אתה לא בהכרח תמיד צריך להשתמש בהכנסה, מחיקת סופר מהירה, ובדיקה של איירי אם אתה באמת לא אכפת לי ההכנסה ומחיקה יותר מדי. אם אתה צריך רק אקראי במהירות גישה, אולי מערך הוא טוב יותר. אז בואו לזקק את זה. בואו נדבר על כל אחד מארבעת סוגים עיקריים של מבני נתונים שדברנו על, ו רק לראות מתי הם יכולים להיות טובים, וכאשר הם לא יכולים להיות כל כך טובים. אז בואו נתחיל עם מערכים. אז הכנסה, זה סוג של רע. 

כניסה בסוף המערך בסדר, אם אנחנו בונים מערך כמו שאנחנו הולכים. אבל אם אנחנו צריכים להכניס אלמנטים למרכז הרחבה, חושב לחזור להכנסה סוג, יש הרבה של הסטה כדי להתאים אלמנט שם. ולכן אם אנחנו הולכים להכניס בכל מקום, אבל בסוף המערך, זה כנראה לא כל כך גדול. 

כמו כן, מחיקה, אלא אם כן אנחנו מחיקה מסוף המערך, כנראה גם לא כל כך גדול אם אנחנו לא רוצים לעזוב את הפערים ריקים, אשר בדרך כלל אין לנו. אנחנו רוצים להסיר את אלמנט, ו אז סוג של לעשות את זה שוב הדוק. וכך מחיקת אלמנטים מ מערך, גם לא כל כך גדול. 

בדיקה, אם כי, היא נהדרת. יש לנו גישה אקראית, בדיקת זמן קבועה. אנחנו רק אומרים שבע, ואנחנו הולכים להעתקת מערך שבע. אנחנו אומרים 20, עם ללכת ל העתקת מערך 20. אנחנו לא צריכים לחזר על פני. זה די טוב. 

מערכים הם גם קלים יחסית כדי למיין. בכל פעם שדברנו על מיון אלגוריתם, כגון מיון בחירה, מיון הכנסה, מיון בועות, למזג סוג, אנחנו תמיד השתמשנו מערכים לעשות את זה, כי מערכים הם די קל סוג, ביחס למבני נתונים שראינו עד כה. 

הם גם קטנים יחסית. אין הרבה מקום נוסף. אתה פשוט להפריש בדיוק באותה המידה כמו שאתה צריך להחזיק את הנתונים שלך, וזה פחות או יותר אותו. אז הם די קטנים ויעיל בדרך זו. אבל חסרון אחר, אם כי, הוא שהם קבועים בגודל. אנחנו צריכים להכריז בדיוק איך גדול שאנחנו רוצים המערך שלנו להיות, ואנחנו מקבלים רק ירייה אחת בזה. אנחנו לא יכולים לגדול ולכווץ אותו. 

אם אנחנו צריכים לגדול או להתכווץ זה, אנחנו צריך להצהיר על מערך חדש לגמרי, להעתיק את כל האלמנטים של המערך ראשון במערך השני. ואם אנחנו טעינו בחישובים ש זמן, אנחנו צריכים לעשות את זה שוב. לא כל כך גדול. אז מערכים לא נותנים לנו את הגמישות יש מספרים משתנה של אלמנטים. 

עם רשימה מקושרת, ההכנסה היא די קלה. אנחנו רק טקטיקה על החזית. מחיקה היא גם די קלה. אנחנו צריכים למצוא את האלמנטים. שכוללים כמה חיפושים. 

אבל ברגע שמצאת את האלמנט שאתה מחפש, כל מה שאתה צריך לעשות הוא לשנות את מצביע, אולי שני אם יש לך קשור list-- כפליים רשימה מקושרת, rather-- ואז אתה יכול פשוט לשחרר את הצומת. אתה לא צריך לעבור כל מה שמסביב. אתה פשוט לשנות שני מצביעים, אז זה די מהר. 

למרות שבדיקה היא רעה, נכון? על מנת שתוכל למצוא אלמנט ברשימה מקושרת, אם יחידים או כפול צמוד, אנחנו צריכים לחפש אותו ליניארי. אנחנו צריכים להתחיל בתחילת ו להעביר את הסוף, או להתחיל במהלך הסוף להתחלה. אין לנו גישה אקראית יותר. אז אם אנחנו עושים הרבה חיפושים, אולי רשימה מקושרת היא לא כל כך טוב לנו. 

הם באמת גם קשה למיין, נכון? רק הדרך שתוכל באמת למיין את רשימה מקושרת הוא למיין את זה כמו שאתה לבנות אותו. אבל אם אתה למיין את זה כמו שאתה לבנות אותו, אתה כבר לא מה שהופך את ההוספות מהירות יותר. אתה לא רק tacking דברים על החזית. אתה צריך למצוא מקום נכון לשים את זה, ולאחר מכן ההכנסה שלך הופך כמעט גרוע כמו כהכנסה למערך. אז רשימות מקושרות אינן כל כך גדול למיון נתונים. 

הם גם די קטן, בגודל חכם. כפליים קשור רשימה מעט גדול יותר מרשימות מקושרות ביחידות, שהם מעט גדולים יותר ממערכים, אבל זה לא כמות השטח מבוזבז ענק. אז אם החלל הוא בפרמיה, אבל לא פרמיה באמת אינטנסיבית, זה עשוי להיות הדרך הנכונה ללכת. 

שולחנות חשיש. כניסה לטבלה חשיש הוא פשוט למדי. זה תהליך דו-שלבים. ראשית אנחנו צריכים להפעיל את הנתונים שלנו דרך פונקצית חשיש כדי לקבל קוד חשיש, ואז אנחנו מכניסים את האלמנט ל טבלת חשיש שבמיקום קוד חשיש. 

מחיקה, דומה לרשימה מקושרת, קל ברגע שאתה מוצא את האלמנט. אתה צריך למצוא את זה קודם, אבל אז כאשר אתה מוחק אותו, אתה רק צריך להחליף כמה עצות, אם אתה משתמש בשרשור נפרד. אם אתה משתמש בחיטוט, או אם אתה לא באמצעות שרשור בכל בטבלת החשיש שלך, המחיקה היא ממש ממש קלה. כל מה שאתה צריך לעשות הוא חשיש הנתונים, ולאחר מכן ללכת למיקום זה. ובהנחה שאתה לא יש כל התנגשויות, תוכל למחוק במהירות רבה. 

עכשיו, בדיקה היא שבו דברים לקבל קצת יותר מסובך. זה בממוצע טוב יותר מרשימות מקושרות. אם אתה משתמש בשרשור, עדיין יש לך רשימה מקושרת, מה שאומר שעדיין יש לך חיפוש רעת רשימה מקושרת. אבל בגלל שאתה לוקח צמוד שלך רשימה ופיצולו מעל 100 או 1,000 או n אלמנטים בטבלת החשיש שלך, אתה רשימות מקושרות כל אחד המי יודע כמה את הגודל. הם כולם באופן משמעותי קטנים יותר. n יש לך רשימות מקושרות במקום של רשימה מקושרת אחד בגודל n. 

וכך בעולם אמיתי זה קבוע גורם, שאנחנו בדרך כלל לא מדבר על מורכבות בזמן, זה עושה בעצם לעשות את הבדל כאן. אז בדיקה היא עדיין ליניארי לחפש אם אתה משתמש בשרשור, אבל האורך של הרשימה אתה מחפש דרך מאוד, מאוד קצר על ידי השוואה. שוב, אם מיון הוא שלך מטרה כאן, שולחן של החשיש כנראה לא הדרך הנכונה ללכת. פשוט להשתמש במערך אם מיון הוא באמת חשוב לך. 

והם יכולים להפעיל את סולם של גודל. קשה לומר אם שולחן חשיש קטן או גדול, כי זה באמת תלוי ב כמה גדול שלך הוא שולחן החשיש. אם אתה רק הולך להיות אחסון חמישה אלמנטים בטבלת החשיש שלך, ויש לך טבלת חשיש עם 10,000 אלמנטים בזה, אתה כנראה לבזבז הרבה מקום. השווה גם להיות שאתה יכול יש שולחנות חשיש קומפקטיים מאוד, אבל שולחן החשיש שלך הקטן יותר מקבל, כל אחד מרשימות המקושרות אלה כבר מקבל. וכך באמת אין דרך להגדיר בדיוק בגודל של שולחן חשיש, אבל זה כנראה בטוח לומר שזה בדרך כלל הולך להיות גדול יותר מצמוד רשימת האחסון אותם נתונים, קטן יותר, אך יותר מאיירי. 

ומנסה הם הרביעי מבנים אלה כי אנחנו כבר מדברים על. ההכנסה לאיירי היא מורכבת. יש הרבה דינמי הקצאת זיכרון, במיוחד בהתחלה, כמו שאתה מתחיל לבנות. אבל זה זמן קבוע. זה הגורם האנושי בלבד כאן זה עושה את זה מסובך. לאחר להיתקל מצביע null, malloc מרחב, ללכת לשם, אולי חלל malloc משם שוב. הסוג של גורם הפחדה של מצביעים בהקצאת זיכרון דינמי הוא המשוכה כדי לנקות. אבל ברגע שפינית אותו, הכנסה למעשה מגיע די פשוט, וזה בהחלט זמן קבוע. 

מחיקה קלה. כל מה שאתה צריך לעשות הוא לנווט את כמה עצות ובחינם הצומת, אז זה די טוב. בדיקה היא גם די מהר. הוא מבוסס רק על אורך הנתונים שלך. אז אם כל הנתונים שלך הוא חמש מחרוזות תווים, לדוגמא, אתה אחסון חמישה מחרוזות תווים באיירי, זה לוקח רק חמישה צעדים ל למצוא את מה שאתה מחפש. חמישה הוא רק גורם קבוע, כך שוב, הכנסה, מחיקה, ובדיקה כאן הם כל הזמן הקבוע, בצורה יעילה. 

דבר נוסף הוא שאיירי שלך היא בעצם סוג של כבר מסודרים, נכון? מכוח איך אנחנו אלמנטי הכנסה, על ידי הולך אות אחרת אות של מפתח, או ספרה בספרה של המפתח, בדרך כלל, את איירי בסופו להיות סוג של מסודרים כמו שאתה בונה אותו. זה לא ממש עושה תחושה לחשוב על מיון באותה הדרך בה אנו חושבים על זה עם מערכים, או רשימות מקושרות, או טבלאות חשיש. אבל במובן מסוים, איירי ממוינת כמו שאתה הולך. 

החסרון, כמובן, הוא ש איירי במהירות הופכת להיות ענק. מכל נקודת צומת, אתה עלול נו-- אם המפתח שלך מורכב מספרות, יש לך 10 אחרים מקומות שאתה יכול ללכת, ש משמעות הדבר היא כי כל צומת מכיל מידע על הנתונים שאתה רוצה לאחסן בצומת זה, בתוספת 10 מצביעים. אשר, על IDE CS50, הוא 80 בתים. אז זה לפחות 80 בתים ל כל צומת שאתה יוצר, וזה אפילו לא סופר את הנתונים. ואם בלוטות שלך אותיות במקום ספרות, עכשיו יש לך 26 מצביעים מכל מקום. ו -26 פעמים 8 היא כנראה 200 בתים, או משהו כזה. ויש לך הון וlowercase-- אתה יכול לראות לאן אני הולך עם זה, נכון? צמתים שלך יכולים לקבל באמת הגדולה וכל כך איירי, עצמו, הכולל, יכול להגיע ממש גדול, יותר מדי. אז אם יש מקום בבית גבוה פרמיה על המערכת שלך, איירי לא יכולה להיות הדרך הנכונה ללכת, למרות שהיתרונות האחרים שלה נכנס לשחק. אני דאג לויד. זה CS50.