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

Posted on In

本篇文章主要内容：

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

基本概念

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

特点：

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

存储结构

顺序存储

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

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

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

数据元素的基本结构：

1
2
3
4
5
6
7
class ListNode {
	var value: Int
	    
	public init(_ value: Int) {
	    self.value = value
	}
}

线性表的基本结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class ArrayList {
	// 存储数据元素的数组
	var values: [ListNode]?
	
	// 表的长度
	var length: Int {
	    get {
	        if let count = values?.count {
	            return count
	        }
	        return 0
	    }
	}
	    
	// MARK: - 创建
	init() {}
}

顺序存储的一些操作

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

插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
}
删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
}
查找
1
2
3
4
5
6
7
8
9
10
11
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)）
    • 当线性表长度变化较大时，难以确定存储空间的容量。
    • 造成存储空间的碎片。

链式存储

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

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