0. 数据结构的建立

数据结构的建立，首先是数据的设计，无论是线性的队列、栈、线性表，还是树、图等，基本的数据类型最后都将抽象为结点 None。对于结点的实现而言，其最为重要的功能便是持有的私有成员变量，以及在构造函数对这些成员变量的赋值； class Node: def __init__(self, value, next=None): self.value = value self.next = next 结点的建立：

• 对于链表的结点而言，一个结点至少有两个域，数据域与指针域； class LNode: def __init__(self, elem, next_=None): self.elem = elem self.next_ = next_
• 对于二叉树的结点而言，一个结点至少有三个域：数据域，左指针域，右指针域； class BinTNode: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right

1. 队列

• 出队：q.head = (q.head+1)%q.len
• 入队：q.rear = (q.rear+1)%q.len
• 队列为空的判断：
  
  • q.head == q.rear，显然这种方式就不能再进行判断队列为满的情况了
• 队列满的判断：
  
  • (q.rear+1 )%q.len == q.head，也即会牺牲掉一个存储空间；

2. Decision tree

• Decision Tree：是一种对解空间的穷举；
• tree：很大的可能性要递归，既然牵涉到递归，以下两点必须注意
  • 递归退出的条件，首先需要言明
  • 只需构造中间的某一子问题，比如树（根节点，左子树，右子树），的情况，剩下的交给递归结构

有感于 从0-1背包问题到动态规划 一文中，为了用动态规划求解0/1背包问题，构造了一个二分的 Decision Tree。而这一 Decision Tree 在程序中的表现浑然一体，绝非牵强； without_i = fastMaxVal(i-1, w, v, c, m) with_i = v[i] + fastMaxVal(i-1, w, v, c-w[i], m) # 俨然已是一个二分支的节点结构 m[(i, c)] = max(with_i, without_i)

3. 字典与hash

统计文件中单词出现的次数： ## Python from collections import defaultdict words = defaultdict(int) with open(fileName) as fp: for line in fp.readlines(): for word in line.strip().split(): words[word] += 1 // C++ typedef std::map<std::string, size_t> WordCountMapType; WordCountMapType wordsInFile(const string& fileName) { std::ifstream ifs(filename); WordCountMapType words; for (std::string word; ifs >> word; ) ++words[word]; return words; }