赞
踩
常用的数据结构有数组、链表(一对一)、栈和队列、哈希表、树(一对多)、图(多对多)等结构。
在本目录下我们将讲解,通过python语言实现常用的数据结构。
2.1链表的结构
链表(linked list)是一种在物理上非连续、非顺序的数据结构,由若干节点(node)所组成。
(1)单向链表的每一个节点又包含两部分,一部分是存放数据的变量data,另一部分是指向下一节点的指针next。
表示方式如下:
#定义单链表节点
class Node:
def __init__(self, data):
self.data = data
self.next = None
(2)双向链表不仅能找到下一个节点,还可回溯到前置节点。其每一个节点包括data变量,next和prev指针。
表示方式如下:
#定义双向链表节点
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
2.2链表的基本操作
(1)查找操作
在查找元素时,链表不像数组那样可以通过下标快速进行定位,只能从头结点开始向后一个一个节点主义查找。步骤:首先定位到头结点,然后根据头结点的next指针,定位到下一个节点,就这样不断通过next指针顺序定位,直到定位到要查找的元素。
关键点:链表中的数据只能按顺序进行访问,最坏的时间复杂度是O(n)。
(2)更新(修改)节点
如果不考虑查找节点的过程,链表的更新过程会像数组那样简单,直接把旧数据(data)替换成新数据(data)即可。
(3)插入节点
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.size = 0 #节点的个数 self.head = None #初始化节点的头指针 self.last = None #初始化节点的尾指针 #查找第几个节点,index表示第几个节点,不是索引号 def get(self,index): if index < 0 or index >= self.size: raise Exception("超出链表节点范围!") p = self.head for i in range(index): p = p.next return p def insert(self, data, index): if index < 0 or index > self.size: raise Exception("超出链表节点范围!") node = Node(data) #空链表 if self.size == 0: self.head = node self.last = node #插入头部 elif index == 0: node.next = self.head self.head = node #插入尾部 elif index == self.size: self.last.next = node self.last = node #此处不需要让node.next指向None,默认指向None了 #插入中间 else: pre_node = self.get(index-1)#查找到插入节点的前置节点 node.next = pre_node.next pre_node.next = node self.size += 1 #不要忘记插入节点后,链表的节点数要加1 def remova(self, index): if index < 0 or index >= self.size: raise Exception("超出链表节点范围!") #暂存被删除的节点,用于返回 #删除头结点 if index == 0: remove_node = self.head self.head = self.head.next #删除尾节点 elif index == self.size: pre_node = self.get(index-1) remove_node = pre_node.next pre_node.next = None self.last = pre_node #删除中间节点 else: pre_node = self.get(index-1) next_node = pre_node.next.next remove_node = pre_node.next pre_node.next = next_node self.size -= 1 #不要忘记删除节点后,链表的节点数要减1 return remove_node def output(self): p = self.head # while p : while p is not None: print(p.data,end="\t") p = p.next linklist = LinkedList() linklist.insert(30, 0) linklist.insert(60, 0) linklist.insert(20, 1) linklist.insert(90, 0) linklist.output() #结果为:90 60 20 30 print() #换行符 linklist.remova(0) linklist.output() #结果为:60 20 30
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。