Learning Key Word

Keyword

 2017/12/12

顺序表

顺序表优化
- 若对表项的排列顺序无要求，在删除或者插入时，存在优化可能。
顺序表优缺点
- 优：
  - 无需为了表达节点间的逻辑关系而增加额外的存储空间，存储利用效率高。
  - 可以方便地随机存取表中任一结点，存取速度快。
- 缺：
  - 当插入或者删除，若需要保持相对次序不变，平均需要移动一般元素，运行效率很低。
  - 顺序表要求占用连续的空间。

链表 — 克服顺序表缺点

单链表特点
- 长度可以方便地进行扩充
单链表的建立
- 前插法
  - 插入数据总是在表的前端进行
- 后插法[ 维护last 指针 ]
  - 插入数据总是在表的后端进行
单循环链表
- 链表的表尾结点的link域中不是NULL，而是存放了一个指向链表开始结点的指针。
- 对于单循环链表，维护表尾结点比维护表头结点性价比更高。
  - 考虑现今在表头插入数据a
  - 如果维护表头指针，则需要遍历到表尾已更新表尾的link域，而维护表尾指针则不需要。
双向链表
- 特点
  - 每个结点有两个链指针，一个指向结点的直接前驱，一个指向结点的直接后续。不论是向前驱搜索还是向后继方向搜索，时间开销都只有O(1)。
静态链表
- 使用数组构建，为每一个元素附加一个链接就指针。它允许我们不改变各元素的物理位置。
- 既可以利用数组下标访问带来的访问速度的提升，也可以避免顺序表插入删除数据时较低的性能表现

栈

栈
- 定义
  - 只允许在表的末端进行插入和删除的线性表。
  - 允许插入的一端为栈顶不允许的一端为栈底 后进先出 ( LIFO )
- 分类
  - 顺序栈
  - 链式栈
- 应用
  - 括号匹配 — 括号匹配本身便是后进先出 [ok]
  - 表达式计算 [not ok]
    - 中缀表达式 [ 2s ]
    - 后缀表达式 [ 1s ]
    - 利用栈将中缀表示转换为后缀表示

栈与递归

定义
- 若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的。
- 若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。
例子
- 阶乘函数、幂函数、斐波那契数列
1.定义是递归的
- 认识
  - 对于一个较为复杂的问题，如果能够分解成几个相对简单的且解法相同或类似的子问题时，只要解决了这些子问题，那么原问题就迎刃而解了。【分治法】
  - 对分解后的子问题可以直接解决时，就停止分解，退出递归。【递归结束条件】
  - 递归定义的函数，可以用递归调用的方式来求解。递归调用的过程直接反映了函数定义本身的意义(结构)
2.数据结构是递归的
- 数据结构本身就是递归的，例如链表、树。
- 链表结点LinkNode 由 数据域data和 指针域link 组成。而指针link则由LinkNode定义
- 对于递归形式的数据结构，使用递归的方法来编写算法特别方便。[idontthinkso]
3.问题的解法是递归的
- 经典例子：汉诺塔

long Factorial(long n){
  if( n == 0 ) return 1;
  else return n * Factorial(n-1);
}

C++

Assert机制

template< class T >
SeqStack<T>::SeqStack(int sz):top(-1), maxSize(sz){
	elements = new T[maxSize];
	assert(elements != NULL); //断言较if判断句更为整洁，可读性更高。
}

