順序表查找
順序查找又叫線性查找掸刊，是最基本的查找技術(shù)析蝴，它的查找過程: 從表中第一個(gè)(或最后一個(gè))記錄開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值比較蜂嗽，若某個(gè)記錄的關(guān)鍵字和給定值相等，則查找成功殃恒，找到所查的記錄植旧；反之，則查找不成功离唐。
int Sequential_Search(int *a, int n, int key) {
int i = n;
a[0] = key;
while (a[i] != key) {
i--;
}
return i;
}
時(shí)間復(fù)雜度為O(n)病附。
有序表查找
折半查找
又稱為二分查找。前提是線性表中的記錄必須是有序亥鬓，采用的是順序存儲(chǔ)完沪。若給定值與中間記錄的關(guān)鍵字相等，則查找尋找嵌戈；若小于則在記錄的左半邊找覆积；若大于則在記錄的右半邊听皿。不斷重復(fù)上述操作，直到中數(shù)不能再對折宽档。
int Binary_Search(int *a, int n, int key) {
int low = 1, high = n, mid;
while (low <= high) {
mid = (low + high) / 2;
if (key < a[mid]) {
high = mid - 1;
} else if (key > a[mid]) {
low = mid + 1;
} else {
return mid;
}
}
return 0;
}
時(shí)間復(fù)雜度為O(㏒n)写穴。
斐波那契查找
int F[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34};
int Fibonacci_Search(int *a, int n, int key) {
int low = 1, high = n, mid, k = 0;
while (n > F[k] - 1) {
k++;
}
for (int i = 0; i < F[k] - 1; i++) {
a[i] = a[n];
}
while (low <= high) {
mid = low + F[k - 1] - 1;
if (key < a[mid]) {
high = mid - 1;
k--;
} else if (key > a[mid]) {
low = mid + 1;
k = k - 2;
} else {
if (mid <= n) {
return mid;
} else {
return n;
}
}
}
return 0;
}
二叉排序樹
二叉排序樹又稱為二叉查找樹。它或者是一棵空樹雌贱，或者是具有下列性質(zhì)的二叉樹。
- 若它的左子樹不空偿短，則左子樹上所有結(jié)點(diǎn)的值均小于它的跟結(jié)構(gòu)的值欣孤；
- 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均小于它的跟結(jié)構(gòu)的值昔逗；
- 它的左降传、右子樹也分別為二叉排序樹。
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
/**
遞歸查找二叉樹排序樹T中是否存在key
@param T 二叉樹
@param key 查找key
@param f 指針f指向T的雙親勾怒，其初始值調(diào)用值為NULL
@param p 指向該數(shù)據(jù)元素結(jié)點(diǎn)
@return TRUE OR 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);
} else {
return SearchBST(T->rchild, key, T, p);
}
}
二叉排序樹插入操作
Status InsertBST(BiTree *T, int key) {
BiTree p, s;
if (!SearchBST(*T, key, NULL, &p)) {
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
if (!p) {
*T = s;
} else if (key < p->data) {
p->lchild = s;
} else {
p->rchild = s;
}
return TRUE;
}
return FALSE;
}
二叉排序樹刪除操作
Status Delete(BiTree *p) {
BiTree q, s;
if ((*p)->rchild == NULL) {
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ū)
if (q != *p) { //重新接好后面的子樹
q->rchild = s->lchild;
} else {
q->lchild = s->lchild;
}
free(s);
}
return TRUE;
}
Status DeleteBST(BiTree *T, int key) {
if (!*T) {
return FALSE;
} else {
if (key == (*T)->data) {
return Delete(T);
} else if (key < (*T)->data) {
return DeleteBST(&(*T)->lchild, key);
} else {
return DeleteBST(&(*T)->rchild, key);
}
}
}
平衡二叉樹(AVL樹)
平衡二叉樹是一種二叉排序樹，其中每一個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差至多等于1笔链。
將二叉樹上結(jié)點(diǎn)的左子樹深度減去右子樹深度的值稱為平衡因子BF段只，那么平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只可能是-1、0和1鉴扫。
距離插入結(jié)點(diǎn)最近的赞枕，且平衡因子的絕對值大于1的結(jié)點(diǎn)為根的子樹，稱為最小不平衡子樹坪创。
#define LH +1
#define EH 0
#define RH -1
typedef struct BiTNode {
int data;
int bf; //平衡因子
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void R_Rotate(BiTree *P) {
BiTree L;
L = (*P)->lchild;
(*P)->lchild = L->rchild;
L->rchild = (*P);
*P = L;
}
void L_Rotate(BiTree *P) {
BiTree R;
R = (*P)->rchild;
(*P)->rchild = R->lchild;
R->lchild = (*P);
*P = R;
}
void LeftBalance(BiTree *T) {
BiTree L, Lr;
L = (*T)->lchild;
switch (L->bf) {
case LH:
(*T)->bf = L->bf = EH;
R_Rotate(T);
break;
case RH:
Lr = L->rchild;
switch (Lr->bf) {
case LH:
(*T)->bf = RH;
L->bf = EH;
break;
case EH:
(*T)->bf = L->bf = EH;
break;
case RH:
(*T)->bf = EH;
L->bf = LH;
break;
}
Lr->bf = EH;
L_Rotate(&(*T)->lchild);
R_Rotate(T);
}
}
散列表查找概述
散列技術(shù)是在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對應(yīng)關(guān)系f炕婶，使得每個(gè)關(guān)鍵字key對應(yīng)一個(gè)存儲(chǔ)位置f（key）。這種對應(yīng)關(guān)系f稱為散列函數(shù)莱预，又稱為哈希函數(shù)柠掂。采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，這快連續(xù)存儲(chǔ)空間稱為散列表或哈希表依沮。
散列表查找實(shí)現(xiàn)
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12
#define NULLKEY -32768
typedef int Status;
typedef struct {
int *elem; //數(shù)據(jù)元素存儲(chǔ)基址涯贞，動(dòng)態(tài)分配數(shù)組
int count;
}HashTable;
int m = 0; //散列表表長
Status InitHashTable(HashTable *H) {
m = HASHSIZE;
H->count = m;
H->elem = (int *)malloc(sizeof(int));
for (int i = 0; i < m; i++) {
H->elem[i] = NULLKEY;
}
return TRUE;
}
//散列函數(shù)
int Hash(int key) {
return key % m; //除留余數(shù)法
}
void InsertHash(HashTable *H, int key) {
int addr = Hash(key); //求散列地址
while (H->elem[addr] != NULLKEY) { //如果不為空，則沖突
addr = (addr + 1) % m; //開放定址法的線性探測
}
H->elem[addr] = key; //直到有空位后插入關(guān)鍵字
}
Status SearchHash(HashTable H, int key, int *addr) {
*addr = Hash(key);
while (H.elem[*addr] != key) {
*addr = (*addr + 1) % m;
if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) {
return UNSUCCESS;
}
}
return SUCCESS;
}
