题目:
一个环形单链表,从头结点开始向后,指针每移动一个结点,就计数加1,当数到第m个节点时,就把该结点删除,然后继续从下一个节点开始从1计数,循环往复,直到环形单链表中只剩下了一个结点,返回该结点。
这个问题就是著名的约瑟夫问题。
代码:
首先给出环形单链表的数据结构:
class Node(object): def __init__(self, value, next=0): self.value = value self.next = next # 指针 class RingLinkedList(object): # 链表的数据结构 def __init__(self): self.head = 0 # 头部 def __getitem__(self, key): if self.is_empty(): print 'Linked list is empty.' return elif key < 0 or key > self.get_length(): print 'The given key is wrong.' return else: return self.get_elem(key) def __setitem__(self, key, value): if self.is_empty(): print 'Linked list is empty.' return elif key < 0 or key > self.get_length(): print 'The given key is wrong.' return else: return self.set_elem(key, value) def init_list(self, data): # 按列表给出 data self.head = Node(data[0]) p = self.head # 指针指向头结点 for i in data[1:]: p.next = Node(i) # 确定指针指向下一个结点 p = p.next # 指针滑动向下一个位置 p.next = self.head def get_length(self): p, length = self.head, 0 while p != 0: length += 1 p = p.next if p == self.head: break return length def is_empty(self): if self.head == 0: return True else: return False def insert_node(self, index, value): length = self.get_length() if index < 0 or index > length: print 'Can not insert node into the linked list.' elif index == 0: temp = self.head self.head = Node(value, temp) p = self.head for _ in xrange(0, length): p = p.next print "p.value", p.value p.next = self.head elif index == length: elem = self.get_elem(length-1) elem.next = Node(value) elem.next.next = self.head else: p, post = self.head, self.head for i in xrange(index): post = p p = p.next temp = p post.next = Node(value, temp) def delete_node(self, index): if index < 0 or index > self.get_length()-1: print "Wrong index number to delete any node." elif self.is_empty(): print "No node can be deleted." elif index == 0: tail = self.get_elem(self.get_length()-1) temp = self.head self.head = temp.next tail.next = self.head elif index == self.get_length()-1: p = self.head for i in xrange(self.get_length()-2): p = p.next p.next = self.head else: p = self.head for i in xrange(index-1): p = p.next p.next = p.next.next def show_linked_list(self): # 打印链表中的所有元素 if self.is_empty(): print 'This is an empty linked list.' else: p, container = self.head, [] for _ in xrange(self.get_length()-1): # container.append(p.value) p = p.next container.append(p.value) print container def clear_linked_list(self): # 将链表置空 p = self.head for _ in xrange(0, self.get_length()-1): post = p p = p.next del post self.head = 0 def get_elem(self, index): if self.is_empty(): print "The linked list is empty. Can not get element." elif index < 0 or index > self.get_length()-1: print "Wrong index number to get any element." else: p = self.head for _ in xrange(index): p = p.next return p def set_elem(self, index, value): if self.is_empty(): print "The linked list is empty. Can not set element." elif index < 0 or index > self.get_length()-1: print "Wrong index number to set element." else: p = self.head for _ in xrange(index): p = p.next p.value = value def get_index(self, value): p = self.head for i in xrange(self.get_length()): if p.value == value: return i else: p = p.next return -1
然后给出约瑟夫算法:
def josephus_kill_1(head, m): ''' 环形单链表,使用 RingLinkedList 数据结构,约瑟夫问题。 :param head:给定一个环形单链表的头结点,和第m个节点被杀死 :return:返回最终剩下的那个结点 本方法比较笨拙,就是按照规定的路子进行寻找,时间复杂度为o(m*len(ringlinkedlist)) ''' if head == 0: print "This is an empty ring linked list." return head if m < 2: print "Wrong m number to play this game." return head p = head while p.next != p: for _ in xrange(0, m-1): post = p p = p.next #print post.next.value post.next = post.next.next p = post.next return p
分析:
我采用了最原始的方法来解决这个问题,时间复杂度为o(m*len(ringlinkedlist))。
但是实际上,如果确定了链表的长度以及要删除的步长,那么最终剩余的结点一定是固定的,所以这就是一个固定的函数,我们只需要根剧M和N确定索引就可以了,这个函数涉及到了数论,具体我就不细写了。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
华山资源网 Design By www.eoogi.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
华山资源网 Design By www.eoogi.com
暂无评论...
更新日志
2024年09月23日
2024年09月23日
- 周冰倩1995《沧桑情歌》JVC日本录制[WAV+CUE]
- 辛禄乐队.2024-热烈的少年【星辰】【FLAC分轨】
- 成龙.1996-龙的心【滚石】【WAV+CUE】
- 童安格.1991-一世情缘【宝丽金】【WAV+CUE】
- 韩红2010-擦肩而过[央金玛][WAV+CUE]
- RiccardoTesi-UnballoLiscio,Vol.II(2024)[24-48]FLAC
- 金池VS刘罡2009《双声情》[WAV+CUE]
- 冯奥迪《卄》[320K/MP3][67.08MB]
- 冯奥迪《卄》[FLAC/分轨][172.46MB]
- Merryland《Merryland》[320K/MP3][69.48MB]
- 苏芮.1991-停在我心里的温柔【福茂】【WAV+CUE】
- 苏慧伦.2020-面面Every.Side.of.Me【相信音乐】【WAV+CUE】
- 群星.1991-不一样的感觉REMIX【宝丽金】【WAV+CUE】
- 银霞.1983-《你那好冷的小手》珍藏纪念版[WAV分轨]
- 银霞.2002-《国语巨星专辑VOL.3》2CD台湾版[WAV+CUE]