阿里云网站备案注销吗,上海备案证查询网站查询网站查询,韩国外贸平台,为进一步加强网站建设一、链表 1、目的
解决顺序表存储数据有上限#xff0c;并且插入和删除操作效率低的问题。
2、概念
链表#xff1a;链式存储的线性表#xff0c;使用随机的物理内存存储逻辑上连续的数据。
链表的组成#xff1a;由一个个结点组成
结点#xff1a;由数据域和链接域组…一、链表 1、目的
解决顺序表存储数据有上限并且插入和删除操作效率低的问题。
2、概念
链表链式存储的线性表使用随机的物理内存存储逻辑上连续的数据。
链表的组成由一个个结点组成
结点由数据域和链接域组成是链表的基本单位。
数据域存储数据元素的区域。
链接域记录下一个结点所在位置的区域。
头结点虚设的一个节点链接域专门记录链表第一个节点位置数据域专门记录链表的长度。
3、链表的种类
单向链表、双向链表、循环链表
二、单向链表
1、单向链表的概念
只能通过头结点或链表的头单向的访问后继节点的链表叫单向链表 2、节点和链表类的格式
⑴包含存储数据元素的数据域
#封装普通节点的类
class Node:#构造函数 定义节点的属性def __init__(self, value):self.value value #普通节点的数据域self.next None #普通节点的链接域 刚构造的节点该位置域为空
⑵有一个存储下一个节点的位置域
#封装链表的类封装头结点
class LinkList:#构造函数def __init__(self, node None):self.size 0 #头结点的数据域为0 链表的长度为0self.head node #头结点的链接域指向None
3、单向链表的相关操作成员函数的封装
⑴判空
函数功能判断链表是否有节点除了头节点。思路头结点的链接域指向空则说明链表为空
函数的返回值逻辑值真、假---1,0 ----返回值int
函数名符合命名规则
参数列表链表 #判空def is_empy(self):return self.size 0 #判断链表长度是否为0#或者判断head是否为None
⑵头插 函数功能将一个节点以头插的方式插入到头结点的后面。思路如上图
函数名符合命名规则
参数列表self 链表、要插入的数据
注意事项
需要申请节点封装数据插入成功链表长度自增 #头插def add_head(self, value):#创建一个新的节点node Node(value)#头插node.next self.headself.head node#插入成功 链表长度自增self.size 1 头插效果 ⑶遍历 函数功能从头到尾打印出链表中每个节点的数据域的数据
函数返回值无
函数名符合命名规则
参数列表self 链表
注意事项判空 #遍历def show(self):#判空if self.is_empy():print(该链表为空)returnelse:q self.headwhile q:print(%d%(q.value),end )q q.next #改变q的指向print()
⑷尾插 函数功能将新的节点增加到链表的尾部。思路如上图
函数返回值无
函数名符合命名规则
参数列表self 链表要插入的数据
注意事项插入成功链表自增 #尾插def add_tail(self, value):#可以判空 空的话 直接将headnode#创建一个节点node Node(value)#找到链表的最后一个节点p self.headi1while iself.size:pp.nexti1#尾插p.next node#尾插成功 链表长度自增self.size 1 尾插效果 ⑸任意位置插 函数功能在指定的位置插入一个节点 思路如上图
函数返回值无
函数名符合命名规则
参数列表self链表、要插入的位置、要插入的数据
注意事项
判断要插入的位置是否合理成功插入 链表长度自增如果是第一个位置做头插 #任意位置插入数据def add_index(self, index, value):#判断位置是否合理if index0 or indexself.size1:print(插入失败)returnelse:pself.headif index 0: #当插入的是第一个位置 头插self.add_head(value)else:# 找到要插入位置的前一个节点p self.headi1while iindex:pp.nexti1#创建一个新的节点nodeNode(value)#插入node.nextp.nextp.nextnode#插入成功 链表自增self.size1 在5号位插入22 ⑹头删 函数功能删除链表的第一个节点除头节点。思路如上图
函数的返回值逻辑值真、假或者 无
函数名符合命名规则
参数列表链表、要删除的数据
注意事项判断链表是否为空 #头删def del_head(self):#判空if self.is_empy():print(删除失败该列表手中为空。)returnelse:#确认被删除元素deleted_value self.head.valueself.head self.head.nextself.size - 1#删除成功 长度自减print(f删除成功{deleted_value}已被删除) 头删 ⑺尾删 函数功能删除链表的最后一个节点。思路如上图
函数的返回值逻辑值真、假或者 无
函数名符合命名规则
参数列表链表、要删除的数据
注意事项
判断链表是否为空如果链表只有一个节点的情况 #尾删def del_tail(self):#判空if self.is_empy():print(删除失败该链表为空)elif self.size 1: #当链表只有一个节点时#确认被删除元素deleted_value self.head.valueself.head Noneself.size - 1print(f删除成功{deleted_value}已被删除)else:#找到最后一个节点的前一个节点q self.headwhile q.next.next:q q.next#确认被删除元素deleted_value q.next.value#删除q.next None #或 q.next q.next.nextself.size - 1#删除成功 长度自减print(f删除成功{deleted_value}已被删除) 尾删 ⑻任意位置删 函数功能在指定的位置删除一个节点 思路如上图
函数返回值逻辑值真、假或者 无
函数名符合命名规则
参数列表self链表、要删除的位置、要删除的数据
注意事项
判断要删除的位置是否合理成功删除 链表长度自减如果是第一个位置做头删 #按位置删除def del_at(self, index):#判断位置是否合理if index 0 or index self.size:print(删除失败位置无效)elif index 0: #当插入的是第一个位置 头删self.del_head()else:# 找到要删除位置的前一个节点p self.headfor _ in range(index - 1):p p.next#确认被删除元素deleted_value p.next.value#删除p.next None#删除成功 链表自减self.size - 1print(f删除成功{deleted_value}已被删除) 删除3号位的数据 ⑼按位置修改 函数功能在指定的位置修改一个节点 思路如上图
函数返回值无
函数名符合命名规则
参数列表self 顺序表要修改的位置、修改的数据
注意事项 判空 修改的位置是否合理 #按位置修改def modify_at(self, index, value):#判断位置是否合理if index 0 or index self.size:print(修改失败位置无效)else:# 找到要修改位置的节点p self.headfor _ in range(index):# 修改p p.nextp.value valueprint(f修改成功位置{index 1}的数据修改为{value}。) 把3号位的数据修改为33 ⑽按值修改 函数功能链表按值修改。思路如上图
函数的返回值逻辑值真、假 ---int 成功返回1失败返回0
函数名符合命名规则
参数列表self 顺序表、旧值、新值
注意事项需要判断链表是否合法链表是否为空新旧值是否相等 #按值修改def modify_by_value(self, old_value, new_value):# 找到要修改位置的节点p self.headfound Falsewhile p:#寻找旧值if p.value old_value:#把旧值修改成新值p.value new_valuefound Truep p.nextif found:print(f修改成功将值{old_value}修改为{new_value}。)else:print(f修改失败值{old_value}未找到。) 把40修改为44 ⑾按值查找返回位置 函数功能链表按值查找返回当前值的位置。思路如上图
函数的返回值----int 查找成功返回位置下标,查找失败0
函数名符合命名规则
参数列表self 顺序表、要查找的元素数据
注意事项需要判断顺序表是否合法顺序表是否为空 #按值查找返回位置def find_value(self, value):# 找到要查找位置的节点p self.headindex 0while p:#返回值if p.value value:return index 1p p.nextindex 1return -1 查找30在列表的什么位置 ⑿链表的反转 函数功能反转单链表的节点顺序使头尾节点互换。思路如上图
函数的返回值无
函数名符合命名规则
参数列表self 顺序表
注意事项
空链表或单节点链表反转后与原链表一致但打印成功消息。反转操作会更改链表结构不可撤销。 #链表的反转def reverse(self):#初始化一个临时变量node为None用于存储反转后的链表头node None#p指向链表的当前头节点遍历过程中会逐步向后移动p self.headwhile p:#暂存当前节点的下一个节点用于后续移动next_node p.next#反转当前节点的指针方向使其指向反转后的部分p.next nodenode pp next_node#最终更新链表的头节点为反转后的头节点self.head nodeprint(链表反转成功) 反转链表 三、链表应用
1、菜单界面
⑴主菜单 主菜单 ⑵添加菜单 添加菜单 ⑶删除菜单 删除菜单 ⑷修改菜单 修改菜单 2、完整代码
#判断输入是否为整数
def get_int(prompt):while True:try:value int(input(prompt))return valueexcept ValueError:print(无效输入请输入一个整数。)#判断输入是否在合理的范围内
def get_valid_int(prompt, min_val, max_val):while True:try:value int(input(prompt))if min_val value max_val:return valueelse:print(f输入不在范围{min_val}-{max_val}之间请重新输入。)except ValueError:print(无效输入请输入一个整数。)#判断选择是否合理
def get_choice(prompt, min_val, max_val):while True:try:value int(input(prompt))if min_val value max_val:return valueelse:print(无法处理您的指令请重新输入。)except ValueError:print(无效输入请输入一个整数。)#封装普通节点的类
class Node:#构造函数 定义节点的属性def __init__(self, value):self.value value #普通节点的数据域self.next None #普通节点的链接域 刚构造的节点该位置域为空#封装链表的类封装头结点
class LinkList:#构造函数def __init__(self, node None):self.size 0 #头结点的数据域为0 链表的长度为0self.head node #头结点的链接域指向None#判空def is_empy(self):return self.size 0 #判断链表长度是否为0#或者判断head是否为None#头插def add_head(self, value):#创建一个新的节点node Node(value)#头插node.next self.headself.head node#插入成功 链表长度自增self.size 1#尾插def add_tail(self, value):#可以判空 空的话 直接将headnode#创建一个节点node Node(value)#找到链表的最后一个节点p self.headi1while iself.size:pp.nexti1#尾插p.next node#尾插成功 链表长度自增self.size 1#任意位置插入数据def add_index(self, index, value):#判断位置是否合理if index0 or indexself.size1:print(插入失败)returnelse:pself.headif index 0: #当插入的是第一个位置 头插self.add_head(value)else:# 找到要插入位置的前一个节点p self.headi1while iindex:pp.nexti1#创建一个新的节点nodeNode(value)#插入node.nextp.nextp.nextnode#插入成功 链表自增self.size1#头删def del_head(self):#判空if self.is_empy():print(删除失败该列表手中为空。)returnelse:#确认被删除元素deleted_value self.head.valueself.head self.head.nextself.size - 1#删除成功 长度自减print(f删除成功{deleted_value}已被删除)#尾删def del_tail(self):#判空if self.is_empy():print(删除失败该链表为空)elif self.size 1: #当链表只有一个节点时#确认被删除元素deleted_value self.head.valueself.head Noneself.size - 1print(f删除成功{deleted_value}已被删除)else:#找到最后一个节点的前一个节点q self.headwhile q.next.next:q q.next#确认被删除元素deleted_value q.next.value#删除q.next None #或 q.next q.next.nextself.size - 1#删除成功 长度自减print(f删除成功{deleted_value}已被删除)#按位置删除def del_at(self, index):#判断位置是否合理if index 0 or index self.size:print(删除失败位置无效)elif index 0: #当插入的是第一个位置 头删self.del_head()else:# 找到要删除位置的前一个节点p self.headfor _ in range(index - 1):p p.next#确认被删除元素deleted_value p.next.value#删除p.next None#删除成功 链表自减self.size - 1print(f删除成功{deleted_value}已被删除)#按位置修改def modify_at(self, index, value):#判断位置是否合理if index 0 or index self.size:print(修改失败位置无效)else:# 找到要修改位置的节点p self.headfor _ in range(index):# 修改p p.nextp.value valueprint(f修改成功位置{index 1}的数据修改为{value}。)#按值修改def modify_by_value(self, old_value, new_value):# 找到要修改位置的节点p self.headfound Falsewhile p:#寻找旧值if p.value old_value:#把旧值修改成新值p.value new_valuefound Truep p.nextif found:print(f修改成功将值{old_value}修改为{new_value}。)else:print(f修改失败值{old_value}未找到。)#按值查找返回位置def find_value(self, value):# 找到要查找位置的节点p self.headindex 0while p:#返回值if p.value value:return index 1p p.nextindex 1return -1#链表的反转def reverse(self):#初始化一个临时变量node为None用于存储反转后的链表头node None#p指向链表的当前头节点遍历过程中会逐步向后移动p self.headwhile p:#暂存当前节点的下一个节点用于后续移动next_node p.next#反转当前节点的指针方向使其指向反转后的部分p.next nodenode pp next_node#最终更新链表的头节点为反转后的头节点self.head nodeprint(链表反转成功)#遍历def show(self):#判空if self.is_empy():print(该链表为空)returnelse:q self.headwhile q:print(%d%(q.value),end )q q.next #改变q的指向print()linkList LinkList()linkList.add_head(10)
linkList.add_head(20)
linkList.add_head(30)
linkList.add_head(40)
linkList.add_head(50)# 主菜单
while True:print(\n菜单)print(1. 显示所有数据)print(2. 添加数据)print(3. 删除数据)print(4. 修改数据)print(5. 查找数据)print(6. 链表反转)print(7. 退出)choice get_choice(请选择操作, 1, 7)if choice 1: #显示所有数据linkList.show()elif choice 2: #显示添加菜单while True:print()print(1. 添加到末尾)print(2. 插入到指定位置)print(3. 返回上一级)add_choice get_choice(请选择操作, 1, 3)if add_choice 1: #添加数据到末尾num get_int(请输入一个整数)linkList.add_tail(num)print(数字加入成功。)elif add_choice 2: #添加数据到指定位置index get_valid_int(f请输入插入位置1-{linkList.size 1}, 1, linkList.size 1) - 1value get_int(请输入一个整数)linkList.add_index(index, value)print(数字加入成功。)elif add_choice 3: #返回主菜单breakelif choice 3: #显示删除菜单while True:print()print(1. 删除第一个数据)print(2. 删除最后一个数据)print(3. 按位置删除数据)print(4. 返回上一级)del_choice get_choice(请选择操作, 1, 4)if del_choice 1: #删除第一个数据linkList.del_head()elif del_choice 2: #删除最后一个数据linkList.del_tail()elif del_choice 3: #按位置删除数据index get_valid_int(f请输入要删除的位置1-{linkList.size}, 1, linkList.size) - 1linkList.del_at(index)elif del_choice 4: #返回主菜单breakelif choice 4: #显示修改菜单while True:print()print(1. 按位置修改)print(2. 按值修改)print(3. 返回上一级)sub_choice get_choice(请选择操作, 1, 3)if sub_choice 1: #按位置修改index get_valid_int(f请输入修改位置1-{linkList.size}, 1, linkList.size) - 1value get_int(请输入新的值)linkList.modify_at(index, value)elif sub_choice 2: #按值修改old_value get_int(请输入要修改的原值)new_value get_int(请输入新的值)linkList.modify_by_value(old_value, new_value)elif sub_choice 3: #返回主菜单breakelif choice 5: #查找数据value get_int(请输入要查找的值)index linkList.find_value(value)if index ! -1:print(f值{value}位于位置{index}。)else:print(f值{value}未找到。)elif choice 6: #反转链表linkList.reverse()elif choice 7: #退出程序print(程序已退出。)break
