《《离散数学》实验课程指导书.docx》由会员分享，可在线阅读，更多相关《《离散数学》实验课程指导书.docx（46页珍藏版）》请在三一文库上搜索。
1、离散数学实验课程指导书计算机学院目录1 查找与排序2 集合与序列3 关系与函数4 图论5 网络模型实验项目 1查找与排序一、实验目的（ 1）掌握查找的问题描述，实现线性查找算法及二分查找算法；（ 2）熟悉排序的问题描述，实现插入排序算法。二、实验内容1、 线性查找（顺序）算法顺序查找：也称为线性查找，是最基本的查找技术。查找过程是：从表中第一个（或最后一个） 记录开始， 逐个进行记录的关键字和给定值进行比较， 若某个记录的关键字和给定值相等，则查找成功；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找失败。#include <stdio.h>
2、;void main()int a101;/定义数组 a，设置其长度为101int i,n,num;printf("*n");printf("顺 序 查 找 算 法 n");printf("*nn");printf("您要在多少个数中进行线性查找，请输入（1 100）： ");scanf("%d",&n);printf("n");while(n<1 | n>100)/如果输入的数据列表长度不在1,100之间printf("您输入的数不正确！请重新
3、输入。n");printf("您要在多少个数中进行线性查找，请输入（1 100）： ");scanf("%d",&n);printf("请您输入第1 个整数 a1:");scanf("%d",&a1);i=2;while(i<=n)printf("请您输入第 %d个整数 a%d:",i,i);scanf("%d",&ai);i+;printf("n输出数据列表：n");for(i=1; i<=n; i+)pri
4、ntf("%6d",ai);printf("nn");doprintf("请输入要查找的数：");scanf("%d",&num);i=1;while(ai!=num && i<=n)/在数据列表内搜索num i+; if(i=n+1)printf(" 该表中没有您要查找的数据 !n"); elseprintf("您要查找的数是%d，在数据列表中的位序为%d。n",num,i); while (num != 9999);/若输入的待查找的数不是9
5、99，则可持续搜索。2、 二分查找算法折半查找（ Binary Search ）：也称为二分查找。它的前提是：1)、线性表中的记录必须是关键字有序（通常是从小到大有序）； 2)、线性表必须采用顺序存储。折半查找的基本思想是：在有序表中， 取中间记录作为比较对象，若给定值与中间记录的关键字相等， 则查找成功； 若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断反复， 直到查找成功；或者直到最后都没有找到，查找失败。mid 计算公式： mid = (low + high) / 2 = low + (high - low) /
6、 2;#include <stdio.h>void main()int a101;int i,n,num ;int Top,Bottom ,Mid;int flag=1; / 如果在列表中找到数字，则值为1，否则为 0int loc=-1;/ 要查找的数在列表中的位置，如果 loca=-1 表示列表中没有这个数;如果有这个数 ,则它的值为所在的位置printf("*n");printf("折 半 查 找 算 法n");printf("*nn");printf(" 您要在多少个数中进行折半查找，请输入（1 100）
7、：");scanf("%d",&n);printf("n");while(n<1 | n>100)/ 如果输入的数据列表长度不在1,100 之间printf("您输入的数不正确！请重新输入。n");printf(" 您要在多少个数中进行折半查找，请输入（1 100）：");scanf("%d",&n);printf(" 请您输入第1 个整数 a1:");scanf("%d",&a1);i=2;while(i&l
8、t;=n)/输入从小到大的表列printf(" 请您输入第 %d 个整数 a%d:",i,i);scanf("%d",&ai);if(ai > ai-1)i+;elseprintf(" 您输入的数不满足升序要求，请重新输入!n");printf("n 输出数据列表：n");for(i=1; i<=n; i+)printf("%6d",ai);printf("nn");doprintf(" 请输入要查找的数：");scanf("
9、%d",&num);flag=1; / 假设输入的数在列表中Top=n;Bottom=1;Mid=(Top+Bottom)/2;while(flag)printf("Bottom=%2d, Top=%2d, Mid=%2d, a%2d=%2dn",Bottom,Top,Mid,Mid,aMid);if( (num>aTop)| (num<aBottom)/输入的数num>aTop或者num<aBottom ，肯定num 不在这个列表中loc=-1;flag=0;else if(aMid=num)/ 如果 num 等于找到的数loc=
10、Mid;printf(" 找到数%d 的位置 %2dnn",num,loc);break;else if(aMid>num)/若 aMid>num ，则 num 一定在aBottom 和 aMid-1 范围之内Top=Mid-1;Mid=(Top+Bottom)/2;else if(aMid<num) /若 aMid<num ，则 num 一定在aMid+1 和 aTop 范围之内Bottom=Mid+1;Mid=(Top+Bottom)/2;if(loc=-1)printf("%d这个数在列表中没有找到。nn",num); wh
11、ile (num != 9999);/若输入的待查找的数不是999，则可持续搜索。3、 插入排序算法放直接插入排序是一种插入排序。前提：数组元素 n 个待排序的元素。a0 用作哨兵或临时变量，a1an存基本思想是：从 a2 开始，将元素插入到前面已经排好序的有序表中，从而得到一个新的、记录数增加 1 的有序表。#include<stdio.h>void main()int a101;int i,j,k,l,m;printf("*n");printf("插 入 排 序 算 法 n");printf("*nn");printf
12、(" 请输入数据列表长度：n");scanf("%d",&l);printf("n 请输入 %d 个数字： n",l);for(i=0;i<l;i+)scanf("%d",&ai);for(i=1;i<l;i+)k=ai;j=i-1;while(j>=0)&&(aj>k)aj+1=aj;j-;aj+1=k;printf("n 第 %d 次插入排序后全部数据为：n",i);for(m=0;m<l;m+)printf("%d &
13、quot;,am);printf("nn按照插入排序法，你输入的数据由小到大排序为：n");for(i=0;i<l;i+)printf("%d ",ai);printf("n");4、 冒泡排序算法#include<stdio.h>void main()int a101;int i,j,k,l,m;int exchanged;printf("*n");printf("冒 泡 排 序 算 法 n");printf("*nn");printf(" 请输
14、入数据列表长度：n");scanf("%d",&l);printf("n 请输入 %d 个数字： n",l);for(i=0;i<l;i+)scanf("%d",&ai);i=0;doexchanged=0;for(j=0;j<l-1-i;j+)if(aj>aj+1)k=aj;aj=aj+1;aj+1=k;exchanged=1;if (i=0)printf("n");printf(" 第 %d 趟冒泡排序法由小到大排序后:n",i+1);for(m=
15、0;m<l;m+)printf("%d",am);printf(" ");printf("n");i+; while (i<l-1 && exchanged=1);5、 线性查找算法#include"stdio.h"#include"stdlib.h"typedef struct Node int r50; int length;list,*sqlist;int CreateSqlist(sqlist s)int i;printf(" 请输入您要进行搜索的数
16、据队列的长度:n");scanf("%d",&(s->length);printf("n请输入您要进行搜索的%d个数据:n",s->length);for(i=0;i<s->length;i+)scanf("%d",&(s->ri);printf("n");printf(" 您所输入的数据为:n");for(i=0;i<s->length;i+)printf("%-5d",s->ri);printf(&
17、quot;nn");return 1; int SearchSqlist(sqlist s,int k)int i=0;s->rs->length=k;while(s->ri!=k)i+;if(i=s->length)printf(" 该表中没有您要查找的数据！n");return -1;elsereturn i+1;sqlist Initlist()sqlist p;p=(sqlist)malloc(sizeof(list);if(p)return p;elsereturn NULL; main()int keyplace,keynum;
18、sqlist T;printf("*n");printf("线 性 查 找 算法n");printf("*nn");T=Initlist();CreateSqlist(T);printf(" 请输入您想要查找的数据的关键字:n");scanf("%d",&keynum);printf("n");keyplace=SearchSqlist(T,keynum);printf(" 您要查找的数据的位置为:n%dnn",keyplace);实验项目 2集合
19、与序列一、实验目的（ 1）掌握并实现判定序列 A 是否为 B 的子序列的算法；（ 2）掌握并实现两个矩阵相乘的算法。二、 实验内容1、子序列的判定算法问题描述：两个整数序列A=a1,a2,a3,.,am 和 B=b1,b2,b3,.,bn 已经存入两个单链表中，设计一个算法，判断序列B 是否是序列A 的连续子序列。算法思想：因为此题需要判断序列B 是否为序列A 的子序列，即单链表B 中所有连续结点的数据域的值是否在A 中能够找到同样连续的一部分。既然如此，那么我们可以从两个链表的第一个结点开始，若对应的数据相等，则后移指针；最后判断下单链表B 是否彻底遍历完成，如果完成，则表示单链表B 是单链
20、表A 的一个子序列；如果没有遍历完成，则表示单链表B 不是单链表A 的一个子序列。#include <stdio.h>#include <string.h>int Subsequence(char s, char t)int m,n,i,j;n=strlen(s);m=strlen(t);/n/m表示序列表示序列S 的长度T 的长度i=0;j=0;if (m>n)return 0;while (i<m) && (j<n)if(sj = ti) / 序列 T 中第 i 个元素与序列 S 中第 j 个元素相等 i=i+1;j=j+1;if
21、(i=m)return 1;/T是 S 的子序列return 0;void main()char s30,t30;int n,m;printf("*n");printf(" 子 序 列 判 定 算 法 n"); printf("*nn");printf("您要在多少组序列中进行判定，请输入（1 100）： ");scanf("%d",&n);printf("n");m=1;while(n-)printf("请输入第 %d组待匹配序列S：",m);s
22、canf("%s",s);printf("请输入第 %d组待匹配序列T：",m);scanf("%s",t);if(Subsequence(s,t) = 1)printf("序列 T（ %s）是序列S（ %s）的子序列。nn",t,s);elseprintf(" 序列 T（ %s）不是序列 S（ %s）的子序列。 nn",t,s); m+;2、 矩阵相乘算法问题描述：实现m*n 矩阵和 n*p 矩阵相乘。 m,n,p分析：首先我们可以根据题意写出函数头。可以定为均小于 10，矩阵元素为整数。vo
23、idMatrixMutiply(intm,intn,intp,longlMatrix1MAXMAX,longlMatrix2MAXMAX,long lMatrixResultMAXMAX)，其中 lMatrix1和 lMatrix2分别是输入的m*n矩阵和 n*p 矩阵，lMatrixResult是输出的 m*p矩阵。因为 m，n 和 p 都是未知量， 要进行处理的矩阵大小是变量。但我们可以定义比较大的二维数组， 只使用其中的部分数组元素。矩阵相乘的算法比较简单，输入一个m*n 矩阵和一个n*p 矩阵，结果必然是m*p 矩阵，有 m*p 个元素，每个元素都需要计算，可以使用m*p 嵌套循环进行
24、计算。根据矩阵乘法公式：可以用循环直接套用上面的公式计算每个元素。嵌套循环内部进行累加前，一定要注意对累加变量进行清零。1)输入两个矩阵的的行列数m,n,p；2)输入第一个矩阵的每个元素；3)输入第二个矩阵的每个元素；4)调用函数进行乘法运算，结果放在lMatrixResult中；5.) 打印输出结果矩阵。#define MAX 10void MatrixMutiply(int m,int n,int p,long lMatrix1MAXMAX,long lMatrix2MAXMAX,long lMatrixResultMAXMAX)int i,j,k;long lSum;/* 嵌套循环计算结
25、果矩阵（m*p ）的每个元素*/for(i=0;i<m;i+)for(j=0;j<p;j+)/* 按照矩阵乘法的规则计算结果矩阵的i*j元素 */lSum=0;for(k=0;k<n;k+)lSum+=lMatrix1ik*lMatrix2kj;lMatrixResultij=lSum;main()long lMatrix1MAXMAX,lMatrix2MAXMAX;long lMatrixResultMAXMAX,lTemp;int i,j,m,n,p;/* 输入两个矩阵的的行列数m,n,p*/printf("nPlease input m of Matrix1:
26、n");scanf("%d",&m);printf("Please input n of Matrix1:n");scanf("%d",&n);printf("Please input p of Matrix2:n");scanf("%d",&p);/*printf("nPlease elements of Matrix1(%d*%d):n",m,n);输入第一个矩阵的每个元素*/for(i=0;i<m;i+)for(j=0;j<
27、n;j+)scanf("%ld",&lTemp);lMatrix1ij=lTemp;/* 输入第二个矩阵的每个元素*/printf("nPlease elements of Matrix2(%d*%d):n",n,p);for(i=0;i<n;i+)for(j=0;j<p;j+)scanf("%ld",&lTemp);lMatrix2ij=lTemp;/* 调用函数进行乘法运算，结果放在lMatrixResultMatrixMutiply(m,n,p,lMatrix1,lMatrix2,lMatrixRes
28、ult);/*printf("nResult matrix: n");for(i=0;i<m;i+)中 */打印输出结果矩阵*/for(j=0;j<p;j+)printf("%ld ",lMatrixResultij);printf("n");实验项目 3关系与函数一、 实验目的（ 1）掌握并实现关系的复合运算R?S 的算法；（ 2）熟悉偏序关系的定义，验证相应的性质判定算法。二、 实验内容1、 关系的复合运算复合运算能由两个二元关系生成一个新的二元关系。设则称 X Z(R?S 关系 ) 为 R 和 S 的复合关系，并规定
29、为：<x,y> R <y,z> S)。X Y(R 关系 ) ， YZ(S 关系 ) ，R?S=<x,z>|x Xz Z ? y(y Y关系可用矩阵表示，故复合运算也可用矩阵表示。设有三个集合：X=x1,x2xm ，Y=y1,y2yn ， Z=z1,z 2zp,X Y Z ， |X|=m ， |Y|=n ， |Z|=p ， MR=aikm×n ，MS=akjn ×p 则复合关系R?S 的关系矩阵为：MR?S= MR?MS=cijm ×p 。实现关系的复合运算R?S 的算法， 就是将二元关系用关系矩阵表示，通过两个关系矩阵对应行列元
30、素先进行逻辑乘，后进行逻辑加生成新的关系矩阵中的每一个元素。新的关系矩阵所对应的二元关系就是两个二元关系复合形成的，编程实现这一复合过程。#include <stdio.h>#define MAX 10void GetCompositiveRelation(int m,int n,int l,int MatrixAMAXMAX, int MatrixBMAXMAX,int MatrixResultMAXMAX)int i,j,k;int lSum;/嵌套循环计算结果矩阵（m*l ）的每个元素for(i=0;i<m;i+)for(j=0;j<l;j+)lSum=0;for
31、(k=0;k<n;k+)lSum+=MatrixAik*MatrixBkj;MatrixResultij=lSum;/ 矩阵乘积中每个非零项用 1 替换后，就可得到关系复合的矩阵if (MatrixResultij>0)MatrixResultij=1;void main()int MatrixAMAXMAX,MatrixBMAXMAX;int MatrixResultMAXMAX,Temp;int i,j,m,n,l;char *s,*t;printf("*n");printf("复 合 关 系 算 法 n");printf("*
32、nn");printf("集合 X = 学生 A，学生 B，学生 C;nY = 离散数学，数据结构;nZ = 教室 A，教室 B; n");printf("R为从 X 到 Y 的关系， S 为从 Y到 Z 的关系。 nn");/ 输入两个矩阵的的行列数 m,n,lprintf("请输入关系 R 对应的矩阵 MatrixA的行数 m: ");scanf("%d",&m);printf("请输入关系 R 对应的矩阵 MatrixA的列数 n: ");scanf("%d&q
33、uot;,&n);printf("请输入关系S 对应的矩阵MatrixB的列数 l: ");scanf("%d",&l);/输入第一个矩阵的每个元素printf("n请输入矩阵MatrixA(%d*%d) 的元素 :n",m,n);for(i=0;i<m;i+)for(j=0;j<n;j+)scanf("%d",&Temp);MatrixAij=Temp; /printf("n请输入矩阵输入第二个矩阵的每个元素MatrixB(%d*%d) 的元素 :n",n,
34、l);for(i=0;i<n;i+)for(j=0;j<l;j+)scanf("%d",&Temp);MatrixBij=Temp;/输出关系R 中所有的序偶printf("n关系 R=");for(i=0;i<m;i+)for(j=0;j<n;j+)if (i=0)s="学生 A"else if (i=1)s="学生 B"elses="学生 C"if (j=0)t="离散数学 "elset="数据结构 "if (Matri
35、xAij=1)printf("(");printf("%s,%s", s, t);printf(") , ");printf("bbn");/输出关系S 中所有的序偶printf("n关系S=");for(i=0;i<n;i+)for(j=0;j<l;j+)if (i=0)s="离散数学"elses="数据结构" ;if (j=0)t="教室A"elset="教室 B"if (MatrixBij=1)pr
36、intf("(");printf("%s,%s",s,t);printf(") , ");printf("bbn");/ 调用函数进行乘法运算，结果放在MatrixResult中GetCompositiveRelation(m,n,l,MatrixA,MatrixB,MatrixResult);/ 打印输出结果矩阵printf("n矩阵相乘的结果MatrixResult为 : n");for(i=0;i<m;i+)for(j=0;j<l;j+)printf("%-4d &q
37、uot;,MatrixResultij);printf("n");/输出关系R 和 S 复合运算后，结果中的所有序偶printf("n关系 R·S = ");for(i=0;i<m;i+)for(j=0;j<l;j+)if (i=0)s="学生 A"else if (i=1)s="学生 B"elses="学生 C"if (j=0)t="教室 A"elset="教室 B"if (MatrixResultij=1)printf("
38、;(");printf("%s,%s",s,t);printf(") , ");printf("bbnn");2、 关系性质判定算法利用 C 语言程序实现判断任意一个二元关系是否具有自反性、反自反性、对称性、 反对称性、传递性。设 RA×A ： 1)若 x(x A xRx) ，称 R 是自反的 2)若 x(x AxRx) ，称 R是反自反的3) 若 xy(x 、 y A xRyyRx) ，称 R 是对称的4) 若xy(x 、 y A xRy x yyRx) ，称 R 是反对称的 5)若 x yz(x 、y、 z A xRy yRzxRz) ，称 R是传递的 6)若 R 是自反的、对称的和传递的，则称R 是等价关系。