* מההתחלה C *

המדריך השלם

מחסנית ותור

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

המחסנית והתור שייכים לקבוצה הנקראת מבנה נתונים מופשט (Abstract Data Type) -כלומר הם מאופיינים ע"י תכונות ייחודיות ועל ידי קבוצת פעולות בסיסיות.

המחסנית (stack)

מחסנית - הינה מבנה נתונים מופשט. התכונה העיקרית שלה היא שהאיבר הראשון שיוכנס אליה יהיה הראשון לצאת (first in last out) - כלומר הוצאה והכנסה של איבר אפשרית רק מלמעלה (מראש המחסנית).

המחסנית
Last
..
Fourth
Third
Second
First

ראש המחסנית הוא האיבר העליון.

הפעולות:
push - דחיפת איבר לראש המחסנית.
pop - שליפת איבר מראש המחסנית (שליפת ראש המחסנית).
init - אתחול המחסנית,האיבר הראשון של המחסנית שווה ל null

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

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

מבנה של המחסנית:

struct stack
{
...
struct stack *next;
};

()push - הכנסת איבר לראש המחסנית:

void push (struct stack** head, int num)
{
    struct stack* second = *head;
    *head = (struct stack*)malloc(sizeof(struct stack));
    (*head)->num = num;
    (*head)->next = second;
}

stack (מחסנית) הוא מבנה רשימתי כלומר מכיל שדות רגילים בחלקו הראשון וחלקו השני מצביע לאיבר הבא.
הפרמטר של הפונקציה ()push הוא מצביע למצביע (המכיל את הכתובת של ראש המחסנית/רשימה). האיבר הראשון של המחסנית נשמר במשתנה second (כשמו כן הוא - יכיל את האיבר השני של המחסנית), מקצים מקום בזיכרון לראש החדש של המחסנית, מאתחלים את שדהו הפשוט (אם יש מספר כאלה אז דואגים להקנות להם ערכים) ואת שדהו המצביע שיצביע על הראש הקודם של המחסנית (כזכור ערך זה נשמר במשתנה second).
בפעם הראשונה שנכנס לפונקציה, המחסנית ריקה ולכן *head שווה ל null (=second). מקצים מקום בזיכרון לאיבר הראשון של המחסנית, מאתחלים את שדהו הפשוט ואחר כך את שדה המצביע שיצביע ל- null (כי senond = null). בפעם הבאה ניצור שוב איבר ראשון חדש למחסנית והוא יצביע לאיבר הראשון שכעת יצרנו.

()pop - הוצאת איבר מראש המחסנית:

void pop (struct stack** head)
{
    if (*head == NULL)
    {
        printf ("\n can't pop from empty stack\n");
        return;
    }
    else
    {
        struct stack *temp = *head;
        *head = (*head)->next;
        free(temp);
    }
}

הפרמטר של הפונקציה ()push הוא מצביע למצביע (המכיל את הכתובת של ראש המחסנית/רשימה). בודקים אם יש איברים במחסנית (*head מכיל את הכתובת של האיבר הראשון במחסנית) ומסיימים אם המחסנית ריקה. אחרת יש צורך למחוק את האיבר שבראש המחסנית. המחיקה מתבצעת באופן הבא:
המשתנה temp שומר את הכתובת של האיבר הראשון במחסנית. מקדמים את האיברים במחסנית כלומר האיבר הראשון החדש במחסנית יהיה האיבר השני במחסנית הקודמת (לפני שקידמנו איבר) ולבסוף משחררים את הזיכרון של האיבר הראשון הקודם.

כעת נממש את שתי הפונקציות שהוסברו בתוכנית אחת:

דוגמא 1:

#include <stdlib.h>
#include <conio.h>
#include <stdlib.h>

const int MAX = 3;

struct stack
{
    int num;
    struct stack *next;
};

void main()
{
    struct stack* head;
    randomize();

    init_stack (&head);
    build_stack (&head);
    display_stack (head);
    delete_stack (&head);
}

העבר את העכבר מעל הדוגמא כדי לראות הסבר מפורט

תור

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

Last

...

Third

Second

First

הכנסה מהתא הימני ביותר, הוצאה מהתא השמאלי ביותר.
התא השמאלי ביותר הוא ראש התור.
האיבר הראשון שהוכנס לתור הוא יהיה הראשון לצאת (first in first out).

הפעולות:
append - הוספת איבר לתור.
Remove - סילוק איבר מהתור.
init - אתחול התור.

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

דוגמא 2:

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

const int MAX = 5;

struct queue
{
    int num;
    struct queue *next;
};

void init_queue (struct queue** que)
{
    *que = NULL;
}

void append (struct queue** que, int num)
{
    static struct queue* last;
    static struct queue* n_last;

    n_last = (struct queue*)malloc(sizeof(struct queue));
    n_last->num = num;
    n_last->next =NULL;

    if (*que == NULL)
        *que = n_last;
    else
        last->next = n_last;
    last = n_last;
}

void build_queue (struct queue** que)
{
    int i, num;

    printf ("\nThe number by their insertion order are:\n");
    for (i = 0; i < MAX; i++)
    {
        num = random(10);
        append (que, num);
    }
}

void display_queue (struct queue* que)
{
    struct queue* temp = que;

    printf ("\nThe members of the queue are: \n\n");

    while (temp != NULL)
    {
        printf (" %d ", temp->num);
        temp = temp->next;
    }

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

void delete_queue (struct queue** que)
{
    struct queue *temp;

    printf("\n\nDeleting the queue:\n");
    while (*que)
    {
        printf ("%p\t", *que);
        temp = *que;
        *que = (*que)->next;
        free(temp);

    }
}

void main()
{
    struct queue* que;
    randomize();

    init_queue (&que);
    build_queue (&que);
    display_queue (que);
    delete_queue (&que);
}