链表+二叉树

作业:

class PrimeObj():
    def __init__(self,num):
        self.num = num
        self.index = 1
    def __iter__(self):
        return self
    def isPrime(self,item):#判断item是否为素数,是返回True否则返回False
        if item == 1:
            return False
        else:
            for i in range(2,item):
                if item % i == 0:
                    return False
            return True

    def __next__(self):
        if self.index > self.num:
            raise StopIteration
        value = self.index
        self.index += 1
        if self.isPrime(value):
            return value

p = PrimeObj(20)
for i in p:
    if i:
        print(i)

链表和列表的区别什么?

列表内存分配是连续
- 可以应用索引的机制
链表内存分配是不连续
- 没有索引机制
列表的弊端:
- 应用场景:需要高频对列表发起元素的添加和删除.
  - 需要将添加元素或者删除元素后续的元素整体向前或者向后进行偏移移动,势必会消耗计算机的算力.
链表的应用场景是什么?
- 高频进行元素的添加和删除

如何实现链表的数据结构(内存空间是不连续)

封装两种不同形式的数据结构

节点Node

作用:存储单个的元素数据

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

n1 = Node(1)

链表Link

链表:有序的组织所有的节点

class Link():
    #构建一个空链表
    def __init__(self):
        self.head = None
link = Link()

完整实现

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

class Link():
    #构建一个空链表
    def __init__(self):
        self.head = None
    #每次都是向链表的头部添加节点(insert(0))
    def addByHead(self,item):
        #创建一个新的节点对象
        node = Node(item)
        node.next = self.head
        self.head = node
        # 遍历链表

    def travel(self):
        # print(self.head.item)
        # print(self.head.next.item)
        # print(self.head.next.next.item)
        # print(self.head.next.next.next.item)
        cur = self.head
        while cur:
            print(cur.item)
            cur = cur.next
    #向链表尾部添加节点
    def append(self,item):
        pass

    #判断链表是否为空
    def isEmpty(self):
        pass
    #返回链表中节点数量
    def size(self):
        pass
    #向任意位置添加节点
    def insertNode(self,item,pos):
        pass
    #删除指定节点
    def removeNode(self,item):
        pass

link = Link() #创建了一个空链表
link.addByHead(1)
link.addByHead(2)
link.addByHead(3)
link.addByHead(4)
link.travel()

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

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

    def addHead(self,item):
        node = Node(item)
        node.next = self.head
        self.head = node
    def travel(self):
        cur = self.head
        while cur:
            print(cur.item)
            cur = cur.next
    def isEmpty(self):
        return self.head == None

    def append(self,item):
        node = Node(item)
        if self.isEmpty(): #链表为空的操作
            self.head = node
            return
        #链表为非空的操作
        cur = self.head
        pre = None #永远指向cur前一个节点

        while cur:
            pre = cur
            cur = cur.next
        #循环结束后,pre一定指向的是链表中最后一个节点
        pre.next = node

    def size(self):
        count = 0
        cur = self.head

        while cur:
            count += 1
            cur = cur.next
        return count

    def insertNode(self,pos,item):
        if pos == 0:
            self.addHead(item)
            return

        node = Node(item)
        pre = None
        cur = self.head

        for i in range(pos):
            pre = cur
            cur = cur.next

        pre.next = node
        node.next = cur

    def removeNode(self,item):
        cur = self.head
        pre = None

        #如果删除的是第一个节点
        if item == self.head.item:
            self.head = self.head.next
            return
        #删除的非第一个节点
        while cur:
            pre = cur
            cur = cur.next

            if cur.item == item:
                pre.next = cur.next
                return

link = Link()
link.addHead(1)
link.addHead(2)
link.addHead(3)
link.append(4)
link.removeNode(40)
link.travel()

链表+二叉树

Python相关栏目本月热门文章