快捷搜索:  汽车  科技

快速查找算法c语言(C基础语法梳理算法查找算法)

快速查找算法c语言(C基础语法梳理算法查找算法)欢迎转行和学习编程的伙伴,利用更多的资料学习成长比自己琢磨更快哦!对于C/C 感兴趣可以关注小编在后台私信我:【编程交流】一起来学习哦!可以领取一些C/C 的项目学习视频资料哦!已经设置好了关键词自动回复,自动领取就好了!

本期是C 基础语法分享的第十七节,今天给大家来梳理一下查找算法!

快速查找算法c语言(C基础语法梳理算法查找算法)(1)

顺序查找

int SequentialSearch(vector<int>& v int k) { for (int i = 0; i < v.size(); i) if (v[i] == k) return i; return -1; } /* The following is a Sentinel Search Algorithm which only performs just one test in each loop iteration thereby reducing time complexity */ int BetterSequentialSearch(vector<int>& v int k) { int last = v[v.size()-1]; v[v.size()-1] = k; int i = 0; while (v[i]!= k) i ; v[v.size()-1] = last; if(i < v.size()-1 || v[v.size()-1] == k) return i; return -1; }二分查找(折半查找)

// 非递归 int BinarySearch(vector<int> v int value int low int high) { if (v.size() <= 0) { return -1; } while (low <= high) { int mid = low (high - low) / 2; if (v[mid] == value) { return mid; } else if (v[mid] > value) { high = mid - 1; } else { low = mid 1; } } return -1; } // 递归 int BinarySearch2(vector<int> v int value int low int high) { if (low > high) return -1; int mid = low (high - low) / 2; if (v[mid] == value) return mid; else if (v[mid] > value) return BinarySearch2(v value low mid - 1); else return BinarySearch2(v value mid 1 high); }插值查找

int InsertionSearch(int a[] int value int low int high) { int mid = low (value-a[low])/(a[high]-a[low])*(high-low); if(a[mid]==value) return mid; if(a[mid]>value) return InsertionSearch(a value low mid-1); if(a[mid]<value) return InsertionSearch(a value mid 1 high); }斐波那契查找

#include "stdafx.h" #include <memory> #include <iostream> using namespace std; const int max_size=20;//斐波那契数组的长度 /*构造一个斐波那契数组*/ void Fibonacci(int * F) { F[0]=0; F[1]=1; for(int i=2;i<max_size; i) F[i]=F[i-1] F[i-2]; } /*定义斐波那契查找法*/ int FibonacciSearch(int *a int n int key) //a为要查找的数组 n为要查找的数组长度 key为要查找的关键字 { int low=0; int high=n-1; int F[max_size]; Fibonacci(F);//构造一个斐波那契数组F int k=0; while(n>F[k]-1)//计算n位于斐波那契数列的位置 k; int * temp;//将数组a扩展到F[k]-1的长度 temp=new int [F[k]-1]; memcpy(temp a n*sizeof(int)); for(int i=n;i<F[k]-1; i) temp[i]=a[n-1]; while(low<=high) { int mid=low F[k-1]-1; if(key<temp[mid]) { high=mid-1; k-=1; } else if(key>temp[mid]) { low=mid 1; k-=2; } else { if(mid<n) return mid; //若相等则说明mid即为查找到的位置 else return n-1; //若mid>=n则说明是扩展的数值 返回n-1 } } delete [] temp; return -1; } int main() { int a[] = {0 16 24 35 47 59 62 73 88 99}; int key=100; int index=FibonacciSearch(a sizeof(a)/sizeof(int) key); cout<<key<<" is located at:"<<index; return 0; }哈希查找

#include<stdio.h> #include<stdlib.h> #define SUCCESS 1 #define UNSUCCESS 0 #define OVERFLOW -1 #define OK 1 #define ERROR -1 #define MAXNUM 9999 // 用于初始化哈希表的记录 key typedef int Status; typedef int KeyType; // 哈希表中的记录类型 typedef struct { KeyType key; }RcdType; // 哈希表类型 typedef struct { RcdType *rcd; int size; int count; int *tag; }HashTable; // 哈希表每次重建增长后的大小 int hashsize[] = { 11 31 61 127 251 503 }; int index = 0; // 初始哈希表 Status InitHashTable(HashTable &H int size) { int i; H.rcd = (RcdType *)malloc(sizeof(RcdType)*size); H.tag = (int *)malloc(sizeof(int)*size); if (NULL == H.rcd || NULL == H.tag) return OVERFLOW; KeyType maxNum = MAXNUM; for (i = 0; i < size; i ) { H.tag[i] = 0; H.rcd[i].key = maxNum; } H.size = size; H.count = 0; return OK; } // 哈希函数:除留余数法 int Hash(KeyType key int m) { return (3 * key) % m; } // 处理哈希冲突:线性探测 void collision(int &p int m) { p = (p 1) % m; } // 在哈希表中查询 Status SearchHash(HashTable H KeyType key int &p int &c) { p = Hash(key H.size); int h = p; c = 0; while ((1 == H.tag[p] && H.rcd[p].key != key) || -1 == H.tag[p]) { collision(p H.size); c ; } if (1 == H.tag[p] && key == H.rcd[p].key) return SUCCESS; else return UNSUCCESS; } //打印哈希表 void printHash(HashTable H) { int i; printf("key : "); for (i = 0; i < H.size; i ) printf("= " H.rcd[i].key); printf("\n"); printf("tag : "); for (i = 0; i < H.size; i ) printf("= " H.tag[i]); printf("\n\n"); } // 函数声明:插入哈希表 Status InsertHash(HashTable &H KeyType key); // 重建哈希表 Status recreateHash(HashTable &H) { RcdType *orcd; int *otag osize i; orcd = H.rcd; otag = H.tag; osize = H.size; InitHashTable(H hashsize[index ]); //把所有元素,按照新哈希函数放到新表中 for (i = 0; i < osize; i ) { if (1 == otag[i]) { InsertHash(H orcd[i].key); } } return OK; } // 插入哈希表 Status InsertHash(HashTable &H KeyType key) { int p c; if (UNSUCCESS == SearchHash(H key p c)) { //没有相同key if (c*1.0 / H.size < 0.5) { //冲突次数未达到上线 //插入代码 H.rcd[p].key = key; H.tag[p] = 1; H.count ; return SUCCESS; } else recreateHash(H); //重构哈希表 } return UNSUCCESS; } // 删除哈希表 Status DeleteHash(HashTable &H KeyType key) { int p c; if (SUCCESS == SearchHash(H key p c)) { //删除代码 H.tag[p] = -1; H.count--; return SUCCESS; } else return UNSUCCESS; } int main() { printf("-----哈希表-----\n"); HashTable H; int i; int size = 11; KeyType array[8] = { 22 41 53 46 30 13 12 67 }; KeyType key; //初始化哈希表 printf("初始化哈希表\n"); if (SUCCESS == InitHashTable(H hashsize[index ])) printf("初始化成功\n"); //插入哈希表 printf("插入哈希表\n"); for (i = 0; i <= 7; i ) { key = array[i]; InsertHash(H key); printHash(H); } //删除哈希表 printf("删除哈希表中key为12的元素\n"); int p c; if (SUCCESS == DeleteHash(H 12)) { printf("删除成功,此时哈希表为:\n"); printHash(H); } //查询哈希表 printf("查询哈希表中key为67的元素\n"); if (SUCCESS == SearchHash(H 67 p c)) printf("查询成功\n"); //再次插入,测试哈希表的重建 printf("再次插入,测试哈希表的重建:\n"); KeyType array1[8] = { 27 47 57 47 37 17 93 67 }; for (i = 0; i <= 7; i ) { key = array1[i]; InsertHash(H key); printHash(H); } getchar(); return 0; }二叉查找树(二叉搜索查找)

/* 二叉搜索树的查找算法: 在二叉搜索树b中查找x的过程为: 1. 若b是空树,则搜索失败,否则: 2. 若x等于b的根节点的数据域之值,则查找成功;否则: 3. 若x小于b的根节点的数据域之值,则搜索左子树;否则: 4. 查找右子树。 */ // 在根指针T所指二叉查找树中递归地查找其关键字等于key的数据元素,若查找成功, // 则指针p指向該数据元素节点,并返回TRUE,否则指针指向查找路径上访问的最终 // 一个节点并返回FALSE,指针f指向T的双亲,其初始调用值为NULL Status SearchBST(BiTree T KeyType key BiTree f BiTree &p){ if(!T) { //查找不成功 p=f; return false; } else if (key == T->data.key) { //查找成功 p=T; return true; } else if (key < T->data.key) //在左子树中继续查找 return SearchBST(T->lchild key T p); else //在右子树中继续查找 return SearchBST(T->rchild key T p); }红黑树

#define BLACK 1 #define RED 0 #include <iostream> using namespace std; class bst { private: struct Node { int value; bool color; Node *leftTree *rightTree *parent; Node() : value(0) color(RED) leftTree(NULL) rightTree(NULL) parent(NULL) { } Node* grandparent() { if (parent == NULL) { return NULL; } return parent->parent; } Node* uncle() { if (grandparent() == NULL) { return NULL; } if (parent == grandparent()->rightTree) return grandparent()->leftTree; else return grandparent()->rightTree; } Node* sibling() { if (parent->leftTree == this) return parent->rightTree; else return parent->leftTree; } }; void rotate_right(Node *p) { Node *gp = p->grandparent(); Node *fa = p->parent; Node *y = p->rightTree; fa->leftTree = y; if (y != NIL) y->parent = fa; p->rightTree = fa; fa->parent = p; if (root == fa) root = p; p->parent = gp; if (gp != NULL) { if (gp->leftTree == fa) gp->leftTree = p; else gp->rightTree = p; } } void rotate_left(Node *p) { if (p->parent == NULL) { root = p; return; } Node *gp = p->grandparent(); Node *fa = p->parent; Node *y = p->leftTree; fa->rightTree = y; if (y != NIL) y->parent = fa; p->leftTree = fa; fa->parent = p; if (root == fa) root = p; p->parent = gp; if (gp != NULL) { if (gp->leftTree == fa) gp->leftTree = p; else gp->rightTree = p; } } void inorder(Node *p) { if (p == NIL) return; if (p->leftTree) inorder(p->leftTree); cout << p->value << " "; if (p->rightTree) inorder(p->rightTree); } string outputColor(bool color) { return color ? "BLACK" : "RED"; } Node* getSmallestChild(Node *p) { if (p->leftTree == NIL) return p; return getSmallestChild(p->leftTree); } bool delete_child(Node *p int data) { if (p->value > data) { if (p->leftTree == NIL) { return false; } return delete_child(p->leftTree data); } else if (p->value < data) { if (p->rightTree == NIL) { return false; } return delete_child(p->rightTree data); } else if (p->value == data) { if (p->rightTree == NIL) { delete_one_child(p); return true; } Node *smallest = getSmallestChild(p->rightTree); swap(p->value smallest->value); delete_one_child(smallest); return true; } else { return false; } } void delete_one_child(Node *p) { Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree; if (p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL) { p = NULL; root = p; return; } if (p->parent == NULL) { delete p; child->parent = NULL; root = child; root->color = BLACK; return; } if (p->parent->leftTree == p) { p->parent->leftTree = child; } else { p->parent->rightTree = child; } child->parent = p->parent; if (p->color == BLACK) { if (child->color == RED) { child->color = BLACK; } else delete_case(child); } delete p; } void delete_case(Node *p) { if (p->parent == NULL) { p->color = BLACK; return; } if (p->sibling()->color == RED) { p->parent->color = RED; p->sibling()->color = BLACK; if (p == p->parent->leftTree) rotate_left(p->sibling()); else rotate_right(p->sibling()); } if (p->parent->color == BLACK && p->sibling()->color == BLACK && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) { p->sibling()->color = RED; delete_case(p->parent); } else if (p->parent->color == RED && p->sibling()->color == BLACK && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) { p->sibling()->color = RED; p->parent->color = BLACK; } else { if (p->sibling()->color == BLACK) { if (p == p->parent->leftTree && p->sibling()->leftTree->color == RED && p->sibling()->rightTree->color == BLACK) { p->sibling()->color = RED; p->sibling()->leftTree->color = BLACK; rotate_right(p->sibling()->leftTree); } else if (p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == RED) { p->sibling()->color = RED; p->sibling()->rightTree->color = BLACK; rotate_left(p->sibling()->rightTree); } } p->sibling()->color = p->parent->color; p->parent->color = BLACK; if (p == p->parent->leftTree) { p->sibling()->rightTree->color = BLACK; rotate_left(p->sibling()); } else { p->sibling()->leftTree->color = BLACK; rotate_right(p->sibling()); } } } void insert(Node *p int data) { if (p->value >= data) { if (p->leftTree != NIL) insert(p->leftTree data); else { Node *tmp = new Node(); tmp->value = data; tmp->leftTree = tmp->rightTree = NIL; tmp->parent = p; p->leftTree = tmp; insert_case(tmp); } } else { if (p->rightTree != NIL) insert(p->rightTree data); else { Node *tmp = new Node(); tmp->value = data; tmp->leftTree = tmp->rightTree = NIL; tmp->parent = p; p->rightTree = tmp; insert_case(tmp); } } } void insert_case(Node *p) { if (p->parent == NULL) { root = p; p->color = BLACK; return; } if (p->parent->color == RED) { if (p->uncle()->color == RED) { p->parent->color = p->uncle()->color = BLACK; p->grandparent()->color = RED; insert_case(p->grandparent()); } else { if (p->parent->rightTree == p && p->grandparent()->leftTree == p->parent) { rotate_left(p); rotate_right(p); p->color = BLACK; p->leftTree->color = p->rightTree->color = RED; } else if (p->parent->leftTree == p && p->grandparent()->rightTree == p->parent) { rotate_right(p); rotate_left(p); p->color = BLACK; p->leftTree->color = p->rightTree->color = RED; } else if (p->parent->leftTree == p && p->grandparent()->leftTree == p->parent) { p->parent->color = BLACK; p->grandparent()->color = RED; rotate_right(p->parent); } else if (p->parent->rightTree == p && p->grandparent()->rightTree == p->parent) { p->parent->color = BLACK; p->grandparent()->color = RED; rotate_left(p->parent); } } } } void DeleteTree(Node *p) { if (!p || p == NIL) { return; } DeleteTree(p->leftTree); DeleteTree(p->rightTree); delete p; } public: bst() { NIL = new Node(); NIL->color = BLACK; root = NULL; } ~bst() { if (root) DeleteTree(root); delete NIL; } void inorder() { if (root == NULL) return; inorder(root); cout << endl; } void insert(int x) { if (root == NULL) { root = new Node(); root->color = BLACK; root->leftTree = root->rightTree = NIL; root->value = x; } else { insert(root x); } } bool delete_value(int data) { return delete_child(root data); } private: Node *root *NIL; }; int main() { cout << "---【红黑树】---" << endl; // 创建红黑树 bst tree; // 插入元素 tree.insert(2); tree.insert(9); tree.insert(-10); tree.insert(0); tree.insert(33); tree.insert(-19); // 顺序打印红黑树 cout << "插入元素后的红黑树:" << endl; tree.inorder(); // 删除元素 tree.delete_value(2); // 顺序打印红黑树 cout << "删除元素 2 后的红黑树:" << endl; tree.inorder(); // 析构 tree.~bst(); getchar(); return 0; }黑红树

#define BLACK 1 #define RED 0 #include <iostream> using namespace std; class bst { private: struct Node { int value; bool color; Node *leftTree *rightTree *parent; Node() : value(0) color(RED) leftTree(NULL) rightTree(NULL) parent(NULL) { } Node* grandparent() { if (parent == NULL) { return NULL; } return parent->parent; } Node* uncle() { if (grandparent() == NULL) { return NULL; } if (parent == grandparent()->rightTree) return grandparent()->leftTree; else return grandparent()->rightTree; } Node* sibling() { if (parent->leftTree == this) return parent->rightTree; else return parent->leftTree; } }; void rotate_right(Node *p) { Node *gp = p->grandparent(); Node *fa = p->parent; Node *y = p->rightTree; fa->leftTree = y; if (y != NIL) y->parent = fa; p->rightTree = fa; fa->parent = p; if (root == fa) root = p; p->parent = gp; if (gp != NULL) { if (gp->leftTree == fa) gp->leftTree = p; else gp->rightTree = p; } } void rotate_left(Node *p) { if (p->parent == NULL) { root = p; return; } Node *gp = p->grandparent(); Node *fa = p->parent; Node *y = p->leftTree; fa->rightTree = y; if (y != NIL) y->parent = fa; p->leftTree = fa; fa->parent = p; if (root == fa) root = p; p->parent = gp; if (gp != NULL) { if (gp->leftTree == fa) gp->leftTree = p; else gp->rightTree = p; } } void inorder(Node *p) { if (p == NIL) return; if (p->leftTree) inorder(p->leftTree); cout << p->value << " "; if (p->rightTree) inorder(p->rightTree); } string outputColor(bool color) { return color ? "BLACK" : "RED"; } Node* getSmallestChild(Node *p) { if (p->leftTree == NIL) return p; return getSmallestChild(p->leftTree); } bool delete_child(Node *p int data) { if (p->value > data) { if (p->leftTree == NIL) { return false; } return delete_child(p->leftTree data); } else if (p->value < data) { if (p->rightTree == NIL) { return false; } return delete_child(p->rightTree data); } else if (p->value == data) { if (p->rightTree == NIL) { delete_one_child(p); return true; } Node *smallest = getSmallestChild(p->rightTree); swap(p->value smallest->value); delete_one_child(smallest); return true; } else { return false; } } void delete_one_child(Node *p) { Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree; if (p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL) { p = NULL; root = p; return; } if (p->parent == NULL) { delete p; child->parent = NULL; root = child; root->color = BLACK; return; } if (p->parent->leftTree == p) { p->parent->leftTree = child; } else { p->parent->rightTree = child; } child->parent = p->parent; if (p->color == BLACK) { if (child->color == RED) { child->color = BLACK; } else delete_case(child); } delete p; } void delete_case(Node *p) { if (p->parent == NULL) { p->color = BLACK; return; } if (p->sibling()->color == RED) { p->parent->color = RED; p->sibling()->color = BLACK; if (p == p->parent->leftTree) rotate_left(p->sibling()); else rotate_right(p->sibling()); } if (p->parent->color == BLACK && p->sibling()->color == BLACK && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) { p->sibling()->color = RED; delete_case(p->parent); } else if (p->parent->color == RED && p->sibling()->color == BLACK && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) { p->sibling()->color = RED; p->parent->color = BLACK; } else { if (p->sibling()->color == BLACK) { if (p == p->parent->leftTree && p->sibling()->leftTree->color == RED && p->sibling()->rightTree->color == BLACK) { p->sibling()->color = RED; p->sibling()->leftTree->color = BLACK; rotate_right(p->sibling()->leftTree); } else if (p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == RED) { p->sibling()->color = RED; p->sibling()->rightTree->color = BLACK; rotate_left(p->sibling()->rightTree); } } p->sibling()->color = p->parent->color; p->parent->color = BLACK; if (p == p->parent->leftTree) { p->sibling()->rightTree->color = BLACK; rotate_left(p->sibling()); } else { p->sibling()->leftTree->color = BLACK; rotate_right(p->sibling()); } } } void insert(Node *p int data) { if (p->value >= data) { if (p->leftTree != NIL) insert(p->leftTree data); else { Node *tmp = new Node(); tmp->value = data; tmp->leftTree = tmp->rightTree = NIL; tmp->parent = p; p->leftTree = tmp; insert_case(tmp); } } else { if (p->rightTree != NIL) insert(p->rightTree data); else { Node *tmp = new Node(); tmp->value = data; tmp->leftTree = tmp->rightTree = NIL; tmp->parent = p; p->rightTree = tmp; insert_case(tmp); } } } void insert_case(Node *p) { if (p->parent == NULL) { root = p; p->color = BLACK; return; } if (p->parent->color == RED) { if (p->uncle()->color == RED) { p->parent->color = p->uncle()->color = BLACK; p->grandparent()->color = RED; insert_case(p->grandparent()); } else { if (p->parent->rightTree == p && p->grandparent()->leftTree == p->parent) { rotate_left(p); rotate_right(p); p->color = BLACK; p->leftTree->color = p->rightTree->color = RED; } else if (p->parent->leftTree == p && p->grandparent()->rightTree == p->parent) { rotate_right(p); rotate_left(p); p->color = BLACK; p->leftTree->color = p->rightTree->color = RED; } else if (p->parent->leftTree == p && p->grandparent()->leftTree == p->parent) { p->parent->color = BLACK; p->grandparent()->color = RED; rotate_right(p->parent); } else if (p->parent->rightTree == p && p->grandparent()->rightTree == p->parent) { p->parent->color = BLACK; p->grandparent()->color = RED; rotate_left(p->parent); } } } } void DeleteTree(Node *p) { if (!p || p == NIL) { return; } DeleteTree(p->leftTree); DeleteTree(p->rightTree); delete p; } public: bst() { NIL = new Node(); NIL->color = BLACK; root = NULL; } ~bst() { if (root) DeleteTree(root); delete NIL; } void inorder() { if (root == NULL) return; inorder(root); cout << endl; } void insert(int x) { if (root == NULL) { root = new Node(); root->color = BLACK; root->leftTree = root->rightTree = NIL; root->value = x; } else { insert(root x); } } bool delete_value(int data) { return delete_child(root data); } private: Node *root *NIL; }; int main() { cout << "---【红黑树】---" << endl; // 创建红黑树 bst tree; // 插入元素 tree.insert(2); tree.insert(9); tree.insert(-10); tree.insert(0); tree.insert(33); tree.insert(-19); // 顺序打印红黑树 cout << "插入元素后的红黑树:" << endl; tree.inorder(); // 删除元素 tree.delete_value(2); // 顺序打印红黑树 cout << "删除元素 2 后的红黑树:" << endl; tree.inorder(); // 析构 tree.~bst(); getchar(); return 0; }

今天的分享就到这里了,大家要好好学C 哟~

写在最后:对于准备学习C/C 编程的小伙伴,如果你想更好的提升你的编程核心能力(内功)不妨从现在开始!

快速查找算法c语言(C基础语法梳理算法查找算法)(2)

快速查找算法c语言(C基础语法梳理算法查找算法)(3)

整理分享(多年学习的源码、项目实战视频、项目笔记,基础入门教程)

欢迎转行和学习编程的伙伴,利用更多的资料学习成长比自己琢磨更快哦!

对于C/C 感兴趣可以关注小编在后台私信我:【编程交流】一起来学习哦!可以领取一些C/C 的项目学习视频资料哦!已经设置好了关键词自动回复,自动领取就好了!

猜您喜欢: