图

Q: 判断有向图是否存在回路，可以用哪些方法？。

A:

• 拓扑排序: 还有顶点未输出,但已经不存在没有前驱的顶点了。

  拓扑排序，是对有向无回路图进行排序，以期找到一个线性序列，这个线性序列在生活正可以表示某些事情完成的相应顺序。如果说所求的图有回路的话，则不可能找到这个序列。

• 深度优先:从一个顶点出发存在搜回到自己的路径。

链表

Q: 如何在一个长度未知的单链表中快速找出位于中间的那个元素

A: 设置两个指针：p1, p2：

• p1, p2置于链表的头部
• p1每次步进两步, p2每次步进一步 当p1到大链表的末尾时, p2所在的位置就是链表的中间元素

FIFO

基本结构

struct ring_buffer
{
    unsigned char *data[RING_BUFFER_MAXSIZE];
    int front, rear;
} *p;

• 初始值: p->front=0; p->rear=0;
• FIFO为空: p->front==p->rear;
• FIFO为满: (p->rear + 1) % RING_BUFFER_MAXSIZE == p->front
• FIFO加1： p->rear = (p-rear + 1) % RING_BUFFER_MAXSIZE
• FIFO减1： p->front= (p-front + 1) % RING_BUFFER_MAXSIZE

哈希表

Q:Hash冲突有什么解决方法?

A:

• 开发地址方法, 逐个往下找, 直到找到有空的
• 再哈希法, 使用多个构造函数
• 溢出区: 冲突的元素都放这
• 链地址法: 和同HASH的元素构成一个链表

随机数

Q: 如何随机生成a-z三个字母的随机组合?

A:

• 打乱a-z字母的列表, 然后取前3个.
• 初始化0-25个数字的列表, 先生成025中的随机数, 然后用最后一个数字填充被抽出来的数字, 在生成024的数字, 如此类推
• 先生成a-z的3字母全排列2600个, 然后随机生成 0-2599的数字, 用下标去取
• 如果内存空间不多, 我用一个集合, 然后生成随机字母放进去, 直到集合中字母数量为3

位运算

Tips:

• 涉及到位运算和移位的，具体运算结果很可能和处理器以及对应的编译器实现相关

MISC

各类数据结构的适用场景

• 数组适合需要随机读写频繁的场景
• 链表适合插入删除频繁的场景
• 树适合层次关系.