C++ Basic Data Structure Part2

basic data structure and algorithm part2

树

  • trie树
    • 特点
      • 根节点没有字符，除此之外，所有节点都只有一个字符
      • 从根节点到任意叶子节点，都是一个独立的单词
      • 每个节点的子节点包含的后续字符串都是不一样的
    • 但是hash表不能一边建立索引一边查数据
      • trie树可以
        • 因为只要之前建立过的，再次出现的时候，就不会再增加
      • 而hash表建立的时候，不知道之前这个单词出现过，所以还是要建完表
        • 再搜索

内排序

  • O(n2)

    • 主要是交换那个动作耗时
    • 冒泡排序
    • 插入排序
    • 选择排序

  • 快速排序

    • 时间复杂度：nlogn
    • 最坏：n2
      • 把区域划分成n-1和1
    • 空间复杂度：nlogn
    • 所以其实要解释快排是什么
      • 就是选一个中间值
        • 把比这个中间值小的放到左边
        • 把比这个中间值大的放到右边
        • 然后分别对这两个子数组递归调用快速排序
        • 最后的出来的就是排序好的
    • 思想：
      • 对于A[p….r]
      • 基于分而治之
      • 首先
        • A[p….r]被分解成两个子数组
          • 一个是A[p….q-1]，一个是A[q+1…..r]
          • 然后递归调用对A[p…q-1]和A[q+1…..r]排序
        • 最后合并子数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

void quicksort(int *a, int low, int upp){
  //low和upp为数组的上界和下界
  int i = low;
  int j = upp;
  int mid = (low + upp)/2;
  //设置pivot用作对比
  int pivot = a[mid];
  int temp;
  //partition
  do{
      while(a[i] < pivot)
          i++;
      while(a[j] > pivot)
          j--;
      if(i <= j){
          swap(a[i], a[j]);
          i++;
          j--;
      }
  }while(i < j);
  //递归调用解决子问题
  if(low < j)
      quicksort(a, low, j);
  if(i < upp)
      quicksort(a, i, upp);
}
int main(){
  int a[10] = {1,5,4,3,6,5,3,4,5,3};
  for(int i = 0; i < 10; i++){
      cout<<a[i]<<" ";
  }
  cout<<endl;
  quicksort(a, 0, 9);
  for(int i = 0; i < 10; i++){
      cout<<a[i]<<" ";
  }
  return 0;
}
  • 归并排序
  • 基本思想：
    • 分而治之
    • 先通过递归分解数组，然后再合并数组完成归并排序
  • 如何合并两个有序数组
    • 比较两个数列的第一个数，把小的那个加入到结果数组中，然后从原来的数组删掉
    • 然后一直循环比较到全部数据都取出来为止 “`

“`

归并和快排的区别

  • 快排分解之后不需要合并就能得到最终答案
  • 归并分解之后还要对比两个子数组然后合并的到答案

外排序

  • 适合在内存不够的时候用
  • 把一个大文件分割成很多小文件
    • 然后依次把每个小文件放入内存排序
    • 排序完之后，再存入文件中
    • 最后就会得到很多排好序的小文件
  • 然后用多路归并，对比每个文件的第一个，把最小的放到一个结果文件中
    • 然后把这个元素在原本的文件中删掉
  • 得到的结果文件就是结果

哈希表

  • 建立hash表
    • 用hash函数把key转换成一个整型数字，这个整型数字对数组长度求模之后就是数组的下标
      • 那么value就存在这个下表的数组空间里面

  • 查询hash表

    • 把要查询的key用hash函数转换成数组下标，再去数组里面提取
    • O(N)非常快

  • 假设有1000万个记录，有重复，去除重复之后大约300万

    • 求top 10出现率的记录
    • 解答：
      • 用hash表
        • 维护一个<记录，出现次数>的hash表
          • 这样就有一个300万条左右记录的hash表
          • 再找前十就行了
      • 找前10可以用部分排序
        • 也就是用一个10个大小的数组
          • 然后搜hash表，每次都和数组最后的那个比
            • 如果比他大，就交换

  • 把key变成下表的方法

    • 1.对key求模
      • index = value % 16
    • 2.平方散列
      • index = (value * value) >> 28
        • 右移28bit是指除以228
  • 如果两个value在hash表中对应同一个index怎么办？
    • 可以用链表解决
      • 这样就不会有冲突产生

索引

  • 线性索引

    • 索引文件是一个线性的列表
    • 并且列表中的每个元素都对应者数据库中的一个元素
      • 或者数据库的某个位置
    • 但是有时候索引文件太大，装不进内存
      • 那么解决方案就是用二级索引
        • 这个二级索引是索引文件的索引
    • 但是每个数据库更新的时候
      • 所有的索引文件都要更新，但是线性索引的代价很大

  • ISAM

  • 树状索引
    • B树
      • balance tree
      • b树的搜索
        • 对根节点进行二分查找
    • B+树
      • B树的变种
      • 叶子节点存数据
      • 非叶子节点存索引
      • 好处
        • 因为B+树内部只是存索引，不像B树是存数据的
          • 因此B+树I/O读写次数降低了
        • 查找效率稳定
          • 因为所有非叶子节点都是索引
          • 因此数据都在叶子节点上，因此关键字查询的路径相同
          • 因此每一个数据的查找效率相当
algorithm, c++
Comments

Comments