python 数据结构 1

一、栈

       线性表 ， 后进先出原则的数据结构；存在栈顶和栈底，元素的取出和添加被称为出栈和入栈。（以下代码使用列表形式展现）

push(element): 添加一个新元素到栈顶位置；判断是否栈已经达到最大空间，满了不可以添加。

def push(self, item):
        if self.isFull():
            raise Exception('stack is full')
        self.items.append(item)

pop()：移除栈顶的元素，同时返回被移除的元素；判断是否栈为空。

def pop(self):
        if self.isEmpty():
            raise Exception('stack is empty')

        return self.items.pop()

peek()：返回栈顶的元素，不对栈做任何修改。

def peak(self):
        if self.isEmpty():
            raise Exception('stack is empty')
        return self.items[-1]

isEmpty()：判断是否为空。

def isEmpty(self):
        return len(self.items) == 0

clear()：移除栈里的所有元素。

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

size()：返回栈里的元素个数。这个方法和数组的length属性很类似。

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

 

class stack:
    # 初始化，创建一个空列表 模拟栈
    def __init__(self, size1):
        self.items = []
        self.size1 = size1

    # 判断栈是否为空，True 为空
    def isEmpty(self):
        return len(self.items) == 0

    # 判断栈是否已满，True 为满
    def isFull(self):
        return len(self.items) == self.size1

    # 入栈操作 判断栈是否已满，是的话抛出异常，中断程序运行，否则继续在栈的尾部添加新的元素
    def push(self, item):
        if self.isFull():
            raise Exception('stack is full')
        self.items.append(item)

    # 出栈操作，判断栈是否为空，空的话抛出栈已空的异常，否则在列表末尾移除元素并返回
    def pop(self):
        if self.isEmpty():
            raise Exception('stack is empty')

        return self.items.pop()

    def peak(self):
        if self.isEmpty():
            raise Exception('stack is empty')
        return self.items[-1]

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

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

 二、链表

        相互链接的数据节点表。每个节点由两部分组成：数据和指向下一个节点的指针；存储单元上非连续，而且采用动态内存分配，能够有效的分配和利用内存资源；节点删除和插入简单，不需要内存空间的重组。

1、插入节点

        在该节点的上一个指针的值赋予新节点的指针，上一个节点的指针指向新节点。

node1 = {'data': '数据1', 'next': '数据2'}
node2 = {'data': '数据2', 'next': '数据3'}
node_a = {'data': '新数据', 'next':''}

# 在节点1和2之间插入新的节点
node_a['next'] = node1['next']
node1['next'] = node_a['data']
print(node1)
print(node_a)
print(node2)
"""
{'data': '数据1', 'next': '新数据'}
{'data': '新数据', 'next': '数据2'}
{'data': '数据2', 'next': '数据3'}
"""

2、删除节点

        将该节点指向内容赋值到上一个节点指向（也就是没有节点指向被删除的节点）

node1 = {'data': '数据1', 'next': '数据2'}
node2 = {'data': '数据2', 'next': '数据3'}
node3 = {'data': '数据3', 'next': '数据4'}

# 删除节点2
node1['next'] = node2['next']
print(node1)
print(node3)
"""
{'data': '数据1', 'next': '数据3'}
{'data': '数据3', 'next': '数据4'}
"""

 代码的体现：

class Node:
    def __init__(self, data=None):
        if data is not None:
            self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        head = Node()
        self.head = head

        #尾部添加节点

    def append(self, data):
        new_node = Node(data)

        # 判断头节点后是否还有数据节点，没有直接将新节点连接到头节点后边
        if self.head.next is None:
            self.head.next = new_node
            return
        # 如果头节点后面有数据节点，则遍历链表，找到next为None的数据节点（尾部节点），将新节点连接到尾部节点
        node = self.head.next
        while True:
            if node.next is None:
                break
            node = node.next
        # 将尾部节点的next 指针指向新的节点
        node.next = new_node

    def display(self):
        node = self.head.next
        while node is not None:
            print(node.data)
            node = node.next

    def prepend(self, data):
        new_data = Node(data)

        # if self.head.next is None:
        new_data.next = self.head.next
        self.head.next = new_data

    def remove(self, data):
        node = self.head

        while True:
            if node.next.data == data:
                node.next = node.next.next
                break
            node = node.next
            if node.next is None:
                raise Exception('data is not found')