算法导论10.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 670 阅读时长 ≈ 1 分钟

10.2-1

因为插入操作仅仅需要在链表\(L\)的头节点插入就好，将当前节点作为新的头节点，链接下一个原来的头节点。这种操作仅需要\(O(1)\)的时间。但是删除一个节点\(x\)时，由于\(L\)是单向链表，因此需要遍历整个\(L\)来查找\(x\)的前驱节点\(y\)，并且将\(y\)链接到原来\(x\)的下一个节点。因此最坏的时间开销为\(\Theta(n)\)，即\(L\)的长度。

10.2-2

1
2
3
4
5
6
7
8
9
10
11
12
13
STACK-EMPTY-LIST(L)
  return L.head == NIL

PUSH(L, x)
  x.next = L.head
  L.head = x

POP(L)
  if STACK-EMPTY-LIST(L)
    error "underflow"
  x = L.head
  L.head = L.head.next
  return x

10.2-3

需要给链表\(L\)需要添加一个属性tail表示链表的末节点指针。

值得注意的是，这里用tail指针表示队头，用head指针表示队尾，链表和队列中指针的头和尾含义完全是“相反”的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
QUEUE-EMPTY-LIST(L)
  return L.head == NIL

ENQUEUE(L, x)
  if QUEUE-EMPTY-LIST(L)
    L.head = x
  else
    L.tail.next = x
  x.next = NIL
  L.tail = x

DEQUEUE(L, x)
  if QUEUE-EMPTY-LIST(L)
    error "underflow"
  x = L.head
  L.head = L.head.next
  if L.head == NIL
    L.tail = NIL
  return x

10.2-4

考虑集合S1, S2分别使用带哨兵的双向链表L1, L2来存储。那么合并两个链表的操作非常简单，只需要将L1的元素放在新链表L的前面，将L2的元素放在新链表L的后面，并且顺序也不会被破坏。

需要注意的是，合并后，需要将L2的哨兵去掉。

1
2
3
4
5
6
7
8
UNION(L1, L2)
  //去掉L2的哨兵
  L1.nil.prev.next = L2.nil.next
  L2.nil.next.prev = L1.nil.prev
  //将L1的哨兵和L2的末节点关联
  L1.nil.prev = L2.nil.prev
  L2.nil.prev.next = L1.nil
  return L1

完成这\(4\)个链表操作后，得到的新链表就是集合S1, S2的并，并且仍然是一个带哨兵的双向链表。

10.2-5

1
2
3
4
5
6
7
8
9
10
11
REVERSE-LIST(L)
  // a, b, c是链表上3个相邻的节点。
  a = NIL
  b = L.head
  while b != NIL
    c = b.next
    b.next = a
    a = b
    b = c
  L'.head = a
  return L'

\(\star\) 10.2-6

基本思路：如果\(A\text{ XOR }B=C\)，那么\(A\text{ XOR }C=B\)。也就是说，对于指针np，如果知道了目前的其中一个值，那么可以求解出另一个值。

考虑双向链表\(L\)有头哨兵指针nilhead，尾哨兵niltail。

和书上介绍的双向链表有所不同，这个双向链表的头哨兵前驱指针prev被认为指向NIL，尾哨兵后继指针next被认为指向NIL。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
SEARCH-NP(L, k)
  prev = L.nilhead
  p = L.nilhead.np
  while p != niltail and p.key != k
    // prev是p前驱节点的指针，next是p的后继节点指针。
    next = p.np XOR prev
    prev = p
    p = next
  if p == L.niltail
    return NIL
  else
    return p

INSERT-NP(L, x)
  q = NIL XOR L.nilhead.np
  // 第一个XOR还原出了q的next地址。
  q.np = (q.np XOR L.nilhead) XOR x
  x.np = L.nilhead XOR q
  L.nilhead.np = NIL XOR x

DELETE-NP(L, x)
  prev = L.nilhead
  p = L.nilhead.np
  while p != niltail
    // prev是p前驱节点的指针，next是p的后继节点指针。
    next = p.np XOR prev
    if p == x
      prev.np = (prev.np XOR p) XOR next
      next.np = (next.np XOR p) XOR prev
      // 注意，p节点被删除了，那么prev仍然是prev，不需要改变。
      p = next
    else
      prev = p
      p = next

REVERSE-NP(L)
  swap L.nilhead with L.niltail