首页 > 程序开发 > 软件开发 > C语言 >

一步一步写算法(之通用数据结构)

2011-11-11

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】 上一篇博客介绍了通用算法,那么有了这个基础我们可以继续分析通用数据结构了。我们知道在c++里面,既有数据又有函数,...

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱: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)通用数据结构有很多好处,写的越熟,用得越好。

相关文章
最新文章
热点推荐