算法学习笔记（一）

有两种思想,像珠宝商放在天鹅绒上的宝石一样濯濯生辉,一个是微积分,另一个就是算法。微积分以及在微积分基础上建立起来的数学分析体系造就了现代科学，而算法则造就了现代世界。                                        ——《算法的出现》

基本数据结构

1、线形数据结构

(1)    数组: “串”(如:数据串, 二进制串)

(2)    链表:  单链表:数据+下一个元素的地址指针

         双链表:上一个元素的地址指针+数据+下一个元素的地址指针

 注:数组与链表的区别:访问方式不同,数组是直接单个访问,链表是循链访问。

(3)    线性列表:

栈：   “后进先出”（LIFO）->“一叠盘子”

       插入和删除操作都在尾端-> 栈顶

队列: “先进先出”(FIFO)-> “顾客队列”

            删除->队头->出队

            插入->队尾->入队

优先队列: (任务)->找出或最大元素，插入一个新元素->堆

2、图

    无向图

    有向图

    区别：是否顶点对(u,v)和顶点对(v,u)相同

    定义：图G=<V,E>

          V 是一个有限集合，其元素为顶点

          E 是一个有限集合，其元素为一对顶点，为边。

          注：是否禁止圈，0<=|E|<=|V|(|V|-1)/2

   根据边数多少:完全圈，稠密圈，稀疏圈。

   图的表示:

          邻接矩阵：一个n*n的布尔矩阵

          邻接链表：邻接矩阵中值为1的列

   加权圈：给边赋值(权重/成本)

   路径和环：

          路径：始于u止于v的邻接顶点序列

               简单路径：a,c,e,f 长度为3

               非简单路径:a,c,e,c,f 长度为4

          注：对于有向图->有向路径

   连通性：是否连通->取决于是否出现连通分量

   无环图：不含回路

3、树(连通无回路图)

    森林(无回路但不一定连通，其连通分量为树)

    有根树：(应用)描述层次关系

    状态空间树：回溯和分支界限

    区分/分辨：祖先，真祖先，父母，子女，兄弟，叶节点，父节点，子孙，子树。

 顶点的深度

 树的高度

4、有序树

     二叉树，二叉查找树，多路查找树。

     注：先子女后兄弟表示法

5、集合与字典

    表示集合的方法：位向量，线性列表结构

    抽象数据类型：数据项的抽象对象集合和一系列对这些对象所做的操作

    集合合并问题