数据结构&算法

常见数据结构初探
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
简单来说：数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的，而对于其他操作则是低效的。

最常见的数据结构：
1、数组：
可以在内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始

NSArray = @[@"123",@"456"];

优点：
1、按照索引查询元素速度快
2、按照索引遍历数组方便

缺点：
1、数组的大小固定后就无法扩容了
2、数组只能存储一种类型的数据
3、添加，删除的操作慢，需移动其他的元素

使用场景：频繁查询，对存储空间要求不大，很少增加和删除的情况

2、链表:
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。
头结点

屏幕快照 2019-07-03 上午10.17.52.png
image.png
image.png

优点：增删快
缺点：查询繁琐

3、双向链表：
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

⚠️autoreleasepool是典型的双向链表

屏幕快照 2019-07-03 上午10.37.11.png
image.png

优点：
很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；

缺点：
因为含有大量的指针域，占用空间较大；
查找元素需要遍历链表来查找，非常耗时。

适用场景：
数据量较小，需要频繁增加，删除操作的场景

4、线性表：
线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）

5、树:
树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。具有以下的特点：
1）每个节点有零个或多个子节点
2）没有父节点的节点称为根节点
3）每一个非根节点有且只有一个父节点
4）除了根节点外，每个子节点可以分为多个不相交的子树
⚠️二叉树。
二叉树-遍历-顺序-反转

image.png
二叉树是树的特殊一种，具有如下特点：

1、每个结点最多有两颗子树，结点的度最大为2。
2、左子树和右子树是有顺序的，次序不能颠倒。
3、即使某结点只有一个子树，也要区分左右子树。

二叉树属于折中方案，添加、删除元素很快，在查找方面有很多算法优化，因此，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。

二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等，这些数据结构在二叉树的基础上衍生了很多的功能，在实际应用中广泛用到，例如mysql的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树

6、队列：
队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队

屏幕快照 2019-07-03 上午10.32.37.png
queue-任务-由线程调度执行

7、栈：
栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈

屏幕快照 2019-07-03 上午10.29.43.png

8、堆：
堆的定义：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)，
满足前者的表达式的成为小顶堆，满足后者表达式的为大顶堆，这两者的结构图可以用完全二叉树排列出来

堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

image.png
image.png

9、散列表：

image.png
左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，
当然这个链表可能为空，也可能元素很多。
我们根据元素的一些特征把元素分配到不同的链表中去，
也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

散列表，也叫哈希表，是根据关键码和值 (key和value)直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。

记录的存储位置=f(key)

这里的对应关系f 成为散列函数，又称为哈希 (hash函数)，而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，
然后就将该数字对数组长度进行取余，取余结果就当作数组的下标

将value存储在以该数字为下标的数组空间里

这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。

哈希表在应用中也是比较常见的，就如Java中有些集合类就是借鉴了哈希原理构造的，例如HashMap，HashTable等，利用hash表的优势，对于集合的查找元素时非常方便的，然而，因为哈希表是基于数组衍生的数据结构，在添加删除元素方面是比较慢的，所以很多时候需要用到一种数组链表来做，也就是拉链法。拉链法是数组结合链表的一种结构，较早前的hashMap底层的存储就是采用这种结构，直到jdk1.8之后才换成了数组加红黑树的结构.iOS中weak表（弱引用表）就是典型的哈希表

10、哈希：
hash又称为散列函数
⚠️字典的底层就是哈希
哈希函数为自定义函数，在定义哈希函数时应遵循计算简单、分布均匀等原则。、
例如：直接地址法:kaka:189****3333根据数据来定义函数。
数据分析法:189****3333当后四位3333发生变化时，将后四位直接存储。
平方取中法：
9 13 14 15 16 18
81 169 196 225 256 324---------225和324都有2 这就是著名的哈希冲突

哈希冲突解决方法：
1 、继续哈希法-哈希函数f(f())。判断位置平方法位移解决冲突
2、拉链法

屏幕快照 2019-07-03 下午2.05.38.png

11 12 22 23 25
取余法:
9 13 14 15 16 18 %10
9 3 4 5 6 8

static weak_entry_t *
weak_entry_for_referent(weak_table_t *weak_table,objc_object (referent){
    assert(referent);
    weak_entry_t *weak_entries = weak_table->weak_entries;
    if(!weak_entries) return nil;
    
    size_t begin = hash_pointer(referent) & weak_table->mask;
    size_t index = begin;
    size_t hash_displancement = 0;
    while (weak_table->weak_entries[index].referent !=referent){
              //哈希函数
              index = (index+1) & weak_table->mask;
              if(index == begin) bad_weak_table(weak_table->weak_entries);
              hash_displancement++;
              if(hash_displancement > weak_table->max_hash_displacement){
                  return nil;
              }
    }
      //哈希
     return &weak_table->weak_entries[index];
}

//hash_pointer 
#if __LP64__
static inline unit32_t prt_hash(unit64_t key){
        key ^= key >>4;
        key *=0x8a970be7488fda55;
        key ^=__builtin_bswap64(key);
        return (unit32_t)key;
}
#else
static inline unit32_t prt_hash(unit32_t key){
      key ^= key >>4;
        key *=0x5052acdb;
        key ^=__builtin_bswap32(key);
        return key;
}
endif

算法
1、字符串翻转
Hello，world =========翻转结果为Drow,olleh
解题思路：两个变量记录、移动、换值、指针

void char_reverse(char * cha){
        //定义第一个字符
        char * begin = cha;
        //定义末尾字符
        char * end = cha+strlen(cha) - 1;
        while (begin < end){
                  //核心逻辑 ---值换 移动
                  char lg_tmp = * begin;
                  *(begin++) = end;
                  *(end--) = lg_tmp;       
        }
}
char ch[] = @"Hello，world";
char_reverse(ch);

2、链表翻转

//定义链表
struct LGNode{
      int data;
      struct LGNode *next;
};

//链表翻转
strut LGNode *reverList(struct LGNode* head);
//构造一个链表
struct LGNode *constructList(void);
//打印链表中的数据
void ld_printList(struct LGNode * head);

strut LGNode *reverList(struct LGNode* head){
      //定义遍历指针，初始化为头节点
      struct LGNode *p = head;
      //翻转后的链表头部
      struct LGNode * newH = NULL; 
      //遍历链表
      while (p !=NULL){
      //记录下一个节点
      struct LGNode * temp = p->next;
      //当前节点的next指向新链表头部
      p ->next = newH;
      //更改新链表头部为当前节点
      newH = p;
      //移动p指针
      //p = temp; 
     }
      //返回翻转后的链表头节点
      return newH;
}

struct LGNode *constructList(void){
       //头节点定义
       struct LGNode *head = NULL;
       //记录当前尾节点
       struct LGNode *cur = NULL;
       
        for (int I = 1;i<5,i++){
               struct LGNode *node = malloc(sizeof(struct LGNode));
               node->data = I;
               //头节点为空，新节点即为头节点
               if (head == NULL){
                    head = node;
               }
                //当前节点的next为新节点
               else{
                      cur->next = node;
               }
               //设置当前节点为新节点
               cur = node;
        }
        return head;
}

void lg_printList(struct LGNode *head)
{
    struct LGNode* lg_temp = head;
    while (lg_temp != NULL) {
        NSLog(@"结点数据: %d",lg_temp->data);
        lg_temp = lg_temp->next;
    }
}

 NSLog(@"*****************链表反转*****************");
 struct LGNode* head = constructList(); //  1 2 3 4 5
 lg_printList(head);
 NSLog(@"------------------------------");
 struct LGNode* newHead = reverseList(head);
 lg_printList(newHead);

3、有序数组合并

// 将有序数组a和b的值合并到一个数组result当中，且仍然保持有序
void mergeList(int a[_Nullable], int aLen, int b[], int bLen, int result[]);

void mergeList(int a[], int aLen, int b[], int bLen, int result[])
{
    int p = 0; // 遍历数组a的指针
    int q = 0; // 遍历数组b的指针
    int i = 0; // 记录当前存储位置
    
    // 任一数组没有到达边界则进行遍历
    while (p < aLen && q < bLen) {
        // 如果a数组对应位置的值小于b数组对应位置的值
        if (a[p] <= b[q]) {
            // 存储a数组的值
            result[i] = a[p];
            // 移动a数组的遍历指针
            p++;
        }
        else{
            // 存储b数组的值
            result[i] = b[q];
            // 移动b数组的遍历指针
            q++;
        }
        // 指向合并结果的下一个存储位置
        i++;
    }
    
    // 如果a数组有剩余
    while (p < aLen) {
        // 将a数组剩余部分拼接到合并结果的后面
        result[i] = a[p++];
        i++;
    }
    
    // 如果b数组有剩余
    while (q < bLen) {
        // 将b数组剩余部分拼接到合并结果的后面
        result[i] = b[q++];
        i++;
    }
}

        NSLog(@"*****************有序数组合并*****************");
        int array1[6] = {1,3,12,23,30,50};
        int array2[8] = {2,5,11,20,28,60,67,87};

        // 用于储存归并结果
        int result[14];
        // 合并结果
        mergeList(array1, 6, array2, 8, result);
        for (int i = 0; i<13; i++) {
            NSLog(@"结果输出:%d",result[i]);
        }

4、哈希算法--查找第一个只出现一次的字符

// 查找第一个只出现一次的字符 --- 
char findFirstChar(char* cha);

char findFirstChar(char* cha)
{
    char result = '\0';
    // 定义一个数组 用来存储各个字母出现次数
    int array[256];
    // 对数组进行初始化操作
    for (int i=0; i<256; i++) {
        array[i] = 0;
    }
    // 定义一个指针 指向当前字符串头部
    char* p = cha;
    // 遍历每个字符
    while (*p != '\0') {
        // 在字母对应存储位置 进行出现次数+1操作
        array[*(p++)]++;
    }
    
    // 将P指针重新指向字符串头部
    p = cha;
    // 遍历每个字母的出现次数
    while (*p != '\0') {
        // 遇到第一个出现次数为1的字符，打印结果
        if (array[*p] == 1)
        {
            result = *p;
            break;
        }
        // 反之继续向后遍历
        p++;
    }
    
    return result;
}

       NSLog(@"*****************查找第一个只出现一次的字符*****************");
        char cha[] = "abcabh"; // c
        char fc = findFirstChar(cha);
        NSLog(@"%c",fc);

5、求两个子视图的公共父视图

// 查找两个视图的共同父视图
 - (NSArray<UIView *> *)findCommonSuperView:(UIView *)view other:(UIView *)viewOther;

- (NSArray <UIView *> *)findCommonSuperView:(UIView *)viewOne other:(UIView *)viewOther
{
    NSMutableArray *result = [NSMutableArray array];

    // 查找第一个视图的所有父视图
    NSArray *arrayOne = [self findSuperViews:viewOne];
    // 查找第二个视图的所有父视图
    NSArray *arrayOther = [self findSuperViews:viewOther];

    int i = 0;
    // 越界限制条件
    while (i < MIN((int)arrayOne.count, (int)arrayOther.count)) {
        // 倒序方式获取各个视图的父视图
        UIView *superOne = [arrayOne objectAtIndex:arrayOne.count - i - 1];
        UIView *superOther = [arrayOther objectAtIndex:arrayOther.count - i - 1];

        // 比较如果相等 则为共同父视图
        if (superOne == superOther) {
            [result addObject:superOne];
            i++;
        }
        // 如果不相等，则结束遍历
        else{
            break;
        }
    }
    return result;
}

- (NSArray <UIView *> *)findSuperViews:(UIView *)view
{
    // 初始化为第一父视图
    UIView *temp = view.superview;
    // 保存结果的数组
    NSMutableArray *result = [NSMutableArray array];
    while (temp) {
        [result addObject:temp];
        // 顺着superview指针一直向上查找
        temp = temp.superview;
    }
    return result;
}


- (instancetype)mas_closestCommonSuperview:(UIView *)view {

    UIView *closestCommonSuperview = nil;
    UIView *secondViewSuperview = view;

    while (!closestCommonSuperview && secondViewSuperview) {
        UIView *firstViewSuperview = self;

        while (!closestCommonSuperview && firstViewSuperview) {

            if (secondViewSuperview == firstViewSuperview) {
                closestCommonSuperview = secondViewSuperview;
            }
            firstViewSuperview = firstViewSuperview.superview;
        }
        secondViewSuperview = secondViewSuperview.superview;
    }
    return closestCommonSuperview;
}

6、从无序数组中找到中位数

// 无序数组中位数查找
int lg_findMedian(int a[_Nullable], int aLen);

//求一个无序数组的中位数
int lg_findMedian(int a[], int aLen)
{
    int low = 0;
    int high = aLen - 1;
    
    int mid = (aLen - 1) / 2;
    int div = lg_partSort(a, low, high);
    
    while (div != mid)
    {
        if (mid < div)
        {
            //左半区间找
            div = lg_partSort(a, low, div - 1);
        }
        else
        {
            //右半区间找
            div = lg_partSort(a, div + 1, high);
        }
    }
    //找到了
    return a[mid];
}

int lg_partSort(int a[], int start, int end)
{
    int low = start;
    int high = end;
    
    //选取关键字
    int key = a[end];
    
    while (low < high)
    {
        //左边找比key大的值
        while (low < high && a[low] <= key)
        {
            ++low;
        }
        
        //右边找比key小的值
        while (low < high && a[high] >= key)
        {
            --high;
        }
        
        if (low < high)
        {
            //找到之后交换左右的值
            int temp = a[low];
            a[low] = a[high];
            a[high] = temp;
        }
    }
    
    int temp = a[high];
    a[high] = a[end];
    a[end] = temp;
    
    return low;
}

int list[9] = {5,3,10,8,6,7,30,13,9};
int median = lg_findMedian(list, 9);
NSLog(@"中位数 %d ", median);