概述:

平衡树——特点:所有结点左右子树深度差≤1

排序树——特点:所有结点“左小右大
字典树——由字符串构成的二叉排序树
判定树——特点:分支查找树(例如12个球如何只称3次便分出轻重)
带权树——特点:路径带权值(例如长度)

最优树——是带权路径长度最短的树,又称 Huffman树,用途之一是通信中的压缩编码。

Continue reading

堆栈与队列的实际应用

堆栈和队列是最基本的两个ADT,简单但是重要。先讲堆栈在计算机中的应用。

堆栈:

https://wenku.baidu.com/view/3eff617480eb6294dc886c91.html

1.用于符号匹配。

在编译器的语法检查中,一个过程就是检查各种括号是否匹配,比如 ([]) ,这就是匹配的,而 {[}] 就不匹配了。可以用堆栈来实现括号匹配。
具体算法如下:

 

6.5 矩阵的运算及其运算规则

 

一、矩阵的加法与减法


  1、运算规则 
  设矩阵
  则
       
  简言之,两个矩阵相加减,即它们相同位置的元素相加减!
  注意:只有对于两个行数、列数分别相等的矩阵(即同型矩阵),加减法运算才有意义,即加减运算是可行的.


  2、 运算性质 (假设运算都是可行的) 
  满足交换律和结合律
  交换律   
  结合律  

链表练习题:

 

编写一个复制构造函数 Chain<T>::Chain(const Chain<T>& C),把链表C中的元素复制到新的节点中。这个构造函数的复杂性是多少?

O(n) n 是链表长度

链表是最基本的数据结构,面试官也常常用链表来考察面试者的基本能力,而且链表相关的操作相对而言比较简单,也适合考察写代码的能力。链表的操作也离不开指针,指针又很容易导致出错。综合多方面的原因,链表题目在面试中占据着很重要的地位。本文对链表相关的面试题做了较为全面的整理,希望能对找工作的同学有所帮助。

链表结点声明如下:

struct ListNode
{
int m_nKey;
ListNode * m_pNext;

};
Continue reading