数据结构与算法（十六）——静态查找&动态查找

/*
 array是待搜索的数组
 arrayCount是数组中元素个数
 searchKey是搜索字段
 返回值是匹配到的array中的元素的下标，这里使用-1来表示没有匹配到值
 */
int sequentialSearch(int *array, int arrayCount, int searchKey) {
  for (int i = 0; i < arrayCount; i++) {
    if (array[i] == searchKey) {
      return i;
    }
  }

  return -1;
}

/*
 array是待搜索的数组，这个数组中的0号位是哨兵位
 arrayCount是数组中除了哨兵位之外的元素的个数
 searchKey是搜索字段
 返回值是匹配到的array中的元素的下标，这里使用哨兵位来表示没有匹配到值
 */
int sentrySequentialSearch(int *array, int arrayCount, int searchKey) {
  array[0] = searchKey; // 将搜索字段设置为哨兵的值

  // 从数组的最后一个元素进行倒序遍历
  int index = arrayCount;
  while (array[index] != searchKey) {
    index--;
  }

  return index;
}

/*
 二分查找的前提是：数组array中的元素是有序的，本例中假设其递增。
 */
int binarySearch(int *array, int arrayCount, int searchKey) {
  int lowIndex = 0;
  int highIndex = arrayCount - 1;
  int middleIndex;

  while (lowIndex < highIndex) {
    middleIndex = (lowIndex + highIndex) / 2;
    if (searchKey < array[middleIndex]) {
      highIndex = middleIndex - 1;
    } else if (searchKey > array[middleIndex]) {
      lowIndex = middleIndex + 1;
    } else {
      return  middleIndex;
    }
  }

  // 没有找到的话就返回-1
  return -1;
}

middleIndex = (lowIndex + highIndex) / 2;

 middleIndex = lowIndex + (highIndex - lowIndex) / 2;

middleIndex = lowIndex + ((searchKey - array[lowIndex]) / (array[highIndex] - array[lowIndex])) * (highIndex - lowIndex);

/*
 插值查找
 */
int intepolationSearch(int *array, int arrayCount, int searchKey) {
  int lowIndex = 0;
  int highIndex = arrayCount - 1;
  int middleIndex;

  while (lowIndex < highIndex) {
    middleIndex = lowIndex + ((searchKey - array[lowIndex]) / (array[highIndex] - array[lowIndex])) * (highIndex - lowIndex);

    if (searchKey > array[middleIndex]) {
      lowIndex = middleIndex + 1;
    } else if (searchKey < array[middleIndex]) {
      highIndex = middleIndex - 1;
    } else {
      return  middleIndex;
    }
  }

  return -1;
} 

 middleIndex = lowIndex + F(n-1) - 1

#pragma mark - 斐波那契查找


// 构建斐波那契数列
void createFibonacciSequence(int arrayCount, int *fibonacciSequence, int *n) {
  fibonacciSequence[0] = 1;
  fibonacciSequence[1] = 1;
  *n = 1;
  while (fibonacciSequence[*n] < arrayCount) {
    (*n)++;
    fibonacciSequence[*n] = fibonacciSequence[*n - 1] + fibonacciSequence[*n - 2];
  }
}


int fibonacciSearch(int *array, int arrayCount, int searchKey) {
  // 1，构建斐波那契数列，并求解出第一个大于等于数组长度的斐波那契元素
  int fibonacciSequence[100]; // 斐波那契数列
  int n; // n是保证【fibonacciSequence[n]>=searchKey】的最小值
  createFibonacciSequence(arrayCount, fibonacciSequence, &n);

  // 2，对原来的有序线性表进行扩容填充
  for (int i = arrayCount; i < fibonacciSequence[n]; i++) {
    array[i] = array[arrayCount-1];
  }

  // 3，循环遍历搜索对应元素
  int lowIndex = 0;
  int highIndex = fibonacciSequence[n] - 1; // 之所以减1是因为下标从0开始
  int middleIndex; // 中间元素下标
  while (lowIndex <= highIndex) {
    middleIndex = lowIndex + fibonacciSequence[n-1] - 1;

    // 比较中间元素与搜索值
    if (searchKey > array[middleIndex]) {
      lowIndex = middleIndex + 1;
      n = n - 2;
    } else if (searchKey < array[middleIndex]) {
      highIndex = middleIndex - 1;
      n = n - 1;
    } else {
      return middleIndex <= arrayCount-1 ? middleIndex : arrayCount-1;
    }
  }

  return -1;
}


int main(int argc, const char * argv[]) {
  // insert code here...
  printf("Hello, World!\n");

  int array[100] = {1,2,3,4,5,6,7,8,9,10};
  int arrayCount = 10;
  printf("斐波那契查找:%d\n", fibonacciSearch(array, arrayCount, 10));

  return 0;
}

//
//  main.c
//  BinarySearchTree
//
//  Created by 拉维 on 2022/5/12.
//


#include <stdio.h>


// 操作的状态
typedef enum : int {
  Success,
  Error,
} Status;


// BST节点结构
typedef struct BSTNode {
  int data; // 数据域
  struct BSTNode *leftChild; // 左子节点
  struct BSTNode *rightChild; // 右子节点
} BSTNode;


// 二叉搜索树的结构
typedef struct BSTNode * BinarySearchTree;

// BST的查找
/*
 如果找到了对应元素，则parentNode是目标节点的双亲节点；如果没有找到对应元素，则parentNode是最终查找的那个节点，此时就可以将新建节点添加为parentNode的子节点
 */
struct BSTNode * bstSearch(BinarySearchTree bstRootNode, int searchKey, BinarySearchTree *parentNode) {
  BinarySearchTree currentNode = bstRootNode;
  *parentNode = NULL;

  while (currentNode) {
    if (currentNode->data == searchKey) {
      break; // 跳出循环
    } else if (currentNode->data > searchKey) {
      *parentNode = currentNode;
      currentNode = currentNode->leftChild;
    } else {
      *parentNode = currentNode;
      currentNode = currentNode->rightChild;
    }
  }

  return currentNode;
}

// BST的插入


void bstInsert(BinarySearchTree *bst, int insertValue) {
  // 1，在二分搜索树中查找待插入的元素
  BinarySearchTree parentNode;
  BinarySearchTree toInsertNode = bstSearch(*bst, insertValue, &parentNode);

  // 2，如果能够找到待插入的元素，则直接略过；如果不能找到待插入的元素，则新建节点并插入到BST中
  if (!toInsertNode) {
    // 2.1，新建节点
    struct BSTNode *node = malloc(sizeof(BSTNode));
    node->data = insertValue;
    node->leftChild = node->rightChild = NULL;

    // 2.2，如果原BST是空树，那么将新节点设置为BST的根节点
    if (!parentNode) {
      *bst = node;
      return;
    }

    // 2.3，按照左小右大进行子节点的插入
    if (parentNode->data > insertValue) {
      parentNode->leftChild = node;
    } else if (parentNode->data < insertValue) {
      parentNode->rightChild = node;
    }
  }
}

#pragma mark - BST的元素删除


void bstDeleteNode(BinarySearchTree *toDeleteNode) {
  BinarySearchTree tempNode;
  if (!(*toDeleteNode)->leftChild) {
    // 1，待删除节点的左子节点为空，此时只需要将待删除节点指向其右子节点即可
    tempNode = *toDeleteNode;
    *toDeleteNode = (*toDeleteNode)->rightChild;
    free(tempNode);
  } else if (!(*toDeleteNode)->rightChild) {
    // 2，待删除节点的右子节点为空，此时只需要将待删除节点指向其左子节点即可
    tempNode = *toDeleteNode;
    *toDeleteNode = (*toDeleteNode)->leftChild;
    free(tempNode);
  } else {
    // 3，待删除节点的左右子节点都存在
    /*
     实际上，BST就是中序排序的。因此，待删除节点的左子树中的最后侧的节点就是该左子树中值最大的节点，也就是待删除节点的前驱结点；待删除节点的右子树中的最左侧的节点就是该右子树中值最小的节点，也就是待删除节点的后继节点。
     如果要删除待删除节点toDeleteNode，那么其实是可以将待删除节点的前驱结点或者后继节点填充到该位置的，这里是以填充前驱结点为例进行讲解。
     注意咯，这里的【待删除节点toDeleteNode】是不会真正销毁的，我们选取一个合适的节点preNode来填充到该位置，然后调整preNode的双亲节点的指向，并将preNode销毁。【待删除节点toDeleteNode】只是名义上的移除，真正销毁的是填充到待删除节点位置上的前驱结点preNode。
     */
    // 3.1，找寻中序排序下的前驱结点，以及前驱结点的双亲结点
    BinarySearchTree preNode = (*toDeleteNode)->leftChild;
    BinarySearchTree parentOfPreNode = *toDeleteNode;
    while (preNode->rightChild) {
      preNode = preNode->rightChild;
      parentOfPreNode = preNode;
    }
    // 3.2，判断前驱结点的双亲节点的双亲节点是否为待删除节点自身
    tempNode = preNode;
    (*toDeleteNode)->data = preNode->data; // 将前驱结点的值填充到待删除节点的位置
    if (parentOfPreNode == *toDeleteNode) {
      /*
       3.2.1 如果待删除节点的前驱节点的双亲结点是待删除节点自身，说明待删除节点的左子节点是没有右子树的，此时将待删除节点的左子节点的值填充到待删除节点的位置，并且将待删除节点指向其左子节点的左子节点，然后删除待删除节点的左子节点即可。
       */
      (*toDeleteNode)->leftChild = preNode->leftChild;
    } else {
      /*
       3.2.2 如果待删除节点的前驱结点的双亲节点不是待删除节点自身，那么说明待删除节点的左子节点是有右子树的，并且该前驱节点没有右子节点，此时需要将前驱节点的值赋值到待删除节点中，并且将前驱结点的双亲结点的右子节点指向前驱结点的左子节点，最终销毁该前驱节点。
       */
      parentOfPreNode->rightChild = preNode->leftChild;
    }
    free(tempNode);
  }
}


void bstDelete(BinarySearchTree *bst, int toDeleteValue) {
  // 递归查找待删除的节点元素，如果找到指定元素，则删除；如果没有找到指定元素，则提示删除失败
  if (!*bst) {
    printf("删除失败，失败原因：未找到指定元素节点\n");
    return;
  }
  
  if ((*bst)->data == toDeleteValue) {
    bstDeleteNode(bst);
  } else if((*bst)->data > toDeleteValue) {
    bstDelete(&(*bst)->leftChild, toDeleteValue);
  } else {
    bstDelete(&(*bst)->rightChild, toDeleteValue);
  }
}

int main(int argc, const char * argv[]) {
  // insert code here...
  printf("Hello, World!\n");
  
  int originalArray[10] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
  
  BinarySearchTree binarySearchTree = NULL;
  for (int i = 0; i < 10; i++) {
    bstInsert(&binarySearchTree, originalArray[i]);
  }
  
  BinarySearchTree parentNode;
  BinarySearchTree searchNode = bstSearch(binarySearchTree, 35, &parentNode);
  if (searchNode) {
    printf("搜索节点%d成功\n", searchNode->data);
  } else {
    printf("搜索节点失败\n");
  }
  
  bstDelete(&binarySearchTree, 74);
  searchNode = bstSearch(binarySearchTree, 73, &parentNode);
  if (searchNode) {
    printf("搜索节点%d成功\n", searchNode->data);
  } else {
    printf("搜索节点失败\n");
  }
  
  return 0;
}