今日学习内容

今天阅读了《算法》1.3 节，并做了几个习题

  • Bag, TestBag

    • 这个程序主要是实现了背包，比较简单，内部就是一个链表，尽管我们存储的数据有序，但背包(集合)的定义中，数据是无需的，提供的接口也应该认为数据无序。

  • Parentheses, TestParentheses

    • 这个程序是习题 1.3.4 的答案，目的是判断输入的括号是否左右匹配
    • 这个程序是算数表达式求值 的简化版本，只用一个栈存储左括号，遇到右括号弹出，并判断是否匹配即可。

  • DoubleNode, TestDoubleNode

    • 这个程序是习题 1.3.31 的答案，目的是实现一个双向链表，它提供了以下的接口

      • public boolean IsEmpty() 判断链表是否为空
      • public int Size() 获取链表长度
      • public void AddHead(Item item) 向头部添加元素
      • public void AddTail(Item item) 向尾部添加元素
      • public Item GetN(int N) 从指定索引获取元素，超出范围时返回 null
      • public Item RemoveHead() 删除头部元素
      • public Item RemoveTail() 删除尾部元素
      • public Item RemoveN(int N) 根据指定索引删除元素，超出范围时返回 null
      • public void AddAfter(Item item, int N) 在指定元素前面添加节点
      • public void AddBefore(Item item, int N) 在指定元素尾部添加节点
      • public Iterator<Item> iterator() 迭代器接口，实现了一个逆序遍历的迭代器
      • public class ReverseDoubleNodeIterator implements Iterator<Item> 迭代器

    • 我遇到的错误主要是以下节点

      • AddTail 和 AddHead 要处理添加到头或尾的情况，及时更新 head 和 tail
      • AddHead 和 AddTail 在链表为空时要正确初始化，仅有一个节点时，节点的 prev 和 next 都应该是空