前言
最經想改寫C用的配置讀取接口, 准備采用hash或二叉樹提到原先用的鏈表,提高查找效率.
就回顧一下二叉樹,這裡分享一下二叉查找樹,代碼很精簡的, 適合學習運用二叉樹查找.
需要基礎
1.具備C基礎知識
2.知道數據結構,最好知道一點二叉樹結構
能夠學到
1.穩固二叉查找樹
2.C良好編碼格式習慣
3.tree 數據結構幾種流行套路(設計)
參照
1.二叉查找樹簡單分析 http://www.cppblog.com/cxiaojia/archive/2012/08/09/186752.html
(上面那個博文, 圖形講解的恨透,但是那種tree數據結構,不要參照)
正文
1 直接奔主題 說二叉查找樹難點
1.1 簡單說一下二叉查找樹原理和突破
二叉樹也是個經典的數據結構,但是工作中用的場景不多,但是我們常用過,例如map,自帶排序的k-v結構.
二叉樹相比雙向鏈表在改變了插入和刪除方式,使查找代價變小.因而適用領域在快速查找的領域.對於那種快速刪除,
快速插入的領域並不適合.
我們今天主要回顧的是二叉查找(搜索)樹. 首先看看數據結構如下
/*
* 這裡簡單的溫故一下 , 二叉查找樹
*一切從簡單的來吧
*/
typedef int node_t;
typedef struct tree {
node_t v; //這裡簡單測試一下吧,從簡單做起
struct tree* lc;
struct tree* rc;
} *tree_t;
上面比較簡陋,不是很通用,方便了解原理設計,最後會帶大家設計一些通用的二叉樹結構. 這裡扯一點,
結構會影響算法,算法依賴特定的結構.蛋和雞的問題,先有一個不好的蛋,孵化一個不好的雞,後來雞下了很多蛋,其中一個蛋很好,
孵化了一個很好的雞,最後蛋雞良好循環出現了.
對於二叉查找樹,除了刪除比較復雜一點,其它的還是很大眾的代碼,這裡從如何找到一個結點的父節點出發.看下面代碼
/*
* 查找這個結點的父結點
* root : 頭結點
* v : 查找的結點
* : 返回這個v值的父親結點,找不見返回NULL,可以返回孩子結點
*/
tree_t
tree_parent(tree_t root, node_t v, tree_t* pn)
{
tree_t p = NULL;
while (root) {
if (root->v == v)
break;
p = root;
if (root->v > v)
root = root->lc;
else
root = root->rc;
}
if (pn) //返回它孩子結點
*pn = root;
return p;
}
本質思路是,構建一個指針p保存上一個結點.這個函數相比其它函數 tree_parent 這裡多返回當前的孩子結點.一個函數順帶做了兩件事.
這是一個突破.推薦學習,同等代價做的事多了,價值也就提升了.
下面說一下 二叉查找樹 刪除原理(從上面參照文中截得,這個比較詳細,但是代碼寫的水)
代碼實現如下,有點精簡,多看幾遍,或者調試幾遍理解更容易寫.
/*
* 刪除結點
* proot : 指向頭結點的結點
* v : 待刪除的值
*/
void
tree_delete(tree_t* proot, node_t v)
{
tree_t root, n, p, t;//n表示v結點,p表示父親結點
if ((!proot) || !(root = *proot))
return;
//這裡就找見 v結點 n和它的父親結點p
p = tree_parent(root, v, &n);
if (!n) //第零情況 沒有找見這個結點直接返回
return;
//第一種情況,刪除葉子結點,直接刪除就可以此時t=NULL; 第二情況 只有一個葉子結點
if (!n->lc || !n->rc) {
if (!(t = n->lc)) //找見當前結點n的唯一孩子結點
t = n->rc;
if (!p)
*proot = NULL;
else {
if (p->lc == n) //讓當前結點的父親收養這個它唯一的孩子
p->lc = t;
else
p->rc = t;
}
//刪除當前結點並返回,C要是支持 return void; 語法就好了
free(n);
return;
}
//第三種情況, 刪除的結點有兩個孩子
//將當前結點 右子樹中最小值替代為它,繼承王位,它沒有左兒子
for (t = n->rc; t->lc; t = t->lc)
;
n->v = t->v;//用nr替代n了,高效,並讓n指向找到t的唯一右子樹,
tree_delete(&n->rc, t->v);//遞歸刪除n右子樹中最小值, 從t開始,很高效
}
第一步找見這個結點和它父親結點,沒找見它直接返回,父親結點為了重新配置繼承關系.
對於 要刪除 葉子結點或只有孩子的結點, 刪除 走 if(!n->lc || !n->rc) 分支不同是t
當只為葉子結點 t = NULL, 當有一個孩子結點, t = 後繼結點,將其二和一了,是一個突破.
最後 刪除 有兩個孩子的結點, 我們的做法,將 它 右子樹中最小值找到,讓其替代自己, 後面在右子樹中刪除 那個結點.
1.2 簡單擴展一下 遞歸的潛規則
遞歸大多數流程如下
//數據打印函數,全部輸出,不會打印回車,中序遞歸
void
tree_print(tree_t root)
{
if (root) { //簡單中序找到最左結點,打印
tree_print(root->lc);
printf("%d ", root->v);
tree_print(root->rc);
}
}
這樣的遞歸的方式 是
tree_print_0 => tree_print_1 => tree_print_2 => tree_print_3 => tree_print_2 => tree_print_1 => tree_print_0
先入函數棧後出函數棧,遞歸深度太長會爆棧.上面就是大多數遞歸的方式.
遞歸中有一種特殊的尾遞歸.不需要依賴遞歸返回結果.一般遞歸代碼在函數最尾端.例如上 刪除代碼,結構如下
tree_delete_0 => tree_delete_0 => tree_delete_1 => tree_delete_1 => tree_delete_2 => tree_delete_2 => tree_delete_3 =>
這裡代碼就是入棧出棧,跳轉到新的遞歸中.屬於編譯器關於遞歸的優化,不依賴遞歸返回的結果,最後一行,一般都優化為尾遞歸很安全.
入不同行開發,潛規則還是比較多的.扯一點, 一天晚上出租車回來和司機瞎扯淡, 他說有一天帶一個導演,那個導演打電話給一個女孩父親,
告訴他,他女兒今天晚上來他房間,痛斥一頓讓她走了,後面就聯系女孩父親,女孩父親神回復,導演你該潛你就潛. 估計當時那個導演心裡就有
一萬個草泥馬奔過,怎麼就有這麼一對活寶父女.
人生活寶多才歡樂,快樂才會笑著帶著'class'.
1.3 說一下接口和測試代碼
一般良好安全的編程喜歡是,先寫接口,再寫總的測試代碼,後面代碼接口打樁挨個測試. 這裡總的接口和測試代碼如下
/*
* 在二叉查找樹中插入結點
* proot : 頭結點的指針
* v : 待插入變量值,會自動分配內存
*/
void tree_insert(tree_t* proot, node_t v);
//數據打印函數,全部輸出,不會打印回車,中序遞歸
void tree_print(tree_t root);
/*
* 在這個二叉查找樹中查找 值為v的結點,找不見返回NULL
* root : 頭結點
* v : 查找結點值
* : 返回值為查找到的結點,找不見返回NULL
*/
tree_t tree_search(tree_t root, node_t v);
/*
* 查找這個結點的父結點
* root : 頭結點
* v : 查找的結點
* : 返回這個v值的父親結點,找不見返回NULL,可以返回孩子結點
*/
tree_t tree_parent(tree_t root, node_t v, tree_t* pn);
/*
* 刪除結點
* proot : 指向頭結點的結點
* v : 待刪除的值
*/
void tree_delete(tree_t* proot, node_t v);
/*
* 刪除這個二叉查找樹,並把根結點置空
* proot : 指向根結點的指針
*/
void tree_destroy(tree_t* proot);
//簡單輸出幫助宏
#define TREE_PRINT(root) \
puts("當前二叉查找樹的中序數據如下:"), tree_print(root), putchar('\n')
//簡單的主函數邏輯
int main(int argc, char* argv[])
{
tree_t root = NULL;
//先創建一個二叉樹 試試
node_t a[] = { 8,4,5,11,2,3,7,-1,9,0,1,13,12,10 };
//中間臨時變量
tree_t tmp;
node_t n;
int i = -1;
//插入數據
while (++i<sizeof(a) / sizeof(*a))
tree_insert(&root, a[i]);
//簡單輸出數據
TREE_PRINT(root);
//這裡查找數據,刪除數據打印數據
n = 5;
tmp = tree_search(root, n);
if (tmp == NULL)
printf("root is no find %d!\n", n);
else
printf("root is find %d, is %p,%d!\n", n, tmp, tmp->v);
//查找父親結點
n = 12;
tmp = tree_parent(root, n, NULL);
if (tmp == NULL)
printf("root is no find %d!\n", n);
else
printf("root is find parent %d, is %p,%d!\n", n, tmp, tmp->v);
//刪除測試
n = 8;
tree_delete(&root, n);
TREE_PRINT(root);
n = 9;
tree_delete(&root, n);
TREE_PRINT(root);
//釋放資源
tree_destroy(&root);
system("pause");
return 0;
}
測試代碼就是把聲明的接口挨個測試一遍.對於代碼打樁意思就是簡單的實現接口,讓其能編譯通過.如下
/*
* 在這個二叉查找樹中查找 值為v的結點,找不見返回NULL
* root : 頭結點
* v : 查找結點值
* : 返回值為查找到的結點,找不見返回NULL
*/
tree_t
tree_search(tree_t root, node_t v)
{
return NULL;
}
就是打樁. 到這裡基本都萬事具備了.設計思路有了,原理也明白了,下面上一個完整案例看結果.
2.匯總代碼, 看運行結果
首先看運行結果截圖
查找,刪除,打印都來了一遍, 具體的實現代碼如下
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
//控制台打印錯誤信息, 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__)
//檢測並退出的宏
#define CERR_EXIT(fmt, ...) \
CERR(fmt, ##__VA_ARGS__), exit(EXIT_FAILURE)
#endif/* !CERR */
/*
* 這裡簡單的溫故一下 , 二叉查找樹
*一切從簡單的來吧
*/
typedef int node_t;
typedef struct tree {
node_t v; //這裡簡單測試一下吧,從簡單做起
struct tree* lc;
struct tree* rc;
} *tree_t;
/*
* 在二叉查找樹中插入結點
* proot : 頭結點的指針
* v : 待插入變量值,會自動分配內存
*/
void tree_insert(tree_t* proot, node_t v);
//數據打印函數,全部輸出,不會打印回車,中序遞歸
void tree_print(tree_t root);
/*
* 在這個二叉查找樹中查找 值為v的結點,找不見返回NULL
* root : 頭結點
* v : 查找結點值
* : 返回值為查找到的結點,找不見返回NULL
*/
tree_t tree_search(tree_t root, node_t v);
/*
* 查找這個結點的父結點
* root : 頭結點
* v : 查找的結點
* : 返回這個v值的父親結點,找不見返回NULL,可以返回孩子結點
*/
tree_t tree_parent(tree_t root, node_t v, tree_t* pn);
/*
* 刪除結點
* proot : 指向頭結點的結點
* v : 待刪除的值
*/
void tree_delete(tree_t* proot, node_t v);
/*
* 刪除這個二叉查找樹,並把根結點置空
* proot : 指向根結點的指針
*/
void tree_destroy(tree_t* proot);
//簡單輸出幫助宏
#define TREE_PRINT(root) \
puts("當前二叉查找樹的中序數據如下:"), tree_print(root), putchar('\n')
//簡單的主函數邏輯
int main(int argc, char* argv[])
{
tree_t root = NULL;
//先創建一個二叉樹 試試
node_t a[] = { 8,4,5,11,2,3,7,-1,9,0,1,13,12,10 };
//中間臨時變量
tree_t tmp;
node_t n;
int i = -1;
//插入數據
while (++i<sizeof(a) / sizeof(*a))
tree_insert(&root, a[i]);
//簡單輸出數據
TREE_PRINT(root);
//這裡查找數據,刪除數據打印數據
n = 5;
tmp = tree_search(root, n);
if (tmp == NULL)
printf("root is no find %d!\n", n);
else
printf("root is find %d, is %p,%d!\n", n, tmp, tmp->v);
//查找父親結點
n = 12;
tmp = tree_parent(root, n, NULL);
if (tmp == NULL)
printf("root is no find %d!\n", n);
else
printf("root is find parent %d, is %p,%d!\n", n, tmp, tmp->v);
//刪除測試
n = 8;
tree_delete(&root, n);
TREE_PRINT(root);
n = 9;
tree_delete(&root, n);
TREE_PRINT(root);
//釋放資源
tree_destroy(&root);
system("pause");
return 0;
}
/*
* 在二叉查找樹中插入結點
* proot : 頭結點的指針
* v : 待插入變量值,會自動分配內存
*/
void
tree_insert(tree_t* proot, node_t v)
{
tree_t n, p = NULL, t = *proot;
while (t) {
if (t->v == v) //不讓它插入重復數據
return;
p = t; //記錄上一個結點
t = t->v > v ? t->lc : t->rc;
}
//這裡創建結點,創建失敗直接退出C++都是這種做法
n = calloc(sizeof(struct tree), 1);
if (NULL == n)
CERR_EXIT("calloc struct tree error!");
n->v = v;
//這裡插入了,開始第一個是頭結點
if (NULL == p) {
*proot = n;
return;
}
if (p->v > v)
p->lc = n;
else
p->rc = n;
}
//數據打印函數,全部輸出,不會打印回車,中序遞歸
void
tree_print(tree_t root)
{
if (root) { //簡單中序找到最左結點,打印
tree_print(root->lc);
printf("%d ", root->v);
tree_print(root->rc);
}
}
/*
* 在這個二叉查找樹中查找 值為v的結點,找不見返回NULL
* root : 頭結點
* v : 查找結點值
* : 返回值為查找到的結點,找不見返回NULL
*/
tree_t
tree_search(tree_t root, node_t v)
{
while (root) {
if (root->v == v)
return root;
if (root->v > v)
root = root->lc;
else
root = root->rc;
}
return NULL;
}
/*
* 查找這個結點的父結點
* root : 頭結點
* v : 查找的結點
* : 返回這個v值的父親結點,找不見返回NULL,可以返回孩子結點
*/
tree_t
tree_parent(tree_t root, node_t v, tree_t* pn)
{
tree_t p = NULL;
while (root) {
if (root->v == v)
break;
p = root;
if (root->v > v)
root = root->lc;
else
root = root->rc;
}
if (pn) //返回它孩子結點
*pn = root;
return p;
}
/*
* 刪除結點
* proot : 指向頭結點的結點
* v : 待刪除的值
*/
void
tree_delete(tree_t* proot, node_t v)
{
tree_t root, n, p, t;//n表示v結點,p表示父親結點
if ((!proot) || !(root = *proot))
return;
//這裡就找見 v結點 n和它的父親結點p
p = tree_parent(root, v, &n);
if (!n) //第零情況 沒有找見這個結點直接返回
return;
//第一種情況,刪除葉子結點,直接刪除就可以此時t=NULL; 第二情況 只有一個葉子結點
if (!n->lc || !n->rc) {
if (!(t = n->lc)) //找見當前結點n的唯一孩子結點
t = n->rc;
if (!p)
*proot = NULL;
else {
if (p->lc == n) //讓當前結點的父親收養這個它唯一的孩子
p->lc = t;
else
p->rc = t;
}
//刪除當前結點並返回,C要是支持 return void; 語法就好了
free(n);
return;
}
//第三種情況, 刪除的結點有兩個孩子
//將當前結點 右子樹中最小值替代為它,繼承王位,它沒有左兒子
for (t = n->rc; t->lc; t = t->lc)
;
n->v = t->v;//用nr替代n了,高效,並讓n指向找到t的唯一右子樹,
tree_delete(&n->rc, t->v);//遞歸刪除n右子樹中最小值, 從t開始,很高效
}
//采用後序刪除
static void __tree_destroy(tree_t root)
{
if (root) {
__tree_destroy(root->lc);
__tree_destroy(root->rc);
free(root);
}
}
/*
* 刪除這個二叉查找樹,並把根結點置空
* proot : 指向根結點的指針
*/
void
tree_destroy(tree_t* proot)
{
if (proot)
__tree_destroy(*proot);
*proot = NULL;
}
大家自己聯系一下,代碼不多,容易學習順帶回顧一下數據結構中二叉樹結構,關於其中 tree_destroy 編碼方式,是個人的編程習慣.
在C中變量聲明後沒有默認初始化, 所以習慣有這樣的代碼
struct sockaddr_in sddr; memset(&sddr, 0, sizeof sddr);
我覺得這樣麻煩,我習慣的寫法是
struct sockaddr_in saddr = { AF_INET };
利用了一個C聲明初始化潛規則,上面和下面代碼轉成匯編後也許都相似.後面寫法,默認編譯器幫我們把它後面沒初始化部分置成0.
還有一個習慣,可以允許一個爛的開始,必須要有一個perfect結束,參照老C++版本的智能指針,也叫破壞指針. 做法就是
char* p = malloc(1); free(p); p = NULL;
防止野指針.一種粗暴的做法,所以個人習慣在結束的時候多'浪費'一點時間回顧一下以前,再將其徹底抹除,等同於亞洲飛人直接刪除所有回憶的做法.
編程的實現.最後再吐槽一下,為什麼C++很爛,因為看了無數的書,還是不知道它要鬧哪樣.它就是一本易筋經,左練右練上練下練都可以,終於練成了
恭喜你,這張一張殘廢證收下.
再扯一點, 為什麼C++中叫模板,上層語言中叫泛型? 哈哈,可以參照全特化和偏(范)特化.這裡賣一個關子,但是本文中最後會有案例解決.
3.繼往開來,了解一些數據結構設計的模式
上面基本都扯的差不多了,這裡分享C中幾種的數據結構設計模式.
第一種 一切解'對象'
/*
* C中如何封裝一個 tree '結構'(結構決定算法)
*/
/*
* 第一種思路是 一切皆'對象'
*/
struct otree {
void* obj;
struct otree* lc;
struct otree* rc;
};
struct onode {
int id;
char* name;
};
// obj => &struct onde的思路,浪費了4字節,方便管理
大家看到那個 void*應該就明白了吧等同於上層語言中Object對象.
第二種 萬物皆'泛型'
/*
* 第二種思路是 萬物皆'泛型'
*/
struct tree_node {
struct tree_node *lc;
struct tree_node *rc;
};
#define TREE_NODE \
struct tree_node *__tn
struct ttree {
TREE_NODE; //必須在第一行,不在第一行需要計算偏移量 offset
//後面就是結構了
int id;
char* name;
};
下面這種相比上面這種節約4字節.缺點調試難.還有好多種例如模板流,特定寫死流. 這裡擴展一下另一個技巧
關於C中宏簡化結構的代碼
/* IPv6 address */
struct in6_addr
{
union
{
uint8_t __u6_addr8[16];
#if defined __USE_MISC || defined __USE_GNU
uint16_t __u6_addr16[8];
uint32_t __u6_addr32[4];
#endif
} __in6_u;
#define s6_addr __in6_u.__u6_addr8
#if defined __USE_MISC || defined __USE_GNU
# define s6_addr16 __in6_u.__u6_addr16
# define s6_addr32 __in6_u.__u6_addr32
#endif
};
是不是很新奇,但是這樣的代碼,上層包塊庫都不推薦用,這些都是內核層的定義.用的越多越容易出錯.
到這裡基本就快結束了,上面介紹的幾種結構設計思路,大家需要自己揣摩. 特別有價值.搞明白.
再扯一點,很久以前對這樣的結構不明白
struct mem_storage{
union {
int again;
void* str;
} mem;
.....
};
上面again 是干什麼的,後來才明白了,主要作用是設定內存對齊的字節數.方便移植.使其結構體內存結構是一樣,也方便CPU讀取.
思考了很多但是還不明白, 那就對了,說明你還有追求!
這裡再擴展一下, 有時候
/*
常遇見下面代碼
*/
void ss_free(void* arg)
{
if(....){
.....
free(arg);
return;
}
....
}
真心 希望 C中提供 return void; 語法,
這樣就可以寫成
return free(arg); //或者 return (void)check(arg);
這樣代碼會更精簡, 更好看. 這裡也可以通過宏設計處理
#define return_func(f, ...) \
f(##__VA_ARGS__); \
return
屬於偽造吧,希望C委員會提供 return void; 語法!!
後記
錯誤是難免的,有問題提示馬上改. 下次有機會將二叉樹講透,關於設計開發庫中用的二叉樹結構都來一遍,最後分享一下,實際運用的
庫案例.拜~,
有時候在想如果不以經濟建設為中心,是不是人會更有意思一點? 有一款小網游叫中國, 挖了無數坑,就希望大R去充值,diao絲去陪練.哈哈
