Data structure

Abstract Data Type (ADT)

在自然界或者计算机语言中，每个物体都可以称之为对象，而每个对象都有属性和功能，我们将一个物体所特有的属性和功能分离开来就是抽象的过程。在计算机科学中，具有类似的属性和功能的数据结构就叫抽象数据类型(ADT)。这篇文章中的数据结构我们同意用Python语言来构建，在Python中我们可以随意创造不同的ADT，我们称之为类(Class)。

每个类都有自己的属性和功能(Operations)，Operations主要可以分为四类：

Constructors：创造和初始化这个类的一个对象 
Accessors：在输入信息中抽出数据，不改变信息本身
Mutators：处理数据
Iterators：迭代器，对输入数据进行迭代的计算

Data types

Bag(背包)：

储存可以重复的元素，无序，可以赋予这个类(ADT)以下一些属性和函数：

length()
contains(item)
add(item)
remove(item)
iterator()           **注意**：其实如果只需要这些功能的话，c语言中的数组这种简单的结构就足以胜任，面向对象语言如Python中的基本数据类型是包含c语言里面的那些基本数据结构的，一般情况下当程序比较小的时候，创建多个list没有关系，但当程序变得非常大的时候，创建过多的list是不合适的，因为list不仅包含数组的属性和功能外，还包含很多其它的功能，你可能并不需要它们，但同样会被创建，而浪费大量的内存。所以c语言往往比面向对象的语言要快。

Array(数组):

一维Array：

一种最基本的数据结构，可以直接在硬件层面上被执行，数组只有三个operations：创建数组(array creation); 根据下标(subscripts)读数据；写数据，并且array的大小是确定的并且不可改变的。Python中的list拥有很多的operations，往往也会浪费很多空间。Python当中有ctypes模块，可以用c语言编程。 ####二维Array：无法在硬件层面上执行，但是可以利用一维Array来创建，同样一旦创建了，大小不能更改。

矩阵(Matrix):

用二维Array来创建，除了array的一些基本operations外，还可以添加一些矩阵特有的功能函数，比如: scaling(矩阵乘以一个实数); 乘法运算，加法运算。
用list创建：对于非常稀疏的矩阵，用二维Array会浪费很多的空间，这时可以用list来构建ADT，比如矩阵中第3行第5列的值为19，那么只需要将(5, 19）存储在list的第2个元素上。

集合(Sets):

和Bag有一点不同，集合里的元素是不能重复的，并且可以在ADT中加入很多集合运算函数，如交集、并集、补集等等。集合可以用list创建

映射(Maps):

在python中就是dictionary，但也可以用list来创建新的映射ADT：

用两个list：一个list储存Keys，另一个list储存Values
用一个list：直接将（Key, Value）存入list中

哈希表(Hash table)：

将Array中的元素通过某种哈希函数转换后按照规则存放到另一个映射Array(Map)中存储，需要检索某个item时，按照同样的方法就可以在新的array中快速找到，比如：

	Array: 165, 431, 96, 142, 579, 226, 903, 388
	Hash函数：h(key) = key % M, 映射Array的大小是13
	Map：11， 2， 5， 12， 7
	分别将Map后的元素放入Map array中存储

无序关联列表(Unsorted Linked List):

由多个节点(nodes)组成，每个节点除了有自身的值外，还有一个指针(next)指向下一个节点

遍历traverse linked list：

def traversal (head):
	curNote = head
	while curNode is not true
		print(curNode.data)
		curNode = curNode.next

检索search linked list:

	def unorderedSearch(head, target):
		curNode = head
		while curNode is not None and curNode.data != target:
			curNode = curNode.next
		return curNode is not None

添加prepend linked list:

```
newNode = ListNode(newItem)
newNode.next = head
head = newNode
```

删除remove nodes from linked list:

```
preNode = None
curNode = head
while curNode is not None and curNode.data != target:
	preNode = curNode
	curNode = curNode.next
if cur Node is not Node:
	if curNode is head:
		head = curNode.next
	else:
		preNode.next = curNode.next
```

堆栈Stack：

后进先出，两个主要的operations是pop()和push()

用list实现(最简单)：用list的尾代表stack的头部

		class Stack :
			def __init__( self ): 
				self._theItems = list() 
			def isEmpty( self ): 
				return len( self ) == 0 
			def __len__ ( self ): 
				return len( self._theItems ) 
			def peek( self ):
				assert not self.isEmpty(), "Cannot peek at an empty stack" 
				return self._theItems[-1] 
			def pop( self ):
				assert not self.isEmpty(), "Cannot pop from an empty stack" 
				return self._theItems.pop() 
			def push( self, item ): 
				self._theItems.append( item ) 

用linked list实现(最有效): 用linked list的head代表stack的头部

		class Stack :
			def __init__( self ): 
    				self._top = None
    				self._size = 0
			def isEmpty( self ): 
				return self._top is None 
			def __len__( self ): 
				return self._size 
			def peek( self ):
				assert not self.isEmpty(), "Cannot peek at an empty stack" 
				return self._top.item 
			def pop( self ):
				assert not self.isEmpty(), "Cannot pop from an empty stack" 
				node = self._top
				self.top = self._top.next
				self._size -= 1
				return node.item 
			def push( self, item ) :
				self._top = _StackNode( item, self._top ) 
				self._size += 1 

		\# ... 
		\# The private storage class for creating stack nodes.
		class _StackNode :
			def __init__( self, item, link ) : 
    			self.item = item
    			self.next = link

队列Queue：

先进先出，两个主要的operations是enqueue(item)和dequeue()

用list实现(最简单)：

			class Queue :
				def __init__( self ): 
					self._qList = list() 
				def isEmpty( self ): 
					return len( self ) == 0 
				def __len__( self ): 
					return len( self._qList ) 
				def enqueue( self, item ): 
    				self._qList.append( item )
				def dequeue( self ):
					assert not self.isEmpty(), "Cannot dequeue from an empty queue." 
					return self._qList.pop( 0 ) 

用linked list：

			class Queue :
				def __init__( self ): 
    				self._qhead = None
    				self._qtail = None
    				self._count = 0
				def isEmpty( self ):
					return self._qhead is None 
				def __len__( self ): 
					return self._count 
			# ... 
			# Private storage class for creating the linked list nodes.
			class _QueueNode:
				def __init__( self, item ): 
    				self.item = item
    				self.next = None

			class Queue : # ... 
				def enqueue( self, item ): 
					node = _QueueNode( item ) 
					if self.isEmpty() : 
						self._qhead = node 
					else : 
      						self._qtail.next = node
    						self._qtail = node
    						self._count += 1
				
				def dequeue( self ):
					assert not self.isEmpty(), "Cannot dequeue from an empty queue." 
					node = self._qhead
					if self._qhead is self._qtail : 
    					self._qtail = None
						self._qhead = self._qhead.next 
						self._count -= 1
						return node.item 

Priority Queue（Unbounded):

用list实现

		class PriorityQueue : 
			def __init__( self ): 
				self._qList = list() 
			def isEmpty( self ): 
				return len( self ) == 0 
			def __len__( self ): 
				return len( self._qList ) # ... 
		class PriorityQueue : # ... 
			def enqueue( self, item, priority ):
				entry = _PriorityQEntry( item, priority )
				self._qList.append( entry ) 
			def dequeue( self ) :
				assert not self.isEmpty(), "Cannot dequeue from an empty queue." 
				   # Find the entry with the highest priority.
				
				highest = self._qList[0].priority 
				for i in range( self.len() ) : 
					if self._qList[i].priority < highest : 
						highest = self._qList[i].priority
						# Remove the entry with the highest priority and return the item.
						entry = self._qList.pop( highest ) 
						return entry.item 

高级linked list

Doubly linked list
Circular linked list
Multi-linked list

Basic data structrue