数据结构笔记pdf

㈠ 利用Python进行数据分析笔记：3.1数据结构

元组是一种固定长度、不可变的Python对象序列。创建元组最简单的办法是用逗号分隔序列值：

tuple 函数将任意序列或迭代器转换为元组：

中括号 [] 可以获取元组的元素， Python中序列索引从0开始 ：

元组一旦创建，各个位置上的对象是无法被修改的，如果元组的一个对象是可变的，例如列表，你可以在它内部进行修改：

可以使用 + 号连接元组来生成更长的元组：

元组乘以整数，则会和列表一样，生成含有多份拷贝的元组：

将元组型的表达式赋值给变量，Python会对等号右边的值进行拆包：

拆包的一个常用场景就是遍历元组或列表组成的序列：

*rest 用于在函数调用时获取任意长度的位置参数列表：

count 用于计量某个数值在元组中出现的次数：

列表的长度可变，内容可以修改。可以使用 [] 或者 list 类型函数来定义列表：

append 方法将元素添加到列表尾部：

insert 方法可以将元素插入到指定列表位置：
（ 插入位置范围在0到列表长度之间 ）

pop 是 insert 的反操作，将特定位置的元素移除并返回：

remove 方法会定位第一个符合要求的值并移除它：

in 关键字可以检查一个值是否在列表中；
not in 表示不在：

+ 号可以连接两个列表：

extend 方法可以向该列表添加多个元素：

使用 extend 将元素添加到已经存在的列表是更好的方式，比 + 快。

sort 方法可以对列表进行排序：

key 可以传递一个用于生成排序值的函数，例如通过字符串的长度进行排序：

bisect.bisect 找到元素应当被插入的位置，返回位置信息
bisect.insort 将元素插入到已排序列表的相应位置保持序列排序

bisect 模块的函数并不会检查列表是否已经排序，因此对未排序列表使用bisect不会报错，但是可能导致不正确结果

切片符号可以对大多数序列类型选取子集，基本形式是 [start:stop]
起始位置start索引包含，结束位置stop索引不包含

切片还可以将序列赋值给变量：

start和stop可以省略，默认传入起始位置或结束位置，负索引可以从序列尾部进行索引：

步进值 step 可以在第二个冒号后面使用， 意思是每隔多少个数取一个值：

对列表或元组进行翻转时，一种很聪明的用法时向步进值传值-1：

dict(字典)可能是Python内建数据结构中最重要的，它更为常用的名字是 哈希表 或者 关联数组 。
字典是键值对集合，其中键和值都是Python对象。
{} 是创建字典的一种方式，字典中用逗号将键值对分隔：

你可以访问、插入或设置字典中的元素,:

in 检查字典是否含有一个键：

del 或 pop 方法删除值， pop 方法会在删除的同时返回被删的值，并删除键：

update 方法将两个字典合并：
update方法改变了字典元素位置，对于字典中已经存在的键，如果传给update方法的数据也含有相同的键，则它的值将会被覆盖。

字典的值可以是任何Python对象，但键必须是不可变的对象，比如标量类型（整数、浮点数、字符串）或元组（且元组内对象也必须是不可变对象）。
通过 hash 函数可以检查一个对象是否可以哈希化（即是否可以用作字典的键）：

集合是一种无序且元素唯一的容器。

set 函数或者是用字面值集与大括号，创建集合：

union 方法或 | 二元操作符获得两个集合的联合即两个集合中不同元素的并集：

intersection 方法或 & 操作符获得交集即两个集合中同时包含的元素：

常用的集合方法列表：

和字典类似，集合的元素必须是不可变的。如果想要包含列表型的元素，必须先转换为元组：

㈡ 鏁版嵁缁撴瀯绗旇

链鏂囧皢浠嬬粛浜屽弶镙戠殑鐩稿叧鐭ヨ瘑锛屽寘𨰾浜屽弶镙戠殑缁撶偣涓鏁般佹爲娣便侀亶铡嗙瓑鍐呭广
🌳浜屽弶镙戠殑缁撶偣涓鏁
浜屽弶镙戠殑绗琄灞备笂锛屾渶澶氭湁2镄刱-1娆″箓涓缁撶偣锛涙繁搴︿负M镄勪簩鍙夋爲链澶氭湁2镄凪娆″箓-1涓缁撶偣锛涙繁搴︿负5镄勬弧浜屽弶镙戜腑锛屽彾瀛愮粨镣圭殑涓鏁颁负2镄(5-1)娆″箓銆
🌲镙戞繁
锅囧畾镙圭粨镣圭殑灞傛℃槸0锛屽惈链15涓缁撶偣镄勪簩鍙夋爲镄勬渶灏忔爲娣辨槸3銆
🔍浜屽垎娉曟煡镓
瀵逛簬涓涓闀垮害涓10镄勬帓濂藉簭镄勮〃鐢ㄤ簩鍒嗘硶镆ユ垒锛岃嫢镆ユ垒涓嶆垚锷燂纴镊冲皯闇瑕佹瘆杈幂殑娆℃暟涓3銆

㈢ 鏁版嵁缁撴瀯瀛︿範绗旇帮细濡备綍镟村ソ鍦版帉鎻＄粡鍏哥畻娉

鏁版嵁缁撴瀯鏄璁＄畻链虹戝︿腑镄勯吨瑕佸熀纭锛屾帉鎻″ソ鏁版嵁缁撴瀯瀵逛簬缂栫▼鑳藉姏鍜岄梾棰樿В鍐宠兘锷涚殑鎻愬崌镊冲叧閲嶈併傛湰鏂囧皢浠嬬粛濡备綍镟村ソ鍦版帉鎻＄粡鍏哥畻娉曪纴甯锷╄昏呮洿濂藉湴搴旂敤鏁版嵁缁撴瀯銆
📚镓揿ソ锘虹
缂栫▼锘虹鐭ヨ瘑鏄鎺屾彙鏁版嵁缁撴瀯镄勫墠鎻愶纴鍙链夋墦濂藉熀纭锛屾墠鑳芥洿濂藉湴搴旂敤鏁版嵁缁撴瀯銆傚洜姝わ纴鍦ㄥ︿範鏁版嵁缁撴瀯涔嫔墠锛岀‘淇濅綘宸茬粡鎺屾彙浜嗙紪绋嬬殑锘虹鐭ヨ瘑锛岃繖镙锋墠鑳戒负钖庣画镄勫︿範镓扑笅鍧氩疄锘虹銆
🤔娣卞叆鐞呜В绠楁硶阃昏緫
瀵逛簬姣忎釜缁忓吀绠楁硶锛岃佹繁鍏ョ悊瑙ｅ叾阃昏緫杩囩▼锛岃繖链夊姪浜庝綘镟村ソ鍦板簲鐢ㄥ畠浠銆傚彧链夋繁鍏ョ悊瑙ｇ畻娉旷殑阃昏緫锛屾墠鑳芥洿濂藉湴搴旂敤瀹冧滑瑙ｅ喅瀹为檯闂棰樸
💻镊宸辫捐℃暟鎹瀛桦偍缁撴瀯
灏濊瘯镊宸辫捐℃暟鎹瀛桦偍缁撴瀯骞剁紪鍐欑畻娉曚唬镰侊纴杩欐牱鍙浠ュ姞娣变綘镄勭悊瑙ｃ傞氲繃镊宸辩殑璁捐″拰缂栧啓锛屼綘鍙浠ユ洿濂藉湴鐞呜В鏁版嵁缁撴瀯鍜岀畻娉旷殑瀹炵幇杩囩▼銆
🔍瀵规瘆浼桦寲绠楁硶
涓庣粡鍏哥畻娉旷殑浠ｇ爜杩涜屽规瘆锛屾垒鍑鸿嚜宸辩殑涓嶈冻锛屼粠绠楁硶璁捐″拰绠楁硶澶嶆潅搴︿袱涓鏂归溃杩涜屼紭鍖栵纴鐩磋呖瀹屽叏鎺屾彙缁忓吀绠楁硶镄勫疄鐜拌繃绋嬨傚彧链変笉鏂鍦板规瘆鍜屼紭鍖栵纴镓嶈兘镟村ソ鍦版帉鎻＄粡鍏哥畻娉旷殑瀹炵幇杩囩▼銆
🚀鎸戞垬镟村氱畻娉曢梾棰
鍦ㄥ﹀畬鏁版嵁缁撴瀯钖庯纴浣犲皢浼氩彂鐜拌嚜宸辩殑缂栫▼鑳藉姏鍜岄梾棰樿В鍐宠兘锷涙湁浜嗘樉镢楃殑鎻愬崌銆傜幇鍦锛屾槸镞跺欑户缁鍓嶈繘锛屾写鎴樻洿澶氱殑绠楁硶闂棰树简锛

㈣ 数据结构与算法之美笔记——散列表（上）

摘要:

我们已经知道随机访问数组元素时间复杂度只有 ，效率极高，当我们想利用数组的这个特性时就需要将元素下标与存储信息对应。例如，一个商店只有四件商品，依次编号 0 至 3，这样就可以将四件商品信息按照编号对应下标的方式存储到数组中，依据编号就可以快速从数组中找到相应商品信息。

如果一段时间之后，商店盈利并且重新进货 100 件商品，商家想对大量商品在编号上区分类别，这时候需要使用类别编号加顺序编号的方式标识每件商品，这种编号变得复杂，并不能直接对应数组下标，此时的商品编号又该如何对应数组下标以实现快速查找商品的功能？这时候我们可以将类别编号去除之后按照顺序编号对应数组下标，同样也能享受数组高效率随机访问的福利。这个例子中，商品编号称为“ 键 ”或“ 关键字 ”，将键转化为数组对应下标的方法就是“ 散列函数 ”或“ Hash 函数 ”，由散列函数生成的值叫做“ 散列值 ”或“ Hash 值 ”，而这样的数组就是散列表。

从散列表的原理来看，数据通过散列函数计算得到散列值是关键，这个步骤中散列函数又是其中的核心，一个散列函数需要遵守以下三个原则。

因为散列函数生成的散列值对应数组下标，而数组下标就是非负整数，所以需要满足第一个原则；两个相等的数据经过散列算法得到的散列值肯定相等，否则利用散列值在散列表中查找数据就无从谈起；至于第三个原则虽然在情理之中，却不那么容易做到，即使是被广泛运用的散列算法也会出现散列值冲突的情况，导致无法满足第三个原则。

散列函数作为散列表的核心部分，必然不能拖散列表的执行效率后腿，毕竟散列表的查询、插入和删除操作都需要经过散列函数，所以散列函数不能太复杂，执行效率不能太低。由于散列函数不可避免地都会出现散列冲突情况，散列函数要尽量降低散列冲突，使散列值能够均匀地分布在散列表中。

解决散列冲突主要有“ 开放寻址 ”（open addressing）和“ 链表法 ”（chaining）两类方法。

开放寻址法是指插入操作时，当生成的散列值对应槽位已经被其他数据占用，就探测空闲位置供插入使用，其中探测方法又分为“ 线性探测 ”（Linear Probing）、“ 二次探测 ”（Quadratic Probing）和“ 双重散列 ”（Double hashing）三种。

线性探测是其中较为简单的一种，这种探测方式是当遇到散列冲突的情况就顺序查找（查找到数组尾部时转向数组头部继续查找），直到查找到空槽将数据插入。当进行查找操作时，也是同样的操作，利用散列值从散列表中取出对应元素，与目标数据比对，如果不相等就继续顺序查找，直到查找到对应元素或遇到空槽为止，最坏情况下查找操作的时间复杂度可能会下降为 。

散列表除了支持插入和查找操作外，当然也支持删除操作，不过并不能将需删除的元素置为空。如果删除操作是将元素置为空的话，查找操作遇到空槽就会结束，存储在被删除元素之后的数据就可能无法正确查找到，这时的删除操作应该使用标记的方式，而不是使用将元素置空，当查找到被标识已删除的元素将继续查找，而不是就此停止。

线性探测是一次一个元素的探测，二次探测就是使用都是线性探测的二次方步长探测。例如线性探测是 ，那二次探测对应的就是 。

双重探测是当第一个散列函数冲突时使用第二个散列函数运算散列值，利用这种方式探测。例如，当 冲突时，就使用 计算散列值，如果再冲突就使用 计算散列值，依此类推。

关于散列表的空位多少使用“ 装载因子 ”（load factor）表示，装载因子满足数学关系 ，也就是说装载因子越大，散列表的空闲空间越小，散列冲突的可能性也就越大，一般我们会保持散列表有一定比例的空闲空间。

为了保持散列表一定比例的空闲空间，在装载因子到达一定阈值时需要对散列表数据进行搬移，但散列表搬移比较耗时。你可以试想下这样的步骤，在申请一个新的更大的散列表空间后，需要将旧散列表的数据重新通过散列函数生成散列值，再存储到新散列表中，想想都觉得麻烦。

散列表搬移的操作肯定会降低散列表的操作效率，那能不能对这一过程进行改进？其实可以将低效的扩容操作分摊至插入操作，当装载因子达到阈值时不一次性进行散列表搬移，而是在每次插入操作时将一个旧散列表数据搬移至新散列表，这样搬移操作的执行效率得到了提高，插入操作的时间复杂度也依然能保持 的高效。当新旧两个散列表同时存在时查询操作就要略作修改，需先在新散列表中查询，如果没有查找到目标数据再到旧散列表中查找。

当然，如果你对内存有更高效的利用要求，可以在装载因子降低至某一阈值时对散列表进行缩容处理。

除了开放寻址之外，还可以使用链表法解决散列冲突的问题。散列值对应的槽位并不直接存储数据，而是将数据存储在槽位对应的链表上，当进行查找操作时，根据散列函数计算的散列值找到对应槽位，再在槽位对应的链表上查找对应数据。

链表法操作的时间复杂度与散列表槽位和数据在槽位上的分布情况有关，假设有 n 个数据均匀分布在 m 个槽位的散列表上，那链表法的时间复杂度为 。链表法可以不用像开放寻址一样关心装载因子，但需要注意散列函数对散列值的计算，使链表结点能够尽可能均匀地分布在散列表槽位上，避免散列表退化为链表。有时黑客甚至会精心制造数据，利用散列函数制造散列冲突，使数据集中某些槽位上，造成散列表性能的极度退化。

面对这样的恶意行为散列表只能坐以待毙吗？其实不然，当槽位上的链表过长时，可以将其改造成之前学习过的跳表等，链表改造为跳表后查询的时间复杂度也只是退化为 ，依然是可以接受的范围。

链表法在存储利用上比开放寻址更加高效，不用提前申请存储空间，当有新数据时申请一个新的结点就行。而且链表法对装载因子也不那么敏感，装载因子的增高也只是意味着槽位对应的链表更长而已，链表增长也有将链表改造为跳表等结构的应对策略，所以链表法在装载因子超过 1 的情况下都可保持高效。

开放寻址不存在像链表法一样有链表过长而导致效率降低的烦恼，不过装载因子是开放寻址的晴雨表，装载因子过高会造成散列冲突机率的上升，开放寻址就需要不断探测空闲位置，算法的执行成本会不断被提高。而且在删除操作时只能将数据先标记为删除，对于频繁增删的数据效率会受到影响。

当然也可以在这种风险出现前进行散列表的动态扩容，不过这样就会出现大量空闲的存储空间，导致存储的利用效率过低，这种现象在数据量越大的情况下越明显。所以开放寻址比较适用于数据量较小的情况。

链表法对于散列冲突的处理更加灵活，同时对存储空间的利用效率也更高，但链表结点除了存储数据外还需要存储指针，如果存储数据较小指针占用的存储甚至会导致整体存储翻倍的情况，但存储数据较大时指针占用的存储也就可以忽略不计，所以链表法较适合存储数据对象较大，但频繁的增删操作不会对链表法造成明显的影响。因为这样的特点，链表法更加适合大数据量，或者数据对象较大的时候，如果数据操作频繁，那链表法更是不二之选。

散列表由数组扩展而来，使用散列函数将键计算为散列值，散列值对应数据存储的数组下标。虽然散列表的执行效率较高，但会有散列冲突的问题，可以通过开放寻址法和链表法解决此问题。

开放寻址存储利用效率较低，适用数据量较小并且增删不频繁的情况，如果数据量较大，增删频繁的情况更加适用链表法，相对之下链表法更加普适。