אלגוריתמים ונתונים (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");
}


// פונקציה להוספת צומת בתחילת הרשימה
void insertAtHead(struct Node **head, int data) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = *head;
*head = newNode;
}


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


insertAtHead(&head, 10);
insertAtHead(&head, 20);
insertAtHead(&head, 30);


printList(head);


// שחרור זיכרון
struct Node *temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}


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



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



6. אלגוריתם דינמי (Dynamic Programming)


בעיה קלאסית של תת-בעיות (Fibonacci Sequence):



c
#include <stdio.h>


// פונקציה לחישוב מספר פיבונאצ'י בעזרת תכנות דינמי
int fibonacci(int n) {
int fib[n+1];
fib[0] = 0;
fib[1] = 1;


for (int i = 2; i <= n; i++) {
fib[i] = fib[i-1] + fib[i-2];
}
return fib[n];
}


int main() {
int n = 10;
printf("Fibonacci of %d is %d\n", n, fibonacci(n));
return 0;
}



סיכום


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


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