编程范式：通用的二分查找

桃扇骨 2022-05-25 07:25 165阅读 0赞

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    void *binary_search (void *arr, void *value, int len, int mem, int(*compare)(void *, void *)) {
    	int low = 0;
    	int high = len-1;
    	int mid;
    	while(low <= high) {
    		mid = (low + high) / 2;
    		void* addr = (char*)arr + mid * mem;
    		if (compare(addr, value) == 0) {
    			return addr;
    		}
    		else if (compare(addr, value) > 0) {
    			high = mid - 1;
    		}
    		else {
    			low = mid + 1;
    		}
    	}
    	return NULL;
    }
    
    int cmp_int (void* x, void* y) {
    	int *a = (int*)x;
    	int *b = (int*)y;
    	return *a - *b;
    }
    
    int cmp_string (void* x, void* y) {
    	char *a = *(char**)x;
    	char *b = *(char**)y;
    	return strcmp(a, b);
    }
    
    
    int main (int argc, char **argv) {
    
    	//查找整数
    	int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    	int num = 10;
    	int value = 10;
    	void* ret = binary_search(arr, &value, num, sizeof(int), cmp_int);
    	if (ret == NULL) {
    		printf("NULL\n");
    	}
    	else {
    		printf("%d\n", *((int*)ret));
    	}
    
    
    	//查找字符串
    	char* books[] = {"水浒传", "三国演义", "西游记", "红楼梦"};
    	char* book = "三国演义";
    	int len = 4;
    	void* retStr = binary_search(books, &book, 4, sizeof(char *), cmp_string);
    	if (retStr == NULL) {
    		printf("NULL\n");
    	}
    	else {
    		printf("%s\n", *((char**)retStr));
    	}
    
    	return 0;
    }

通用线性查找：

#include <stdio.h>
    #include <stdlib.h>
    #include <memory.h>
    #include <string.h>
    
    void *search (void *a, void *value, int len, int size, int(*cmp)(void*, void*)) {
        for (int i = 0; i < len; i++) {
            void *addr = (char *)a + i * size;
            if (cmp(addr, value) == 0) {
                return addr;
            }
        }
        return NULL;
    }
    
    int cmp_int(void *x, void *y) {
        return *(int *)x - *(int *)y;
    }
    
    int cmp_str(void *x, void *y) {
        return strcmp(*(char **)x, *(char **)y);
    }
    
    int main (int argc, char **argv) {
        char *books[] = {"水浒传", "三国演义", "西游记", "红楼梦"};
        char *book = "西游记";
        void *ret_str = search(books, &book, 4, sizeof(char *), cmp_str);
        printf("%s\n", *(char **)ret_str);
        int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int len = 10;
        int value = 5;
        void *ret_int = search(a, &value, len, sizeof(int), cmp_int);
        printf("%d\n", *(int *)ret_int);
        return 0;
    }

通用交换函数：

#include <stdio.h>
    #include <memory.h>
    
    void swap (void *a, void *b, int size) {
        char tmp[size];
        memcpy(tmp, a, size);
        memcpy(a, b, size);
        memcpy(b, tmp, size);
    }
    
    int main (int argc, char **argv) {
        int x = 36, y = 72;
        swap(&x, &y, sizeof(int));
        printf("%d %d\n", x, y);
    
        double p = 3.1415926, e = 2.7182818;
        swap(&p, &e, sizeof(double));
        printf("%lf %lf\n", p, e);
    
        char *s1 = strdup("倚天剑");
        char *s2 = strdup("屠龙刀");
        swap(&s1, &s2, sizeof(char *));
        printf("%s %s", s1, s2);
        return 0;
    }

通用栈：

#include <stdio.h>
    #include <stdlib.h>
    #include <memory.h>
    #include <string.h>
    
    typedef struct {
        int *elem;
        int len;//栈中元素的个数
        int volume;
        int size;
    } stack;
    
    void init (stack *s, int size) {
        s->len = 0;
        s->volume = 3;
        s->size = size;
        s->elem = malloc(s->volume * s->size);
    }
    
    void push (stack *s, void *value) {
        if (s->len == s->volume) {
            s->volume *= 2;
            s->elem = realloc(s->elem, s->volume * s->size);
        }
        void *addr = (char *)s->elem + s->len * s->size;
        memcpy(addr, value, s->size);
        s->len++;
    }
    
    void pop (stack *s, void *value) {
        void *addr = (char *)s->elem + (s->len - 1) * s->size;
        memcpy(value, addr, s->size);
        s->len--;
    }
    
    int main (int argc, char **argv) {
        int cards[5] = {3, 7, 1, 2, 4};
        stack s;
        init (&s, sizeof(int));
        for (int i = 0; i < 5; i++) {
            push(&s, &cards[i]);
        }
        for (int i = 0; i < 5; i++) {
            pop(&s, &cards[i]);
        }
        for (int i = 0; i < 5; i++) {
            printf("%d\n", cards[i]);
        }
    
        char *books[4] = {"西游记", "三国演义", "水浒传", "红楼梦"};
        stack st;
        init(&st, sizeof(char *));
        for (int i = 0; i < 4; i++) {
            char *book = strdup(books[i]);
            push(&st, &book);
        }
        char *name;
        for (int i = 0; i < 4; i++) {
            pop(&st, &name);
            printf("%s\n", name);
            free(name);
        }
    }