文章目录 线性表的插入 线性表的删除 单链表的建立 栈的顺序存储 队列的顺序存储 串的顺序存储 树的存储 二叉树遍历 二分法插入排序 利用普里姆算法构造最小生成树
线性表的插入
def insert ( a, pos, key, n) : i = n - 1 while i >= pos: a[ i + 1 ] = a[ i] i -= 1 a[ pos] = keyreturn 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] = numprint ( "插入前列表为:" ) print ( a[ : n] ) pos = int ( input ( "请输入要插入的位置:" ) ) key = int ( input ( "请输入要插入的数据:" ) ) listlen = insert( a, pos, key, n) print ( "插入后列表为" ) print ( a[ : listlen] )
线性表的删除
def dellist ( a, pos, n) : i = poswhile 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] = 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 = 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 = 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. next q. 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. 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 = sizesize. 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 = selfself. 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 xif __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. 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 : break else : 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 = None val. pop( 0 ) return Rootdef 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 = 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 = None val. pop( 0 ) return Rootdef 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 = 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 = None val. pop( 0 ) return Rootdef 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 ] n= len ( r) 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)