《Python编程从0到1 视频教学版》_深入Python设计的本质_3.1 列表

【摘要】 本书摘自《Python编程从0到1 视频教学版》一书中第3章，第1节，作者是张頔。

3.1 列表

数组 (array)是以连续地址存储同类型数据的结构，它以最直接的方式使用内存。

Python 的列表类型 (list) 是基于数组构建的强大结构。列表提供了各种内建操作，如插 入、排序和二分查找等。这些操作的特性(尤其是时间复杂度)都建立在数组结构的基本 性质之上。 Python入门的初学者固然可以在短时间内掌握这些操作并运用之，但风险是他 们将在较长时间内“知其然而不知其所以然”并且满足于这种状态。本节将从内存和数组 的基本概念出发，展示列表的各种操作背后的运作原理。在对底层原理有所了解后，读者 将能对各种操作的性能做出预测而无须“道听途说”。

【学习目标】

· 了解数组的概念；

● 了解Python 列表的内部结构；

● 掌握列表的常用操作并了解其内部原理； ·掌握列表的排序和查找操作接口；

● 掌握并分析基于数组的数据结构的操作复杂度。

3.1.1 数组和内存

为了讲解列表的原理(包括之后各种结构的原理),必须先介绍内存和数组2。在本 小节中出现的代码片段均为 C 语言代码，无 C 语言基础的读者可以粗略浏览本小节，了 解相关原理即可。

1. 字节

内存的基本单元是字节， 内存地址依字节递增。字节由8个0/1 存储单元(比 特(bit))③组成，如图3.1 所示。故单个字节可以存储2⁸=256 个不同的值(00000000)2- (11111111)2。这些值被程序解释为不同的含义，如：

·整数：例如(00000000)2对应0,(01111111)2对应(127)10;

·ASCI  码字符：例如(01001000)2对应字符H。

想表示更复杂的信息，则需采用双字节或更多字节。如更大范围的整数、浮点数、64位地址和更大的字符集。也可通过精心设计的编码，用可变字节数量表示更大集合的数据， 如 UTF-8 字符编码。

用0/1序列表示各种具体和抽象概念的手段称为“编码”。例如色彩可以被编码为不 同的形式：依据人眼的三种感光细胞的结构被编码为 RGB  格式，或为了彩色电视信号传 输便利被编码为IUV 格式。不论采用哪一种编码方式，基本目的都是以0/1序列传输图片 或视频。

2. 内存

程序需要使用内存时要向运行环境°申请。 C 语言中malloc 函数用来申请指定大小的 内存，并返回所分配内存区域的首地址。如下C 代码片段请求100字节内存，并将首地址 保存于泛型指针变量p。

void  *  p  =  malloc(100);

如需指定此段内存存储的数据类型为32位带符号整数类型，则需使用 int类型指针指向首地址：

int   *  q  =  malloc(100);

在算法分析中常常认为对某一 内存地址的访问在 O(1) 时间内完成。当使用 q[10]访问 第10个整数时，编译器会根据指针q 的类型计算出地址偏移量40进行读写操作。如果对 内存地址的访问具有 O(1) 时间复杂度，那么数组索引访问也能在常数时间内完成。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们 18664393530@aliyun.com 处理，核实后本网站将在24小时内删除侵权内容。