שיעור 15: רשימות מקושרות

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

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

----------        ----------
- Data   -       >- Data   -    
----------     -  ----------   
- Pointer- - -    - Pointer-  
----------        ----------

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

לפי שעה אנחנו יודעים איך יראה מבנה הקשר:

struct node
{
  int x;
  node *next;
};

int main()
{
  node *root;  //This will be the unchanging first node
  root=new node; //Now root points to a node struct
  root->next=NULL; //The node root points to has its next pointer
				   //set equal to NULL
  root->x=5;   //By using the -> operator, you can modify the node
  return 0;	   //a struct (root in this case) points to.
} 

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

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

כך זה נראה:

struct node
{
  int x;
  node *next;
};

int main()
{
  node *root; //This won't change, or we would lose the list in memory
  node *conductor; //This will point to each node as it traverses
				   //the list
  root=new node; //Sets it to actually point to something
  root->next=NULL; //Otherwise it would not work well
  root->x=12;
  conductor=root; //The conductor points to the first node
  if(conductor!=NULL)
  {
    while(conductor->next!=NULL)
    {
      conductor=conductor->next;   
    }
  }
  conductor->next=new node; //Creates a node at the end of the list
  conductor=conductor->next; //Points to that node
  conductor->next=NULL; //Prevents it from going any further
  conductor->x=42;
}

זה הקוד הבסיסי למעבר על רשימה. פקודת ה if מבטיחה שיש משהו לפתוח בו (קשר ראשון). בדוגמא זה תמיד יהיה כך, אבל אם זה היה משתנה, זה עשוי לא להיות נכון. אם פקודת ה if היא אמת, אז זה בסדר לנסות ולגשת לקשר שאליו מצביע הכרטיסן. לולאת ה while תמשיך כל עוד יש מצביע נוסף ב next. הכרטיסן פשוט מתקדם. הוא משנה את מה שאליו הוא מצביע על ידי קבלת הכתובת של conductor->next.

לבסוף, בקוד שבסוף ניתן להשתמש כדי להוסיף קשר חדש בסוף. ברגע שלולאת ה while הסתימה, ה conductor יצביע לקשר האחרון במערך. (אתה זוכר שהכרטיסן של הרכבת ינוע עד שאין לאן להמשיך? הוא עובד באותו אופן בלולאת ה while). לכן, conductor->next נקבע ל null, כך שזה בסדר להקצות שטח זיכרון חדש שאליו הוא יצביע. לאחר מכן ה conductor עובר אלמנט אחד (כמו כרטיסן רכבת שעובר לקרון החדש שנוסף) ומוודא שהמצביע שלו נקבע ל NULL כך שלרשימה יש סוף. ה NULL מתפקד כמו נקודה, הוא אומר שאין יותר דבר מעבר. לבסוף, לקוד החדש יש את הערך של x שלו קבוע. (ניתן לקבוע אותו על ידי קלט של המשתמש. אני פשוט כתבתי '42=' בתור דוגמא.)

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

לדוגמא:

conductor=root;
if(conductor!=NULL) //Makes sure there is a place to start
{
  while(conductor->next!=NULL)
  {
    cout<<conductor->x;
    conductor=conductor->next;
  }
  cout<<conductor->x;
}

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

לדף הראשון

<< לדף הקודם

לדף הבא >>