# NCKU CSIE PD1 Week15
👉[English](https://hackmd.io/@zhu424/NCKU-CSIE-PD1-2023-week-15-English)
> 如果已經知道 **Generic Programming** 是什麼
> 可以直接跳到 [Lab](#Lab)
## 如果我們要寫一個交換兩個變數的 function ...
對於 `int` 來說，我們可以這樣寫
```c
void my_swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
int main() {
int a = 1, b = 2;
my_swap(&a, &b);
printf("%d %d\n", a, b);
return 0;
}
```
對於 `float` 來說，我們可以這樣寫
```c
void my_swap(float *a, float *b) {
float tmp = *a;
*a = *b;
*b = tmp;
}
```
那如果我們想要交換的是這些型態呢？
- `long long`
- `unsigned int`
- `char`
- `char *`
- ```c
struct student {
char name[20];
int age;
};
```
- ```c
struct Node {
int data;
struct Node *next;
};
```
我們需要對每個型態都寫一個 `my_swap` function 嗎？
```c
void my_swap(long long *a, long long *b);
void my_swap(unsigned int *a, unsigned int *b);
void my_swap(char *a, char *b);
void my_swap(char **a, char **b);
void my_swap(struct student *a, struct student *b);
void my_swap(struct Node *a, struct Node *b);
// ...
// Implementations
void my_swap(long long *a, long long *b) {
long long tmp = *a;
*a = *b;
*b = tmp;
}
// ...
```
## Generic Programming
**Generic** (泛型) 是一種程式設計的技巧
可以讓程式碼更加的彈性、減少重複的程式碼
在 C 語言中
我們可以使用 `void *` 來實現泛型
在寫 Generic function 前
我們先來複習一下 `void *` 的特性
## `void *` 的特性
- `void *` 是一種特殊的 pointer
可以指向任何型態的資料
```c
int a = 1;
float b = 2.0;
char c = '3';
void *ptr;
ptr = &a;
printf("%d\n", *(int *)ptr);
ptr = &b;
printf("%f\n", *(float *)ptr);
ptr = &c;
printf("%c\n", *(char *)ptr);
```
- `void *` 不能直接 dereference
必須先轉型成正確的型態
```c
int a = 1;
void *ptr = &a;
printf("%d\n", *ptr); // Error
printf("%d\n", *(int *)ptr); // Correct
```
## 我們有用過 Generic Function 嗎？
在不知不覺中，我們已經用過很多 Generic Function 了
```c
#include <stdlib.h> // need include <-
int cmp(const void *a, const void *b){
return *(int *)a - *(int *)b;
}
int main() {
int arr[10] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
qsort(arr, 10, sizeof(int), cmp);
for (int i = 0; i < 10; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
<br>
其實 **`qsort`** 本身就是一個 Generic Function !
我們來看一下 `qsort` 的 declaration
<br>
```c
void qsort( void *ptr, size_t count, size_t size,
int (*comp)(const void *, const void *) );
```
> [c reference : qsort](https://en.cppreference.com/w/c/algorithm/qsort)
陣列傳入時，會被轉型成 `void *`
- 以 `count` 作為陣列的長度
- 以 `size` 來切割陣列 ( 這邊的 `size` 代表每個元素是多少 bytes )
- 以 `comp` 來決定排序的方式 ( 這邊的 `comp` 是一個 function pointer )
## Generic Function 實作
由 `qsort` 觀察
可以看到 Generic Function 有幾個特性
- `void *` 型態傳入
- 以 `size` 來切割資料
- 以 function pointer 來決定操作
## Generic Swap
那我們可以嘗試實作一個 Generic Swap
> **Hint** :
- `void *` 型態傳入
- 以 `size` 來切割資料
```c
void my_swap(void *a, void *b, size_t size) {
void *tmp = malloc(size);
memcpy(tmp, a, size);
memcpy(a, b, size);
memcpy(b, tmp, size);
free(tmp);
}
```
> [c reference : memcpy](https://en.cppreference.com/w/c/string/byte/memcpy) ( 需要 `#include <string.h>` )
也可以用 `strcpy` 來實作
```c
void my_swap(void *a, void *b, size_t size) {
char *tmp = malloc(size);
strcpy(tmp, a);
strcpy(a, b);
strcpy(b, tmp);
free(tmp);
}
```
或是用 for loop 來實作
```c
void my_swap(void *a, void *b, size_t size) {
char *tmp = malloc(size);
for(int i = 0; i < size; i++){
*((char *)tmp + i) = *((char *)a + i);
*((char *)a + i) = *((char *)b + i);
*((char *)b + i) = *((char *)tmp + i);
}
free(tmp);
}
```
> 因為 `char` 的大小是 1 byte
> 所以我們可以用 loop ㄧ個一個 byte 來交換
## Lab
請實作一個 **Generic Bubble Sort**
並將 :
- `student` 依照 `id` 由小到大排序
```c
struct student {
char name[20];
int id;
int age;
};
```
- `point` 依照 `x` 由小到大排序
```c
struct point {
float x;
float y;
};
```
<br>
**TODO** :
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct student {
char name[20];
int id;
int age;
} student;
typedef struct point {
float x;
float y;
} point;
void swap(void *a, void *b, size_t size) {
// TODO
}
void bubble_sort(void *ptr, size_t count, size_t size,
int (*comp)(const void *, const void *)) {
// TODO
}
int cmp_student(/* TODO */) {
// TODO
}
int cmp_point(/* TODO */) {
// TODO
}
int main(){
student students[10] = {
{"Henry", 8, 25},
{"Alice", 1, 18},
{"David", 4, 21},
{"Eason", 5, 22},
{"Jason", 10, 27},
{"Bob", 2, 19},
{"Frank", 6, 23},
{"Cindy", 3, 20},
{"Iris", 9, 26},
{"Gina", 7, 24}
};
point points[10] = {
{19.0, 20.0},
{1.0, 2.0},
{5.0, 6.0},
{3.0, 4.0},
{13.0, 14.0},
{9.0, 10.0},
{15.0, 16.0},
{11.0, 12.0},
{17.0, 18.0},
{7.0, 8.0}
};
bubble_sort(students,/* TODO */);
bubble_sort(points,/* TODO */);
for (int i = 0; i < 10; i++) {
printf("student(name=%s,id=%d,age=%d)\n", students[i].name, students[i].id, students[i].age);
}
printf("====================================\n");
for (int i = 0; i < 10; i++) {
printf("point(x=%f,y=%f)\n", points[i].x, points[i].y);
}
return 0;
}
```
> **Hint** : int 的 bubble sort 如下
```c
void bubble_sort_int(int *arr, int n) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
}
```
ans : https://gist.github.com/jason810496/073978e521feb5cdab41ec81fe56ae6b
結果應該要是這樣 :
```
student(name=Alice,id=1,age=18)
student(name=Bob,id=2,age=19)
student(name=Cindy,id=3,age=20)
student(name=David,id=4,age=21)
student(name=Eason,id=5,age=22)
student(name=Frank,id=6,age=23)
student(name=Gina,id=7,age=24)
student(name=Henry,id=8,age=25)
student(name=Iris,id=9,age=26)
student(name=Jason,id=10,age=27)
====================================
point(x=1.000000,y=2.000000)
point(x=3.000000,y=4.000000)
point(x=5.000000,y=6.000000)
point(x=7.000000,y=8.000000)
point(x=9.000000,y=10.000000)
point(x=11.000000,y=12.000000)
point(x=13.000000,y=14.000000)
point(x=15.000000,y=16.000000)
point(x=17.000000,y=18.000000)
point(x=19.000000,y=20.000000)
```
## 我們知道 Generic Programming 可以做什麼 ？
如 `qsort` 這種演算法可以寫成 Generic Function 來重複使用 <br>
又或是接下來會學到的 `linked list` 也可以寫成 Generic Type 來重複利用 <br>
<br>
:::spoiler Generic Linked List
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Define the student structure
typedef struct student {
char name[20];
int id;
int age;
} student;
// Define the node structure for the linked list
typedef struct Node {
void *data;
struct Node *next;
} Node;
// Function to create a new node with data
Node *createNode(void *data) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
perror("Memory allocation error");
exit(EXIT_FAILURE);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to insert a new node at the beginning of the linked list
Node *insertNodeAtBeginning(Node *head, void *data) {
Node *newNode = createNode(data);
newNode->next = head;
return newNode;
}
// Function to print a student's information
void printStudent(const void *data) {
const student *s = (const student *)data;
printf("ID: %d, Name: %s, Age: %d\n", s->id, s->name, s->age);
}
// Function to print the linked list
void printList(Node *head, void (*print)(const void *)) {
Node *current = head;
while (current != NULL) {
print(current->data);
current = current->next;
}
}
// Function to free the linked list
void freeList(Node *head) {
Node *current = head;
while (current != NULL) {
Node *next = current->next;
free(current->data);
free(current);
current = next;
}
}
int main() {
// Example usage with the student structure
Node *head = NULL;
// Create and insert student nodes
student *s1 = (student *)malloc(sizeof(student));
strcpy(s1->name, "Alice");
s1->id = 1;
s1->age = 20;
head = insertNodeAtBeginning(head, s1);
student *s2 = (student *)malloc(sizeof(student));
strcpy(s2->name, "Bob");
s2->id = 2;
s2->age = 22;
head = insertNodeAtBeginning(head, s2);
student *s3 = (student *)malloc(sizeof(student));
strcpy(s3->name, "Charlie");
s3->id = 3;
s3->age = 21;
head = insertNodeAtBeginning(head, s3);
// Print the linked list
printf("Linked List of Students:\n");
printList(head, printStudent);
// Clean up the linked list
freeList(head);
return 0;
}
```
:::
<br>
又或是更複雜的資料結構，如 `AVL Tree` 也可以寫成 Generic Type 來重複利用 <br>
:::spoiler Generic AVL Tree
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct AVLNode {
void *data;
struct AVLNode *left;
struct AVLNode *right;
int height;
} AVLNode;
// Function pointer type for data comparison
typedef int (*CompareFunction)(const void *, const void *);
// Function pointer type for data printing
typedef void (*PrintFunction)(const void *);
// Function to get the height of a node
int getHeight(AVLNode *node) {
return (node == NULL) ? 0 : node->height;
}
// Function to update the height of a node
void updateHeight(AVLNode *node) {
if (node != NULL) {
int leftHeight = getHeight(node->left);
int rightHeight = getHeight(node->right);
node->height = 1 + ((leftHeight > rightHeight) ? leftHeight : rightHeight);
}
}
// Function to get the balance factor of a node
int getBalanceFactor(AVLNode *node) {
return (node == NULL) ? 0 : getHeight(node->left) - getHeight(node->right);
}
// Right rotate a subtree rooted with y
AVLNode *rightRotate(AVLNode *y) {
AVLNode *x = y->left;
AVLNode *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
updateHeight(y);
updateHeight(x);
// Return new root
return x;
}
// Left rotate a subtree rooted with x
AVLNode *leftRotate(AVLNode *x) {
AVLNode *y = x->right;
AVLNode *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
updateHeight(x);
updateHeight(y);
// Return new root
return y;
}
// Balance the AVL tree after an insertion or deletion
AVLNode *balanceNode(AVLNode *node) {
// Update height of the current node
updateHeight(node);
// Get the balance factor of this node
int balance = getBalanceFactor(node);
// Left Heavy (Left-Left Case)
if (balance > 1 && getBalanceFactor(node->left) >= 0) {
return rightRotate(node);
}
// Left Heavy (Left-Right Case)
if (balance > 1 && getBalanceFactor(node->left) < 0) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Heavy (Right-Right Case)
if (balance < -1 && getBalanceFactor(node->right) <= 0) {
return leftRotate(node);
}
// Right Heavy (Right-Left Case)
if (balance < -1 && getBalanceFactor(node->right) > 0) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
// No rotation needed
return node;
}
// Insert a node into the AVL tree
AVLNode *insertNode(AVLNode *node, void *data, CompareFunction compare) {
// Standard BST insertion
if (node == NULL) {
AVLNode *newNode = (AVLNode *)malloc(sizeof(AVLNode));
newNode->data = data;
newNode->left = newNode->right = NULL;
newNode->height = 1;
return newNode;
}
// Perform standard BST insert
int cmpResult = compare(data, node->data);
if (cmpResult < 0) {
node->left = insertNode(node->left, data, compare);
} else if (cmpResult > 0) {
node->right = insertNode(node->right, data, compare);
} else {
// Duplicate data is not allowed
return node;
}
// Update height of the current node
updateHeight(node);
// Balance the tree
return balanceNode(node);
}
// Find target node in the AVL tree
AVLNode *findNode(AVLNode *node, void *target, CompareFunction compare) {
if (node == NULL) {
return NULL;
}
int cmpResult = compare(target, node->data);
if (cmpResult < 0) {
return findNode(node->left, target, compare);
} else if (cmpResult > 0) {
return findNode(node->right, target, compare);
} else {
return node;
}
}
// Function to free the AVL tree nodes
void freeAVLTree(AVLNode *root) {
if (root != NULL) {
freeAVLTree(root->left);
freeAVLTree(root->right);
free(root);
}
}
typedef struct student {
char name[20];
int id;
int age;
} student;
// Compare function for student
int compareStudent(const void *a, const void *b) {
return ((student *)a)->id - ((student *)b)->id;
}
// Compare function for finding student
int compareStudentId(const void *target_id, const void *p) {
return *((int *)target_id) - ((student *)p)->id;
}
// Print function for student
void printStudent(const void *data) {
student *s = (student *)data;
printf("Name: %s, ID: %d, Age: %d\n", s->name, s->id, s->age);
}
// Print AVL tree in-order
void printAVLTree(AVLNode *root, PrintFunction print) {
if (root != NULL) {
printAVLTree(root->left, print);
print(root->data);
printAVLTree(root->right, print);
}
}
int main() {
AVLNode *root = NULL;
student students[10] = {
{"Henry", 8, 25},
{"Alice", 1, 18},
{"David", 4, 21},
{"Eason", 5, 22},
{"Jason", 10, 27},
{"Bob", 2, 19},
{"Frank", 6, 23},
{"Cindy", 3, 20},
{"Iris", 9, 26},
{"Gina", 7, 24}
};
// Insert 10 students into the AVL tree
for (int i = 0; i < 10; i++) {
printf("Inserting student %d %s\n", students[i].id, students[i].name);
root = insertNode(root, &students[i], (CompareFunction)compareStudent);
}
// Print the AVL tree in-order
printf("Printing AVL tree in-order:\n");
printAVLTree(root, (PrintFunction)printStudent);
// Check student id = 5
printf("Checking student id = 5\n");
int target_id = 5;
AVLNode* result = (AVLNode *)findNode(root, &target_id, (CompareFunction)compareStudentId);
if (result == NULL) {
printf("Student not found\n");
} else {
printStudent(result->data);
}
// Check student id = 99
printf("Checking student id = 99\n");
target_id = 99;
result = (AVLNode *)findNode(root, &target_id, (CompareFunction)compareStudentId);
if (result == NULL) {
printf("Student not found\n");
} else {
printStudent(result->data);
}
// Clean up
freeAVLTree(root);
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet