據(jù)結(jié)構(gòu)與算法學(xué)習(xí)-查找與二叉排序樹

查找表操作方式分為靜態(tài)查找和動(dòng)態(tài)查找鸯乃。
靜態(tài)查找表(Static Search Table): 只作查找操作的查找表;

  • 1.查詢某個(gè)”特定的”數(shù)據(jù)元素是否在查找表中;
    1. 檢索某個(gè)"特定的"數(shù)據(jù)元素和各種屬性;

動(dòng)態(tài)查找表(Dynamic Search Table): 在查找過(guò)程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素, 或者從查找表中刪除已經(jīng)存在的某個(gè)數(shù)據(jù)元素; 顯然動(dòng)態(tài)查找表的操作就是2個(gè)動(dòng)作

    1. 查找時(shí)插?入數(shù)據(jù)元素;
    1. 查找時(shí)刪除數(shù)據(jù)元素;

1、靜態(tài)查找

1.1、順序表查找

順序查找(Sequential Search), 又稱為線性查找. 是最基本的查找技術(shù). 它的查找過(guò)程: 從表中的第一個(gè)(或最后一個(gè))記錄開始,逐個(gè)進(jìn)?記錄關(guān)鍵字和給定值?比較;

  • 1.若某個(gè)記錄的關(guān)鍵字和給定值相等,則查找成功,找到所查記錄;
    1. 如果直到最后一個(gè)(或第一個(gè))記錄, 其關(guān)鍵字和給定值比較都不等 時(shí), 則表中沒(méi)有所查的記錄,查找不成功;
      代碼實(shí)現(xiàn)
int Sequential_Search(int *a,int n,int key){
    for (int i = 1; i <= n ; i++)
        if (a[i] == key)
            return i;
   
    return 0;
}

上面的代碼是可以優(yōu)化的躁愿,因?yàn)閒or循環(huán)每次都要比較 i<=n砸彬,我們可以減少這步装黑,只需要將給定值存在起始位限番,從末尾開始查起。
代碼實(shí)現(xiàn):

int Sequential_Search2(int *a,int n,int key){
    int i;
    //設(shè)置a[0]為關(guān)鍵字值,稱為'哨兵'
    a[0] = key;
    //循環(huán)從數(shù)組尾部開始
    i = n;
    while (a[i] != key) {
        i--;
    }
    //返回0,則說(shuō)明查找失敗
    return i;
}

1.2想幻、折半查找

折半查找(Binary Search)技術(shù),又稱為二分查找粱栖。
它的前提是線性表中的記錄必須是關(guān)鍵碼有序(通常是從小到大有序),線性 表必須采用順序存儲(chǔ);
折半查找的基本思想是:

  • 在有序表中,取中間記錄作為?較對(duì)象,若給定值與中間記錄的關(guān)鍵字相等則查找成功;
  • 若給定值小于中間的記錄關(guān)鍵字,則在中間記錄的左半?yún)^(qū)繼續(xù)查找;
  • 若給定值大于中間的記錄關(guān)鍵字,則在中間記錄的右半?yún)^(qū)繼續(xù)查找;
  • 不斷重復(fù)以上的過(guò)程,直到查找成功,或所有查找區(qū)域無(wú)記錄,查找失敗為止。
    代碼實(shí)現(xiàn):
int Binary_Search(int *a,int n,int key){
    
    int low,high,mid;
    //定義最低下標(biāo)為記錄首位
    low = 1;
    //定義最高下標(biāo)為記錄末位
    high = n;
    while (low <= high) {
        
        //折半計(jì)算
        mid = (low + high) /2;
        
        
        if (key < a[mid]) {
            //若key比a[mid] 小,則將最高下標(biāo)調(diào)整到中位下標(biāo)小一位;
            high = mid-1;
        }else if(key > a[mid]){
             //若key比a[mid] 大,則將最低下標(biāo)調(diào)整到中位下標(biāo)大一位;
            low = mid+1;
        }else
            //若相等則說(shuō)明mid即為查找到的位置;
            return mid;
    }
    
    return 0;
}

1.3举畸、插值查找

插值查找是根據(jù)查找的關(guān)鍵字key 與查找表中最大最小記錄的關(guān)鍵字比較后的查找方法,其核心就是在于插值的計(jì)算公式: (key - a[low]) / (a[high] - a[low]).
代碼實(shí)現(xiàn):

int Interpolation_Search(int *a,int n,int key){
    int low,high,mid;
    low = 1;
    high = n;
    
    while (low <= high) {
        
        //插值
        mid = low+ (high-low)*(key-a[low])/(a[high]-a[low]);
    
        if (key < a[mid]) {
            //若key比a[mid]插值小,則將最高下標(biāo)調(diào)整到插值下標(biāo)小一位;
            high = mid-1;
        }else if(key > a[mid]){
            //若key比a[mid]插值 大,則將最低下標(biāo)調(diào)整到插值下標(biāo)大一位;
            low = mid+1;
        }else
            //若相等則說(shuō)明mid即為查找到的位置;
            return mid;
    }
    
    return 0;
}

1.4查排、斐波拉契查找

斐波拉契查找利用了黃金分割的原理來(lái)實(shí)現(xiàn)。
代碼實(shí)現(xiàn):

int F[100]; /* 斐波那契數(shù)列 */
int Fibonacci_Search(int *a,int n,int key){
  
    int low,high,mid,i,k;
    //最低下標(biāo)為記錄的首位;
    low = 1;
    //最高下標(biāo)為記錄的末位;
    high = n;
    k = 0;
    
    //1.計(jì)算n為斐波拉契數(shù)列的位置;
    while (n > F[k]-1) {
        k++;
    }
    
    //2.將數(shù)組a不滿的位置補(bǔ)全值;
    for(i = n;i < F[k]-1;i++)
        a[i] = a[n];
    
    //3.
    while (low <= high) {
        
        //計(jì)算當(dāng)前分隔的下標(biāo);
        mid = low+F[k-1]-1;
        
        
        if (key < a[mid]) {
            //若查找的記錄小于當(dāng)前分隔記錄;
            //將最高下標(biāo)調(diào)整到分隔下標(biāo)mid-1處;
            high = mid-1;
            //斐波拉契數(shù)列下標(biāo)減1位;
            k = k-1;
            
        }else if(key > a[mid]){
            //若查找的記錄大于當(dāng)前的分隔記錄;
            //最低下標(biāo)調(diào)整到分隔下標(biāo)mid+1處
            low = mid+1;
            //斐波拉契數(shù)列下標(biāo)減2位;
            k = k-2;
            
        }else{
            if (mid <= n) {
                //若相等則說(shuō)明,mid即為查找的位置;
                return mid;
            }else
            {
                //若mid>n,說(shuō)明是補(bǔ)全數(shù)值,返回n;
                return n;
            }
        }
    }
    return 0;
}

2抄沮、動(dòng)態(tài)查找

二叉排序樹(Binary Sort Tree),又稱為二叉查找樹. 它或者是一顆空樹.或者是一顆具有下列性質(zhì)的二叉樹跋核。

  • 若它的左子樹不空,則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值;
  • 若它的右子樹不空,則右子樹上的所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值;
  • 它的左右子樹也分別是?叉排序樹。
    代碼實(shí)現(xiàn):
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100

typedef int Status;

//二叉樹的二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)定義
//結(jié)點(diǎn)結(jié)構(gòu)
typedef  struct BiTNode
{
    //結(jié)點(diǎn)數(shù)據(jù)
    int data;
    //左右孩子指針
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

//1.二叉排序樹--查找
/*
 遞歸查找二叉排序樹T中,是否存在key;
 指針f指向T的雙親,器初始值為NULL;
 若查找成功,則指針p指向該數(shù)據(jù)元素的結(jié)點(diǎn),并且返回TRUE;
 若指針p指向查找路徑上訪問(wèn)的最后一個(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<T->data)
        return SearchBST(T->lchild, key, T, p);  /*  在左子樹中繼續(xù)查找 */
    else
        return SearchBST(T->rchild, key, T, p);  /*  在右子樹中繼續(xù)查找 */
}

//2.二叉排序樹-插入
/*  當(dāng)二叉排序樹T中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)叛买, */
/*  插入key并返回TRUE砂代,否則返回FALSE */
Status InsertBST(BiTree *T, int key) {
    
    BiTree p,s;
    //1.查找插入的值是否存在二叉樹中;查找失敗則->
    if (!SearchBST(*T, key, NULL, &p)) {
        
        //2.初始化結(jié)點(diǎn)s,并將key賦值給s,將s的左右孩子結(jié)點(diǎn)暫時(shí)設(shè)置為NULL
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = key;
        s->lchild = s->rchild = NULL;
        
        //3.
        if (!p) {
            //如果p為空,則將s作為二叉樹新的根結(jié)點(diǎn);
            *T = s;
        }else if(key < p->data){
            //如果key<p->data,則將s插入為左孩子;
            p->lchild = s;
        }else
            //如果key>p->data,則將s插入為右孩子;
            p->rchild = s;
        
        return  TRUE;
    }
    
    return FALSE;
}

//3.從二叉排序樹中刪除結(jié)點(diǎn)p,并重接它的左或者右子樹;
Status Delete(BiTree *p){
    
    BiTree temp,s;
    
    
    if((*p)->rchild == NULL){
       
        //情況1: 如果當(dāng)前刪除的結(jié)點(diǎn),右子樹為空.那么則只需要重新連接它的左子樹;
        //①將結(jié)點(diǎn)p臨時(shí)存儲(chǔ)到temp中;
        temp = *p;
        //②將p指向到p的左子樹上;
        *p = (*p)->lchild;
        //③釋放需要?jiǎng)h除的temp結(jié)點(diǎn);
        free(temp);
        
    }else if((*p)->lchild == NULL){
        
        //情況2:如果當(dāng)前刪除的結(jié)點(diǎn),左子樹為空.那么則只需要重新連接它的右子樹;
        //①將結(jié)點(diǎn)p存儲(chǔ)到temp中;
        temp = *p;
        //②將p指向到p的右子樹上;
        *p = (*p)->rchild;
        //③釋放需要?jiǎng)h除的temp結(jié)點(diǎn)
        free(temp);
    }else{
        
        //情況③:刪除的當(dāng)前結(jié)點(diǎn)的左右子樹均不為空;
       
        //①將結(jié)點(diǎn)p存儲(chǔ)到臨時(shí)變量temp, 并且讓結(jié)點(diǎn)s指向p的左子樹
        temp = *p;
        s = (*p)->lchild;
      
        //②將s指針,向右到盡頭(目的是找到待刪結(jié)點(diǎn)的前驅(qū))
        //-在待刪除的結(jié)點(diǎn)的左子樹中,從右邊找到直接前驅(qū)
        //-使用`temp`保存好直接前驅(qū)的雙親結(jié)點(diǎn)
        while (s->rchild) {
            temp = s;
            s = s->rchild;
        }
        
        //③將要?jiǎng)h除的結(jié)點(diǎn)p數(shù)據(jù)賦值成s->data;
        (*p)->data = s->data;
        
        //④重連子樹
        //-如果temp 不等于p,則將S->lchild 賦值給temp->rchild
        //-如果temp 等于p,則將S->lchild 賦值給temp->lchild
        if(temp != *p)
            temp->rchild = s->lchild;
        else
            temp->lchild = s->lchild;
        
        //⑤刪除s指向的結(jié)點(diǎn); free(s)
        free(s);
    }
    
    return  TRUE;
}

//4.查找結(jié)點(diǎn),并將其在二叉排序中刪除;
/* 若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí),則刪除該數(shù)據(jù)元素結(jié)點(diǎn), */
/* 并返回TRUE率挣;否則返回FALSE刻伊。 */
Status DeleteBST(BiTree *T,int key)
{
    //不存在關(guān)鍵字等于key的數(shù)據(jù)元素
    if(!*T)
        return FALSE;
    else
    {
        //找到關(guān)鍵字等于key的數(shù)據(jù)元素
        if (key==(*T)->data)
            return Delete(T);
        else if (key<(*T)->data)
            //關(guān)鍵字key小于當(dāng)前結(jié)點(diǎn),則縮小查找范圍到它的左子樹;
            return DeleteBST(&(*T)->lchild,key);
        else
            //關(guān)鍵字key大于當(dāng)前結(jié)點(diǎn),則縮小查找范圍到它的右子樹;
            return DeleteBST(&(*T)->rchild,key);
        
    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市椒功,隨后出現(xiàn)的幾起案子捶箱,更是在濱河造成了極大的恐慌,老刑警劉巖动漾,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件丁屎,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡旱眯,警方通過(guò)查閱死者的電腦和手機(jī)晨川,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)删豺,“玉大人共虑,你說(shuō)我怎么就攤上這事⊙揭常” “怎么了妈拌?”我有些...
    開封第一講書人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)赔桌。 經(jīng)常有香客問(wèn)我供炎,道長(zhǎng)渴逻,這世上最難降的妖魔是什么疾党? 我笑而不...
    開封第一講書人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任音诫,我火速辦了婚禮,結(jié)果婚禮上雪位,老公的妹妹穿的比我還像新娘竭钝。我一直安慰自己,他們只是感情好雹洗,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開白布香罐。 她就那樣靜靜地躺著,像睡著了一般时肿。 火紅的嫁衣襯著肌膚如雪庇茫。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,713評(píng)論 1 312
  • 那天螃成,我揣著相機(jī)與錄音旦签,去河邊找鬼。 笑死寸宏,一個(gè)胖子當(dāng)著我的面吹牛宁炫,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播氮凝,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼羔巢,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了罩阵?” 一聲冷哼從身側(cè)響起竿秆,我...
    開封第一講書人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎稿壁,沒(méi)想到半個(gè)月后幽钢,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡常摧,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年搅吁,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片落午。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡谎懦,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出溃斋,到底是詐尸還是另有隱情界拦,我是刑警寧澤,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布梗劫,位于F島的核電站享甸,受9級(jí)特大地震影響截碴,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜蛉威,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一日丹、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧蚯嫌,春花似錦哲虾、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至栅盲,卻和暖如春汪诉,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背谈秫。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工扒寄, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人孝常。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓旗们,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親构灸。 傳聞我的和親對(duì)象是個(gè)殘疾皇子上渴,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361