当前位置: 代码迷 >> 综合 >> 深入理解数据结构——查找算法
  详细解决方案

深入理解数据结构——查找算法

热度:82   发布时间:2024-01-17 05:07:27.0
#include <iostream>
#include <string>using namespace std;
typedef int EtypeKey;
typedef int DataType;struct EType {EtypeKey key;DataType data;
};struct LinearList {//查找表类型EType* elem;//指向顺序表的指针int len;int maxsize;
};//顺序查找算法
int Search(LinearList &L, EtypeKey SearchKey) {//在L中顺序查找关键字为SearchKey的//查找成功时返回该记录的下标序号,失败是返回-1int i;i = 0;while (i < L.len && L.elem[i].key != SearchKey)i++;if (L.elem[i].key == SearchKey)return i;elsereturn -1;
}//顺序查找改进算法
int Search(LinearList& L, EtypeKey SearchKey) {//在L中顺序查找关键字为SearchKey的//查找成功时返回该记录在表中的位置,失败是返回0L.elem[0].key = SearchKey;//设置“哨兵”int i;for (int i = L.len; L.elem[i].key != SearchKey; --i);return i;
}int BinarySearch(LinearList& L, EtypeKey SearchKey,int n) {//如果找到则返回该记录的下标,否则返回-1int low = 0;int high = n - 1;while (low <= high) {int mid = (low + high) / 2;if (SearchKey == L.elem[mid].key)return mid;elseif (SearchKey > L.elem[mid].key)low = mid + 1;elsehigh = mid - 1;}return -1;
}//分块查找的算法
struct IndexType {EtypeKey key;int link;
};int IndexSearch(IndexType ls[],EType L[],int m,int blocksize,EtypeKey SearchKey) {//顺序表为L,块长为blocksizeint i, j; i = 0;while (i<m && SearchKey>ls[i].key)i++;if (i >= m)return -1;else {//在顺序表中顺序查找j = ls[i].link;while (SearchKey != L[j].key && j - ls[i].link < blocksize)j++;if (SearchKey != L[j].key)return j;elsereturn -1;}
}/**************************ALV树算法****************************/#define EQ(a,b)   ((a)==(b))
#define LT(a,b)   ((a)<(b))
#define LQ(a,b)   ((a)>(b))#define LH +1    //左高
#define EH 0	//等高
#define RH -1	//右高
#define NULL 0struct BLNode {int data;int bf; //节点平衡因子BLNode* LChird, * RChird;//左右孩指针
} ;
typedef BLNode* BLree;//对*p为根的二叉排序树作右旋处理
void R_Rotate(BLree& p) {BLree lc = p->LChird;//lc指向*p的左子树节点p->LChird = lc->RChird;//lc的右子树挂接为*p的左子树lc->RChird = p;p = lc;//p指向新的节点
}//对*p为根的二叉排序树作左旋处理
void L_Rotate(BLree& p) {BLree rc = p->RChird;//lc指向*p的左子树节点p->RChird = rc->LChird;//lc的左子树挂接为*p的右子树rc->LChird = p;p = rc;//p指向新的节点
}//对以指针T所指节点为根的二叉树作左平衡旋转处理
void LeftBalance(BLree& T) {BLree lc, rd;lc = T->LChird;//lc指向*T的左子树根节点switch (lc->bf) {//检查*T的左子树的平衡度,并作相应平衡处理case LH:		//新节点插入在*T的左孩子的左子树上,要作单右旋处理T->bf = lc->bf = EH;R_Rotate(T); break;case RH:       //新节点插入在*T的左孩子的左子树上,要作双旋处理rd = lc->RChird;   //rd指向*T的左孩子的左子树根switch (rd->bf) {  //修改*T及其左孩子的平衡因子case LH:T->bf = RH; lc->bf = EH; break;case EH:T->bf =lc->bf = EH; break;case RH:T->bf = EH; lc->bf = LH; break;}rd->bf = EH;L_Rotate(T->LChird);//对*T的左子树作左旋平衡处理R_Rotate(T);//对*T的右旋平衡处理}
}//对以指针T所指节点为根的二叉树作右平衡旋转处理
void RightBalance(BLree& T) {BLree rc, ld;rc = T->RChird;//lc指向*T的you子树根节点switch (rc->bf) {//检查*T的左子树的平衡度,并作相应平衡处理case RH:		//新节点插入在*T的you孩子的you子树上,要作单zuo旋处理T->bf = rc->bf = EH;L_Rotate(T); break;case LH:       //新节点插入在*T的you孩子的左子树上,要作双旋处理ld = rc->LChird;   //ld指向*T的you孩子的左子树根switch (ld->bf) {  //修改*T及其左孩子的平衡因子case LH:T->bf = EH; rc->bf = RH; break;case EH:T->bf = rc->bf = EH; break;case RH:T->bf = LH; rc->bf = EH; break;}ld->bf = EH;R_Rotate(T->RChird);//对*T的左子树作YOU旋平衡处理L_Rotate(T);//对*T的ZUO旋平衡处理}
}//删除节点时左平衡旋转处理
void LeftBalance_div(BLree& p, int& shorter) {BLree p1, p2;if (p->bf == 1) {//p节点的左子树高,删除节点后p的bf-1.树变矮p->bf = 0;shorter = 1;}else if (p->bf == 0) {//p节点的左you子树deng高,删除节点后p的bf-1.树gao不变p->bf = -1;shorter = 0;}else {//p节点的you子树高p1 = p->RChird;if (p1->bf == 0) {//p1节点的左you子树等高,删除节点后p的bf=0,进行zuo旋处理,树变矮L_Rotate(p);p1->bf = 1;p->bf = -1;shorter = 0;}else if (p1->bf == -1) {L_Rotate(p);p1->bf = 0;p->bf = 0;shorter = 1;}else {//p1的左子树高,进行双旋处理(先右旋后左旋),树变矮p2 = p1->LChird;p1->LChird = p2->RChird;p2->RChird = p1;p->RChird = p2->LChird;p2->LChird = p;if (p2->bf == 0) {p->bf = 0;p1->bf = 0;}else if (p2->bf == -1) {p->bf = 1;p1->bf = 0;}else {p->bf = 0;p1->bf = -1;}p2->bf = 0;p = p2;shorter = 1;}}
}//删除节点时you平衡旋转处理
void RightBalance_div(BLree& p, int& shorter) {BLree p1, p2;if (p->bf == -1) {p->bf = 0;shorter = 1;}else if (p->bf == 0) {p->bf = 1;shorter = 0;}else {p1 = p->LChird;if (p1->bf == 0) {R_Rotate(p);p1->bf = -1;p->bf = 1;shorter = 0;}else if (p1->bf == 1) {R_Rotate(p);p1->bf = 0;p->bf = 0;shorter = 1;}else {//p1的左子树高,进行双旋处理(先右旋后左旋),树变矮p2 = p1->RChird;p1->RChird = p2->LChird;p2->LChird = p1;p->LChird = p2->RChird;p2->RChird = p;if (p2->bf == 0) {p->bf = 0;p1->bf = 0;}else if (p2->bf == 1) {p->bf = 1;p1->bf = 0;}else {p->bf = 0;p1->bf = 1;}p2->bf = 0;p = p2;shorter = 1;}}
}//ALV树插入算法
bool InsertAVL(BLree& T, int e,bool &taller) {/*若平衡二叉排序树T中不存在和e有相同关键码的节点,则插入一个数据元素为e的新节点,并返回1,否则返回0.若因为插入而使得二叉排序树失去平衡,则作平衡旋转处理布尔型变量taller反映T长高与否*/if (!T) {//插入新节点,树长高,置taller为trueT = (BLree)malloc(sizeof(BLree));T->data = e;T->LChird = T->RChird = NULL;T->bf = EH;taller = true;}else {if (EQ(e, T->data)) {//树中已存在相同关键字的节点taller = false;printf("已存在相同关键字的节点");return 0;}//不再插入if (LT(e, T->data)) {if (!InsertAVL(T->LChird, e, taller))return 0;//未插入if(taller)//已插入到*T的左子树,且左子树长高switch (T->bf) {//检查*T的平衡度case LH://原本左子树比右子树高,需要做左平衡处理LeftBalance(T);taller = false;break;case EH://原本左子树和右子树等高,先因为左子树增高而使得树增高T->bf = LH;taller = true;break;case RH://原本you子树比zuo子树高,需要左右子树等高T->bf = EH;taller = false;break;}}else {//应该继续再*T的右子树进行搜索if (!InsertAVL(T->RChird, e, taller))return 0;//未插入if (taller)//已插入到*T的右子树,且右子树长高switch (T->bf) {//检查*T的平衡度case LH://原本左子树比右子树高,需要左右子树等高T->bf = EH;taller = false;break;case EH://原本左子树和右子树等高,先因为右子树增高而使得树增高T->bf = RH;taller = true;break;case RH://原本you子树比zuo子树高,需要做you平衡处理RightBalance(T);taller = false;break;}}}return 1;
}//ALV树删除算法void Delete(BLree q, BLree &r,int &shorter) {//删除节点if (r->RChird == NULL) {q->data = r->data;q = r;free(q);shorter = 1;}else {Delete(q, r->RChird, shorter);if (shorter == 1)RightBalance_div(r, shorter);}}int DeleteAVL(BLree& p, int x, int& shorter) {//平衡二叉树的删除操作int k;BLree q;if (p == NULL) {printf("不存在要删除的关键字!!\n");return 0;}else if(x<p->data){//p的左子树中进行删除k = DeleteAVL(p->LChird, x, shorter);if (shorter == 1)LeftBalance_div(p, shorter);return k;}else if (x > p->data) {k = DeleteAVL(p->RChird, x, shorter);if (shorter == 1)RightBalance_div(p, shorter);return k;}else {q = p;if (p->RChird == NULL) {//右子树为空,只需要重接它的左子树p = p->LChird;free(q);shorter = 1;}else if (p->LChird == NULL) {//zuo子树为空,只需要重接它的you子树p = p->RChird;free(q);shorter = 1;}else {//左右子树均不为空Delete(q, q->LChird, shorter);if (shorter == 1)LeftBalance_div(p, shorter);p = q;}return 1;}
}/**********************B-算法***********************/#define m 5   //定义树的度
#define KeyType int   //定义关键码struct BTNode {//定义节点类型int KeyNum;//关键码个数BTNode* parent;//指向父节点的指针KeyType Key[m + 1];//关键码数组BTNode* NodePtr[m + 1];//孩子节点指针数组EType* Elem[m + 1];//数据元素,如文件中的记录号
};struct Result {//定义结果类型BTNode* NodePtr;//节点指针int NodePos;//节点位置(在一个节点内)int RetFlag;//返回标志
};struct Btree {//B-树结构定义BTNode* RootPtr;//根节点指针int ElemNum;//元素个数int NodeNum;//节点个数int ChildNum; //孩子个数
};//在一个节点内顺序查找
int SqSearch(BTNode* BT, KeyType SearchKey) {int i = 0, j;for (j = 1; j <= BT->Key[j]; j++)if (SearchKey >= BT->Key[j])i = j;return i;
}
//B-树上的查找算法void B_Search(Btree* bt, KeyType SearchKey, Result& x) {BTNode* current, * parent;int i = 0; bool Found = false;current = bt->RootPtr;//从根节点开始parent = NULL;while (current && !Found) {//循环至查找到的叶子节点或已查到所需关键字i = SqSearch(current, SearchKey);//在一个节点内顺序查找if (i > 0 && current->Key[i] == SearchKey)Found = true;//相等则查找成功else {parent = current;current = current->NodePtr[i];}}if (Found) {//查找成功x.NodePos = i;x.NodePtr = current;x.RetFlag = true;}else {x.NodePos = i;x.NodePtr = parent;x.RetFlag = false;}}/****************************哈希表法********************************/
EType* ht;bool* Empty;
int n;
void HashTable(int divisor) {//构造函数,分配哈希函数n = divisor;ht = new EType[n];Empty = new bool[n];for (int i = 0; i < n; i++)Empty[i] = true;
}//基于开放定址法哈希表查找算法
int HashSearch(KeyType& SearchKey) {//查询一个开地址表,如果存在,则返回k的位置,否则返回插入点(若空间足够)int i = SearchKey % n;//起始桶int j = i;do {if (Empty[j] || ht[j].key == SearchKey)return j;j = (j + 1) / n;//下一个桶} while (j != i);return j;
}bool Search(KeyType& SearchKey, EType& result) {//搜索与k匹配的元素int b = HashSearch(SearchKey);if (Empty[b] || ht[b].key != SearchKey)return false;result = ht[b];return true;
}//基于开放定址法哈希表的插入
bool HashInsert(EType& x, KeyType& SearchKey) {KeyType SearchKey = x.key;int b = HashSearch(SearchKey);if (Empty[b]) {Empty[b] = false;ht[b] = x;return true;}return false;
}//链地址法
struct ChainNode {KeyType Key;ChainNode* link;
};
//基于链地址法哈希表查找算法
ChainNode* HashSearch(ChainNode *a[],KeyType SearchKey,int mod) {//在链接址的哈希表a中查找关键字SearchKey,a[]中存放指向链节点的指针ChainNode* p;int i;i = SearchKey % mod;p = a[i];while (p != NULL && p->Key != SearchKey)p = p->link;if (p == NULL)return NULL;//查找不到时返回空值elsereturn p;//查找到时返回该记录的地址
}
//基于链地址法哈希表插入算法
bool HashInsert(ChainNode* a[], KeyType SearchKey, int mod) {
//在链地址的哈希表a中若查找不到关键字为SearchKey记录则插入该记录ChainNode*pre,* p,*q;int i;i = SearchKey % mod;p = a[i];while (p != NULL && p->Key != SearchKey) {//在对应的链表中查找关键字为SearchKey的记录pre = p;p = p->link;}if (p == NULL) {//未查找到时插入该记录在对应的链表尾q = new ChainNode;q->Key = SearchKey;q->link = NULL;if (a[i] == NULL)a[i] = q;                          //在该链插入第一个记录elsepre->link = q;                     //在该链插入后续记录return true;							//插入新节点返回}return false;			//未插入返回}