第3章 线性表数据结构

第3章线性表3.2顺序存储Python提供列表实现顺序表的各种操作，进行判空，查找，插入，删除，打印等功能。#创建一个空的顺序表：my_list=[]#初始化列表my_list=list(map(int,input().split()))#比如3135#在顺序表末尾插入元素：data=int(input())#9my_list.append(data)#[3,1,3,5,9]print(my_list)#在指定位置插入元素：my_list.insert(1,15)#[3,15,1,3,5,9]print(my_list)#获取指定位置的元素：element=my_list[0]#3#修改指定位置的元素：my_list[2]=25#[3,15,25,3,5,9]print(my_list)#删除指定位置的元素：delmy_list[1]#[3,25,3,5,9]print(my_list)#获取顺序表的长度：length=len(my_list)#5#判断元素是否在顺序表中：is_present=25inmy_list#True#查找元素在顺序表中的索引：index=my_list.index(25)#1#清空顺序表：my_list.clear()#[]程序输入：31359输出：[3,1,3,5,9]#初始化的列表[3,15,1,3,5,9]#末尾添加9[3,15,25,3,5,9]#位置2修改为25[3,25,3,5,9]#删除位置1后的列表3.3链式存储classNode(object):"""节点类"""def__init__(self,elem):self.elem=elemself.next=None#初始设置下一节点为空classSingleLinkList(object):"""创建单链表"""def__init__(self,node=None):#使用一个默认参数，传入头结点接收；没有传入时，默认头结点为空self.__head=nodedefis_empty(self):'''链表是否为空'''returnself.__head==Nonedeflength(self):'''链表长度'''cur=self.__head#cur游标，用来移动遍历节点count=0#count记录数量whilecur!=None:count+=1cur=cur.nextreturncountdeftravel(self):'''遍历整个列表'''cur=self.__headwhilecur!=None:print(cur.elem,end='')cur=cur.nextprint("\n")defadd(self,item):'''链表头部添加元素'''node=Node(item)node.next=self.__headself.__head=nodedefappend(self,item):'''链表尾部添加元素'''node=Node(item)#由于特殊情况当链表为空时没有next，所以在前面要做个判断ifself.is_empty():self.__head=nodeelse:cur=self.__headwhilecur.next!=None:cur=cur.nextcur.next=nodedefinsert(self,pos,item):'''指定位置添加元素'''ifpos<=0:#如果pos位置在0，当做头插法self.add(item)elifpos>self.length()-1:#如果pos位置比原链表长，那么都当做尾插法来做self.append(item)else:per=self.__headcount=0whilecount<pos-1:count+=1per=per.next#当循环退出后，pre指向pos-1位置node=Node(item)node.next=per.nextper.next=nodedefremove(self,item):'''删除节点'''cur=self.__headpre=Nonewhilecur!=None:ifcur.elem==item:#先判断该节点是否是头结点ifcur==self.__head:self.__head=cur.nextelse:pre.next=cur.nextbreakelse:pre=curcur=cur.nextdefsearch(self,item):'''查找节点是否存在'''cur=self.__headwhilenotcur:ifcur.elem==item:returnTrueelse:cur=cur.nextreturnFalseif__name__=="__main__":ll=SingleLinkList()print(ll.is_empty())print(ll.length())ll.append(3)ll.add(999)ll.insert(-3,110)ll.insert(99,111)print(ll.is_empty())print(ll.length())()ll.remove(111)()【程序运行结果】True0False4110999311111099933.4双链表3.5实例——一元多项式的加法classNode:#单链表结点存储一元多项式非零项的系数，指数和下一个结点def__init__(self,coefficient,exponent):self.coefficient=coefficientself.exponent=exponentself.next=NoneclassPolynomial:#一元多项式的类定义def__init__(self):#初始化空链表self.head=Nonedefis_empty(self):returnself.headisNonedefinsert_term(self,coefficient,exponent):new_node=Node(coefficient,exponent)ifself.is_empty()orexponent>self.head.exponent:new_node.next=self.headself.head=new_nodeelse:current=self.headprev=Nonewhilecurrentandexponent<current.exponent:prev=currentcurrent=current.nextifcurrentandexponent==current.exponent:current.coefficient+=coefficientifcurrent.coefficient==0:ifprev:prev.next=current.nextelse:self.head=current.nextelse:ifprevisNone:new_node.next=self.headself.head=new_nodeelse:new_node.next=currentprev.next=new_nodedefadd(self,p2):result=Polynomial()current1=self.headcurrent2=p2.headwhilecurrent1andcurrent2:ifcurrent1.exponent>current2.exponent:result.insert_term(current1.coefficient,current1.exponent)current1=current1.nextelifcurrent1.exponent<current2.exponent:result.insert_term(current2.coefficient,current2.exponent)current2=current2.nextelse:sum_coefficient=current1.coefficient+current2.coefficientifsum_coefficient!=0:result.insert_term(sum_coefficient,current1.exponent)current1=current1.nextcurrent2=current2.nextwhilecurrent1:#下面的2个循环最多有一个会被执行result.insert_term(current1.coefficient,current1.exponent)current1=current1.nextwhilecurrent2:result.insert_term(current2.coefficient,current2.exponent)current2=current2.nextreturnresultdefdisplay(self):current=self.headwhilecurrent:coefficient=current.coefficientexponent=current.exponentifexponent==0:term="+"+str(coefficient)elifexponent==1:term=f"{coefficient}x"else:term=f"{coefficient}x^{exponent}"print(term,end="")current=current.nextprint()#测试示例p1=Polynomial()p1.insert_term(3,3)p1.insert_term(-2,2)p1.insert_term(1,0)p2=Polynomial()p2.insert_term(3,3)p2.insert_term(-2,2)p2.insert_term(5,1)print("Polynomial1:")p1.display()print("Polynomial2:")p2.display()p3=p1.add(p2)print("Resultofaddition:")p3.display()【程序运行结果】Polynomial1:3x^3-2x^2+1Polynomial2:3x^3-2x^25xResultofaddition:6x^3-4x^25x+13.6实例——舞蹈链classNode:#舞蹈链的结点def__init__(self,value):self.value=value#结点的值self.up=None#上方相邻结点self.down=None#下方相邻结点self.left=None#左侧相邻结点self.right=None#右侧相邻结点self.column=None#列结点classCrossList:#舞蹈链def__init__(self):self.head=Node(None)#头结点，不存储具体值self.columns=[]#列结点列表#二维矩阵matrix初始化十字链表definit(self,matrix):#创建列结点col_count=len(matrix[0])foriinrange(col_count):col_node=Node(i)col_node.left=self.headifi==0elseself.columns[-1]col_node.left.right=col_nodeself.columns.append(col_node)#构建行结点forrowinmatrix:row_head=None#当前行的头结点prev_node=None#前一个结点forj,valueinenumerate(row):ifvalue==1:#创建新的结点node=Node(j)node.column=self.columns[j]node.column.up=node.columnifnotnode.column.upelsenode.column.upnode.column.up.down=nodeifnotrow_head:row_head=node#插入到行链表中ifprev_node:prev_node.right=nodenode.left=prev_nodeprev_node=node#连接行链表首尾ifrow_head:row_head.left=prev_nodeprev_node.right=row_head#删除指定行结点defremove_row(self,row_index):#找到指定行结点的起始结点start_node=self.head.rightwhilestart_node.value!=row_index:start_node=start_node.right#迭代删除对应列结点的链接关系node=start_nodewhilenode:#断开行链表的链接关系node.left.right=node.rightnode.right.left=node.left#断开列链表的链接关系col_node=node.upwhilecol_node!=node:col_node.down.up=col_node.upcol_node.up.down=col_node.downcol_node=col_node.upnode=node.right3.7实例——最大子序列和defget_max_data(data):#全部都是负数，则最大和是最大负数max_data=data[0]fordindata[1:]:ifmax_data<d:max_data=dreturnmax_datadefget_max_sum(data):max_sum=get_max_data(data)ifmax_sum<0:#最大值是负数，则全部都是负数returnmax_sumthis_sum=0max_sum=0fordindata:this_sum+=d;ifmax_sum<this_sum:max_sum=this_sumifthis_sum<0:this_sum=0returnmax_sumdata=list(map(int,input().split()))max_sum=get_max_sum(data)print(max_sum)【程序运行结果】6-23-83-1273.8实例——链表合并classListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmergeTwoLists(list1,list2):#创建一个虚拟头结点，方便后续操作dummy=ListNode()current=dummy#遍历两个链表，直到其中一个链表为空whilelist1andlist2:iflist1.val<list2.val:current.next=list1list1=list1.nextelse:current.next=list2list2=list2.nextcurrent=current.next#如果list1不为空，直接连接到新链表末尾iflist1:current.next=list1#如果list2不为空，直接连接到新链表末尾eliflist2:current.next=list2#返回新链表的头结点（虚拟头结点的下一个结点）returndummy.next#创建链表1->3->5list1=ListNode(1)list1.next=ListNode(3)lis