מבוא לתכנות ולמדעי המחשב בשפת C/מבני נתונים דינמיים - רשימה משורשרת ו merge sort

מבני נתונים דינמיים

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

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

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

רשימה משורשרת

אחד ממבני הנתונים הדינמיים הבסיסיים וגם השימושיים ביותר הוא רשימה משורשרת. רשימה משורשרת היא סדרה של מבנים שלכל אחד מהם מצביע המצביע למבנה הבא. המבנה האחרון מצביע ל NULL.

קודקוד אחד

נתחיל מקוד פשוט המצהיר על מבנה שבו נתון כלשהו, במקרה זה int פשוט, ומצביע למבנה אחר. למבנה הזה נקרא קודקוד או Node.

#include <stdio.h> 
#include <stdlib.h> 

typedef struct Node {
    int data; 
    struct Node* next; 
} Node; 

int main() {
    Node *p = (Node*) malloc (sizeof(Node)); 
    p->data = 123; 
    p->next = NULL; 

    printf("%d \n",p->data); 

    return 0; 
}

שני קודקודים מקושרים

כעת ניצור שני מבנים כאלה כך שאחד מצביע לשני.

#include <stdio.h> 
#include <stdlib.h> 
 
typedef struct Node {
    int data; 
    struct Node* next; 
} Node; 
 
int main() {
    Node *p1 = (Node*) malloc (sizeof(Node)); 
    p1->data = 1; 
    p1->next = NULL; 
 

    Node *p2 = (Node*) malloc (sizeof(Node)); 
    p2->data = 2; 
    p2->next = p1; // linking the new node to the previous node 


    Node *p = p2; 

    printf("%d \n",p->data); 

    p = p->next; // move pointer to the next node 

    printf("%d \n",p->data); 

 
    return 0; 
}

פלט:

2 
1

הכנסת קודקוד בין קודקודים קיימים

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

#include <stdio.h> 
#include <stdlib.h> 
 
typedef struct Node {
    int data; 
    struct Node* next; 
} Node; 
 
int main() {
    Node *p1 = (Node*) malloc (sizeof(Node)); 
    p1->data = 1; 
    p1->next = NULL; 
 

    Node *p2 = (Node*) malloc (sizeof(Node)); 
    p2->data = 2; 
    p2->next = p1; 

    Node *p3 = (Node*) malloc (sizeof(Node)); 
    p3->data = 3; 

    // place the new node *between* the two existing node  
    p3->next = p1; 
    p2->next = p3; 

    Node *p = p2; 

    while(p!=NULL) {
	printf("%d \n",p->data); 
	p = p->next; 
    }

    return 0; 
}

קוד פרוצדורלי

כל פעולות שעשינו עד כה היו מאוד ספציפיות. יצרנו קודקוד מסויים, שירשרנו אותו, תפרנו לפניו וכ'. כעת נכתוב קוד יותר כללי לטיפול ברשימה משורשרת. הקוד יכיל מספר שירותים בסיסיים שהיינו רוצים שיהיו למבנה הנתונים.

#include <stdio.h> 
#include <stdlib.h> 
 
typedef struct Node {
    int data; 
    struct Node* next; 
} Node; 
 
Node* newNode(int data, Node *next) {
    Node *p = (Node*) malloc (sizeof(Node)); 
    p->data = data; 
    p->next = next; 
    return p; 
}
 
void insertFirst(int data, Node **head) {
 
    Node *tmp = *head; 
    *head = (Node*) malloc (sizeof(Node)); 
    (*head)->data = data; 
    (*head)->next = tmp; 
 
    // An alternative implemetation of the function: 
    // *head = newNode(data,*head); 
}
 
void printList(Node *head) {
    while(head) {
	printf("%d->",head->data);
	head = head->next; 
    }
    printf("\n"); 
}
 
void freeList(Node *p) {
    if(!p)
	return; 
    freeList(p->next);
    free(p); 
}
 
int main() {
    int ints[] = {4,3,1,7,8,5};
    int N = sizeof(ints)/sizeof(int); 
 
    Node *head = NULL;
    int i; 
    for(i=0; i<N; ++i)
	insertFirst(ints[i], &head); 
 
    printList(head); 

    freeList(head); 

    return 0; 
}

פלט:

5->8->7->1->3->4->

הוספה לסוף הרשימה

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

void insertLast(int data, struct Node **head) {
    if(*head == NULL) {
	*head = newNode(data,NULL); 
	return; 
    }
    
    struct Node *p = *head; 

    while(p->next != NULL)
	p = p->next; 

    p->next = newNode(data,NULL); 
}

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

void insertLast(int data, struct Node **head) {
    struct Node **p = head; 
    while(*p)
	p = &((*p)->next); 
    *p = newNode(data,NULL); 
}

merge sort

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

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

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

#include <stdio.h> 
#include <stdlib.h> 

typedef struct Node {
    int data; 
    struct Node* next; 
} Node; 

Node* newNode(int data, Node *next) {
    Node *p = (Node*) malloc (sizeof(Node)); 
    p->data = data; 
    p->next = next; 
    return p; 
}

void printList(Node *head) {
    while(head) {
	printf("%d->",head->data);
	head = head->next; 
    }
    printf("\n"); 
}

void freeList(Node *p) {
    if(!p)
	return; 
    freeList(p->next);
    free(p); 
}

void split(Node *p, Node **l1, Node **l2) {
    Node *n1, *n2; 
    n1 = *l1 = p; 
    n2 = *l2 = p->next; 
    while(1) {
	if(!n2->next) {
	    n1->next = NULL; 
	    return; 
	}
	n1 = n1->next = n2->next;
	if(!n1->next) {
	    n2->next = NULL; 
	    return; 
	}
	n2 = n2->next = n1->next; 
    }
}

Node* merge(Node *n1, Node *n2) {
    Node *head; 
    Node **l = &head; 
    while(1) {
	if(!n1) {
	    *l = n2;
	    return head; 
	}
	
	if(!n2) {
	    *l = n1;
	    return head; 
	}

	if(n1->data < n2->data) {
	    *l = n1; 
	    l = &(n1->next); 
	    n1 = n1->next; 
	} else {
	    *l = n2; 
	    l = &(n2->next); 
	    n2 = n2->next; 
	}
    }
}

Node* mergeSort(Node *p) {
    if(!p || !(p->next))
	return p; 
    Node *l1,*l2; 
    split(p,&l1,&l2); 
    l1 = mergeSort(l1); 
    l2 = mergeSort(l2); 
    return merge(l1,l2); 
}

int main() {
    Node *node = NULL;
    int i; 
    for(i=0; i<1000; ++i)
	node = newNode(rand()%10000+1,node); 

    printList(node); 

    node = mergeSort(node); 
    printList(node); 

    return 0; 
}