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

תַחבִּיר

רשימת קדימה מוגדרת כ- STD :: Forward_List תבנית כיתה בתוך< רשימת קדימה > קובץ כותרת.

רשימת קדימהfl;

אֵיפֹה

• T: סוג הנתונים של אלמנטים ברשימה קדימה.
• F: שם שהוקצה לרשימת הפורוורד.

הצהרה ואתחול

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

מחרוזות משרשרות java

#include    using namespace std; void printFL(forward_list<int>& fl) {  for (auto i : fl)  cout << i << ' ';  cout << 'n'; } int main() {    // Creating an empty forward_list  forward_list<int> fl1;  // Creating a forward_list with  // default value  forward_list<int> fl2(3 4);    // Creating a forward_list from an  // initializer list  forward_list<int> fl3 = {1 5 3 4};    printFL(fl2);  printFL(fl3);  return 0; } 

4 4 4 1 5 3 4 

דוּגמָה: בתוכנית לעיל אנו פשוטים רשימת קדימה לאתחל בשלוש דרכים:

• הַצהָרָה רשימת קדימה FL1 יוצר רשימה קדימה ריקה של מספרים שלמים.
• הַצהָרָה רשימת קדימה FL2 (34) יוצר רשימה קדימה של גודל 3 ועם כל אלמנט הוא 4.
• הַצהָרָה רשימת קדימה FL3 = {1 5 3 4} יוצר רשימה קדימה ומאתחל עם האלמנטים מהווים את רשימת האתחול.

פעולות בסיסיות

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

1. גישה לאלמנטים

לא ניתן לגשת לאלמנטים של רשימת קדימה באמצעות מדדים כמו מערכים או וקטורים. עלינו לעבור את הרשימה ברצף מההתחלה למצב הרצוי כדי לגשת אליה. ניתן לעשות זאת על ידי הגדלה לְהַתְחִיל() איטרטור אבל עדיף להשתמש הַבָּא() אוֹ לְקַדֵם() פוּנקצִיָה.

עם זאת ניתן לגשת בקלות לאלמנט הראשון ברשימה חֲזִית() שִׁיטָה.

דוּגמָה:

#include    using namespace std; int main() {  forward_list<int> fl = {1 5 3 4};  // Access the first element  cout << fl.front() << endl;    // Access third element  auto it = next(fl.begin() 2);  cout << *it;  return 0; } 

1 3

דוּגמָה: בתוכנית לעיל האלמנט הראשון מודפס על ידי שימוש חֲזִית() שִׁיטָה. כדי לגשת לאלמנט השלישי הַבָּא() משמש כדי להזיז את האיטרטור שתי עמדות מההתחלה ו *זֶה משמש להפעלת האיטרטור.

2. הכנסת אלמנטים

ניתן להכניס אלמנטים ברשימה קדימה באמצעות insert_after () פוּנקצִיָה. זה דורש את האיטרטור שאחריו יש להכניס את האלמנט. עם זאת, החדרת מהירה בחזית נתמכת על ידי Push_front () שִׁיטָה.

דוּגמָה:

#include    using namespace std; int main() {  forward_list<int> fl = {5 4};  // Inserting Element at front  fl.push_front(1);    // Insert 3 after the second element  auto it = fl.begin();  advance(it 1);  fl.insert_after(it 3);    for (auto x: fl) cout << x << ' ';  return 0; } 

1 5 3 4 

הֶסבֵּר: בתוכנית זו המוחדר האלמנט הראשון של ה- Forward_list בחזית Push_front () פוּנקצִיָה. ואז נוצר איטרטור ומעביר מיקום אחד קדימה באמצעות לְקַדֵם() פוּנקצִיָה. אחרי זה האלמנט 5 מוכנס לאחר האלמנט השני באמצעות insert_after () פוּנקצִיָה.

3. עדכון אלמנטים

ניתן לשנות את ערך האלמנטים הקיימים פשוט על ידי גישה אליהם ושימוש מפעיל הקצאה להקצאת הערך החדש.

דוּגמָה:

למצוא את האייפון שלי מאנדרואיד

#include    using namespace std; int main() {  forward_list<int> fl = {1 5 3 4};  // Updating first element  fl.front() = 111;  cout << fl.front() << endl;    // Updating third element  auto it = next(fl.begin() 2);  *it = 333;  cout << *it;  return 0; } 

111 333

4 מציאת אלמנט

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

דוּגמָה :

#include    using namespace std; int main() {  forward_list<int> fl = {1 5 3 4};  // Finding 3  auto it = find(fl.begin() fl.end() 3);    if (it != fl.end()) cout << *it;  else cout << 'Element not Found';  return 0; } 

3

5. חוצה

ניתן לחצות רשימה קדימה באמצעות לְהַתְחִיל() וכן סוֹף() איטרטורים עם לולאה אבל אנחנו יכולים רק להתקדם ולא לאחור.

דוּגמָה:

#include    using namespace std; int main() {  forward_list<int> fl = {1 5 3 4};    // Traversing using range-based for loop  for(auto i : fl)  cout << i << ' ';  cout << endl;    return 0; } 

1 5 3 4 

6. מחיקת אלמנטים

ברשימה קדימה אנו יכולים למחוק את האלמנט במיקום הנתון באמצעות arase_after () שִׁיטָה. שיטה זו לוקחת את האיטרטור למיקום אחד לפני אלמנט היעד. מחיקה מהירה מקדימה אפשרית באמצעות pop_front () שִׁיטָה.

דוּגמָה:

#include    using namespace std; int main() {  forward_list<int> fl = {1 5 3 4};  // Delete first element  fl.pop_front();    // Delete third element  auto it = fl.begin();  advance(it 1);  fl.erase_after(it);    for (auto x: fl) cout << x << ' ';  return 0; } 

5 3 

7. גודל הרשימה קדימה

ל- Forward_List אין פונקציה מובנית (). כדי למצוא את גודלו עלינו לספור ידנית את האלמנטים על ידי חצייתו עם לולאה או שימוש ב- STD :: מרחק.

#include    #include  #include    using namespace std; int main() {  forward_list<int> flist={10203040};  //Calculate size by counting elements using std:: distance  int size=distance(flist.begin()flist.end());  cout<<'Size of forward_list: '<<size<<endl;  return 0; } 

Size of forward_list: 4 

8. ריק ()

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

#include    #include  using namespace std; int main() {  forward_list<int> flist;  if (flist.empty()) {  cout << 'The forward_list is empty.' << endl;  }  flist.push_front(10);  if (!flist.empty()) {  cout << 'The forward_list is not empty.' << endl;  }  return 0; } 

The forward_list is empty. The forward_list is not empty. 

מורכבות זמן

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

רשימת קדימה לעומת רשימה