数据结构种类
从数据存储结构上分以下几类:
集合结构: 元素唯一,没有明确关系
序列结构:元素有明确先后关系
层次结构:数据元素分属于不同的层次
-
树形结构:只有一个最上层元素,称为根,其他为子,或为叶(树,二叉树,平衡二叉树,红黑树)
由节点和节点之间连接关系构成 一个结构如果不为空,则至少存在一个节点,成为根遍历二叉树
深度优先遍历 宽度优先遍历
-
图结构:元素之间有任意复杂关系
复杂数据结构 分为有向图和无向图两种
不涉及元素如何存储,元素之间如何关联,讲究功能方面的特点,功能性数据结构:
-
栈
连续存储数据结构 先进后出,后进先出LIFO,python 实现 deque
-
队列
先进先出,后进后出 FIFO,python 实现 queue,deque
-
优先队列
headq库
-
字典
因为只有功能要求,这类数据结构可以采用任何技术实现
-
堆 实现
堆数据结构是一种数组对象，它可以被视为一科完全二叉树结构。它的特点是父节点的值大于（小于）两个子节点的值（分别称为大顶堆和小顶堆）。它常用于管理算法执行过程中的信息，应用场景包括堆排序，优先队列等。
python 里面数据类型:
在Python中, Queue的主要任务是用于线程之间的通信, 而不是作为一种数据结构.
如果你需要链表, 那就使用deque, 他的底层实现是链表,既可以作为栈使用,也可以作为队列使用
# coding=utf-8
from multiprocessing import Queue, Process
from Queue import Empty as QueueEmpty
import random
def getter(name, queue):
print 'Son process %s' % name
while True:
try:
value = queue.get(True, 10)
# block为True,就是如果队列中无数据了。
# |—————— 若timeout默认是None，那么会一直等待下去。
# |—————— 若timeout设置了时间，那么会等待timeout秒后才会抛出Queue.Empty异常
# block 为False，如果队列中无数据，就抛出Queue.Empty异常
print "Process getter get: %f" % value
except QueueEmpty:
break
def putter(name, queue):
print "Son process %s" % name
for i in range(0, 1000):
value = random.random()
queue.put(value)
# 放入数据 put(obj[, block[, timeout]])
# 若block为True，如队列是满的：
# |—————— 若timeout是默认None，那么就会一直等下去
# |—————— 若timeout设置了等待时间，那么会等待timeout秒后，如果还是满的，那么就抛出Queue.Full.
# 若block是False，如果队列满了，直接抛出Queue.Full
print "Process putter put: %f" % value
if __name__ == '__main__':
queue = Queue()
getter_process = Process(target=getter, args=("Getter", queue))
putter_process = Process(target=putter, args=("Putter", queue))
getter_process.start()
putter_process.start()
数组和链表:
数组 : 各元素内存存储在一块
链表: 各元素分开存,并存储指向下一个元素地址
索引操作: 数组 O(1) 链表 O(n)
插入和删除操作: 数组 O(n) 链表O(1)
线性表数据结构,python 数据类型
-
list 列表(线性表数据结构—数组) 实现
动态指针数组 元素个数可变的线性表 顺序存储 访问时间短(缺点) 删除和增加操作移动代价大,不够灵活,不易调整和变化(缺点) -
链表,双向链表python 实现
用链接关系显示表示元素之间的顺序关联,基于链接技术实现的线性表 实现: 把表数据元素分别存储在独立的存储块里 保证从任一节点可以找到下一个节点 在前一个节点显示记录与下一个节点关联信息
tuple 元组(线性表数据结构)
dict 字典(采用散列表技术)
collections.deque 单向队列,双端队列
支持元素两端插入和删除,采用双链表技术实现
同时也涵盖队列的功能,也可以将其作为队列使用
-
array模块,[array数组模块]
array模块所提供的array对象则是保存相同类型的数值的动态数组 array元素的类型是在创建并使用的时候确定的。 如果你的程序需要优化内存的使用，并且你确定你希望在list中存储的数据都是同样类型的，那么使用array模块很合适。举个例子，如果需要存储一千万个整数，如果用list，那么你至少需要160MB的存储空间，然而如果使用array，你只需要40MB。但虽然说能够节省空间，array上几乎没有什么基本操作能够比在list上更快。 -
headq模块
heapq模块使用一个用堆实现的优先级队列。堆是一种简单的有序列表，并且置入了堆的相关规则。 堆是一种树形的数据结构，树上的子节点与父节点之间存在顺序关系。二叉堆(binary heap)能够用一个经过组织的列表或数组结构来标识，在这种结构中，元素N的子节点的序号为2*N+1和2*N+2(下标始于0)。简单来说，这个模块中的所有函数都假设序列是有序的，所以序列中的第一个元素(seq[0])是最小的，序列的其他部分构成一个二叉树，并且seq[i]节点的子节点分别为seq[2*i+1]以及seq[2*i+2]。当对序列进行修改时，相关函数总是确保子节点大于等于父节点。import heapq (实现优先级队列) class Item: def __init__(self, name): self.name = name def __repr__(self): return 'Item({!r})'.format(self.name) class PriorityQueue: def __init__(self): self._queue = [] self._index = 0 def push(self, item, priority): heapq.heappush(self._queue, (-priority, self._index, item)) self._index += 1 def pop(self): return heapq.heappop(self._queue)[-1] q = PriorityQueue() q.push(Item('foo'), 1) q.push(Item('bar'), 5) q.push(Item('spam'), 4) q.push(Item('grok'), 1) print q.pop() # Item('bar') print q.pop() # Item('spam') print q.pop() # Item('foo') print q.pop() # Item('grok') -
bisect 高级数据结构
bisect模块能够提供保持list元素序列的支持。它使用了二分法完成大部分的工作。 它在向一个list插入元素的同时维持list是有序的。 在某些情况下，这比重复的对一个list进行排序更为高效，并且对于一个较大的list来说，对每步操作维持其有序也比对其排序要高效。 import bisect a = [(0, 100), (150, 220), (500, 1000)] bisect.insort_right(a, (250,400)) print a # [(0, 100), (150, 220), (250, 400), (500, 1000)]
</article>
