Python数据结构与算法补全系列(一)--基本数据结构

什么是线性数据结构

对于某种数据集合，一旦某个元素被添加进来，它与前后元素的相对位置保持不变，这样的数据集合就被称为线性数据结构。

线性数据结构可以看做有两端。这两段可以被称为”左端””右端”，有时候也被称为”前端””后端”或者”顶端””底端”。

栈

栈有时候也被称为”下推栈”，是一个有序集合。添加操作和移除操作总发生在顶端。栈是后进先出(LIFO)的集合。

Python 的 list 方法使得列表作为堆栈非常容易：

>>> stack = [3, 4, 5]
>>> stack.append(6) # list.append() 对应栈的 push()方法
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

队列与双端队列

队列是有序集合，添加操作发生在后端，移除操作发生在前端。队列是先进先出(FIFO)的集合。

双端队列则对两端的添加和移除没有任何限制。

Python 列表也可以用作队列，但在列表开头插入或移除元素较慢，因此效率很低。用 collections.deque 可以快速在两端添加或删除元素:

>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry")           # Terry arrives
>>> queue.append("Graham")          # Graham arrives
>>> queue
deque(['Eric', 'John', 'Michael', 'Terry', 'Graham'])
>>> queue.popleft()                 # The first to arrive now leaves
'Eric'
>>> queue.popleft()                 # The second to arrive now leaves
'John'
>>> queue                           # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])

列表

这里所指的列表区别于 Python 的 list ，是计算机科学中的一种抽象数据类型。列表是有限的有序值得集合，每个值可以出现多次。
用 Python 来构建列表中的元素: Node 类：

class Node:
    def __init__(self, initdata):
        self.data = initdata
        self.next = None
    
    def get_data(self):
        return self.data
    
    def get_next(self):
        return self.next
    
    def set_data(self, newdata):
        self.data = new_data
    
    def set_next(self, newnext):
        self.next = newnext
        
    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.get_data() == item:
                found = True
            else:
                previous = current
                current = current.get_next()
        
        if previous == None:
            self.head = current.get_next()
        else:
            previous.set_next(current.get_next())

无序列表

无序列表中的每个元素都有相对于其他元素的位置。
用 Python 实现无序列表：

class UnorderedList:
    def __init__(self):
        self.head = None
        
    def is_empty(self):
        return self.head == None
    
    def add(self, item):
        temp = Node(item)
        temp.set_next(self.head)
        self.head = temp
    
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.get_next()
        return count
    
    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
            if current.get_data() == item:
                fount = True
            else:
                current = current.get_next()
        
        return found

有序列表

有序列表中元素的相对位置取决于他们的基本特征，通常以升序或者降序排列，并且元素间能进行有意义的比较。
用 Python 实现有序列表：

class OrderedList:
    def __init__(self):
        self.head = None
    
    def is_empty(self):
        return self.head == None
    
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.get_next()
        return count
    
    def search(self, item):
        current = self.head
        found = False
        stop = False
        while current != None and not found and not stop:
            if current.get_data() == item:
                found = True
            else:
                if current.get_data() > item:
                    stop = True
                else:
                    current = current.get_next()
            
        return found
    
    def add(self, item):
        current = self.head
        pervious = None
        stop = False
        while current != None and not stop:
            if current.get_data() > item:
                stop = True
            else:
                previous = current
                current = current.get_next()
        
        temp = Node(item)
        if previous == None:
            temp.set_next(self.head)
            self.head = temp
        else:
            temp.set_next(current)
            previous.set_next(temp)