阅读 22

Swift 数据结构学习:线性表(顺序存储)

本篇文章主要内容:

  • 线性表的基本概念
  • 线性表的存储结构
    • 顺序存储--一般使用数组实现
    • 链式存储--链表

基本概念

线性表定义: 零个或多个数据元素的有限序列。

特点:

  • 有限:元素的数量是有限的。
  • 序列:代表元素之间是有顺序的。若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。

存储结构

顺序存储

**顺序存储结构:**指的是用一组地址连续的存储单元依次存储线性表的数据元素。

根据线性表的特点及顺序存储结构的特点,所以顺序存储可以用一维数组来实现。

顺序存储时线性表基本结构

数据元素的基本结构:

class ListNode {
	var value: Int
	    
	public init(_ value: Int) {
	    self.value = value
	}
}
复制代码

线性表的基本结构:

class ArrayList {
	// 存储数据元素的数组
	var values: [ListNode]?
	
	// 表的长度
	var length: Int {
	    get {
	        if let count = values?.count {
	            return count
	        }
	        return 0
	    }
	}
	    
	// MARK: - 创建
	init() {}
}
复制代码

顺序存储的一些操作

利用 Swift 中的数组实现,Swift 数组已经内置了插入、删除等基本操作。这里为了探究插入及删除时发生了什么,自己实现这两个过程。

插入
func insert(_ value: Int, _ index: Int) {
    let newNode = ListNode(value)
    guard let nodes = values else {
        values = []
        values?.append(newNode)
        return
    }
    
    // index 越界
    if index < 0 || index >= nodes.count {
        return
    }
    
    var temp: [ListNode] = []
    
    for i in 0..<nodes.count {
        if i == index {
            temp.append(newNode)
        }
        temp.append(nodes[i])
    }
    values = temp
}
复制代码
删除
func remove(at index: Int) {
    guard let nodes = values else {
        return
    }
    
    // 超出数组长度
    if index < 0 && index >= nodes.count { return }
    
    var temp: [ListNode] = []
    for i in 0..<nodes.count {
        if i != index {
            temp.append(nodes[i])
        }
    }
    values = temp
}
复制代码
查找
func node(at index: Int) -> ListNode? {
    guard let nodes = values else {
        return nil
    }
    
    if index > 0 && index < nodes.count {
        return nodes[index]
    }
    
    return nil
}
复制代码

顺序存储结构优缺点

  • 优点:

    • 无须为表中数据元素的逻辑关系增加额外的存储空间。
    • 可以快速的存取表中任一位置的元素。(时间复杂度为 O(1))
  • 缺点

    • 插入和删除操作需要移动大量元素。(时间复杂度为 O(n))
    • 当线性表长度变化较大时,难以确定存储空间的容量。
    • 造成存储空间的碎片。

链式存储

**链式存储结构:**用一组任意的存储单元存储数据元素,这组存储单元可以是连续的,也可以是不连续的。数据元素间的逻辑顺序是通过结点中的指针域来实现。

关于链式存储会在下一篇文章介绍。

关注下面的标签,发现更多相似文章
评论