《离散数学实验报告__四个实验!!!_中学教育-中学实验.pdf》由会员分享，可在线阅读，更多相关《离散数学实验报告__四个实验!!!_中学教育-中学实验.pdf（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、.word 资料 离散数学 课程设计 学 院 计算机学院 学生 学 号 指导教师 评阅意见 提交日期 2011 年 11 月 25 日 .word 资料 引言 离散数学是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离
2、散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。实验一、编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性）一、前言引语：二元关系是离散数学中重要的容。因为事物之间总是可以根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之间存在的关系。二、数学原理：自反、对称、传递关系 设 A 和 B 都是已知的集合，R 是 A 到
3、B 的一个确定的二元关系，那么集合个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间
4、总是以根据需要确定相应的关系从数学的角度来看.word 资料 R 就是 A B 的一个合于 R=(x,y)A B|xRy 的子集合 设 R 是集合 A 上的二元关系：自反关系：对任意的 x A,都满足 R，则称 R 是自反的，或称 R 具有自反性，即 R 在 A 上是自反的(x)(x A)(R)=1 对称关系：对任意的 x,y A，如果 R，那么 R，则称关系 R 是对称的，或称 R 具有对称性，即 R 在 A 上是对称的(x)(y)(x A)(y A)(R)(R)=1 传递关系：对任意的 x,y,z A，如果 R 且 R，那么 R，则称关系 R 是传递的，或称 R 具有传递性，即 R 在 A
5、 上是传递的(x)(y)(z)(x A)(y A)(z A)(R)(R)(R)=1 三、实验原理：通过二元关系与关系矩阵的联系，可以引入 N 维数组，以数组的运算来实现二元关系的判断。图示：性质 关系矩阵特性 自反性 主对角线元素全为 1 反自反性 主对角线元素全为 0 对称性 对称矩阵 反对称性 非主对角线上的元素等于 1 且与之对称的元素等于 0 个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学
6、课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 传递性 矩阵（M*M）中 1 所在的位置，M 中与之相对应位置鲜红都为 1 四、实验环境：Windows 7 Ultimate DEV C+五、实验语言：C 语言 六、程序源代码：#includestdio.h#def
7、ine N 4 main()int i,j,k;int f,e,z;int MNN;printf(判断 R 是否为自反关系、对称关系、是否可传递？n);printf(请输入一个 4*4 的矩阵。n);for(i=0;iN;i+)/*输入一个 4*4 的矩阵*/for(j=0;jN;j+)scanf(%d,&Mij);for(i=0;iN;i+)for(j=0;jN;j+)printf(%4d,Mij);个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与
8、数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 printf(n);for(i=0;iN;i+)if(Mii=1)/判断自反性 if(i=N-1 e=0;else;else if(Mii=0)/判断反自反性 if(
9、i=N-1)e=1;else;个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是
10、以根据需要确定相应的关系从数学的角度来看.word 资料 else e=2;break;for(i=0;iN;i+)for(j=0;jN;j+)if(Mij!=Mji)/判断对称性 f=1;break;for(i=0;iN;i+)for(j=0;jN;j+)个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和
11、严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 if(Mij=1)/判断反对称性 if(Mji=0)if(i=(N-1)&j=N-1)f=0;else break;if(f!=0&f!=1)f=2;for(i=0;iN;i+)/判断可传递性 for(j=0;jN;j+)个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数
12、有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 if(Mij=1)continue;else for(k=0;k
13、N;k+)if(Mik*Mki=0)continue;else z=0;if(e=0)printf(关系 R 是自反关系 n);else if(e=1)printf(关系 R 是反自反关系 n);else if(e=2)printf(关系 R 是反自反关系 n);if(f=0)printf(关系 R 是反对称关系 n);else if(f=1)printf(关系 R 不是对称关系 n);else if(f=2)printf(关系 R 是对称关系 n);if(z=0)个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问
14、它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 printf(关系 R 是不可传递关系 n);else printf(关系 R 是可传递关系 n);s
15、ystem(PAUSE);七、程序运行截图：i、程序启动截图：ii、程序输入截图：个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一
16、前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 iii、程序运行结果截图:八、实验总结：实验简洁高效地判断二元关系的性质。实验二、编程求一个二元关系的自反闭包、对称闭包、传递闭包 一、前言引语 个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严
17、密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 一个二元关系可能具有某种性质，也可能不具有这种性质。现在讨论怎样使一个二元关系变成具有指定性质的新关系，并且还要满足最小性条件。二、数学原理 自反闭包、对称闭包、传递闭包 设 R 是定义在 A 上的二元关系，若存在 A 上的关系 R满足：1)R是自反的(或对称的、或可传递的)，2)R R，3)对 A 上任何其它满足
18、 1）和 2）的关系 R，都有：R R。则称 R为 R 的自反闭包(或对称闭包、或传递闭包)，分别记为 r(R)、(s(R)和 t(R)。三、实验原理 Warshall 算法的基本思想 对每个结点（从第一列开始），找出所有具有到此结点的有向边的结点（即该列中元素为 1 的所在行的结点），再将这些结点所在行同该结点所在行进行逻辑加后作为这些结点所在的新行（添加新的有向边）（反映了如果这些结点没有到其它结点的有向边，但有到该结点的有向边，再通过该结点间接到达其它结点，根据传递闭包的定义，这些结点就必然有一条有向边到达其它结点）。设 R 是集合上的二元关系,Mr 是 R 的关系矩阵(1)置新矩阵 A
19、:=Mr(2)置(列)j:=1(3)对所有的 i(1 i n)如 A(i,j)=1,则对 k=1,2,n A(i,k):=A(i,k)A(j,k)个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断
20、一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料(即将 A 的第 i 行与 A 的第 j 行进行逻辑加后送回 A 的第 i 行)(4)j:=j+1(5)如 j n 转(3),否则停止。四、实验环境：Windows 7 Ultimate DEV C+五、实验编程语言：C 语言 六、实验程序源代码/source file:War.cpp#include void War(int m,int n)int i,j,k;设置临时变量 int a=0,b=0;设置临时变量 int a
21、rr1010;for(a=0;a m;+a)printf(请输入矩阵第%d 行元素:,a);for(b=0;b n;+b)scanf(%d,&arrab);printf(n);个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不
22、少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 for(i=0;i m;i+)for(j=0;j m;j+)if(arrji=1)for(k=0;k n;k+)arrjk=arrik|arrjk;printf(所得的可传递闭包关系矩阵是：n);for(i=0;i m;+i)for(j=0;j n;+j)printf(%d,arrij);个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的
23、数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 printf(n);/file:test.cpp#include void m
24、ain()printf(利用 Warshall 算法求二元关系的可传递闭包 n);void War(int,int);int m,n;printf(请输入矩阵的行数(必须小于 10）：);scanf(%d,&m);printf(请输入矩阵的列数(必须小于 10）：);scanf(%d,&n);War(m,n);system(“PAUSE”);return 0;七、实验截图 i.程序启动画面：个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专
25、业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 ii.输入关系矩阵的行数和列数以及关系矩阵的各个元素。iii.得出结果，并打印在屏幕上。个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理
26、数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 八、实验总结 如果当一个集合的元素的个数 n 很大时，求在该集
27、合上的二元关系的可传递闭包是非常复杂的。幸好 Warshall 算法给我们提供了一个求二元关系的可传递闭包的高效方法。结合计算机程序技术，利用 warshall 算法我们可以轻松的求出一个二元关系的可传递闭包。本次实验便捷高效地达到了实验的目的。实验三、编程求一个二元关系的复合运算 一、实验引语：关系作为集合，除了具有一般的运算功能外，还具有自身独个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程
28、学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 特的复合运算。二、数学原理 设 R 是集合 A 到 B 的二元关系，S 是集合 B 到 C 的二元关系，则 R。S=（x，z）A C|(y B)(x，y)R（y，z）S称为 R和 S 的复合关系。三、实验原理：矩阵的运算
29、四、实验环境：Windows 7 Ultimate DEV C+五、实验语言：C 语言 六、实验程序源代码#includestdio.h#includestring.h#define M 3#define N 3#define P 3 main()int i,j,k,x;char p;int ANM,BMP,CNP;printf(关系的复合运算 n);printf(“请输入一个 3*3 的矩阵”);printf(A:n);个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为
30、学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 for(i=1;i=N;i+)for(j=1;j=M;j+)scanf(%4d,&Aij);printf(n);printf(“请输入一个 3*3
31、 的矩阵”);printf(B:n);for(i=1;i=M;i+)for(j=1;j=P;j+)scanf(%4d,&Bij);printf(n);printf(经过复合运算后得到 C:n);for(i=1;i=N;i+)for(j=1;j=P;j+)x=0;for(k=1;k=M;k+)x=x+Aik*Bkj;个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论
32、计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 if(x0)Cij=1;else Cij=0;printf(%4d,Cij);printf(n);system(PAUSE);return 0;七、程序运行截图：i、程序启动截图：ii、程序输入截图:个重要分支也是计算机科学与技术电子信息技术生物技术等的核
33、心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 iii、程序运行结果截图：八
34、、实验总结：本实验利用计算机技术，快速便捷地实现了关系的运算，极大提高了效率。实验四：编程实现拓扑排序算法 一、实验引言 一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成,，任务之间具有先后关系，任务的先后顺序可用有向图表示。个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和
35、严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 二、数学原理：拓扑排序 i）定义：由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。ii）实现方法：从有向图中选择一个没有前驱的顶点并输出它。从网中删去该顶点并删去从该顶点发出的全部有向边。重复上述两步直到剩余的网中不存在没有前驱的顶点。三、实验原理 首先对有向图，我们采取邻接表作为数据结构。
36、且将表头指针改为头结点，其数据域存放该结点的入度，入度设为零的结点即没有前趋。在建立邻接表输入之前，表头向量的每个结点的初始状态为数据域 VEX（入度）为零，指针域 NXET 为空，每输入一条弧 建立链表的一个结点，同时令 k 的入度加 1，因此在输入结束时，表头的两个域分别表示顶点的入度和指向链表的第一个结点指针。在拓扑排序的过程之中，输入入度为零（即没有前趋）的顶点，同时将该顶点的直接后继的入度减 1。（1）、查邻接表中入度为零的顶点，并进栈。（2）、当栈为空时，进行拓扑排序。（a）、退栈，输出栈顶元素 V。（b）、在邻接表中查找 Vj 的直接后继 Vk，将 Vk 的入度减一，并令入度减至
37、零的顶点进栈。（3）、若栈空时输出的顶点数不是 N 个则说明有向回路，否则拓扑排序结束。为建立存放入度为零的顶点的栈，不需要另分配存储单元，即可借入入度为零的数据域。一方面，入度为零的顶点序号即为表头结点的序号，另一方面，借用入度为零的数据域存放带链栈的指针域（下一个入度的顶点号）。四、实验环境：Windows 7 Ultimate DEV C+五、实验语言：C+六、程序源代码#include#include#include#include#include 个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面
38、充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 using namespace std;#define MAX 9999 stackmystack;int i
39、ndegreeMAX;struct node int adjvex;node*next;adjMAX;int Create(node adj,int n,int m)/邻接表建表函数，n 代表定点数，m 代表边数 int i;node*p;for(i=0;i=n-1;i+)adji.adjvex=i;adji.next=NULL;for(i=0;i=m-1;i+)cout 请输入第 iuv;p=new node;p-adjvex=v;p-next=adju.next;adju.next=p;return 1;void print(int n)/邻接表打印函数 int i;node*p;for(
40、i=0;i=n-1;i+)p=&adji;while(p!=NULL)coutadjvex;个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性
41、和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 p=p-next;coutendl;void topsort(node adj,int n)int i;node*p;memset(indegree,0,sizeof(indegree);for(i=0;iadjvex+;p=p-next;for(i=0;i=n-1;i+)if(indegreei=0)mystack.push(i);int count=0;while(mystack.size()!=0)i=mystack.top();mystack.pop();coutin
42、ext)int k=p-adjvex;indegreek-;if(indegreek=0)mystack.push(k);coutendl;if(countn)cout 有回路 endl;个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散
43、数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 int main()int n;int m;cout 拓扑排序算法 endl;coutnm;Create(adj,n,m);cout 输入的邻接表为:endl;print(n);cout 拓扑排序结果为:endl;topsort(adj,n);system(pause);return 0;七、程序运行截图 以下图为例：i、程序启动截图 个重要分支也是计算机科学与技术电子信息技术生物
44、技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 ii、程序输入截图
45、 iii、程序运行结果截图 八、实验总结 通过本次实验掌握拓扑排序的算法，了解拓扑排序的有向图的数据结构。参考文献 1.离散数学 伟森、栾新成、石兵等编著 机械工业 2.C 语言程序设计 良银、游洪跃、旭伟等编著 清华大学 个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及
46、用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看.word 资料 3.C+：面向对象程序设计 涛、游洪跃等编 高等教育 个重要分支也是计算机科学与技术电子信息技术生物技术等的核心基础课程它是研究离散量如整数有理数有限字母表等的数学结构性质及关系的学问它一方面充分地描述了计算机科学离散性的特点为学生进一步学习算法与数据结构 专业课打好数学基础另一方面通过学习离散数学课程学生在获得离散问题建模离散数学理论计算机求解方法和技术知识的同时还以培养和提高抽象思维能力和严密的逻辑推理能力为今后爱念族皮及用计算机处理大量的日常事务和科 离散数学更是必不少的基础理论工具实验一编程判断一个二元关系的性质是否具有自反性反自反性对称性反对称性和传递性一前言引语二元关系是离散数学中重要的容因为事物之间总是以根据需要确定相应的关系从数学的角度来看