Python常见的数据结构实现（python 常用数据结构）
off999 2024-11-09 12:52 15 浏览 0 评论
一、链表
class LinkNode: #单链表结点类
def __init__(self,data=None): #构造函数
self.data=data #data属性
self.next=None class LinkList: #单链表类
def __init__(self): #构造函数
self.head=LinkNode() #头结点head
self.head.next=None
def CreateListF(self, a): #头插法：由数组a整体建立单链表
for i in range(0,len(a)): #循环建立数据结点s
s=LinkNode(a[i]) #新建存放a[i]元素的结点s
s.next=self.head.next #将s结点插入到开始结点之前,头结点之后
self.head.next=s
def CreateListR(self, a): #尾插法：由数组a整体建立单链表
t=self.head #t始终指向尾结点,开始时指向头结点
for i in range(0,len(a)): #循环建立数据结点s
s=LinkNode(a[i]); #新建存放a[i]元素的结点s
t.next=s #将s结点插入t结点之后
t=s
t.next=None #将尾结点的next成员置为null
def geti(self, i): #返回序号为i的结点
p=self.head
j=-1
while (j<i and p is not None):
j+=1
p=p.next
return p
def Add(self, e): #在线性表的末尾添加一个元素e
s=LinkNode(e) #新建结点s
p=self.head
while p.next is not None: #查找尾结点p
p=p.next
p.next=s; #在尾结点之后插入结点s
def getsize(self): #返回长度
p=self.head
cnt=0
while p.next is not None: #找到尾结点为止
cnt+=1
p=p.next
return cnt
def __getitem__(self,i): #求序号为i的元素
assert i>=0 #检测参数i正确性的断言
p=self.geti(i)
assert p is not None #p不为空的检测
return p.data
def __setitem__(self, i, x): #设置序号为i的元素
assert i>=0 #检测参数i正确性的断言
p=self.geti(i)
assert p is not None #p不为空的检测
p.data=x
def GetNo(self,e): #查找第一个为e的元素的序号
j=0
p=self.head.next
while p is not None and p.data!=e:
j+=1 #查找元素e
p=p.next
if p is None:
return -1 #未找到时返回-1
else:
return j #找到后返回其序号
def Insert(self, i, e): #在线性表中序号i位置插入元素e
assert i>=0 #检测参数i正确性的断言
s=LinkNode(e) #建立新结点s
p=self.geti(i-1) #找到序号为i-1的结点p
assert p is not None #p不为空的检测
s.next=p.next #在p结点后面插入s结点
p.next=s
def Delete(self,i): #在线性表中删除序号i位置的元素
assert i>=0 #检测参数i正确性的断言
p=self.geti(i-1) #找到序号为i-1的结点p
assert p.next is not None #p.next不为空的检测
p.next=p.next.next; #删除p结点的后继结点
def display(self): #输出线性表
p=self.head.next
while p is not None:
print(p.data,end=' ')
p=p.next;
print()if __name__ == '__main__':
L=LinkList()
for i in range(1,6):
L.Add(i)
print("L: ",end=''),L.display()
print("序号为2的元素=%d" %(L[2]))
print("设置序号为2的元素为8")
L[2]=8
print("序号为2的元素=%d" %(L[2]))
n=L.getsize()
print("size=%d" %(n))
for i in range(0,n):
print("删除%d序号的元素" %(0))
L.Delete(0)
print("L: ",end=''),L.display()
print("size=%d" %(L.getsize()))二、顺序表
class SqList:
def __init__(self): #构造函数
self.initcapacity=5; #初始容量设置为10
self.capacity=self.initcapacity #容量设置为初始容量
self.data=[None]*self.capacity #设置顺序表的空间
self.size=0 #长度设置为0
def resize(self, newcapacity): #改变顺序表的容量为newcapacity
assert newcapacity>=0 #检测参数正确性的断言
olddata=self.data
self.data=[None]*newcapacity
self.capacity=newcapacity
for i in range(self.size):
self.data[i]=olddata[i]
def CreateList(self, a): #由数组a中元素整体建立顺序表
for i in range(0,len(a)):
if self.size==self.capacity: #出现上溢出时
self.resize(2*self.size); #扩大容量
self.data[self.size]=a[i]
self.size+=1 #添加后元素个数增加1
def Add(self, e): #在线性表的末尾添加一个元素e
if self.size==self.capacity: #顺序表空间满时倍增容量
self.resize(2*self.size)
self.data[self.size]=e #添加元素e
self.size+=1 #长度增1
def getsize(self): #返回长度
return self.size
def __getitem__(self,i): #求序号为i的元素
assert 0<=i<self.size #检测参数i正确性的断言
return self.data[i]
def __setitem__(self, i, x): #设置序号为i的元素
assert 0<=i<self.size #检测参数i正确性的断言
self.data[i]=x
def GetNo(self, e): #查找第一个为e的元素的序号
i=0;
while i<self.size and self.data[i]!=e:
i+=1 #查找元素e
if (i>=self.size): #未找到时返回-1
return -1;
else:
return i; #找到后返回其序号
def Insert(self, i, e): #在线性表中序号i位置插入元素e
assert 0<=i<=self.size #检测参数i正确性的断言
if self.size==self.capacity: #满时倍增容量
self.resize(2*self.size)
for j in range(self.size,i,-1): #将data[i]及后面元素后移一个位置
self.data[j]=self.data[j-1]
self.data[i]=e #插入元素e
self.size+=1 #长度增1
def Delete(self, i): #在线性表中删除序号i的元素
assert 0<=i<=self.size-1 #检测参数i正确性的断言
for j in range(i,self.size-1):
self.data[j]=self.data[j+1] #将data[i]之后的元素前移一个位置
self.size-=1 #长度减1
if self.capacity>self.initcapacity and self.size<=self.capacity/4:
self.resize(self.capacity//2) #满足要求容量减半
def display(self): #输出顺序表
for i in range(0,self.size):
print(self.data[i],end=' ')
print()
if __name__ == '__main__':
L=SqList()
for i in range(1,6):
L.Add(i)
print("L: ",end=''),L.display()
print("序号为2的元素=%d" %(L[2]))
print("设置序号为2的元素为8")
L[2]=8
print("序号为2的元素=%d" %(L[2]))
n=L.getsize()
print("size=%d" %(n))
for i in range(0,n):
print("删除%d序号的元素" %(0))
L.Delete(0)
print("L: ",end=''),L.display()
print("size=%d" %(L.getsize()))三、顺序栈
#顺序栈
class SqStack:
def __init__(self): #构造函数
self.data=[] #存放栈中元素，初始为空
def empty(self): #判断栈是否为空
if len(self.data)==0:
return True
return False
def push(self,e): #元素e进栈
self.data.append(e)
def pop(self): #元素出栈
assert not self.empty() #检测栈为空
return self.data.pop()
def gettop(self): #取栈顶元素
assert not self.empty() #检测栈为空
return self.data[len(self.data)-1]
if __name__ == '__main__':
st=SqStack()
st.push(1)
st.push(2)
st.push(3)
st.push(4)
print("出栈顺序:",end=' ')
while not st.empty():
print(st.pop(),end=' ')
print()四、非循环列表
MaxSize=100 #假设容量为100
class SqQueue: #非循环队列类
def __init__(self): #构造方法
self.data=[None]*MaxSize #存放队列中元素
self.front=-1 #队头指针
self.rear=-1 #队尾指针
def empty(self): #判断队列是否为空
return self.front==self.rear
def push(self,e): #元素e进队
assert not self.rear==MaxSize-1 #检测队满
self.rear+=1
self.data[self.rear]=e
def pop(self): #出队元素
assert not self.empty() #检测队空
self.front+=1
return self.data[self.front]
def gethead(self): #取队头元素
assert not self.empty() #检测队空
return self.data[self.front+1]
if __name__ == '__main__':
qu=SqQueue()
qu.push(1)
qu.push(2)
qu.push(3)
while not qu.empty():
print(qu.pop(),end=' ')
print()五、链栈
class LinkNode: #单链表结点类
def __init__(self,data=None): #构造方法
self.data=data #data域
self.next=None #next域
class LinkStack: #链栈类
def __init__(self): #构造方法
self.head=LinkNode() #头结点head
self.head.next=None
def empty(self): #判断栈是否为空
if self.head.next==None:
return True
return False
def push(self,e): #元素e进栈
p=LinkNode(e)
p.next=self.head.next
self.head.next=p
def pop(self): #元素出栈
assert self.head.next!=None #检测空栈的异常
p=self.head.next;
self.head.next=p.next
return p.data
def gettop(self): #取栈顶元素
assert self.head.next!=None #检测空栈的异常
return self.head.next.data
if __name__ == '__main__':
st=LinkStack()
st.push(1)
st.push(2)
st.push(3)
st.push(4)
print("出栈顺序:",end=' ')
while not st.empty():
print(st.pop(),end=' ')
print()
六、链队
class LinkNode: #链队结点类
def __init__(self,data=None): #构造方法
self.data=data #data域
self.next=None #next域
class LinkQueue: #链队类
def __init__(self): #构造方法
self.front=None #队头指针
self.rear=None #队尾指针
def empty(self): #判断队是否为空
return self.front==None
def push(self,e): #元素e进队
s=LinkNode(e) #新建结点s
if self.empty(): #原链队为空
self.front=self.rear=s
else: #原链队不空
self.rear.next=s #将s结点链接到rear结点后面
self.rear=s
def pop(self): #出队操作
assert not self.empty() #检测空链队
if self.front==self.rear: #原链队只有一个结点
e=self.front.data #取首结点值
self.front=self.rear=None #置为空队
else: #原链队有多个结点
e=self.front.data #取首结点值
self.front=self.front.next #front指向下一个结点
return e
def gethead(self): #取队顶元素操作
assert not self.empty() #检测空链队
e=self.front.data #取首结点值
return e
if __name__ == '__main__':
qu=LinkQueue()
qu.push(1)
qu.push(2)
qu.push(3)
qu.push(4)
print("队头元素: %d" %(qu.gethead()))
print("出队顺序:",end=' ')
while not qu.empty():
print(qu.pop(),end=' ')
print()七、顺序栈
#顺序栈
class SqStack:
def __init__(self): #构造函数
self.data=[] #存放栈中元素，初始为空
def empty(self): #判断栈是否为空
if len(self.data)==0:
return True
return False
def push(self,e): #元素e进栈
self.data.append(e)
def pop(self): #元素出栈
assert not self.empty() #检测栈为空
return self.data.pop()
def gettop(self): #取栈顶元素
assert not self.empty() #检测栈为空
return self.data[len(self.data)-1]
if __name__ == '__main__':
st=SqStack()
st.push(1)
st.push(2)
st.push(3)
st.push(4)
print("出栈顺序:",end=' ')
while not st.empty():
print(st.pop(),end=' ')
print()相关推荐
- 不用拉网线的路由器是真的吗
-
是真的不插卡不拉线有线就有网，这11个字其实就涵盖了无线路由器的特点，无线路由器免插卡、不用拉网线，完全摆脱了之前家用路由器和网线捆绑的模式，有电就有网，其实说的就是无线路由器的使用操作简单，通电就可...
- u盘检测软件下载（u盘测试软件）
-
1、u盘芯片检测工具(ChipEasy)可以查看USB设备PID、VID、SN、制造商、产品名等；2、查看USB设备主控芯片信息、闪存芯片信息、固件信息、电流控制3、SSD型号...
- 电脑现在什么系统最好（电脑现在用什么系统好）
-
WINXP好用，但过时了。VISTA不好用，没推开就夭折了。WIN8/8.1是针对触模屏设计的,如果你用的不是触摸屏平板电脑是普通电脑,使WIN8/8.1总觉着很蹩扭。新出的WIN10，功能...
- 账号怎么注册（steam账号怎么注册）
-
如果注册是qq账号【qq号码的申请办法】【1】双击qq登陆界面，在qq帐号填写空格的后面你可以看见：[申请帐号]；【2】点击[申请帐号]进入，就可以在网上免费申请号码了；【3】进入www.qq.com...
- tmp文件是什么意思（tmp文件有什么用）
-
在系统C:\Windows\Temp文件夹中，我们经常会发现一些后缀名为TMP的文件，在该文件夹中的这些文件其实都是临时文件。它们可能是系统被误关机，或者其他程序没有删除而生的。而且在该文件夹中还有其...
- 怎么给u盘格式化（怎么给u盘格式化成FAT32）
-
u盘插入电脑，等待桌面弹出u盘图标。打开“计算机”。左键选中u盘，单击右键，在弹出的菜单中，点击“格式化”。点击“开始”，点击“确定”即可。格式化u盘详细步骤1、找到U盘盘符，鼠标右键点击，弹出菜单中...
- harmonyos主题下载（harmonyos主题怎么换）
-
首先，打开荣耀手机的应用市场，在搜索框中输入“华为鸿蒙主题”，然后点击搜索。找到“华为鸿蒙主题”应用后，点击下载即可。下载完成后，打开“华为鸿蒙主题”应用，选择心仪的主题，点击下载并应用即可享受华为鸿...
- 戴尔笔记本电脑黑屏却开着机
-
对于电脑黑屏的处理基本上采用排除、替换相结合的方法，其原则应本着先替换排除可疑性最大的部件。对于普通电脑用户来讲，专业知识不足，可以按下列步骤分析故障原因，以便可以自己动手排除故障。首先检查接触是否良...
- 手机版电脑桌面下载（手机电脑桌面下载软件安装包）
-
只有电脑版手机助手软件，没有手机桌面这个软件在电脑上点击今日头条APP下载安装即可哦你好，陌陌电脑版如果说你想要下载到电脑桌面的话，你只需要长按把它添加到你的电脑桌面就可以了。要将软件下载到桌面并创建...
- ghost备份中文图解（ghost备份1837）
-
其实是这样的ghost文件备份后会生成两个文件一个是.GHO一个是.GHS文件FAT32格式的分区，单个文件最大只支持到2G(2048M),如果你的镜像>2G,这时的做的GHOST在一个文件里装...
- win10一键重装win7（win10一键重装系统）
-
1、首先准备一个4GB以上可以正常使用的U盘。2、在一个可以正常使用的电脑上，下载老毛桃软件并安装。3、去网上下载所需的win7，win10选择自己所需要的系统，并下载下来。4、插入u盘并打开老毛桃...
- 戴尔按f12还原系统步骤win10
-
基本上正常的话是f8，如果你希望他变成年，F12，你要打开设置去连，然后把这个快捷键的位置调一调戴尔的键盘f1到f12恢复原功能的方法：1、可能是操作者操作有误的原因，使键盘没有任何反应。2、根据复合...
-
- qq网页版官网（qq1网页版）
-
https://aq.qq.com/cn2/indexQQ安全中心是腾讯公司推出的QQ帐号保护软件，为广大QQ用户提供一站式的QQ安全服务，包括了密保管理、帐号保护、安全体检、修改密码、帐号申诉等功能，让账号更加安全可靠。为了全面保护QQ帐...
-
2025-11-18 15:03 off999
欢迎 你 发表评论:
- 一周热门
-
-
抖音上好看的小姐姐，Python给你都下载了
-
全网最简单易懂!495页Python漫画教程，高清PDF版免费下载
-
Python 3.14 的 UUIDv6/v7/v8 上新，别再用 uuid4 () 啦!
-
python入门到脱坑 输入与输出—str()函数
-
飞牛NAS部署TVGate Docker项目，实现内网一键转发、代理、jx
-
宝塔面板如何添加免费waf防火墙?（宝塔面板开启https）
-
Python三目运算基础与进阶_python三目运算符判断三个变量
-
(新版)Python 分布式爬虫与 JS 逆向进阶实战吾爱分享
-
慕ke 前端工程师2024「完整」
-
失业程序员复习python笔记——条件与循环
-
- 最近发表
- 标签列表
-
- python计时 (73)
- python安装路径 (56)
- python类型转换 (93)
- python进度条 (67)
- python吧 (67)
- python的for循环 (65)
- python格式化字符串 (61)
- python静态方法 (57)
- python列表切片 (59)
- python面向对象编程 (60)
- python 代码加密 (65)
- python串口编程 (77)
- python封装 (57)
- python写入txt (66)
- python读取文件夹下所有文件 (59)
- python操作mysql数据库 (66)
- python获取列表的长度 (64)
- python接口 (63)
- python调用函数 (57)
- python多态 (60)
- python匿名函数 (59)
- python打印九九乘法表 (65)
- python赋值 (62)
- python异常 (69)
- python元祖 (57)