美文网首页Aha! Algorithms
Aha! Algorithms - Linked List Si

Aha! Algorithms - Linked List Si

作者: su3 | 来源:发表于2017-03-17 09:48 被阅读0次

《啊哈!算法》第 2 章第 5 节,模拟链表的 Swift 实现。

问题

为数组添加一个数,仍然得到按数值大小的排序,但不移动原数组的位置。

解决

用 data 存数组,用 right 记录对应 data 中的数值的下一个数所在的编号(0 编号表示结束)。为 data 尾部添加一个数后,修改 3 处 right 编号(1 新添加的数 2 此前的数 3 结束的数),完成插入。

var data = [0] //初始化链表,前置一个空项,不打印此项
var right: [Int] = []

//待操作的数组
data += [2, 3, 5, 8, 9, 10, 18, 26, 32]

//初始化数组的 right
var count = data.count
for i in 0...count  {
    if i != count {
        right.append(i+1)
    }else{
        right.append(0)
    }
}

//直接在数组 data 末尾添加一个数
data.append(6)
count += 1

//从链表头部开始遍历
var t = 1
while t != 0 {
    //如果当前节点的下一个节点大于插入数,将数插到中间
    if data[right[t]] > data[count-1] {
        //新插入数的下一个节点编号等于当前节点的下一个节点编号
        right[count-1] = right[t]
        //当前节点的下一个节点编号等于新插入数的编号(最后一个)
        right[t] = count - 1
        //原数组最后一个节点的下一个节点编号为0(标记着数组结束)书中的 bug,缺了结束编号
        right[count-1-1] = 0
        break //完成插入,退出循环
    }
    t = right[t]
}

//遍历输出链表中的所有数
t = 1
while t != 0 {
    print("\(data[t])")
    t = right[t]
}

代码在 GitHub

相关文章

  • Aha! Algorithms - Linked List Si

    《啊哈!算法》第 2 章第 5 节,模拟链表的 Swift 实现。 问题 为数组添加一个数,仍然得到按数值大小的排...

  • 笨办法学C 练习33:链表算法

    练习33:链表算法 原文:Exercise 33: Linked List Algorithms 译者:飞龙 我将...

  • 2019-03-03

    LeetCode 328. Odd Even Linked List Description Given a si...

  • Aha! Algorithms

    1. 涉及的数据结构 栈、队列、链表、树、并查集、堆、图 2. 涉及的算法 排序、枚举、深度和广度优先搜索、图的遍...

  • Aha! Algorithms - Quicksort

    《啊哈!算法》第 1 章第 3 节,快速排序的 Swift 实现 问题 为给定数字序列排序 解决 以左侧第一个位置...

  • Aha! Algorithms - Queue

    《啊哈!算法》第 2 章第 1 节,队列的 Swift 实现 问题 给一个数字序列,解密方法是:删除第 1 个,将...

  • Aha! Algorithms - Dijkstra

    《啊哈!算法》第 6 章第 2 节,Dijkstra 算法求最短路径的 Swift 实现。 问题 已经若干顶点和路...

  • Aha! Algorithms - Floodfill

    《啊哈!算法》第 4 章第 5 节,漫水填充法的 Swift 实现。 问题 给一个群岛地图中不同的岛屿填充不同的颜...

  • Aha! Algorithms - Bomberman

    《啊哈!算法》第 3 章第 2 节,bomb 人的 Swift 实现。 问题 在哪里放置 bomb 才可以消灭最多...

  • Aha! Algorithms - Stack

    《啊哈!算法》第 2 章第 2 节,栈的 Swift 实现。 问题 判断字符串是否回文 解决 将字符串前半部分入栈...

网友评论

    本文标题:Aha! Algorithms - Linked List Si

    本文链接:https://www.haomeiwen.com/subject/qizsnttx.html