【 聲明:版權所有,歡迎轉載,請勿用於商業用途。 聯系信箱: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)通用數據結構有很多好處,寫的越熟,用得越好。