中心主题 谁践踏了优雅 2023-06-08 14:57 133阅读 0赞 ## 4.链表 ## ### 概念 ### * 顺序表，将元素顺序地存放在-块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。 * 链表，将元素存放在通过链接构造起来的一系列存储块中。 * 顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活。 链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。 * 链表(Linked list)是一种常见的基础数据结构，是-种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点(数据存储单元)里存放下一个节点的位置信息(即地址)。 ### 单向链表 ### * 单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域(元素域)和一个链接域。这个链接指向链表中的下一一个节点，而最后一个节点的链接域则指向一个空值。 * ●表元素域elem用来存放具体的数据。 ●链接域next用来存放下一个节点的位置(python中的标识)。 ●变量p指向链表的头节点(首节点)的位置，从p出发能找到表中的任意节点。 * 节点实现 * class SingleNode(object()):\#单链表的结点”… def **init**(self,item): # \_ item存放数据元素 # self.item = item \#\_ next是下一个节点的标识 self.next= None * 单向链表的操作 * ●is\_empty0链表是否为空 ●length()链表长度 ●travel() 遍历整个链表 ●add(item) 链表头部添加元素 ●append(item) 链表尾部添加元素 ●insert(pos, item)指定位置添加元素 ●remove(item) 删除节点 ●search(item) 查找节点是否存在 * 单向链表的实现 * 链表和顺序表比对 * 注意虽然表面看起来复杂度都是O(n),但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找，删除和插入操作本身的复杂度是0(1)。顺序表查找很快，主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作，只能通过拷贝和覆盖的方法进行。 class Node(object): def __init__(self,elem): self.elem=elem self.next=None node=Node(100) class single_link_list(object): def __init__(self,node=None): self.__head=node 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 travel(self): cur=self.__head while cur !=None: print(cur.elem,end=' ') cur=cur.next def add(self,item): node=Node(item) node.next=self.__head 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 def insert(self,pos, item): if pos<=0: self.add(item) elif pos>(self.length()-1): self.append(item) else: pre=self.__head count=0 while count<(pos-1): count +=1 pre=pre.next node=Node(item) node.next=pre.next pre.next=node def remove(self,item): cur=self.__head pre=None while cur!=None: if cur.elem==item: if cur==self.__head: self.__head=cur.next else: pre.next=cur.next break else: pre=cur cur=cur.next def search(self,item): cur=self.__head while cur!=None: if cur.elem==item: return True else: cur=cur.next return False if __name__ == '__main__': ll=single_link_list() print(ll.is_empty()) print(ll.length()) ll.append(1) print(ll.is_empty()) print(ll.length()) ll.append(21) ll.add(3333333333333333) ll.append(22) ll.append(24) ll.append(2555) ll.insert(-1,321) ll.insert(99,88) ll.insert(2,4) ll.append(277) ll.append(452) ll.append(267890) ll.search(11) print(ll.is_empty()) print(ll.length()) ll.travel() ll.search(34) ll.remove(4) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTAzOTk3_size_16_color_FFFFFF_t_70] ### 双向列表 ### * 后继节点 * 前驱节点 * `在这里插入代码片` class Node(object): def __init__(self,item): self.elem=item self.next=None self.prev=None class double_link_list(object): def __init__(self,node=None): self.__head=node 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 travel(self): cur=self.__head while cur !=None: print(cur.elem,end=' ') cur=cur.next def add(self,item): node=Node(item) node.next=self.__head self.__head=node node.next.prev=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.prev=cur def insert(self,pos, item): if pos<=0: self.add(item) elif pos>(self.length()-1): self.append(item) else: cur=self.__head count=0 while count<pos: count +=1 cur=cur.next node=Node(item) node.next=cur node.prev=cur.prev cur.prev.next=node cur.prev=node def remove(self,item): cur=self.__head while cur!=None: if cur.elem==item: if cur==self.__head: self.__head=cur.next if cur.next: cur.next.prev=None else: cur.prev.next=cur.next if cur.next: cur.next.prev=cur.prev break else: cur=cur.next def search(self,item): cur=self.__head while cur!=None: if cur.elem==item: return True else: cur=cur.next return False if __name__ == '__main__': ll=double_link_list() print(ll.is_empty()) print(ll.length()) ll.append(1) print(ll.is_empty()) print(ll.length()) ll.append(21) ll.add(3333333333333333) ll.append(22) ll.append(24) ll.append(2555) ll.insert(-1,321) ll.insert(99,88) ll.insert(2,4) ll.append(277) ll.append(452) ll.append(267890) ll.search(11) print(ll.is_empty()) print(ll.length()) ll.travel() ll.search(34) ll.remove(4) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTAzOTk3_size_16_color_FFFFFF_t_70 1] ### 单向循环列表 ```python class Node(object): def __init__(self,elem): self.elem=elem self.next=None node=Node(100) class single_cycle_link_list(object): def __init__(self,node=None): self.__head=node if node: node.next=node def is_empty(self): return self.__head==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 while cur.next !=self.__head: print(cur.elem,end=' ') cur=cur.next print(cur.elem) def add(self,item): node=Node(item) if self.is_empty(): self.__head=node node.next=node else: cur=self.__head while cur.next !=self.__head: cur=cur.next node.next=self.__head #self.__head=node cur.next=self.__head def append(self,item): node=Node(item) if self.is_empty(): self.__head=node node.next=node else: cur=self.__head while cur.next !=self.__head: cur=cur.next node.next=self.__head cur.next=node def insert(self,pos, item): if pos<=0: self.add(item) elif pos>(self.length()-1): self.append(item) else: pre=self.__head count=0 while count<(pos-1): count +=1 pre=pre.next node=Node(item) node.next=pre.next pre.next=node def remove(self,item): if self.is_empty(): return cur=self.__head pre=None while cur.next!=self.__head: if cur.elem==item: if cur==self.__head: new=self.__head while new.next !=self.__head: new=new.next self.__head=cur.next new.next=self.__head else: pre.next=cur.next return else: pre=cur cur=cur.next if cur.elem ==item: if cur==self.__head: self.__head=None else: pre.next=cur.next def search(self,item): if self.is_empty(): return False cur=self.__head while cur.next!=self.__head: if cur.elem==item: return True else: cur=cur.next if cur.elem==item: return True return False if __name__ == '__main__': ll=single_cycle_link_list() print(ll.is_empty()) print(ll.length()) ll.append(1) print(ll.is_empty()) print(ll.length()) ll.append(21) ll.add(3333333333333333) ll.append(22) ll.append(24) ll.append(2555) ll.insert(-1,321) ll.insert(99,88) ll.insert(2,4) ll.append(277) ll.append(452) ll.append(267890) ll.search(11) print(ll.is_empty()) print(ll.length()) ll.travel() ll.search(34) ll.remove(4) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTAzOTk3_size_16_color_FFFFFF_t_70 2] *XMind: ZEN - Trial Version* [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTAzOTk3_size_16_color_FFFFFF_t_70]: /images/20230531/5e0e5579c33c48d487d3d5eb257a790b.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTAzOTk3_size_16_color_FFFFFF_t_70 1]: /images/20230531/64ef7a2269fd4486b5b94983bfa0adbf.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTAzOTk3_size_16_color_FFFFFF_t_70 2]: /images/20230531/a2026a8ebedc4535be4bd15c607984fe.png
相关 中心主题 5.数据类型 元组（tuple） 特点 任意对象的有序集合 通过下标来访问 属于‘’不可变类型‘’ ╰+哭是因爲堅強的太久メ/ 2023年08月17日 16:52/ 0 赞/ 110 阅读
相关 中心主题 5.数据类型 数值 声明、赋值、使用 表达式 显示 ‘0:.2f’.format(4.444) import Dear 丶/ 2023年08月17日 16:18/ 0 赞/ 130 阅读
相关 中心主题 4.链表 概念 顺序表，将元素顺序地存放在-块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。 链表，将元素存放在通过链接构造起来的一系列存储 谁践踏了优雅/ 2023年06月08日 14:57/ 0 赞/ 134 阅读
相关 中心主题 18.文件读取 txt def write\_txt(): with open(‘data.txt’,‘w’,encoding=‘utf8’) a 淩亂°似流年/ 2023年06月07日 08:23/ 0 赞/ 34 阅读
相关 中心主题 15.正则表达式 概述 概念 Regular Expression 一种文本模式，描述在搜索文本时要匹配的一个或多个字符 分手后的思念是犯贱/ 2023年06月06日 12:22/ 0 赞/ 27 阅读
相关 中心主题 13.对象持久化 扁平文件 文本文件 使用列表存储出现，把标点符号独立存储问题 使用eval()可以解决上述问题，但是当 ゝ一纸荒年。/ 2023年06月05日 13:59/ 0 赞/ 52 阅读
浅浅的花香味﹌
╰+哭是因爲堅強的太久メ
不念不忘少年蓝@
淩亂°似流年
分手后的思念是犯贱
￡神魔★判官ぃ
还没有评论，来说两句吧...