一步一步写算法（之通用数据结构）

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】

    上一篇博客介绍了通用算法，那么有了这个基础我们可以继续分析通用数据结构了。我们知道在c++里面，既有数据又有函数，所以一个class就能干很多事情。举一个简单的例子来说，我们可以编写一个数据的class计算类。

view plaincopy to clipboardprint?class calculate{ 

    int m; 

    int n; 

public: 

    calculate():m(0),n(0) {} 

    calculate(int a, int b):m(a),n(b) {} 

    ~calculate() {} 

    int add() { return m+n; } 

    int sub() { return m-n; } 

    int mul() { return m *n;} 

    int div() { return (n!=0) ?m /n : -1;} 

}; 

class calculate{

       int m;

       int n;

public:

       calculate():m(0),n(0) {}

       calculate(int a, int b):m(a),n(b) {}

       ~calculate() {}

       int add() { return m+n; }

       int sub() { return m-n; }

       int mul() { return m *n;}

       int div() { return (n!=0) ?m /n : -1;}

};    那么我们可不可以仿造这个思路，在常用的数据结构里面添加一些函数指针呢？至于为什么要这些函数指针，主要是因为我们设计的数据结构是通用的数据类型，那么其中必然有一些譬如compare的函数需要具体数据类型的参与。现在，我们定义一个循环队列，

view plaincopy to clipboardprint?typedef struct _QUEUE 

{ 

    int start; 

    int end; 

    int length; 

    int count; 

    void** head; 

    int (*compare)(void*, void*); 

    void (*print)(void*); 

    void* (*find)(void*, void*); 

}QUEUE; 

typedef struct _QUEUE

{

       int start;

       int end;

       int length;

       int count;

       void** head;

       int (*compare)(void*, void*);

       void (*print)(void*);

       void* (*find)(void*, void*);

}QUEUE;    那么QUEUE的创建函数、打印函数有什么区别吗？

view plaincopy to clipboardprint?QUEUE* create_new_queue(int length) 

{ 

    QUEUE* pQueue; 

    if(0 == length) 

        return NULL; 

    pQueue = (QUEUE*)malloc(sizeof(QUEUE)); 

    assert(NULL != pQueue); 

    pQueue->head = (void**)malloc(sizeof(void*)* length); 

    assert(NULL != pQueue->head); 

    pQueue->start = 0; 

    pQueue->end = 0; 

    pQueue->count = 0; 

    pQueue->length = length; 

    pQueue->compare = compare; 

    pQueue->find = find; 

    pQueue->print = print; 

    return pQueue; 

} 

QUEUE* create_new_queue(int length)

{

       QUEUE* pQueue;

       if(0 == length)

              return NULL;

       pQueue = (QUEUE*)malloc(sizeof(QUEUE));

       assert(NULL != pQueue);

       pQueue->head = (void**)malloc(sizeof(void*)* length);

       assert(NULL != pQueue->head);

       pQueue->start = 0;

       pQueue->end = 0;

       pQueue->count = 0;

       pQueue->length = length;

       pQueue->compare = compare;

       pQueue->find = find;

       pQueue->print = print;

       return pQueue;

}

    有了函数指针之后，整个数据结构显得有点复杂。但是我们没有办法，这是设计通用数据结构必须花的一个代价。那么有了这个数据结构之后，如何才能实现对整个队列的数据打印呢？朋友们可以自己写一下，再看看我写的是否正确。

view plaincopy to clipboardprint?void print_value_in_queue(QUEUE* pQueue) 

{ 

    int index ; 

    int end; 

    if(NULL == pQueue || 0 == pQueue->count) 

        return; 

    end = pQueue->start; 

    if(end < pQueue->end) 

        end = pQueue->end + pQueue->length; 

    for(index = pQueue->start; index < end; index ++){ 

        pQueue->print(pQueue->head[index % pQueue->length]); 

    } 

    return; 

} 

void print_value_in_queue(QUEUE* pQueue)

{

       int index ;

       int end;

       if(NULL == pQueue || 0 == pQueue->count)

              return;

       end = pQueue->start;

       if(end < pQueue->end)

              end = pQueue->end + pQueue->length;

       for(index = pQueue->start; index < end; index ++){

              pQueue->print(pQueue->head[index % pQueue->length]);

       }

       return;

}

总结：

    （1）剩下还有compare、find两个子函数，朋友们可以想想怎么利用？

    （2）通用数据结构有很多好处，写的越熟，用得越好。