רשימות מקושרות Linked List
- הרשימה המקושרת היא מבנה (struct) לשמירת הרבה נתונים מאותו הסוג.- איברי הרשימה לא שמורים ברצף בזיכרון.
- כל איבר מכיל 2 דברים:
1. שדה/שדות מידע
2. שדה קישור (מצביע) לכתובת של האיבר הבא
סוגי רשימות:
רשימה חד סטרית
רשימה דו סטרית
רשימה מעגלית
התחלה [head] > [ מידע |next] > [ מידע |next] > [ מידע |next] > [ מידע |NULL] סוף
head הוא מצביע לתחילת הרשימה.
הרשימה מסתיימת באיבר בו שדה המצביע הוא NULL.
למרות שמערך הוא יותר מהיר עבור המחשב ותופס פחות מקום בזיכרון,
היתרון של רשימה מקושרת הוא הקלות בעבודה דינאמית.
לדוגמה על מנת למחוק איבר במערך נצטרך לסרוק אותו ולהעתיק את כל האיברים אחרי האיבר שמחקנו למקום שהתפנה,
בעוד שברשימה מקושרת כל שעלינו לעשות זה למחוק איבר אחד ולהעתיק את שדה הקישור שלו לשדה הקישור של
האיבר שלפניו.
כדי להמשיך נחזור ל struct, נראה איך יוצרים מצביע על מבנה:
#include <stdio.h> struct worker { char name[20]; int age; double hours, pph; }; void main() { struct worker w1 ,*p; p = &w1; // *p.age = 32; פקודה לא חוקית בשפה, כי הנקודה קודמת למצביע (*p).age = 32; // חוקי // במקום להשתמש בצורה הארוכה הזאת יצרו לזה קיצור p->age = 32; // זה יותר קצר וכך נהוג לכתוב }
בניית רשימה מקושרת (חד סטרית):
נכתוב פונקציה בשם Creat List שלא מקבלת כלום, בונה רשימה מקושרת עם ערכים שמכניס המשתמש ומחזירהמצביע על האיבר הראשון (head).
-הוספת האיברים תהיה לסוף הרשימה.
לפני הכתיבה נסביר מה אנחנו הולכים לעשות:
פעולת הפונקציה:
שאלה למשתמש האם רוצה להוסיף עוד איבר או לא:
- אם כן: לייצר האיבר, ולקשר אותו לסוף הרשימה. ולחזור למעלה (כלומר לשאול שוב).
- אם לא: לצאת.
כשקולטים צריך להתייחס אם האיבר שנקלט הוא האיבר הראשון או שכבר יש איברים ברשימה (כדי לדעת איך להכניס לרשימה את הקלט מהמשתמש)
- אם הרשימה ריקה (כלומר קיבלנו את האיבר הראשון)
p מקבל כתובת מ malloc
;head = tail = p
- אם הרשימה לא ריקה (כלומר לא קיבלנו את האיבר הראשון אלא כבר היו איברים לפנינו)
p מקבל כתובת מ malloc
;tail->next = p
;tail = pהגדרת סוג איברי הרשימה:
תוכן - info
שדה קישור - next
נשמור את המרכיבים במבנה:
struct Item{
int info
struct Item *next;
};
struct Item שימו לב שכמו קודם גם כאן בהגדרת המצביע אנחנו מציינים שהוא
אפשר גם ליצור את איברי המערך עם יותר משדה תוכן אחד (לא נעשה את זה בתוכנית הבאה):
struct worker{
char[20];
int age;
struct worker* next;
};
עכשיו נעבור לתוכנית עצמה:
#include <stdio.h> #include <stdlib.h> struct Item { int info; struct Item* next; }; struct Item* CreateList() { struct Item *head = NULL, *tail, *p; while( 1 ) { printf("Enter Esc to finish, any other key to continue\n"); flushall(); if(getch() == 27) break; p = (struct Item*) malloc( sizeof(struct Item) ); printf("Enter number: "); scanf("%d",&p->info); p->next = NULL; if(head == NULL) head = tail = p; else { tail->next = p; tail = p; } } return head; } void main() { struct Item* head; head = CreateList(); }
הסבר נוסף על התוכנית בשיעור הבא..
אין תגובות:
הוסף רשומת תגובה