C介面與設計,需要註意的流程還是比較多的. 從演算法設計到演算法測試,到基礎庫封裝, 到基礎庫測試,後面是投入生產, 和框架融合再測試. 等等,都特別的耗時間, 今天分享的 是一個關於二叉樹基庫的封裝測試.下一個版本投入到生產環節.
引文
今天分享一個喜歡佩服的偉人,應該算人類文明極大突破者.收藏過一張紙幣類型如下
那我們繼續科普一段關於他的簡介
'高斯有些孤傲，但令人驚奇的是，他春風得意地度過了中產階級的一生，而
沒有遭受到冷酷現實的打擊；這種打擊常無情地加諸於每個脫離現實環境生活的
人。或許高斯講求實效和追求完美的性格，有助於讓他抓住生活中的簡單現實。
高斯22歲獲博士學位，25歲當選聖彼德堡科學院外籍院士，30歲任哥廷根大學數
學教授兼天文臺台長。雖說高斯不喜歡浮華榮耀，但在他成名後的五十年間，這
些東西就像雨點似的落在他身上，幾乎整個歐洲都卷入了這場授獎的風潮，他一
生共獲得75種形形色色的榮譽，包括1818年英王喬治三世賜封的“參議員”，
1845年又被賜封為“首席參議員”。高斯的兩次婚姻也都非常幸福，第一個妻子
死於難產後，不到十個月，高斯又娶了第二個妻子。心理學和生理學上有一個常
見的現象，婚姻生活過得幸福的人，常在喪偶之後很快再婚，他的晚年不幸福,
孩子和他關係不好...'
關於他的專業知識 業界評價如下
'能從九霄雲外的高度按照某種觀點掌握星空和深奧數學的天才。'地球上搞數學人類中公認前三diao.
有時候我們所有的一切 都是自己抉擇的過程,
不是自己選擇,就是別人選擇. 很公平, 就看每個人覺醒的早晚,覺醒能力的 不同而已.
推薦參照
沒有什麼不同 http://music.163.com/#/song?id=25713024
再扯一點, '孤傲'的話題, 生活中有時候遇到一類人, 第一次見他覺得太傲了, 接觸了一段時間
發現這人了不起, 後面瞭解多了, 還是很喜歡和他交朋友. 人不錯.
人是最複雜的,也是最容易改變的.關鍵需要多瞭解.
前言
到這裡逐漸切入正題了, 當一個構想 投入生產環境一般 需要下麵幾個步驟.
1演算法/思路 構思
2演算法實現 測試
3.封裝基礎演算法結構庫
4.演算法/思路結構庫 測試
5. 投入生產環境輕微重構
6.生產環境測試
7.實戰檢測.
所以封裝一個庫還是有些流程比較耗時的. 我們這裡分享的是關於一個二叉樹基礎庫的分享. 原先花了2天使用紅黑樹實現,
但是最後磕磕碰碰,抄抄補補搞出來但是代碼很不好維護,最後退而求其次採用 二叉查找樹構造了一個基礎庫. 並測試了一下基本可以.
等下一次直接用到實戰環境中.
首選學習這個二叉樹 庫封裝 需要
1.瞭解二叉樹基礎原理
2.瞭解C介面的簡單設計
能夠學到
1.C介面設計的一些技巧
2.介面簡單測試
首先看下麵介面文檔 tree.h
#ifndef _H_TREE #define _H_TREE //4.0 控制台列印錯誤信息, fmt必須是雙引號括起來的巨集 #ifndef CERR #define CERR(fmt, ...) \ fprintf(stderr,"[%s:%s:%d][error %d:%s]" fmt "\r\n",\ __FILE__, __func__, __LINE__, errno, strerror(errno),##__VA_ARGS__) #endif/* !CERR */ //4.1 控制台列印錯誤信息並退出, t同樣fmt必須是 ""括起來的字元串常量 #ifndef CERR_EXIT #define CERR_EXIT(fmt,...) \ CERR(fmt,##__VA_ARGS__),exit(EXIT_FAILURE) #endif/* !ERR */ /* * 這裡是簡單二叉查找樹封裝的基庫,封裝庫的庫 * 需要用的的一些輔助結構,主要是通用結構和申請釋放的函數指針 */ typedef struct tree* tree_t; typedef void* (*pnew_f)(); typedef void (*vdel_f)(void* node); typedef int (*icmp_f)(void* ln, void* rn); // __開頭一般意思是不希望你使用,私有的,系統使用 struct __tnode { struct __tnode* lc; struct __tnode* rc; }; /* * 這個巨集必須放在使用的結構體開頭,如下 * struct persion { _TREE_HEAD; char* name; int age; ... * } * */ #define _TREE_HEAD \ struct __tnode __tn /* * new : 結點申請記憶體用的函數指針, 對映參數中是 特定結構體指針 * acmp : 用於添加比較 * gdcmp : 兩個結點比較函數,用戶查找和刪除 * del : 結點回收函數,第一個參數就是 二叉樹中保存的結點地址 * ret : 返回創建好的二叉樹結構, 這裡是 tree_t 結構 */ tree_t tree_create(pnew_f new, icmp_f acmp, icmp_f gdcmp, vdel_f del); /* * proot : 指向tree_t 根結點的指針, * node : 待處理的結點對象, 會調用new(node) 創建新結點 * ret : proot 即是輸入參數也是返回參數,返回根結點返回狀況 */ void tree_add(tree_t* proot, void* node); /* * proot : 輸入和輸出參數,指向根結點的指針 * node : 刪除結點,這裡會調用 cmp(node 左參數, foreach) 找見,通過del(find) 刪除 */ void tree_del(tree_t* proot, void* node); /* * root : 根結點,查找的總對象 * node : 查找條件,會通過cmp(node, foreach)去查找 * parent : 返回查找到的父親結點 * ret : 返回查找到的結點對象 */ void* tree_get(tree_t root, void* node, void** parent); /* * proot : 指向二叉樹數結點指針 * 會調用 del(foreach) 去刪除所有結點,並將所有還原到NULL */ void tree_destroy(tree_t* proot); #endif // !_H_TREE
上面有些代碼在實戰環節是要去掉和統一修改的.這裡是為了降低耦合性,方便測試,就放在一起了.
介面比較精簡,還可以更精簡,下次再優化.應該一看都明白上面代碼是乾什麼的. 需要註意的是
在你想使用二叉樹性質的 結構體中 需要在第一個 成員位置 加入
_TREE_NODE;
舉例如下
//通用結構體變數 struct dict { _TREE_HEAD; char* key; char* value; };
至於為什麼,想一想也都明白了,這樣的代碼或者說技巧 太多了, Linux內核中結構喜歡 將其放在最末的位置,會有一個
typeof 巨集 判斷位置.那下麵我們開始說說具體設計. 扯一點,一個需要C入門選手,要麼把C語言之父的書看一遍,倒著看一遍.
寫一遍或理解會用上面的結構體設計,基本C這塊語法都明白了.
一定要多寫代碼, 因為未來不清楚, 但可以知道的是不好好寫代碼, 那現在都不清楚了. 大家覺得呢.
正文
1.說細節實現
首先看創建函數定義,這裡主要用到函數指針技巧,比較直白.
//內部使用的主要結構 struct tree { //保存二叉樹的頭結點 struct __tnode* root; //構建,釋放,刪除操作的函數指針 pnew_f new; icmp_f acmp; icmp_f gdcmp; vdel_f del; }; /* * new : 結點申請記憶體用的函數指針, 對映參數中是 特定結構體指針 * acmp : 用於添加比較 * gdcmp : 兩個結點比較函數,用戶查找和刪除 * del : 結點回收函數,第一個參數就是 二叉樹中保存的結點地址 * ret : 返回創建好的二叉樹結構, 這裡是 tree_t 結構 */ tree_t tree_create(pnew_f new, icmp_f acmp, icmp_f gdcmp, vdel_f del) { tree_t root = malloc(sizeof(struct tree)); if (NULL == root) CERR_EXIT("malloc struct tree error!"); //初始化挨個操作 memset(root, 0, sizeof(struct tree)); root->new = new; root->acmp = acmp; root->gdcmp = gdcmp; root->del = del; return root; }
上面主要是需要註冊4個函數, 第一個new自然是分配記憶體的操作返回void*就是構造好的記憶體, acmp是添加結點的時候比較函數,
gdcmp 是 get 和 del 時候需要調用的查找函數指針, 對於del可以沒有這個時候,可以傳入NULL,表示不需要幫忙回收記憶體.
大家可以仔細考慮一下為什麼要這些.
首先創建和銷毀是必須的,後面 add的時候添加的是 node 結點, 而查找的時候是比較的是 關鍵字key結構是不一樣的.
同樣看一下回收函數
static void __tree_destroy(struct __tnode* root, vdel_f del) { if (root) { __tree_destroy(root->lc, del); __tree_destroy(root->rc, del); del(root); //結點刪除採用註冊方法 } } /* * proot : 指向二叉樹數結點指針 * 會調用 del(foreach) 去刪除所有結點,並將所有還原到NULL */ void tree_destroy(tree_t* proot) { tree_t root; if ((!proot) || !(root = *proot)) return; if (root->root && root->del) __tree_destroy(root->root, root->del); free(*proot); //單獨釋放最外層內容 *proot = NULL; }
比較質朴沒有好解釋的,最後會讓釋放的指針指向NULL.
後面就是二叉查找樹插入查找和刪除演算法實現了,比較基礎,對著書翻譯就可以了.添加代碼如下
/* * proot : 指向tree_t 根結點的指針, * node : 待處理的結點對象, 會調用new(node) 創建新結點 * ret : proot 即是輸入參數也是返回參數,返回根結點返回狀況 */ void tree_add(tree_t* proot, void* node) { tree_t tm; struct __tnode *n, *p = NULL; icmp_f cmp; int tmp = 0; if ((!proot) || (!node) || !(tm = *proot)) //參數無效直接返回 return; if (!(n = tm->root)) { //插入的結點為頭結點,直接賦值返回 tm->root = tm->new(node); return; } //下麵開始找 待插入結點 cmp = tm->acmp; while (n) { if ((tmp = cmp(node, n)) == 0) //這種情況是不允許插入的 return; p = n; if (tmp < 0) n = n->lc; else n = n->rc; } //找見了開始插入結點 if (tmp < 0) p->lc = tm->new(node); else p->rc = tm->new(node); }
對於cmp
typedef int (*icmp_f)(void* ln, void* rn);
這裡有點約定, ln == rn 返回0, ln>rn 返回 >0 反之返回<0. 其中 傳入的基參數 .都是做第一個參數.
下一版本想改為
//int cmp(void* node, void* rn); 必須是這樣格式 typedef int (*icmp_f)();
弱約束,可以用.畢竟底層庫應該靈活,上層庫應該寫死. 這樣在難處學習成本高,簡單處學習成本低. 等同於紅黑樹的添加和查找.
後面還有一個刪除代碼
/* * proot : 輸入和輸出參數,指向根結點的指針 * node : 刪除結點,這裡會調用 cmp(node 左參數, foreach) 找見,通過del(find) 刪除 */ void tree_del(tree_t* proot, void* node) { tree_t tm; struct __tnode *n, *p, *t, *tp; if ((!proot) || (!node) || !(tm = *proot) || !(tm->root)) return; //查找一下這個結點,如果不存在直接返回 if (!(n = tree_get(tm, node, (void**)&p))) return; //第一種刪除和操作 if ((!n->lc || !n->rc) && !(t = n->lc)) t = n->rc; else { //第二種情況,將右子樹最小結點和當前刪除結點交換 for (tp = n, t = tp->rc; (t->lc); tp = t, t = t->lc) ; //找見了最小的左子樹結點n 和父結點p if (tp->lc == t) tp->lc = t->rc; else tp->rc = t->rc; //移動孩子關係 t->lc = n->lc; t->rc = n->rc; } if (!p) //設置新的root結點 tm->root = t; else { if (p->lc == n) //調整父親和孩子關係,需要你理解二叉查找樹,否則那就相信我吧 p->lc = t; else p->rc = t; } //這裡釋放那個結點 if (tm->del) tm->del(n); }
刪除思路解釋,單節點刪除,父節點指向後繼, 多結點找到右子樹中最小的結點當做新結點,再刪除它.上一個版本用尾遞歸,這裡採用的是非遞歸實現.
對於查找是這樣的,也會一起找到父節點
/* * root : 根結點,查找的總對象 * node : 查找條件,會通過cmp(node, foreach)去查找 * parent : 返回查找到的父親結點 * ret : 返回查找到的結點對象 */ void* tree_get(tree_t root, void* node, void** parent) { struct __tnode *n, *p = NULL; icmp_f cmp; int tmp; if(parent) //初始化功能 *parent = NULL; if ((!node) || (!root) || !(n = root->root)) return NULL; //查找結點 cmp = root->gdcmp; while (n) { if ((tmp = cmp(node, n)) == 0){ //這種情況是不允許插入的 //返回父親結點,沒有就置空 if (parent) *parent = p; break; } p = n; if (tmp < 0) n = n->lc; else n = n->rc; } return n; }
特別是開頭的
if(parent) //初始化功能 *parent = NULL;
為了是查找返回數據都是正常數據,沒有意外.
到這裡基本上二叉樹基庫就整理完畢了. 主要是一些C介面設計的技巧 + 二叉樹查找樹的簡單演算法.
還是比較直白的.下一個版本 將公有頭文件內容移除去,會更簡約一點.
2.tree.c 代碼完整展示
完整代碼展示如下
#include "tree.h" #include <stdio.h> #include <stdlib.h> #include <errno.h> #include <string.h> //內部使用的主要結構 struct tree { //保存二叉樹的頭結點 struct __tnode* root; //構建,釋放,刪除操作的函數指針 pnew_f new; icmp_f acmp; icmp_f gdcmp; vdel_f del; }; /* * new : 結點申請記憶體用的函數指針, 對映參數中是 特定結構體指針 * acmp : 用於添加比較 * gdcmp : 兩個結點比較函數,用戶查找和刪除 * del : 結點回收函數,第一個參數就是 二叉樹中保存的結點地址 * ret : 返回創建好的二叉樹結構, 這裡是 tree_t 結構 */ tree_t tree_create(pnew_f new, icmp_f acmp, icmp_f gdcmp, vdel_f del) { tree_t root = malloc(sizeof(struct tree)); if (NULL == root) CERR_EXIT("malloc struct tree error!"); //初始化挨個操作 memset(root, 0, sizeof(struct tree)); root->new = new; root->acmp = acmp; root->gdcmp = gdcmp; root->del = del; return root; } /* * proot : 指向tree_t 根結點的指針, * node : 待處理的結點對象, 會調用new(node) 創建新結點 * ret : proot 即是輸入參數也是返回參數,返回根結點返回狀況 */ void tree_add(tree_t* proot, void* node) { tree_t tm; struct __tnode *n, *p = NULL; icmp_f cmp; int tmp = 0; if ((!proot) || (!node) || !(tm = *proot)) //參數無效直接返回 return; if (!(n = tm->root)) { //插入的結點為頭結點,直接賦值返回 tm->root = tm->new(node); return; } //下麵開始找 待插入結點 cmp = tm->acmp; while (n) { if ((tmp = cmp(node, n)) == 0) //這種情況是不允許插入的 return; p = n; if (tmp < 0) n = n->lc; else n = n->rc; } //找見了開始插入結點 if (tmp < 0) p->lc = tm->new(node); else p->rc = tm->new(node); } /* * proot : 輸入和輸出參數,指向根結點的指針 * node : 刪除結點,這裡會調用 cmp(node 左參數, foreach) 找見,通過del(find) 刪除 */ void tree_del(tree_t* proot, void* node) { tree_t tm; struct __tnode *n, *p, *t, *tp; if ((!proot) || (!node) || !(tm = *proot) || !(tm->root)) return; //查找一下這個結點,如果不存在直接返回 if (!(n = tree_get(tm, node, (void**)&p))) return; //第一種刪除和操作 if ((!n->lc || !n->rc) && !(t = n->lc)) t = n->rc; else { //第二種情況,將右子樹最小結點和當前刪除結點交換 for (tp = n, t = tp->rc; (t->lc); tp = t, t = t->lc) ; //找見了最小的左子樹結點n 和父結點p if (tp->lc == t) tp->lc = t->rc; else tp->rc = t->rc; //移動孩子關係 t->lc = n->lc; t->rc = n->rc; } if (!p) //設置新的root結點 tm->root = t; else { if (p->lc == n) //調整父親和孩子關係,需要你理解二叉查找樹,否則那就相信我吧 p->lc = t; else p->rc = t; } //這裡釋放那個結點 if (tm->del) tm->del(n); } /* * root : 根結點,查找的總對象 * node : 查找條件,會通過cmp(node, foreach)去查找 * parent : 返回查找到的父親結點 * ret : 返回查找到的結點對象 */ void* tree_get(tree_t root, void* node, void** parent) { struct __tnode *n, *p = NULL; icmp_f cmp; int tmp; if(parent) //初始化功能 *parent = NULL; if ((!node) || (!root) || !(n = root->root)) return NULL; //查找結點 cmp = root->gdcmp; while (n) { if ((tmp = cmp(node, n)) == 0){ //這種情況是不允許插入的 //返回父親結點,沒有就置空 if (parent) *parent = p; break; } p = n; if (tmp < 0) n = n->lc; else n = n->rc; } return n; } //實際的刪除函數,採用後續刪除 static void __tree_destroy(struct __tnode* root, vdel_f del) { if (root) { __tree_destroy(root->lc, del); __tree_destroy(root->rc, del); del(root); //結點刪除採用註冊方法 } } /* * proot : 指向二叉樹數結點指針 * 會調用 del(foreach) 去刪除所有結點,並將所有還原到NULL */ void tree_destroy(tree_t* proot) { tree_t root; if ((!proot) || !(root = *proot)) return; if (root->root && root->del) __tree_destroy(root->root, root->del); free(*proot); //單獨釋放最外層內容 *proot = NULL; }
總長度還是比較短的.上面代碼寫了幾遍,都沒有加測試介面. 後面單獨寫測試demo.因為是封裝庫的庫,測試代碼會多一點.
3.說測試結果
到這裡就是說測試的時候,先簡單看一個test.c 測試,編譯命令是
gcc -g -Wall -o test.out test.c tree.c
源碼如下
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "tree.h" //通用結構體變數 struct dict { _TREE_HEAD; char* key; char* value; }; static void* __dict_new(void* arg) { return arg; } //為了通用庫,這種比較演算法比較不好,採用hash不能夠唯一確定 static int __dict_acmp(struct dict* ln, struct dict* rn) { return strcmp(ln->key, rn->key); } static int __dict_gdcmp(const char* ln, struct dict* rn) { return strcmp(ln, rn->key); } /* * 這裡測試 tree.c 基類型測試的 */ int main(int argc, char* argv[]) { struct dict *pd , *pp; struct dict dt1 = { { 0, 0 }, "123", "123" }; struct dict dt2 = { { 0, 0 }, "1","1" }; struct dict dt3 = { { 0, 0 }, "2","2" }; struct dict dt4 = { { 0, 0 }, "456", "456" }; struct dict dt5 = { { 0, 0 }, "7","7" }; //創建一個結點,後面創建刪除 tree_t root = tree_create(__dict_new, (icmp_f)__dict_acmp, (icmp_f)__dict_gdcmp, NULL); //開始添加結點 tree_add(&root, &dt1); tree_add(&root, &dt2); tree_add(&root, &dt3); tree_add(&root, &dt4); tree_add(&root, &dt5); //得到這個結點,並返回 pd = tree_get(root, "123", NULL); printf("key:[%s], value:[%s].\n", pd->key, pd->value); pd = tree_get(root, "456", (void**)&pp); printf("key:[%s], value:[%s].\n", pd->key, pd->value); printf("key:[%s], value:[%s].\n", pp->key, pp->value); //刪除結點測試,這個普通樹型結構確實不好 tree_del(&root, "123"); pd = tree_get(root, "456", (void**)&pp); printf("key:[%s], value:[%s].\n", pd->key, pd->value); if (!pp) puts("應該不存在的!"); //通過單點調試,記憶體檢測一切正常 tree_destroy(&root); system("pause"); return 0; }
測試結果,原先是在window上,後面在Linux上測試了.結果如下
一切正常.
第二個測試,測試在堆上分配是否正常 main.c
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include "tree.h" //繼續測試堆上分配 struct node { _TREE_HEAD; char* key; char* value; }; //構建運用到的函數 static void* __node_new(struct node* n) { struct node* nn = calloc(1, sizeof(struct node)); if(NULL == nn) CERR_EXIT("malloc struct node error!"); nn->key = n->key; nn->value = n->value; //返回最終結果 return nn; } //添加時候查找函數 static int __node_acmp(void* ln, void* rn) { return strcmp(((struct node*)ln)->key, ((struct node*)rn)->key); } //查找和刪除的查找函數 static int __node_gdcmp(void* ln, void* rn) { return strcmp(ln, ((struct node*)rn)->key); } //簡單測試函數 static void __node_puts(void* arg) { struct node* n = arg; if(NULL == n) puts("now node is empty!"); else printf("key:%s, value:%s.\n", n->key, n->value); } //簡單釋放函數 static void __node_delete(void* arg) { __node_puts(arg); free(arg); } //寫到這裡自己都想抱怨一句前戲太長了, tree.c 其實本質是個通用演算法庫,... /* * 這裡繼續測試一下 tree 基類庫介面 */ int main(int argc, char* argv[]) { tree_t root = tree_create(__node_new, __node_acmp, __node_gdcmp, __node_delete); //這裡就添加結點 struct node ntmp = { {NULL, NULL}, "a", "123"}; tree_add(&root, &ntmp); ntmp.key = "bb"; ntmp.value = "ccccccc"; tree_add(&root, &ntmp); ntmp.key = "bbc"; ntmp.value = "ccccccc"; tree_add(&root, &ntmp); ntmp.key = "bbcc"; ntmp.value = "ccccccc"; tree_add(&root, &ntmp); ntmp.key = "bbcccc"; ntmp.value = "dd你好ccc"; tree_add(&root, &ntmp); //tree_destroy(&root); if(NULL == root) puts("root is null"); ntmp.key = "好的"; ntmp.value = "cccok就這樣c"; tree_add(&root, &ntmp); //這裡查找結點 void *p, *n; n = tree_get(root, "好的", &p); if(p) __node_puts(p); else puts("沒有父結點"); __node_puts(n); //刪除結點 tree_del(&root, "好的"); tree_destroy(&root); return 0; }
編譯命令,Makefile文件內容如下
main.out:main.c tree.c gcc -g -Wall -o $@ $^
運行結果截圖如下
一切正常沒有記憶體泄露.
後面準備到庫再進行生產測試.
後記
這裡,這個基礎tree C庫基本封裝了,根據庫簡單修改一下基本就可以用在開發中了.下一個版本利用這個庫 構造一個 C 配置文件讀取介面.
讓框架具備簡單配置文件熱讀取的能力.扯一點,像這些解析配置的引擎難點都在 語法解析上.其它都好搞.以後有機會帶大家手把手寫json,csv 解析'引擎'.
這裡就這樣了. 錯誤是難免的, 因為經歷的太少, 拜~.
