线性表

线性表(Linear List):由同类型数据元素构成有序序列的线性结构,一对一

  • 表中元素的个数称为线性表的长度
  • 线性表没有元素时称为空表
  • 表起始位置称为表头,结束位置称为表尾

线性表的抽象数据类型描述

类型名称:线性表(List)

数据对象集:线性表是n(n>=0)个元素构成的有序序列(a1,a2,….an)

操作集

  • 初始化一个空线性表
  • 是否空表
  • 查找
    • 根据key返回value
    • 根据value返回第一次出现此value的key
  • 插入
  • 删除
  • 表长

线性表的实现方式

线性表的顺序存储实现(数组)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

// 线性结构的数组实现
struct LinearListUseArray<T> where T : Equatable, T : Any {
    var data : [T]?
    var last : Int// 最后一个下标
    
    init() {
        data = nil
        last = -1
    }
    
    func isEmpty() -> Bool {
        return last < 0
    }
    
    func key(for value:T) -> Int {
        if isEmpty() {
            return NSNotFound
        }
        if let array = data {
            for i in 0..<array.count {
                if array[i] == value {
                    return i
                }
            }
            return NSNotFound
        }
        else {
            return NSNotFound
        }
    }
    
    func value(for key:Int) -> T? {
        if isEmpty() || key < 0 || key > last {
            return nil
        }
        return data?[key]
    }
    
    mutating func insert(value v:T, at i:Int) -> Bool {
        if i<0 || i > last || isEmpty() {
            return false
        }
        data?.insert(v, at: i)
        last += 1
        return true;
    }
    
    mutating func delete(key i:Int) -> T? {
        if i<0 || i > last || isEmpty()  {
            return nil
        }
        let v = data?.remove(at: i)
        last -= 1
        return v
    }
}

线性表的链式存储实现(链表)

  • 不要求逻辑上相邻的元素在物理存储上也相邻
  • 插入,删除不需要移动元素,只需要修改链
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

class LinearListNode<T: Hashable> {
    var data : T?
    var next : LinearListNode?
    init(data:T?) {
        self.data = data
    }
}

class LinearList<T : Hashable> {
    var head : LinearListNode<T>?
    init() {
        head = nil
    }
    
    func length() -> Int {
        var length = 0, n = head
        while (n != nil) {
            n = n!.next
            length += 1
        }
        return length
    }
    
    func findNode(number:Int) -> LinearListNode<T>? {
        var i = 0, n = head
        while n != nil && i < number {
            n = n!.next
            i += 1
        }
        if i == number {
            return n
        }
        else {
            return nil
        }
    }
    
    func findNode(data:T) -> LinearListNode<T>? {
        var n = head
        while n != nil {
            if n!.data == data {
                return n
            }
            n = n!.next
        }
        return nil
    }
    
    func insert(value:T, at i:Int) -> Void {
        let node = LinearListNode(data: value);
        if i == 0 {
            node.next = head
            head = node;
            return
        }
        
        let lastNode = findNode(number: i - 1)
        node.next = lastNode?.next
        lastNode?.next = node
    }
    
    func delete(at i:Int) -> T?{
        var temp : T? = nil
        if i == 0 {
            temp = head?.data
            head = head?.next
            return temp
        }
        
        let n = findNode(number: i - 1)
        if n == nil || n!.next == nil {
            return nil
        }
        temp = n!.next!.data
        n!.next = n!.next!.next
        return temp
    }
}

let list = LinearList<String>()
list.insert(value: "aaa", at: 0)
list.insert(value: "bbb", at: 1)
list.insert(value: "ccc", at: 2)

广义表

  • 广义表是线性表的推广
  • 线性表中,n个元素都是单元素
  • 广义表中,元素不仅可以是单元素也可以是另一个广义表
1
2
3
4
5
6
7
8
9

typedef struct GNode *GList; 
struct GNode{
    int Tag; /*标志域:0表示结点是单元素，1表示结点是广义表 */
    union { /*子表指针域Sublist与单元素数据域Data复用，即共用存储空间*/
        ElementType Data;
        GList SubList;
    } URegion;
    GList Next; /* 指向后继结点 */
};

多重链表

链表中的节点可能同时隶属于多个链

  • 多重链表中的节点的指针域会有多个,例如广义表中的Next和SubList两个指针域
  • 但包含两个指针域的链表不一定是多重链表,如双向链表不是多重链表
  • 多重链表有广泛的用途,如树,图这种复杂度数据结构都可以用多重链表的方式实现存储