阅读裘宗燕老师的《数据结构与算法:python语言描述》的课件所记笔记

6.循环单链表

  • 最后结点的next指向首结点
  • 该设计在结构上有致命的缺点
    • 首端加入删除不能在O(1)时间内完成,因为要修改尾结点的next
    • 让表对象指向概念上的尾结点更有利,可支持O(1)的首端加入删除,以及O(1)的尾端加入
  • 操作实现的关键是加入、删除后表对象域的正确更新
    • 把问题想清楚,实现并不困难
    • 非变动操作也许修改
a.程序实现
class LCList(object):
    def __init__(self):
        self.rear = None

    def isEmpty(self):
        return self.rear is None

    def prepend(self, elm): #首端加入
        if self.rear is None:
            self.rear = LNode(elm, None)
            self.rear.next = self.rear
        else:
            p = self.rear.next
            self.rear.next = LNode(elm, p)

    def append(self, elm): #尾端加入
        #p = LNode(elm, None)
        #p.next = self.rear.next
        #self.rear.next = p
        #self.rear = p
        prepend(self, elm)
        self.rear = self.rear.next

    def pop(self): # 首端弹出
        if self.rear is None:
            raise ValueError
        p = self.rear.next
        e = p.elem
        if self.rear = self.rear.next:
            self.rear = None
        else:
            self.rear.next = p.next
        return e

    def poplast(self): # 尾端弹出
        if self.rear is None:
            raise ValueError
        p = self.rear.next
        e = self.rear.elem
        if self.rear = self.rear.next:
            self.rear = None
        else:
            while p is not self.rear:
                pre = p
                p = p.next
            pre.next = p
            self.rear = pre
        return e

    def prinall(self):
        if self.rear is None:
            raise ValueError
        p = self.rear.next
        while True:
            print(p.elem)
            if p is self.rear:
                break
            p = p.next

7.双向链接表

  • 从任一结点出发,可以直接找到前后的相邻结点
  • 每个结点需要增加一个前向引用域,指向前一结点
  • 支持首尾端高效操作
  • 定义一个新结点类
a.程序实现
class LDNode(LNode):
    def __init__(self, pre, elm, nxt):
        LNode.__init__(self, elm, nxt)
        self.prev = pre
  • 双向链表实现,带尾结点

    class LDList(LList1):
    def __init__(self):
        LList.__init__(self)
    
    def prepend(self, elm):
        p = self.head
        self.head = LDNode(None, elm, p)
        if self.rear is None:
            self.rear = self.head
        else:
            p.prev = self.head
    
    def append(self, elm):
        p = self.rear
        self.rear = LDNode(p, elm, None)
        if self.head is None:
            self.head = self.rear
        else:
            p.next = self.rear
    
    def pop(self):
        if self.head is None:
            raise ValueError
        e = self.head.elem
        self.head = self.head.next
        if self.head is None:
            self.rear = None
        else:
            self.head.prev = None
        return e
    
    def poplast(self):
        if self.rear is None:
            return ValueError
        e = self.rear.elem
        self.rear = self.rear.prev
        if self.rear is None:
            self.head = None:
        else:
            self.rear.next = None
        return e

8.表元素反转

  • 表元素反转,要求修改被操作的表,其中元素按原顺序反转
  • 表元素排序,要求修改被操作的表,其中表元素按<排好顺序
  • 表元素反转,算法通常用两个下标,逐对交换元素位置
    • 在双链表上很容易实现
    • 单链表由于不支持从后向前找结点,只能每次从头开始找,需要$O(n^2)$时间
  • 对顺序表,只能搬动表中元素;对链接表,即可通过搬动结点元素,也可通过修改链接关系
    • 在单链表通过搬动元素实现反转,不方便,效率低
    • 考虑基于修改链接的方式
a.表元素反转实现
def rev(self):
    p = None
    while self.head is not None:
        q = self.head
        self.head = self.head.next
        q.next = p
        p = q
    self.head = p

9.表元素排序

  • 先看一个对list中元素的排序,使用插入排序算法
    def listSort(lst):
    for i in range(1, len(lst)):
        p = lst[i]
        x = i
        while x > 0 and lst[x-1] > p:
            list[x] = lst[x-1]
             x -= 1
        lst[x] = p
a.单链表排序,移动元素实现
def sortll(self):
    if self.head is None:
        return
    p = self.head.next
    while p is not None:
        h = self.head
        m = p.elem
        while h is not p:
            if h.elem <= m:
                pass
            else:
                x = h.elem
                h.elem = m
                m = x
            h = h.next
        p.elem = m
        p = p.next
b.单链表,调整链接实现
def sort(self):
    if self.head is None:
        return
    n = self.head
    p = n.next
    while p is not None:
        j = None
        h = self.head
        m = p.elem
        while h is not p and h.elem <= m:
            j = h; h = j.next
        if h is p:
            n = p # 不用修改链接,n和p都定位到相应的下一结点
        else: # 需要修改链接,将p取出插入到对应位置,新p的前一结点依然是n,因此不用修改n
            p.next = h
            n.next = p.next
            if j is None:
                self.head = p
            else:
                j.next = p
        p = n.next

五、应用实例

1.Josephus问题

  • 问题:设有n个人围坐一圈,现在从第k个人开始报数,报到第m的人退出。然后继续报数,直至所有人退出。输出出列人顺序编号
a.基于python list和固定大小‘数组’
  • 建立一个包含n个人的list编号
  • 找到第k个人,开始报数。处理过程中,通过把相应元素修改为0表示人已不在位
  • 反复做:
    • 数m个人
    • 把表示第m个人的元素值修改为0
    • 数到list最后元素之后转到下标为0的元素继续
      
      def josephus(n, k, m):
      people = list(range(1, n+1))
      i = k-1
      for num in range(n):
      count = 0
      while n < m:
          if people[i] > 0:
              count += 1
          if count == m:
              print(people[i])
              people[i] = 0  
          i = (i+1) % n
          print("," if num < n-1 else "\n")
* 该算法重点是保证报1时是本身,因此count判断应在改变i值之前
* 算法复杂性$O(n^2)$

##### **b.连续表算法实现**
* 将保存人员编号的list按照表的方式处理
* 算出应该退出的人后,将其从表里删除
* 元素计数与下标计数统一,下标更新可用i=(i+m-1)%num
```python
def josephusL(n, k, m):
    people = list(range(1, n+1))
    i = k-1
    for num in range(n,0,-1):
        i = (i+m-1) % num
        print(people.pop(i))
        print("," if num > 1 else "\n")
  • 该算法重点是pop()弹出操作,弹出后下标i后面的所有元素前移一位,因此还是从下标i位置开始记录报数,只是表长度减一
  • 由于pop操作为$O(n)$,因此算法复杂性为$O(n^2)$
c.循环链表算法实现
  • 建立一个包含n个人编号的循环链表
  • 循环计数,删去需要退出的结点
  • 基于循环单链表
    class Joesphus(LCList):
    def turn(self, m):
        for i in range(m):
            self.rear = self.rear.next
    def __init__(self, n, k, m):
        LCList.__init__(self)
        for i in range(1, n+1)
            self.append(i)
        self.turn(k-1)
        while not self.isEmpty():
            self.turn(m-1)
            print(self.pop())
            print("," if not self.isEmpty else "\n")
  • 该算法重点利用了self.rear,初始时self.rear指向循环链表尾端结点,通过预先调用turn函数沿next移动k-1步,即到了编号为k-1所在结点,由于pop是首端弹出,在链表上体现为self.rear的next域所指向的结点,因此应将self.rear移动到结点被弹出处的前一位置。由于报数是从1开始报,因此每次循环,self.rear都是沿next移动m-1步,为了保证循环的统一性,因而第一次调用turn只移动k-1步。
  • 算法复杂性O(m*n)
最后由 oucb 编辑于2016年05月03日 16:15