יסודות מדעי המחשב — מרחב למידה אישי

ברוכים הבאים ליחידת הלימוד "מבני נתונים יסודיים: רשימות ומחרוזות" בקורס יסודות מדעי המחשב (371.1.1601). יחידה זו היא אבן יסוד בהבנת אופן הארגון והעיבוד של נתונים בסיסיים בתוכנה. נתמקד בשני מבני נתונים פופולריים ורב-גוניים ב-Python – רשימות (Lists) ומחרוזות (Strings) – ונבחן את תכונותיהם, פעולותיהם המרכזיות, והשימושים הנפוצים שלהם, תוך דגש על הבנה מעמיקה הנדרשת לבחינות באוניברסיטת בן-גוריון.

מבוא לרשימות ומחרוזות

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

רשימה (List): אוסף מסודר וניתן לשינוי (mutable) של פריטים. פריטים אלו יכולים להיות מטיפוסים שונים (הטרוגניים). רשימות מוגדרות באמצעות סוגריים מרובעים `[]` והפריטים מופרדים בפסיקים.

מחרוזת (String): אוסף מסודר וקבוע (immutable) של תווים. מחרוזות משמשות לייצוג טקסט ומוגדרות באמצעות גרשיים בודדים `''` או כפולים `""`.

תכונות משותפות

סדר (Ordered): הסדר שבו הפריטים נשמרים הוא קבוע וניתן לגשת אליהם לפי אינדקס (מ-0 ואילך).
אינדקס (Indexing): גישה לפריט בודד באמצעות מיקומו. לדוגמה, `my_list[0]` או `my_string[2]`.
פריסה (Slicing): יצירת תת-אוסף של פריטים מתוך האוסף המקורי. לדוגמה, `my_list[1:4]` או `my_string[::2]`.
איטרציה (Iteration): ניתן לעבור על כל הפריטים באוסף באמצעות לולאת `for`.

פעולות יסודיות ושימוש נפוץ

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

פעולות על רשימות

הוספה: `list.append(item)` מוסיף בסוף, `list.insert(index, item)` מוסיף במיקום ספציפי.
הסרה: `list.pop()` מסיר את האחרון ומחזיר אותו, `list.pop(index)` מסיר במיקום ספציפי, `list.remove(value)` מסיר את המופע הראשון של ערך מסוים.
חיפוש: `value in list` בודק קיום, `list.index(value)` מחזיר אינדקס של מופע ראשון.
מיון: `list.sort()` ממיין את הרשימה במקום, `sorted(list)` מחזיר רשימה ממוינת חדשה.
היפוך: `list.reverse()` הופך את סדר הרשימה במקום.

פעולות על מחרוזות

שרשור (Concatenation): חיבור מחרוזות באמצעות האופרטור `+`. לדוגמה: `'hello' + ' ' + 'world'`.
חזרה (Repetition): הכפלת מחרוזת באמצעות האופרטור `*`. לדוגמה: `'abc' * 3` ייתן `'abcabcabc'`.
פיצול (Splitting): `string.split(delimiter)` מפצל מחרוזת לרשימת מחרוזות לפי מפריד.
איחוד (Joining): `delimiter.join(list_of_strings)` מאחד רשימת מחרוזות למחרוזת אחת באמצעות מפריד.
חיפוש והחלפה: `string.find(substring)`, `string.replace(old, new)`.
שינוי רישיות: `string.upper()`, `string.lower()`, `string.capitalize()`.

ההבדל המהותי: שינוי מול קביעות

ההבדל בין רשימות (mutable) למחרוזות (immutable) הוא קריטי ומקור לטעויות רבות, ולכן הוא נושא אהוב בבחינות.

רשימות (Mutable)

ניתן לשנות את תוכן הרשימה לאחר יצירתה. הוספה, הסרה או שינוי של פריטים משפיעים על אותה אובייקט בזיכרון. לדוגמה: my_list = [1, 2, 3]; my_list[0] = 10; my_list.append(4).

מחרוזות (Immutable)

לא ניתן לשנות את תוכן המחרוזת לאחר יצירתה. כל פעולה שנראית כמשנה מחרוזת (כמו שרשור או החלפה) למעשה יוצרת מחרוזת חדשה בזיכרון. המחרוזת המקורית נשארת ללא שינוי. לדוגמה: my_string = "hello"; new_string = my_string.upper(). my_string עדיין "hello".

השלכות של שינוי (Mutability): הבנת מושג ה-Mutability חיונית. כאשר מעבירים רשימה כארגומנט לפונקציה, הפונקציה מקבלת הפניה לאותה רשימה בזיכרון. שינויים שתבצע הפונקציה ברשימה ישפיעו על הרשימה המקורית מחוץ לפונקציה. זהו מקור נפוץ לבאגים ולשאלות בבחינה הדורשות ניתוח קוד. שימו לב גם להבדל בין העתקה רדודה (shallow copy) לעמוקה (deep copy) ברשימות מקוננות.

יישומים מתקדמים ופתרון בעיות

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

רשימות של רשימות (מטריצות)

רשימות יכולות להכיל רשימות אחרות, וליצור מבנים דו-ממדיים כמו מטריצות. לדוגמה, matrix = [[1, 2], [3, 4]]. גישה לאלמנט תתבצע באמצעות שני אינדקסים: matrix[row][col]. שאלות רבות בבחינות עוסקות במניפולציות על מטריצות (סיבוב, חיפוש, סכימה).

עיבוד טקסט וביואינפורמטיקה

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

פתרון בעיות אלגוריתמיות

רשימות ומחרוזות משמשות ככלי עבודה בסיסי ליישום אלגוריתמים רבים:

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

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

שאלות לדיון

הסבירו את ההבדל בין העתקת רשימה באמצעות `new_list = old_list` לבין `new_list = old_list[:]`. מתי נכון להשתמש בכל אחת מהן?
כתבו פונקציה ב-Python שמקבלת רשימה של מספרים שלמים ומחזירה רשימה חדשה המכילה רק את המספרים הזוגיים, בסדר הפוך.
כיצד ניתן לבדוק האם מחרוזת היא פלינדרום (נקראת זהה קדימה ואחורה) ביעילות? הציגו שתי גישות אפשריות.
בהינתן רשימה של מחרוזות, כתבו קטע קוד שיאחד את כל המחרוזות למחרוזת אחת ארוכה, כאשר כל מחרוזת מקורית מופרדת ברווח.
תארו מצב שבו אי-הבנה של מושג ה-Mutability ברשימות עלולה להוביל לבאג קשה בתוכנה.

נקודות לתשובת מודל

העתקת רשימות: `new_list = old_list` יוצר הפניה לאותו אובייקט (aliasing), שינוי באחת משפיע על השנייה. `new_list = old_list[:]` (או `old_list.copy()`) יוצר עותק רדוד (shallow copy) חדש, שינויים בו לא ישפיעו על המקור (אלא אם הפריטים הם אובייקטים mutable בעצמם).
פונקציה למספרים זוגיים הפוכים: שימוש בלולאה לבדיקת זוגיות (`num % 2 == 0`), הוספה לרשימה חדשה, ולבסוף היפוך הרשימה החדשה (`new_list.reverse()` או `new_list[::-1]`).
בדיקת פלינדרום:
1. השוואה בין המחרוזת למחרוזת ההפוכה שלה: `s == s[::-1]`.
2. שימוש בשני מצביעים (אחד מההתחלה ואחד מהסוף) והתקדמות פנימה, תוך השוואת תווים.
איחוד מחרוזות: שימוש בשיטת `str.join()`: `result = " ".join(list_of_strings)`.
באג מ-Mutability: לדוגמה, פונקציה שמקבלת רשימה, מבצעת עליה שינויים (כגון מיון או הסרת איברים), ומצפה שהרשימה המקורית מחוץ לפונקציה תישאר ללא שינוי. אם לא נוצר עותק מפורש בתוך הפונקציה, הרשימה המקורית תשתנה באופן בלתי צפוי.

מצאתם טעות או שחסר משהו?