[Powered by Google Translate] בתכנות, לעתים קרובות אנו צריכים לייצג רשימות הערכים, כגון שמות של תלמידים בסעיף או ציוניהם בשאלון האחרון. 

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

כאשר אנו מכריזים עליהם, אנחנו נדרשים לומר עד לפני כמה גדול הם, כלומר, כמה אלמנטים שהם יכולים לאחסן וכמה גדול אלמנטים אלה, הנקבע לפי סוגם. לדוגמה, int arr (10) יכול לאחסן 10 פריטים שהם בגודל של int. 

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

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

הנה קצת קוד C לרשימה מקושרת מאוד פשוטה של ​​מספרים שלמים. אתה יכול לראות שיש לנו תייצג כל צומת ברשימה כstruct המכיל 2 דברים, שלם לאחסון בשם "val" וקישור לצומת הבאה ברשימה שאנו מייצגים כמצביע נקרא 'הבא'. בדרך זו, אנו יכולים לעקוב אחר כל הרשימה רק עם מצביע בודד לצומת 1, ואז אנחנו יכולים לבצע את המצביעים הבאים לצומת 2, לצומת 3, לצומת 4, וכן הלאה, עד שנגיע לסוף הרשימה. 

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

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

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

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

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

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

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

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

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

לכן, אם סורק → הבא הוא ריק, זוכר שתחביר החץ הוא קיצור לביטול הפניה מצביע ל struct, ולאחר מכן כניסה השדה הבא שלה שווה הערך למסורבל: (* סורק). הבא. ברגע שמצאנו את הצומת האחרונה, אנחנו רוצים להדפיס הסורק → val, הערך בצומת הנוכחית אנחנו יודעים שהוא אחד האחרון. אחרת, אם אנחנו עדיין לא בצומת האחרונה ברשימה, יש לנו כדי לעבור את הצומת הבאה ברשימה ולבדוק אם זה אחרון. כדי לעשות זאת, אנחנו פשוט להגדיר מצביע הסורק שלנו כדי להצביע על הערך הבא של הצומת הנוכחית, כלומר, את הצומת הבאה ברשימה. הדבר נעשה על ידי הגדרה סורק = סורק → הבא. אז לחזור על תהליך זה, עם לולאה לדוגמה, עד שאנחנו מוצאים את הצומת האחרונה. כך, למשל, אם הסורק הצביע על הראש, אנו קובעים סורק להצביע על סורק → הבא, שהוא זהה לשדה הבא של הצומת 1. אז, עכשיו הסורק שלנו מצביע לצומת 2, ושוב, אנחנו חוזרים על זה עם לולאה, עד שמצאנו את הצומת האחרונה, כלומר, שם המצביע הבא של הצומת מצביע על null. ויש לנו את זה, שמצאנו את הצומת האחרונה ברשימה, ולהדפיס את הערך שלו, אנחנו פשוט משתמשים בסורק → val. 

חוצה הוא לא כל כך רע, אבל מה לגבי הכנסה? אניח שאנו רוצים להכניס מספר שלם לתוך עמדת 4 ברשימה של מספרים שלמות. כלומר בין צומת 3 ו 4 הנוכחיים. שוב, אנחנו צריכים לעבור את הרשימה רק כדי להגיע לאלמנט 3, זה שאנחנו אחרי ההחדרה. לכן, אנו יוצרים מצביע סורק שוב לעבור את הרשימה, לבדוק אם מצביע הראש שלנו הוא ריק, ואם זה לא, יצביע מצביע הסורק שלנו בצומת בראש. אז, אנחנו באלמנט 1. אנחנו צריכים ללכת קדימה עוד 2 אלמנטים לפני שנוכל להוסיף, כך אנו יכולים להשתמש עבור לולאה אני int = 1; i <3: אני + + ובכל איטרציה של הלולאה, לקדם מצביע הסורק שלנו קדימה על ידי צומת 1 על ידי בדיקה אם השדה הבא של הצומת הנוכחית הוא ריק, ואם זה לא, להעביר את מצביע הסורק שלנו לצומת הבאה על ידי הגדרתה שווה למצביע הבא של הצומת הנוכחית. לכן, מאז הלולאה עבורנו אומרת לעשות את זה פעמים, אנחנו כבר הגענו לצומת 3, וברגע שמצביע הסורק שלנו הגיע לצומת לאחר בו אנו רוצים להכניס המספר השלם החדש שלנו, איך אנחנו בעצם ההחדרה? 

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

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

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

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

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

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

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

השם שלי הוא ג'קסון Steinkamp, ​​זה CS50.