1. 介绍

最近在学习数据结构，参照的课程为 Problem solving with algorithms and data structures.

这篇文章总结此课程的1-3章内容，主要有两部分：基本数据结构和Python 数据结构

2. 基本数据结构

线性结构 (linear structures)：区别线性结构的标准为如何在结构中实现添加和删除操作

stack(栈)
queue(队列)
deque(双端)
list(列表)

栈 (stack)

Stack: the addition of new items and the removal of existing items always takes place at the same end.

LIFO: last-in first-out

class Stack:
     def __init__(self):
         self.items = []

     def isEmpty(self):
         return self.items == []

     def push(self, item):
         self.items.append(item)

     def pop(self):
         return self.items.pop()

     def peek(self):
         return self.items[len(self.items)-1]

     def size(self):
         return len(self.items)

应用场景一：Balanced symbols

应用场景二：Converting decimal numbers to binary number

Divided by 2(BASE) algorithm: continually divides the decimal number by 2(BASE) and keeps tracks of the remainder

def baseConverter(decNumber,base):
    digits = "0123456789ABCDEF"

    remstack = Stack()

    while decNumber > 0:
        rem = decNumber % base
        remstack.push(rem)
        decNumber = decNumber // base

    newString = ""
    while not remstack.isEmpty():
        newString = newString + digits[remstack.pop()]

    return newString

应用场景三：Infix, prefix and postfix expression conversion

Prefix all operators preceds the two operands that they works on
Postfix ……..after ………….

infix to prefix or postfix 手工换算很简单：给所有运算添上符号，然后将操作符移动到括号外，移除括号．

def infixToPostfix(infixexpr):
    prec = {}
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1
    opStack = Stack()
    postfixList = []
    tokenList = infixexpr.split()

    for token in tokenList:
        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
            postfixList.append(token)
        elif token == '(':
            opStack.push(token)
        elif token == ')':
            topToken = opStack.pop()
            while topToken != '(':
                postfixList.append(topToken)
                topToken = opStack.pop()
        else:
            while (not opStack.isEmpty()) and \
               (prec[opStack.peek()] >= prec[token]):
                  postfixList.append(opStack.pop())
            opStack.push(token)

    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    return " ".join(postfixList)

队列 (Queue)

Queue: starts at the rear and makes its way toward the front

FIFO:first-in first-out

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

双端队列 (Deque)

deque: hybird of stack and queue

class Deque:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def addFront(self, item):
        self.items.append(item)

    def addRear(self, item):
        self.items.insert(0,item)

    def removeFront(self):
        return self.items.pop()

    def removeRear(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items)

应用场景： Palindrome-Checker(回文)

List(表)

Unordered List: linked list(链表)

Linked list: collection of items where each item holds a relative position with repect to the others.

In the figure below, it appears that these values have been placed randomly. maintain the location of the next item.

Node Class holds at least two pieces of information:

data field of this node;
a reference to the next node

\(注意:\)

A linked list implementation maintains logical order without requiring physical storage requirments
Modification to the head of the linked list is a special case.

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

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext


class UnorderedList:

    def __init__(self):
        self.head = None

    def isEmpty(self):
        return self.head == None

    def add(self,item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()

        return count

Ordered List

与上面主要区别是 add() 和　search()

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

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext


class OrderedList:
    def __init__(self):
        self.head = None

    def search(self,item):
        current = self.head
        found = False
        stop = False
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
            else:
                if current.getData() > item:
                    stop = True
                else:
                    current = current.getNext()

        return found

    def add(self,item):
        current = self.head
        previous = None
        stop = False
        while current != None and not stop:
            if current.getData() > item:
                stop = True
            else:
                previous = current
                current = current.getNext()

        temp = Node(item)
        if previous == None:
            temp.setNext(self.head)
            self.head = temp
        else:
            temp.setNext(current)
            previous.setNext(temp)

    def isEmpty(self):
        return self.head == None

    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()

        return count

3. Python 数据结构

字符串格式化

具体细节参见链接

string	list	tuple
immutable	mutable	immutatble

Data Structure and Python Data Structure