顺序查找 SeqSearch.c
#include <stdio.h> void Print(int *a, int n) { for (int i = 1; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } void SeqSort(int *a, int n) { int i, j; for(i = 1; i < n-1; i++) { for(j = 1; j < n; j++) { if (a[j] > a[j+1]) { a[0] = a[j]; a[j] = a[j+1]; a[j+1] = a[0]; } } } } int SeqSearch(int *a, int e,int n) { a[0] = e; while (a[0] != a[n]) { n--; } if (n == 0) { return -1; } else { return n; } } int main() { int a[] = { 0, 1, 4, 7, 9, 3, 5, 8, 2 }; int iLen = sizeof(a)/sizeof(a[0]); Print(a, iLen); SeqSort(a, iLen); Print(a, iLen); int n = SeqSearch(a, 7, iLen-1); printf("Index:%d\n", n); return 0; }
折半(二分)查找 BinarySearch.c
#include <stdio.h> int BinarySearch(int *a, int e, int n) { int low, high, mid; low = 0; high = n; while (low <= high) { mid = (low + high)/2; if (a[mid] > e) { high = mid - 1; } if (a[mid] < e) { low = mid + 1; } else if (a[mid] == e) { return mid; } } return -1; } int main() { int a[] = {0,1,2,3,4,5,6,7,8,9}; int iLen = sizeof(a)/sizeof(a[0]); int n = BinarySearch(a, 3, iLen-1); printf("The element is:"); printf("%d\n", n); return 0; }
二分查找树 BinarySortTree.c
#include <stdio.h> #include <stdlib.h> #include <malloc.h> typedef struct Tnode { int data; struct Tnode *lChild; struct Tnode *rChild; }TNode,*Bitree; void InsertTree(TNode **root, int e) { if (*root == NULL) { *root = (TNode*)malloc(sizeof(TNode)); (*root)->data = e; (*root)->lChild = NULL; (*root)->rChild = NULL; return; } if ((*root)->data == e) { return; } if (e >(*root)->data) { InsertTree(&((*root)->rChild), e); } else if (e < (*root)->data) { InsertTree(&((*root)->lChild), e); } } void InOrderTraverse(TNode *root) { if(root != NULL) { InOrderTraverse(root->lChild); printf("%d ",root->data); InOrderTraverse(root->rChild); } } void PreOrderTraverse(TNode *root) { if(root != NULL) { printf("%d ",root->data); PreOrderTraverse(root->lChild); PreOrderTraverse(root->rChild); } } int BinarySortSearch(TNode *root, int e) { if (root == NULL) { return 0; } else if (root->data == e) { return 1; } if (root->data > e) { BinarySortSearch(root->lChild, e); } else if (root->data < e) { BinarySortSearch(root->rChild, e); } } void DeleteTree(TNode **root) { TNode *p = NULL,*q = NULL; if ((*root)->lChild == NULL) { p = *root; *root= (*root)->rChild; free(p); p = NULL; } else { p = (*root)->lChild; while (p->rChild != NULL) { q = p; p = p->rChild; } q->rChild = p->lChild; (*root)->data = p->data; free(p); p = NULL; } } void DeleteBST(TNode **root, int e) { if (root == NULL) { return; } if ((*root)->data == e) { DeleteTree(root); } else if ((*root)->data > e) { DeleteBST(&(*root)->lChild, e); } else if ((*root)->data < e) { DeleteBST(&(*root)->rChild, e); } } int main() { int a[] = { 9, 4, 1, 7, 2, 8, 0, 3 }; int iLen = sizeof (a) / sizeof(a[0]); int x,y; TNode *root = NULL, *T = NULL; for(int i = 0; i<iLen ;i++) { InsertTree(&root, a[i]); } printf("InOrderTraverse:"); InOrderTraverse(root); printf("\n"); printf("Enter number:"); scanf("%d",&y); x = BinarySortSearch(root, y); printf("Search elem(1 is success,and 0 is fault):"); printf("%d\n", x); printf("Delete 7\n"); DeleteBST(&root, 7); printf("InOrderTraverse:"); InOrderTraverse(root); printf("\n"); printf("PreOrderTraverse:"); PreOrderTraverse(root); printf("\n"); return 0; }
平衡二叉树 Blance.c Blance.h
/* *平衡二叉树 *目的：编程实现平衡二叉树，并掌握其原理 ** *BlancedBinaryTree.h */ /* *************************************************************** *平衡二叉树的基本思想： * *************************************************************** * 平衡二叉树首先要是一棵二叉排序树。 * * 平衡二叉树又称为AVL树，满足一棵树的根节点中，左右子树的高度* *差的绝对值不超过1. * * 在建立平衡二叉树的过程中，要考虑插入的是在哪个地方，然后才 * *能做出对应的调整，出现的情况如下： * * 插入在左子树的情况下： * * 如果插入的是左子树的左子树（LL型）:需要进行单右旋。 * * 如果插入的是左子树的右子树（LR型）:需要进行双旋，先左单* *旋，再右单旋。 * * 插入在右子树的情况下： * * 如果插入的是右子树的左子树（RL型）:需要进行双旋，先右单* *旋，再左单旋。 * * 如果插入的是右子树的右子树（RR型）:需要进行左单旋。 * *-------------------------------------------------------------* * 从上面的分析中，可以知道，总共需要的操作，也就是左单旋、右 * *单旋的操作，而对于双旋的情况，需要分在左子树和右子树中就行了 * *进行左平衡和右平衡操作。而对于左平衡操作而言，需要进行的是先 * *判断左子树的平衡因子，如果确定为LL型，则只需要进行单右旋就可 * *以，然后设置根节点和左子树的平衡因子为0.如果是LR型，然后需要 * *进行进行双旋，只是平衡因子的设定可能有所不同，画图即可知。对 * *于右平衡的操作，和左平衡类似。 * * 然后进行插入操作，在插入操作中，根据当前结点的平衡因子，做 * *相应的操作，进入操作平衡因子的时候，平衡因子并不是最新的平衡 * *因子，而是插入数据之前的平衡因子，根据插入之前的平衡因子，以 * *及插入的位置，进行相应的平衡因子调整和平衡操作。 * *************************************************************** *时间复杂度：O(log2n) * *空间复杂度： * *平均查找长度： * *************************************************************** */ #pragma once #include <stdio.h> #include <stdlib.h> #define true 1 #define LH +1 #define EH 0 #define RH -1 //二叉树的结构 typedef struct _TNode { int data; int bf; //平衡因子 struct _TNode *lChild; struct _TNode *rChild; }TNode; //单左旋 void L_Rotate(TNode **p) { TNode *rc = NULL; //获得根节点的右子树 rc = (*p)->rChild; //改变根节点的右子树的指向 (*p)->rChild = rc->lChild; //根节点的右子树成为新的根节点，左子树指向原来的根节点 rc->lChild = *p; //保存新的根节点 *p = rc; } //单右旋 void R_Rotate(TNode **p) { TNode *lc = NULL; //获得根节点的左子树 lc = (*p)->lChild; //改变根节点的左子树的指向 (*p)->lChild = lc->rChild; //根节点的左子树成为新的根节点 lc->rChild = *p; *p = lc; } //左平衡处理（插入结点在根节点的左子树上） void LeftBalance(TNode **T) { TNode *lc,*rd; //获取根节点的左子树 lc = (*T)->lChild; //判断左子树的平衡因子 switch (lc->bf) { //如果新插入的结点在左子树的左子树上，属于LL型，需要进行单右旋 case LH: //单右旋之后，根节点的平衡因子和左子树的平衡因子都为0 (*T)->bf = lc->bf = EH; //右单旋处理 R_Rotate(T); break; //新插入结点在左子树的右子树的情况，LR型，先左旋，后右旋 case RH: //要考虑左子树的右子树的平衡因子的情况，分三种 //获取左子树的右子树 rd = lc->rChild; switch (rd->bf) { //如果左子树的右子树的平衡因子为1，则说明插入的位置是左子树的右子树的左子树 case LH: //调整平衡因子，左子树的平衡因子为0，根节点的平衡因子为-1，左子树的右子树的平衡因子为0（放到最后处理） (*T)->bf = RH; lc->bf = EH; break; //如果左子树的右子树的平衡因子为0，则说明插入之后，当前的结点已经稳定 case EH: //调衡平衡因子之后，根节点的平衡因子为0，左子树的平衡因子为0，左子树的右子树的平衡因子为0（最后调整） (*T)->bf = lc->bf = EH; break; //如果左子树的右子树的平衡因子为-1，说明插入的是左子树的右子树的右子树位置 case RH: //调整平衡因子之后，根节点的平衡因子为0，左子树的平衡因子为1，左子树的右子树的平衡因子为0（最后处理） (*T)->bf = EH; lc->bf = LH; } //画图找规律之后，会发现，最后左子树的右子树的平衡因子必为0 rd->bf = EH; //LR型，进行旋转，先左旋转，再右旋转，左旋转的时候，是左子树进行左旋转，右旋转的时候，是对根节点进行右旋转 L_Rotate(&(*T)->lChild); R_Rotate(T);//asd } } //右平衡处理（插入结点在右子树上） void RightBalance(TNode **T) { TNode *rc, *rd; //获取根节点的右子树 rc = (*T)->rChild; //判断右子树的平衡因子 switch (rc->bf) { //如果插入的结点是在右子树的右子树上，属于RR型，进行单左旋就可以了 case RH: //进行单左旋，旋转之后，左子树的平衡因子为0，根节点的平衡因子为0，左子树的右子树的平衡因子为0 (*T)->bf = rc->bf = EH; //进行左旋转处理 L_Rotate(T);//asd break; //如果插入结点在右子树的左子树上，属于RL型，进行双旋，先右旋再左旋 case LH: //获取右子树的左孩子 rd = rc->lChild; //判断右子树的左孩子的平衡因子 switch (rd->bf) { case LH: (*T)->bf = EH; rc->bf = RH; case EH: (*T)->bf = EH; rc->bf = EH; break; case RH: (*T)->bf = LH; rc->bf = EH; break; } //调整平衡因子之后，右子树的左子树的平衡因子一定为0 rd->bf = EH; //属于RL型，要进行双旋，先右旋，再左旋，右旋的时候，以右子树进行右旋，左旋的时候，以根节点左旋 R_Rotate(&(*T)->rChild); L_Rotate(T);//asd } } #define TRUE 1 #define FALSE 0 //建立平衡二叉树（首先要明确平衡二叉树一定是二叉排序树） int InsertAVL(TNode **T, int e, int *taller) { //首先判断根节点是不是为NULL if (!(*T)) { *T = (TNode *)malloc(sizeof(TNode)); (*T)->data = e; (*T)->bf = EH; (*T)->lChild = (*T)->rChild = NULL; *taller = true; } //根节点不为NULL else { //如果要插入的数据和当前的根节点相同，则结束，不需要插入 if ((*T)->data == e) { *taller = FALSE; return FALSE; } //如果根节点的值大于要插入的元素的值，则往左子树中去寻找 if ((*T)->data > e) { //在左子树中寻找有没有和插入元素值一样的 if (!InsertAVL(&(*T)->lChild, e, taller))//asd { return FALSE; } //插入的是左子树的左子树 if (*taller) { //判断当前结点的平衡因子 switch ((*T)->bf) { //如果当前结点的平衡因子为1，则进行左平衡处理(因为插入的是左子树的左子树) case LH: LeftBalance(T);//asd *taller = FALSE;//asd break; //原来左子树平衡，在左子树中插入左子树之后，平衡因子改变 case EH: (*T)->bf = LH; *taller = TRUE; break; //原来的左子树只有右子树的情况，在左子树插入左子树之后，高度平衡 case RH: (*T)->bf = EH; *taller = FALSE; } } } else { //如果插入的结点在右子树中，判断在右子树中有没有相同的 if (!InsertAVL(&(*T)->rChild, e, taller)) { return FALSE; } if (*taller) { //插入结点在右子树的右子树上 switch ((*T)->bf) { //原本右子树只有一个左子树，在右子树插入右子树之后，平衡因子为0，高度平衡 case LH: (*T)->bf = EH; *taller = FALSE; break; //原本右子树平衡，在右子树上插入右子树 case EH: (*T)->bf = RH; *taller = TRUE; break; //原本右子树上有一个右子树，现在又插入一个右子树，则平衡打破，进行右平衡处理 case RH: RightBalance(T);//asd *taller = FALSE; } } } } return TRUE; } //中序遍历 void InOrderTraverse(TNode *T) { if (T != NULL) { InOrderTraverse(T->lChild); printf("[%d]", T->data); InOrderTraverse(T->rChild); } } void PreOrderTraverse(TNode *T) { if (T != NULL) { printf("[%d]",T->data); PreOrderTraverse(T->lChild); PreOrderTraverse(T->rChild); } } //二叉平衡树中寻找关键字 TNode *SearchAVL(TNode *root,int e) { if (root == NULL) { return NULL; } if (root->data == e) { return root; } if (root->data > e) { return SearchAVL(root->lChild, e); } if (root->data < e) { return SearchAVL(root->rChild, e); } } #include "Blance.h" int main() { TNode *root = NULL; int a[] = { 9, 1, 3, 2, 4, 8, 7, 0 }; int iLen = sizeof(a) / sizeof(a[0]); int t = -1; for (int i = 0; i < iLen; i++) { InsertAVL(&root, a[i], &t); } printf("PRE:"); PreOrderTraverse(root); printf("\n"); printf("IN:"); InOrderTraverse(root); printf("\n"); TNode *s = NULL; /* s = SearchAVL(root, 8); if (s != NULL) { printf("%d\n", s->data); } */ return 0; }
哈希查找 HashSearch.h HashSearch.c
/* *哈希查找 *目的：编程实现哈希查找，并掌握其原理 ** *HashSearch.h */ /* ****************************************************************** *哈希查找的基本思想： * ****************************************************************** * 开放地址法： * * 如果两个数据元素的哈希值相同，则在哈希表中为后插入的数据元素另* *外选择一个表项。当程序查找哈希表时，如果没有在第一个对应的哈希表* *项中找到符合查找要求的数据元素，程序就会继续往后查找，直到找到一* *个符合查找要求的数据元素，或者遇到一个空的表项。 * *----------------------------------------------------------------* * 链地址法： * * 将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，* *当查找到这个链表时，必须采用线性查找方法。 * ****************************************************************** *时间复杂度：O(1) * *空间复杂度： * *平均查找长度： * ****************************************************************** */ #pragma once #include <stdio.h> #include <stdlib.h> //哈希表的增量 int hashsize[] = { 20, 21, 22, 30 }; //哈希表表长 int m = 0; //哈希表元素的数据类型 typedef int ElemType; //哈希表结构体 typedef struct _HashTable { ElemType *elem; //数据元素存储基址，动态分配数组 int count; //当前数据元素个数 int sizeindex; //当前容量 }HashTable; //哈希表的初始化 int InitHashTable(HashTable *H) { //循环变量 int i; //哈希表的当前元素个数0 H->count = 0; //设置哈希表的初始容量 H->sizeindex = 0; //哈希表的容量 m = hashsize[0]; //为哈希表分配空间 H->elem = (ElemType *)malloc(m*sizeof(ElemType)); //哈希表元素的初始化 for (i = 0; i < m; i++) { H->elem[i] = 0; } return 0; } //获取键值为K的元素的索引 int Hash(ElemType k) { return k%m; } //处理冲突 void collision(int *p, int d) { *p = (*p + d) % m; } //在哈希表中查找要插入元素的位置 //K是关键字，p是之后要返回的索引，c是冲突的次数 int SearchHash(HashTable H, ElemType K, int *p, int *c) { //获得要插入元素的索引 *p = Hash(K); //记录冲突的次数 while (H.elem[*p] != 0 && H.elem[*p] != K) { //出现冲突，冲突次数加1 (*c)++; //如果冲突的次数小于哈希表的长度，则处理冲突，寻找下一个索引号 if (*c < m) { collision(p, *c); } else { break; } } //当前的索引号的值是不是等于查找的K if (H.elem[*p] == K) { return 1; } else { return 0; } } //插入元素 int InsertHash(HashTable *H, ElemType e) { //处理冲突的次数 int c; int p; c = 0; //if () return 0; } /****************************************链地址法******************************************/ //链地址法哈希表结点的结构 typedef struct _LHashTable { int data; //键值 struct _LHashTable *next; //指向下一个结点 }LHashTable; //哈希表结构 typedef struct _LHash { int index; //下标 LHashTable *next; //指针域 }LHash[10]; //哈希表的初始化 void InitLHashTable(LHash **H) { *H = (LHash *)malloc(sizeof(LHash)); for (int i = 0; i < 10; i++) { (**H + i)->index = i; (**H + i)->next = NULL; } } //哈希表的插入操作 void InsertLHashTable(LHash *H, int e) { //指针变量 LHashTable *p = NULL; //求得下标 int index = e % 10; //先判断下标值为index中有没有和e相等的元素，有的话，就不再加入 p = (*H+index)->next; while (p != NULL && p->data != e) { p = p->next; } if (p == NULL) { p = (LHashTable *)malloc(sizeof(LHashTable)); p->data = e; p->next = (*H+index)->next; (*H+index)->next = p; } } //哈希表的遍历 void HashTraverse(LHash *H) { LHashTable *p = NULL; for (int i = 0; i < 10; i++) { p = (*H+i)->next; printf("%d: ", i + 1); while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); } } //哈希表的查找 LHashTable *Find(LHash *H, int e) { //获取索引 int index = e % 10; LHashTable *p = (*H + index)->next; while (p != NULL && p->data != e) { p = p->next; } if (p != NULL && p->data == e) { return p; } else { return NULL; } } #include "HashSearch.h" int main() { LHash *H = NULL; int a[] = { 19, 23, 45, 67, 12, 34, 89, 1, 3, 6, 7, 9, 10 }; int iLen = sizeof(a) / sizeof(a[0]); InitLHashTable(&H); for (int i = 0; i < iLen; i++) { InsertLHashTable(H, a[i]); } HashTraverse(H); LHashTable *p = NULL; p = Find(H, 67); if (p != NULL) { printf("%d\n", p->data); } return 0; }