Fork me on GitHub

顺序表和链表

Posted on | In , |
Words count in article: 2.9k | Reading time ≈ 13

引言

题目：a**2 + b**2 = c**2，a+b+c=1000，求解a，b，c

关于jupyter中的魔法命令

  • timeit：自动运行多次取均值

    • %timeit 运行单条语句
    • %%timeit 运行多条语句

  • time：只运行一次

    • %time 运行单条语句

    • %%time 运行多条语句

1
2
3
4
5
6
7
8
9
10
11
%%time
import time 

start = time.time()
for a in range(0, 1001):
    for b in range(0, 1001):
        for c in range(0, 1001):
            if a + b + c == 1000 and a**2 + b**2 == c**2:
                print("a:{0}，b:{1}, c:{2}".format(a, b, c))
end = time.time()
print(end - start)

算法五大特征

  • 输入

  • 输出

  • 有穷性

  • 确定性

  • 可行性

1
2
3
4
5
6
7
8
9
10
11
12
%%time
import time 

start = time.time()
for a in range(0, 1001):
    for b in range(0, 1001):
        # 优化之处
        c = 1000 - a - b
        if  a**2 + b**2 == c**2:
            print("a:{0}，b:{1}, c:{2}".format(a, b, c))
end = time.time()
print(end - start)

时间复杂度O(n)

基础

通过运算的时间来进行度量，用n来进行表示。有几种情况：

  • 最优时间复杂度
  • 最坏时间复杂度
  • 平均复杂度

常见的计算规则：

  • 顺序：累加结构计算
  • 循环：乘法结构计算
  • 分支：取最大值

一般取的是最坏时间复杂度，考虑最坏的情况，同时忽略常数项

常见的时间复杂度

消耗的时间大小关系：$O(1)< O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2n)<O(n!)<O(nn)$

timeit模块

主要功能是进行测试

1
2
3
4
# 生成列表
li1 = [1, 2]
li2 = [3, 4]
li = li1 + li2
1
li
1
2
li = [i for i in range(10)]
li
1
2
li = list(range(10))
li
1
2
3
4
li = []
for i in range(10):
    li.append(i)
li
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
# 比较几种列表生成式
from timeit import Timer

def t1():
    li = []
    for i in range(10000):
        li.append(i)
        
def t2():
    li = []
    for i in range(10000):
        # li = li + [i]
        li += [i]
        
def t3():
    li = [i for i in range(10000)]
    
def t4():
    li = []
    for i in range(10000):
        li.insert(0, i)
    
time1 = Timer("t1()", "from __main__ import t1")
print("append:", time1.timeit(10000))

time2 = Timer("t2()", "from __main__ import t2")
print("+:", time2.timeit(10000))

time3 = Timer("t3()", "from __main__ import t3")
print("[]:", time3.timeit(10000))

time4 = Timer("t4()", "from __main__ import t4")
print("insert:", time4.timeit(10000))

列表和字典的时间复杂度

列表

操作 复杂度
index [] 0(1)
append 0(1)
pop() 0(1)
pop(i) O(n)
insert() O(n)
sort() O(nlogn)

字典

操作 复杂度
copy() O(n)
get,set,delete,contains,iteration O(1)

数据结构

数据结构是指数据对象中数据元素之间的关系，在Python中内置的数据结构，比如列表、字典、元组等，扩展结构：栈、队列等。
程序 = 数据结构 + 算法

常见的操作：

  • 插入
  • 删除
  • 修改
  • 查找
  • 排序

顺序表

存储方式

数据本身是连续存储，每个元素占据固定大小的单元，元素下标是逻辑地址，包含：数据区+表头信息，两种存储方式：

  • 一体式结构：表头信息和数据区连在一起，表头区包含容量和元素个数
  • 分离式结构：表头信息和数据区分开存放，通过表头区的地址单元去指向数据区

扩充策略

  • 每次固定的扩充数目：线性扩充，节省空间。扩充频繁，操作频繁
  • 每次扩充容量加倍：减少扩充执行次数，浪费资源。以空间换取时间

链表

链表由来

顺序表的构建需要预先知道数据大小来申请连续的存储空间；再进行扩充的时候需要进行数据的迁移，很不方便。链表能够充分地利用计算机的存储空间，实现灵活的内存动态管理。

线性表包含顺序表和链表。在链表中，元素与元素之间通过链接构造起来的一系列存储结构中，每个节点（存储单元）中存放下一个节点的位置信息。。节点中包含：数据取 + 链接区（指针区）。最后一个没有指针区

单向链表

单向链表包含数据区和链接区。链接指向下一个链接表中的节点。最后一个节点指向空值(一竖一横表示)。

主要的操作是：

  • is_empty()
  • length()
  • travel()
  • add(item)
  • append()
  • insert()
  • remove()
  • search()

在Python的$a=10$中，a是个地址，保存的不是10，地址指向10。

顺序表和链表对比

顺序表

  • 随机读取数据
  • 查找很快，耗时主要是在拷贝和覆盖
  • 存储空间必须是连续的

链表

  • 增加了节点地指针区域，空间开销大，对存储空间的使用更加灵活
  • 耗时主要是体现在：遍历查找
  • 只记录头结点，如果想找到其他节点，必须通过遍历的方式去寻找
  • 存储空间不是连续的：数据区+指针区，对离散空间能够充分利用

时间复杂度对比

操作 链表 顺序表
访问元素 O(n) O(1)
头部 O(1) O(n)
尾部 O(n) O(1)
中间 O(n) O(n)

为什么链表的时间复杂度增加，还要使用链表？

  • 链表存储数据时不使用连续空间，如果内存中没有连续的空间用来存储数据，那么不能用顺序表只能用链表；链表对离散空间利用率高
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
# 单向链表

# 定义节点类
class Node(object):
    def __init__(self, elem):
        self.elem = elem
        self.next = None
        
class SingleLinkList(object):
    def __init__(self, node=None):
        self.__head = node
    
    def is_empty(self):
        return self.__head == None
    
    def length(self):
        # 遍历整个链表
        # cur游标，用来移动遍历节点；初始值设为头部的值
        cur = self.__head
        # count记录数量 
        # 特殊情形：若链表是空的，cur = self._head = None，不进入while循环，count=0直接返回
        count = 0
        while cur != None:
            count += 1
            # 移动
            cur = cur.next
        return count
    
    def travel(self):
        # 遍历：打印每个节点的数据
        cur = self.__head
        while cur != None:
            # 游标所指的当前节点的数据
            # end属性：使用空格不换行，默认是换行\n
            print(cur.elem, end=" ")
            # 移动
            cur = cur.next
        print("")
        
    def add(self,item):
        # 头部插入元素
        # 实例构造节点
        node = Node(item)
        # 将节点的next值指向最初__head的值
        node.next = self.__head
        # 将创建的节点的值node赋给self.__head
        self.__head = node
    
    def append(self, item): 
        # 尾部插入元素     
        # item是传入的具体元素，通过实例存入节点中
        node = Node(item)
        # 考虑空列表的情况
        if self.is_empty():
            # 如果为空，直接指向节点node
            self.__head = node
        else:
            cur = self.__head
            # 只要cur的next区域不是None，则一直进行
            while cur.next != None:
                cur = cur.next
            # 添加节点
            cur.next = node
    
    def insert(self, pos, item):
        """
        指定位置添加：指定位置pos的前一个位置添加
        pos：从0开始
        
        """
        # 如果pos <= 0，相当于是pos=0，看做是在头部插入add方法
        if pos <= 0:
            self.add(item)
        # 如果pos比链表最后一个元素的位置还大，默认看做是在尾部插入
        elif pos > (self.length()-1):
            self.append(item)
        else:
            pre = self.__head
            count = 0
            while count < (pos-1):
                count += 1
                pre = pre.next
            # 当循环退出，pre指向pos-1位置
            node = Node(item)
            node.next = pre.next
            pre.next = node
        
        
    def remove(self, item):
        """
        删除节点
        使用两个游标：pre和cur；最开始pre指向None，cur指向head
        """
        cur = self.__head
        pre = None
        # 终止条件：走到最后，直至每个元素都有被遍历
        # 空链表为None，不执行任何操作
        while cur != None:
            if cur.elem == item:
                # 先判断此节点是否是头节点
                # 如果是头节点：pre == None或者cur == self.__head
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next
        
    def search(self, item):
        #  判断是否存在某个数据item：存在返回T，否则F
        # 如果直接是空链表，也可以进行处理，直接返回F
        cur = self.__head
        # while cur.next != None：如果这样写，最后一个元素的next为空，那么最后的元素将不能进入while循环，导致最后的元素没有进行遍历
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False
    
if __name__ == "__main__":
    li = SingleLinkList()
    print(li.is_empty())
    print(li.length())
    
    li.append(1)
    print(li.is_empty())
    print(li.length())
    
    li.append(2)
    li.append(3)
    li.append(4)
    # 插入在头部
    li.add(8)
    li.append(5)
    li.append(6)
    li.insert(-1,9)
    li.travel()
    li.insert(4,11)
    li.travel()
    li.insert(15,12)
    li.travel()
    li.remove(9)
    li.travel()
    li.remove(4)
    li.travel()
    li.remove(12)
    li.travel()
1
2
3
4
5
6
7
8
9
10
True
0
False
1
9 8 1 2 3 4 5 6 
9 8 1 2 11 3 4 5 6 
9 8 1 2 11 3 4 5 6 12 
8 1 2 11 3 4 5 6 12 
8 1 2 11 3 5 6 12 
8 1 2 11 3 5 6
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
# 单向循环链表

# 定义节点类
class Node(object):
    def __init__(self, elem):
        self.elem = elem
        self.next = None
        
class SingleCycleList(object):
    def __init__(self, node=None):
        self.__head = node
    
    def is_empty(self):
        return self.__head == None
    
    # 单向循环链表
    # 尾节点的指针指向头部head
    def length(self):
        # 空链表直接返回0
        if self.is_empty():
            return 0
        cur = self.__head
        # 循环链表中的count初始值为1
        count = 1
        # 判断cur的下个指向是否为head
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        return count
    
    def travel(self):
        # 遍历：打印每个节点的数据
        if self.is_empty():
            return 
        cur = self.__head
        while cur.next != self.__head:
            # 游标所指的当前节点的数据
            # end属性：使用空格不换行，默认是换行\n
            print(cur.elem, end=" ")
            cur = cur.next
        # 退出循环，cur指向尾结点，但尾结点的元素未被打印，单独处理
        print(cur.elem)
      
    # 循环链表中添加元素
    def add(self,item):
        # 头部插入元素
        node = Node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            # 退出循环，cur指向尾结点
            node.next = self.__head
            self.__head = node
            # cur.next = node
            cur.next = self.__head

    def append(self, item): 
        # 尾部插入
        node = Node(item)
        # 考虑空链表的情况
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            # node.next = cur.next
            node.next = self.__head
            cur.next = node
    
    def insert(self, pos, item):
        """
        指定位置添加：指定位置pos的前一个位置添加
        pos：从0开始
        
        """
        # 如果pos <= 0，相当于是pos=0，看做是在头部插入add方法
        if pos <= 0:
            self.add(item)
        # 如果pos比链表最后一个元素的位置还大，默认看做是在尾部插入
        elif pos > (self.length()-1):
            self.append(item)
        else:
            pre = self.__head
            count = 0
            while count < (pos-1):
                count += 1
                pre = pre.next
            # 当循环退出，pre指向pos-1位置
            node = Node(item)
            node.next = pre.next
            pre.next = node
          
    def remove(self, item):
        """
        删除节点
        使用两个游标：pre和cur；最开始pre指向None，cur指向head
        """
        if self.is_empty():
            return 
        cur = self.__head
        pre = None
        # 终止条件：走到最后，直至每个元素都有被遍历
        # 空链表为None，不执行任何操作
        while cur.next != self.__head:
            if cur.elem == item:
                # 先判断此节点是否是头节点
                # 如果是头节点：pre == None或者cur == self.__head
                if cur == self.__head:
                    # 头结点
                    # self.__head = cur.next
                    rear = self.__head
                    while rear.next != self.__head:
                        rear = rear.next
                    self.__head = cur.next
                    rear.next = self.__head
                else:
                    # 中间结点
                    pre.next = cur.next
                return
            else:
                pre = cur
                cur = cur.next
        # 退出循环，cur指向尾结点
        if cur.elem == item:
            if cur == self.__head:
                # 链表只有一个节点
                self.__head = None
            else:
                pre.next = cur.next      
        
        
    def search(self, item):
        #  判断是否存在某个数据item：存在返回T，否则F
        # 如果直接是空链表，也可以进行处理，直接返回F
        if self.is_empty():
            return False
        cur = self.__head
        while cur.next != self.__head:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        # 退出循环，cur指向尾节点
        if cur.elem == item:
            return True
        return False
    
if __name__ == "__main__":
    li = SingleCycleList()
    print(li.is_empty())
    print(li.length())
    
    li.append(1)
    print(li.is_empty())
    print(li.length())
    
    li.append(2)
    li.append(4)
    # 插入在头部
    li.add(8)
    li.append(5)
    li.insert(-1,9)
    li.travel()
    li.insert(4,11)
    li.travel()
    li.insert(15,12)
    li.travel()
    li.remove(9)
    li.travel()
    li.remove(4)
    li.travel()
    li.remove(12)
    li.travel()
1
2
3
4
5
6
7
8
9
10
True
0
False
1
9 8 1 2 4 5
9 8 1 2 11 4 5
9 8 1 2 11 4 5 12
8 1 2 11 4 5 12
8 1 2 11 5 12
8 1 2 11 5
Stay Foolish Stay Hungry

本文标题:顺序表和链表

发布时间:2019年09月09日 - 18:09

原始链接:http://www.renpeter.cn/2019/09/09/Python%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%951%E2%80%94%E2%80%94%E9%A1%BA%E5%BA%8F%E8%A1%A8%E5%92%8C%E9%93%BE%E8%A1%A8.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

Coffee or Tea