数据库课程设计-企业人事管理系统.doc

武汉工程大学本科课程设计 论文 I 2013 级课程 设计 论文 题题 目目 企企业业人人事事管管理理系系统统 专专业业班班级级 1 13 3 级级信信息息与与计计算算科科学学 0 02 2 班班 学学 号号 X XX X 学学生生姓姓名名 X XX X 指指导导教教师师 X XX X 指指导导教教师师职职称称 讲讲 师师 学学院院名名称称 理理学学院院 完完成成日日期期 2 20 01 16 6 年年 1 1 月月 5 5 日日 武汉工程大学本科课程设计 论文 II 摘摘 要要 英英文文 T Th hr ro ou ug gh h t th he e k kn no ow wl le ed dg ge e o of f d di is sc cr re et te e m ma at th he em ma at ti ic cs s i in n t th hi is s t te er rm m I I h ha av ve e a a c ce er rt ta ai in n u un nd de er rs st ta an nd di in ng g o of f t th he e m mi in ni im mu um m s sp pa an nn ni in ng g t tr re ee e a an nd d k kn no ow w t th ha at t t th he e m mi in ni im mu um m s sp pa an nn ni in ng g t tr re ee e c ca an n b be e r re ea al li iz ze ed d b by y u us si in ng g p pr ro og gr ra am mm mi in ng g T Th hi is s p pa ap pe er r s si im mp pl ly y i in nt tr ro od du uc ce es s t tw wo o a al lg go or ri it th hm ms s f fo or r m mi in ni im mu um m s sp pa an nn ni in ng g t tr re ee e a an nd d t th he e u us se e o of f o on ne e o of f t th he es se e t tw wo o a al lg go or ri it th hm ms s n na am me el ly y t th he e K Kr ru us sk ka al l s s a al lg go or ri it th hm m a an nd d p pr ro og gr ra am mm mi in ng g K Ke ey yw wo or rd ds s m mi in ni im mu um m s sp pa an nn ni in ng g t tr re ee e a al lg go or ri it th hm m K Kr ru us sk ka al l s s a al lg go or ri it th hm m p pr ro og gr ra am mm mi in ng g 武汉工程大学本科课程设计 论文 III 目目 录录 目 录 III 摘 要 IV 前 言 V 第 1 章 课题背景 1 1 1 问题背景及基础知识 1 1 2 意义 2 第 2 章 需求分析 3 2 1 普里姆算法 3 2 2 克鲁斯克尔算法 3 2 3 克鲁斯克尔算法的程序 5 第 3 章 数据库设计 6 3 1 实例及其算法分析 6 3 2 相关程序代码及运行结果 9 第 4 章 总 结 14 致 谢 15 参考文献 16 武汉工程大学本科课程设计 论文 IV 摘摘 要要 通过本学期学习的离散数学的知识 我对最小生成树有了一定了解 并知道 了最小生成树可以运用编程实现 本文主要简单介绍了最小生成树的两种算法 并运用其中一种算法 即克鲁斯克尔算法 进行编写程序 关关键键词词 最小生成树 克鲁斯克尔算法 程序 武汉工程大学本科课程设计 论文 V 前前 言言 本文解决了最小生成树如何用编程实现的问题 全文共四章 第 1 章介绍了 问题背景以及相关的基础知识 第 2 章主要介绍了最小生成树的两种算法 第 3 章主要介绍了如何用最小生成树的编程来解决相关问题 第 4 章是本次课程设计的总结 全文的最后是致谢 参考文献 刘润秋 2015 7 9 于武汉工程大学理学院 武汉工程大学本科课程设计 论文 1 第第 1 1 章章 课课题题背背景景 1 1 1 1 问题背景问题背景及基础知识及基础知识 一个有 n 个结点的连通图的生成树是原图的极小连通子图 且包含原图中 的所有 n 个结点 并且有保持图连通的最少的边 只有连通图才有最小生成树 在一给定的无向图 G V E 中 u v 代表连接顶点 u 与顶点 v 的边 而 w u v 代表此边的权重 若存在 T 为 E 的子集 即 且为无循环图 使 得的 w T 最小 则此 T 为 G 的最小生成树 最小生成树其实是最小权重生 成树的简称 最小生成树也有自己的性质 其性质为其算法提供了一定的依据 最小生成 树性质 设 G V E 是一个连通网络 U 是顶点集 V 的一个非空真子集 若 u v 是 G 中一条 一个端点在 U 中 例如 u U 另一个端点不在 U 中的边 例如 v V U 且 u v 具有最小权值 则一定存在G 的一棵 最小生成树包括此边 u v 另外 贪心原理也是最小生成树算法所依据的原理之一 所谓贪心原理指的 是从初始状态出发 每步都经过贪心选择 最终得到问题的最优解 其含义 将每一步都看成是当前最佳的选择 做到局部最优化 直到无法选择为止 寄希 望于局部最优的选择能够导致全局最优解 在此基础上 便有了普里姆算法和克 鲁斯克尔算法 武汉工程大学本科课程设计 论文 2 1 1 2 2 意义意义 生成树和最小生成树有许多重要的应用 而在实际生活中的许多例子并不适合让 人来逐一通过画图计算来解决 有的问题涉及到的数据多且大 这时候我们就需要 运用所学的计算机的相关知识进行编程来更快速有效的解决问题 所以说 最小生 成树的编程实现是非常有必要的 1 1 3 3 文献综述文献综述 文献 1 介绍了最小生成树的相关知识 文献 2 介绍了克鲁斯克尔算法和普里姆算法 武汉工程大学本科课程设计 论文 3 第第 2 2 章章 算算法法介介绍绍 2 2 1 1 普里姆算法普里姆算法 普里姆 Prim 算法简述 1 输入 一个加权连通图 其中顶点集合为V 边集合为 E 2 初始化 Vnew x 其中 x 为集合 V 中的任一节点 起始点 Enew 为 空 3 重复下列操作 直到 Vnew V a 在集合 E 中选取权值最小的边 其中 u 为集合 Vnew 中的元素 而 v 不在 Vnew 集合当中 并且 v V 如果存在有多条满足前述条件即具有相同权值 的边 则可任意选取其中之一 b 将 v 加入集合 Vnew 中 将边加入集合 Enew 中 4 输出 使用集合 Vnew 和 Enew 来描述所得到的最小生成树 2 2 2 2 克鲁斯克尔算法克鲁斯克尔算法 克鲁斯卡尔算法 Kruskal s algorithm 是两个经典的最小生成树算法的较为简 单理解的一个 这里面充分体现了贪心算法的精髓 假设 WN V E 是一 个含有 n 个顶点的连通网 则按照克鲁斯卡尔算法构造最小生成树的过程为 先构造一个只含 n 个顶点 而边集为空的子图 若将该子图中各个顶点看成是 各棵树上的根结点 则它是一个含有 n 棵树的一个森林 之后 从网的边集 E 中选取一条权值最小的边 若该条边的两个顶点分属不同的树 则将其加入子 图 也就是说 将这两个顶点分别所在的两棵树合成一棵树 反之 若该条边的 两个顶点已落在同一棵树上 则不可取 而应该取下一条权值最小的边再试之 依次类推 直至森林中只有一棵树 也即子图中含有 n 1 条边为止 到这里所 武汉工程大学本科课程设计 论文 4 有的边点都已经连通了 一个最小生成树构建完成 Kruskal 算法的时间复杂 度由排序算法决定 若采用快排则时间复杂度为O N log N 算法步骤如下 设 G V E f 是一具有 n 个结点的连通有权图 构造G 的最小生成树 1 选取 G 中一条边 使在 G 的所有边中有最小的权 令 1 e 1 e V 置 i 为 1 1 G 1 S 1 S 1 e 2 若已选好 从 E 中选一条边使其满足下列条 i S 1 e 2 e i e i S 1 i e 件 1 中不含环 i S 1 i e 2 在 E Si 的满足 的所有边中 有最小的权 1 i e 若满足上述条件的边不存在 则 V 就是最小生成树 否则令 1 i e i G i S V 1 i S i S 1 i e 1 i G 1 i S 3 i 增加 1 并返回到第 2 步 武汉工程大学本科课程设计 论文 5 2 3 克克鲁鲁斯斯克克尔尔算算法法的的程程序序 克鲁斯克尔算法的函数 void Kruskal Graph G int i j m1 m2 n1 n2 for i 0 i G e i 对对图图中中的的每每条条边边进进行行挑挑选选 m1 G E i u m2 G E i v 取取第第 i 条条边边的的起起点点与与终终点点 n1 G V m1 n2 G V m2 获获取取两两顶顶点点的的连连通通类类别别 if n1 n2 如如果果两两顶顶点点不不属属于于同同一一连连通通类类 输输出出该该边边与与权权值值 cout 边边 m1 m2 代代价价 G E i w endl for j 0 j G n j if G V j n2 使使 n2 类类顶顶点点归归并并为为 n1 类类顶顶点点 G V j n1 武汉工程大学本科课程设计 论文 6 第第 3 3 章章 实实例例及及编编程程 3 3 1 1 实例及其算法分析实例及其算法分析 例如 要在 n 个城市之间铺设光缆 主要目标是要使这 n 个城市的任 意两个之间都可以通信 但铺设光缆的费用很高 且各个城市之间铺设光缆的费 用不同 因此另一个目标是要使铺设光缆的总费用最低 这就需要找到带权的最 小生成树 以下图为例 从0 出发 得到此图的最小生成树 图 3 1 1 根据克鲁斯克尔算法 将其步骤细化如下 武汉工程大学本科课程设计 论文 7 1 对带权边数组 E 按权值做升序排序如下表 表表 3 1 13 1 1 对图的顶点数组 V 7 表 3 1 2 2 挑边 0 3 因为 V 0 0 3 V 3 将边 0 3 选入最小生成树 并置 V 3 V 0 0 即顶点 0 3 为一个连通类 顶点数组 V 7 被改变为 表 3 1 3 武汉工程大学本科课程设计 论文 8 3 挑边 2 4 表 3 1 4 4 挑边 3 5 表 3 1 5 5 挑边 0 1 表 3 1 6 6 挑边 1 4 表 3 1 7 7 边 1 2 4 5 1 3 不需要 挑边 4 6 由于 V 中元素全为 V1 这表明 6 个顶点属于与顶点 V1 连通的类 继续挑选下去 也不会增加新的边 最小生成树画出来如下图 武汉工程大学本科课程设计 论文 9 图 3 1 2 3 3 2 2 相关程序代码及运行结果相关程序代码及运行结果 include using namespace std define Maxsize 20 最最大大顶顶点点数数 带带权权边边的的定定义义 struct Edge int u v w 边边的的起起点点 终终点点与与权权值值 图图的的定定义义 struct Graph int V Maxsize 顶顶点点 Edge E Maxsize 带带权权边边 武汉工程大学本科课程设计 论文 10 int n 顶顶点点数数 int e 边边数数 根根据据顶顶点点集集合合 V 边边集集合合 E 创创建建图图 void Creat Graph 获获取取图图的的顶顶点点数数 G e en 获获取取图图的的边边数数 for int k 0 k G n k G V k V k 对对图图的的顶顶点点赋赋值值 for k 0 k G e k G E k u E 3 k 0 对对第第 k 边边的的起起点点赋赋值值 G E k v E 3 k 1 对对第第 k 边边的的终终点点赋赋值值 G E k w E 3 k 2 对对第第 k 边边的的权权赋赋值值 输输出出边边 void Display Graph G cout 起起点点 t 终终点点 t 代代价价 endl for int k 0 k G e k cout G E k u t G E k v t G E k w endl 选选择择排排序序 void Sort Graph Edge temp for i 0 i G e i min G E i w pos i flag 1 武汉工程大学本科课程设计 论文 11 for j i jG E j w min G E j w pos j flag 0 if flag 0 temp G E i G E i G E pos G E pos temp 克克鲁鲁斯斯克克尔尔算算法法 void Kruskal Graph G int i j m1 m2 n1 n2 for i 0 i G e i 对对图图中中的的每每条条边边进进行行挑挑选选 m1 G E i u m2 G E i v 取取第第 i 条条边边的的起起点点与与终终点点 n1 G V m1 n2 G V m2 获获取取两两顶顶点点的的连连通通类类别别 if n1 n2 如如果果两两顶顶点点不不属属于于同同一一连连通通类类 输输出出该该边边与与权权值值 cout 边边 m1 m2 代代价价 G E i w endl for j 0 j G n j if G V j n2 使使 n2 类类顶顶点点归归并并为为 n1 类类顶顶点点 G V j n1 主主函函数数 void main int V 7 0 1 2 3 4 5 6 顶顶点点集集 int E 11 3 0 1 7 0 3 5 1 2 8 1 3 9 1 4 7 武汉工程大学本科课程设计 论文 12 2 4 5 3 4 15 3 5 6 4 5 8 4 6 9 5 6 11 带带权权边边集集 Graph G 定定义义图图 Creat G 利利用用顶顶点点集集 V 和和带带权权边边集集 E 创创建建图图 G Sort G 调调用用排排序序函函数数 cout 带带权权变变的的排排序序 endl Display G 输输出出带带权权边边的的排排序序 cout 最最小小生生成成树树 endl Kruskal G 调调用用克克鲁鲁斯斯克克尔尔算算法法函函数数 运运行行结结果果 武汉工程大学本科课程设计 论文 13 图 3 2 1 武汉工程大学本科课程设计 论文 14 第第 4 4 章章 总总 结结 通过此次课程设计 让我掌握了如何运用计算机知识解决连通图的最小生成 树的问题 我更加深入到体会到 只有