בעברית' פרק 1 דף 4 C++ ללמוד'

דף הבית >> זיכרון דינמי>> הגדרת זיכרון עבור אוביקטים>>רשימות מקושרות>>תיאור הפונקציות

( )list כפונקציה בונה המקבלת עבור אובייקט מסוג phone ,שם פרטי ,שם משפחה ומספר טלפון ,ומבצעת הקצאה דינמית , כך ש head יצביע לעבר האובייקט. שים לב !עפ"י צורת האתחול , כאשר מגדירים רשימה מגדירים גם את האיבר הראשון שלה. ( )find_place פונקציה זו מקבלת שם משפחה ומוצאת את המקום אשר אחריו יש להכניס את האובייקט החדש. הבדיקה היא עפ"י הא"ב.הפונקציה insert משתמשת בפונקציה זו אם נרצה להכניס את האובייקט המכיל את הטלפון של danny robas ,מקומו יהיה אחרי george Michael ולפני mark twain ,ולכן הערך המוחזר ע"י הפונקציה ( )find_place יהיה מחוון לאובייקט המכיל את george Michael .

דרך פעולת הפונקציות

הפונקציה מגדירה שני מחוונים לאובייקט מסוג phone ,tamp ו prep שני מחוונים מאוחלים ל head ,כך שהם מצביעים לאיבר הראשון .tamp מקודם לאיבר הבא ברשימה, בכל פעם שהלולאה מבוצעת ע"י הפקודה tamp=tamp->next .prep נמצא באיבר אחד לפני tamp ,כיוון שהוא מקבל את ערכו של tamp לפני ש tamp מקודם.הלולאה בודקת בכל איטר ציה אם שם משפחה אשר בtamp גדול משם המשפחה אשר אותו קיבלה הפונקציה כפרמטר . כאשר הוא גדול יותר , סימן ,שעברנו את המקום באחד, ולכן צריך להחזיר את המחוון לאיבר הקודם .הדבר מבוצע ע"י החזרת המחוון prev. נבדוק את מקרה הקצה .אם איבר שמעונינים להכניס לרשימה גדול משאר האיברים , אזי הלולאה תסתיים ע"י כך ש tmp יגיע לסוף ,ויהיה שווה לnull .במקרה כזה prev יצביע על האיבר האחרון ,וזהו באמת המקום שלאחריו יש להכניס את האיבר החדש .אם האיבר החדש יהיה אף קטן מן האיבר הראשון . יוחזר מצביע על האיבר הראשון .מכוון שכך מטופל מקרה זה באופן מיוחד בפונקציה ( )insert .

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

תיאור ההכנסה .

הפקודה p->next=tmp->next משרשרת את האיבר החדש המוצבע ע"י P לפני האיבר אשר נמצא אחרי האיבר המוצבע ע"י tmp לאחר מכן ,צריך ש tmp->next יצביע על האיבר החדש , ודבר זה אכן מבוצע ע"י הפקודה tmp->next=p .

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

if (strcmp (p ->last_name,head->last_name)<0)
 {
 tmp=head;
 head=p;
 p->next=tmp;
 return ( );
 }

( )find הפונקציה מקבלת כפרמטר שם משפחה ומחזירה מחוון לאיבר הנמצא לפני האובייקט הנושא שם משפחה זה .

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

if (!strcmp(last, head->last_name))
 {
 tmp=head;
 head=head->next;
 delete tmp;
 return (1) ;
 }

( )print פונקציה זו מדפיסה את כל הרשימה .הביצוע הוא ע"י לולאת for ומחוון ל phone בשם tmp . המחוון tmp מאותחל לראש הרשימה ומקודם ע"י הפקודה tmp =tmp->next .תנאי העצירה הוא tmp!=null תנאי זה אומר שהגענו לסוף הרשימה.

( )list~ פונקציה הורסת, המשמשת למחיקת איברים מן הזיכרון .מחיקת האובייקט list עצמו תמחק רק את האובייקט list המכיל את מחוון לphone ולא את איברי הרשימה המקושרת .

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


#include <iostream.h>
#include "phone.h"
#include "List1.h"
main()
{
	char last[15],first[15];
    long num;
    List1 *l1=new List1("Lennon","John",456641);
    phone *ph1=new phone("Haim","Moshe",345765);
    phone *ph2=new phone("Rabin","Itzhak",467323),*phone_ptr;
    l1->insert(ph1);
    l1->insert(ph2);
    l1->print();
    l1->del("Haim");
    cout<<"after deleting\n";
    l1->print();
     cout<<"input last name first name and phone number\n";
    do{
     cin>>last>>first>>num;
	phone_ptr=new phone(last,first,num);
	l1->insert(phone_ptr);
     }
   while(num);

    l1->print();
  delete l1;
  return 0;
  }

הפלט:

Haim moshe 345765
Lennon john 456641
Rabin itzhak 467323

Total number of objects are 3
Destructing phone number 3

Haim moshe 345765
After deleting
Lennon john 456641
Rabin itzhak 467323

Total number of objects are 2
Input last name first name and phone number

Bush george 384774
Lennon john 456641
Lennon john 345589
Michael george 345778
Rabin itzhak 467323
Robas danny 0
Twain mark 347876

Total number of objects are 7
Destructing phone number 7

Bush george 384774
Destructing phone number 7
Lennon john 456641
Destructing phone number 6
Lennon john 345589
Destructing phone number 5
Michael george 345778
Destructing phone number 4
Rabin itzhak 467323
Destructing phone number 3
Robas danny 0
Destructing phone number 2
Twain mark 347876
Destructing phone number 1

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


ll->insert(ph1);
ll->insert(ph2);

לאחר מכן מודפסת הרשימה ע"י הפקודה ll->print( ) .nהפלט בשלב זה:


Haim       moshe   345765
Lennon    john      456641
Rabin       itzhak    467323    


Total number of objects are 3

לאחר הדפסת הרשימה נמחק האיבר בעל שם המשפחה "haim",ושוב מודפסת הרשימה .

Destructing phone number   3


Haim       moshe   345765
After deleting
Lennon    john      456641
Rabin       itzhak    467323    


Total number of objects are 2

ההודעה על מחיקת האובייקט נתקבלה ע"י הפונקציה ההורסת של phone. לאחר מחיקת האובייקט ישנה לולאת do_while אשר מקבלת נתונים מלוח המקשים ומכניסה אותם לרשימה .הלולאה מסתיימת כאשר מכניסים מספר טלפון 0 .

Bush        george    384774
Lennon    john       345589
Michael   george    345778
Twain      mark       347876
Robas      danny          0

בסוף הכנסת הנתונים שוב מודפסת הרשימה .

Bush        george    384774
Lennon    john       456641
Lennon    john       345589
Michael   george    345778
Rabin       itzhak     467323    
Robas      danny          0
Twain      mark       347876

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

לסיכום:

אפשר להכניס כמות בלתי מוגבלת של נתונים

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

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

הרשימה מסודרת באופן אלפביתי.