第三章——基本数据结构

作者: IvyFan2017 | 来源:发表于2018-04-12 15:36 被阅读0次

0. 目标

To understand the abstract data types **stack, queue, deque, and list **.
To be able to implement the ADT‘s stack, queue, and deque using Python lists.
To understand the performance of the implementations of basic linear data structures.
To understand prefix, infix, and postfix expression formats.
To use stacks to evaluate postfix expressions.
To use stacks to convert expressions from infix to postfix.
To use queues for basic timing simulations.
To be able to recognize problem properties where stacks, queues, and deques are appropriate data structures.
To be able to implement the abstract data type list as a linked list using the node and reference pattern.
To be able to compare the performance of our linked list implementation with Python’s list
implementation.

1. 课程笔记

1.1 线性数据结构——stack 堆

stack特点1：LIFO last-in-fist-out，最近的在Top，最老的在Base （例如一堆书）。常见例子：浏览过的URL存储在stack的数据结构，点击Back button可以退回到上一个。
stack的实现

stack( ): 空的stack
push (item): 加入一个新数据在stack top，无返回
pop ( ): 移除一个在stack top，返回item
peek( ): 返回top item，但对stack 没有修改
is_empty( ): 返回布尔值
size( ): stack的大小，返回一个整数。

class Stack():  #最右边是top
    def __init__(self):
        self.stack = []
    def is_empty(self):
        if self.stack == []:
            return True
        else:
            False
    def push(self, item):
        self.stack.append(item)
        return self.stack
    def pop(self):
        m =self.stack.pop()
        return m
    def peek(self):
        last_num = len(self.stack) - 1
        return self.stack[last_num]
    def size(self):
        num = len(self.stack)
        return num

from Stack_function import Stack  ##从相同工程下的Stack_function.py取出Stack class的定义
s = Stack()
print(s.is_empty())
print(s.push(4))
print(s.push(5))
print(s.push('dog'))
print(s.pop())
print(s.peek())
print(s.size())

stack应用一：翻转字符串

a20a5b41-53cd-4435-94c5-0030a377c06a.png

    def reverse(self):
        new_list = []
        i = len(self.stack) - 1
        while i >= 0:
            m = self.stack[i]
            new_list.append(m)
            i = i - 1
        return new_list

stack 应用二：检查括号是否成对出现：将符号放入stack中

from Stack_function import Stack

def cheek_balance(list):
    mystack = Stack() # 初始化一个stack的空间
    index = 0
    num = len(list)
    while index < num and index >= 0:
        i = list[index] #从list中取出一个需要判断的符号
        if i == '(': #push进stack
            mystack.push(i)
        if i == ')' and mystack.is_empty():
            return 'sorry, it is not balance'
        if i == ')':
            mystack.pop()

        index = index + 1

    if mystack.is_empty() == True:
        return 'perfect'
    else:
        return 'sorry'

stack 应用三：十进制转化成二进制：将余数放入stack中

from Stack_function import Stack

def dicimal_to_binary(k):
    mystack = Stack()
    new_string = ''
    if k == 1:    #排除0、1的二进制
        return 1
    if k == 0:
        return 0
    else:
        while k != 0:
            remainder = k % 2 # 余数
            mystack.push(remainder)
            k = k // 2  #除数
    while not mystack.is_empty():
        index = str(mystack.pop())
        new_string = new_string + index   #字符串可以通过加号连接
    return new_string

print(dicimal_to_binary(20))

1.2 线性结构——Queue 队列

特点： FIFO
实现queue的数据结构

class Queue():
    def __init__(self):
        self.queue = []
    def enqueue(self, item):
        self.queue.insert(0, item)
    def dequeue(self):
        return self.queue.pop()
    def  is_empty(self):
        if len(self.queue) == 0:
            return True
        else:
            return False
        #return self.queue == []
    def size(self):
        return len(self.queue)
    def print_queue(self):
        return self.queue

queue的应用一：烫手的山芋(hot potato): 约瑟夫环问题

from queue_structure import Queue

def hot_potato(List, num):
    queue = Queue() # 初始化一个排队
    for i in List:
        queue.enqueue(i)
    print(queue.print_queue()) #放入queue，已将考虑了bill在最前面

    while queue.size() > 1: #最后只剩下一个人
        for k in range(num):  # k = 1,2,3,4,5,6,7
            name = queue.dequeue()
            queue.enqueue(name)
        queue.dequeue() #达到7次后删除第一个

    return queue.print_queue()

Namelist = ["Bill","David","Susan","Jane","Kent","Brad"]
print (hot_potato(Namelist, 7))

queue的应用二：打印机任务建模

1.3 线性结构——Dequeue 双端队列

特点：两端都可以插入和输入
实现dequeue

class Dequeue():
    def __init__(self):
        self.dequeue = []

    def add_front(self, item):
        self.dequeue.append(item)

    def add_back(self, item):
        self.dequeue.insert(0, item)

    def delete_front(self):
        return self.dequeue.pop()
    
    def delet_back(self):
        return self.dequeue.pop(0)
    
    def is_empty(self):
        if self.dequeue == []:
            return True
        else:
            return False

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

    def print_dequeue(self):
        print(self.dequeue)

双端队列的应用：回文检测
① 一个数据结构(list)，不可能凭空变成另一种数据结构(dequeue)，只能通过一个一个添加的方法，将数据录入dequeue
②下面的dequeue的数据结构，没有dequeue[0]，因为没有定义

from dequeue_structure import Dequeue

def Palindrome_check(list):
    dequeue = Dequeue()
    n = len(list)
    for i in range(n):
        dequeue.add_back(list[i]) #倒叙输入到dequeue中
    dequeue.print_dequeue()

    while dequeue.size() > 1:
       if dequeue.delete_back() == dequeue.delete_front():
           continue
       else:
           return "False"
    return "True"

1.4 无序队列(节点存储的数字大小是随机的)——链表(liked list)

为什么要使用链表？
list插入的时候耗时太长（需要向后移动）
存储特点：
① 节点：一个具体存放的数值&下一个节点的地址
② head = none，既是代表了每个节点next node
③ 先add的当作old list，将最近添加的node连接到old list
构造链表结构

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

    def get_data(self):
        return self.data

    def get_next(self): #type:Node
        return self.next

    def set_data(self, new_data):
        self.data = new_data

    def set_next_node(self, new_next):
        self.next = new_next

实现链表

class UnorderList:
    def __init__(self):
        self.head = None #!! the end of structure / the entrance point

    def is_empty(self):
        return self.head == None #查看是否有head之后有node连接

    def add(self, item):
        temp = Node(item) #初始化一个节点
        temp.set_next_node(self.head)  #连接上end， 或者old list node
        self.head = temp

    def print_link_list(self):
        current = self.head
        list = []
        while current != None:
            item = current.get_data()
            list.append(item)
            current = current.get_next()
        return list


    def size(self):
        current = self.head
        sum_node = 1
        while current.get_next() != None:
            sum_node = sum_node + 1
            current = current.get_next()
        return sum_node

    def search(self, item):
        current = self.head  # star at the head
        while current.get_next() != None:
            if current.get_data() == item:
                return "Find" , item
            else:
                current = current.get_next()
        return "Not find"

    def remove(self, item):
        current = self.head
        pro_node = None
        found = False
        while not found:
            if current.get_data() == item:
                found = True
            else:
                pro_node = current
                current = current.get_next()

        if pro_node == None: #第一个节点删除
            self.head = current.get_next()
        else: #其他节点或者最后一个节点
            pro_node.set_next_node(current.get_next())

mylist = UnorderList()
print(mylist.is_empty())
mylist.add(31)
mylist.add(30)
mylist.add(29)
print(mylist.size())
print(mylist.remove(30))
print(mylist.print_link_list())

True
3
None
[29, 31]

扩展其他的功能append, insert, index, and pop

## 在最后一个节点后面增加一个节点，记录消耗的时间

def append(self, item):
    #search最后一个点
    current = self.head  #current is <class '__main__.Node'>
    new_node = Node(item)
    while current.get_next() != None:
        current = current.get_next()
    else:
        current.set_next_node(Node)
        return None

import time
mylist = UnorderList()
mylist.add(31)
mylist.add(30)
mylist.add(29)
tic = time.time()
mylist.append(10)
toc = time.time()
print('time is'+ str(1000*(toc-tic))+ 'ms')

---------------------------------------------------------------------------

AttributeError                            Traceback (most recent call last)

<ipython-input-21-29193cbe3960> in <module>()
      5 mylist.add(29)
      6 tic = time.time()
----> 7 mylist.append(10)
      8 toc = time.time()
      9 print('time is'+ str(1000*(toc-tic))+ 'ms')


AttributeError: UnorderList instance has no attribute 'append'

def insert(self, item, position):
    # initialize a node
    new_node = Node(item)
    current = self.head
    print(current.get_data())
    pos = 0
    pro_node = None
    find = False
    while not find:
        if pos != position:
            pro_node = current
            current = current.get_next()
            pos += 1
        if position == 0:  # Can I improve it?
            self.head = new_node
            new_node.set_next_node(current)
            find = True
        else:
            pro_node.set_next_node(new_node)
            new_node.set_next_node(current.get_next())
            find = True

def index(self, num):
    current = self.head
    pos = 0
    Find = False
    while not Find:
        if current.get_data() == num:
            return pos
        else:
            current = current.get_next()
            pos += 1

def pop(self):
    current = self.head
    Find = False
    pro_node = None
    while not Find:
        if current.get_next() != None:
            pro_node = current
            current = current.get_next()
            print(pro_node.get_data())

        else:
            pro_node.set_next_node(None)
            Find = True

有序链表，例如从小到大排列

class OrderList():
    def __init__(self):
        self.head = None
    def add(self, item):
        node = Node(item)
        node.set_next_node(self.head)
        self.head = node
        
    def print_list(self):
        current = self.head
        list = []
        while current != None:
            item = current.get_data()
            list.append(item)
            current = current.get_next()
        return list
    
    def search(self, item):
        current = self.head
        while current != None:
            if current.get_data() == item:
                return 'Find it'
                
            if current.get_data() > item:
                return 'Sorry, you dont find it'
            else:
                print('serch:', current.get_data())
                current = current.get_next()
        return 'Dont find it'
    
    def add_new_node(self, item):
        current = self.head
        pro_node = None
        print(type(pro_node))
        Find = False
        new_node = Node(item)
        pos = 0
        while not Find :

            if current.get_data() >= item:
                if pos == 0:  # 在位置0加入
                    self.head = new_node
                    new_node.set_next_node(current)
                    Find = True
                
                else:  #在中间其他位置加入|
                    pro_node.set_next_node(new_node)
                    new_node.set_next_node(current)
                    Find = True
                
            else:
                pro_node = current
                print ('through:', current.get_data())
                current = current.get_next()
                pos += 1
            
            if current.get_next() == None: #最后一个节点加入
                current.set_next_node(new_node)
                Find = True

order_list = OrderList()
order_list.add(11)
order_list.add(9)
order_list.add(6)
print('1:', order_list.print_list())
# search
print('2:', order_list.search(8))
#add
order_list.add_new_node(12)
print('3:',order_list.print_list())

('1:', [6, 9, 11])
('serch:', 6)
('2:', 'Sorry, you dont find it')
<type 'NoneType'>
('through:', 6)
('through:', 9)
('3:', [6, 9, 11, 12])

第三章——基本数据结构

0. 目标

1. 课程笔记

1.1 线性数据结构——stack 堆

1.2 线性结构——Queue 队列

1.3 线性结构——Dequeue 双端队列

1.4 无序队列(节点存储的数字大小是随机的)——链表(liked list)

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

我爱编程