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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

תבנית:ניווט מבוא

מבני נתונים דינמיים[עריכה]

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

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

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

רשימה משורשרת[עריכה]

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

קודקוד אחד[עריכה]

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

Linkedlist1.png
#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; 
}

שני קודקודים מקושרים[עריכה]

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

Linkedlist2.png
#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; 
}
Linkedlist3.png

קוד פרוצדורלי[עריכה]

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

#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); 
}
Linkedlist insertLast1.png

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

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

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; 
}

תבנית:ניווט מבוא