python - 列表

标签（空格分隔）： python-数据结构

---

一、列表定义

1.1 定义

• [x] 定义：

  • 有序的,可变的元素集合

  • [x] 定义方式
    list() --> new empty list
    list(iterable) ---> 存放一个可迭代对象
    列表不能一开始就定义大小

---

二、列表常用方法

2.1 查询元素

2.1.1 index(value,[start,[stop])

• 功能:
  • 按照索引查找元素 <默认从左往右查找>
• 工作方式:
  • 通过值value，从指定区间查询列表的元素是否存在,匹配第一个就立即 返回索引;
  • 匹配不到，抛出异常 IndexError

---

2.1.2 count(value)

• 功能:
  • 统计列表中匹配value的次数
• 时间复杂度:
  • Oⁿ

---

2.1.3 时间复杂度比较

index 和 count 方法都是O(n) ----> 都是采用迭代的方式
随着列表数据规模的增大,而效率下降

---

2.2 新增元素

2.2.1 append(object)

• 功能:
  • 列表尾部追加元素，返回None
• 工作方式：
  • 返回None意味着没有新的列表产生,是原地修改
• 时间复杂度为：
  • O¹

---

2.2.2 insert(index,object)

• 功能:
  • 在指定的索引index处插入元素object
• 工作方式:
  • 返回None意味着没有新的列表产生,是原地修改;
  • 索引可以超出上下界,超出时默认为尾部和头部追加元素
• 时间复杂度为：
  • Oⁿ >>> 效率低,前面，中间位置操作元素,会引发效率问题
  • 正索引越界，则相当于尾部追加，时间复杂度为 O¹

(列表少用，queue队列常用-->效率问题)

---

2.2.3 extend(iteratable)

• 功能:
  • 将可迭代对象的元素追加进来，返回None
• 工作方式:
  • 就地修改
• 用法实例:

>>> A = [1,2,3,4,5]
>>> B = ['A','B','C','D','E','F','G']
>>> A.extend(B) # 向A列表中加入B列表
>>> A
... [1,5,'A','G']

---

2.2.4 + ---> New list

• 功能:
  • 连接操作,将列表连接起来
• 工作方式:
  • 产生新的列表,原列表不变,本质调用的是__add__()方法

---

2.2.5 * --->> New list

• 功能：
  • 重复操作,将本列表元素重复n次
• 工作方式:
  • 返回新的列表

---

2.3 删除元素

2.3.1 remove(value)

• 功能:
  • 从左往右查找第一个匹配value的值,移除;
  • 如果没有找到，则引发异常 ValueError
• 修改方式:
  • 就地修改
• 时间复杂度为：
  • O(n) 效率低 ---> 中间位置操作元素,会引发效率问题

慎用,中间位置操作元素,会引发效率问题

---

2.3.2 pop([index])

• 修改方式:
  • item (有返回值,可以使用变量接收,然后进行操作)
• 工作方式：
  • 不指定索引 index,默认从列表尾部弹出一个元素并删除
    • 尾部操作元素,不会引起其他元素的改变
      
    • 时间复杂度：
      • O¹
  • 指定索引 index,从列表的index位置弹出一个元素,并删除
    • 中间操作元素,涉及到对其他元素位置的改变
    • 时间复杂度：
      • Oⁿ

---

2.3.3 clear()

• 功能:
  • 清除列表所有元素,剩下一个空列表
    • 清除元素本身就是一个一个删除,本身就存在效率问题
    • 元素清除后,会引发调用对对象的释放操作,从而引发垃圾回收机制的处理,占用内存

慎用,逐一删除引发效率问题,特别是大数据集下； 同时元素删除后，会引发垃圾回收机制；

---

2.4 列表其他操作

2.4.1 reverse()

• 功能：
  • 将列表元素反转,返回None
• 修改方式：
  • 就地修改
• 时间复杂度
  • O^n/2

---

2.4.2 sort(key=None,reverse=False)

• 功能:
  • 对列表元素进行排序,就地修改,默认升序排列
  • reverse为True,反转,降序排列
  • key一个函数,指定key如何排序 (高阶函数 --> 函数的参数是函数)

尽量少用,同样会引发效率问题

---

2.4.3 in / not in

• 功能
  • 成员运算符

---

2.4.4 内置函数reversed()

• 功能
  • 内置函数reversed()也可以翻转

---

三、深拷贝和浅拷贝问题

copy() ---> list

• 功能:

  • 返回一个新的列表

    浅拷贝(shadow copy)

  • 影子拷贝，遇到引用类型,只是复制了一个引用而已,
  • 复杂结构中拷贝的是内存地址,因此操作时会引起两边元素的变化

  >>> list1 = [1,[2,5],6]
  >>> list2 = list1.copy()
  >>> list2 == list1  
  ... True    （ == 是值判断）
  >>> list2 is list1  
  ... False   ( is 是比较内存地址是否一致 )
  >>> list1 = list2     （赋值时，实际上是内存地址的拷贝）
  >>> list2[1][1] = 20    (此处对拷贝列表进行修改)
  >>> list2
  ... [1,20,6]
  >>> list1
  ... [1,6]
  >>> list1 == list2  
  ... True

  浅拷贝:导致嵌套结构拷贝的是内存地址,因此操作时会引起两边元素的变化

深拷贝

• [x] copy模块提供了deepcopy

>>> import deepcopy
>>> list3 = [1,6]
>>> list4 = copy.deepcopy(list3)
>>> list3 == list4
... True
>>> list4[1][1] = 30
>>> list4 
... [1,30,6]
>>> list3
... [1,6]
>>> list3 == list4
... False (此处为深度拷贝)

深拷贝: 是根据源数据进行递归创建，拷贝，因此此处不再是拷贝的内存地址

---

四、随机数模块

• random 模块
  random.randint(a,b) 返回[a,b]之间的整数
  random.choice(seq) 从非空系列的元素中随机挑选一个返回
  random.randrange([start,]stop,[step]) 从指定范围内,按指定基数递增的集合中获取一个随机数,基数缺省值为1 (前包后不包)
  random.shuffle(list) ---> 返回None,就地打乱列表元素

---

五、练习题

5.1 结合列表相关知识，求 100以内的素数

• 需求分析:
  • 概念: 素数：即只能被 1 和本身整除的数
  • 如果一个数不能被素数整除，则这个数就是素数（合数一定可以分解成素数的乘积）
• 算法思路：
  • 合数一定可以被分解成素数的乘积； 因此，如果一个数不能被素数整除，则这个数就是素数；
  • 优化点：还是可以计算一半，即只用将小于 n**2 的 数来除计算
    ```python
    items = list(range(2,101)) # 待计算数据
    result = [2] # 素数列表

for item in items:
for i in result:
if item % i == 0:
break
else:
result.append(item)

print(result) # 打印素数列表

### **5.2 杨辉三角的多种方式实现**

- **优化思路：**
    - **1、末尾补0 的方式**
        - 考虑时间复杂度,通过负索引的方式实现;但使用append的方法尾部追加属于多次开辟空间
    - **2、一次开辟空间**
        - 主要从空间复杂度;一次性开辟列表空间的方式,节约内存空间,提高效率

功能未完全实现，

result = [[1]]
n = 10

for i in range(1,n):
line = result[i-1][:]
line.append(0)
temp = line[:] # 多余步骤

for j in range(i):
    v = line[j] + line[j+1] 
    line[j+1] = v   # 如上不用 temp再次拷贝，则此处需要使用中间变量接; 后续的计算一半目前无法实现
    
result.append(line)

打印杨辉三角

for i in result:
print(i)

```