python数据结构基础(3)

书接上文.要创建一个单链表类,首先是初始化方法:

class singlelink:def __init__(self):self.head = Noneself.tail = Noneself.length=0return

判断链表是否为空:

def isempty(self):return self.length == 0

向链表尾部添加节点:

def add_node(self,item):if not isinstance(item,Node):item = Node(item)if self.head is None:self.head = itemself.tail = itemelse:self.tail.next = itemself.tail = itemself.length+=1return

在链表中插入节点:

def insert_node(self,index,data):if self.isempty():print('this link is empty')returnif index < 0 or index >= self.length:print('error:out of index')returnitem = Node(data)if index == 0:item.next = self.headself.head = itemself.length += 1return j = 0node = self.headprev = self.headwhile node.next and j<index:prex = nodenode = node.nextj += 1if j == index:item._next = nodeprev._next = itemself.length += 1

通过索引,在链表中删除节点:

def delete_node_byid(self,item_id):id = 1current_node = self.headprevious_node = Nonewhile current_node is not None:if id == item_id:if previous_node is not None:previous_node.next = current_node.nextelse:self.head = current_node.nextreturnprevious_node = current_nodecurrent_node = current_node.nextid = id + 1self.length-=1return

通过数值在链表中找到节点:

def find_node(self,value):current_node = self.headnode_id = 1results = []while current_node is not None:if current_node.has_value(value):results.append(node_id)current_node = current_node.nextnode_id = node_id + 1return results

按顺序输出链表:

def print_link(self):current_node = self.headwhile current_node is not None:print(current_node.data)current_node = current_node.nextreturn

最后尝试使用以上类和方法,形成一个有三个节点的简单链表,并将链表输出:

1 2 3

整体代码如下:

class Node:def __init__(self,data):self.data = dataself.next = Nonedef has_value(self,value):if self.data == value:return Trueelse:return Falseclass singlelink:def __init__(self):self.head = Noneself.tail = Noneself.length=0def isempty(self):return self.length == 0def add_node(self,item):if not isinstance(item,Node):item = Node(item)if self.head is None:self.head = itemself.tail = itemelse:self.tail.next = itemself.tail = itemself.length+=1returndef insert_node(self,index,data):if self.isempty():print('this link is empty')returnif index < 0 or index >= self.length:print('error:out of index')returnitem = Node(data)if index == 0:item.next = self.headself.head = itemself.length += 1return j = 0node = self.headprev = self.headwhile node.next and j<index:prex = nodenode = node.nextj += 1if j == index:item.next = nodeprev._next = itemself.length += 1def delete_node_byid(self,item_id):id = 1current_node = self.headprevious_node = Nonewhile current_node is not None:if id == item_id:if previous_node is not None:previous_node.next = current_node.nextelse:self.head = current_node.nextreturnprevious_node = current_nodecurrent_node = current_node.nextid = id + 1self.length-=1returndef find_node(self,value):current_node = self.headnode_id = 1results = []while current_node is not None:if current_node.has_value(value):results.append(node_id)current_node = current_node.nextnode_id = node_id + 1return resultsdef print_link(self):current_node = self.headwhile current_node is not None:print(current_node.data)current_node = current_node.nextreturnNode1 = Node(1)
Node2 = Node(2)
Node3 = Node(3)
#定义一个空链表
link = singlelink()
for node in [Node1,Node2,Node3]:link.add_node(node)
link.print_link()

参考书目:算法实例精讲