数据结构代码

线性表的插入

#a: 列表，pos: 要插入的位置，key: 要插入的数据，n: 列表中已有数据长度
def insert(a, pos, key, n):i = n - 1while i >= pos:a[i + 1] = a[i]i -= 1a[pos] = keyreturn n + 1if __name__ == '__main__':a = [None] * 10n = int(input("请输入有效数据个数n："))for i in range(0, n):print(f"请输入第{i + 1}数据给列表a：", end=' ')num = int(input())a[i] = numprint("插入前列表为:")print(a[:n])pos = int(input("请输入要插入的位置："))key = int(input("请输入要插入的数据："))listlen = insert(a, pos, key, n)print("插入后列表为")print(a[:listlen])

线性表的删除

#a: 列表，pos: 要删除的位置，n: 列表中已有数据长度
def dellist(a, pos, n):i = poswhile i < n - 1:a[i] = a[i + 1]i += 1return n - 1if __name__ == '__main__':a = [None] * 10n = int(input("请输入有效数据个数n："))for i in range(0, n):print(f"请输入第{i + 1}数据给列表a：", end=' ')num = int(input())a[i] = numprint("插入前列表为:")print(a[:n])pos = int(input("请输入要删除的位置："))listlen = dellist(a, pos, n)print("删除后列表为")print(a[:listlen])

单链表的建立

#建立数据节点类
class Node(object):def __init__(self, data):self.data = self.dataself.next = None#创建单链表类
class SLinkList:def __init__(self):self.head = Noneself.length = 0#判断是否为空def is_empty(self):if self.head == None:return Truereturn False在链表头部插入数据def add(self, p):if self.is_empty():self.head = pp.next = self.headself.head = pself.length += 1#在链表尾部插入数据def appendnode(self, p):q = self.headif self.is_empty():self.add(p)else:while (q.next != None):q = q.nextq.next = pself.length += 1#输出链表当前链接节点数据的状态def travel(self):q = self.headif self.length == 0:print("目前链表没有数据！")else:print("目前链表里面的元素有：", end=' ')for i in range(self.length):print("%s->" % q.data, end=' ')q = q.nextprint("\n")def main():s = SLinkList()print("""0、结束所有操作1、从尾部插入数据建立单链表2、从头部插入数据建立单链表""")while True:number = eval(input("请输入0、1、2进行下一步操作："))if number == 1:print("目前链表状态")s.travel()print("正在尾部插入数据:")p = Node(eval(input("请输入要插入的数据")))s.appendnode(p)print("操作后的链表状态")s.travel()elif number == 2:print("目前链表状态")s.travel()print("正在头部插入数据:")q = Node(eval(input("请输入要插入的数据")))s.add(q)print("操作后的链表状态")s.travel()elif number == 0:breakif __name__ == "__main__":main()

栈的顺序存储

class Stack(object):def __init__(self, size):size.MAX = sizesize.s = []self.top = 0def stackEmpty(self):if self.top == 0:return Truereturn Falsedef pop(self):if self.stackEmpty():print("栈已为空，不能执行出栈操作")else:self.top = self.top - 1return self.s.pop()if __name__ == "__main__":s = Stack(50)s.s = [1, 2, 3, 4, 5]s.top = 5while True:print("请选择操作方式")print("1、出栈0、退出")number = int(input())if number == 1:print(s.pop())else:break

队列的顺序存储

class Quene(object):def __init__(self, size):self.MAX = selfself.q = []self.front = -1self.rear = -1def isEmpty(self):if self.rear == self.front:return Truereturn Falsedef delquene(self):if self.isEmpty():print("队列已经空，不能执行出队操作")x = - 9999else:self.front = self.front + 1x = self.q[self.front]return xif __name__ == "__main__":q = Quene(50)q.q = [1, 2, 3, 4, 5]q.rear = 4q.front = -1while True:print("请选择操作方式")print("1、出队0、退出")number = int(input())if number == 1:x = q.delquene()if x != -9999:print(f"出队元素放入{x}")print("出队后队列元素为")for i in range(q.front + 1, len(q.q)):print(q.q[i], end=' ')else:break

串的顺序存储

class sqstring(object):def __init__(self,obj=None):if objis None:# 构造空串self.strvalue=[] # 字符数组存放串值self.curLen =0 # 当就串的长度elif isinstance(obj,str): # 以字符串构造串self.curLen =len(obj)self.strValue=[None]* self.curLenfor i in range(self.curlen):self.strvaluelil = obj[i]elif isinstance(obj,list): # 以字符列表梅造串self.curLen =len(obj)self.strValue =[None]* self.curLenfor i in range(self.curlen):self.strValue[i]= obj[i]def length(self):'''返回串的长度'''return self.curLendef display(self):'''打印字符串'''for i in range(self.curten):print(self.strValue[il, end='')
if __name__ ='__main__':string=input(”请输入字符串给变量string:")s=sqstring(string)while True;print("----请选择操作方式---")print("----1.打印字符串的长度并输出字符串\n----0.退出")number=int(input())if number==1:print(s.length())s.display()if number==0:break

树的存储

class Node:def __init__(self, data, parent):self.data = dataself.parent = parentclass Tree:def __init__(self):self._array = []def addNode(self, data, parent):node = Node(data, parent)self._array.append(node)def show(self):for i, v in enumerate(self._array):print('节点下标为 = {} 值为 = {} 父节点下标为{}'.format(i,v.data,v.parent))def findParent(self, node):return self._array[node.parent]if __name__ == "__main__":print("------1.建立双亲表示树------\n----2.显示建立结结果-----\n")print("------3.输入节点求双亲节点-----\n-----4.退出-----\n")tree = Tree()while True:number = int(input("请输入选择（1-4）"))if number == 1:print("请输入节点data以及双亲parent所在的下标")data = input()parent = int(input())if data != "#":tree.addNode(data.strip(), parent)else:print("数据输入结束，请选择其他选项")elif number == 2:tree.show()elif number == 3:print("请输入某一节点的数据值data，及双亲节点的下标parent求双亲节点")data = input();parent = int(input())node = Node(data, parent)node_parent = tree.findParent(node)print('父节点为={}'.format(node_parent.data))elif number == 4:breakelse:print("输入错误请重新输入数字（1-4）\n")

二叉树遍历

前序遍历

class TreeNode:def __init__(self, val, lchild=None, rchild=None):self.val = valself.lchild = lchildself.rchild = rchilddef CreateTree(Root, val):if len(val) == 0:return Rootif val[0] != '#':Root = TreeNode(val[0])val.pop(0)Root.lchild = CreateTree(Root.lchild, val)Root.rchild = CreateTree(Root.rchild, val)return Rootelse:Root = Noneval.pop(0)return Rootdef perOrderTraversal(root):if root is None:returnprint(root.val, end=' ')perOrderTraversal(root.lchild)if __name__ == '__main__':Root = Nonestrs = "-*a##b##c##"varls = list(strs)print("程序构建的前序序列：\n%s\n构建的二叉树,\n" % varls)Root = CreateTree(Root, varls)print("二叉树的前序遍历结果为：\n")perOrderTraversal(Root)

中序遍历

class TreeNode:def __init__(self, val, lchild=None, rchild=None):self.val = valself.lchild = lchildself.rchild = rchilddef CreateTree(Root, val):if len(val) == 0:return Rootif val[0] != '#':Root = TreeNode(val[0])val.pop(0)Root.lchild = CreateTree(Root.lchild, val)Root.rchild = CreateTree(Root.rchild, val)return Rootelse:Root = Noneval.pop(0)return Rootdef inOrderTraversal(root):if root is None:returninOrderTraversal(root.lchild)print(root.val, end=' ')if __name__ == '__main__':Root = Nonestrs = "-*a##b##c##"varls = list(strs)print("程序构建的前序序列：\n%s\n构建的二叉树,\n" % varls)Root = CreateTree(Root, varls)print("二叉树的中序遍历结果为：\n")inOrderTraversal(Root)

后序遍历

class TreeNode:def __init__(self, val, lchild=None, rchild=None):self.val = valself.lchild = lchildself.rchild = rchilddef CreateTree(Root, val):if len(val) == 0:return Rootif val[0] != '#':Root = TreeNode(val[0])val.pop(0)Root.lchild = CreateTree(Root.lchild, val)Root.rchild = CreateTree(Root.rchild, val)return Rootelse:Root = Noneval.pop(0)return Rootdef postOrderTraversal(root):if root is None:returnpostOrderTraversal(root.lchild)postOrderTraversal(root.rchild)if __name__ == '__main__':Root = Nonestrs = "-*a##b##c##"varls = list(strs)print("程序构建的前序序列：\n%s\n构建的二叉树,\n" % varls)Root = CreateTree(Root, varls)print("二叉树的后序遍历结果为：\n")postOrderTraversal(Root)

二分法插入排序

def insertion sort binarysearch(r):for i in range(2,len(r)):r[0]=r[i]low=1high=i-1while low<=high:m=(low+high)//2if r[e]<r[m]:high=m-1else:low=m+1for j in range(i-1,low-1,-1):r[j+1]=r[j]r[low]=r[0]return r
if __name__ =='__main__':r=[0,42,36,56,56,78,67,11,27,38]#定义列表并赋初值，其中r[0]的元素值无意义n=len(r)#输出时r[0]无意义所以不输出for i in range(1,n):print(r[i],end="")

利用普里姆算法构造最小生成树

class MGraph(object):def __init__(self, vertex):self.vertex = vertex # 表示图的节点个数self.data = vertex * [0] # 存放节点数据# 用邻接矩阵存放边上的权值self.weight = [[0 for row in range(vertex)] for col in range(vertex)]
# 创建最小生成树
class MinTree(object):# 创建图的邻接矩阵def create_graph(graph, vertex, data, weight):"""graph:图对象vertex:图对应的顶点个数data:存放图的各个顶点值的列表weight:存放图的邻接矩阵"""for i in range(vertex): # 顶点graph.data[i] = data[i]for j in range(vertex):graph.weight[i][j] = weight[i][j]#显示图的方法def show_graph(graph):for link in graph.weight:print(link)