רשימות מקושרות

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

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

struct phone{
 
 char first_name[15],last_name[15];
   long number;
   phone *next;
   static int n;
   phone(const char *last,const char *first,long num);
   ~phone();
   void print();
   };
 }

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

#include <iostream.h>
#include "phone.h"
#include <string.h>
#include <process.h>
#include <iomanip.h>

int phone::n;

 phone::phone(const char *last,const char *first,long num)
   {
    if ( strlen(last)<15 )
	 strcpy(last_name,last);
    else
       {
	cout<<"Error! the last name is too long\n";
	exit(1);
	}
     if ( strlen(first)<15 )
	 strcpy(first_name,first);
    else
       {
	cout<<"Error! the first name is too long\n";
	exit(1);
	}          
    number=num;
  next=NULL;
  n++;
  }
phone::~phone()
  {
    cout<<"destructing phone number "<<n<<'\n';
    print();
   n- -;
  }

void phone::print()
   {
    cout<<setw(15)<<last_name<<setw(15)<<first_name
    <<setw(15)<<number<<'\n';
   }

הפונקציה הבונה מאתחלת את המשתנים תוך כדי בדיקה שאין חריגה מן הגודל המקסמלי של שם ,שהמחלקה יכולה להכיל .כמו כן היא מאתחלת את המכוון next לnull ומקדמת את n מכיוון שכרגע ישנו אובייקט נוסף ברשימה .הפונקציה ( )print מדפיסה את נתוני האובייקט, והפונקציה ההורסת רושמת הודעה על כך שהיא מופעלת ומדפיסה את הנתונים ,לפני שהאובייקט נמחק מהזיכרון ,פונקציה זו גם מקטינה את n ב1 מכיוון שיש אובייקט אחד פחות .שים לב !הקובץ המכיל את הפונקציות חייב לכלול בתוכו ע"י פקודת include# את קובץ הגדרת המחלקה .נבדוק את הפונקציות שהגדרנו .את בדיקת הנכונות הפונקציות נעשה ע"י יצירת קובץ המכיל את ( )main ,ומשתמש בפונקציה של המחלקה.

#include <iostream.h>
#include "phone.h"
main()
 {
    phone ph1("Rabin","Itzhak",7512398),ph2("Bush","George",6390651),*ph3;
    ph3=new phone("Twain","Mark",7253045);
    ph1.print();
    ph2.print();
    ph3->print();
 return 0;
 }

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

רשימות מקושרות list ( )

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

class list{
 phone *head;
public:
list(const char *last,const char *first,long num);
~list();
void insert(phone *p);
phone *find_place(const char *last);
phone *find(const char *last);
phone *find_last_place();
del(const char *last);
void print();
};

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

#include <iostream.h>
#include <string.h>				  
#include "phone.h"
#include "List1.h"

List1::List1(const char *last,const char *first,long num)
   {
    head=new phone(last,first,num);
    }

phone *List1::find_last_place()
   {
      phone *tmp,*prev;
    for(tmp=head,prev=head;tmp->next;prev=tmp,tmp=tmp->next);
	 return(prev);
   }

phone *List1::find(const char *last)
  {
    phone *tmp,*prev;
    for(tmp=head,prev=head;tmp != NULL;prev=tmp,tmp=tmp->next)
      if (strcmp(last,tmp->last_name)==0)
	 return(prev);
      return(prev);
    }

phone *List1::find_place(const char *last)
  {
    phone *tmp,*prev;
    for(tmp=head,prev=head;tmp != NULL;prev=tmp,tmp=tmp->next)
	{
      if (strcmp(tmp->last_name,last)>=0)
	 return(prev);
	}
      return(prev);
    }
void List1::insert(phone *p)
  {
    phone *tmp;
    if ( strcmp(p->last_name,head->last_name)<0 )
      {
      tmp=head;
      head=p;
      p->next=tmp;
      return;
      }
    tmp=find_place(p->last_name);
    p->next=tmp->next;
    tmp->next=p;
   }

void List1::print()
  {
    phone *tmp;
    for(tmp=head;tmp!=NULL;tmp=tmp->next)
       tmp->print();
    cout<<"Total number of Objects are "<n<<'\n';
  }

List1::del(const char *last)
  {
    phone *place,*tmp;
    if (!strcmp(last,head->last_name))
      {
      tmp=head;
      head=head->next;
      delete tmp;
      return(1);
      }

    place=find(last);
    tmp=place->next;
    if (tmp == NULL || strcmp(tmp->last_name,last)!=0 )
	 return(0);
    else
       {
	place->next=place->next->next;
	delete tmp;
	return(1);
       }
    }

 List1::~List1()
   {
    phone *tmp,*tmpn;
    for(tmp=head,tmpn=head->next;tmpn!=NULL;
            tmp=tmpn,tmpn=tmpn->next)
       delete tmp;
    delete tmp;
    }