רשימות מקשרות
צמתים המחוברים באמצעות נורמלים
- רשימה מקושרת היא שרשרת של מבני נתונים קטנים הנקראים צמתים, מפוזרים בכל הזיכרון.
- כל צומח מחזיק ערך ו-נורמל לצומח הבא. עקוב אחרי הנורמלים כדי לעבור על הרשימה.
- בניגוד למערך, רשימה יכולה להתרחב צומח אחד בכל פעם ללא העברת האחרים.
מבנה נתונים המתייחס לעצמו
- צומח הוא מבנה נתונים המכיל נורמל ל-סוג שלו:
struct Node { int data; struct Node *next; };—dataהוא הערך,nextמצביע לצומח הבא.- זה נתון לך כ-
Nodeבכל תבנית התחלה. ה-nextשל הנודה האחרונה הואNULL.
ראש הסוף NULL
- נורמל אחד, ה-ראש, מצביע לצומח הראשון. ממנו מגיעים לשאר.
- הצומח האחרון מצביע ל-
NULL, שמסמן את סוף הרשימה. - רשימה ריקה היא פשוט
head == NULL— אין כלל נודות.
#include <stdio.h>
typedef struct Node { int data; struct Node *next; } Node;
int main(void) {
// A tiny list on the stack: 10 -> 20 -> 30 -> NULL
Node n3 = {30, NULL};
Node n2 = {20, &n3};
Node n1 = {10, &n2};
const Node *head = &n1;
// Walk it: follow ->next until NULL, counting nodes
int count = 0;
const Node *cur = head; // start at the head
while (cur != NULL) { // stop at the NULL end
count++;
cur = cur->next; // step to the next node
}
printf("length = %d\n", count); // length = 3
return 0;
}
הוספת צומח בהתחלה
- להוספה בראש, צור נוד (צומת) חדש, נקד את
nextשלו לראש הקיים, והחזר את הנוד החדש כראש החדש. - פעולה זו מהירה — היא אינה פוגעת בשום נוד אחר.
- מכיוון שהראש משתנה, הפונקציה מחזירה את הראש החדש, והקורא שומר אותו.
טעויות נפוצות
- Never lose the
headpointer, or the whole list is unreachable. - שחרר כל נוד; הנוד האחרון מצביע על
NULL.
כעת תנסו בעצמכם
- הליכה ברשימה עם מצביע
curו-cur = cur->next, עצור ב-NULL. - נודים חדשים מגיעים מ
malloc(sizeof(Node)); הבוחן משחרר את הרשימה. אל תכתובmain.
נודים ומצביעים
כל נוד מופנה לנוד הבא; הוספה/מחיקה מתבצעת על ידי שינוי הקישורים.
רמת קושי 5/5 · 400 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם את int length(const Node *head) כדי לספור את הנודים ברשימה (0 עבור רשימה ריקה). צלול עם ->next עד ש-NULL. סוג ה-Node נתון. אל תכתוב פונקציית main.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 5/5 · 400 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם את int sum_list(const Node *head) כדי להחזיר את הסך הכל של כל ה-data של כל נוד (0 עבור רשימה ריקה). סוג ה-Node נתון. אל תכתוב פונקציית main.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 5/5 · 400 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם את Node *push_front(Node *head, int value) כדי ליצור נוד חדש (עם malloc), להפנות את ה-next שלו ל-head הישן, ולהחזירו כראש חדש. הבוקר ישחרר את הרשימה. אל תכתוב פונקציית main.
לחץ על הרץ כדי לראות את התוצא כאן.