Python实现数据结构

今天药忘吃喽~ 2023-10-10 20:22 19阅读 0赞

#### 文章目录 ####

*  一、Python实现数据结构
 *   *  1.1 python实现单向链表
     *  1.2 python实现单向循环链表
     *  1.3 python实现双向链表

## 一、Python实现数据结构 ##

### 1.1 python实现单向链表 ###

*singleLinkedList.py*

class SingleNode:
        """the node of single link list"""
        def __init__(self, item):
            self.item = item
            self.next = None
        def __str__(self):
            return str(self.item)
    
    class SingleLinkList:
        """sing link list"""
        def __init__(self):
            self._head = None
    
        def is_empty(self):
            """判断链表是否为空"""
            return self._head is None
        
        def length(self):
            """获取链表长度"""
            cur = self._head
            count = 0
            while cur is not None:
                count += 1
                cur = cur.next
            return count
        
        def travel(self):
            """遍历链表"""
            cur = self._head
            while cur is not None:
                print(cur.item)
                cur = cur.next
            print()
        
        def add(self, item):
            """链表头部添加元素"""
            node = SingleNode(item)
            node.next = self._head
            self._head = node
    
        def append(self, item):
            """链表尾部添加元素"""
            node = SingleNode(item)
            if self.is_empty():
                self._head = node
            else:
                cur = self._head
                while cur.next is not None:
                    cur = cur.next
    
                """此时cur指向最后一个节点，next=None"""
                cur.next = node
            
        def insert(self, pos, item):
            """指定位置添加元素"""
            # 若pos小于0，则执行头部插入
            if pos <= 0:
                self.add(item)
            
            # 若pos大鱼链表长度，则执行尾部插入
            elif pos > self.length() - 1:
                self.append(item)
            
            else:
                node = SingleNode(item)
                cur = self._head
                cur_pos = 0
                while cur.next is not None:
                    """获取插入位置的上一个节点"""
                    if pos - 1 == cur_pos:
                        node.next = cur.next
                        cur.next = node
                        break
                    cur = cur.next
                    cur_pos += 1
        
        def remove(self, item):
            """删除节点"""
            if self.is_empty():
                return
            cur = self._head
            if cur.item == item:
                self._head = cur.next
            else:
                while cur.next is not None:
                        if cur.next.item == item:
                            cur.next = cur.next.next
                            break
                        cur = cur.next
        
        def search(self, item):
            """查找节点位置"""
            cur = self._head
            count = 0
            while cur is not None:
                if cur.item == item:
                    return count
                cur = cur.next
                count += 1
            return -1
        
    # if __name__ == "__main__":
    #     ll = SingleLinkList()
    #     ll.add(1)
    #     ll.add(2)
    #     ll.append(3)
    #     ll.insert(2,4)
    #     print("length: ", ll.length())
    #     ll.travel()
    #     print("search(3): ", ll.search(3))
    #     print("search(5): ", ll.search(5))
    #     ll.remove(1)
    #     print("length: ", ll.length())
    #     ll.travel()

### 1.2 python实现单向循环链表 ###

*sinCycLinkedList.py*

class Node:
        def __init__(self, item):
            self.item = item
            self.next = None
        def __str__(self):
            return str(self.item)
        
    class SinCycLinkedList:
        """单向循环链表"""
        def __init__(self):
            self._head = None
        
        def is_empty(self):
            """判断链表受否为空"""
            return self._head is None
        
        def length(self):
            """返回链表长度"""
            if self.is_empty():
                return 0
            cur = self._head
            count = 1
            while cur.next != self._head:
                count += 1
                cur = cur.next
            return count
        
        def travel(self):
            """遍历链表"""
            if self.is_empty():
                return
            cur = self._head
            print(cur.item)
            while cur.next != self._head:
                cur = cur.next
                print(cur.item)
            print()
        
        def add(self, item):
            """链表头部添加节点"""
            node = Node(item)
            if self.is_empty():
                self._head = node
                node.next = node
            else:
                cur = self._head
                node.next = self._head
                while cur.next != self._head:
                    cur = cur.next
                cur.next = node
                self._head = node
        
        def append(self, item):
            """链表尾部添加节点"""
            node = Node(item)
            if self.is_empty():
                self._head = node
                node.next = self._head
            else:
                cur = self._head
                while cur.next != self._head:
                    cur = cur.next
                cur.next = node
                node.next = self._head
    
        def insert(self, pos, item):
            """链表指定位置插入节点"""
            if pos <= 0:
                self.add(item)
            elif pos > self.length() - 1:
                self.append(item)
            else:
                cur = self._head
                cur_pos = 0
                node = Node(item)
                while cur.next != self._head:
                    if cur_pos == pos - 1:
                        node.next = cur.next
                        cur.next = node
                        break
                    cur = cur.next
                    cur_pos += 1
                
        def remove(self, item):
            """删除链表指定节点"""
            if self.is_empty():
                return
            pre = self._head
            if pre.item == item:
                cur = pre
                while cur.next != pre:
                    cur = cur.next
                cur.next = pre.next
                self._head = pre.next
            else:
                cur = pre
                while cur.next != pre:
                    if cur.next.item == item:
                        cur.next = cur.next.next
                        # break
                    cur = cur.next
        
        def search(self, item):
            """查找节点，返回下标"""
            cur = self._head
            count = 0
            while cur.next != self._head:
                if cur.item == item:
                    return count
                count += 1
                cur = cur.next
            return -1
        
    # if __name__ == "__main__":
    #     ll = SinCycLinkedList()
    #     ll.add(1)
    #     ll.add(2)
    #     ll.travel()
    #     ll.append(3)
    #     ll.insert(2, 4)
    #     ll.insert(4, 5)
    #     ll.insert(0, 6)
    #     print("length ", ll.length())
    #     ll.travel()
    #     print("search(3)", ll.search(3))
    #     print("search(7)", ll.search(7))
    #     print("search(6)", ll.search(6))
    #     print("remove(1)")
    #     ll.remove(1)
    #     print("length: ", ll.length())
    #     print("remove(6)")
    #     ll.remove(6)
    #     ll.travel()

### 1.3 python实现双向链表 ###

*doubleLinkedList.py*

class Node:
        def __init__(self, item):
            self.item = item
            self.previous = None
            self.next = None
        
        def __str__(self):
            return str(self.item)
        
    class DLinkedList:
        """双向链表"""
        def __init__(self):
            self._head = None
        
        def is_empty(self):
            """判断链表是否为空"""
            return self._head is None
        
        def length(self):
            """返回链表长度"""
            if self.is_empty():
                return 0
            count = 1
            cur = self._head
            while cur.next is not None:
                count += 1
                cur = cur.next
            return count
        
        def travel(self):
            """遍历链表"""
            if self.is_empty():
                return
            cur = self._head
            print(cur.item)
            while cur.next is not None:
                cur = cur.next
                print(cur.item)
            print()
        
        def add(self, item):
            """链表头部添加节点"""
            node = Node(item)
            if self.is_empty():
                self._head = node
            else:
                node.next = self._head
                self._head.previous = node
                self._head = node
            
        def append(self, item):
            """链表尾部添加节点"""
            node = Node(item)
            if self.is_empty():
                self._head = node
            else:
                cur = self._head
                while cur.next is not None:
                    cur = cur.next
                cur.next = node
                node.previous = cur
        
        def insert(self, pos, item):
            """链表指定位置插入节点"""
            if pos <= 0:
                self.add(item)
            elif pos > self.length() - 1:
                self.append(item)
            else:
                cur = self._head
                node = Node(item)
                cur_pos = 0
                while cur is not None:
                    if cur_pos == pos - 1:
                        node.next = cur.next
                        node.previous = cur
                        cur.next = node
                        cur.next.previous = node
                        break
                    cur = cur.next
                    cur_pos += 1
        
        def remove(self, item):
            """链表删除指定元素"""
            if self.is_empty():
                return
            cur = self._head
            if cur.item == item:
                self._head = cur.next
                self._head.previous = None
            else:
                while cur.next is not None:
                    if cur.item == item:
                        cur.previous.next = cur.next
                        cur.next.previous = cur.previous
                        return
                    cur = cur.next
                if cur.item == item:
                    cur.previous.next = None
    
        def search(self, item):
            """查找链表指定元素，返回元素下标"""
            cur_pos = 0
            cur = self._head
            while cur is not None:
                if cur.item == item:
                    return cur_pos
                cur = cur.next
                cur_pos += 1
            return -1
        
    if __name__ == "__main__":
        ll = DLinkedList()
        ll.add(1)
        ll.add(2)
        ll.append(3)
        ll.insert(2, 4)
        ll.insert(4, 5)
        ll.insert(0, 6)
        print("length: ", ll.length())        
        ll.travel()
        print("search(3) ", ll.search(3))
        print("search(4) ", ll.search(4))
        print("search(10) ", ll.search(10))
        ll.remove(1)
        print("length: ", ll.length())
        ll.travel()
        print("删除首节点 remove(6): ")
        ll.remove(6)
        ll.travel()
        print("删除尾节点 remove(5): ")
        ll.remove(5)
        ll.travel()