python算法

python 数据结构

栈

一端开口，一端封闭的容器，栈只能对其栈顶的数据进行操作

class Stack():

  def __init__(st, size):
    st.stack = []
    st.size = size
    st.top = -1

  def push(st, content):
    if st.Full():
      print "Stack is full."
    else:
      st.stack.append(content)
      st.top += 1
  def pop(st):
    if st.Empty():
      return False
    else:
      st.top -= 1

  def Full(st):
    if st.top == st.size:
      return True
    else:
      return False

  def Empty(st):
    if st.top == -1:
      print "Stack is Empty!"

队列

两端都通的容器， 一端只能删， 一端只能进
数据流向是单向的。

class Queue():
  def __init__(qu, size):
    qu.queue = []
    qu.size = size
    qu.head = 1
    qu.tail = -1

  def Empty(qu):
    if qu.head == qu.tail:
      return True
    else:
      return False
  def Full(qu):
    if qu.tail - qu.head + 1 == size:
      return True
    else:
      return False
  def enQueue(qu, content):
    if qu.Full():
      print "Queue is Full!!"
    else:
      qu.queue.append(content)
      qu.tail += 1
  def outQueue(qu):
    if qu.Empty():
      print "queue is empyt..."
    else:
      qu.head += 1

链表

class Node():
  def __init__(self, data, next=None):
    self.data = data
    self.next = next

def LinkList():
  def __init__(self, node):
    self.head = node
    self.head.next = None
    self.tail = self.head
  def add(self, node):
    self.tail.next = node
    self.tail = self.tail.next
  def view(self):
    node = self.head
    link_str = ' '
    while node is not None:
      if node.next is not None:
        link_str = link_str + str(node.data) + "-->"
      else:
        link_str += str(node.data)
      node = node.next

    print link_str

二叉树

class BtreeNode():
  def __init__(self, lft=None, rgh=None, data=0):
    self.lft = lft
    self.rgh = rgh
    self.data = data

class Btree():
  def __init__(self, base=None):
    self.base = base
  def empty(self):
    if self.base is None:
      return True
    else:
      return False
  def qout(self, node):
    if node is None:
      return
    print node.data
    self.qout(node.lft)
    self.qout(node.rgh)
  def mout(self, node):
    if node is None:
      return
    self.mout(node.lft)
    print node.data
    self.mout(node.rgh)

  def hout(self, node):
    if node is None:
      return
    self.hout(node.lft)
    self.hout(node.rgh)
    print node.data

##bitmap
class Bitmap():
  def __init__(self, max):
    self.size = int((max + 31 -1) / 31)
    self.array = [0 for i in range(self.size)]
  def bit_index(self, num):
    return num % 31
  def set(self, num):
    elem_index = num / 31
    byte_index = self.bit_index(num)
    elem = self.array［elem_index］  
    self.array[elem_index] = elem | (1 << byte_index)

  def test(self, i):
    elem_index = i / 31
    byte_index = self.bit_index(i)
    if self.array[elem_index] & (1 << byte_index):
      return True
    else:
      return False

if __name__ == "__main__":
  MAX = ord('z')
  suffle = [x for x in 'coledraw']
  res = []
  bitmap = Bitmap(MAX)
  for c in suffle:
    bitmap.set(ord(c))
  for i in range(MAX + 1):
    if bitmap.test(i):
      res.append(chr(i))
  print '%s' %suffle
  print 'ordered %s' %res

#图的视线
chart ＝  {'A':["B", "D"], 'C':['E'], 'D':['C', 'E']}

def path(chart, x, y, pathd=[]):
  pathd = pathd + [x]
  if x == y:
    return pathd
  if not chart.has_key(x):
    return None
  for node in chart[x]:
    if node not in pathd:
      new_node = path(chart, node, y, pathd)
      if new_node:
        return new_node

#quicksort

def quicksort(array, i, j):
  if i < j:
    base = find_sorted_index(array, i, j)
    quicksort(array, i, base)
    quicksort(array, base+1, j)

def find_sorted_index(array, i, j):

  base = array[i]
  while i < j:
    while i < j and array[j]>=base:
      j -= 1
    while i < j and array[j] < base:
      array[i] = array[j]
      i += 1
      array[j] = array[i]
  array[i] = base
  return i

#select sorted

# mergesort