iOS 数据结构与算法
一、数据结构
1、集合结构：无序、无重复的元素结构，可看成特殊的数组（没有顺序，并且数据元素不重复）
2、线性结构：
a、集合中必然存在一个唯一的一个第一元素；
b、集合中必然存在一个唯一的一个最后元素
c、除了最后一个元素之外，其他元素均有唯一的后继
d、除了第一个元素之外，其他元素均有唯一的前驱-
3、树形结构：元素存在一对多的树形关系的数据结构，是重要的非线性数据结构
image.png
-
4、图形结构：节点的前驱和后继的个数没有限制，类似这样的结构称之为图形数据结构
image.png
二、数据结构的存储
1、顺序存储结构：连续的内存地址，比如数组
-
2、链式存储结构
a、单向链表
image.png
b、双向链表
c、循环链表
-
3、二叉树/平衡二叉树（五种形式二叉树：a、没有节点，空二叉树；b、只有根节点；c、只有左子树；d、只有右子树；e、有左右子树）
image.png
二、算法例子
- 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
}
- 转载请标明出处
- 如有错误理解，还请各路大神批评指出
