Python数据结构与算法-线性表（链表）

清疚 2022-05-14 07:46 312阅读 0赞

### 1.单向链表：（10/31增加根据索引删除结点，删除头结点额尾部结点） ###

#1.单向链表：
    class SingleNode():
        def __init__(self, item):
            '''单向链表的结点实现'''
            self.item = item # item 存放数据
            self.next = None 
    #单链表的操作： 增删改查
    # is_empty() 链表是否为空
    # length() 链表长度
    # show() 遍历整个链表
    # add(item) 链表头部添加元素
    # append(item) 链表尾部添加元素
    # insert(pos, item) 指定位置添加元素
    # remove(item) 删除节点
    # search(item) 查找节点是否存在
    #remove_index(index)根据索引删除结点
    #remove_head()删除头部结点
    #remove_tail()删除尾部结点
    class SingleLinkList():
        '''单向链表的实现'''
        def __init__(self):
            self._head  = None 
        
        def is_empty(self):
            return self._head == None 
        
        def length(self):
            cur = self._head 
            count = 0
            while cur != None:  #xi此处错误写成  if 
                count += 1
                cur = cur.next 
            return count 
    
        def show(self):
            '''遍历列表数据'''
            list = []
            cur = self._head 
            while cur != None:
                list.append(cur.item)
                cur = cur.next 
            print(list)
    
        def add(self, item):
            '''在单向链表的头部增加元素'''
            node = SingleNode(item)
            node.next = self._head
            self._head = node 
            
        def append(self, item):
            '''在尾部添加数据:
            1.判断结点是否为空：如是增加即可
            2.不为空：1。找到尾部结点；2，增加结点
            '''
            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 = node
         
        def insert(self, pos , item):
            '''在指定位置添加数据:
            1.判断结点是否为空：如是增加即可
            2.不为空：1。找到尾部结点；2，增加结点
            '''
            node = SingleNode(item)
            if pos <= 0:
                self.add(item)
            elif pos > (self.length()-1):
                self.append(item)
            else:
                count = 0
                pre = self._head
                while count < (pos-1):
                    count += 1
                    pre = pre.next
                node.next = pre.next 
                pre.next = node 
         
        def remove(self, item):
            cur = self._head
            pre = None
            while cur != None:
                if cur.item == item:
                    if not pre:
                        self._head = cur.next
                    else:
                        pre.next = cur.next 
                    break
                else:
                    pre = cur 
                    cur = cur.next 
        def remove_head(self):
            #移除头部结点
            self._head = self._head.next
                
        def remove_index(self, index):
            #依据索引移除结点
            cur = self._head 
            pre = None 
            count = 0
            while cur is not None:
                if count == index:
                    if not pre:
                        self._head = cur.next
                    else:
                        pre.next = cur.next
                count += 1
                pre = cur 
                cur = cur.next 
            
        def remove_tail(self):
            #删除尾部结点
            print(self._head.next.item)
            cur = self._head 
            pre = None 
            while cur.next is not None:
                pre = cur 
                cur = cur.next
            pre.next = None
        def reseach(self, item):
            '''在单向链表的查找元素，如存在返回True，不存在返回False'''
            cur = self._head
            while cur is not None:
                if cur.item == item:
                    return True
                cur = cur.next 
            return False 
            
    s = SingleLinkList()
    s.append(12)
    s.append(100)
    s.show()
    print(s.length())
    s.insert(1, 222)
    s.remove(100)
    s.show()      
    # [12, 100]
    # 2
    # [12, 222]       
    s.add(11)
    s.show() # [11, 12, 222]
    print(s.reseach(12))    # True

### 2.单向循环列表： ###

单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。

#coding=gbk
    #单向循环链表
    # 单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。
    from platform import node
    class Node():
        '''定义结点'''
        def __init__(self, item):
            self.item = item 
            self.next = None
    
    # is_empty() 判断链表是否为空
    # length() 返回链表的长度
    # show() 遍历
    # add(item) 在头部添加一个节点
    # append(item) 在尾部添加一个节点
    # insert(pos, item) 在指定位置pos添加节点
    # remove(item) 删除一个节点
    # search(item) 查找节点是否存在
    class SinCycLinkedList():
        def __init__(self):
            self._head = None
            
        def is_empty(self):
            return self._head == None
        
        def length(self):
            '''获取单向循环链表的长度'''
            if self.is_empty():
                return 0
            count = 1 #    当 cur.next == self._head 时，表示已经有了一个结点
            cur = self._head 
            while cur.next != self._head:   #不同于普通的单向链表的判断条件： while cur.next != None:
                count += 1
                cur = cur.next 
            return count 
        
        def show(self):
            '''获取单向循环链表的数据'''
            if self.is_empty():
                return
            li = []
            cur = self._head
            li.append(cur.item)
            while cur.next != self._head:
                cur = cur.next 
                li.append(cur.item)
            print(li)
        
        def add(self, item):
            '''添加头结点'''
            node = Node(item)
            if self.is_empty():
                
                self._head = node
                node.next = self._head 
    
            else:
                node.next = self._head #如果不为空的话：1.将node.next 指向 头结点
                cur = self._head 
                while cur.next != self._head:   # 2.找到尾结点
                    cur = cur.next 
                cur.next = node    # 3. node作为头结点，连接头结点
                self._head = node #4. 复原头结点
        
        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     # 尾结点的 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:
                node = Node(item)
                cur = self._head    # 当pos为 1时的情况，不执行while语句
                count = 0
                while count < (pos-1):  # 当 pos 大于1 的情况，移动到指定位置的前一位置(pos - 1)
                    count += 1
                    cur = cur.next 
                node.next = cur.next
                cur.next = node
        
        def remove(self, item):
            '''依据数据值， 删除一个结点'''
            if self.is_empty():
                return 
            cur = self._head
            pre = None
            if cur.item == item:    #大的判断条件：是否头结点是要删除的元素
                if cur.next != self._head:  #如果还有多个结点
                    while cur.next != self._head:    # 先找到尾结点
                        cur = cur.next 
                    cur.next = self._head.next
                    self._head = self._head.next 
                else:
                    self._head = None   #如果只有1个结点，  则全部删除
                    
            else: #如果不是要删除头结点
                pre = self._head
                while cur.next != self._head:
                    if cur.item == item:
                        pre.next = cur.next 
                        return
                    else:
                        pre = cur 
                        cur = cur.next
                         
                if cur.item == item:    #如果恰好是尾结点
                    pre.next = cur.next
            print('输入的数值错误')    
                
            
                    
         
                
        def search(self, item):
            if self.is_empty():
                return False
            cur = self._head
            if cur.item == item:
                return True
            while cur.next != self._head:
                cur = cur.next
                if cur.item == item:
                    return True
            return False
                
    print('test------')
    s = SinCycLinkedList()
    s.add(10)
    s.add(11)
    s.show()    # [11, 10]
    print(s.is_empty()) #False
    print(s.length()) # 2 
    s.append(12)
    s.append(13)
    s.show()    # [11, 10, 12, 13] 
    print(s.length())   # 4
    s.insert(1, 100)    
    s.show()    # [11, 100, 10, 12, 13]
    print(s.search(12)) #True
    print(s.search(20)) #False
    s.remove(101)   #输入的数值错误
    s.show()    #[11, 100, 10, 12, 13]
    s.remove(11)
    s.show()    #[100, 10, 12, 13]

### 3.双向链表：（增加插入的结点图片解释） ###

每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。

#coding=gbk
    #双向链表
    #每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。
    class Node():
        def __init__(self, item):
            self.item = item 
            self.next = None
            self.pre = None
            
    #操作
    # is_empty() 链表是否为空
    # length() 链表长度
    # show() 遍历链表
    # add(item) 链表头部添加
    # append(item) 链表尾部添加
    # insert(pos, item) 指定位置添加
    # remove(item) 删除节点
    # search(item) 查找节点是否存在
    class DLinkList():
        def __init__(self):
            self._head = None
        def is_empty(self):
            return self._head == None
        def length(self):
            cur = self._head
            count = 0
            while cur != None:
                count += 1
                cur = cur.next 
            return count 
        def show(self):
            cur = self._head
            li = []
            while cur != None:
                li.append(cur.item)
                cur = cur.next 
            print(li)
        def search(self, item):
            if self.is_empty():
                return False
            else:
                cur = self._head
                while cur != None:
                    if cur.item == item:
                        return True
                    cur = cur.next 
                return False
            
        def add(self, item):
            '''在双向链表的头增加结点'''
            node = Node(item)
            if self.is_empty():
                self._head = node 
            else:
                node.next = self._head
                self._head.pre = node   #将_head 的pre 指向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 != None:
                    cur = cur.next 
                cur.next = node 
                node.pre = cur 
         
        def insert(self, pos, item):
            '''在双向链表的指定位置增加结点'''
            if pos <= 0:
                self.add(item)
            elif pos >(self.length() - 1):
                self.append(item)
            else:
                node = Node(item)
                cur = self._head
                count = 0
                while count < (pos - 1):
                    count += 1
                    cur = cur.next
                node.next = cur.next     #4 个指针的指向
                node.pre = cur 
                cur.next = node 
                cur = node
                 
        def remove(self, item):
            '''删除对应元素'''
            if self.is_empty():
                return 
            else:
                cur = self._head
                if cur.item == item:    #如果头结点就是要删除的元素
                    if cur.next == None:    #如果只有一个结点
                        self._head = None
                    else:
                        cur.next.pre = None
                        self._head = cur.next 
                    return
                    # 如果不是头结点时要删除的元素
                while cur != None:
                    if cur.item == item:
                        cur.pre.next = cur.next     #需要变换 2 个指向
                        cur.next.pre = cur.pre
                        return
                    cur = cur.next 
    
    print('test ===')
    d = DLinkList()
    d.add(11)
    d.add(12)
    d.show()    # [12, 11]
    print(d.length())   #2
    print(d.is_empty())#False
    d.append(13)
    d.append(14)
    d.show()    # [12, 11, 13, 14]
    print(d.search(11)) #True
    print(d.search(18)) #False
    d.insert(1, 100)
    d.show()    # [12, 100, 11, 13, 14]
    d.remove(11)
    d.show()    #[12, 100, 13, 14]
    # for i in range(10):
    #     print(i)
    #     return
    # i = 0
    # while i<10:
    #     i += 1
    #     if i == 5:
    #         break
    #     print(i)
    #     for k in range(1):
    #         print('kkkkkk')

**其中，插入元素中：**

node.next = cur.next     #4 个指针的指向
                node.pre = cur 
                cur.next = node 
                cur = node

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70]: /images/20220514/585e409cab6e480eb0befcdd4953d105.png