1 of 41

מבוא למדעי המחשב��רשימה מקושרת

בס"ד

צביקה ברגר

2 of 41

רשימה מקושרת

בס"ד

Head

NULL

3 of 41

יצירת רשימה מקושרת

יצירת מצביע לאיבר ה-head של הרשימה.

בס"ד

Head

NULL

4 of 41

יצירת איבר

בס"ד

5 of 41

הכנסה

כאשר מכניסים יש 3 מקרים:

הכנסה בתחילת הרשימה.
הכנסה באמצע הרשימה.
הכנסה בסוף הרשימה.

בס"ד

6 of 41

הכנסה לראש הרשימה

בס"ד

7 of 41

הכנסה לסוף הרשימה

בס"ד

8 of 41

הכנסה לאמצע הרשימה

בס"ד

9 of 41

מחיקה

כאשר מוחקים איבר ברשימה יש 3 מקרים:

מחיקת האיבר הראשון ברשימה.
מחיקת איבר באמצע הרשימה.
מחיקת האיבר האחרון ברשימה.

בס"ד

10 of 41

מחיקת האיבר הראשון

בס"ד

11 of 41

מחיקת האיבר האחרון

בס"ד

12 of 41

מחיקת איבר באמצע

בס"ד

13 of 41

חיפוש

חיפוש איבר ברשימה על פי ערך האיבר:

בס"ד

14 of 41

הדפסת כל הרשימה

בס"ד

15 of 41

מחיקת כל הרשימה

בס"ד

16 of 41

תרגיל 1 - הפיכת רשימה

בס"ד

17 of 41

הפיכת רשימה

כתוב תוכנית שהופכת רשימה מקושרת

בס"ד

18 of 41

הפיכת רשימה

בס"ד

הרעיון:

נאתחל עוד פוינטר temp בתחילת הרשימה.

כל פעם Head יתקדם ויחליף את המצביע ל-temp.

לאחר מכן, temp יתקדם למקום של Head.

19 of 41

הפיכת רשימה

בס"ד

temp

Head

NULL

20 of 41

הפיכת רשימה

בס"ד

NULL

Head

temp

21 of 41

הפיכת רשימה

בס"ד

NULL

Head

temp

22 of 41

הפיכת רשימה

בס"ד

NULL

Head

temp

NULL

23 of 41

הפיכת רשימה

בס"ד

NULL

Head

temp

NULL

24 of 41

הפיכת רשימה

בס"ד

NULL

Head

temp

NULL

25 of 41

הפיכת רשימה

בס"ד

NULL

Head

temp

NULL

26 of 41

הפיכת רשימה

בס"ד

NULL

Head

temp

NULL

27 of 41

הפיכת רשימה

בס"ד

NULL

Head

temp

NULL

28 of 41

הפיכת רשימה

בס"ד

NULL

Head

temp

NULL

29 of 41

הפיכת רשימה

בס"ד

NULL

Head

temp

NULL

30 of 41

הפיכת רשימה

בס"ד

NULL

Head

temp

NULL

31 of 41

הפיכת רשימה

בס"ד

NULL

Head

temp

32 of 41

הפיכת רשימה - איטרטיבי

נפעיל את הפונקציה עם הפקודה:

בס"ד

33 of 41

הפיכת רשימה - רקורסיבי

בס"ד

34 of 41

תרגיל 2 – מציאת אמצע ברשימה

בס"ד

35 of 41

תרגיל 2 - מציאת אמצע ברשימה

כתוב תוכנית שמוצאת את האיבר האמצעי ברשימה מקושרת

בס"ד

Head

NULL

36 of 41

תרגיל 2 - מציאת אמצע ברשימה

הרעיון:

נאתחל שני פוינטרים p1, p2 בתחילת הרשימה.

P1 כל פעם יקפוץ לאיבר הבא.

P2 יקפוץ 2 איברים קדימה.

כאשר p2 מגיע לאיבר האחרון, p1 נמצא באיבר האמצעי.

בס"ד

37 of 41

תרגיל 2 - מציאת אמצע ברשימה

בס"ד

Head

NULL

p1

p2

38 of 41

תרגיל 2 - מציאת אמצע ברשימה

בס"ד

Head

NULL

p1

p2

39 of 41

תרגיל 2 - מציאת אמצע ברשימה

בס"ד

Head

NULL

p1

p2

40 of 41

תרגיל 2 - מציאת אמצע ברשימה

בס"ד

41 of 41

שאלות?

בס"ד