缥缈峰

计算机解决问题的本质就是搜索，说通俗一点就是尝试各种可能的情况，然后比较找出所需的解。我是从高一开始接触信息学竞赛的，竞赛和工程不一样，要求的是好的算法和在非常短的时间内实现，而工程要求的是稳定性可控和可测。说句实话，高二NOI'98(杭州)以后，我基本上没有再研究过搜索算法，很惭愧，这里贴出我高中的笔记，希望对大家有所帮助。


搜索算法分类：
1）盲目搜索：回溯法、广度优先、深度优先、双向广度优先、分支定界等
2）启发式搜索：A*、分段A*、博弈树等


回溯法：搜索算法的一种控制策略，亦是求解特殊性计数题或较复杂的枚举题中使用频率最高的一种算法，属基础算法，需优化后才能满足解题需要。

常用优化策略：
A）设定阀值，依次扩展节点
B）对处理过的节点不保留


广度优先、双向广度优先算法：解决最优化问题，盲目搜索无智力，一般都用双向广度优先算法。
需要注意的是：
A）双向广度优先算法，使用两头向中间扩展的队列
B）若产生重复节点的几率小，则可以取消判重
C）节点输出用递归：
void Print(int n)
{
   if (n > Queue[n]) printf("%dn", Queue[n].data);
   if (Queue[n] <> 0) Print(Queue[n].from);
   if (n < Queue[n]) printf("%dn", Queue[n].data);
}
单向输出： Print(F);
双向输出： Print(Queue[i].From); Print(i); // i为重合节点
D）扩展节点不是机械的按照正方向一层再逆方向一层，两个方向交替扩展的方法，而是选择节点个数较少的那个方向先扩展，这样就克服了两个方向节点生成速度不平衡的缺点（广度优先搜索的最大困难就是节点膨胀成指数级增长）


分支定界法：试题并未指定目标状态，而是给出约束条件和求某个目标函数的最小要求。
采用分支定界法题目的特点：
A）设置了一个下届prim－－目前为止的最优解。在分支定界中，每扩展一个节点，都要重新评估下界，若子节点中相关于目标函数的域值小于下界，才取该域值为新下界，并几下子节点信息
B）设定了一个界变量。在分支定界法中，必须按照目标函数的要求设计变量，作为分支标准，每扩展一个节点之前，都要根据当时已扩展情况计算界变量
C）搜索方式与广度搜索类似（队列）


A*算法：（这个内容好想Job Hunting的时候一般不会考察(游戏界人士除外)，所以不费口水了）
………………


各类搜索算法联系图
深度优先------------------>分支定界
         |---->启发式-->A*(修改A*)
广度优先------------------>双向广度


小结
>>深度优先（回溯法）：适用于求所有解或普通解，没有智力，对空间要求不大，是一种最自然的走迷宫方法
>>广度优先：适用于求最优解，没有智力，对空间要求很大（必须存储所有节点）
>>A*（修改A*）：是启发性搜索的最优化版本（不放弃“坏”节点），适用于求最优解
>>分支定界：是深度优先的最优化版本，是一种简单的求最优解的算法，逆同样可以将你的智慧放在剪枝函数>>中，它继承了深度优先的空间要求小的优点（完全放弃“坏”节点，类似“贪心法”）
>>双向广度：一定程度上降低了广度优先的空间要求大的弊端，尽管没有智力，也不失一种很好的求最优解算法


搜索算法的选择方法
A）根据题目要求和各类算法的适用范围，将不可行的算法抛弃
B）根据题目的规模，将某些不适用与大规模试题的算法抛弃
C）分析问题，找到问题的特点，如果找到了启发函数，就可以使用启发的解法解决
D）如果进一步找到更多关于问题的信息，也许可以使用数学算法（构造法）解决


转载请注明出处，谢谢！

线性表是《数据结构》正文第一部分的内容，是很简单的，也是很重要的基础知识。对于这部分知识大家应该记得滚瓜烂熟。
     线性表的实现分为顺序（数组）和链表，顺序实现过于简单，这里就不费口水了。
     链表实现有三种类型： 1)单向链表 2)循环链表 3)双向链表


链表的实现有几种形式：（主要是两种表示空节点的方式：NULL和DummyNode哑节点)

A)单链表，头节点NULL为空，尾节点NULL为空
初始化：head = NULL;
x节点后插入t节点：if (x == NULL) { head = t; } else { t->next = x->next; x->next = t;}
删除x后的节点：t = x->next; if (t) { x->next = t->next; free(t); }
遍历： t = head; while(t) { ...; t = t->next; }
是否为空：if (head == NULL) {...}


B)单链表，头节点哑节点为空，尾节点NULL为空
初始化：head = malloc(); head->next = NULL; // 浪费一个节点空间
x节点后插入t节点：t->next = x->next; x->next = t; // 少做一次判断
删除x后的节点：（同A）
遍历： （同A）
是否为空：if (head->next == NULL) {...}


C)单链表，头节点哑节点为空，尾节点哑节点为空 (这个很少用)
初始化：head = malloc(); z = malloc(); head->next = z; z->next = z; // 浪费两个节点空间
x节点后插入t节点：（同B）
删除x后的节点：（同B）
遍历： t = head->next; while (t != z) { ...; t = t->next; }
是否为空：if (head->next == z) {...}


D)循环链表
初始化：head = malloc(); head->next = head;
x节点后插入t节点：（同B）
删除x后的节点：（同B）
遍历： t = head; do { ...; t = t->next; } while (t != head);
是否为空：if (head->next == head) {...}


E)双向循环链表
初始化：head = malloc(); head->next = head->prev = head;
x节点后插入t节点：t->next = x->next; t->prev = x; x->next->prev = t; x->next = t;
删除x节点：x->prev->next = x->next; x->next->prev = x->prev; free(x);
遍历：（同D）
是否为空：（同D）



线性表应用：
1)单向链表
合并两个有序单向链表


逆转链表



2)循环链表
Josephus问题



转载请注明出处，谢谢！

英语啊……英语！
努力啊……努力！

最近正好是如火如荼的Job hunting time，经常会和同学们一起讨论数据结构，算法，C语言的知识，或许我真的应该仔细记录一下这段经历。虽然自己已经拿到offer，不过可以作为其他同学面试的参考，对自己所学的知识也算是一个回顾。

<大家有什么建议和意见请在评论中指出，谢谢！>

Job Hunting -- 1.起因
C语言:
Job Hunting -- 2. sizeof运算符
Job Hunting -- 3. const与static
Job Hunting -- 4. C函数调用
算法:
Job Hunting -- 5. 排序
Job Hunting -- 6. 查找
Job Hunting -- 7. 搜索
数据结构:
Job Hunting -- 8. 线性表
Job Hunting -- 9. 字符串
Job Hunting -- 10. 堆栈和队列
Job Hunting -- 11. 树
Job Hunting -- 12. 图
其他：
Job Hunting -- 13. 经典书籍
Job Hunting -- 14. 编译器与解释器

Job Hunting 第一次讲座 幻灯片下载！