数据结构：线性表_线性表包含什么

线性表是基本的数据结构之一，是一组元素的抽象。

线性表包含顺序表和链接表（简称链表），顺序表在C语言中一般使用数组去实现，链表使用结构体去实现。在Python中，list对象是采用顺序表实现的。

1. 顺序表

顺序表是将表中的元素顺序的存储在连续的内存里。

优点：

• 查询速度快，时间复杂度为O(1)

缺点：

• 插入元素速度慢，时间复杂度为O(n)
• 表中元素个数需要提前定义

2. 链表

链表：通过链接各个结点实现的技术就叫做链表。链表中的结点分为指针域和数据域，具体见下图。结点中的data用来存放数据，next用来存放下一个节点的地址。

链表分为单链表和双链表。单链表只有数据域data和地址域next指向下一个节点的地址，双链表含有前地址域prev、数据域data和后地址域next。

2.1 单链表

定义结点的代码：

# 定义结点  
class Node:  
    def __init__(self, data, next_=None):  
        self.data = data  
        self.next = next_
1
2
3
4
5

添加元素

• 首先temp是遍历节点
• 遍历结点使得temp指向最后一个结点
• temp的地址域指向新添加的结点的地址

temp.next = node
1

插入元素

核心代码：
假如要在 元素10之间插入元素13，我们需要找到元素10的前一个元素，使得temp指向 元素9。

node = Node(13)  # node 是要插入的元素
node.next = temp.next
temp.next = node
1
2
3

删除元素

temp.next = temp.next.next
1

单链表实现全部代码：

  
# 定义结点  
class Node:  
    def __init__(self, data, next_=None):  
        self.data = data  
        self.next = next_  
  
class LinkedListUnderflow(ValueError):  
    pass  
  
# 头结点定义为空(头结点指向第一个元素)  
class single_linked_list:  
  
    def __init__(self):  
        self._head = None # 下划线开头，表明该成员变量是私有的  
 # 判断是否为空  
 def is_empty(self):  
        return self._head is None  
  
 # 开头插入  
 def prepend(self, data):  
        self._head = Node(data, self._head)  
  
    # 移除首元素,并返回该结点的data  
 def prepop(self):  
        if self.head is None:  
            raise LinkedListUnderflow("in prepop")  
        e = self._head.data  
        self._head = self._head.next  
        return e  
  
    # 移除尾部元素，并返回该结点的值  
 def pop(self):  
        if self._head is None:  
            raise LinkedListUnderflow("in pop")  
        temp = self._head  
        # 注意 temp 和 temp.next 的区别  
 while temp.next is not None:  
            temp = temp.next  
        e = temp.data  
        temp.next = None  
 return e  
# 该结点会自动被回收，如果是C语言需要手动free，释放节点的内存  
  
 # 尾部添加  
 def append(self, data):  
        if self._head is None:  
            self._head = Node(data)  
            return  
 # 遍历查找尾部结点  
 temp = self._head  
        while temp.next is not None:  
            temp = temp.next  
        temp.next = Node(data)  
        return  
  
 ''':找到满足给定条件的表元素, pred 是给定条件的函数  
 :只能找到第一个满足条件时的元素，pred 可以使用 lambda 表达式  
 ''' def find(self, pred):  
        temp = self._head  
        while temp is not None:  
            if pred(temp.data):  
                return temp.data  
            temp = temp.next  
        return  
 # 找到满足 pred 的所有 结点值  
 def filter(self, pred):  
        temp = self._head  
        while temp is not None:  
            if pred(temp.data):  
                yield temp.data  
            temp = temp.next  
        return  
  
 # 传统遍历  
 def print_all(self):  
        temp = self._head  
        while temp is not None:  
            print(temp.data, end='\t')  
            temp = temp.next  
        print()  
        pass  
  
 """:arg传统的遍历结点的所有值  
 这里使用谓词函数，调用的时候传入print函数即可  
 使用 C语言遍历时，可以直接把printf()函数写到函数里面  
 """ def for_each(self, proc):  
        temp = self._head  
        while temp is not None:  
            proc(temp.data, end='\t')  
            temp = temp.next  
        return  
  
 ''':遍历所有结点的data值：使用生成器函数定义迭代器  
 ''' def elements(self):  
        temp = self._head  
        while temp is not None:  
            yield temp.data       # 使用 yield 定义迭代器  
 temp = temp.next  
        return  
  
  
if __name__ == '__main__':  
    mlist = single_linked_list()  
    for i in range(10):  
        mlist.prepend(i)  
    for i in range(11, 20):  
        mlist.append(i)  
# 遍历输出所有元素  
 for x in mlist.elements():  
        print(x, end='\t')  
    print()  
      
    res = mlist.find(lambda x: x>15)  
    print(res)  
  
    for x in mlist.filter(lambda x: x>15):  
        print(x, end='\t')  
    print()  
  
    mlist.for_each(print)  
    print()  
    mlist.print_all()
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

2.2 双链表

正在总结中…