什么是数据结构
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系的组成。
数据结构就是设计数据以何种方式存储在计算机中，列表、字典等都算是数据结构。
程序=数据结构+算法，数据结构属于静态的部分，算法的调用为动态部分
数据结构的分类
根据逻辑结构划分：
线性结构：数据结构中的元素一对一的关系，一前驱，一后继。
树结构：数据结构中元素一对多的关系，一前驱，多后继。
图结构：数据结构中元素存在多对多的关系，多前驱，多后继，我也不会。
判断一个图形能不能一笔画完，就判断它的奇数度节点数目是否为0或2.这种能一笔画完的就是欧拉图，奇数度节点为四个，就是两笔画完。
线性结构
列表
列表和数组
python中的列表和其他语言中的数组很相似，区别为：
数组是定长的。
数组的数据类型也必须一致。
对列表或数组来说，它们的下标操作是最快的。
列表解决的变长问题的方式
假设一开始在内存中分配了四个元素存储的空间，那么前四个元素的append操作不会出现问题。
当第五次append操作时，会先在内存中分配一个能够存储八个元素的空间，也就是翻倍。
然后进行复制，把以前的四个元素依次放到相应的位置上。
若再次超出长度，则继续执行上述操作。
也就是使用了动态表的原理
append操作会不会使速度变慢？
根据摊还分析，没有变长时的append和变长时的append均摊，最后的复杂度时O(3).
append越往后，变长时的出现频率就会越小
浪费了一部分空间，最坏情况应该是浪费了长度除二减一的空间。
列表解决多数据类型问题的方式
对于纯整数的数组，它的每一个元素占4个字节，那么就事先计算好内存分配的大小，计算方法为：- 第一个元素的地址+元素个数 乘 4
python的列表里存的不是值，而是指向这个值的内存地址。
地址的大小是一样的，32位里地址是4个字节，64位里地址是8个字节。
这种方法的缺点是内存开销翻倍，这也是python被人诟病的地方。
栈
相关知识点
总是能听到一个词 堆栈 ，堆(heap)和栈(stack)是两个东西，传统的编程语言中把内存分为两个地方，堆空间和栈空间，堆存储的是一些动态生成的对象，与数据结构中的堆是不同的，栈空间由系统调用，存放函数的参数值，局部变量的值。
应该是早年间翻译的问题，一般听到堆栈指的就是栈。
栈是一个数据集合，可以理解为只能在一端进行插入和删除操作的列表。
栈的特点：后进先出(last-in,first-out)
栈顶：操作永远在栈顶。
栈底：最后一个元素。
栈的基本操作：
进栈(压栈)：push
出栈：pop
取栈顶： gettop
关于出栈顺序的问题：
对于某个元素，如果进展顺序在它前面的元素出栈时在它后面，那么前面的元素顺序是相反的。
不知道说的明不明白
卡特兰数，n个数的出栈顺序，就是卡特兰数的第n项。
栈的应用--括号匹配问题
给定一个字符串，问其中字符串是否匹配。
括号本身满足栈的性质
匹配失败的情况：
def brace_match(s): stack = [] d ={'(':')','[':']','{':'}'} for ch in s: if ch in {'(','[','{'}: stack.append(ch) elif len(stack): print('多了%s' %ch) return False elif d[stack[-1]] == ch: stack.pop() else: print('%s不匹配'%ch) if len(stack)==0: return True else: print("未匹配") return False括号不匹配
匹配完毕栈没空
栈空了又进元素
队列
相关知识点：
队列是一个数据集合，仅允许在列表的一端插入，另一端删除。
进行插入的时队尾，进行删除操作的是队首，插入和删除操作也被称为进队(push)和出队(pop)。
队列的性质：先进先出(first-in,first-out)
双向队列：两边都能进行插入删除操作的队列。
队列的数组实现：
简单的pop(0)操作复杂度过高，不采用。
由于数组定长，不能继续添加数据，如果是列表，出队的操作就会出现空位，所以想办法让数组变成一个圆环。
设置两个指针，队首指针front，队尾指针rear。
由于，队列满的时候和队列空的时候rear和front都在一个位置，那么就无法判断了。于是设置成队列满的时候减去一做为队满的标志。
这种队列就叫做环形队列。
队首指针前进1：front=(front+1)%maxsize
队尾指针前进1：rear=(rear+1)%maxsize
队空条件：rear=front
队满条件：(rear+1)%maxsize=front
当队尾指针front=最大长度+1时，再前进一个位置就自动到0.
实现方式：求余数运算
通过两个栈做一个队列的方法
1号栈进栈 模拟进队操作。
2号站出栈，如果2号栈空，把1号站依次出栈并进2号栈，模拟出队操作。
通过摊还分析，时间复杂度还是O(1)。
python关于队列的模块
import queue #涉及线程安全用queuefrom collections import deque #常用解题的用dequeq = deque() #是一种双向队列，popleft出队#模拟linux命令 head和tail,假如是tail 5deque(open('a.text','r',encooding='utf8'),5)#建立一个定长的队列，当队列满了之后，就会删除第一行，继续添加链表
相关知识点：
链表就是非顺序表，与队列和栈对应。
链表中每一个元素都是一个对象，每个对象称为一个节点，包含有数据域key和指向下一个节点的next，通过各个节点之间的相互连接，最终串联成一个链表。
在机械硬盘中，文件就是以链表的形式存储的。
以FAT32为例，文件的单位是文件块(block)，一个文件块的大小是4k，一个文件的内容是由链表的方式连接文件块组成的。
链表的第一个节点被称为头节点，数据可以是空的，也可以有值。
头节点为空也是为了表示空链表，也叫做带空节点的链表，头节点也可以记录链表的长度
节点定义
class Node(object): def __init__(self,item): self.item=item self.next=None#ega=Node(1) b=Node(2) c=Node(3) a.next=b b.next=c #链表的最后一个节点的next就为None
链表类的实现
class LinkList:
def __init___(self,li,method='tail'):
self.head = None
self.tail = None
if method == 'head':
self.create_linklist_head(li) if method == 'tail'
self.create_linklist_tail(li) else:
rais ValueError('unsupport')
#头插法
def create_linklist_head(self,li):
self.head = Node(0) for v in li:
n = Node(v)
n.next = l.next #当插入下一个元素时，应该与下一个节点连接后再跟头节点连接
self.head.next = n
self.head.data += 1
#尾插法
def create_linlist_tail(self,li):
self.head = Node(0)
self.tail = self.head for v in li:
p = Node(v)
self.tail.next = p
self.tail = p
self.head.data += 1
#链表的遍历输出
def traverse_linlist(self):
p = self.head.next while p: yield p.data
p = p.next插入删除总结
插入
#p表示待插入节点，curNode表示当前节点p.next = curNode.next #不能当前连接直接断开curNode,next = p
删除
p = curNode.next curNode.next = p.nextdel p #不写也一样，引用计数，python的内存回收机制
双链表
双链表中每个节点有两个指针：一个指向后面节点、一个指向前面节点。
节点定义：
class Node(object): def __init__(self, item=None): self.item = item self.next = None self.prior = None
双链表的插入和删除
插入
p.next = curNode.next curNode.next.prior = p p.prior = curNode curNode.next = p
删除
p = curNode.next curNode.next = p.next p.next.prior = curNodedel p
链表的复杂度分析
链表与列表相比
按元素值查找：列表可以使用二分法是O(logn)，链表是O(n)
按下标查找：O(1),O(n)
再某元素后插入：O(n),O(1)
删除莫元素：O(n),O(1)
总的来说链表再插入和删除某元素的操作时明显快于顺序表，而且通过双链表可以更容易实现栈和队列。
哈希表
直接寻址表
哈希表就是直接寻址表的改进。当关键字的全域U比较小时，直接寻址是一种简单有效的方法。
全域的意思就是它的取值范围。
也就是直接把关键字为key的value放在key的位置上
直接寻址的缺点：当域U很大时，需要消耗大量内存。
如果U很大，但关键字很少，浪费大量空间。
若关键字不是数字则无法处理。
直接寻址表的改进：构建大小为m的寻址表T
key为k的元素放到h(k)上
h(k)是一个函数，其将域U映射到表T(0,1,..,m-1)
哈希表
哈希表是一个通过哈希函数计算数据存储位置的线性表的存储结构，又叫做散列表。
哈希表由一个直接寻址表和一个哈希函数组成。
哈希函数h(k)将元素关键字k作为自变量，返回元素的存储下标。
哈希表的基本操作：
insert(key,value):插入键值对。
get(key):如果存在键为key的键值对则返回其value。
delete(key)：删除键为key的键值对。
简单哈希函数
除法哈希：
h(k)= k mod m乘法哈希：
h(k) = floor(m(KA mod 1)) 0<A<1
哈希冲突
由于哈希表的大小是有限的，而要存储信息的数量是无限的，因此，对于任何哈希函数，都会出现两个元素映射到同一个位置的情况，这种情况就叫做哈希冲突。
解决哈希冲突的方法：
开放寻址法：如果哈希函数返回的位置已经有值，则可以向后探查新的位置来储存这个值。
线性探查：如果位置p被占用，则探查
p+1,p+2....。二次探查：如果位置p被占用，则探查
p+1**2,p-1**2,p+2**2。二度哈希：有n个哈希函数，当使用第一个哈希函数h1发生冲突时，则使用h2。
哈希表的快速查找可以以空间换时间，需要保证元素个数除以数组容积小于0.5，这个比值就是装载率。
拉链法：哈希表的每个位置都连接一个链表，当冲突发生时，冲突的元素被加到该位置链表的最后。拉链表需要保证每一个链表的长度都不要太长。
拉链法的装载率是可以大于一的。
插入、查找等操作的时间复杂度是O(1)的。
哈希在python中的应用
字典和集合都是通过哈希表来实现的
集合可以看作没有value的字典，因为集合也有不重复的性质。
通过哈希函数把字典的键映射为函数：
dic = {'name':'cui'}#可以认为是h('name')=1，则哈希表为[None,'cui']作者：崔园樟