CString str1=\Split1.SetSplitFlag(\
Split1.SetSequenceAsOne(TRUE); Split2.SetSplitFlag(\
Split2.SetSequenceAsOne(TRUE); CString m_string1; CString m_string2;
char m_char1[80]; char m_char2[80]; int i; int j; int m=0; int n=0;
int k=0;
this->GetDlgItemText(IDC_EDIT1,m_string1); this->GetDlgItemText(IDC_EDIT2,m_string2); strcpy(m_char1,m_string1); strcpy(m_char2,m_string2); Split1.SetData(m_char1); Split2.SetData(m_char2); int counter=1;
CStringArray array1; CStringArray array2;
Split1.GetSplitStrArray(array1); Split2.GetSplitStrArray(array2); { }
for (j=0;j<=80;j++) { }
for(i=0;i<=m;i++) {
for(j=0;j<=n;j++) if(m_char2[j]==',')
n++; if(m_char1[i]==',')
m++;
for (i=0;i<=80;i++)
13
}
{
if(!strcmp(array1[i],array2[j])) { } }
str1=str1+array1[i]; str1=str1+\
str1.TrimRight(\
str1=str1+\
char *p=new char[1000]; strcpy(p,\∩B=\
strcat(p,str1);
this->SetDlgItemText(IDC_STATICoutput,p);
delete[]p; }
3、编译程序，连调发现程序中存在的问题并修改 四、实验数据及结果分析：
要有实验结果与结果分析 例如：运行结果如下：
? 集合A={1,2,3,4}，集合B={3,4,5,6} 求并：{1,2,3,4}∪{3,4,5,6}={1,2,3,4,5,6} 求交：{1,2,3,4}∩{3,4,5,6}={3,4} 求补：{1,2,3,4}{3,4,5,6}={1,2} ? 集合A={1,2}，集合B={a,b} 求笛卡儿积： A×B={<1,a>,<1,b>,<2,a>,<2,b
五、实验开设方式
本实验开设方式为个人实验；上机2学时； 六、实验思考
在掌握集合运算的基础上，思考如何使用集合的运算来证明集合间的包含、相等和真包含的关系？
14
实验三 求最短路径或平面图的判断
一、实验目的
学习图在计算机中的矩阵表示，并能利用课堂所学知识进行最短路径的计算。 二、实验内容与要求
题目：迷宫最短路径 ⒈问题描述
从一个迷宫的入口到出口找出一条最短路经。用一个二维数组MAZE(1：m，1：n)模拟迷宫，数组元素为0表示该位置可以通过， 数组元素为1表示该位置不可以通行。MAZE(1，1)和MAZE(m，n)分别为迷宫的入口和出口。
⒉基本要求 输入数据
输入迷宫的大小m行和n列，两者为整数 由随机数产生0或1，建立迷宫。 输出数据
首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示：
(m，n)， ??， (I，j)， ??， (1，1) 如无通道，则打印： THERE IS NO PATH. ⒊实现提示 数据结构
a） 为了在程序中判断方便，把迷宫扩展成为MAZE(0：m+1，0：n+1)，扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置(I，j)上都有八个可以移动的方向。
15
b） 用二维数组MOVE(1：8，1：2)存放八个方向上的位置量，如图所示： (I+MOVE[1，1]， j+MOVE[1，2])
(I+MOVE[8，1]， j+MOVE[8，2]) (I+MOVE[1，1]， j+MOVE[1，2])
(I+MOVE[7，1]， j+MOVE[7，2]) (I+MOVE[3，1]， j+MOVE[3，2])
(I+MOVE[6，1]， j+MOVE[6，2]) (I+MOVE[4，1]， j+MOVE[4，2]) (I+MOVE[5，1]， j+MOVE[5，2]) I j 1 2 3 4 5 6 7 8
为了标志已经通过的位置，采用一个标志数组MARK（1..m，1..n）初值为0，在寻找路径的过程中，若通过了位置（I，j），则将MARK（I，J）置为为1。
为了记录查找过程中到达位置及其前一位置，建立一个Q（1..m*n-1， 0..2）数组，对于某一个数组元素Q(P)，其中，Q(P，0)和Q(P，1)记下到达位置I和j，Q(P，2)记下其出
16
1 2 MOVE的设置情况 -1 -1 0 1 1 1 0 -1 0 1 1 1 0 -1 -1 -1 发点在Q数组中的下标。
（2）算法基本思想
将入口（1，1）作为第一个出发点，依次在八个反方向上搜索可通行的位置，形成第一层新的出发点，然后对第一层中各个位置分别搜索他所在八个方向上的可通行位置，形成第二层新的出发点，?，如此进行下去，直至达到出口(m，n)或者迷宫所有位置都搜索完毕为止。
具体实施：从(m，n)开始，将其记入Q数组，比如记入Q(1)，以它作为第一个出发点，依次对八个方向进行搜索，若下一个位置(I，j)可通行并且尚未经过（即MAZE(I，j)=0 且MARK(I，j)=0），则记入Q数组，如记在Q(P)，则在Q(P，2)中要记下其出发点在Q数组中的下标1，在八个方向上都搜索过以后，根据先进先出的原则Q从数组中重新取出一个位置作为新的出发点（这里，我们实际上把Q数组作为一个顺序表示的队列），重复以上过程，若能达到位置(m ，n)，表示找到最短路径；若Q数组中已经没有位置可以作为新的出发点了，则表示迷宫没有通路。
题目:是否是平面图 可以用
定理:::(非平面图判定)(库拉托夫斯基)：一线图为非平面图的充要条件是他包含同胚于K5或K3,3的子图。
来判定，但较复杂。
下面介绍不可分线图平面性的判定 算法思想与原理 -------------------- 1 桥
线图G中选择一回路C，则C将G分为3个部分 用边集表示为3种：
I 回路上顶点在回路内连接的边
II 回路内的顶点与回路上的顶点连接的边
III 回路外的边和回路外的点与回路上的顶点连接的边
G中子图H的桥：H是G的子图(不一定是回路)，若G - E(H) 能表示为若干个I、II、III类边集的直和，则这些I、II、III类边集为桥。
任一桥是连通的；它的任二顶点都有和子图H内部不相交的一条通路相连；除去H上的顶点外，H的任二桥都没有公共顶点。
H的附着点：桥Bh(i)和子图H的公共顶点称为Bh(i)对于H的附着顶点。 2 非平面图的判定
G可容纳的：平面图G有 子图的平面嵌入? 图G的平面嵌入 G不可容纳的：若不存在这样的关系。
可画入：G某子图H的桥B，若他对H的全部附着点都在H嵌入图中的某个面f的周界上，则B是可画入的。F(B,H~)表示桥B在其中可画入的H~的面的集合。
17
不可画入：不都在某一个面的周界上，则是不可画入的。
定理：若H的平面嵌入图是G可容纳的，则对H的每一桥B有，F(B,H~)非空。(也是G是平面图的一个必要条件，可用于非平面判定)
3 平面性算法 算法：
------------------------------------- 有5步组成
1 在G中选一回路G1，并求出G1的一个平面嵌入G1~，置 i = 1
2 若E(G)- E(Gi) = 空，则停止。于是Gi~是G的一个平面嵌入，G是平面图。 否则，确定G中Gi中的所有的桥，并对每一座桥B求出它的可画入的面的集合F(B,Gi~)
3 若有一座桥B，使得F(B,Gi~)=空，则停止。根据定理判定为非平面图。 若有一座桥B，使得|F(B,Gi~)|=1，则取{f}=F(B,Gi~)； 否则，从F(B,Gi~)中任选一个面作为f。
4 在桥B中选一条连接Gi上两个附着顶点的通路Pi，Pi?B，置Gi+1=Gi∪Pi，由Pi在Gi~的面f内的一个画法得到Gi+1的一个平面嵌入Gi+1。
5 换i为i+1，转2 -------------------------------------
三、实验的软硬件环境
PC机一台，装有VC++6.0或其它C语言集成开发环境。
四、实验准备
图可以用多种方式来表示，其中邻接矩阵是一种较简单的方式。复习离散数学教材12.5节中关于邻接矩阵的描述。明确一下内容：
1．如何使用邻接矩阵表示图。
2．利用图的邻接矩阵求结点的出度和入度的方法。 3.利用最短路径算法与平面图的算法
五、实验步骤
1．编写一段代码，接收键盘的输入，并以输入的整数对作为边来建立图形的邻接矩阵graph_matrix。
2．根据第一步得到的邻接矩阵计算每个结点的度数()。 一个结点i的出度等于邻接矩阵第i行之和。
deg_out[i] = graph_matrix[i][0]+ graph_matrix[i][1]+ …+graph_matrix[i][n] 一个结点i的入度等于邻接矩阵第i列之和。
deg_in[i] = graph_matrix[0] [i]+ graph_matrix[1] [i]+ …+graph_matrix[n][i] 3.利用DJKSTR最短路径算法与平面图的判定算法,进行实现.
18