Python数据结构的实现

1 . 链表 python中，使用类的嵌套实现链表。 节点和链表都用类来表示。节点有两个变量data和next，data存储数据，next为下一个节点。链表有一个变量head，将node赋给head。

#!/usr/bin/python # coding: utf-8 class Node(object): def __init__(self,value,pointer=0): self.data = value self.next = pointer class LinkList(object): def __init__(self): self.head = 0 def initlist(self, data): self.head = Node(data[0]) temp = self.head for i in data[1:]: node = Node(i) temp.next = node temp = temp.next def length(self): p = self.head length = 0 while p != 0: length += 1 p = p.next return length def empty(self): if self.length() == 0: return True else: return False def clear(self): self.head = 0 def append(self, item): #append item in the end of LinkList new_node = Node(item) if self.head == 0: self.head = new_node else: temp = self.head while temp.next != 0: temp = temp.next temp.next = new_node def getitem(self, index): # index is the No.number of the Linked_list if self.empty(): print 'LinkList is empty.' return None elif index < 0 or index >= self.length(): print 'The index is out of the LinkList.' return None counter = 0 temp = self.head while temp.next != 0 and counter<index: temp = temp.next counter += 1 if counter == index: return temp.data else: print 'target is not exist!' def insert(self, index, item): # insert item in the middle of the LinkList if self.empty(): print 'LinkList is empty.' return None elif index > self.length(): print 'The index is out of the LinkList.' return None if index == 0: self.head = Node(item, self.head) return None temp = self.head for i in range(index-1): temp = temp.next if temp.next == 0: temp.next = Node(item) else: old_item = temp.next temp.next = Node(item) temp.next.next = old_item return None def delete(self, index): if self.empty() or index < 0 or index >= self.length(): print 'Index is out of the range' return None if index == 0: self.head = self.head.next temp = self.head for i in range(index-1): temp = temp.next if temp.next.next == 0: temp.next =0 else: temp.next = temp.next.next def index(self, value): if self.empty(): print 'LinkList is empty.' return None temp = self.head counter = 0 while temp.next != 0: if temp.data == value: return counter counter += 1 temp = temp.next return 'No value!'

单向循环链表 双向链表

2 . 栈

#!/usr/bin/env python # coding: utf-8 class Stack(object): def __init(self): self.stack = [] def push(self, item): self.stack.append(item) def pop(self): if self.stack != []: self.stack.pop() else: return None def head(self): if self.stack != []: return self.stack[0] else: return None def tail(self): if self.stack != []: return self.stack[-1] else: return None def length(self): return len(self.stack) def empty(self): return self.stack == []

3 . 队列

python对队列有现成的库Queue。

>import Queue >q = Queue.Queue() >q.put(1) >q.put(2) >q.empty() False >q.get() 1 >q.get() 2

注意，在队列空的时候调用get()，解释器就会崩溃（win python2.7），暂时没有解决办法。

用列表写的队列如下：

#!/usr/bin/env python # coding: utf-8 class Queue(object): def __init__(self): self.queue = [] def enqueue(self, item): self.queue.append(item) def dequeue(self): if self.queue != []: return self.queue.pop(0) else: return None def head(self): if self.queue != []: return self.queue[0] else: return None def tail(self): if self.queue != []: return self.queue[-1] else: return None def length(self): return len(self.queue) def empty(self): return self.queue == []