数据结构学习_ python常用数据结构

数据结构种类

从数据存储结构上分以下几类:

集合结构: 元素唯一,没有明确关系
序列结构:元素有明确先后关系
层次结构:数据元素分属于不同的层次

树形结构:只有一个最上层元素,称为根,其他为子,或为叶(树,二叉树,平衡二叉树,红黑树)

由节点和节点之间连接关系构成
一个结构如果不为空,则至少存在一个节点,成为根

遍历二叉树

深度优先遍历
宽度优先遍历

图结构:元素之间有任意复杂关系

复杂数据结构
分为有向图和无向图两种

不涉及元素如何存储,元素之间如何关联,讲究功能方面的特点,功能性数据结构:

栈

连续存储数据结构
先进后出,后进先出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>