数据结构与算法之线性结构

什么是数据结构

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系的组成。

数据结构就是设计数据以何种方式存储在计算机中，列表、字典等都算是数据结构。
程序=数据结构+算法，数据结构属于静态的部分，算法的调用为动态部分

数据结构的分类

根据逻辑结构划分：

线性结构：数据结构中的元素一对一的关系，一前驱，一后继。
树结构：数据结构中元素一对多的关系，一前驱，多后继。
图结构：数据结构中元素存在多对多的关系，多前驱，多后继，我也不会。
- 判断一个图形能不能一笔画完，就判断它的奇数度节点数目是否为0或2.这种能一笔画完的就是欧拉图，奇数度节点为四个，就是两笔画完。

线性结构

列表

列表和数组

python中的列表和其他语言中的数组很相似，区别为：

数组是定长的。
数组的数据类型也必须一致。
对列表或数组来说，它们的下标操作是最快的。

列表解决的变长问题的方式

假设一开始在内存中分配了四个元素存储的空间，那么前四个元素的append操作不会出现问题。
当第五次append操作时，会先在内存中分配一个能够存储八个元素的空间，也就是翻倍。
然后进行复制，把以前的四个元素依次放到相应的位置上。
若再次超出长度，则继续执行上述操作。
也就是使用了动态表的原理

append操作会不会使速度变慢？

根据摊还分析，没有变长时的append和变长时的append均摊，最后的复杂度时O(3).
append越往后，变长时的出现频率就会越小
浪费了一部分空间，最坏情况应该是浪费了长度除二减一的空间。

列表解决多数据类型问题的方式

对于纯整数的数组，它的每一个元素占4个字节，那么就事先计算好内存分配的大小，计算方法为：- 第一个元素的地址+元素个数乘 4
python的列表里存的不是值，而是指向这个值的内存地址。
地址的大小是一样的，32位里地址是4个字节，64位里地址是8个字节。
这种方法的缺点是内存开销翻倍，这也是python被人诟病的地方。

栈

栈的应用--括号匹配问题

给定一个字符串，问其中字符串是否匹配。
括号本身满足栈的性质

匹配失败的情况：

括号不匹配
匹配完毕栈没空
栈空了又进元素

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

队列

队列的数组实现：

简单的pop(0)操作复杂度过高，不采用。
由于数组定长，不能继续添加数据，如果是列表，出队的操作就会出现空位，所以想办法让数组变成一个圆环。
设置两个指针，队首指针front，队尾指针rear。
由于，队列满的时候和队列空的时候rear和front都在一个位置，那么就无法判断了。于是设置成队列满的时候减去一做为队满的标志。
这种队列就叫做环形队列。
- 当队尾指针front=最大长度+1时，再前进一个位置就自动到0.
- 实现方式：求余数运算
  - 队首指针前进1：front=(front+1)%maxsize
  - 队尾指针前进1：rear=(rear+1)%maxsize
  - 队空条件：rear=front
  - 队满条件：(rear+1)%maxsize=front

通过两个栈做一个队列的方法

1号栈进栈模拟进队操作。
2号站出栈，如果2号栈空，把1号站依次出栈并进2号栈，模拟出队操作。
通过摊还分析，时间复杂度还是O(1)。

python关于队列的模块

import queue    #涉及线程安全用queue
from collections import deque   #常用解题的用deque

q = deque()     #是一种双向队列，popleft出队

#模拟linux命令 head和tail,假如是tail 5
deque(open('a.text','r',encooding='utf8'),5)
#建立一个定长的队列，当队列满了之后，就会删除第一行，继续添加

链表

节点定义

class Node(object):
    def __init__(self,item):
        self.item=item
        self.next=None
#eg
a=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.next
del 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 = curNode
del 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']

心情半佛半神仙