iOS 数据结构与算法

一、数据结构

• 1、集合结构：无序、无重复的元素结构，可看成特殊的数组（没有顺序，并且数据元素不重复）

• 2、线性结构：
  a、集合中必然存在一个唯一的一个第一元素；
  b、集合中必然存在一个唯一的一个最后元素
  c、除了最后一个元素之外，其他元素均有唯一的后继
  d、除了第一个元素之外，其他元素均有唯一的前驱

• 3、树形结构：元素存在一对多的树形关系的数据结构，是重要的非线性数据结构
  

• 4、图形结构：节点的前驱和后继的个数没有限制，类似这样的结构称之为图形数据结构
  

二、数据结构的存储

• 1、顺序存储结构：连续的内存地址，比如数组

• 2、链式存储结构
  a、单向链表
  

b、双向链表

c、循环链表

• 3、二叉树/平衡二叉树（五种形式二叉树：a、没有节点，空二叉树；b、只有根节点；c、只有左子树；d、只有右子树；e、有左右子树）
  

二、算法例子

• 1、不使用中间变量交换两个变量的值

void exchangeWithPlus(int a,int b){
        a = a + b;
        b = a - b;
        a = a - b;
}
void exchangeWithXor(int a,int b){
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
}

• 2、求最大公约数
  a、直接遍历法

//swift语言
func normalMaxCommonDivisor(a:Int,b:Int) -> Int{
        let r = a > b ? b : a
        var result = 1
        for i in 2..<r+1{
            if a % i == 0 && b % i == 0{
                result = i
            }
        }
        return result
}

b、辗转相除法：（若a=b*r+q，则gcd(a,b)=gcd(b,q)，可自行查找验证）

//swift语言
func tossAndTurnDivisor(a:Int,b:Int) -> Int{
        var ta = a,tb = b
        var resullt = tb
        while ta % tb != 0 {
            resullt = ta % tb
            ta = tb
            tb = resullt
        }
        return resullt
}

c、选择排序：最值出现在起始端（第一趟：在n个数中找到最小/最大的数值与第一个交换；第二趟：在剩下n-1个数中找到最小/最大的数值与第二个数交换；依此类推）

//swift
func selectSort(arr:[Int]) -> [Int]{
        var tArr = arr
        let count = tArr.count
        for i in 0..<count{
            for j in i..<count{
                if tArr[i] > tArr[j]{
                    let temp = tArr[i]
                    tArr[i] = tArr[j]
                    tArr[j] = temp
                }
            }
        }
        return tArr
}

d、冒泡排序：相邻两个元素两两比较，比较完一趟，最值出现在末尾（第 1 趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第 n 个元素位置；第 2 趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第 n-1 个元素位置；以此类推）

//swift
func bubbleSort(arr:[Int]) -> [Int]{
        var tArr = arr
        let count = tArr.count
        for i in 0..<count{
            for j in 1..<count-i{
                if tArr[j-1] > tArr[j]{
                    let temp = tArr[j-1]
                    tArr[j-1] = tArr[j]
                    tArr[j] = temp
                }
            }
        }
        return tArr
}

e、快速排序：从数列中挑出一个元素，称为 “基准”（pivot）;重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

//swift
//使用例子：quickSort(arr: arr, start: 0, end: arr.count-1)
func quickSort(arr:[Int],start:Int,end:Int) -> [Int]{
        if start >= end{
            return arr
        }
        var tArr = arr
        var base = start
        var offsetI=start,offsetJ=end
        while offsetI<offsetJ {
            while offsetJ >= offsetI && tArr[offsetJ] >= tArr[base] {
                offsetJ = offsetJ - 1
            }
            if offsetJ>=offsetI{
                let temp = tArr[offsetJ]
                tArr[offsetJ] = tArr[base]
                tArr[base] = temp
                base = offsetJ
                offsetJ = offsetJ - 1
            }
            while offsetJ >= offsetI && tArr[offsetI] <= tArr[base] {
                offsetI = offsetI + 1
            }
            if offsetI <= offsetJ{
                let temp = tArr[base]
                tArr[base] = tArr[offsetI]
                tArr[offsetI] = temp
                base = offsetI
                offsetI = offsetI + 1
            }
        }
        let ttarr = quickSort(arr: tArr, start: start, end: base-1)
        let rarr = quickSort(arr: ttarr, start: base+1, end: end)
        return rarr
}

f、折半查找（二分查找）:折半查找：优化查找时间（不用遍历全部数据） 折半查找的原理：1> 数组必须是有序的；2> 必须已知 min 和 max（知道范围）；3> 动态计算 mid 的值，取出 mid 对应的值进行比较；4> 如果 mid 对应的值大于要查找的值，那么 max 要变小为 mid-1；5> 如果 mid 对应的值小于要查找的值，那么 min 要变大为 mid+1；

//swif
// 已知一个有序数组, 和一个 key, 要求从数组中找到 key 对应的索引位置
//使用例子：binarySearch(arr: arr, start: 0, end: result.count, key: keyValue)
func binarySearch(arr:[Int],start:Int,end:Int,key:Int){
        if start >= end{
            print("找不到该该值的位置")
            return
        }
        let midle = (start + end) / 2
        let midleValue = arr[midle]
        if midleValue < key{
            binarySearch(arr: arr, start: midle+1, end: end, key: key)
        }else if midleValue > key{
            binarySearch(arr: arr, start: start, end: midle-1, key: key)
        }else{
            print("index:\(midle)")
            return
        }
}

g、字符串反转

//swift
func reverseString(originalString:String) -> String{
        var arr = Array(originalString)
        let count = arr.count
        for i in 0..<count/2{
            arr.swapAt(i, count-1-i)
        }
        return String(arr)
}

h、有序数组合并

//swift
func sortArrayCombine(arrA:[Int],arrB:[Int]) -> [Int]{
        if arrA.count <= 0{
            return arrB
        }
        if arrB.count <= 0{
            return arrA
        }
        var resultArr = [Int]()
        var i = 0, j = 0
        let aCount = arrA.count,bCount = arrB.count
        while i < aCount && j < bCount {
            while j < bCount && arrA[i] >= arrB[j] {
                resultArr.append(arrB[j])
                j = j + 1
            }
            while i < aCount && arrA[i] <= arrB[j] {
                resultArr.append(arrA[i])
                i = i + 1
            }
        }
        if i >= aCount{
            while j < bCount {
                resultArr.append(arrB[j])
                j = j + 1
            }
        }
        if j >= bCount{
            while i < aCount {
                resultArr.append(arrA[i])
                i = i + 1
            }
        }
        return resultArr
}

i、hash算法：哈希表 例：给定值是字母 a，对应 ASCII 码值是 97，数组索引下标为 97。 这里的 ASCII 码，就算是一种哈希函数，存储和查找都通过该函数，有效地提高查找效率。在一个字符串中找到第一个只出现一次的字符。如输入"abaccdeff"，输出’b’字符(char)是一个长度为 8 的数据类型，因此总共有 256 种可能。每个字母根据其 ASCII 码值作为数组下标对应数组种的一个数 字。数组中存储的是每个字符出现的次数。

//swift
func hashFindFindFisrtOneCharacter(string:String) -> String{
        let strArr = Array(string)
        var sult = [Int]()
        for _ in 0..<256{
            sult.append(0)
        }
        for ch in strArr{
            let tStr = String(ch)
            let index = tStr.unicodeScalars.first!.value
            sult[Int(index)] = sult[Int(index)] + 1
        }
        for i in 0..<sult.count{
            if sult[i] == 1{
                let ch = Character(UnicodeScalar(i)!)
                return String(ch)
            }
        }
        return ""
}

j、查找两个视图的共同父视图:分别记录两个子视图的所有父视图并保存到数组中，然后倒序寻找,直至找到第一个不一样的父视图

func findFaterView(subView:UIView) -> [UIView]{
        var resultArr = [UIView]()
        var temp = subView.superview
        while temp != nil {
            resultArr.append(temp!)
            temp = temp!.superview
        }
        return resultArr
    }
    
    func findTwoViewCommonFathers(viewOne:UIView,viewTwo:UIView) -> [UIView]{
        let viewOneFathers = findFaterView(subView: viewOne)
        let viewTwoFathers = findFaterView(subView: viewTwo)
        var i = 0
        let oneCount = viewOneFathers.count,twoCount = viewTwoFathers.count
        let count = min(oneCount, twoCount)
        var result = [UIView]()
        while i < count {
            let view1 = viewOneFathers[oneCount-i-1]
            let view2 = viewTwoFathers[twoCount-i-1]
            if view1 == view2{
                result.append(view1)
            }else{
                break
            }
            i = i + 1
        }
        return result
    }