肇东网站建设云聚达,白云做网站,wordpress添加子站,wordpress页面无法显示链表
链表的定义:
链表#xff08;Linked list#xff09;是一种常见的基础数据结构#xff0c;是一种线性表#xff0c;但是不像顺序表一样连续存储数据#xff0c;而是在每一个节点#xff08;数据存储单元#xff09;里存放下一个节点的位置信息#xff08;即地址…链表
链表的定义:
链表Linked list是一种常见的基础数据结构是一种线性表但是不像顺序表一样连续存储数据而是在每一个节点数据存储单元里存放下一个节点的位置信息即地址。 单项链表
单向链表也叫单链表是链表中最简单的一种形式它的每个节点包含两个域一个信息域元素域和一个链接域。这个链接指向链表中的下一个节点而最后一个节点的链接域则指向一个空值。 表元素域elem用来存放具体的数据。链接域next用来存放下一个节点的位置python中的标识变量p指向链表的头节点首节点的位置从p出发能找到表中的任意节点。单向链表单链表的操作
is_empty() 链表是否为空
length() 链表长度
travel() 遍历整个链表
add(item) 链表头部添加元素
append(item) 链表尾部添加元素
insert(pos, item) 指定位置添加元素
remove(item) 删除节点
search(item) 查找节点是否存在class Node(object):单向链表的节点def __init__(self, item):self.elem itemself.next Noneclass SingleLinkList(object):单链表def __init__(self):self.__head Nonedef is_empty(self):链表是否为空return self.__head Nonedef length(self):链表长度cur self.__headcount 0while cur ! None:cur cur.nextcount 1return countdef travel(self):遍历整个链表cur self.__headwhile cur ! None:print(cur.elem, end )cur cur.nextprint()def add(self, item):链表头部添加元素node Node(item)node.next self.__headself.__head nodedef append(self, item):链表尾部添加元素cur self.__headnode Node(item)if cur None:self.__head nodeelse:while cur.next ! None:cur cur.nextcur.next nodedef insert(self, pos, item):指定位置添加元素if pos 0:self.add(item)elif pos (self.length() - 1):self.append(item)else:pre self.__headcount 0while count (pos - 1):count 1pre pre.nextnode Node(item)node.next pre.nextpre.next nodedef remove(self, item):删除节点cur self.__headpre Nonewhile cur ! None:if cur.elem item:# 判断是否是第一if pre None:self.__head cur.nextelse:pre.next cur.nextbreakelse:pre curcur cur.nextdef search(self, item):查找节点是否存在cur self.__headwhile cur ! None:if cur.elem item:return Truecur cur.nextreturn FalsesingList SingleLinkList()singList.add(a)
singList.add(b)
singList.append(c)
singList.append(d)
singList.append(e)
singList.append(f)
singList.append(g)print(singList.is_empty())
print(singList.length())
singList.travel()print(search, singList.search(1))singList.remove(b)singList.travel()singList.insert(3, 3)
singList.travel()
单向循环链表
单链表的一个变形是单向循环链表链表中最后一个节点的next域不再为None而是指向链表的头节点。 单循环链表class Node(object):单向链表的节点def __init__(self, item):self.elem itemself.next Noneclass SingleCircleLinkList(object):单循环链表def __init__(self, node None):self.__head nodeif node:node.next nodedef is_empty(self):链表是否为空return self.__head Nonedef length(self):链表长度cur self.__headcount 1while cur.next ! self.__head:count 1cur cur.nextreturn countdef travel(self):遍历整个链表cur self.__headif cur None:returnelse:while cur.next ! self.__head:print(cur.elem, end )cur cur.nextprint(cur.elem)def add(self, item):链表头部添加元素cur self.__headnode Node(item)if cur None:self.__head nodenode.next nodeelse:while cur.next ! self.__head:cur cur.nextnode.next cur.nextself.__head nodecur.next nodedef append(self, item):链表尾部添加元素cur self.__headnode Node(item)if cur None:self.__head nodenode.next nodeelse:while cur.next ! self.__head:cur cur.nextcur.next nodenode.next self.__headdef insert(self, pos, item):指定位置添加元素if pos 0:self.add(item)elif pos (self.length() - 1):self.append(item)else:count 0cur self.__headpre Nonenode Node(item)while count pos:count 1pre curcur cur.nextnode.next curpre.next nodedef remove(self, item):删除节点注意1、为空2、第一个节点的情况a) 列表只有一个节点b) 列表有多个节点3、在中间的情况if self.is_empty():return Nonecur self.__headpre Nonewhile cur.next ! self.__head:if cur.elem item:if cur self.__head:rear self.__headwhile rear.next ! self.__head:rear rear.nextself.__head cur.nextrear.next self.__headelse:pre.next cur.nextreturnelse:pre curcur cur.next# 链表的最后一个元素if cur.elem item:if pre None:self.__head Noneelse:pre.next self.__headdef search(self, item):查找节点是否存在cur self.__headif cur None:return Falsewhile cur.next ! self.__head:if cur.elem item:return Truecur cur.nextif cur.elem item:return Truereturn Falsen Node(1)
sc SingleCircleLinkList()sc.add(a)
sc.add(b)
sc.add(c)
sc.add(d)
sc.add(e)
sc.add(f)
sc.append(11)
sc.insert(2, 22)sc.travel()sc.remove(f)
sc.travel()
双向链表
一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接一个指向前一个节点当此节点为第一个节点时指向空值而另一个指向下一个节点当此节点为最后一个节点时指向空值。 双向链表
class Node(object):节点def __init__(self, item):self.elem itemself.prev Noneself.next Noneclass DoubleLinkList(object):双向链表def __init__(self, node None):self.__head nodedef is_empty(self):链表是否为空return self.__head Nonedef length(self):链表长度cur self.__headcount 0while cur ! None:cur cur.nextcount 1return countdef travel(self):遍历整个链表cur self.__headwhile cur ! None:print(cur.elem, end )cur cur.nextprint()def add(self, item):链表头部添加元素node Node(item)if self.__head None:self.__head nodeelse:node.next self.__headself.__head.prev nodeself.__head nodedef append(self, item):链表尾部添加元素node Node(item)cur self.__headif cur None:self.__head nodeelse:while cur.next ! None:cur cur.nextcur.next nodenode.prev curdef insert(self, pos, item):指定位置添加元素if pos 0:self.add(item)elif pos (self.length() - 1):self.append(item)else:node Node(item)cur self.__headcount 0while count pos:count 1cur cur.nextnode.next curnode.prev cur.prevcur.prev nodenode.prev.next nodedef remove(self, item):删除节点cur self.__headwhile cur ! None:if cur.elem item:if cur self.__head:删除第一个元素self.__head cur.nextif cur.next:cur.next.prev Noneelse:cur.prev.next cur.nextif cur.next:cur.next.prev cur.prevreturnelse:cur cur.nextdef search(self, item):查找节点是否存在cur self.__headwhile cur ! None:if cur.elem item:return Truecur cur.nextreturn Falsedl DoubleLinkList()print(is_empty , dl.is_empty())
print(length , dl.length())
dl.add(aa)
dl.add(bb)
dl.add(cc)
dl.append(dd)
dl.append(ee)dl.travel()# dl.remove(cc)
dl.remove(bb)
dl.remove(ee)
dl.travel()# print(dl.search(1))dl.insert(0, 00)
dl.insert(2, 22)dl.travel()