《离散数学》实验课程指导书.doc

《离散数学》实验课程

指

导

书

计算机学院

目 录
1 查找与排序
2 集合与序列
3 关系与函数
4 图论
5 网络模型

实验项目1 查找与排序

一、实验目的
（1）掌握查找的问题描述，实现线性查找算法及二分查找算法；
（2）熟悉排序的问题描述，实现插入排序算法。
二、实验内容
1、 线性查找（顺序）算法
顺序查找：也称为线性查找，是最基本的查找技术。查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找失败。
#include <stdio.h>
void main()
{
int a[101]; //定义数组a，设置其长度为101
int i,n,num;
printf("**************************************************\n");
printf(" 顺 序 查 找 算 法\n");
printf("**************************************************\n\n");
printf("您要在多少个数中进行线性查找，请输入（1～100）：");
scanf("%d",&n);
printf("\n");
while(n<1 || n>100) //如果输入的数据列表长度不在[1,100]之间
{
printf("您输入的数不正确！请重新输入。\n");
printf("您要在多少个数中进行线性查找，请输入（1～100）：");
scanf("%d",&n);
}

printf("请您输入第1个整数a[1]:");
scanf("%d",&a[1]);
i=2;
while(i<=n)
{
printf("请您输入第%d个整数a[%d]:",i,i);
scanf("%d",&a[i]);
i++;
}

printf("\n输出数据列表：\n");
for(i=1; i<=n; i++)
{
printf("%6d",a[i]);
}
printf("\n\n");

do
{
printf("请输入要查找的数：");
scanf("%d",&num);
i=1;
while(a[i]!=num && i<=n) //在数据列表内搜索num
{ i++; }
if(i==n+1)
printf("该表中没有您要查找的数据!\n");
else
printf("您要查找的数是%d，在数据列表中的位序为%d。\n",num,i);
} while (num != 9999); //若输入的待查找的数不是999，则可持续搜索。
}

2、 二分查找算法
折半查找（Binary Search）：也称为二分查找。它的前提是：1)、线性表中的记录必须是关键字有序（通常是从小到大有序）；2)、线性表必须采用顺序存储。
折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断反复，直到查找成功；或者直到最后都没有找到，查找失败。
mid计算公式：mid = (low + high) / 2 = low + (high - low) / 2;
#include <stdio.h>
void main()
{
int a[101];
int i,n,num ;
int Top,Bottom ,Mid;
int flag=1; //如果在列表中找到数字，则值为1，否则为0
int loc=-1;//要查找的数在列表中的位置，如果loca=-1表示列表中没有这个数;如果有这个数,则它的值为所在的位置
printf("**************************************************\n");
printf(" 折 半 查 找 算 法\n");
printf("**************************************************\n\n");
printf("您要在多少个数中进行折半查找，请输入（1～100）：");
scanf("%d",&n);
printf("\n");
while(n<1 || n>100) //如果输入的数据列表长度不在[1,100]之间
{
printf("您输入的数不正确！请重新输入。\n");
printf("您要在多少个数中进行折半查找，请输入（1～100）：");
scanf("%d",&n);
}

printf("请您输入第1个整数a[1]:");
scanf("%d",&a[1]);
i=2;
while(i<=n) //输入从小到大的表列
{
printf("请您输入第%d个整数a[%d]:",i,i);
scanf("%d",&a[i]);
if(a[i] > a[i-1])
i++;
else
printf("您输入的数不满足升序要求，请重新输入!\n"); }

printf("\n输出数据列表：\n");
for(i=1; i<=n; i++)
{
printf("%6d",a[i]);
}
printf("\n\n");

do
{
printf("请输入要查找的数：");
scanf("%d",&num);
flag=1; //假设输入的数在列表中
Top=n;
Bottom=1;
Mid=(Top+Bottom)/2;
while(flag)
{
printf("Bottom=%2d, Top=%2d, Mid=%2d, a[%2d]=%2d\n",Bottom,Top,Mid,Mid,a[Mid]);
if( (num>a[Top]) || (num<a[Bottom]) ) //输入的数 num>a[Top] 或者 num<a[Bottom]，肯定num不在这个列表中
{
loc=-1;
flag=0;
}
else if(a[Mid]==num) //如果num 等于找到的数
{
loc=Mid;
printf("找到数 %d 的位置%2d\n\n",num,loc);
break;
}
else if(a[Mid]>num) //若 a[Mid]>num，则num 一定在 a[Bottom]和a[Mid-1]范围之内
{
Top=Mid-1;
Mid=(Top+Bottom)/2;
}
else if(a[Mid]<num) //若 a[Mid]<num，则num 一定在 a[Mid+1]和a[Top]范围之内
{
Bottom=Mid+1;
Mid=(Top+Bottom)/2;
}
}
if(loc==-1)
{
printf("%d 这个数在列表中没有找到。\n\n",num);
}
} while (num != 9999); //若输入的待查找的数不是999，则可持续搜索。
}

3、 插入排序算法
直接插入排序是一种插入排序。前提：数组元素a[0]用作哨兵或临时变量，a[1]~a[n]存放n个待排序的元素。
基本思想是：从a[2]开始，将元素插入到前面已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。
#include<stdio.h>
void main()
{
int a[101];
int i,j,k,l,m;
printf("****************************************\n");
printf(" 插 入 排 序 算 法\n");
printf("****************************************\n\n");
printf("请输入数据列表长度：\n");
scanf("%d",&l);
printf("\n请输入%d个数字：\n",l);
for(i=0;i<l;i++)
scanf("%d",&a[i]);
for(i=1;i<l;i++)
{
k=a[i];
j=i-1;
while((j>=0)&&(a[j]>k))
{
a[j+1]=a[j];
j--;
}
a[j+1]=k;
printf("\n第%d次插入排序后全部数据为：\n",i);
for(m=0;m<l;m++)
{
printf("%d ",a[m]);
}
}
printf("\n\n按照插入排序法，你输入的数据由小到大排序为：\n");
for(i=0;i<l;i++)
{printf("%d ",a[i]);
}
printf("\n");
}

4、 冒泡排序算法
#include<stdio.h>
void main( )
{
int a[101];
int i,j,k,l,m;
int exchanged;
printf("****************************************\n");
printf(" 冒 泡 排 序 算 法\n");
printf("****************************************\n\n");
printf("请输入数据列表长度：\n");
scanf("%d",&l);
printf("\n请输入%d个数字：\n",l);
for(i=0;i<l;i++)
scanf("%d",&a[i]);
i=0;
do
{
exchanged=0;
for(j=0;j<l-1-i;j++)
if(a[j]>a[j+1])
{
k=a[j];
a[j]=a[j+1];
a[j+1]=k;
exchanged=1;
}
if (i==0)
printf("\n");
printf("第%d趟冒泡排序法由小到大排序后:\n",i+1);
for(m=0;m<l;m++)
{printf("%d",a[m]);
printf(" ");
}
printf("\n");
i++;
} while (i<l-1 && exchanged==1);
}

5、 线性查找算法
#include"stdio.h"
#include"stdlib.h"
typedef struct Node
{ int r[50];
int length;
}list,*sqlist;
int CreateSqlist(sqlist s)
{
int i;
printf("请输入您要进行搜索的数据队列的长度:\n");
scanf("%d",&(s->length));
printf("\n请输入您要进行搜索的%d个数据:\n",s->length);
for(i=0;i<s->length;i++)
scanf("%d",&(s->r[i]));
printf("\n");
printf("您所输入的数据为:\n");
for(i=0;i<s->length;i++)
printf("%-5d",s->r[i]);
printf("\n\n");
return 1; }
int SearchSqlist(sqlist s,int k)
{
int i=0;
s->r[s->length]=k;
while(s->r[i]!=k)
{
i++;
}
if(i==s->length)
{
printf("该表中没有您要查找的数据！\n");
return -1; }
else
return i+1;
}
sqlist Initlist()
{
sqlist p;
p=(sqlist)malloc(sizeof(list));
if(p)
return p;
else
return NULL; }
main()
{
int keyplace,keynum;
sqlist T;
printf("****************************************\n");
printf(" 线 性 查 找 算 法 \n");
printf("****************************************\n\n");
T=Initlist();
CreateSqlist(T);
printf("请输入您想要查找的数据的关键字:\n");
scanf("%d",&keynum);
printf("\n");
keyplace=SearchSqlist(T,keynum);
printf("您要查找的数据的位置为:\n%d\n\n",keyplace);
}

实验项目2 集合与序列
一、实验目的
（1）掌握并实现判定序列A是否为B的子序列的算法；
（2）掌握并实现两个矩阵相乘的算法。
二、 实验内容
1、子序列的判定算法
问题描述：两个整数序列A=a1,a2,a3,...,am和B=b1,b2,b3,...,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子序列。
算法思想：因为此题需要判断序列B是否为序列A的子序列，即单链表B中所有连续结点的数据域的值是否在A中能够找到同样连续的一部分。既然如此，那么我们可以从两个链表的第一个结点开始，若对应的数据相等，则后移指针；最后判断下单链表B是否彻底遍历完成，如果完成，则表示单链表B是单链表A的一个子序列；如果没有遍历完成，则表示单链表B不是单链表A的一个子序列。
#include <stdio.h>
#include <string.h>
int Subsequence(char s[], char t[])
{
int m,n,i,j;
n=strlen(s); //n表示序列S的长度
m=strlen(t); //m表示序列T的长度
i=0;
j=0;
if (m>n)
return 0;
while ((i<m) && (j<n))
{
if(s[j] == t[i]) //序列T中第i个元素与序列S中第j个元素相等
i=i+1;
j=j+1;
}
if (i==m)
return 1; //T是S的子序列
return 0;
}
void main()
{
char s[30],t[30];
int n,m;
printf("**************************************************\n");
printf(" 子 序 列 判 定 算 法\n");
printf("**************************************************\n\n");
printf("您要在多少组序列中进行判定，请输入（1～100）：");
scanf("%d",&n);
printf("\n");
m=1;
while(n--)
{
printf("请输入第%d组待匹配序列S：",m);
scanf("%s",s);
printf("请输入第%d组待匹配序列T：",m);
scanf("%s",t);
if(Subsequence(s,t) == 1)
printf("序列T（%s）是序列S（%s）的子序列。\n\n",t,s);
else
printf("序列T（%s）不是序列S（%s）的子序列。\n\n",t,s);
m++;
}
}

2、 矩阵相乘算法
问题描述：实现m*n矩阵和n*p矩阵相乘。m,n,p均小于10，矩阵元素为整数。
分析：首先我们可以根据题意写出函数头。可以定为void MatrixMutiply(int m,int n,int p,long lMatrix1[MAX][MAX],long lMatrix2[MAX][MAX], long lMatrixResult[MAX][MAX])，其中lMatrix1和lMatrix2分别是输入的m*n矩阵和n*p矩阵，lMatrixResult是输出的m*p矩阵。
因为m，n和p都是未知量，要进行处理的矩阵大小是变量。但我们可以定义比较大的二维数组，只使用其中的部分数组元素。矩阵相乘的算法比较简单，输入一个m*n矩阵和一个n*p矩阵，结果必然是m*p矩阵，有m*p个元素，每个元素都需要计算，可以使用m*p嵌套循环进行计算。根据矩阵乘法公式：

可以用循环直接套用上面的公式计算每个元素。嵌套循环内部进行累加前，一定要注意对累加变量进行清零。
1)．输入两个矩阵的的行列数m,n,p；
2)．输入第一个矩阵的每个元素；
3)．输入第二个矩阵的每个元素；
4)．调用函数进行乘法运算，结果放在lMatrixResult 中；
5.) 打印输出结果矩阵。
#define MAX 10
void MatrixMutiply(int m,int n,int p,long lMatrix1[MAX][MAX],
long lMatrix2[MAX][MAX],long lMatrixResult[MAX][MAX])
{
int i,j,k;
long lSum;/*嵌套循环计算结果矩阵（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+=lMatrix1[i][k]*lMatrix2[k][j];
lMatrixResult[i][j]=lSum;
}
}
main()
{
long lMatrix1[MAX][MAX],lMatrix2[MAX][MAX];
long lMatrixResult[MAX][MAX],lTemp;
int i,j,m,n,p;/*输入两个矩阵的的行列数m,n,p*/
printf("\nPlease input m of Matrix1:\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<n;j++)
{
scanf("%ld",&lTemp);
lMatrix1[i][j]=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);
lMatrix2[i][j]=lTemp;
}/*调用函数进行乘法运算，结果放在lMatrixResult 中*/
MatrixMutiply(m,n,p,lMatrix1,lMatrix2,lMatrixResult);/*打印输出结果矩阵*/
printf("\nResult matrix: \n");
for(i=0;i<m;i++)
{
for(j=0;j<p;j++)
printf("%ld ",lMatrixResult[i][j]);
printf("\n");
}
}

实验项目3 关系与函数
一、 实验目的
（1）掌握并实现关系的复合运算R◦S的算法；
（2）熟悉偏序关系的定义，验证相应的性质判定算法。
二、 实验内容
1、 关系的复合运算
复合运算能由两个二元关系生成一个新的二元关系。设X→Y(R关系)，Y→Z(S关系)，则称X→Z(R◦S关系)为R和S的复合关系，并规定为：R◦S={<x,z>|x∈X∧z∈Z∧∃y(y∈Y∧<x,y>∈R∧<y,z>∈S)} 。
关系可用矩阵表示，故复合运算也可用矩阵表示。设有三个集合：X={x1,x2… xm}，Y={y1,y2…yn}，Z={z1,z2…zp}, X→Y→Z，|X|=m，|Y|=n，|Z|=p，MR=[aik]m×n，MS=[akj]n×p则复合关系R◦S的关系矩阵为：MR◦S= MR◦MS=[cij]m×p 。
实现关系的复合运算R◦S的算法，就是将二元关系用关系矩阵表示，通过两个关系矩阵对应行列元素先进行逻辑乘，后进行逻辑加生成新的关系矩阵中的每一个元素。新的关系矩阵所对应的二元关系就是两个二元关系复合形成的，编程实现这一复合过程。
#include <stdio.h>
#define MAX 10
void GetCompositiveRelation(int m,int n,int l,int MatrixA[MAX][MAX],
int MatrixB[MAX][MAX],int MatrixResult[MAX][MAX])
{
int i,j,k;
int lSum;//嵌套循环计算结果矩阵（m*l）的每个元素
for(i=0;i<m;i++)
for(j=0;j<l;j++)
{
lSum=0;
for(k=0;k<n;k++)
lSum+=MatrixA[i][k]*MatrixB[k][j];
MatrixResult[i][j]=lSum;
//矩阵乘积中每个非零项用1替换后，就可得到关系复合的矩阵
if (MatrixResult[i][j]>0)
MatrixResult[i][j]=1;
}
}
void main()
{
int MatrixA[MAX][MAX],MatrixB[MAX][MAX];
int MatrixResult[MAX][MAX],Temp;
int i,j,m,n,l;
char *s,*t;
printf("**************************************************\n");
printf(" 复 合 关 系 算 法\n");
printf("**************************************************\n\n");
printf("集合 X = {学生A，学生B，学生C};\nY = {离散数学，数据结构};\nZ = {教室A，教室B}; \n");
printf("R为从X到Y的关系，S为从Y到Z的关系。\n\n");
//输入两个矩阵的的行列数m,n,l
printf("请输入关系R对应的矩阵MatrixA的行数m: ");
scanf("%d",&m);
printf("请输入关系R对应的矩阵MatrixA的列数n: ");
scanf("%d",&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);
MatrixA[i][j]=Temp; }//输入第二个矩阵的每个元素
printf("\n请输入矩阵MatrixB(%d*%d)的元素:\n",n,l);
for(i=0;i<n;i++)
for(j=0;j<l;j++)
{
scanf("%d",&Temp);
MatrixB[i][j]=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";
else
s="学生C";
if (j==0)
t="离散数学";
else
t="数据结构";
if (MatrixA[i][j]==1)
{
printf("(");
printf("%s,%s", s, t);
printf(") , ");
}
}
printf("\b\b}\n");//输出关系S中所有的序偶
printf("\n关系 S = { ");
for(i=0;i<n;i++)
for(j=0;j<l;j++)
{
if (i==0)
s="离散数学";
else
s="数据结构"; ;
if (j==0)
t="教室A";
else
t="教室B";
if (MatrixB[i][j]==1)
{
printf("(");
printf("%s,%s",s,t);
printf(") , ");
}
}
printf("\b\b}\n");
//调用函数进行乘法运算，结果放在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 ",MatrixResult[i][j]);
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";
else
s="学生C";
if (j==0)
t="教室A";
else
t="教室B";
if (MatrixResult[i][j]==1)
{
printf("(");
printf("%s,%s",s,t);
printf(") , ");
}
}
printf("\b\b}\n\n");
}

2、 关系性质判定算法
利用C语言程序实现判断任意一个二元关系是否具有自反性、反自反性、对称性、 反对称性、传递性。
设RÍ A×A： 1) 若x(x∈A®xRx)，称R是自反的 2) 若x(x∈A®ØxRx)，称R是反自反的 3) 若xy(x、y∈A∧xRy®yRx)，称R是对称的 4) 若"xy(x、y∈A∧xRy∧x≠y®ØyRx)，称R是反对称的 5) 若xyz(x、y、z∈A∧xRy∧yRz®xRz)，称R是传递的 6) 若R是自反的、对称的和传递的，则称R是等价关系。
#include <stdio.h>
#include <stdlib.h>
//确定集合及矩阵大小，分配空间
void Init(char ***a, int *len)
{
int i,n;
printf("请输入集合A的基数n：");
do
{ scanf("%d",&n);
if(n<=1)
printf("n应该大于1,请重新输入： ");
}while(n<=1);
printf("集合A中的元素默认为：");
for(i=1;i<=n;i++)
{
if (i<n)
printf("%d, ",i);
else
printf("%d\n",i);
}
*len=n;
(*a)=(char **)malloc(sizeof(char*)*n);
if((*a)==NULL)
{
printf("malloc error\n");
return;
}
for(i=0;i<n;i++)
{
(*a)[i]=(char*)malloc(sizeof(char)*n);
if((*a)[i]==NULL)
{
printf("malloc error\n");
return ;
} }
}//输入关系中的序偶
void Input(char **a,int n)
{ int x,y;
printf("\n请输入关系中的序偶,使用\",\"分开,例如1,2，完成后输入0,0退出\n");
for(;;)
{
scanf("%d,%d",&x,&y);
if(x<=0 || x>n || y<=0 || y>n)
break;
a[x-1][y-1]=1;
}
}//具备自反性返回1，否则0
int IsSelf(char **a,int n)
{
int i;
for(i=0;i<n;i++)
{
if(a[i][i]==0)
return 0;
}
return 1;
}//具备反自反性返回1，否则0
int IsAntiSelf(char **a,int n)
{
int i;
for(i=0;i<n;i++)
{
if(a[i][i]==1)
return 0;
}
return 1;}//具备对称性返回1，否则0
int IsSym(char **a,int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
if(a[i][j]!=a[j][i])
return 0;
}
}
return 1;}//具备反对称性返回1，否则0
int IsAntiSym(char **a,int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
if(a[i][j]==1 && a[j][i]==1)
return 0;
}
}
return 1;
}//具备传递性返回1，否则0
int IsTran(char **a,int n)
{
int i,j,k;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
for(k=0; k<n;k++)
{
if(a[i][j]==1 && a[j][k]==1 && a[i][k]==0)
return 0;
}
}
}
return 1;}//显示关系性质的判定结果
void Show(char** a,int n)
{
char b[5];
b[0]=IsSelf(a,n);
b[1]=IsAntiSelf(a,n);
b[2]=IsSym(a,n);
b[3]=IsAntiSym(a,n);
b[4]=IsTran(a,n);

if(b[0]==1)
printf("关系R具有自反性\n");
else
printf("关系R不具有自反性\n");
if(b[1]==1)
printf("关系R具有反自反性\n");
else
printf("关系R不具有反自反性\n");
if(b[2]==1)
printf("关系R具有对称性\n");
else
printf("关系R不具有对称性\n");
if(b[3]==1)
printf("关系R具有反对称性\n");
else
printf("关系R不具有反对称性\n");
if(b[4]==1)