数据结构代码

线性表的插入

#a: 列表，pos: 要插入的位置，key: 要插入的数据，n: 列表中已有数据长度
def insert(a, pos, key, n):
    i = n - 1
    while i >= pos:
        a[i + 1] = a[i]
        i -= 1
    a[pos] = key
    return n + 1


if __name__ == '__main__':
    a = [None] * 10
    n = int(input("请输入有效数据个数n："))
    for i in range(0, n):
        print(f"请输入第{i + 1}数据给列表a：", end=' ')
        num = int(input())
        a[i] = num
    print("插入前列表为:")
    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 = pos
    while i < n - 1:
        a[i] = a[i + 1]
        i += 1
    return n - 1


if __name__ == '__main__':
    a = [None] * 10
    n = int(input("请输入有效数据个数n："))
    for i in range(0, n):
        print(f"请输入第{i + 1}数据给列表a：", end=' ')
        num = int(input())
        a[i] = num
    print("插入前列表为:")
    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.data
        self.next = None

#创建单链表类
class SLinkList:
    def __init__(self):
        self.head = None
        self.length = 0
	
    #判断是否为空
    def is_empty(self):
        if self.head == None:
            return True
        return False
	
    在链表头部插入数据
    def add(self, p):
        if self.is_empty():
            self.head = p
        p.next = self.head
        self.head = p

        self.length += 1
	
    #在链表尾部插入数据
    def appendnode(self, p):
        q = self.head
        if self.is_empty():
            self.add(p)
        else:
            while (q.next != None):
                q = q.next
            q.next = p
            self.length += 1
            
	#输出链表当前链接节点数据的状态
    def travel(self):
        q = self.head
        if self.length == 0:
            print("目前链表没有数据！")
        else:
            print("目前链表里面的元素有：", end=' ')
            for i in range(self.length):
                print("%s->" % q.data, end=' ')
                q = q.next
            print("\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:
            break


if __name__ == "__main__":
    main()

栈的顺序存储

class Stack(object):
    def __init__(self, size):
        size.MAX = size
        size.s = []
        self.top = 0

    def stackEmpty(self):
        if self.top == 0:
            return True
        return False

    def pop(self):
        if self.stackEmpty():
            print("栈已为空，不能执行出栈操作")
        else:
            self.top = self.top - 1
            return self.s.pop()


if __name__ == "__main__":
    s = Stack(50)
    s.s = [1, 2, 3, 4, 5]
    s.top = 5
    while 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 = self
        self.q = []
        self.front = -1
        self.rear = -1

    def isEmpty(self):
        if self.rear == self.front:
            return True
        return False

    def delquene(self):
        if self.isEmpty():
            print("队列已经空，不能执行出队操作")
            x = - 9999
        else:
            self.front = self.front + 1
            x = self.q[self.front]
        return x


if __name__ == "__main__":
    q = Quene(50)
    q.q = [1, 2, 3, 4, 5]
    q.rear = 4
    q.front = -1
    while 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.curLen
        	for i in range(self.curlen):
                self.strvaluelil = obj[i]
            elif isinstance(obj,list): # 以字符列表梅造串
                self.curLen =len(obj)
                self.strValue =[None]* self.curLen
                for i in range(self.curlen):
                    self.strValue[i]= obj[i]
	def length(self):
        '''返回串的长度'''
		return self.curLen
    def 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 = data
        self.parent = parent


class 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:
            break
        else:
            print("输入错误请重新输入数字（1-4）\n")

二叉树遍历

前序遍历

class TreeNode:
    def __init__(self, val, lchild=None, rchild=None):
        self.val = val
        self.lchild = lchild
        self.rchild = rchild


def CreateTree(Root, val):
    if len(val) == 0:
        return Root
    if val[0] != '#':
        Root = TreeNode(val[0])
        val.pop(0)
        Root.lchild = CreateTree(Root.lchild, val)
        Root.rchild = CreateTree(Root.rchild, val)
        return Root
    else:
        Root = None
        val.pop(0)
        return Root


def perOrderTraversal(root):
    if root is None:
        return
    print(root.val, end=' ')
    perOrderTraversal(root.lchild)


if __name__ == '__main__':
    Root = None
    strs = "-*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 = val
        self.lchild = lchild
        self.rchild = rchild


def CreateTree(Root, val):
    if len(val) == 0:
        return Root
    if val[0] != '#':
        Root = TreeNode(val[0])
        val.pop(0)
        Root.lchild = CreateTree(Root.lchild, val)
        Root.rchild = CreateTree(Root.rchild, val)
        return Root
    else:
        Root = None
        val.pop(0)
        return Root


def inOrderTraversal(root):
    if root is None:
        return
    inOrderTraversal(root.lchild)
    print(root.val, end=' ')


if __name__ == '__main__':
    Root = None
    strs = "-*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 = val
        self.lchild = lchild
        self.rchild = rchild


def CreateTree(Root, val):
    if len(val) == 0:
        return Root
    if val[0] != '#':
        Root = TreeNode(val[0])
        val.pop(0)
        Root.lchild = CreateTree(Root.lchild, val)
        Root.rchild = CreateTree(Root.rchild, val)
        return Root
    else:
        Root = None
        val.pop(0)
        return Root


def postOrderTraversal(root):
    if root is None:
        return
    postOrderTraversal(root.lchild)
    postOrderTraversal(root.rchild)


if __name__ == '__main__':
    Root = None
    strs = "-*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=1
		high=i-1
		while low<=high:
			m=(low+high)//2
			if r[e]<r[m]:
				high=m-1
			else:
				low=m+1
		for 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)