语言中数据结构的基本实现
✍️ 正文
各个编程语言中的实践
数据结构
数据结构的实际应用：元组，列表，字典，集合；序列，矩阵，数组，json
-
序列：被排成一列的对象（或事件）；这样，每个元素不是在其他元素之前，就是在其他元素之后。这里，元素之间的顺序非常重要。
- 序列：长度固定，且有序的字典
- 序列是有索引的，python的索引是从0开始的
-
tuple 元组：一种固定长度、不可变的列表
- tup = 4, 5, 6
- 复杂的元组 tup = (4, 5, 6), (7, 8)
- 将序列转换成元组：tuple([4, 5, 6])
- tup = tuple('string')
- 对象元组中存储的对象其自身是可变的，但是元组一旦创建，各个位置上的对象是无法被修改的
- tup=tuple(['foo',[1,2],True])
- tup[1]是列表，自身可变
- 而tup[2]是不可变的
- 使用+号可以连接元组
- 元组*整数，可以生成多份拷贝的元组请注意对象自身并没有复制，只是指向它们的引用进行了复制。
- 元组和列表一样，但元组只能通过内部的方法，不能直接修改里面的值
- 元组的拆包和历遍
- tup=(4,5,6)
- a,b,c=tup
- rest 和 *_ :余下的
- 实例方法
- tup.count()：计算某个数值出现的次数
-
list 列表：有序的集合，可以随时增加删除其中的元素。用[]表示
- list = [4, 5, 6] 或 list(tup)
- 和元组不同，列表的长度是可变的，包含的内容也是可以修改的。
- 实例方法
- insert（1, 'red'）：将元素插入到指定的列表位置
- append（'red'）：将元素添加到列表尾部
- pop（2）：将指定位置的元素移除并返回
- remove（'red'）：移除符合条件的第一个元素
- in；not in
- extend()：向列表添加多个元素
- sort（key=len）和sorted（）：排序
- del mylist[0]
- reversed（）：倒序
- bisect.bisect(list, 5)：二分搜索，元素应当被插入的位置
- bisect.insort()：将元素插到相应的位置
- zip（）序列元组之间的配对
- 生成的长度以最短的为准
- 切片 seq[0:9:2] 1到10的数字，步进2
- mapping = {}
- for i, value in enumerate(collection):
- mapping[v] = i
- 将序列映射到字典中去
-
序列：访问以上数据结构的方法索引和切片
- mylist[2]，索引
- mylist[2:6]，切片
- mylist[2:]
- mylist[2:-1]
-
dict 字典（哈希表，关联数组）：键值对集合，用逗号隔开。用{}表示
字典
{ 'a':'somevalue' 'b':[1,2,3,4] }- 和列表的区别是，列表是有序的，字典是无序的，字典通过键而不是偏移来读取数据。
- 字典的键必须是标量类型或元组
- 方法
- 取值d1['b']
- in ； not in
- pop（）
- del（）
- update（）：合并字典
- 对于相同键，新的将覆盖相同键原来的值
- get（）：
- value = dic.get(key, default_value)
- 取字典相应键的值，如果没有这个键，则返回默认的值
- list(d1.keys)：字典键的列表
- list(d1.values)：字典值的列表
-
set 集合：是一种无序且元素唯一的**容器。**可以认为集合也像字典，但是只有键没有值。不重复。
- set([2, 2, 2, 1, 3, 3])
- 或者用 {2, 2, 2, 1, 3, 3} 表示
- 联合：union（）并集：a | b
- 交集：intersection（）交集： a & b
- set([2, 2, 2, 1, 3, 3])
-
推导式：
- 列表推导式是最受欢迎的Python语言特性之一。它允许你过滤一个容器的元素，用一种简明的表达式转换传递给过滤器的元素，从而生成一个新的列表。
- 列表推导式：[expr for val in collection if condition]
- 字典推导式：
- 集合推导式：
-
具体的：
- 表格型数据，用逗号或者制表符分隔
- 多维数组或者矩阵
- ndarray：numpy中的多维数组
- Series：pandas中使用的一维的带标签的数组
- pd.Series(np.arange(10),index=list(string.ascii_uppercase[:10]))
- pd.Series.index的type是：pandas.core.indexes.base.Index
- pd.Series.value的type是numpy.ndarray
- **DataFrame：**pandas中二维的，Series容器
- 由键位列关联的多张表格数据
- 均匀或者非均匀时间序列
- 数据集转换为一种更适合分析、建模的结构形式。如果不进行转换，从数据集中提取特征形成一种结构形式也是可行的。例如，一个新闻文章的数据集可以被处理为一个词频表，然后再用于情感分析。
算法实例：leetCode解题
- 随机数的使用
- import "math/rand"
- 设置种子
- rand.Seed(666)
- 种子一样，产生的随机数一样
- 用时间作为种子数
- rand.Seed(time.Now().UnixNano())
- 产生随机数
- 随机很大的数
- rand.Int()
- 限制在100内的随机数
- rand.Intn(100)
- 随机很大的数
- 冒泡排序for i := 0; i< n-1; i++ { for j := 0; j<n-1-i: j++ { if a[j] > a[j+1] { a[j], a[j+1] = a[j+1], a[j] } } }
- 二叉树
- 红黑树
- B+树索引
- 解压序列赋值给多个变量data='nobody:*:-2:-2:Unprivileged User:/var/empty:/usr/bin/false' uname,*fields,homedir,sh=line.split(':')
- headpq查找的元素比较少的时候用nlargest()，nsmallest() 唯一一个min()，max() 大小和集合差不多个数sorted(item)[:0]
- mutidict
- 哈希表
- 排序算法
- 路径规划
- 背包问题
- 字符串动态匹配
- 动态规划
- 递归遍历
- 蓄水池算法
- 布隆过滤器
- 稀疏数组 sparsearray
- 一个数组中大部分没有元素，或者同为一个值，可以用稀疏数组来保留该数组
- 处理方法
- 记录数组一共几行几列，有多少个不同的值
- 把具有不同值的行列及值记录在一个小规模的数组中，从而缩小程序的规模
- 队列 queue
- 链表
- deque队列
- 队列的应用场景：银行排队
- 队列是一个有序列表，可以用数组或者链表来实现
- 遵循先入先出的原则。
- 数组模拟队列
- maxSize：队列最大容量
- front：记录前端的下标
- rear：记录后端的下标
- addqueue()