Python数据结构和算法

数据结构和算法 评论

类 都是对数据的构成（状态）以及数据能做什么（行为）的描述。
由于类的使用者只能看到数据项的状态和行为，因此类与抽象数据类型是相似的、

在面向对象编程范式中，数据项被称作 对象 一个对象就是类的一个实例。

1.内建原子数据结构
python是通过两种内建数据类型实现整数类型和浮点数类型的，相应的python类就是 int 和 float 。

列表

列表 是零个或多个指向 Python 数据对象的引用的有序集合，通过在方括号内以逗号分隔的一系列值来表达。空列表就是 []。列表是异构的，这意味着其指向的数据对象不需要都是同一个类，并且这一集合可以被赋值给一个变量。下面的代码段展示了列表含有多个不同的 Python 数据对象。

元组 通常写成由括号包含并且以逗号分隔的一系列值。与序列一样，元组允许之前描述的任一操作。

列表提供的方法

方法名 用法 解释
append alist.append(item) 在列表末尾添加一个新元素
insert alist.insert(i,item) 在列表的第! i 个位置插入一个元素
pop alist.pop() 删除并返回列表中最后一个元素
pop alist.pop(i) 删除并返回列表中第 i 个位置的元素
sort alist.sort() 将列表元素排序
reverse alist.reverse() 将列表元素倒序排列
del del alist[i] 删除列表中第 i 个位置的元素
index alist.index(item) 返回 item 第一次出现时的下标
count alist.count(item) 返回 item 在列表中出现的次数
remove alist.remove(item) 从列表中移除第一次出现的 item

对应输出：

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
>>> myList
[1024, 3, True, 6.5]
>>> myList.append(False)
>>> myList
[1024, 3, True, 6.5, False]
>>> myList.insert(2,4.5)
>>> myList
[1024, 3, 4.5, True, 6.5, False]
>>> myList.pop()
False
>>> myList
[1024, 3, 4.5, True, 6.5]
>>> myList.pop(1)
3
>>> myList
[1024, 4.5, True, 6.5]
>>> myList.pop(2)
True
>>> myList
[1024, 4.5, 6.5]
>>> myList.sort()
>>> myList
[4.5, 6.5, 1024]
>>> myList.reverse()
>>> myList
[1024, 6.5, 4.5]
>>> myList.count(6.5)
1
>>> myList.index(4.5)
2
>>> myList.remove(6.5)
>>> myList
[1024, 4.5]
>>> del myList[0]
>>> myList
[4.5]

字符串

字符串是零个或多个字母、数字和其他符号的有序集合。这些字母、数字和其他符号被称为 字符。常量字符串值通过引号（单引号或者双引号均可）与标识符进行区分。

1
2
3
4
5
6
7
8
9
>>> "David"
'David'
>>> myName = "David"
>>> myName[3]
'i'
>>> myName*2
'DavidDavid'
>>> len(myName)
5

字符串提供的方法

方法名 用法 解释
center astring.center(w) 返回一个字符串，原字符串居中，使用空格填充新字符串，使其长度为 w
count astring.count(item) 返回 item 出现的次数
ljust astring.ljust(w) 返回一个字符串，将原字符串靠左放置并填充空格至长度 w
rjust astring.rjust(w) 返回一个字符串，将原字符串靠右放置并填充空格至长度 w
lower astring.lower() 返回均为小写字母的字符串
upper astring.upper() 返回均为大写字母的字符串
find astring.find(item) 返回 item 第一次出现时的下标
split astring.split(schar) 在 schar 位置将字符串分割成子串，不填则默认分割空格和换行符

列表和字符串的区别：

  • 列表有 可修改性 ，字符串没有

集合

集（set）是由零个或多个不可修改的 Python 数据对象组成的无序集合。集不允许重复元素，并且写成由花括号包含、以逗号分隔的一系列值。空集由 set() 来表示。集是异构的，并且可以通过下面的方法赋给变量。

Python 集支持的运算

运算名 运算符 解释
成员 in 询问集中是否有某元素
长度 len 获取集的元素个数
| aset | otherset 返回一个包含 aset 与 otherset 所有元素的新集
& aset & otherset 返回一个包含 aset 与 otherset 共有元素的新集
- aset - otherset 返回一个集，其中包含只出现在 aset 中的元素
<= aset <= otherset 询问 aset 中的所有元素是否都在 otherset 中

Python 集提供的方法

方法名 用法 解释
union aset.union(otherset) 返回一个包含 aset 和 otherset 所有元素的集
intersection aset.intersection(otherset) 返回一个仅包含两个集共有元素的集
difference aset.difference(otherset) 返回一个集，其中仅包含只出现在 aset 中的元素
issubset aset.issubset(otherset) 询问 aset 是否为 otherset 的子集
add aset.add(item) 向 aset 添加一个元素
remove aset.remove(item) 将 item 从 aset 中移除
pop aset.pop() 随机移除 aset 中的一个元素
clear aset.clear() 清除 aset 中的所有元素 
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
>>> mySet
{False, 4.5, 3, 6, 'cat'}
>>> yourSet = {99,3,100}
>>> mySet.union(yourSet)
{False, 4.5, 3, 100, 6, 'cat', 99}
>>> mySet | yourSet
{False, 4.5, 3, 100, 6, 'cat', 99}
>>> mySet.intersection(yourSet)
{3}
>>> mySet & yourSet
{3}
>>> mySet.difference(yourSet)
{False, 4.5, 6, 'cat'}
>>> mySet - yourSet
{False, 4.5, 6, 'cat'}
>>> {3,100}.issubset(yourSet)
True
>>> {3,100}<=yourSet
True
>>> mySet.add("house")
>>> mySet
{False, 4.5, 3, 6, 'house', 'cat'}
>>> mySet.remove(4.5)
>>> mySet
{False, 3, 6, 'house', 'cat'}
>>> mySet.pop()
False
>>> mySet
{3, 6, 'house', 'cat'}
>>> mySet.clear()
>>> mySet

字典

字典 是无序结构，由相关的元素对构成，其中每对元素都由一个键和一个值组成。这种键–值对通常写成键:值的形式。字典由花括号包含的一系列以逗号分隔的键–值对表达，如下所示。

1
2
>>> capitals = {'Iowa':'DesMoines','Wisconsin':'Madison'}
>>> capitals{'Wisconsin':'Madison', 'Iowa':'DesMoines'}

可以通过键访问其对应的值，也可以向字典添加新的键–值对。
访问字典的语法与访问序列的语法十分相似，只不过是使用键来访问，而不是下标。添加新值也类似。

1
2
3
4
5
6
7
>>> capitals['Iowa'] = 'DesMoines'
>>> capitals['Utah'] = 'SaltLakeCity'
>>> capitals{'Utah':'SaltLakeCity', 'Wisconsin':'Madison', 'Iowa':'DesMoines'}
>>> capitals['California']='Sacramento'
>>> capitals{'Utah':'SaltLakeCity', 'Wisconsin':'Madison', 'Iowa':'DesMoines', 'California':'Sacramento'}
>>> len(capitals)
>>> 4

需要谨记，字典并不是根据键来进行有序维护的。第一个添加的键–值对（'Utah':'SaltLakeCity'）被放在了字典的第一位，第二个添加的键–值对（'California':'Sacramento'）则被放在了最后。

字典的运算

keys、values 和 items 方法均会返回包含相应值的对象。可以使用 list 函数将字典转换成列表。

运算名 运算符 解释
[] myDict[k] 返回与 k 相关联的值，如果没有则报错
in key in adict 如果 key 在字典中，返回 True，否则返回 False
del del adict[key] 从字典中删除 key 的键–值对

字典的方法

get 方法有两种版本。如果键没有出现在字典中，get 会返回 None。然而，第二个可选参数可以返回特定值。

方法名 用法 解释
keys adict.keys() 返回包含字典中所有键的 dict_keys 对象
values adict.values() 返回包含字典中所有值的 dict_values 对象
items adict.items() 返回包含字典中所有键–值对的 dict_items 对象
get adict.get(k) 返回 k 对应的值，如果没有则返回 None
get adict.get(k, alt) 返回 k 对应的值，如果没有则返回 alt

字典实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
>>> phoneext={'david':1410, 'brad':1137}
>>> phoneext
{'brad':1137, 'david':1410}
>>> phoneext.keys()
dict_keys(['brad', 'david'])
>>> list(phoneext.keys())
['brad', 'david']
>>> phoneext.values()
dict_values([1137, 1410])
>>> list(phoneext.values())
[1137, 1410]
>>> phoneext.items()
dict_items([('brad', 1137), ('david', 1410)])
>>> list(phoneext.items())
[('brad', 1137), ('david', 1410)]
>>> phoneext.get("kent")
>>> phoneext.get("kent", "NO ENTRY")
'NO ENTRY'
>>>

输入和输出

程序经常要和用户进行交互。

目前的大多数程序使用对话框作为要求用户提供某种输入的方式。尽管 Python 确实有方法来创建这样的对话框，但是可以利用更简单的函数。Python 提供了一个函数，它使得我们可以要求用户输入数据并且返回一个字符串的引用。这个函数就是 input。

提示字符串

input 函数接受一个字符串作为参数。由于该字符串包含有用的文本来提示用户输入，因此它经常被称为 提示字符串。举例来说，可以像下面这样调用 input。

不论用户在提示字符串后面输入什么内容，都会被存储在 aName 变量中。使用 input 函数，可以非常简便地写出程序，让用户输入数据，然后再对这些数据进行进一步处理。例如，在下面的两条语句中，第一条要求用户输入姓名，第二条则打印出对输入字符串进行一些简单处理后的结果。

1
2
3
4
5
aName = input("Please enter your name ")
print("Your name in all capitals is ",
        aName.upper(),
        "and has length",
        len(aName))

需要注意的是，input 函数返回的值是一个字符串，它包含用户在提示字符串后面输入的所有字符。如果需要将这个字符串转换成其他类型，必须明确地提供类型转换。在下面的语句中，用户输入的字符串被转换成了浮点数，以便于后续的算术处理。

1
2
3
sradius = input("Please enter the radius of the circle ")
radius = float(sradius)
diameter = 2 * radius

格式化字符串

print 函数为输出 Python 程序的值提供了一种非常简便的方法。它接受零个或者多个参数，并且将单个空格作为默认分隔符来显示结果。通过设置 sep 这一实际参数可以改变分隔符。此外，每一次打印都默认以换行符结尾。这一行为可以通过设置实际参数 end 来更改。下面是一些例子。

1
2
3
4
5
6
7
8
>>> print("Hello")
Hello
>>> print("Hello","World")
Hello World
>>> print("Hello","World", sep="***")
Hello***World
>>> print("Hello","World", end="***")
Hello World***

Python 提供了另一种叫作 格式化字符串 的方式。格式化字符串是一个模板，其中包含保持不变的单词或空格，以及之后插入的变量的占位符。例如，下面的语句包含 is 和 years old.，但是名字和年龄会根据运行时变量的值而发生改变。

1
print(aName, "is", age, "years old.")

使用格式化字符串，可以将上面的语句重写成下面的语句。

1
print("%s is %d years old." % (aName, age))

格式化字符串可用的类型声明

% 是字符串运算符，被称作 格式化运算符。

表达式的左边部分是模板（也叫格式化字符串），右边部分则是一系列用于格式化字符串的值。

格式化字符串可以包含一个或者多个转换声明。转换字符告诉格式化运算符，什么类型的值会被插入到字符串中的相应位置。

在上面的例子中，%s 声明了一个字符串，%d 则声明了一个整数。其他可能的类型声明还包括 i、u、f、e、g、c 和 %。

字符 输出格式
d、i 整数
u 无符号整数
f m.dddd 格式的浮点数
e m.dddde+/-xx 格式的浮点数
E m.ddddE+/-xx 格式的浮点数
g 对指数小于-4 或者大于 5 的使用 %e，否则使用 %f
c 单个字符
s 字符串，或者任意可以通过 str 函数转换成字符串的 Python 数据对象
% 插入一个常量 % 符号

格式化修改符

修改符 例子 解释
数字 %20d 将值放在 20 个字符宽的区域中
- %-20d 将值放在 20 个字符宽的区域中，并且左对齐
+ %+20d 将值放在 20 个字符宽的区域中，并且右对齐
0 %020d 将值放在 20 个字符宽的区域中，并在前面补上 0
. %20.2f 将值放在 20 个字符宽的区域中，并且保留小数点后 2 位
(name) %(name)d 从字典中获取 name 键对应的值 
1
2
3
4
5
6
7
8
9
10
11
>>> price = 24
>>> item = "banana"
>>> print("The %s costs %d cents" % (item,price))
The banana costs 24 cents
>>> print("The %+10s costs %5.2f cents" % (item,price))
The     banana costs 24.00 cents
>>> print("The %+10s costs %10.2f cents" % (item,price))
The     banana costs     24.00 cents
>>> itemdict = {"item":"banana","cost":24}
>>> print("The %(item)s costs %(cost)7.1f cents" % itemdict)
The banana costs    24.0 cents

控制结构

Python提供的标准的标准控制语句有 while 语句以及 for 语句。

1
2
3
4
5
6
7
8
9
10
11
>>> counter = 1
>>> while counter <= 5:
...     print("Hello, world")
...     counter = counter + 1
...

Hello, world
Hello, world
Hello, world
Hello, world
Hello, world

看下面这个例子。

1
while counter <= 10 and not done:

迭代语句只有在上面两个条件都满足的情况下才会被执行。变量 counter 的值需要小于或等于 10，并且变量 done 的值需要为 False（not False 就是 True），因此 True and True 的最后结果才是 True。

for在遍历每一个成员上非常的方便。例如：

1
2
3
4
5
6
7
8
>>> for item in [1,3,6,2,5]:
...    print(item)
...
1
3
6
2
5

列表解析式

列表可以通过使用迭代结构和分支结构来创建。这种方式被称为 列表解析式。通过列表解析式，可以根据一些处理和分支标准轻松创建列表。

举例来说，如果想创建一个包含前 10 个完全平方数的列表，可以使用以下的 for 语句。

1
2
3
4
5
>>> sqlist = []
>>> for x in range(1,11):
         sqlist.append(x*x)
>>> sqlist
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

进阶：使用列表解析式，只需一行代码即可创建完成。

1
2
3
>>> sqlist = [x*x for x in range(1,11)]
>>> sqlist
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

进阶：变量 x 会依次取由 for 语句指定的 1 到 10 为值。之后，计算 x*x 的值并将结果添加到正在构建的列表中。列表解析式也允许添加一个分支语句来控制添加到列表中的元素。

1
2
3
>>> sqlist = [x*x for x in range(1,11) if x%2 != 0]
>>> sqlist
[1, 9, 25, 49, 81]

例子：（力扣的原题：输出列表中非元音的字母并以大写形式返回）

1
2
>>>[ch.upper() for ch in 'comprehension' if ch not in 'aeiou']
['C', 'M', 'P', 'R', 'H', 'N', 'S', 'N']

函数

下面定义的简单函数会返回传入值的平方。

1
2
3
4
5
6
7
>>> def square(n):
...    return n**2
...
>>> square(3)
9
>>> square(square(3))
81

同样的，我们可以自己定义一个平方根函数 squareroot()

通过牛顿迭代法求解平方根

1
2
3
4
5
6
1.  def squareroot(n):
2.      root = n/2 #initial guess will be 1/2 of n
3.      for k in range(20):
4.          root = (1/2)*(root + (n / root))
5.
6.      return root

接下来，模拟调用这个函数

1
2
3
4
>>> squareroot(9)
3.0
>>> squareroot(4563)
67.549981495186216

面向对象：定义 类

算法分析相关

复杂度计算

大 O 表示法

如果可以通过观察循环结构和算法的方式快速判断出复杂度就算出师

异序词排序问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def anagramSolution1(s1, s2):
   alist = list(s2)

   pos1 = 0
   StillOK = True

   while pos1 < len(s1) and stillOK:
      pos2 = 0
      found = False
      while pos2 < len(alist) and not found:
         if s1[pos1] == alist[pos2]:
            found = True
         else:
            pos2 += 1
      
      if found:
         alist[pos2] = None
      else:
         stillOK = False
      
      pos1 += 1
   
   return stillOK
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def anagramSolution2(s1, s2):
   alist1 = list(s1)
   alist2 = list(s2)

   # 这里需要记住，常用的几类排序时间复杂度在 O(n^2) 或 O(nlogn)
   alist1.sort()
   alist2.sort()

   pos = 0
   matches = True

   while pos < len(s1) and matches:
      if alist1[pos] == alist2[pos]:
         pos += 1
      else:
         matches = False
   
   return matches
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def anagramSolution3(s1, s2):
   c1 = [0] * n
   c2 = [0] * n

   for i in range(len(s1)):
      pos = ord(s1[i]) - ord('a')
      c1[pos] += 1

   for i in range(len(s2)):
      pos = ord(s2[i] - ord('a'))
      c2[pos] += 1

   j = 0
   stillOk = True
   while j < 26 and stillOK:
      if c1[j] == c2[j]:
         j += 1
      else:
         stillOK = False

   return stillOk

第四个例子是最快的。因为没有循环嵌套，只有O(n)的复杂度。倘若需要考虑关于空间上的需求，那么第四个例子新开了额外的空间用于存储计数器，这种方式就是常说的：空间换时间的方法。

AndroidStudent & Coder

Happy Coding!