读书人
栏目▼

谋略模式C语言实现

发布时间： 2013-03-10 09:38:39 作者： rapoo

策略模式C语言实现

【说明】策略模式的C语言实现，实现了3种排序算法的灵活切换。

【代码清单】

typedef.h

/*Author : tandesirTime : 2013-03-09借鉴Li XianJing部分代码, 感谢  Li XianJing <xianjimli@hotmail.com>欢迎访问 http://blog.csdn.net/tandesir*/#ifndef __TYPEDEF_H__#define __TYPEDEF_H__#include <stdio.h>enum {RET_OK,RET_FAIL};#ifdef __cplusplus#define DECLS_BEGIN extern "C" {#define DECLS_END }#else#define DECLS_BEGIN #define DECLS_END #endif/* __cplusplus */#define DEBUG_PRINT(FORMAT, VALUE) printf("File %s line %d: "\#VALUE " = " FORMAT "\n"\,__FILE__, __LINE__,VALUE\);#define LENGTH(array) (sizeof(array)/sizeof(array[0])) #define return_if_fail(p) if(!(p)) \{printf("%s : %d Warning : "#p" failed.\n",\__func__, __LINE__); return ;}#define return_val_if_fail(p, ret) if(!(p))\{printf("%s : %d Warning : "#p" failed.\n",\__func__, __LINE__); return (ret);}#define SAFE_FREE(p) if(p != NULL){free(p); p = NULL;}#endif/*__TYPEDEF_H__*/


sort.h

#ifndef __SORT_H__#define __SORT_H__#include "typedef.h"#include "cmp.h"DECLS_BEGIN struct _Sort;typedef struct _Sort Sort;struct _Sort{int (*sort)(int arr[], size_t count, DataCompare cmp);void (*destroy)(void *thiz);};static inline int sort(Sort *thiz, DataCompare cmp, int arr[], size_t count){return_val_if_fail(thiz != NULL, RET_FAIL);if(thiz->sort != NULL){return thiz->sort(arr, count, cmp);}return RET_OK;}static inline void sorter_destroy(Sort *thiz){return_if_fail(thiz != NULL);if(thiz->destroy != NULL){return thiz->destroy(thiz);}}DECLS_END#endif


bubble_sort.h

/*Author : tandesirTime : 2013-03-09借鉴Li XianJing部分代码, 感谢  Li XianJing <xianjimli@hotmail.com>欢迎访问 http://blog.csdn.net/tandesir*/#ifndef __BUBBLE_SORT_H__#define __BUBBLE_SORT_H__#include "typedef.h"#include "sort.h"#include "cmp.h"DECLS_BEGIN struct _Bubble;typedef struct _Bubble Bubble;typedef int (*BubbleSort)(int arr[], size_t count, DataCompare cmp);struct _Bubble{Sort sorter;};Bubble *BubbleSortCreate(void);DECLS_END#endif


bubble_sort.c

/*Author : tandesirTime : 2013-03-09借鉴Li XianJing部分代码, 感谢  Li XianJing <xianjimli@hotmail.com>欢迎访问 http://blog.csdn.net/tandesir*/#include <stdio.h>#include <stdlib.h>#include <assert.h>#include "typedef.h"#include "bubble_sort.h"#include "cmp.h"/*  冒泡排序(1) i∈[N-1,0)               //循环N-1遍   j∈[N-1,N-i-1)         //每遍循环要处理的无序部分     swap(j,j-1)         //两两排序(升序/降序)*/static int bubble_sort(int arr[], size_t count, DataCompare cmp){size_t i, j;int temp;if(count < 2){return RET_OK;}for(i = count - 1; i > 0; i--){for(j = count - 1; j > count - 1 - i; j--){if(cmp(arr[j-1], arr[j]) > 0){   temp = arr[j];arr[j] = arr[j-1];arr[j-1] = temp;}}}return RET_OK;}static void bubble_destroy(void *thiz){if(thiz != NULL){SAFE_FREE(thiz);}}Bubble *BubbleSortCreate(void){Bubble *thiz = malloc(sizeof(Bubble));if(thiz != NULL){thiz->sorter.sort = bubble_sort;thiz->sorter.destroy = bubble_destroy;}#ifdef DEBUGprintf("construct bubble\n");#endifreturn thiz;}


merge_sort.h

/*Author : tandesirTime : 2013-03-09借鉴Li XianJing部分代码, 感谢  Li XianJing <xianjimli@hotmail.com>欢迎访问 http://blog.csdn.net/tandesir*/#ifndef __MERGE_SORT_H__#define __MERGE_SORT_H__#include "sort.h"#include "cmp.h"DECLS_BEGIN struct _Merge;typedef struct _Merge Merge;typedef int (*MergeSort)(int storage[], int arr[], size_t low, size_t mid, size_t high, DataCompare cmp);struct _Merge{Sort sorter;};Merge *MergeSortCreate(void);DECLS_END#endif


merge_sort.c

/*Author : tandesirTime : 2013-03-09借鉴Li XianJing部分代码, 感谢  Li XianJing <xianjimli@hotmail.com>欢迎访问 http://blog.csdn.net/tandesir*/#include <stdio.h>#include <stdlib.h>#include <assert.h>#include "typedef.h"#include "merge_sort.h"#include "cmp.h"#ifdef DEBUGstatic int i = 0;#endif/*  归并排序(1) 递归*/static int merge_sort_impl(int storage[], int arr[], size_t low, size_t mid, size_t high, DataCompare cmp){size_t i = low;size_t j = low;size_t k = mid;if((low + 1) < mid){size_t x = low + ((mid - low) >> 1);merge_sort_impl(storage, arr, low, x, mid, cmp);}if((mid + 1) < high){size_t x = mid + ((high - mid) >> 1);merge_sort_impl(storage, arr, mid, x, high, cmp);}while(j < mid && k < high){if(cmp(arr[j], arr[k]) <= 0){storage[i++] = arr[j++];}else{storage[i++] = arr[k++];}}while(j < mid){storage[i++] = arr[j++];}while(k < high){storage[i++] = arr[k++];}for(i = low; i < high; i++){arr[i] = storage[i];}#ifdef DEBUGprintf("depth:%d\n", i++);#endifreturn RET_OK;}static int merge_sort(int arr[], size_t count, DataCompare cmp){#ifdef DEBUGDEBUG_PRINT("%d", count);#endifreturn_val_if_fail(cmp != NULL, RET_FAIL);int storage[count];if(count > 1){merge_sort_impl(storage, arr, 0, count>>1, count, cmp);}#ifdef DEBUGi = 0;#endifreturn RET_OK;}static void merge_destroy(void *thiz){if(thiz != NULL){SAFE_FREE(thiz);}}Merge *MergeSortCreate(void){Merge *thiz = malloc(sizeof(Merge));if(thiz != NULL){thiz->sorter.sort = merge_sort;thiz->sorter.destroy = merge_destroy;}#ifdef DEBUGprintf("construct merge\n");#endifreturn thiz;}


quick_sort.h

/*Author : tandesirTime : 2013-03-09借鉴Li XianJing部分代码, 感谢  Li XianJing <xianjimli@hotmail.com>欢迎访问 http://blog.csdn.net/tandesir*/#ifndef __QUICK_SORT_H__#define __QUICK_SORT_H__#include "typedef.h"#include "sort.h"#include "cmp.h"DECLS_BEGIN struct _Quick;typedef struct _Quick Quick;typedef int (*QuickSort)( int arr[], size_t left, size_t right, DataCompare cmp);struct _Quick{Sort sorter;};Quick *QuickSortCreate(void);DECLS_END#endif


quick_sort.c

/*Author : tandesirTime : 2013-03-09借鉴Li XianJing部分代码, 感谢  Li XianJing <xianjimli@hotmail.com>欢迎访问 http://blog.csdn.net/tandesir*/#include <stdio.h>#include <stdlib.h>#include <assert.h>#include "typedef.h"#include "quick_sort.h"#include "cmp.h"#ifdef DEBUGstatic int i = 0;#endif/*  快速排序(1)*/static int quick_sort_impl(int arr[], size_t left, size_t right, DataCompare cmp){size_t save_left = left;size_t save_right = right;int x = arr[left];while(left < right){while(cmp(arr[right], x) >= 0 && left < right) right--;if(left != right){arr[left] = arr[right];left++;}while(cmp(arr[left], x) <= 0 && left < right) left++;if(left != right){arr[right] = arr[left];right--; }}arr[left] = x;if(save_left < left){quick_sort_impl(arr, save_left, left-1, cmp);}if(save_right > left){quick_sort_impl(arr, left+1, save_right, cmp);}#ifdef DEBUGprintf("depth:%d\n", i++);#endifreturn RET_OK;}static int quick_sort(int arr[], size_t count, DataCompare cmp){#ifdef DEBUGDEBUG_PRINT("%d", count);#endifreturn_val_if_fail(cmp != NULL, RET_FAIL);if(count > 1){quick_sort_impl(arr, 0, count-1, cmp);}#ifdef DEBUGi = 0;#endifreturn RET_OK;}static void quick_destroy(void *thiz){if(thiz != NULL){SAFE_FREE(thiz);}}Quick *QuickSortCreate(void){Quick *thiz = malloc(sizeof(Quick));if(thiz != NULL){thiz->sorter.sort = quick_sort;thiz->sorter.destroy = quick_destroy;}#ifdef DEBUGprintf("construct quick\n");#endifreturn thiz;}


cmp.h

#ifndef __CMP_H__#define __CMP_H__#include "typedef.h"DECLS_BEGIN typedef int (*DataCompare)(int a, int b);int cmp_int(int a, int b);int cmp_int_invert(int a, int b);DECLS_END#endif


cmp.c

#include "cmp.h"int cmp_int(int a, int b){return a - b;}int cmp_int_invert(int a, int b){return b - a;}


test.c

/*Author : tandesirTime : 2013-03-09借鉴Li XianJing部分代码, 感谢  Li XianJing <xianjimli@hotmail.com>欢迎访问 http://blog.csdn.net/tandesir*/#include <stdio.h>#include <stdlib.h>#include <assert.h>#include "bubble_sort.h"#include "quick_sort.h"#include "merge_sort.h"#include "sort.h"#include "cmp.h"int main(int arc, char* const argv[]){size_t i = 0, n = 0;int arr1[] = {5, 4, 1, 3, 6, 10, 9, 8, 7, 2, 2};//-1-n = LENGTH(arr1);#ifdef DEBUGDEBUG_PRINT("%d", n);#endifprintf("Before sort:\n");for(i = 0; i < n; i++)printf("%4d", arr1[i]);printf("\nAfter sort:\n");sort((Sort *)QuickSortCreate(), cmp_int_invert, arr1, n);for(i = 0; i < n; i++)printf("%4d", arr1[i]);printf("\n");return 0;}


Makefile

src = typedef.h sort.h bubble_sort.h bubble_sort.c merge_sort.h merge_sort.c quick_sort.h quick_sort.c cmp.h cmp.c test.ctarget = testtemp = $(wildcard *~ test)flags = -DDEBUGall:$(src)gcc -g $^ -o $(target)clean:rm $(temp)

【源码下载】

*欢迎纠错，共同进步！

转载请标明出处，仅供学习交流，勿用于商业目的

Copyright @ http://blog.csdn.net/tandesir


读书人网 >C语言

热点推荐

触屏版 | 电脑版

读书人网 m.reader8.net