Data structrue and algorithm

def bubbleSort( theSeq ):
	n = len( theSeq )
	for i in range( n - 1 ) :
		for j in range( n –i - 1 ) :
			if theSeq[j] > theSeq[j + 1] :
				tmp = theSeq[j]
        		theSeq[j] = theSeq[j + 1]
        		theSeq[j + 1] = tmp

def selectionSort( theSeq ):
	n = len( theSeq )
	for i in range( n - 1 ): 
		smallNdx = i
		for j in range( i + 1, n ): 
			if theSeq[j] < theSeq[smallNdx] : 
				smallNdx = j 
	if smallNdx != i : 
		tmp = theSeq[i] 
     		theSeq[i] = theSeq[smallNdx]
     		theSeq[smallNdx] = tmp

def insertionSort( theSeq ): 
	n = len( theSeq )
	for i in range( n-1 ) : 
    	value = theSeq[i]
		pos = i
		while pos > 0 and value < theSeq[pos - 1] : 
     		theSeq[pos] = theSeq[pos - 1]
      		pos -= 1
    	theSeq[pos] = value

def pythonMergeSort( theList ): 
	# Check the base case. 
	if len(theList) <= 1 : 
		return theList 
	else :
		# Compute the midpoint. 
       mid = len(theList) // 2
       # Split the list and perform the recursive step.
        leftHalf = pythonMergeSort( theList[ :mid ] )
        rightHalf = pythonMergeSort( theList[ mid: ] )
        #Merge the two ordered sublists.
        newList = mergeOrderedLists( leftHalf, rightHalf ) 
	return newList 

	\# Sorts an array or list using the recursive quick sort algorithm. 
def quickSort( theSeq ):
n = len( theSeq ) recQuickSort( theSeq, 0, n-1 ) 

	\# The recursive implementation using virtual segments. 
def recQuickSort( theSeq, first, last ): 
	if first >= last : # Check the base case. 
		return 
	else : 
      	# Save the pivot value.
     	pivot = theSeq[first]
		# Partition the sequence and obtain the pivot position. 
		pos = partitionSeq( theSeq, first, last ) 
		# Repeat the process on the two subsequences. 
     	recQuickSort( theSeq, first, pos - 1 )
     	recQuickSort( theSeq, pos + 1, last )

from llistqueue import Queue 
from array import Array 
def radixSort( intList, numDigits ):
\#the latter represents the maximum number of digits possible in the largest key value.
	binArray = Array( 10 ) 
	for k in range( 10 ): 
  		binArray[k] = Queue()
	column = 1
		for d in range( numDigits ): 
			for key in intList :
				digit = (key // column) % 10 
				binArray[digit].enqueue( key ) 
			i=0
			for bin in binArray : 
				while not bin.isEmpty() : 
					intList[i] = bin.dequeue() 
					i += 1 
			column *= 10 

def preorderTrav( subtree ): 
	if subtree is not None : 
    	print( subtree.data )
    	preorderTrav( subtree.left )
    	preorderTrav( subtree.right )

def inorderTrav( subtree ): 
	if subtree is not None : 
        inorderTrav( subtree.left )
        print( subtree.data )
        inorderTrav( subtree.right )

def postorderTrav( subtree ): 
	if subtree is not None :
		postorderTrav( subtree.left )
		postorderTrav( subtree.right )
		print( subtree.data )

def breadthFirstTrav( bintree ):
# Create a queue and add the root node to it. 
Queue q
q.enqueue( bintree )
\# Visit each node in the tree. 
while not q.isEmpty() :
	# Remove the next node from the queue and visit it. 
   node = q.dequeue()
   print( node.data )
   # Add the two children to the queue.
   if node.left is not None :
   		q.enqueue( node.left ) 
	if node.right is not None : 
		q.enqueue( node.right ) 

class ExpressionTree :
	def __init__( self, expStr ): 
    	self._expTree = None
    	self._buildTree( expStr )
	def evaluate( self, varMap ):
		return self._evalTree( self._expTree, varMap ) 
	def __str__( self ):
		return self._buildString( self._expTree ) 
\# ... 
\# Storage class for creating the tree nodes. 

class _ExpTreeNode :
	def __init__( self, data ): 
   		self.element = data
    	self.left = None
    	self.right = None

class MaxHeap :
# ... # Add a new value to the heap. 
def add( self, value ):
	assert self._count < self.capacity(), 
		"Cannot add to a full heap."
	# Add the new value to the end of the list. 
	self._elements[ self._count ] = value self._count += 1 
   	# Sift the new value up the tree.
  	self._siftUp( self._count - 1 )
			
def _siftUp( self, ndx ): 
	if ndx > 0 : 
    	parent = ndx // 2
		if self._elements[ndx] > self._elements[parent] : 
			tmp = self._elements[ndx]
			self._elements[ndx] = self._elements[parent] 
			self._elements[parent] = tmp 
			self._siftUp( parent )

class MaxHeap : 
\# ... 
	def extract( self ): 
		assert self._count > 0, 
			"Cannot extract from an empty heap."
		value = self._elements[0]
		self._count -= 1
		self._elements[0] = self._elements[ self._count ] 
		self._siftDown( 0 ) 

1. 图G=(V, E), V代表nodes也叫vertices，E表示Edges
2. Kn：complete graph，所有的edges都相连
3. Cn：circle graph，不一定所有的edges都相连，但首尾相接
4. trees：没有circle的graph