鞍山信息港二手房,seo推广哪家服务好,宁夏电力建设工程公司门户网站,哪家建站好目录 一、双向链表
定义类和封装函数以及测试样例如下#xff1a;
注意事项#xff1a;
二、循环链表
单循环列表的类和函数封装如下#xff1a;
注意事项#xff1a;
三、双向循环链表
结点类和双循环链表的定义部分
函数封装之判空和尾插
双循环链表遍历
双循…目录 一、双向链表
定义类和封装函数以及测试样例如下
注意事项
二、循环链表
单循环列表的类和函数封装如下
注意事项
三、双向循环链表
结点类和双循环链表的定义部分
函数封装之判空和尾插
双循环链表遍历
双循环链表尾删
完整测试以及结果
四、栈
顺序栈
顺序栈本质以及组成
顺序栈的操作
链栈 一、双向链表 对于单向链表而言。只能通过头节点或者第一个节点出发单向的访问后继节点每个节点只能记录其后继节点的信息位置不能向前遍历。 所以引入双向链表双向链表可以保持单向链表特点的基础上让每个节点既能向后访问后继节点也可以向前访问前驱节点。 相较于单向链表我们更多的是在每个结点上加入了一个前驱链接域
定义类和封装函数以及测试样例如下
class Node(object):def __init__(self,data):self.next Noneself.prior Noneself.data dataclass DoubleLinklist(object):def __init__(self):self.head Noneself.size 0def is_empty(self):return self.size 0def add_head(self,value):nodeNode(value)if self.is_empty():self.head nodeself.size1else:node.next self.headself.head.prior nodeself.head nodeself.size 1def show_me(self):if self.is_empty():print(空表查看不了)else:q self.headwhile q :print(q.data,end )q q.nextdef add_anywhere(self,location,value):if location 1 or location self.size1:print(插入失败)else:node Node(value)if location 1:self.add_head(value)else:q self.headi 1while i location-1:q q.nexti 1if q.next is None:q.next nodenode.prior qelse:node.next q.nextnode.prior qq.next.prior nodeq.next nodeself.size1def del_anywhere(self,location):if self.is_empty() or location 1 or location self.size:print(删除失败)else:if location 1:self.head self.head.nextself.head.prior Noneelse:qself.headi 1while i location :q q.nexti 1if q.next :q.prior.next q.nextq.next.prior q.priorelse:q.prior.next Noneself.size -1def find_node(self,value):if self.is_empty():print(查找失败)else:q self.headwhile q:if q.data value:return Trueq q.nextreturn Falseif __name__ __main__:new_lDoubleLinklist()print(头插)new_l.add_head(50)new_l.add_head(40)new_l.add_head(30)new_l.add_head(20)new_l.add_head(10)new_l.show_me()print()print(任意位置插入)new_l.add_anywhere(1,666)new_l.add_anywhere(7,666)new_l.add_anywhere(3,666)new_l.show_me()print()print(任意位置删除)new_l.del_anywhere(8)new_l.del_anywhere(3)new_l.del_anywhere(1)new_l.show_me()print()print(找是否存在值30)print(new_l.find_node(30))print()
结果如下 注意事项
对链表的删除和插入操作我们均要考虑空表、末尾元素、单个元素情况双循环链表的插入操作 : node.next q.next node.prior q q.next.prior node q.next node
这四条语句除了第一条的位置不能变动以外防止丢失结点后面的操作前后顺序没有强制要求。 二、循环链表
循环链表就是首尾相连的链表通过任意一个节点都能将整个链表遍历一遍
单循环列表的类和函数封装如下 class Node(object):def __init__(self,data):self.data dataself.next Noneclass CirculateLinkList(object):def __init__(self):self.head Noneself.size 0def is_empty(self):return self.size 0def add_tail(self,value):node Node(value)if self.is_empty():self.head nodenode.next nodeelse:q self.headi 1while i self.size:q q.nexti 1q.next nodenode.next self.headself.size 1def show_me(self):if self.is_empty():print(空表)elif self.size 1 :print(self.head.data)else:q self.headi 1while i self.size1: #q要定位到第一个结点才能遍历完print(q.data,end )qq.nexti 1def del_tail(self):if self.is_empty():print(删除失败)elif self.size 1 :self.head Noneself.size -1else:q self.headi 1while i self.size-1 :q q.nexti1q.next self.headself.size - 1if __name__ __main__:new_lCirculateLinkList()print(尾插)new_l.add_tail(30)new_l.add_tail(20)new_l.add_tail(10)new_l.show_me()print()print(尾删)new_l.del_tail()new_l.del_tail()new_l.show_me()print()
结果 注意事项
基本注意事项不再赘述这里有个格外要注意的点 def show_me(self): if self.is_empty(): print(空表) elif self.size 1 : print(self.head.data) else: q self.head i 1 while i self.size1: #q要定位到第一个结点才能遍历完 print(q.data,end ) qq.next i 1 while循环要多循环一次使得q指向第一个结点才能遍历完整 三、双向循环链表
双循环链表同样需要考虑几个点如何创建如何增删改查由于是双向的那么可以不用像单向的删除操作中一定要找到删除元素前一个位置可以直接定位到要删除的位置只需要把前驱后继都重新分配好即可。
结点类和双循环链表的定义部分
class Node(object):def __init__(self,data):self.datadataself.nextNoneself.priorNoneclass DoubleCirculateLinkList(object):def __init__(self):self.headNoneself.size0
函数封装之判空和尾插 注意尾插部分要注意分空表和单元素情况 def is_empty(self):return self.size 0def add_tail(self,value):nodeNode(value)if self.is_empty():self.headnodenode.nextnodenode.priornodeelif self.size 1:self.head.nextnodeself.head.priornodenode.nextself.headnode.priorself.headelse:qself.headwhile True:qq.nextif q.nextself.head:breaknode.nextself.headnode.priorqq.nextnodeself.head.priornodeself.size1
这里的常规尾插我用到的遍历循环是while True内部增加一个判断退出的条件来获得末尾结点q
情况全分析完毕整体判断外size1即可
双循环链表遍历
遍历涉及到打印我们用一个变量q来记录常规情况下要遍历到最后一个结点但这还不够要执行的下去循环内的打印语句才行所以要留意。 def show_me(self):if self.is_empty():print(空表)else:qself.headwhile True:print(q.data,end )qq.nextif q self.head:break
双循环链表尾删
首先空表无法删除单元素删除直接headNone常规情况可直接遍历到最后一个结点由于是双向的链表所以不用找倒数第二个结点了然后将该结点的前驱结点next指向headhead指向的结点的前驱再指向回来即可删除。 def del_tail(self):if self.is_empty():print(空表)elif self.size 1:self.head Noneelse:qself.headwhile True:qq.nextif q.nextself.head:breakq.prior.nextself.headself.head.priorq.priorself.size-1完整测试以及结果
class Node(object):def __init__(self,data):self.datadataself.nextNoneself.priorNoneclass DoubleCirculateLinkList(object):def __init__(self):self.headNoneself.size0def is_empty(self):return self.size 0def add_tail(self,value):nodeNode(value)if self.is_empty():self.headnodenode.nextnodenode.priornodeelif self.size 1:self.head.nextnodeself.head.priornodenode.nextself.headnode.priorself.headelse:qself.headwhile True:qq.nextif q.nextself.head:breaknode.nextself.headnode.priorqq.nextnodeself.head.priornodeself.size1def show_me(self):if self.is_empty():print(空表)else:qself.headwhile True:print(q.data,end )qq.nextif q self.head:breakdef del_tail(self):if self.is_empty():print(空表)elif self.size 1:self.head Noneelse:qself.headwhile True:qq.nextif q.nextself.head:breakq.prior.nextself.headself.head.priorq.priorself.size-1if __name__ __main__:new_lDoubleCirculateLinkList()print(尾插)new_l.add_tail(10)new_l.add_tail(20)new_l.add_tail(30)new_l.add_tail(40)new_l.add_tail(50)new_l.show_me()print()print(尾删)new_l.del_tail()new_l.del_tail()new_l.show_me()print() 四、栈
顺序栈
顺序存储的栈即是顺序栈
顺序栈本质以及组成
本质上顺序栈是一个只允许在栈顶进行插入和删除操作的顺序表遵循LIFO
需要使用一个容器存储一个栈例如列表
顺序栈的操作
这里直接使用内置函数去对栈封装
class Stack(object):def __init__(self):self.data []def is_empty(self):return self.data []def push(self,value):self.data.insert(0,value)def pop(self):self.data.pop(0)def show(self):for i in self.data:print(i,end )print()def get_top_value(self):return self.data[0]def get_size(self):return len(self.data)
链栈
既然顺序栈就是对栈顶元素增删的特殊的顺序表那么链栈就是对栈顶元素增删的特殊的单向链表
这里我的pop不仅实现了删除而且还增加了额外的返回值
代码如下
class Node(object):def __init__(self,data):self.datadataself.nextNoneclass LinkStack(object):def __init__(self):self.size0self.headNonedef is_empty(self):return self.size0def push(self,value):nodeNode(value)node.nextself.headself.headnodeself.size1def pop(self):if self.is_empty():print(空栈)else:qself.head.dataself.headself.head.nextself.size-1return qdef show(self):if self.is_empty():print(空栈)else:qself.headwhile q:print(q.data,end )qq.nextdef get_top_value(self):if self.is_empty():return Noneelse:return self.head.datadef get_size(self):return self.size未完待续持续跟新中
