[השמעת מוסיקה] 

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

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

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

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

אבל אנחנו מקבלים רק ירייה אחת בזה, אנחנו לא מקבל אז לומר אה, בעצם אני צורך 101, או שאני צריך x בתוספת 20. מאוחר מדי, כבר הכריז מערך, ואם אנחנו רוצים להגיע 101 או x בתוספת 20, אנחנו צריכים להכריז מערך שונה לחלוטין, להעתיק את כל האלמנטים של המערך מעל, ולאחר מכן יש לנו מספיק. ומה אם אנחנו טועים שוב, מה אם אנחנו באמת צריכים 102, או בתוספת 40 x, אנחנו חייבים לעשות את זה שוב. אז הם מאוד לא גמישים לשינוי גודל הנתונים שלנו, אבל אם אנו משלבים יחד כמה של היסודות שיש לנו כבר למד על מצביעים ומבנים, בפרט שימוש בזיכרון דינמי הקצאה עם malloc, אנחנו יכול לשים את החתיכות הללו יחד כדי ליצור נתונים חדשים structure-- ביחידים קשורים רשימה שאולי say-- המאפשר לנו לגדול ו לכווץ אוסף של ערכים ולא יהיה לנו כל שטח מבוזבז. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

אז הנה הרשימה שלנו, זה מורכב מ ארבעה יסודות, צומת המכילות 15, המצביע על צומת המכיל 9, ש מצביע על צומת המכילה 13, המצביע על צומת המכילה 10, שבו יש null מצביע כמצביע הבא שלה אז זה סוף הרשימה. אז אנחנו רוצים להכניס צומת חדשה עם הערך 12 בתחילת זה רשימה, מה עושים? ובכן, קודם אנחנו malloc מקום ל צומת, ואז אנחנו שמים 12 שם. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

אני דאג לויד, זה CS50.