都说 程序 = 数据结构 + 算法 ，最开始不太懂数据结构，而且觉得算法更是不靠谱，数学太烂，后来懵懵懂懂的明白了数据结构，为了实现某些功能，也写过一些算法。
不过就目前的经验而言，个人觉得算法还是要根据数据结构来写的。
最近有一个算法要实现，算法攻城狮只会写C++，我是写java的，而且java和C除了用动态(静态)链接库之外，没法混编，这种情况下，只需要了解一下他的算法原理，然后给根据自己的数据结构去写就行了，毕竟，他也不了解我的数据结构。
一个关于 数据结构和算法 的牛逼网站
https://visualgo.net
这里还是主要说一下Python的数据结构
列表
list的常用方法
- append(x)
- 在列表的末尾添加一个项
- 等价于
a[len(a):] = [x]
- extend(iterable)
- 遍历
iterable中所有项来扩展列表 a[len(a):] = iterable
- 遍历
- insert(i, x)
- 在指定位置插入一个值
- i=位置，x=值
- remove(x)
- 从列表中删除第一项x值
- 如果没有值，返回一个错误。
- pop([i])
- 删除列表中指定位置的值，并返回它
- 如果没有指定，则删除最后一项并返回
- 方括号代表可选参数
- clear()
- 清空所有项
del a[:]
- index(x[, start[, end]])
- 在第一个值为x的列表中返回从零开始的索引
- 如果没有这样的项，就会产生一个
ValueError - 返回的索引是相对于完整序列开始计算的，不是开始参数。
- count(x)
- x的个数
- sort(key=None, reverse=False)
- 排序
- 这是个多参数方法
- 详见 https://docs.python.org/3/library/functions.html#sorted
- reverse()
- 反转
- 返回一个反转后的list
- copy()
- 复制
a[:]
Python的设计
- 像
insert,remove,sort之类的方法，都不输出返回值，默认为None。 - Python中所有 可变数据结构 的设计原则都是这样的
>>> nums = ["one","two","three","one","five","one"]
>>> nums.count("one")
3
>>> nums.count("fix")
0
>>> nums.index("one")
0
>>> nums.index("five")
4
# 从位置4开始的one
>>> nums.index("one",4)
5
>>> nums.reverse()
>>> nums
['one', 'five', 'one', 'three', 'two', 'one']
>>> nums.append("six")
>>> nums
['one', 'five', 'one', 'three', 'two', 'one', 'six']
# 默认排序
>>> nums.sort()
>>> nums
['five', 'one', 'one', 'one', 'six', 'three', 'two']
>>> nums.pop()
'two'
堆栈中使用list
- 用
append()可以添加到栈顶 - 用
pop()可以从栈顶开始检索 - 后进先出
>>> stack = [3,4,5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]
队列中使用list
- 添加的第一个元素也是被检索的第一个元素(低效，先进先出)
- 虽然追加到末尾速度最快，但是添加删除会很慢(需要逐渐位移)
-
collections.deque可以解决这个问题，可以从两端快速添加或者删除
>>> from collections import deque
>>> queue = deque(["one","two","three"])
>>> queue.append("four")
>>> queue.append("five")
>>> queue
deque(['one', 'two', 'three', 'four', 'five'])
>>> queue.popleft()
'one'
>>> queue
deque(['two', 'three', 'four', 'five'])
List Comprehensions
List Comprehensions为创建列表提供了一种简洁的方式。
通常生成一个列表是直接new一个新列表，其中每个item是另一个集合或迭代器的结果，或者他们的的子集。
# 一个平方列表
>>> squares = []
>>> for x in range(10):
squares.append(x**2)
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
# 创建(或覆盖)一个名为x的变量，该变量在循环完成后仍然存在。
>>> x
9
# 还有一种方式可以计算出没有任何副作用的平方列表
>>> squares = list(map(lambda x: x**2,range(10)))
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
# 相当于这样
squares = [x**2 for x in range(10)]
# 相信你已经看出来为什么了，限定了它的范围
# 而且可读性更强，接下来用这种方式玩一个蛋疼的循环
>>> ballachefor = [(x,y) for x in [1,2,3] for y in [3,1,4] if x != y]
>>> ballachefor
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]
# 等价于这样，很容易懂，因为它们的顺序是相同的
>>> for x in [1,2,3]:
for y in [3,1,4]:
if x != y:
dantengfor.append((x,y))
>>> dantengfor
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]
List Comprehension括号内包含表达式的括号，然后是for子句，然后是0或if子句。结果是一个new list，该列表来自于对该表达式上下文中的表达式进行评估，以及是否遵循它的子句。
如果它是一个元祖，则必须用()，就像上面的例子一样
代码呀，还是要多练
>>> vec = [-4,-2,0,2,4]
>>> [x*2 for x in vec]
[-8, -4, 0, 4, 8]
>>> [x for x in vec if x>= 0]
[0, 2, 4]
>>> [abs(x) for x in vec]
[4, 2, 0, 2, 4]
>>> freshnums = ["one","two","three"]
>>> [weapon.strip() for weapon in freshnums]
['one', 'two', 'three']
>>> [(x,x**2) for x in range(6)]
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]
嵌套列表
>>> matrix = [[1,2,3],[4,5,6],[7,8,9]]
>>> [[row[i] for row in matrix] for i in range(3)]
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]
# 等价于
>>> convert = []
>>> for i in range(3):
convert2 = []
for row in matrix:
convert2.append(row[i])
convert.append(convert2)
>>> convert
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]
# 对于这些内置函数复杂流语句可以用zip()函数
>>> list(zip(*matrix))
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]
删除语句
#The del statement
del_stmt ::= "del" target_list
-
del方法可以从列表中根据索引删除一个项，而不是它的价值。这不同于pop()方法返回一个值。del语句也可以从列表中移除片或清除整个列表 - 删除是递归地定义赋值定义的方式非常相似
- 删除一个目标表的递归删除每个目标,从左到右。
- 删除一个名称删除绑定的名称从本地或全局命名空间,取决于这个名字出现在全局声明相同的代码块。
- 如果名字是释放状态,会抛出NameError异常。
>>> a = [-3,-2,-1,0,1,2,3,301]
>>> del a[0]
>>> a
[-2, -1, 0, 1, 2, 3, 301]
>>> del a[-1]
>>> a
[-2, -1, 0, 1, 2, 3]
>>> del a[:]
>>> a
[]
# 删除整个变量
>>> del a
>>> a
Traceback (most recent call last):
File "<pyshell#50>", line 1, in <module>
a
NameError: name 'a' is not defined
元组和序列
列表和字符串有很多共同属性。他们是序列数据类型的两个例子。Python是不断发展的，正如之前一直用的2，到3不兼容之前的版本了...
它添加了新的标准序列数据类型:tuple。
元组看起来和list有点像，但还是不一样的，比如，可以不带括号，不可变，而且是通过索引找对象，list通过循环就可以
# 元组
>>> t = 123,321,"hello"
>>> t[2]
'hello'
>>> t
(123, 321, 'hello')
# 嵌套元组
>>> u = t,(1,2,3)
>>> u
((123, 321, 'hello'), (1, 2, 3))
# 元组和字符串一样，是不可变的
>>> t[0] = 123
Traceback (most recent call last):
File "<pyshell#66>", line 1, in <module>
t[0] = 123
TypeError: 'tuple' object does not support item assignment
# 但是可以包含可变对象，如list
>>> v = ([1,2,3],[3,2,1])
>>> v
([1, 2, 3], [3, 2, 1])
# 创建一个空元组
>>> empty = ()
>>> empty
()
# 不带逗号就是字符串
>>> one = "hello"
>>> one
'hello'
# 带逗号就是元组
>>> one = "hello",
>>> one
('hello',)
# 元组的拆包
>>> x,y,z = t
>>> t
(123, 321, 'hello')
>>> x
123
>>> y
321
>>> z
'hello'
Sets
- sets也是python的数据类型之一
- set是一个无序集合（没有重复元素）
- 基本用于item测试和消除重复元素
- set对象也支持数学运算(唯一性，交集,差异和对称差分)
- 花括号或者set()函数都可以用来创建sets
- 创建一个空set，必须用
set(),不能用{},花括号是用来创建一个空字典的 - list包含的，set都包含
# 去重
>>> nums = {"one","two","one","three","four","five","six","five"}
>>> nums
{'four', 'five', 'two', 'six', 'one', 'three'}
# item 测试
>>> "one" in nums
True
>>> "seven" in nums
False
# set 操作
>>> a = set("aabbccdd")
>>> b = set("aaccee")
# 拆分a
>>> a
{'a', 'b', 'c', 'd'}
# 差异(a有，b没有)
>>> a-b
{'b', 'd'}
# 合并
>>> a | b
{'e', 'a', 'b', 'c', 'd'}
# 交集
>>> a & b
{'a', 'c'}
# a,b各自独有的合集
>>> a ^ b
{'e', 'b', 'd'}
# list包含的，set都包含
>>> a = {x for x in "aabbccddee" if x not in "abc"}
>>> a
{'e', 'd'}
字典dictionary
dict,字典在其他语言中叫“关联存储”或“关联数组”，和序列不同的是，序列是range范围，字典是index索引，可以是任何不可变类型。
- 数字和字符串可以一直是键
- 只包含字符串、数字、或元组的元组也可以是键
- 如果一个tuple直接或间接包含任何可变对象,则不能作为一个关键。
- 不能用list作为key
- 最好是把dict看作一组无序的键值对,在一个字典是唯一的。
- 用一对{}可以创建一个空字典。
- 向字典添加键值对，要用“，”分隔
字典的主要操作是多个key一个value和根据key取value。也可以用del删除一个键值对。如果你正在用的key已经被使用了，那么与旧值关联的key会被遗弃。
在字典中使用多个key，将返回一个无序列表，如果要排序,就用sorted(d.keys())。
>>> tel = {"zhangsan":133,"lisi":134,"wangwu":135}
>>> tel["zhaoliu"] = 136
>>> tel
{'zhangsan': 133, 'lisi': 134, 'wangwu': 135, 'zhaoliu': 136}
>>> tel
{'zhangsan': 133, 'lisi': 134, 'wangwu': 135, 'zhaoliu': 136}
>>> tel["zhangsan"]
133
>>> tel["zhang"]
Traceback (most recent call last):
File "<pyshell#24>", line 1, in <module>
tel["zhang"]
KeyError: 'zhang'
>>> del tel["zhaoliu"]
>>> tel
{'zhangsan': 133, 'lisi': 134, 'wangwu': 135}
>>> list(tel.keys())
['zhangsan', 'lisi', 'wangwu']
>>> sorted(tel.keys())
['lisi', 'wangwu', 'zhangsan']
>>> "zhangsan" in tel
True
>>> "zhaoliu" in tel
False
dirt()构造函数直接通过键值对构建字典:
>>> dict([("zhangsan",133),("lisi",134),("wangwu",135)])
{'zhangsan': 133, 'lisi': 134, 'wangwu': 135}
另外，dict comprehensions可以从任意键值对表达式中创建字典
>>> {x: x**2 for x in (2,4,6)}
{2: 4, 4: 16, 6: 36}
当key是字符串时，更容易使用关键字参数指定键值对:
>>> dict(zhangsan=133,lisi=134,wangwu=135)
{'zhangsan': 133, 'lisi': 134, 'wangwu': 135}
