/**

 *创建函数

 * 参数是String,返回值是String。其中参数和返回值都是可选的,但是如果有参数,或者有return,则是必须的

 */

func sayHello(name:String)->String{

    return "Hello "+name+"."

}

println(sayHello("lane"))


func sayHelloOptional(name:String?)->String{

    var result = "Hello," + (name ?? "Guest")

    return result

}

var name:String?

println(sayHelloOptional(name))


/**

 *函数和元组

 * 参数是String,返回值是String。其中参数和返回值都是可选的

 */

func maxMinScores( scores:[Int] )->( maxScore:Int, minScore:Int)?{

    if scores.isEmpty{

        return nil

    }

    var curmax = scores[0]

    var curmin = scores[0]

    for score in scores[1..<scores.count]{

        curmax = max(curmax, score)

        curmin = min(curmin, score)

    }

   //两种返回方式

    return (maxScore:curmax, minScore:curmin)

   //两种返回方式

   //return (curmax, curmin)

}


var userScores:[Int]? = [12, 990, 572, 3258, 9999, 1204]

userScores=userScores?? []

if let maxMin = maxMinScores(userScores!){

    maxMin.maxScore

    maxMin.minScore

}


/**

 *值传递、引用、默认情况

 */

//默认下不能对参数修改,只能读取。此时参数被称为常数参数

func paramTest(varName:Int)->Int{

    var sum = varName*2;

   //报错,不能对参数修改,只能读

   //varName--;

    return sum

}

//值传递,可读可写,变量前面加一个var

func paramTest1(var varName:Int)->Int{

    var sum = varName*2;

   //这个时候下句不报错了。

    varName--;

    return sum

}

//引用,可读可写,变量前面加一个inout,使用时加&

func paramTest2(inout varName:Int)->Int{

    var sum = varName*2;

   //这个时候下句不报错了。

    varName--;

    return sum

}

var param = 10;

paramTest(param)

//param = 10

paramTest1(param)

//param = 10

paramTest2(&param)

//param = 9



/**

 *函数类型

 */

func add(a:Int, b:Int)->Int{

    return a+b

}

//隐式声明一个函数类型

let funcVar = add

add(3, 4)

//显式声明一个函数类型

let funcVar2:(Int, Int)->Int = add

//显式声明一个不需要参数和返回值的函数类型

func voidFunc(){

   println("hello world")

}

//let funcVar3:()->() = voidFunc

let funcVar4:()->Void = voidFunc


/**

 *函数嵌套

 */

func sum(a:Int, b:Int)->Int{

    func num(c:Int)->Int{

        return c*c

    }

    return num(a) + num(b)

}

sum(10, 20)


/**

 *返回函数类型的函数

 */

func func1(a:Int)->String{

    return "结果是"+String(a * a)

}

func func2(a:Int)->String{

    return "结果是"+String(a + a)

}

func choseFunc(a:Int)->(Int)->String{

    var result:(Int)->String

    if a%2==0 {

        result = func1

    }else{

        result = func2

    }

    return result

}

var funcName = choseFunc(10)

funcName(10)

funcName=choseFunc(5)

funcName(5)




    Swift条件控制,有for,for...in...,switch,if...else,while等,而跳出条件控制有break,continue,fallthrough。本篇文章变分析这几个控制的特性。

    for in相关的如下:

/**

* for - in 循环

*/

//for循环 >=-10 <=10

for i in -10...10{

    i*i

}

//遍历一个数组

var arr = ["a", "b", "c"]

for a in arr{

    println(a)

}

for (key, value) in enumerate(arr){

    println("\(key):\(value)")

}

//遍历一个字典

vardict = ["a":"A","b":"B","c":"C"]

for (key, value) in dict{

    println("\(key):\(value)")

}

    for相关的如下:

/**

* for 循环

*/

//等同for var i = -100; i<=100; i++

var i = -10

for ; i<=10; i++

{

    i*i

}

    if相关的如下:

//if else

iftrue{

    

}else{

    

}

    switch相关的如下:

/**

 *switch,可以对IntStringBoolFloatDouble进行判断

 *

 *不需要显式写break;

 */

var switchValue = "a"

switchswitchValue{

    case "a":

        println("a")

    case "b":

        println("b")

   default:

        println("d")

}

//判断多个值不能写:

//case "a":

//case "A":

//  println("ok");

//而是应该写:

//case "a", "A":

    switch高级特性相关的如下:

/**

 * switch高级特性

 */

//元组在switch

//如果想执行第一个case后还想执行第二个case,则添加fallthrough,此时直接进入下面的语句,不进行case判断

var request = (true, "success")

switchrequest{

   //这个是正确的

    case (true, "success"):

       println("true, success")

       fallthrough

   //这个也是正确的,可以忽略元组的第一个元素,将剩下的元素判断

    case (true, _):

       println("true, success")

   //这个也是正确的

    case (true, let requestStatus):

        println("当前登陆状态为:\(requestStatus)");

   default:

       println("not found!")

}

//switch可以比较范围

var request2 = (5, 12);

switchrequest2{

    case (1...8, 10...20):

        println("ok")

   default:

       println("not found!")

}

//switchcase中可以增加逻辑判断

var request3 = (3, 3)

switchrequest3{

    case let(x, y) where x==y:

        println("\(x)->\(y)")

   default:

       println("not found!")

}

    控制转移相关的如下,break只能跳出一层循环,如果要跳出多层,可以看下面的例子。另外break只能跳出循环,而不是花括号得代码块,比如if:

/**

 *控制转移

 * fallthroughbreakcontinue

 */

import UIKit

var board = Array<Array<Int>>()

for i in 0...10{

    board.append(Array(count:10, repeatedValue:0))

}

let x = Int(arc4random()%10)

let y = Int(arc4random()%10)

board[x][y] = 1

board

var i = 0, j = 0

mainloop:for i = 0; i<10; i++ {

    for j=0; j < 10; j++ {

        if board[i][j] == 1 {

            break mainloop

        }

    }

}

println("\(i)-\(j)")

    Swift的集合有两种,是数组和字典,显式声明和隐式声明、增删改查、基本操作等将在本文介绍。

/**

 *数组的初始化

 */

//数组只能存同一种数据类型

var array = ["a", "b", "c"]

array[0] = "A"

//显式的声明存储字符串的数组

var array2:[String] = ["a", "b", "c"]

var array3:Array<String> = ["a", "b", "c"]

//创建空数组,存储Int类型

var array4 = [Int]()

var array5 = Array<String>()

var array6:[Int] = []

var array7:Array<Int> = []

//清空数组,清空后,后期仍然只能使用之前定义的数据类型

array2 = []

array2 = [String]()

array2 = Array<String>()

//初始化,10个值,每个值都为0

var array8 = [Int](count:10, repeatedValue:0)

//数组合并

var array9 = [1, 2, 3]

var array10 = array8+array9



/**

 *数组的基本操作

 */

var array = ["A", "B", "C", "D"]

//数组的总数

array.count

//数组是否为空

array.isEmpty

//数组结尾加入新的元素

array.append("E")

array += ["F"]

array += ["G", "H"]

//数组任意位置加入新元素

array.insert("b", atIndex: 2)

//删除任意位置的元素,返回所删除的元素的值

array.removeAtIndex(1)

//删除最后一个元素

array.removeLast()

//删除所有元素

array.removeAll(keepCapacity: false)

//修改单个元素

array[0] = "AA"

//修改一组元素,若key为2...4,包含2,3,4三个key,而value只有一个,那么2,3,4三个值将只剩一个

array[2...4] = ["AA", "BB", "CC"]

array[2..<4] = ["AA", "bb"]

//遍历数组

for index in 0..<array.count{

    println("\(index) -> \(array[index])")

}

for item in array{

    println(item)

}

for (index, item) in enumerate(array){

    println("\(index) -> \(item)")

}



/**

 * 字典

 *键值对,可以是任意类型,但是一旦声明了一个字典,那么只能有一种搭配的类型。比如下面是键是Int,值是String。那么所有的键都必须是Int,所有的值都必须是String

 */

//隐式声明字典

var dictionary = [1:"a", 2:"b", 3:"c"]

//现式声明字典

var dictionary1:Dictionary<Int, String> = [1:"a", 2:"b", 3:"c"]

var dictionary2:[Int:String] = [1:"a", 2:"b", 3:"c"]

//声明空字典、清空一个已有的字典

var dictionary3 = Dictionary<Int, String>()

var dictionary4 = [Int, String]()

//清空字典的特殊表示

dictionary4 = [:]


/**

 *字典的基本操作

 */

//字典总数

var dictionary = [1:"a", 2:"b", 3:"c"]

dictionary.count

//字典是否为空

dictionary.isEmpty

//调用,传入的key可以是任意值,程序不会报错,因为返回的是optionalkey不存在时返回nil

dictionary[1]

"第一个元素:" + dictionary[1]!

//插入新元素

dictionary[4] = "d"

//修改元素两种方式

dictionary[4] = "e"

var oldValue = dictionary.updateValue("e", forKey: 4)

//删除元素两种方式

dictionary[4] = nil

var oldValue4 = dictionary.removeValueForKey(4)

//字典的遍历

for (key, value) in dictionary{

    println("\(key) -> \(value)")

}

//遍历key

Array(dictionary.keys)

[Int](dictionary.keys)

//遍历value

Array(dictionary.values)

[String](dictionary.values)

    堆是一种特殊的完全二叉树,是树的一种常见的应用,最简单的便是解决将无序的数列从大到小排列或者从小到大排列。性能极佳。

    堆分两种,一种是最大堆,即所有的父节点都大于它的两个子节点。另一种是最小堆,即所有的父节点都小于它的两个子节点。

    如果一组数列,是无序的,要将它有序的排列,那么:

min = 9999;

for(i=0; i<n; i++){

    if(num[i] < min){

        min = num[i];

    }

}

    这是最简单也是最高效的算法。可是,如果现在要删除最小数,在数列中插入一个任意一个数,此时再求最小值呢?那么就要重复上面的操作。那么问题来了,如果这个动作要重复100亿次呢?此时,时间复杂度就要100亿×数列的长度。即O(num.count*100亿)。这是不科学的,这个时候,我们引入了堆。

    最小堆的根节点永远是最小值!此时我们删掉了最小值,也就是根节点,在根节点的位置插入一个任意值,这个时候这个树就不是堆了,我们要把根节点向下移动,找到他合适的位置,也就是他要比他父节点大,比他的根节点小。此时这个树又恢复成了堆。

    现在有如下堆:

无标题.jpg


    堆的黑色数组表示节点的编号,在圈圈里。红色数组表示这个节点的值。我们现在要从小到大排列一个数列。也就是对红色数组进行排序。

    1、1号节点是根节点,永远是最小值,这是最小堆的特性。反之最大堆的根节点是最大值。

    2、将1号节点的值改变为新插入的任意值。

    3、将新插入的值向下移动,使树恢复为最小堆。和它的左子节点还有右子节点比较,若大,则交换位置。如此反复,直到不能再交换位置了。

    使用最小堆来从小到大排列一个无序数列的全部代码如下,时间复杂度为O(NLogN):

#include <stdio.h>

//存放堆

int h[100];

//存储堆的元素个数

int n;

//交换元素

void swap(int x, int y){

    int t;

    t = h[x];

    h[x] = h[y];

    h[y] = t;

}

//向下调整

void siftdown(int i){

    int t, flag=0;

    //判断该点的做儿子是否存在

    while(i*2 <= n && flag == 0){

        //如果左儿子存在,则判断是否交换值

        if(h[i] > h[i*2])

            t = i * 2;

        else

            t = i;

        //右儿子是否存在

        if(i*2+1 <= n && h[t] > h[i*2+1]){

            t = i*2+1;

        }

        //如果需要交换则交换

        if( t!= i){

            swap(t, i);

            i = t;

        //如果不需要交换,则准备退出while

        }else{

            flag = 1;

        }

    }

}

//向上调整,本函数本次将不会用到。

void siftup(int i){

    int flag = 0;

    while(i != 1 && flag == 0){

        if(h[i] < h[i/2]){

            swap(i, i/2);

            i = i/2;

        }else{

            flag = 1;

        }

    }

}

//创建堆

void create(){

    int i;

    for(i=n/2; i>=1; i--){

        siftdown(i);

    }

}

//获取最小的元素

int getMin(){

    int t;

    //堆顶(根节点)为最小值

    t = h[1];

    //删除根节点,把堆的最后一个元素赋给根节点

    h[1] = h[n];

    n--;

    //把根节点向下移动,使堆恢复最小堆

    siftdown(1);

    return t;

}

int main(){

    int i, num;

    scanf("%d", &num);

    for(i=1; i<=num; i++){

        scanf("%d", &h[i]);

    }

    n = num;

    //创建堆

    create();

    //讲堆从小到大排列

    for(i=1; i<=num; i++){

        printf("%d ", getMin());

    }

    return 0;

}


输入:

14

99 5 36 7 22 17 46 12 2 19 25 28 1 92

//输出:

1 2 5 7 12 17 19 22 25 28 36 46 92 99


    若使用最大堆,根节点就是整个数列的最大值,那么将h[1]和h[n]交换位置,此时h[n]就是最大值,然后将h[1]向下移动已恢复新的堆。此时将堆的大小减一,重复上面的操作。时间复杂度将会从O(NLogN)降低到O(NLogK)

    完整代码如下:

#include <stdio.h>

//存放堆

int h[100];

//存储堆的元素个数

int n;

//交换元素

void swap(int x, int y){

    int t;

    t = h[x];

    h[x] = h[y];

    h[y] = t;

}

//向下调整

void siftdown(int i){

    int t, flag=0;

    //判断该点的做儿子是否存在

    while(i*2 <= n && flag == 0){

        //如果左儿子存在,则判断是否交换值

        if(h[i] < h[i*2])

            t = i * 2;

        else

            t = i;

        //右儿子是否存在

        if(i*2+1 <= n && h[t] < h[i*2+1]){

            t = i*2+1;

        }

        //如果需要交换则交换

        if( t!= i){

            swap(t, i);

            i = t;

        //如果不需要交换,则准备退出while

        }else{

            flag = 1;

        }

    }

}

//创建堆

void create(){

    int i;

    for(i=n/2; i>=1; i--){

        siftdown(i);

    }

}

//从小到大排序

int minToMaxSort(){

    while(n>1){

        swap(1, n);

        n--;

        siftdown(1);

    }

}

int main(){

    int i, num;

    scanf("%d", &num);

    for(i=1; i<=num; i++){

        scanf("%d", &h[i]);

    }

    n = num;

    //创建堆

    create();

    //排序

    minToMaxSort();

    for(i=1; i<=num; i++){

        printf("%d ", h[i]);

    }

    return 0;

}

输入:

14

99 5 36 7 22 17 46 12 2 19 25 28 1 92

//输出:

1 2 5 7 12 17 19 22 25 28 36 46 92 99

Ps:本算法参考《啊哈!算法》一书。

   什么是Bellman-Ford算法?Bellman-Ford算法是一种堪称完美的解决一个点到其他各点的最短路径的算法。Bellman-Ford算法的核心代码只有4行,可以解决负权边的问题。

    Bellman-Ford算法的核心代码只有四行,如下

for(k=1; k<=n-1; k++)

    for(i=1; i<=m; i++)

        if(dis[v[i]] > dis[u[i]] + w[i])

            dis[v[i]] = dis[u[i]] + w[i];

    Bellman-Ford算法的核心代码意思是:遍历每一个点,其中每一次遍历时,遍历所有的边,对每个边进行一次松弛操作。

    松弛什么?请点击查看。算法十一:Dijkstra算法 - 一个点到各个点的最短路径

    现在有如下图,共5个点5条边,边都是有向边,其中点1到点2的距离为负数。如下:

无标题.jpg


    为什么会进行n-1次的循环呢?因为在不包含负权回路的路径中,n个点最多有n-1条边。在负权边中,负权回路会使最短路径不断的变小,永无止境。

完整代码如下:

#include <stdio.h>

int main(){

    int dis[10], i, k, m, n, u[10], v[10], w[10];

    int maxValue = 9999;

    //源点为1

    int start = 1;

    //读入点的个数n,边的个数m

    scanf("%d %d", &n, &m);

    //读入边

    for(i=1; i<=m; i++){

        scanf("%d %d %d", &u[i], &v[i], &w[i]);

    }

    //初始化dis数组。dis数组表示源点到各个点的初始距离,初始化时都为无穷大

    for(i=0; i<=n; i++){

        dis[i] = maxValue;

    }

    //源点到源点的距离为0

    dis[start] = 0;

    //Bellman-Ford算法的核心语句

    for(k=1; k<=n-1; k++){

        for(i=1; i<=m; i++){

            if(dis[v[i]] > dis[u[i]] + w[i]){

                dis[v[i]] = dis[u[i]] + w[i];

            }

        }

    }

    for(i=1; i<=n; i++){

        printf("%d ", dis[i]);

    }

    return 0;

}

输入:

5 5

2 3 2

1 2 -3

1 5 5

4 5 2

3 4 3

//输出:

0 -3 -1 2 4

    Bellman-Ford算法的时间复杂对为O(MN)。

    我们可以更加完善上面的代码。比如我们已经知道了使用Bellman-Ford算法不能包含负权回路,那么我们需要检测图中是否包含负权回路:

sign = 0

for(i=1; i<=m; i++)

    if(dis[v[i]] > dis[u[i]] + w[i])

        flag = 1;

if(sign == 1)

    printf("此图有负权回路");

    另外,在n-1轮循环中,若n-3轮已经松弛完毕,那么n-2和n-1两次循环便毫无意义,因此增加判断,若第x轮dis数组已经不再发生变化了,则不在继续进行循环。

    新版的完整代码如下:

#include <stdio.h>

int main(){

    int dis[10], i, k, m, n, u[10], v[10], w[10], sign, check;

    int maxValue = 9999;

    //源点为1

    int start = 1;

    //读入点的个数n,边的个数m

    scanf("%d %d", &n, &m);

    //读入边

    for(i=1; i<=m; i++){

        scanf("%d %d %d", &u[i], &v[i], &w[i]);

    }

    //初始化dis数组。dis数组表示源点到各个点的初始距离,初始化时都为无穷大

    for(i=0; i<=n; i++){

        dis[i] = maxValue;

    }

    //源点到源点的距离为0

    dis[start] = 0;

    //Bellman-Ford算法的核心语句

    for(k=1; k<=n-1; k++){

        //本轮dis数组是否发生变化

        ckeck = 0;

        for(i=1; i<=m; i++){

            if(dis[v[i]] > dis[u[i]] + w[i]){

                dis[v[i]] = dis[u[i]] + w[i];

                check = 1;

            }

        }

        //本轮没有发生松弛,则不再继续进行了。

        if(ckeck == 0){

            break;

        }

    }

    sign = 0

    for(i=1; i<=m; i++)

        if(dis[v[i]] > dis[u[i]] + w[i])

            sign = 1;

    if(sign == 1){

        printf("此图有负权回路");

    }else{

        for(i=1; i<=n; i++){

            printf("%d ", dis[i]);

       }

    }

    return 0;

}



    在第每一轮循环中,其实只对上一次发生了松弛的边的相邻边判断是否需要松弛,因此,没有必要每次都进行m次循环(遍历所有的边判断是否需要松弛)。比如第一轮松弛了1->2和1->5,那么第二次仅仅判断2->3和5->4这两个边是否需要松弛,而不需要遍历所有的边。

    在这种情况下,我们引入队列,将需要松弛的点加入队列。每个点仅仅需要入队一次即可,因为入队多次是没有意义的。初始时我们将1号点(源点)加入队列。然后开始遍历队列,对队列中每个点的边进行松弛。队列为空时所得结果便是一个点到其他所有点的最短路径。这是对上述的Bellman-Ford算法一种极大的优化。当然,在最坏的情况下,和Bellman-Ford算法的时间复杂度是一样的,即O(MN)。此优化也可以解决负权边。

    完整代码如下:

#include <stdio.h>

int main(){

    int dis[10] = {0}, i, j, k, m, n, u[10], v[10], w[10];

    int book[10] = {0};

    //first数组和next数组用来建立领接表,即first记录一个边的开头,比如第2号边的开头是点a,那么first[a]=2,a开头的下一个边是第5号边,则next[5]=a,组成一个链表的形式

    int first[10], next[10];

    int queue[100] = {0}, head = 1, tail = 1;

    int maxValue = 9999;

    //源点为1

    int start = 1;

    //读入点的个数n,边的个数m

    scanf("%d %d", &n, &m);

    //初始化dis数组。dis数组表示源点到各个点的初始距离,初始化时都为无穷大

    //book用来标记那个点已经入队了,因为队列中同时出现同一个点多次是没有意义。

    //first用来标记第i条边的起点

    for(i=0; i<=n; i++){

        dis[i] = maxValue;

        book[i] = 0;

        first[i] = -1;

    }

    //源点到源点的距离为0

    dis[start] = 0;

    //读入边

    for(i=1; i<=m; i++){

        scanf("%d %d %d", &u[i], &v[i], &w[i]);

        //使用first和next两个数组建立领接表

        next[i] = first[u[i]];

        first[u[i]] = i;

    }

    //源点入队

    queue[tail] = start;

    tail++;

    //标记已经入队的点

    book[i] = start;

    while(head < tail){

        //当前需要处理的点,是队首的点,处理队首开头的所有边

        k = first[queue[head]];

        //扫描这个点开头的所有边

        while( k != -1){

            if(dis[v[k]] > dis[u[k]] + w[k]){

                dis[v[k]] = dis[u[k]] + w[k];

                if(book[v[k]] == 0){

                    queue[tail] = v[k];

                    tail++;

                    book[v[k]] = 1;

                }

            }

            k = next[k];

        }

        //这个点开头的所有边都处理完了,就出队

        book[queue[head]] = 0;

        head++;

    }

    for(i=1; i<=n; i++){

        printf("%d ", dis[i]);

    }

    getchar();getchar();

    return 0;

}

输入:

5 5

2 3 2

1 2 -3

1 5 5

4 5 2

3 4 3

//输出:

0 -3 -1 2 4

Ps:本算法参考《啊哈!算法》一书。