第一讲算法基础.ppt

任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点， F 被称为子树森林 森林： 是 m（m≥0）棵互 不相交的树的集合 A root B E F K L C G D H I J M F 树的存储结构 双亲存储结构 typedef struct { ElemType data; int parent; }Ptree[MaxSize]; 链存储结构 typedef struct node { ElemType data; struct node*sons[MaxSons]; }TSonNode; 图 定义 图(Graph)G由两个集合V(Vertex)和E(Edge)组成,记为G=(V,E),其中V是顶点的有限集合,记为V(G),E是连接V中两个不同顶点(顶点对)的边的有限集合,记为E(G)。 E A C B D B C A F E D 图的基本术语 邻接点 相关边 路径 权和网 权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图,也称作网。 连通 若图G中任意两个顶点都连通,则称G为连通图,否则称为非连通图。 生成树 一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有构成一棵树的(n-1)条边。 A B E C F 15 9 7 21 11 3 2 图的存储结构 邻接矩阵 V0 V2 V3 V1 V4 V5 5 4 8 9 7 3 1 5 6 5 (a) 有向网 ? 5 ? 7 ? ? ? ? 4 ? ? ? 8 ? ? ? ? 9 ? ? 5 ? ? 6 ? ? ? 5 ? ? 3 ? ? ? 1 ? (b) 邻接矩阵 邻接表存储方法 1 3 0 2 4 1 3 0 2 4 (a) (b) 邻接表存储结构的定义如下： typedef struct ANode /*弧的结点结构类型*/ { int adjvex; /*该弧所指向的顶点的位置*/ struct ANode *nextarc; /*指向下一条弧的指针*/ InfoType info; /*该弧的相关信息*/ } ArcNode; typedef struct Vnode /*邻接表头结点的类型*/ { Vertex data; /*顶点信息*/ ArcNode *firstarc; /*指向第一条弧*/ } VNode; typedef VNode AdjList[MAXV]; /*AdjList是邻接表类型*/ typedef struct { AdjList adjlist; /*邻接表*/ int n,e; /*图中顶点数n和边数e*/ } ALGraph; /*图的类型*/ 集合 集合定义 集合之间关系 集合运算 集合的表示 常用数学公式 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 V没v * 举例： 假设算法A的运行时间表达式为T1(n) T1(n)=30n4+20n3+40n2+46n+100 假设算法B的运行时间表达式为T2(n) T2(n)=1000n3+50n2+78n+10 随着n的增大，对算法的执行时间影响最大的是最高次方。 算法A的运行时间可记为：T*1(n)≈n4 算法B的运行时间可记为：T*2(n)≈n3 渐近符号: O---上界 ?---下界 ?---精确界（上界和下界） 渐进符号 1. 大O符号(上界） 定义1.1 若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n)) n0 问题规模n 执行次数 n0之前的情况无关紧要 T(n) c×f(n) f(N)是T(N)的一个上界， 即T(N)的阶不高于f(N)的阶