אלגוריתמים ונתונים (Algorithms and Data Structures) בשפת C

[Tamir]

אלגוריתמים ומבני נתונים (Algorithms and Data Structures) בשפת C


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


1. מערכים (Arrays)


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



c



#include <stdio.h>


int main() {
int arr[5] = {1, 2, 3, 4, 5};


for (int i = 0; i < 5; i++) {
printf("Element at index %d: %d\n", i, arr[i]);
}


return 0;
}



2. רשימות מקושרות (Linked Lists)


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



c



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


// הגדרת מבנה לצומת
struct Node {
int data;
struct Node *next;
};


// פונקציה להדפסת רשימה מקושרת
void printList(struct Node *head) {
struct Node *current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}


int main() {
struct Node *head = NULL;


// יצירת צמתים
struct Node *node1 = (struct Node *)malloc(sizeof(struct Node));
struct Node *node2 = (struct Node *)malloc(sizeof(struct Node));
struct Node *node3 = (struct Node *)malloc(sizeof(struct Node));


node1->data = 10;
node1->next = node2;
node2->data = 20;
node2->next = node3;
node3->data = 30;
node3->next = NULL;


head = node1;


// הדפסת הרשימה
printList(head);


// שחרור זיכרון
free(node1);
free(node2);
free(node3);


return 0;
}



3. ערימות (Stacks)


ערימה היא מבנה נתונים שבו התוספות וההסרות מתבצעות לפי עקרון LIFO (Last In, First Out).



c



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


#define MAX 100


// הגדרת מבנה לערימה
struct Stack {
int top;
int items[MAX];
};


// פונקציה להוספת פריט לערימה
void push(struct Stack *s, int item) {
if (s->top == MAX - 1) {
printf("Stack Overflow\n");
return;
}
s->items[++(s->top)] = item;
}


// פונקציה להסרת פריט מהערימה
int pop(struct Stack *s) {
if (s->top == -1) {
printf("Stack Underflow\n");
return -1;
}
return s->items[(s->top)--];
}


// פונקציה לבדוק אם הערימה ריקה
int isEmpty(struct Stack *s) {
return s->top == -1;
}


int main() {
struct Stack s;
s.top = -1;


push(&s, 10);
push(&s, 20);
push(&s, 30);


while (!isEmpty(&s)) {
printf("%d\n", pop(&s));
}


return 0;
}



4. תורים (Queues)


תור הוא מבנה נתונים שבו התוספות מתבצעות בצד אחד וההסרות בצד השני, לפי עקרון FIFO (First In, First Out).



c



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


#define MAX 100


// הגדרת מבנה לתור
struct Queue {
int front, rear, size;
int items[MAX];
};


// פונקציה להוספת פריט לתור
void enqueue(struct Queue *q, int item) {
if (q->size == MAX) {
printf("Queue Overflow\n");
return;
}
q->items[q->rear] = item;
q->rear = (q->rear + 1) % MAX;
q->size++;
}


// פונקציה להסרת פריט מהתור
int dequeue(struct Queue *q) {
if (q->size == 0) {
printf("Queue Underflow\n");
return -1;
}
int item = q->items[q->front];
q->front = (q->front + 1) % MAX;
q->size--;
return item;
}


// פונקציה לבדוק אם התור ריק
int isEmpty(struct Queue *q) {
return q->size == 0;
}


int main() {
struct Queue q;
q.front = 0;
q.rear = 0;
q.size = 0;


enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);


while (!isEmpty(&q)) {
printf("%d\n", dequeue(&q));
}


return 0;
}

[Tamir]

5. מיון (Sorting) חיפוש (Searching)


מיון הוא תהליך של סידור רשימה לפי סדר מסוים, וחיפוש הוא תהליך מציאת אלמנט ברשימה.


מיון במהירות (Quick Sort):



c



#include <stdio.h>


// פונקציה להחלפת ערכים
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}


// פונקציה לפיצול
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;


for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}


// פונקציה למיון מהיר
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}


int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);


quickSort(arr, 0, n - 1);


for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");


return 0;
}



חיפוש בינארי (Binary Search):



c



#include <stdio.h>


// פונקציה לחיפוש בינארי
int binarySearch(int arr[], int size, int target) {
int left = 0;
int right = size - 1;


while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}


int main() {
int arr[] = {2, 3, 4, 10, 40};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 10;
int result = binarySearch(arr, size, target);


if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found\n");
}


return 0;
}



סיכום


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


אם יש לכם שאלות נוספות או אתם זקוקים לעזרה נוספת, אתם מוזמנים לשאול!