python环形单链表的约瑟夫问题详解
题目：
一个环形单链表，从头结点开始向后，指针每移动一个结点，就计数加1，当数到第m个节点时，就把该结点删除，然后继续从下一个节点开始从1计数，循环往复，直到环形单链表中只剩下了一个结点，返回该结点。
这个问题就是著名的约瑟夫问题。
代码：
首先给出环形单链表的数据结构：
classNode(object): def__init__(self,value,next=0): self.value=value self.next=next#指针 classRingLinkedList(object): #链表的数据结构 def__init__(self): self.head=0#头部 def__getitem__(self,key): ifself.is_empty(): print'Linkedlistisempty.' return elifkey<0orkey>self.get_length(): print'Thegivenkeyiswrong.' return else: returnself.get_elem(key) def__setitem__(self,key,value): ifself.is_empty(): print'Linkedlistisempty.' return elifkey<0orkey>self.get_length(): print'Thegivenkeyiswrong.' return else: returnself.set_elem(key,value) definit_list(self,data):#按列表给出data self.head=Node(data[0]) p=self.head#指针指向头结点 foriindata[1:]: p.next=Node(i)#确定指针指向下一个结点 p=p.next#指针滑动向下一个位置 p.next=self.head defget_length(self): p,length=self.head,0 whilep!=0: length+=1 p=p.next ifp==self.head: break returnlength defis_empty(self): ifself.head==0: returnTrue else: returnFalse definsert_node(self,index,value): length=self.get_length() ifindex<0orindex>length: print'Cannotinsertnodeintothelinkedlist.' elifindex==0: temp=self.head self.head=Node(value,temp) p=self.head for_inxrange(0,length): p=p.next print"p.value",p.value p.next=self.head elifindex==length: elem=self.get_elem(length-1) elem.next=Node(value) elem.next.next=self.head else: p,post=self.head,self.head foriinxrange(index): post=p p=p.next temp=p post.next=Node(value,temp) defdelete_node(self,index): ifindex<0orindex>self.get_length()-1: print"Wrongindexnumbertodeleteanynode." elifself.is_empty(): print"Nonodecanbedeleted." elifindex==0: tail=self.get_elem(self.get_length()-1) temp=self.head self.head=temp.next tail.next=self.head elifindex==self.get_length()-1: p=self.head foriinxrange(self.get_length()-2): p=p.next p.next=self.head else: p=self.head foriinxrange(index-1): p=p.next p.next=p.next.next defshow_linked_list(self):#打印链表中的所有元素 ifself.is_empty(): print'Thisisanemptylinkedlist.' else: p,container=self.head,[] for_inxrange(self.get_length()-1):# container.append(p.value) p=p.next container.append(p.value) printcontainer defclear_linked_list(self):#将链表置空 p=self.head for_inxrange(0,self.get_length()-1): post=p p=p.next delpost self.head=0 defget_elem(self,index): ifself.is_empty(): print"Thelinkedlistisempty.Cannotgetelement." elifindex<0orindex>self.get_length()-1: print"Wrongindexnumbertogetanyelement." else: p=self.head for_inxrange(index): p=p.next returnp defset_elem(self,index,value): ifself.is_empty(): print"Thelinkedlistisempty.Cannotsetelement." elifindex<0orindex>self.get_length()-1: print"Wrongindexnumbertosetelement." else: p=self.head for_inxrange(index): p=p.next p.value=value defget_index(self,value): p=self.head foriinxrange(self.get_length()): ifp.value==value: returni else: p=p.next return-1
然后给出约瑟夫算法：
defjosephus_kill_1(head,m): ''' 环形单链表，使用RingLinkedList数据结构，约瑟夫问题。 :paramhead:给定一个环形单链表的头结点，和第m个节点被杀死 :return:返回最终剩下的那个结点 本方法比较笨拙，就是按照规定的路子进行寻找，时间复杂度为o(m*len(ringlinkedlist)) ''' ifhead==0: print"Thisisanemptyringlinkedlist." returnhead ifm<2: print"Wrongmnumbertoplaythisgame." returnhead p=head whilep.next!=p: for_inxrange(0,m-1): post=p p=p.next #printpost.next.value post.next=post.next.next p=post.next returnp
分析：
我采用了最原始的方法来解决这个问题，时间复杂度为o(m*len(ringlinkedlist))。
但是实际上，如果确定了链表的长度以及要删除的步长，那么最终剩余的结点一定是固定的，所以这就是一个固定的函数，我们只需要根剧M和N确定索引就可以了，这个函数涉及到了数论，具体我就不细写了。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。