Element
======

element או node , item 
	הוא חלק בסיסי של מבנה אינפורמציה המורכב ממילת מחשב אחת או ממספר עוקב של מלות מחשב. ה-element מחולק לשדות.

זיכרון memory= – מקום אחסון של אינפורמציה במחשב.  הזיכרון מורכב ממלות מחשב עם גישה לכל מלה.  מלה מרכבת מיחידות אינפורמציה 0 או 1 – Bite.

address (link, pointer, reference) של element הוא המקום, ה- location בזיכרון של מילת המחשב הראשונה של ה-element.

Δ link = null link הוא ה-link ללא element.  לפעמים בתאור גרפי נוח לסמן link בעזרת חץ.

שדה – field – הוא חלק מ-element המורכב מ-bit  אחד או ממספר עוקב של bits/
השדה יכול לקבל ערכים מקבוצת הטיפוסים שהזכרנו:     integers, float, char .
שדה מטיפוס integer יכול להיות מספר שמשמעותו  link ל-element  אחר.

דוגמאות:
======
רוצים לסמן ערמה של קלפים:
1) 10 תלתן Club הפוך,
2)  3 עלה שחור Spade
3)   2 יהלום Diamond

נשתמש בשדות הבאים לייצוג כל אלמנט:
1) TAG הוא שדה המציין את מצבו של הקלף:  (1)פנים למעלה או הפוך(0);
2) SUIT הסידרה של הקלף:Club, Diamonds, Heart, Spade ובהתאם במספרים סידוריים 1,2,3,4 ;
3) RANK – ערך של הקלף: 1,2,3,4,5,6,7,8,9,10,11,12,13
      מאס עד מלך;
4) NEXT – הכתובת של האלמנט הבא;

האלמנט נראה כך:
TAG	SUIT	RANK	NEXT	
TITLE	

והוא מורכב משתי מלות מחשב.

אפשר לתאר את ה-element ב-C בתור structure :
struct node{
int TAG;
int SUIT;
int RANK;
int NEXT;
char TITLE[6];
}

וייצוג במחשב של ערמת שלושת הקלפים הוא כך:

100
101	1	1	10	0	
	Club 10	

386
387	0	4	3	100	
	Spade 3	

	   
242
243	0	2	2	386	
	Diamond 2	

או בעזרת חיצים:
TOP	0	2	2			0	4	3			1	1	10		
	2        D          		3        S                		10       C               	

---------
------- 
----  
הארקה  מסמנת את ה-Null link.
שמות סימבוליים:
1. variables – משתנים;
     הכוללים גם את ה-link variable שהוא משתנה שערכו הוא link.
2.   fields - שדות,
3.  elements שלמים – ז"א מספר שדות ביחד.

התיחסות לשדות של האלמנט:
נתנת על ידי  מתן שם של השדה )לדוגמא במקרה שלנו – (RANK ובהמשך ה-link  (כתובת) ל- element בסוגריים.

למשל:   RANK (100)
	    Value =  Field (Link)

ערכו 10.  (ראה את הקלף הראשון בערמה לעיל).

SUIT(TOP)
ערכו 1.

אם F הוא שם של שדה ו-L הוא link   L≠∆ אז F(L) הוא משתנה.

הקשר בין הכתובות והערכים המאוחסנים בהן:
1)CONTENTS(V) 
	V- link  variable (משתנה מטיפוס    כתובת - Link)
	
     הערך של מלת מחשב שלמה, אליה מצביע ה- V.

למשל אם V=100  אז   CONTENTS(100)  הוא הקיבולת, התוכן של מלת מחשב בכתובת 100.

2)   NODE(V) הערך של element  שלם,

סכום
עד עכשיו התעכבנו על מבנה אינפורמציה מסוג אחד.  דברנו על ערמת קלפים ותארנו אותה במחשב בעזרת אלמנטים עם   pointer  אחד: מלמעלה למטה.
ז"א מטפלים בקלף k    דרך  הגישה לקלף העליון (בעזרת ה-pointer  (TOP -
זהו מחסנית.

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

כלל 1 בתכנון מבנה נתונים:
בזמן תכנון מבנה נתונים לנתונים הקימים, יש להתחשב לא רק בסטרוקטורה של הנתונים – אלא גם במחלקת הפעולות שיש לעשות על הנתונים.
רשימה לינארית: קבוצה של מ>=0 אלמנטים 
x(1), x(2),   .. x(n)  .
התכונות הסטרוקטורליות שלהם כוללות בעיקרו רק מיקום יחסי לינארי (חד ממדי).
ז"א אם n>1 x(1) הוא ה-element הראשון,
:    1<k<n     ה- element   ה-k x(k) בא אחרי האלמנט ה- k-1ז"א x(k-1)
						ולפני האלמנט ה- k+1ז"א x(k+1)

הפעולות  האפשריות ב-linear list   הן:
1. גישה לאלמנט ה-ל של הרשימה,
    בדיקה ו/או שנוי שדותיו.
2. השתלת (insert) אלמנט חדש לפני האלמנט ה-k.
3. הוצאת (delete)  האלמנט ה-k.
4. קשירת שתיים או יותר רשימות לינאריות לרשימה אחת.
5. פרוק רשימה לינארית לשתיים או יותר רשימות.
6. עשיית העתר של רשימה לינארית.
7. ספירת האלמנטים ברשימה.
8. מיון הרשימה לפי סדר עולה או יורד, המבוסס על אחד משדות האלמנטץ
9. חפוש אחר אלמנט בעל ערך מיוחד באחד משדותיו.

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

אימפלמנטציות נפוצות של רשימות לינאריות כאשר הפעולות היסודיות הנדרשות הן:
1) השתלה insertion,
2) הוצאה delete,
3) גישה נוחה לאבר הראשון והאחרון ברשימה.

S (store)

1. stack – מחסנית, LIFO     

R (remove)

כאן הפעולות מתבצעות בתחילת הרשימה בעזרת הפעולות:
push – הוצאת אבר ממחסנית,
pop – הכנסת אבר למחסנית.

2. queue – תור FIFO
 הכנסת אבר מתבצעת בצעד אחד של הרשימה,
הוצאת אבר מתבצעת בצד השני של הרשימה.

R (remove)

S (store)

3. deque – דותור
הכנסתו של האבר לרשימה והוצאתו מהרשימה מתבצעים בשני צדי ה-דותור.

T

R (remove)

S (store)

.

X

4. חד-פלט:

X

S (store)

יכול לפעול כמחסנית וכתור.

R(remove))))רקצםהק (remove)

5. חד קלט

T

R(remove))))רקצםהק (remove)

S (store)

גם יכול לפעול כמחסנית וכתור.