无码操人,国产乱伦综合导航,18xxxxxxxxx日本超碰,亚洲AV蜜桃永久无码精品色哟,亚洲黄色免费网站,天天干中文字幕,久草视频在线播放,欧美成人性爱视频在线播放

關(guān)注、星標(biāo)公眾號(hào)，直達(dá)精彩內(nèi)容

ID：技術(shù)讓夢(mèng)想更偉大

作者：李肖遙

線性查找介紹與實(shí)現(xiàn)

查找算法

從一些數(shù)據(jù)之中，找到一個(gè)特殊的數(shù)據(jù)，這種實(shí)現(xiàn)方法就是查找算法。它與遍歷唯一的不同就是它并不一定會(huì)將每一個(gè)數(shù)據(jù)都進(jìn)行訪問，有些查找算法如二分查找等，并不需要完全訪問所有的數(shù)據(jù)。

在我們的日常生活中，幾乎每天都要進(jìn)行一些查找的工作，比如在網(wǎng)盤的文件夾中查找某個(gè)文件，在微信中找到某人的聯(lián)系方式，在已知次品商品的特征情況下，從一堆商品當(dāng)中查找出這些次品等等。

算法簡(jiǎn)介

順序查找算法是最簡(jiǎn)單的查找算法，其線性的從一個(gè)端點(diǎn)開始，將所有的數(shù)據(jù)依次訪問，并求得所需要查找到的數(shù)據(jù)的位置。

代碼實(shí)現(xiàn)

舉個(gè)例子：有6個(gè)商品，他們每一個(gè)商品的重量都是10，但其中有一個(gè)商品是次品，他的重量只有9，其設(shè)計(jì)代碼如下：

#include?

int?main(){
?int?i=0;
????int?commodity[6]={10,10,9,10,10,10};
????for(i=0;i<6;i++){
????????if(commodity[i]==9){
????????????printf("find it at ：%d",i+1);
????????}
????}
????return?0;
}

折半查找（二分查找）介紹與實(shí)現(xiàn)

算法簡(jiǎn)介

二分查找也稱折半查找，是一種效率較高的查找方法。折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。

但有一種特殊情況可以不必須有序排列，即商品選取，從一堆標(biāo)準(zhǔn)重量為10的商品中查找出唯一的次品，這種特殊的數(shù)據(jù)情況也可以使用二分查找。

具體過程

二分查找是將n個(gè)元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2]，則找到x，算法中止；

如果x，則只要在數(shù)組a的左半部分繼續(xù)搜索x；如果x>a[n/2]，則只要在數(shù)組a的右半部搜索x。

總共有n個(gè)元素，漸漸跟下去就是n,n/2,n/4,....n/2^k（接下來操作元素的剩余個(gè)數(shù)），其中k就是循環(huán)的次數(shù)。

由于n/2^k取整后>=1即令n/2^k=1可得k=log2n，所以時(shí)間復(fù)雜度為O(log2n)。

`代碼實(shí)現(xiàn)`

//二分查找算法，找不到就返回-1，找到了就返回值
int?binary_search(int?*?list,int?len,int?target)?{
????int?low?=?0;
????int?hight?=?len-1;
????int?middle;
????while(low?<=?hight)?{
????????middle?=?(low?+?hight)/2;
????????if(list[middle]?=?target)?{
????????????printf("已找到該值，數(shù)組下標(biāo)為:%d\n",middle);
????????????return?list[middle];
????????}?else?if(list[middle]?>?target)?{
????????????hight?=?middle?-1;
????????}?else?if(list[middle]?????????????low?=?middle?+?1;
????????}
????}
????printf("未找到該值");
????return?-1;
}

`分塊查找算法介紹與實(shí)現(xiàn)`

`算法簡(jiǎn)介`

分塊查找是折半查找和順序查找的一種改進(jìn)方法，由于分塊查找只要求索引表是有序的，對(duì)塊內(nèi)節(jié)點(diǎn)沒有排序要求，因此特別適合于節(jié)點(diǎn)動(dòng)態(tài)變化的情況。

分塊查找要求把一個(gè)大的線性表分解成若干塊，每塊中的節(jié)點(diǎn)可以任意存放，但塊與塊之間必須排序。

假設(shè)是按關(guān)鍵碼值非遞減的，那么對(duì)于任意的i，第i塊中的所有節(jié)點(diǎn)的關(guān)鍵碼值都必須小于第i+1塊中的所有節(jié)點(diǎn)的關(guān)鍵碼值。

此外，還要建立一個(gè)索引表，把每塊中的最大關(guān)鍵碼值作為索引表的關(guān)鍵碼值，按塊的順序存放到一個(gè)輔助數(shù)組中，且按關(guān)鍵碼值遞減排序。

查找時(shí)，首先在索引表中進(jìn)行查找，確定要找的節(jié)點(diǎn)所在的塊，可以采用順序查找或折半查找；然后，在相應(yīng)的塊中采用順序查找，即可找到對(duì)應(yīng)的節(jié)點(diǎn)。

`具體過程`

如圖所示，假設(shè)要查找關(guān)鍵字 38 的具體位置

首先將 38 依次和索引表中各最大關(guān)鍵字進(jìn)行比較，因?yàn)?code style="font-size: 14px;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;color: rgb(30, 107, 184);background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;">22 < 38 < 48，所以可以確定 38 如果存在，肯定在第二個(gè)子表中。

由于索引表中顯示第二子表的起始位置在查找表的第 7 的位置上，所以從該位置開始進(jìn)行順序查找，一直查找到該子表最后一個(gè)關(guān)鍵字，找到即可。

代碼實(shí)現(xiàn)

struct?index?
{?
??//定義塊的結(jié)構(gòu)
??int?key;
??int?start;
??
}?newIndex[3];??//定義結(jié)構(gòu)體數(shù)組
??
int?search(int?key,?int?a[])
{
??int?i,?startValue;
??i?=?0;
??while?(i<3?&&?key>newIndex[i].key)?
??{?
????//?確定在哪個(gè)塊中，遍歷每個(gè)塊，確定key在哪個(gè)塊中
????i++;
??}
??if?(i>=3)?
??{?
????//大于分得的塊數(shù)，則返回0
????return?-1;
??}
??startValue?=?newIndex[i].start;?//startValue等于塊范圍的起始值
??while?(startValue?<=?startValue+5?&&?a[startValue]!=key)
??{
????startValue++;
??}
??if?(startValue>startValue+5)?
??{?
????//如果大于塊范圍的結(jié)束值，則說明沒有要查找的數(shù)
????return?-1;
??}
??
??return?startValue;
}

動(dòng)態(tài)查找-二叉排序樹介紹與實(shí)現(xiàn)

算法簡(jiǎn)介

二叉排序樹又稱二叉查找樹，亦稱二叉搜索樹。該樹屬于一種輸入數(shù)據(jù)就默認(rèn)產(chǎn)生一種順序的數(shù)據(jù)結(jié)構(gòu)。動(dòng)態(tài)查找是一種輸入時(shí)就會(huì)自動(dòng)對(duì)其進(jìn)行排序的數(shù)據(jù)結(jié)構(gòu)。

算法性質(zhì)

若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于或等于它的根結(jié)點(diǎn)的值；
若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；
左、右子樹也分別為二叉排序樹；

查找實(shí)現(xiàn)

考慮如果樹是空的，則查找結(jié)束，無(wú)匹配；如果被查找的值和根結(jié)點(diǎn)的值相等，查找成功。

如果被查找的值小于根結(jié)點(diǎn)的值就選擇左子樹，大于根結(jié)點(diǎn)的值就選擇右子樹。代碼如下：

typedef?int?Status;?/*?Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等?*/?
??
/*?二叉樹的二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)定義?*/
typedef??struct?BiTNode?/*?結(jié)點(diǎn)結(jié)構(gòu)?*/
{
????int?data;???/*?結(jié)點(diǎn)數(shù)據(jù)?*/
????struct?BiTNode?*lchild,?*rchild;????/*?左右孩子指針?*/
}?BiTNode,?*BiTree;
??
/*?遞歸查找二叉排序樹T中是否存在key,?*/
/*?指針f指向T的雙親，其初始調(diào)用值為NULL?*/
/*?若查找成功，則指針p指向該數(shù)據(jù)元素結(jié)點(diǎn)，并返回TRUE?*/
/*?否則指針p指向查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)并返回FALSE?*/
Status?SearchBST(BiTree?t,?int?key,?BiTree?f,?BiTree?*p)?
{??
????if?(!t)?/*??查找不成功?*/
????{?
????????*p?=?f;??
????????return?FALSE;?
????}
????else?if?(key?==?t->data)?/*??查找成功?*/
????{?
????????*p?=?t;??
????????return?TRUE;?
????}?
????else?if?(key?data)?
????????return?SearchBST(t->lchild,?key,?t,?p);??/*??在左子樹中繼續(xù)查找?*/
????else??
????????return?SearchBST(t->rchild,?key,?t,?p);??/*??在右子樹中繼續(xù)查找?*/
}

插入方法及實(shí)現(xiàn)

二叉排序的插入是建立在二叉排序的查找之上的，插入一個(gè)結(jié)點(diǎn)，就是通過查找發(fā)現(xiàn)該結(jié)點(diǎn)合適插入位置，把結(jié)點(diǎn)直接放進(jìn)去。

若查找的關(guān)鍵字已經(jīng)有在樹中，則指向該數(shù)據(jù)結(jié)點(diǎn)，若查找的關(guān)鍵字沒有在樹中，則指向查找路徑上最后一個(gè)結(jié)點(diǎn)。代碼如下：

struct?BiTree?{
????int?data;
????BiTree?*lchild;
????BiTree?*rchild;
};
??
//在二叉排序樹中插入查找關(guān)鍵字key
BiTree*?InsertBST(BiTree?*t,int?key)
{
????if?(t?==?NULL)
????{
????????t?=?new?BiTree();
????????t->lchild?=?t->rchild?=?NULL;
????????t->data?=?key;
????????return?t;
????}
??
????if?(key?data)?
????????t->lchild?=?InsertBST(t->lchild,?key);
????else
????????t->rchild?=?InsertBST(t->rchild,?key);
??
????return?t;
}
??
//n個(gè)數(shù)據(jù)在數(shù)組d中，tree為二叉排序樹根
BiTree*?CreateBiTree(BiTree?*tree,?int?d[],?int?n)
{
????for?(int?i?=?0;?i?????????tree?=?InsertBST(tree,?d[i]);
}

刪除方法及實(shí)現(xiàn)

二叉樹的刪除會(huì)影響到樹的其它部分的結(jié)構(gòu)，刪除的時(shí)候需要考慮以下幾種情況：

刪除結(jié)點(diǎn)為葉子結(jié)點(diǎn)；
刪除的結(jié)點(diǎn)只有左子樹；
刪除的結(jié)點(diǎn)只有右子樹
刪除的結(jié)點(diǎn)既有左子樹又有右子樹。

參考代碼如下：

/*?若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，則刪除該數(shù)據(jù)元素結(jié)點(diǎn),?*/
/*?并返回TRUE；否則返回FALSE。?*/
Status?DeleteBST(BiTree?*T,int?key)
{?
????if(!*T)?/*?不存在關(guān)鍵字等于key的數(shù)據(jù)元素?*/?
????????return?FALSE;
????else
????{
????????if?(key==(*T)->data)?/*?找到關(guān)鍵字等于key的數(shù)據(jù)元素?*/?
????????????return?Delete(T);
????????else?if?(key<(*T)->data)
????????????return?DeleteBST(&(*T)->lchild,key);
????????else
????????????return?DeleteBST(&(*T)->rchild,key);
??
????}
}
/*?從二叉排序樹中刪除結(jié)點(diǎn)p，并重接它的左或右子樹。?*/
Status?Delete(BiTree?*p)
{
????BiTree?q,s;
????if((*p)->rchild==NULL)?/*?右子樹空則只需重接它的左子樹（待刪結(jié)點(diǎn)是葉子也走此分支)?*/
????{
????????q=*p;?*p=(*p)->lchild;?free(q);
????}
????else?if((*p)->lchild==NULL)?/*?只需重接它的右子樹?*/
????{
????????q=*p;?*p=(*p)->rchild;?free(q);
????}
????else?/*?左右子樹均不空?*/
????{
????????q=*p;?s=(*p)->lchild;
????????while(s->rchild)?/*?轉(zhuǎn)左，然后向右到盡頭（找待刪結(jié)點(diǎn)的前驅(qū)）?*/
????????{
????????????q=s;
????????????s=s->rchild;
????????}
????????(*p)->data=s->data;?/*??s指向被刪結(jié)點(diǎn)的直接前驅(qū)（將被刪結(jié)點(diǎn)前驅(qū)的值取代被刪結(jié)點(diǎn)的值）?*/
????????if(q!=*p)
????????????q->rchild=s->lchild;?/*??重接q的右子樹?*/?
????????else
????????????q->lchild=s->lchild;?/*??重接q的左子樹?*/
????????free(s);
????}
????return?TRUE;
}

動(dòng)態(tài)查找-平衡二叉樹

算法簡(jiǎn)介

它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。

常用實(shí)現(xiàn)方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等，我們以AVL樹為例。

AVL樹算法性質(zhì)

它必須是一顆二叉查找樹
它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對(duì)值不超過1。
若將二叉樹節(jié)點(diǎn)的平衡因子BF定義為該節(jié)點(diǎn)的左子樹的深度減去它的右子樹的深度，則平衡二叉樹上所有節(jié)點(diǎn)的平衡因子只可能為-1,0,1.
只要二叉樹上有一個(gè)節(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，那么這顆平衡二叉樹就失去了平衡。

AVL樹具體過程

AVL樹的構(gòu)建過程是通過在一棵平衡二叉樹中依次插入元素，若出現(xiàn)不平衡，則要根據(jù)新插入的結(jié)點(diǎn)與最低不平衡結(jié)點(diǎn)的位置關(guān)系進(jìn)行相應(yīng)的調(diào)整。

各個(gè)調(diào)整的方法分為LL型、RR型、LR型和RL型4種類型，以其中一種LR型調(diào)整為例說明，如圖所示：

由于在A的左孩子(L)的右子樹(R)上插入新結(jié)點(diǎn)，使原來平衡二叉樹變得不平衡，此時(shí)A的平衡因子由1變?yōu)?。

按照大小關(guān)系，結(jié)點(diǎn)C應(yīng)作為新的根結(jié)點(diǎn)，其余兩個(gè)節(jié)點(diǎn)分別作為左右孩子節(jié)點(diǎn)才能平衡，操作如下：

將B的左孩子C提升為新的根結(jié)點(diǎn)
將原來的根結(jié)點(diǎn)A降為C的右孩子
各子樹按大小關(guān)系連接(BL和AR不變，CL和CR分別調(diào)整為B的右子樹和A的左子樹)。

代碼實(shí)現(xiàn)

//結(jié)點(diǎn)設(shè)計(jì)?
typedef?struct?Node?{
????int?key;
????struct?Node?*left;
????struct?Node?*right;
????int?height;
}?BTNode;
??
int?height(struct?Node?*N)?{
????if?(N?==?NULL)
????????return?0;
????return?N->height;
}
??
int?max(int?a,?int?b)?{
????return?(a?>?b)???a?:?b;
}
??
BTNode*?newNode(int?key)?{
????struct?Node*?node?=?(BTNode*)malloc(sizeof(struct?Node));
????node->key?=?key;
????node->left?=?NULL;
????node->right?=?NULL;
????node->height?=?1;
????return(node);
}
??
//ll型調(diào)整?
BTNode*?ll_rotate(BTNode*?y)?{
????BTNode?*x?=?y->left;
????y->left?=?x->right;
????x->right?=?y;
??
????y->height?=?max(height(y->left),?height(y->right))?+?1;
????x->height?=?max(height(x->left),?height(x->right))?+?1;
??
????return?x;
}
??
//rr型調(diào)整?
BTNode*?rr_rotate(BTNode*?y)?{
????BTNode?*x?=?y->right;
????y->right?=?x->left;
????x->left?=?y;
??
????y->height?=?max(height(y->left),?height(y->right))?+?1;
????x->height?=?max(height(x->left),?height(x->right))?+?1;
??
????return?x;
}
??
//判斷平衡
int?getBalance(BTNode*?N)?{
????if?(N?==?NULL)
????????return?0;
????return?height(N->left)?-?height(N->right);
}
??
//插入結(jié)點(diǎn)&數(shù)據(jù)
BTNode*?insert(BTNode*?node,?int?key)?{
????if?(node?==?NULL)
????????return?newNode(key);
??
????if?(key?key)
????????node->left?=?insert(node->left,?key);
????else?if?(key?>?node->key)
????????node->right?=?insert(node->right,?key);
????else
????????return?node;
??
????node->height?=?1?+?max(height(node->left),?height(node->right));
??
????int?balance?=?getBalance(node);
??
????if?(balance?>?1?&&?key?left->key)?//LL型
????????return?ll_rotate(node);
??
????if?(balance??node->right->key)?????//RR型
????????return?rr_rotate(node);
??
????if?(balance?>?1?&&?key?>?node->left->key)?{???//LR型
????????node->left?=?rr_rotate(node->left);
????????return?ll_rotate(node);
????}
??
????if?(balance?right->key)?{???//RL型
????????node->right?=?ll_rotate(node->right);
????????return?rr_rotate(node);
????}
??
????return?node;
}
??
//遍歷
void?preOrder(struct?Node?*root)?{
????if?(root?!=?NULL)?{
????????printf("%d?",?root->key);
????????preOrder(root->left);
????????preOrder(root->right);
????}
}

總結(jié)

這里介紹了幾種常見，項(xiàng)目中常用的代碼，幫助大家了解，內(nèi)容也比較基礎(chǔ)，希望對(duì)大家有學(xué)習(xí)作用，我們下一期，再見！

推薦閱讀：

嵌入式編程專輯
Linux 學(xué)習(xí)專輯
C/C++編程專輯
Qt進(jìn)階學(xué)習(xí)專輯
關(guān)注微信公眾號(hào)『技術(shù)讓夢(mèng)想更偉大』，后臺(tái)回復(fù)“m”查看更多內(nèi)容。

長(zhǎng)按前往圖中包含的公眾號(hào)關(guān)注

查找算法問什么？我和面試官進(jìn)行了深入探討…

線性查找介紹與實(shí)現(xiàn)

查找算法

算法簡(jiǎn)介

代碼實(shí)現(xiàn)

折半查找（二分查找）介紹與實(shí)現(xiàn)

算法簡(jiǎn)介

具體過程

代碼實(shí)現(xiàn)

分塊查找算法介紹與實(shí)現(xiàn)

算法簡(jiǎn)介

具體過程

代碼實(shí)現(xiàn)

動(dòng)態(tài)查找-二叉排序樹介紹與實(shí)現(xiàn)

算法簡(jiǎn)介

算法性質(zhì)

查找實(shí)現(xiàn)

插入方法及實(shí)現(xiàn)

刪除方法及實(shí)現(xiàn)

動(dòng)態(tài)查找-平衡二叉樹

算法簡(jiǎn)介

AVL樹算法性質(zhì)

AVL樹具體過程

代碼實(shí)現(xiàn)

總結(jié)

`代碼實(shí)現(xiàn)`

`分塊查找算法介紹與實(shí)現(xiàn)`

`算法簡(jiǎn)介`

`具體過程`