Skip to content

Instantly share code, notes, and snippets.

@bcho

bcho/gist:6804046

Forked from anonymous/gist:6803900
Created October 3, 2013 02:52
Show Gist options
  • Save bcho/6804046 to your computer and use it in GitHub Desktop.
Save bcho/6804046 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
gistfile1.txt
2.16③ 已知指针la和lb分别指向两个无头结点单链表中
的首元结点。 下列算法是从表la中删除自第i个元素起共
len个元素后，将它们插入到表lb中第i个元素之前。试问
此算法是否正确? 若有错，则请改正之。
实现下列函数：
Status DeleteAndInsertSub(LinkList &la, LinkList &lb,
int i, int j, int len);
// la和lb分别指向两个单链表中第一个结点， */
/* 本算法是从la表中删去自第i个元素起共len个元素，*/
/* 并将它们插入到lb表中第j个元素之前， */
/* 若lb表中只有j-1个元素，则插在表尾。 */
单链表类型定义如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.17② 试写一算法，在无头结点的动态单链表上实现
线性表操作INSERT(L,i,b)，并和在带头结点的动态单
链表上实现相同操作的算法进行比较。
实现下列函数：
void Insert(LinkList &L, int i, ElemType b);
单链表类型定义如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.18② 同2.17题要求。试写一算法，
实现线性表操作DELETE(L,i)。
实现下列函数：
void Delete(LinkList &L, int i);
单链表类型定义如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
◆2.19③ 已知线性表中的元素以值递增有序排列，并以
单链表作存储结构。试写一高效的算法，删除表中所有值
大于mink且小于maxk的元素(若表中存在这样的元素)同时
释放被删结点空间，并分析你的算法的时间复杂度（注意：
mink和maxk是给定的两个参变量，它们的值可以和表中的
元素相同，也可以不同）。
实现下列函数：
void DeleteSome(LinkList &L, ElemType mink, ElemType maxk);
/* Delete all the elements which value is between mink and */
/* maxk from the single sorted LinkList with head pointer L.*/
单链表类型定义如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.20② 同2.19题条件，试写一高效的算法，删除表中所
有值相同的多余元素 (使得操作后的线性表中所有元素的
值均不相同) 同时释放被删结点空间，并分析你的算法的
时间复杂度。
实现下列函数：
void Purge(LinkList &L);
单链表类型定义如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
◆2.21③ 试写一算法，实现顺序表的就地逆置，
即利用原表的存储空间将线性表(a1,a2,…,an)
逆置为(an,an-1,…,a1)。
实现下列函数：
void Inverse(SqList &L);
顺序表类型定义如下：
typedef struct {
ElemType *elem;
int length;
int listsize;
} SqList;
◆2.22③ 试写一算法，对单链表实现就地逆置。
实现下列函数：
void Inverse(LinkList &L);
/* 对带头结点的单链表L实现就地逆置 */
单链表类型定义如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.23③ 设线性表A=(a1,...,am), B=(b1,...,bn)，试写
一个按下列规则合并A、B为线性表C的算法，即使得
C=(a1,b1,...,am,bm,bm+1,...,bn) 当m≤n时；
或者 C=(a1,b1,...,an,bn,an+1,...,am) 当m＞n时。
线性表A、B和C均以单链表作存储结构，且C表利用A表和
B表中的结点空间构成。注意：单链表的长度值m和n均未
显式存储。
实现下列函数：
void Merge(LinkList ha, LinkList hb, LinkList &hc)
/* 依题意，合并带头结点的单链表ha和hb为hc */
单链表类型定义如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
◆2.24④ 假设有两个按元素值递增有序排列的线性表
A和B，均以单链表作存储结构，请编写算法将A表和B表
归并成一个按元素值递减有序（即非递增有序，允许表
中含有值相同的元素）排列的线性表C， 并要求利用原
表（即A表和B表）的结点空间构造C表。
实现下列函数：
void Union(LinkList &lc, LinkList la, LinkList lb);
/* 依题意，利用la和lb原表的结点空间构造lc表 */
单链表类型定义如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.26④ 假设以两个元素依值递增有序排列的线性表
A和B分别表示两个集合（即同一表中的元素值各不相
同），现要求另辟空间构成一个线性表C，其元素为A
和B中元素的交集，且表C中的元素也依值递增有序排
列。试对单链表编写求C的算法。
实现下列函数：
void Intersect(LinkList &hc, LinkList ha, LinkList hb);
单链表类型定义如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.31② 假设某个单向循环链表的长度大于1，且表
中既无头结点也无头指针。已知s为指向链表中某个
结点的指针，试编写算法在链表中删除指针s所指结
点的前驱结点。
实现下列函数：
ElemType DeleteNode(LinkList s);
/* 删除指针s所指结点的前驱结点，并返回被删结点的元素值 */
单链表类型定义如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.32② 已知有一个单向循环链表，其每个结点中
含三个域：prev、data和next，其中data为数据域，
next为指向后继结点的指针域，prev也为指针域，
但它的值为空(NULL)，试编写算法将此单向循环链
表改为双向循环链表，即使prev成为指向前驱结点
的指针域。
实现下列函数：
void PerfectBiLink(BiLinkList &CL);
双向循环链表类型定义如下：
typedef struct BiNode {
ElemType data;
int freq; // 2.38题用
struct BiNode *prev,
*next;
} BiNode, *BiLinkList;
◆2.33③ 已知由一个线性链表表示的线性表中含有
三类字符的数据元素（如：字母字符、数字字符和其
它字符），试编写算法将该线性链表分割为三个循环
链表，其中每个循环链表表示的线性表中均只含一类
字符。
实现下列函数：
void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll);
单链表类型定义如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.37④ 设以带头结点的双向循环链表表示的线性
表L=(a1,a2,...,an)。试写一时间复杂度为O(n)的
算法，将L改造为L=(a1,a3,...,an,...,a4,a2)。
实现下列函数：
void ReverseEven(BiLinkList &L);
双向循环链表类型定义如下：
typedef struct BiNode {
ElemType data;
int freq; // 2.38题用
struct BiNode *prev,
*next;
} BiNode, *BiLinkList;
◆2.38④ 设有一个双向循环链表，每个结点中除有
prev、data和next三个域外，还增设了一个访问频度
域freq。在链表被起用之前，频度域freq的值均初始
化为零， 而每当对链表进行一次LOCATE(L,x)的操作
后， 被访问的结点（即元素值等于x的结点）中的频
度域freq的值便增1， 同时调整链表中结点之间的次
序，使其按访问频度递减的次序顺序排列，以便始终
保持被频繁访问的结点总是靠近表头结点。试编写符
合上述要求的LOCATE操作的算法。
实现下列函数：
BiLinkList Locate(BiLinkList dh, ElemType x);
双向循环链表类型定义如下：
typedef struct BiNode {
ElemType data;
int freq;
struct BiNode *prev,
*next;
} BiNode, *BiLinkList;
◆2.39③ 试对稀疏多项式Pn(x)采用存储量同多项式项
数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0为
给定值），并分析你的算法的时间复杂度。
实现下列函数：
float Evaluate(SqPoly pn, float x);
/* pn.data[i].coef 存放ai， */
/* pn.data[i].exp存放ei (i=1,2,...,m) */
/* 本算法计算并返回多项式的值。不判别溢出。 */
/* 入口时要求0≤e1<e2<...<em，算法内不对此再作验证*/
多项式的顺序存储结构:
typedef struct {
int coef;
int exp;
} PolyTerm;
typedef struct {
PolyTerm *data;
int length;
} SqPoly;
◆2.41② 试以循环链表作稀疏多项式的存储结构，
编写求其导函数的算法，要求利用原多项式中的结
点空间存放其导函数（多项式），同时释放所有无
用（被删）结点。
实现下列函数：
void Difference(LinkedPoly &pa);
/* 稀疏多项式 pa 以循环链表作存储结构， */
/* 将此链表修改成它的导函数，并释放无用结点 */
链式多项式的类型定义：
typedef struct PolyNode {
int coef;
int exp;
struct PolyNode *next;
} PolyNode, *PolyLink; // 多项式元素（项）结点类型
typedef PolyLink LinkedPoly; // 链式多项式
1.00① 试设计一算法，
判断元素与集合之间的关系。
实现下列函数：
/**
* 判断元素与集合之间的关系。元素和集合之间的关系只有两种。
* @param elem： 元素
* @param pA： 集合
* @return: 如果elem ∈ pA，则返回TRUE，否则返回FALSE
*/
Boolean IsInSet(SetElem elem, pSet pA){
//Add your code here
}
//---------------------------------------------------------------------------------
注解：
1. pSet为指向一个集合结构体的指针类型，集合元素的类型为SetElem。至于其具体实现，
可以参考下面的伪代码。
typedef ...... SetElem; // 集合元素结点
typedef struct Set {
......
......
}Set, *pSet; // 集合
至于集合内各元素的实际存储方式，并不需要关注。
2. Boolean, true, flase, TRUE, FALSE已经在作业系统内部定义实现。
参考实现代码：
typedef ...... Boolean;
#define true ......
#define false ......
#define TRUE ......
#define FALSE ......
3. 以下函数已经在作业系统内部实现，可以直接调用：
（1）
/**
* 将一个集合中的元素输出至一个缓冲区中存储。根据集合定义，集合元素
* 之间是没有相对顺序的，所以为了方便对集合进行遍历操作，需要首先将
* 集合中的元素随机输出至一缓冲区中。
* @param pS: 需要进行元素输出的集合
* @return: 如果pS所指的集合存在，则返回一个存储pS中所有元素的缓冲区，
* 该缓冲区以'\n'字符结尾；否则返回NULL。
*/
SetElem * outToBuffer(pSet pS) {
......
}
例如假设集合pS的内容是{a, b, c}，则本函数被调用后会得到一个如下图所示
的缓冲区:
-------------------------------------
... a b c \n ...
-------------------------------------
其中'\n'字符是本函数自动添加上去的，此字符不是集合中的元素。
示例代码：
pSet pSetA;
pSetA = ......; //假设在此初始化好一个集合
SetElem * pAElems;
//将集合pSetA中的元素随机输出至缓冲区pAElems中
pAElems = outToBuffer(pSetA);
......
问题与提示：
① 如何获得缓冲区中第一个元素的值？
答：*pAElems
② 如何令pAElems指针指向缓冲区中的下一个元素？
答：++pAElems 或 pAElems++
③ 集合元素或者缓冲区中的元素如何进行比较？
答：为简化编程，在本作业系统中支持集合元素与缓冲区元素应用运算符直接比较。
示例代码：
SetElem elem = ...; //假设存在某集合元素
if( elem == *pAElems) {
// do something
}
或者：
if( elem != *pAElems) {
// do another thing
}
4. 如果需要自定义新的函数，则该函数必须定义在IsInSet函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
Boolean IsInSet(SetElem elem, pSet pA){
//Add your code here
yourFunction; //调用自定义函数
}
1.01③ 试设计一算法，
实现集合的并运算。
实现下列函数：
/**
* 进行两个集合的并运算
* @param pA： 要进行并运算的集合
* @param pB： 要进行并运算的集合
* @return: 将pA和pB进行并运算后得到的集合
*/
pSet SetUnion(pSet pA, pSet pB){
//Add your code here
}
//---------------------------------------------------------------------------------
注解：
1. pSet为指向一个集合结构体的指针类型，集合元素的类型为SetElem。至于其具体实现，
可以参考下面的伪代码。
typedef ...... SetElem; // 集合元素结点
typedef struct Set {
......
......
}Set, *pSet; // 集合
至于集合内各元素的实际存储方式，并不需要关注。
2. Boolean, true, flase, TRUE, FALSE已经在作业系统内部定义实现。
参考实现代码：
typedef ...... Boolean;
#define true ......
#define false ......
#define TRUE ......
#define FALSE ......
3. 以下函数已经在作业系统内部实现，可以直接调用：
（1）
/**
* 创建一个空集
* @return 返回一个指向空集的指针。
*/
pSet createNullSet(){
......
}
（2）
/**
* 判断一个集合是否为空集
* @param pS： 要进行判断是否为空集的集合
* @return: 如果pS是空集，则返回TRUE；否则返回 FALSE。
*/
Boolean isNullSet(pSet pS){
......
}
（3）
/**
* 判断一个元素是否属于指定集合
* @param pS： 指定集合
* @param elem: 需要进行判断是否属于集合pS的集合元素
* @return: 如果elem属于集合pS，则返回TRUE；否则返回 FALSE。
*/
Boolean isInSet(pSet pS, SetElem elem) {
......
}
（4）
/**
* 将一个集合中的元素输出至一个缓冲区中存储。根据集合定义，集合元素
* 之间是没有相对顺序的，所以为了方便对集合进行遍历操作，需要首先将
* 集合中的元素随机输出至一个缓冲区中。
* @param pS: 需要进行元素输出的集合
* @return: 如果pS所指的集合存在，则返回一个存储pS中所有元素的缓冲区，
* 该缓冲区以'\n'字符结尾；否则返回NULL。
*/
SetElem * outToBuffer(pSet pS) {
......
}
例如假设集合pS的内容是{a, b, c}，则本函数被调用后会得到一个如下图所示
的缓冲区:
-------------------------------------
... a b c \n ...
-------------------------------------
其中'\n'字符是本函数自动添加上去的，此字符不是集合中的元素。
示例代码：
pSet pSetA;
pSetA = ......; //假设在此初始化好一个集合
SetElem * pAElems;
//将集合pSetA中的元素随机输出至缓冲区pAElems中
pAElems = outToBuffer(pSetA);
......
问题与提示：
① 如何获得缓冲区中第一个元素的值？
答：*pAElems
② 如何令pAElems指针指向缓冲区中的下一个元素？
答：++pAElems 或 pAElems++
③ 集合元素或者缓冲区中的元素如何进行比较？
答：为简化编程，在本作业系统中支持集合元素与缓冲区元素应用运算符直接比较。
示例代码：
SetElem elem = ...; //假设存在某集合元素
if( elem == *pAElems) {
// do something
}
或者：
if( elem != *pAElems) {
// do another thing
}
（5）
/**
* 如果pS所指的集合存在，则将一个数据元素插入至某个集合。在插入过程中，
* 本函数并不检查集合中是否存在相同的元素。
*/
void directInsertSetElem(pSet pS, SetElem elem){
......
}
4. 如果需要自定义新的函数，则该函数必须定义在SetUnion函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pSet SetUnion(pSet pA, pSet pB){
//Add your code here
yourFunction; //调用自定义函数
}
1.02② 试设计一算法，
实现集合的交运算。
实现下列函数：
/**
* 进行两个集合的交运算
* @param pA： 要进行交运算的集合
* @param pB： 要进行交运算的集合
* @return: 将pA和pB进行交运算后得到的集合
*/
pSet SetIntersection(pSet pA, pSet pB){
//Add your code here
}
//---------------------------------------------------------------------------------
注解：
1. pSet为指向一个集合结构体的指针类型，集合元素的类型为SetElem。至于其具体实现，
可以参考下面的伪代码。
typedef ...... SetElem; // 集合元素结点
typedef struct Set {
......
......
}Set, *pSet; // 集合
至于集合内各元素的实际存储方式，并不需要关注。
2. Boolean, true, flase, TRUE, FALSE已经在作业系统内部定义实现。
参考实现代码：
typedef ...... Boolean;
#define true ......
#define false ......
#define TRUE ......
#define FALSE ......
3. 以下函数已经在作业系统内部实现，可以直接调用：
（1）
/**
* 创建一个空集
* @return 返回一个指向空集的指针。
*/
pSet createNullSet(){
......
}
（2）
/**
* 判断一个集合是否为空集
* @param pS： 要进行判断是否为空集的集合
* @return: 如果pS是空集，则返回TRUE；否则返回 FALSE。
*/
Boolean isNullSet(pSet pS){
......
}
（3）
/**
* 判断一个元素是否属于指定集合
* @param pS： 指定集合
* @param elem: 需要进行判断是否属于集合pS的集合元素
* @return: 如果elem属于集合pS，则返回TRUE；否则返回 FALSE。
*/
Boolean isInSet(pSet pS, SetElem elem) {
......
}
（4）
/**
* 将一个集合中的元素输出至一个缓冲区中存储。根据集合定义，集合元素
* 之间是没有相对顺序的，所以为了方便对集合进行遍历操作，需要首先将
* 集合中的元素随机输出至一个缓冲区中。
* @param pS: 需要进行元素输出的集合
* @return: 如果pS所指的集合存在，则返回一个存储pS中所有元素的缓冲区，
* 该缓冲区以'\n'字符结尾；否则返回NULL。
*/
SetElem * outToBuffer(pSet pS) {
......
}
例如假设集合pS的内容是{a, b, c}，则本函数被调用后会得到一个如下图所示
的缓冲区:
-------------------------------------
... a b c \n ...
-------------------------------------
其中'\n'字符是本函数自动添加上去的，此字符不是集合中的元素。
示例代码：
pSet pSetA;
pSetA = ......; //假设在此初始化好一个集合
SetElem * pAElems;
//将集合pSetA中的元素随机输出至缓冲区pAElems中
pAElems = outToBuffer(pSetA);
......
问题与提示：
① 如何获得缓冲区中第一个元素的值？
答：*pAElems
② 如何令pAElems指针指向缓冲区中的下一个元素？
答：++pAElems 或 pAElems++
③ 集合元素或者缓冲区中的元素如何进行比较？
答：为简化编程，在本作业系统中支持集合元素与缓冲区元素应用运算符直接比较。
示例代码：
SetElem elem = ...; //假设存在某集合元素
if( elem == *pAElems) {
// do something
}
或者：
if( elem != *pAElems) {
// do another thing
}
（5）
/**
* 如果pS所指的集合存在，则将一个数据元素插入至某个集合。在插入过程中，
* 本函数并不检查集合中是否存在相同的元素。
*/
void directInsertSetElem(pSet pS, SetElem elem){
......
}
4. 如果需要自定义新的函数，则该函数必须定义在SetIntersection函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pSet SetIntersection(pSet pA, pSet pB){
//Add your code here
yourFunction; //调用自定义函数
}
1.03② 试设计一算法，
实现集合的差运算。
实现下列函数：
/**
* 进行两个集合的差运算
* @param pA： 要进行差运算的集合，相当于A - B中的A
* @param pB： 要进行差运算的集合，相当于A - B中的B
* @return: 将pA和pB进行差运算后得到的集合
*/
pSet SetSubtraction(pSet pA, pSet pB){
//Add your code here
}
//---------------------------------------------------------------------------------
注解：
1. pSet为指向一个集合结构体的指针类型，集合元素的类型为SetElem。至于其具体实现，
可以参考下面的伪代码。
typedef ...... SetElem; // 集合元素结点
typedef struct Set {
......
......
}Set, *pSet; // 集合
至于集合内各元素的实际存储方式，并不需要关注。
2. Boolean, true, flase, TRUE, FALSE已经在作业系统内部定义实现。
参考实现代码：
typedef ...... Boolean;
#define true ......
#define false ......
#define TRUE ......
#define FALSE ......
3. 以下函数已经在作业系统内部实现，可以直接调用：
（1）
/**
* 创建一个空集
* @return 返回一个指向空集的指针。
*/
pSet createNullSet(){
......
}
（2）
/**
* 判断一个集合是否为空集
* @param pS： 要进行判断是否为空集的集合
* @return: 如果pS是空集，则返回TRUE；否则返回 FALSE。
*/
Boolean isNullSet(pSet pS){
......
}
（3）
/**
* 判断一个元素是否属于指定集合
* @param pS： 指定集合
* @param elem: 需要进行判断是否属于集合pS的集合元素
* @return: 如果elem属于集合pS，则返回TRUE；否则返回 FALSE。
*/
Boolean isInSet(pSet pS, SetElem elem) {
......
}
（4）
/**
* 将一个集合中的元素输出至一个缓冲区中存储。根据集合定义，集合元素
* 之间是没有相对顺序的，所以为了方便对集合进行遍历操作，需要首先将
* 集合中的元素随机输出至一个缓冲区中。
* @param pS: 需要进行元素输出的集合
* @return: 如果pS所指的集合存在，则返回一个存储pS中所有元素的缓冲区，
* 该缓冲区以'\n'字符结尾；否则返回NULL。
*/
SetElem * outToBuffer(pSet pS) {
......
}
例如假设集合pS的内容是{a, b, c}，则本函数被调用后会得到一个如下图所示
的缓冲区:
-------------------------------------
... a b c \n ...
-------------------------------------
其中'\n'字符是本函数自动添加上去的，此字符不是集合中的元素。
示例代码：
pSet pSetA;
pSetA = ......; //假设在此初始化好一个集合
SetElem * pAElems;
//将集合pSetA中的元素随机输出至缓冲区pAElems中
pAElems = outToBuffer(pSetA);
......
问题与提示：
① 如何获得缓冲区中第一个元素的值？
答：*pAElems
② 如何令pAElems指针指向缓冲区中的下一个元素？
答：++pAElems 或 pAElems++
③ 集合元素或者缓冲区中的元素如何进行比较？
答：为简化编程，在本作业系统中支持集合元素与缓冲区元素应用运算符直接比较。
示例代码：
SetElem elem = ...; //假设存在某集合元素
if( elem == *pAElems) {
// do something
}
或者：
if( elem != *pAElems) {
// do another thing
}
（5）
/**
* 如果pS所指的集合存在，则将一个数据元素插入至某个集合。在插入过程中，
* 本函数并不检查集合中是否存在相同的元素。
*/
void directInsertSetElem(pSet pS, SetElem elem){
......
}
4. 如果需要自定义新的函数，则该函数必须定义在SetSubtraction函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pSet SetSubtraction(pSet pA, pSet pB){
//Add your code here
yourFunction; //调用自定义函数
}
1.04② 试设计一算法，
实现集合的求补集运算。
实现下列函数：
/**
* 进行集合的求补集运算。
* @param pA： 要进行求补集运算的集合
* @param pI： 全集
* @return: 返回pA相对于pI的补集。注意：有可能存在pA不是PI的子集的情况，
* 在这种情况下pA的补集不存在，应当返回NULL
*/
pSet SetComplement(pSet pA, pSet pI){
//Add your code here
}
//---------------------------------------------------------------------------------
注解：
1. pSet为指向一个集合结构体的指针类型，集合元素的类型为SetElem。至于其具体实现，
可以参考下面的伪代码。
typedef ...... SetElem; // 集合元素结点
typedef struct Set {
......
......
}Set, *pSet; // 集合
至于集合内各元素的实际存储方式，并不需要关注。
2. Boolean, true, flase, TRUE, FALSE已经在作业系统内部定义实现。
参考实现代码：
typedef ...... Boolean;
#define true ......
#define false ......
#define TRUE ......
#define FALSE ......
3. 以下函数已经在作业系统内部实现，可以直接调用：
（1）
/**
* 创建一个空集
* @return 返回一个指向空集的指针。
*/
pSet createNullSet(){
......
}
（2）
/**
* 判断一个集合是否为空集
* @param pS： 要进行判断是否为空集的集合
* @return: 如果pS是空集，则返回TRUE；否则返回 FALSE。
*/
Boolean isNullSet(pSet pS){
......
}
（3）
/**
* 判断一个元素是否属于指定集合
* @param pS： 指定集合
* @param elem: 需要进行判断是否属于集合pS的集合元素
* @return: 如果elem属于集合pS，则返回TRUE；否则返回 FALSE。
*/
Boolean isInSet(pSet pS, SetElem elem) {
......
}
（4）
/**
* 将一个集合中的元素输出至一个缓冲区中存储。根据集合定义，集合元素
* 之间是没有相对顺序的，所以为了方便对集合进行遍历操作，需要首先将
* 集合中的元素随机输出至一个缓冲区中。
* @param pS: 需要进行元素输出的集合
* @return: 如果pS所指的集合存在，则返回一个存储pS中所有元素的缓冲区，
* 该缓冲区以'\n'字符结尾；否则返回NULL。
*/
SetElem * outToBuffer(pSet pS) {
......
}
例如假设集合pS的内容是{a, b, c}，则本函数被调用后会得到一个如下图所示
的缓冲区:
-------------------------------------
... a b c \n ...
-------------------------------------
其中'\n'字符是本函数自动添加上去的，此字符不是集合中的元素。
示例代码：
pSet pSetA;
pSetA = ......; //假设在此初始化好一个集合
SetElem * pAElems;
//将集合pSetA中的元素随机输出至缓冲区pAElems中
pAElems = outToBuffer(pSetA);
......
问题与提示：
① 如何获得缓冲区中第一个元素的值？
答：*pAElems
② 如何令pAElems指针指向缓冲区中的下一个元素？
答：++pAElems 或 pAElems++
③ 集合元素或者缓冲区中的元素如何进行比较？
答：为简化编程，在本作业系统中支持集合元素与缓冲区元素应用运算符直接比较。
示例代码：
SetElem elem = ...; //假设存在某集合元素
if( elem == *pAElems) {
// do something
}
或者：
if( elem != *pAElems) {
// do another thing
}
（5）
/**
* 如果pS所指的集合存在，则将一个数据元素插入至某个集合。在插入过程中，
* 本函数并不检查集合中是否存在相同的元素。
*/
void directInsertSetElem(pSet pS, SetElem elem){
......
}
4. 如果需要自定义新的函数，则该函数必须定义在SetComplement函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pSet SetComplement(pSet pA, pSet pI){
//Add your code here
yourFunction; //调用自定义函数
}
1.05② 试设计一算法，
实现集合的对称差运算。
实现下列函数：
/**
* 进行集合的对称差运算。
* @param pA： 需要进行对称差运算的集合
* @param pB： 需要进行对称差运算的集合
* @return: 返回pA与pB进行对称差运算后得到的集合。
*/
pSet SetSysmmetricDifference(pSet pA, pSet pB){
//Add your code here
}
//---------------------------------------------------------------------------------
注解：
1. pSet为指向一个集合结构体的指针类型，集合元素的类型为SetElem。至于其具体实现，
可以参考下面的伪代码。
typedef ...... SetElem; // 集合元素结点
typedef struct Set {
......
......
}Set, *pSet; // 集合
至于集合内各元素的实际存储方式，并不需要关注。
2. Boolean, true, flase, TRUE, FALSE已经在作业系统内部定义实现。
参考实现代码：
typedef ...... Boolean;
#define true ......
#define false ......
#define TRUE ......
#define FALSE ......
3. 以下函数已经在作业系统内部实现，可以直接调用：
（1）
/**
* 创建一个空集
* @return 返回一个指向空集的指针。
*/
pSet createNullSet(){
......
}
（2）
/**
* 判断一个集合是否为空集
* @param pS： 要进行判断是否为空集的集合
* @return: 如果pS是空集，则返回TRUE；否则返回 FALSE。
*/
Boolean isNullSet(pSet pS){
......
}
（3）
/**
* 判断一个元素是否属于指定集合
* @param pS： 指定集合
* @param elem: 需要进行判断是否属于集合pS的集合元素
* @return: 如果elem属于集合pS，则返回TRUE；否则返回 FALSE。
*/
Boolean isInSet(pSet pS, SetElem elem) {
......
}
（4）
/**
* 将一个集合中的元素输出至一个缓冲区中存储。根据集合定义，集合元素
* 之间是没有相对顺序的，所以为了方便对集合进行遍历操作，需要首先将
* 集合中的元素随机输出至一个缓冲区中。
* @param pS: 需要进行元素输出的集合
* @return: 如果pS所指的集合存在，则返回一个存储pS中所有元素的缓冲区，
* 该缓冲区以'\n'字符结尾；否则返回NULL。
*/
SetElem * outToBuffer(pSet pS) {
......
}
例如假设集合pS的内容是{a, b, c}，则本函数被调用后会得到一个如下图所示
的缓冲区:
-------------------------------------
... a b c \n ...
-------------------------------------
其中'\n'字符是本函数自动添加上去的，此字符不是集合中的元素。
示例代码：
pSet pSetA;
pSetA = ......; //假设在此初始化好一个集合
SetElem * pAElems;
//将集合pSetA中的元素随机输出至缓冲区pAElems中
pAElems = outToBuffer(pSetA);
......
问题与提示：
① 如何获得缓冲区中第一个元素的值？
答：*pAElems
② 如何令pAElems指针指向缓冲区中的下一个元素？
答：++pAElems 或 pAElems++
③ 集合元素或者缓冲区中的元素如何进行比较？
答：为简化编程，在本作业系统中支持集合元素与缓冲区元素应用运算符直接比较。
示例代码：
SetElem elem = ...; //假设存在某集合元素
if( elem == *pAElems) {
// do something
}
或者：
if( elem != *pAElems) {
// do another thing
}
（5）
/**
* 如果pS所指的集合存在，则将一个数据元素插入至某个集合。在插入过程中，
* 本函数并不检查集合中是否存在相同的元素。
*/
void directInsertSetElem(pSet pS, SetElem elem){
......
}
4. 如果需要自定义新的函数，则该函数必须定义在SetSysmmetricDifference函数前面，
例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pSet SetSysmmetricDifference(pSet pA, pSet pB){
//Add your code here
yourFunction; //调用自定义函数
}
1.05③ 试设计一算法，
判断两个集合之间的包含关系。
实现下列函数：
/**
* 判断两个集合之间的包含关系。规定集合之间的包含关系为：
* 真包含，被真包含于，相等。
* @param pA： 需要进行包含关系判断的集合
* @param pB： 需要进行包含关系判断的集合
* @return: 如果pA真包含pB，返回REALINCLUDING;
* 如果pA被真包含于pB，返回REALINCLUDED;
* 如果pA等于pB，返回EQUAL；
* 对于其它情况，返回NOT_INCLUSIVE。
*/
SetRelationshipStatus SetRelationship(pSet pA, pSet pB){
//Add your code here
}
注解：
1. SetRelationshipStatus是一个重定义枚举变量：
typedef enum {
REALINCLUDING, //真包含
REALINCLUDED, //真包含于
EQUAL, //相等
NOT_INCLUSIVE //其它情况
}SetRelationshipStatus;
2. pSet为指向一个集合结构体的指针类型，集合元素的类型为SetElem。至于其具体实现，可以参考下面的伪代码。
typedef ...... SetElem; // 集合元素结点
typedef struct Set {
......
......
}Set, *pSet; // 集合
至于集合内各元素的实际存储方式，并不需要关注。
2. Boolean, true, flase, TRUE, FALSE已经在作业系统内部定义实现。
参考实现代码：
typedef ...... Boolean;
#define true ......
#define false ......
#define TRUE ......
#define FALSE ......
4. 以下函数已经在作业系统内部实现，可以直接调用：
（1）
/**
* 创建一个空集
* @return 返回一个指向空集的指针。
*/
pSet createNullSet(){
......
}
（2）
/**
* 判断一个集合是否为空集
* @param pS： 要进行判断是否为空集的集合
* @return: 如果pS是空集，则返回TRUE；否则返回 FALSE。
*/
Boolean isNullSet(pSet pS){
......
}
（3）
/**
* 判断一个元素是否属于指定集合
* @param pS： 指定集合
* @param elem: 需要进行判断是否属于集合pS的集合元素
* @return: 如果elem属于集合pS，则返回TRUE；否则返回 FALSE。
*/
Boolean isInSet(pSet pS, SetElem elem) {
......
}
（4）
/**
* 将一个集合中的元素输出至一个缓冲区中存储。根据集合定义，集合元素
* 之间是没有相对顺序的，所以为了方便对集合进行遍历操作，需要首先将
* 集合中的元素随机输出至一个缓冲区中。
* @param pS: 需要进行元素输出的集合
* @return: 如果pS所指的集合存在，则返回一个存储pS中所有元素的缓冲区，
* 该缓冲区以'\n'字符结尾；否则返回NULL。
*/
SetElem * outToBuffer(pSet pS) {
......
}
例如假设集合pS的内容是{a, b, c}，则本函数被调用后会得到一个如下图所示
的缓冲区:
-------------------------------------
... a b c \n ...
-------------------------------------
其中'\n'字符是本函数自动添加上去的，此字符不是集合中的元素。
示例代码：
pSet pSetA;
pSetA = ......; //假设在此初始化好一个集合
SetElem * pAElems;
//将集合pSetA中的元素随机输出至缓冲区pAElems中
pAElems = outToBuffer(pSetA);
......
问题与提示：
① 如何获得缓冲区中第一个元素的值？
答：*pAElems
② 如何令pAElems指针指向缓冲区中的下一个元素？
答：++pAElems 或 pAElems++
③ 集合元素或者缓冲区中的元素如何进行比较？
答：为简化编程，在本作业系统中支持集合元素与缓冲区元素应用运算符直接比较。
示例代码：
SetElem elem = ...; //假设存在某集合元素
if( elem == *pAElems) {
// do something
}
或者：
if( elem != *pAElems) {
// do another thing
}
（5）
/**
* 如果pS所指的集合存在，则将一个数据元素插入至某个集合。在插入过程中，
* 本函数并不检查集合中是否存在相同的元素。
*/
void directInsertSetElem(pSet pS, SetElem elem){
......
}
5. 如果需要自定义新的函数，则该函数必须定义在SetRelationship函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
SetRelationshipStatus SetRelationship(pSet pA, pSet pB){
//Add your code here
yourFunction; //调用自定义函数
}
1.07⑤ 试设计一个非递归算法，
实现集合的求幂集运算。
实现下列函数：
/**
* 求一个集合的幂集。
* @param pA： 需要进行幂集的集合
* @return: 返回pA的幂集
*/
pSetFamily PowerSet(pSet pA){
//Add your code here
}
//---------------------------------------------------------------------------------
注解：
1. pSetFamily为指向一个集族结构体的指针类型，在集族元素的类型是集合，即为pSet类型。至于其具体实现，
可以参考下面的伪代码。
typedef struct FamilyOfSet{
......
......
}FamilyOfSet, *pFamilyOfSet;
至于集族内各元素的实际存储方式，并不需要关注。
2. pSet为指向一个集合结构体的指针类型，集合元素的类型为SetElem。至于其具体实现，可以参考下面的伪代码。
typedef ...... SetElem; // 集合元素结点
typedef struct Set {
......
......
}Set, *pSet; // 集合
至于集合内各元素的实际存储方式，并不需要关注。
3. Boolean, true, flase, TRUE, FALSE已经在作业系统内部定义实现。
参考实现代码：
typedef ...... Boolean;
#define true ......
#define false ......
#define TRUE ......
#define FALSE ......
4. 以下函数已经在作业系统内部实现，可以直接调用：
（1）
/**
* 创建一个空集
* @return 返回一个指向空集的指针。
*/
pSet createNullSet(){
......
}
（2）
/**
* 判断一个集合是否为空集
* @param pS： 要进行判断是否为空集的集合
* @return: 如果pS是空集，则返回TRUE；否则返回 FALSE。
*/
Boolean isNullSet(pSet pS){
......
}
（3）
/**
* 判断一个元素是否属于指定集合
* @param pS： 指定集合
* @param elem: 需要进行判断是否属于集合pS的集合元素
* @return: 如果elem属于集合pS，则返回TRUE；否则返回 FALSE。
*/
Boolean isInSet(pSet pS, SetElem elem) {
......
}
（4）
/**
* 将一个集合中的元素输出至一个缓冲区中存储。根据集合定义，集合元素
* 之间是没有相对顺序的，所以为了方便对集合进行遍历操作，需要首先将
* 集合中的元素随机输出至一个缓冲区中。
* @param pS: 需要进行元素输出的集合
* @return: 如果pS所指的集合存在，则返回一个存储pS中所有元素的缓冲区，
* 该缓冲区以'\n'字符结尾；否则返回NULL。
*/
SetElem * outToBuffer(pSet pS) {
......
}
例如假设集合pS的内容是{a, b, c}，则本函数被调用后会得到一个如下图所示
的缓冲区:
-------------------------------------
... a b c \n ...
-------------------------------------
其中'\n'字符是本函数自动添加上去的，此字符不是集合中的元素。
示例代码：
pSet pSetA;
pSetA = ......; //假设在此初始化好一个集合
SetElem * pAElems;
//将集合pSetA中的元素随机输出至缓冲区pAElems中
pAElems = outToBuffer(pSetA);
......
问题与提示：
① 如何获得缓冲区中第一个元素的值？
答：*pAElems
② 如何令pAElems指针指向缓冲区中的下一个元素？
答：++pAElems 或 pAElems++
③ 集合元素或者缓冲区中的元素如何进行比较？
答：为简化编程，在本作业系统中支持集合元素与缓冲区元素应用运算符直接比较。
示例代码：
SetElem elem = ...; //假设存在某集合元素
if( elem == *pAElems) {
// do something
}
或者：
if( elem != *pAElems) {
// do another thing
}
（5）
/**
* 如果pS所指的集合存在，则将一个数据元素插入至某个集合。在插入过程中，
* 本函数并不检查集合中是否存在相同的元素。
*/
void directInsertSetElem(pSet pS, SetElem elem){
......
}
（6）
/**
* 创建一个空集族
* @return 一个空集族
*/
pFamilyOfSet createNullFamilyOfSet(){
...
}
（7）
/**
* 将一个简单集合作为集族的元素插入至集族，插入前检查是否已存在相同的简单集合，
* 如果存在，则不作插入。
* @param pFamSet：集族
* @param pS：要插入至集族的简单集合
*/
void insertToFamilyOfSet(pFamilyOfSet pFamSet, pSet pS){
......
}
（8）
/**
* 将一个集族的所有元素按顺序输出至缓冲区，以便遍历访问。
* @param pFamSet：集族
* @return：一个指向某缓冲区首地址的指针。该缓冲区存储了集族的所有简单集合。
* 的地址。该缓冲区的最后一个元素为NULL，用于标记结尾。
*/
pSet * outFamilyOfSetToBuffer(pFamilyOfSet pFamSet) {
......
}
例如，某集族pFamSet中有3个元素（实际上也是简单集合），此3个元素的类型为
pSet类型，即所在简单集合的地址，例如是：4778、4102、4584，则使用此函数进
行输出后，将可会得到一个指向以下缓冲区的指针，在该缓冲区中有4个元素，前3
个元素的类型也是pSet类型，而最后一个元素为NULL（由该函数自动添加上去的）。
-------------------------------------
...4778 4102 4584 NULL...
-------------------------------------
至于这三个集族元素pSet类型的地址则分别指向三个简单集合，例如可能是以下情况：
4778所指向的集合是：{a, b, c}
4102所指向的集合是：{1, 2}
4584所指向的集合是：空集
5. 如果需要自定义新的函数，则该函数必须定义在PowerSet函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pSetFamily PowerSet(pSet pA){
//Add your code here
yourFunction; //调用自定义函数
}
1.08④ 试设计一个递归算法，
实现集合的求幂集运算。
实现下列函数：
/**
* 求一个集合的幂集。
* @param pA： 需要进行幂集的集合
* @return: 返回pA的幂集
*/
pFamilyOfSet PowerSet(pSet pA){
//Add your code here
}
//---------------------------------------------------------------------------------
注解：
1. pFamilyOfSet为指向一个集族结构体的指针类型，在集族元素的类型是集合，即为pSet类型。至于其具体实现，
可以参考下面的伪代码。
typedef struct FamilyOfSet{
......
......
}FamilyOfSet, *pFamilyOfSet;
至于集族内各元素的实际存储方式，并不需要关注。
2. pSet为指向一个集合结构体的指针类型，集合元素的类型为SetElem。至于其具体实现，可以参考下面的伪代码。
typedef ...... SetElem; // 集合元素结点
typedef struct Set {
......
......
}Set, *pSet; // 集合
至于集合内各元素的实际存储方式，并不需要关注。
3. Boolean, true, flase, TRUE, FALSE已经在作业系统内部定义实现。
参考实现代码：
typedef ...... Boolean;
#define true ......
#define false ......
#define TRUE ......
#define FALSE ......
4. 以下函数已经在作业系统内部实现，可以直接调用：
（1）
/**
* 创建一个空集
* @return 返回一个指向空集的指针。
*/
pSet createNullSet(){
......
}
（2）
/**
* 判断一个集合是否为空集
* @param pS： 要进行判断是否为空集的集合
* @return: 如果pS是空集，则返回TRUE；否则返回 FALSE。
*/
Boolean isNullSet(pSet pS){
......
}
（3）
/**
* 判断一个元素是否属于指定集合
* @param pS： 指定集合
* @param elem: 需要进行判断是否属于集合pS的集合元素
* @return: 如果elem属于集合pS，则返回TRUE；否则返回 FALSE。
*/
Boolean isInSet(pSet pS, SetElem elem) {
......
}
（4）
/**
* 将一个集合中的元素输出至一个缓冲区中存储。根据集合定义，集合元素
* 之间是没有相对顺序的，所以为了方便对集合进行遍历操作，需要首先将
* 集合中的元素随机输出至一个缓冲区中。
* @param pS: 需要进行元素输出的集合
* @return: 如果pS所指的集合存在，则返回一个存储pS中所有元素的缓冲区，
* 该缓冲区以'\n'字符结尾；否则返回NULL。
*/
SetElem * outToBuffer(pSet pS) {
......
}
例如假设集合pS的内容是{a, b, c}，则本函数被调用后会得到一个如下图所示
的缓冲区:
-------------------------------------
... a b c \n ...
-------------------------------------
其中'\n'字符是本函数自动添加上去的，此字符不是集合中的元素。
示例代码：
pSet pSetA;
pSetA = ......; //假设在此初始化好一个集合
SetElem * pAElems;
//将集合pSetA中的元素随机输出至缓冲区pAElems中
pAElems = outToBuffer(pSetA);
......
问题与提示：
① 如何获得缓冲区中第一个元素的值？
答：*pAElems
② 如何令pAElems指针指向缓冲区中的下一个元素？
答：++pAElems 或 pAElems++
③ 集合元素或者缓冲区中的元素如何进行比较？
答：为简化编程，在本作业系统中支持集合元素与缓冲区元素应用运算符直接比较。
示例代码：
SetElem elem = ...; //假设存在某集合元素
if( elem == *pAElems) {
// do something
}
或者：
if( elem != *pAElems) {
// do another thing
}
（5）
/**
* 如果pS所指的集合存在，则将一个数据元素插入至某个集合。在插入过程中，
* 本函数并不检查集合中是否存在相同的元素。
*/
void directInsertSetElem(pSet pS, SetElem elem){
......
}
（6）
/**
* 创建一个空集族
* @return 一个空集族
*/
pFamilyOfSet createNullFamilyOfSet(){
...
}
（7）
/**
* 将一个简单集合作为集族的元素插入至集族，插入前检查是否已存在相同的简单集合，
* 如果存在，则不作插入。
* @param pFamSet：集族
* @param pS：要插入至集族的简单集合
*/
void insertToFamilyOfSet(pFamilyOfSet pFamSet, pSet pS){
......
}
（8）
/**
* 将一个集族的所有元素按顺序输出至缓冲区，以便遍历访问。
* @param pFamSet：集族
* @return：一个指向某缓冲区首地址的指针。该缓冲区存储了集族的所有简单集合。
* 的地址。该缓冲区的最后一个元素为NULL，用于标记结尾。
*/
pSet * outFamilyOfSetToBuffer(pFamilyOfSet pFamSet) {
......
}
例如，某集族pFamSet中有3个元素（实际上也是简单集合），此3个元素的类型为
pSet类型，即所在简单集合的地址，例如是：4778、4102、4584，则使用此函数进
行输出后，将可会得到一个指向以下缓冲区的指针，在该缓冲区中有4个元素，前3
个元素的类型也是pSet类型，而最后一个元素为NULL（由该函数自动添加上去的）。
-------------------------------------
...4778 4102 4584 NULL...
-------------------------------------
至于这三个集族元素pSet类型的地址则分别指向三个简单集合，例如可能是以下情况：
4778所指向的集合是：{a, b, c}
4102所指向的集合是：{1, 2}
4584所指向的集合是：空集
5. 如果需要自定义新的函数，则该函数必须定义在PowerSet函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pFamilyOfSet PowerSet(pSet pA){
//Add your code here
yourFunction; //调用自定义函数
}
3.01⑤ 试设计一个非递归算法，
验证一个表达式是不是命题公式(statement formula)。
实现下列函数：
/**
* 判断一个表达式是不是命题公式。
* @param pFormula: 要进行判断的表达式。该表达式的最后一个元素为“#”，而且规定
* '#'仅用于指示该表达式的结尾，并不属于表达式的一部分。
* @return: 如果pFormula是命题公式，返回TRUE；否则返回FALSE。
*/
Boolean IsStatementFormula(pStatementFormula pFormula){
//Add your code here
}
//---------------------------------------------------------------------------------
注解：
1. pStatementFormula为指向一个命题公式的指针类型。至于其具体实现，可以参考下面的伪代码。
typedef struct { // 命题公式定义
......;
......;
}StatementFormula, *pStatementFormula;
规定所有的命题公式都有一个结束字符'#'，但'#'不属于命题公式的一部分，仅用于表示当前公式的末端。
注意：不能将命题公式简单理解为字符串类型，从而以字节为单位直接获取命题公式中的符号。
只能由下面提供的相关函数对命题公式中的符号的获取。
例1：以下输入是合法的命题公式：
（1）┐(P∨T)→Q#
（2）(P∧(Q∽┐W))#
例2：以下输入不是合法的命题公式：
（1）┐(P∨T)→QS#
（2）┐(P∨T)→#
（3）(P∧(Q∽┐W)))#
2. Boolean, TRUE, FALSE也在作业系统内部定义好了，参考源代码为：
typedef ...... Boolean;
#define true ......
#define false ......
3. 命题公式中的符号类型分为以下几种：
typedef enum {
Exception, //异常情况，例如取到了公式外的字符
Negation, //否定号 '┐'
Conjunction, //合取号 '∨'
Disjunction, //析取号 '∧'
Implication, //蕴涵号 '→'
Equivalence, //等价号 '∽'
PropositionalVariable, //命题变元，使用单个字符表示。每个字符的取值范围为[A, Z]
LeftParenthesis, // '('
RightParenthesis, // ')'
EndOfFormula //命题公式的结束字符'#'
}StatementFormulaSymbles;
4. 以下函数已经在作业系统内部实现，可以直接调用：
（1）
/**
* 返回命题公式中当前位置的符号类型。在命题公式中隐含了一个记录当前访问位置
* 的指示器。本函数只能返回指示器指示的当前符号的类型。
* 注意：你不能通过任何方法直接改变指示器的值。如果需要将指示器指向下一个
* 字符，请参看nextPos函数。
* @param pFormula: 命题公式
* @return 返回一个符号类型。如果pFormula为空，则返回Exception；特别地规定
* 字母集合[A, Z]中的任意元素是命题变量，只要命题变量的具体符号属于
* 该集合，都返回PropositionalVariable。其余类型参照枚举定义
* StatementFormulaSymbles。
*/
StatementFormulaSymbles getCurrentSymbleType(pStatementFormula pFormula) {
......
}
（2）
/**
* 将命题公式中记录当前访问位置的指示器指向下一个符号。特别地，为防止误访问内存，
* 如果当前位置已经指向公式最后一个字符，即'#'，则本函数不会改变指示器的值，也
* 不返回任何提示信息。
* @param pFormula: 命题公式
*/
void nextPos(pStatementFormula pFormula) {
......
}
5. 如果需要自定义新的函数，则该函数必须定义在IsStatementFormula函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
Boolean IsStatementFormula(pOriginalSet pA, pOriginalSet pB, pCartersianSet pC)
//Add your code here
yourFunction; //调用自定义函数
}
3.02⑤ 试设计一个递归算法，
验证一个表达式是不是命题公式(statement formula)。
实现下列函数：
/**
* 判断一个表达式是不是命题公式。
* @param pFormula: 要进行判断的表达式。该表达式的最后一个元素为“#”，而且规定
* '#'仅用于指示该表达式的结尾，并不属于表达式的一部分。
* @return: 如果pFormula是命题公式，返回TRUE；否则返回FALSE。
*/
Boolean IsStatementFormula(pStatementFormula pFormula){
//Add your code here
}
//---------------------------------------------------------------------------------
注解：
1. pStatementFormula为指向一个命题公式的指针类型。至于其具体实现，可以参考下面的伪代码。
typedef struct { // 命题公式定义
......;
......;
}StatementFormula, *pStatementFormula;
规定所有的命题公式都有一个结束字符'#'，但'#'不属于命题公式的一部分，仅用于表示当前公式的末端。
注意：不能将命题公式简单理解为字符串类型，从而以字节为单位直接获取命题公式中的符号。
只能由下面提供的相关函数对命题公式中的符号的获取。
例1：以下输入是合法的命题公式：
（1）┐(P∨T)→Q#
（2）(P∧(Q∽┐W))#
例2：以下输入不是合法的命题公式：
（1）┐(P∨T)→QS#
（2）┐(P∨T)→#
（3）(P∧(Q∽┐W)))#
2. Boolean, TRUE, FALSE也在作业系统内部定义好了，参考源代码为：
typedef ...... Boolean;
#define true ......
#define false ......
3. 命题公式中的符号类型分为以下几种：
typedef enum {
Exception, //异常情况，例如取到了公式外的字符
Negation, //否定号 '┐'
Conjunction, //合取号 '∨'
Disjunction, //析取号 '∧'
Implication, //蕴涵号 '→'
Equivalence, //等价号 '∽'
PropositionalVariable, //命题变元，使用单个字符表示。每个字符的取值范围为[A, Z]
LeftParenthesis, // '('
RightParenthesis, // ')'
EndOfFormula //命题公式的结束字符'#'
}StatementFormulaSymbles;
4. 以下函数已经在作业系统内部实现，可以直接调用：
（1）
/**
* 返回命题公式中当前位置的符号类型。在命题公式中隐含了一个记录当前访问位置
* 的指示器。本函数只能返回指示器指示的当前符号的类型。
* 注意：你不能通过任何方法直接改变指示器的值。如果需要将指示器指向下一个
* 字符，请参看nextPos函数。
* @param pFormula: 命题公式
* @return 返回一个符号类型。如果pFormula为空，则返回Exception；特别地规定
* 字母集合[A, Z]中的任意元素是命题变量，只要命题变量的具体符号属于
* 该集合，都返回PropositionalVariable。其余类型参照枚举定义
* StatementFormulaSymbles。
*/
StatementFormulaSymbles getCurrentSymbleType(pStatementFormula pFormula) {
......
}
（2）
/**
* 将命题公式中记录当前访问位置的指示器指向下一个符号。特别地，为防止误访问内存，
* 如果当前位置已经指向公式最后一个字符，即'#'，则本函数不会改变指示器的值，也
* 不返回任何提示信息。
* @param pFormula: 命题公式
*/
void nextPos(pStatementFormula pFormula) {
......
}
5. 如果需要自定义新的函数，则该函数必须定义在IsStatementFormula函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
Boolean IsStatementFormula(pOriginalSet pA, pOriginalSet pB, pCartersianSet pC)
//Add your code here
yourFunction; //调用自定义函数
}
6.01③ 试设计一算法，
实现集合的卡氏积运算。
实现下列函数：
/**
* 进行两个集合的卡氏积运算
* @param pA： 要进行卡氏积运算的集合
* @param pB： 要进行卡氏积运算的集合
* @return: 将pA和pB进行卡氏积运算后得到的集合
*/
pCartersianSet CartesianProduct(pOriginalSet pA, pOriginalSet pB)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. Boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... Boolean;
#define TRUE ......
#define FALSE ......
4. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何判断一个pOriginalSet集合是否为空集？
isNullOriginalSet函数可用于判断一个pOriginalSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 原始集合
* @return：如果原始集合是空集，则返回true；否则返回false。
*/
boolean isNullOriginalSet(pOriginalSet pSet)
{
......
}
（3）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（4）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（5）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
5. 如果需要自定义新的函数，则该函数必须定义在CartesianProduct函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pCartersianSet CartesianProduct(pOriginalSet pA, pOriginalSet pB)
{
//Add your code here
yourFunction; //调用自定义函数
}
6.02② 试设计一算法，
给定集合A、集合B和集合C，判断集合C是否为A到B的一个二元关系。
实现下列函数：
/**
* 给定集合A、集合B和集合C，判断集合C是否为A到B的一个二元关系。
* @param pA： 集合A
* @param pB： 集合B
* @param pC： 集合C
* @return: 如果集合C是A到B的一个二元关系，则返回true，否则返回false。
*/
boolean isBinaryRelation(pOriginalSet pA, pOriginalSet pB, pCartersianSet pC)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
（3）如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（4）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（5）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（6）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（7）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
5. 如果需要自定义新的函数，则该函数必须定义在isBinaryRelation函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
boolean isBinaryRelation(pOriginalSet pA, pOriginalSet pB, pCartersianSet pC)
{
//Add your code here
yourFunction; //调用自定义函数
}
6.03② 试设计一算法，求集合A上的恒等关系。
实现下列函数：
/**
* 给定集合A，求集合A上的恒等关系。
* @param pSet： 原始集合
* @return: 集合A上的恒等关系。
*/
pCartersianSet IdentityRelation(pOriginalSet pSet)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
（3）如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（4）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（5）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（6）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（7）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
5. 如果需要自定义新的函数，则该函数必须定义在IdentityRelation函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pCartersianSet IdentityRelation(pOriginalSet pSet)
{
//Add your code here
yourFunction; //调用自定义函数
}
6.04③ 试设计一算法，求两个卡氏积集合的复合运算。
实现下列函数：
/**
* 给定两个集合，求该两个集合的复合运算。
* @param pA： 卡氏积集合
* @param pB： 卡氏积集合
* @return: pA与pB的复合运算结果。
*/
pCartersianSet CompositeOperation(pCartersianSet pA, pCartersianSet pB)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
（3）如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（4）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（5）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（6）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（7）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（8）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（9）如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在CompositeOperation函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pCartersianSet CompositeOperation(pCartersianSet pA, pCartersianSet pB)
{
//Add your code here
yourFunction; //调用自定义函数
}
6.05② 试设计一算法，求一个关系的逆运算。
实现下列函数：
/**
* 求一个关系的逆运算。
* @param pA： 卡氏积集合
* @return: pA的逆运算结果。
*/
pCartersianSet InverseOperation(pCartersianSet pA)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
（3）如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（4）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（5）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（6）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（7）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（8）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（9）如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在InverseOperation函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pCartersianSet InverseOperation(pCartersianSet pA)
{
//Add your code here
yourFunction; //调用自定义函数
}
6.06④ 试设计一算法，对某集合A上的一个二元关系，求该关系的幂运算。
实现下列函数：
/**
* 求一个关系的幂运算。
* @param pA： 原始集合
* @param pBinaryRelationR： pA上的关系R
* @param n： 幂运算的次数，且n >= 0
* @return: pBinaryRelationSet的n次幂运算结果。
*/
pCartersianSet PowOperation(pOriginalSet pA,
pCartersianSet pBinaryRelationR,
int n)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
（3）如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（4）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（5）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（6）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（7）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（8）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（9）如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
（10）特别需要注意的是，如果需要进行对同一个关系R进行复合运算时，必须首先对R进行复制
（可使用copyCartersianSet），然后将复制后的R'与R看作两个“不同的”关系进行运算。这
是由于作业系统内部限制实现时，每个关系的当前位置指针只有一个，而进行复合运算时，该指
针有可能被意外重置，导致复合运算结果错误。
/** --------------------------------------------------------------------------
* 复制一个卡氏积集合。
* @param pA: 卡氏积集合
* @return: 一个与pA具有相同元素的集合
*/
pCartersianSet copyCartersianSet(pCartersianSet pA)
{
......
}
正确的复合运算代码示例：
pCartersianSet R = ...; //假设某关系R已初始化
pCartersianSet R2;
R2 = copyCartersianSet(R);
result = compositeOperation(R, R2); //result是R与R2的复合结果，
//但compositeOperation需要自行实现
错误的复合运算代码示例：
pCartersianSet R = ...; //假设某关系R已初始化
result = compositeOperation(R, R); //有可能得到错误的复合运算结果
5. 如果需要自定义新的函数，则该函数必须定义在PowOperation函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pCartersianSet PowOperation(pOriginalSet pA,
pCartersianSet pBinaryRelationR,
int n)
{
//Add your code here
yourFunction; //调用自定义函数
}
6.02② 试设计一算法，对某集合A上的一个二元关系R，判断R是否具有自反性。
实现下列函数：
/**
* 判断一个关系是否具有自反性。
* @param pA： 原始集合
* @param pBinaryRelationR： 卡氏积集合，该集合是一个pA上的二元关系
* @return: 如果pBinaryRelationSet具有自反性；则返回true，否则返回false。
*/
boolean IsReflexivity(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
（3）如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（4）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（5）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（6）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（7）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（8）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（9）如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在IsReflexivity函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
boolean IsReflexivity(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
//Add your code here
yourFunction; //调用自定义函数
}
6.08② 试设计一算法，对某集合A上的一个二元关系R，判断R是否具有反自反性。
实现下列函数：
/**
* 判断一个关系是否具有反自反性。
* @param pA： 原始集合
* @param pBinaryRelationR： 卡氏积集合，该集合是一个pA上的二元关系
* @return: 如果pBinaryRelationSet具有反自反性；则返回true，否则返回false。
*/
boolean IsAntiReflexivity(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
（3）如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（4）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（5）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（6）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（7）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（8）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（9）如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在IsAntiReflexivity函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
boolean IsAntiReflexivity(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
//Add your code here
yourFunction; //调用自定义函数
}
6.09③ 试设计一算法，对某集合A上的一个二元关系R，判断R是否具有自反性或者反自反性。
在实际运算中，A无需给出。
实现下列函数：
/**
* 判断一个关系是否具有自反性或者反自反性。对一个关系R是否具有自反性或者反自反性，
* 有四种可能：是自反的；是反自反的；既是自反的也是反自反的、
* 既不是自反的也不是反自反的。
* @param pA： 原始集合
* @param pBinaryRelationR： 卡氏积集合，该集合是一个pA上的二元关系
* @return: 返回一个Reflexivity_Type枚举类型值。
* 如果pBinaryRelationSet具有自反性，则返回REFLEXIVITY;
* 如果pBinaryRelationSet具有反自反性，则返回ANTI_REFLEXIVITY;
* 如果pBinaryRelationSet既具有自反性，也具有反自反性，则返回
* REFLEXIVITY_AND_ANTI_REFLEXIVITY;
* 如果pBinaryRelationSet既不具有自反性，也不具有反自反性，则返回
* NOT_REFLEXIVITY_AND_NOT_ANTI_REFLEXIVITY;
*/
Reflexivity_Type DetermineReflexivity0609(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. Reflexivity_Type枚举类型定义：
typedef enum { //对于一个关系是否具有自反性的表示
REFLEXIVITY, //自反性
ANTI_REFLEXIVITY, //反自反性
REFLEXIVITY_AND_ANTI_REFLEXIVITY, //既具有自反性也具有反自反性
NOT_REFLEXIVITY_AND_NOT_ANTI_REFLEXIVITY //既不具有自反性也不具有反自反性
} Reflexivity_Type;
5. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
（3）如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（4）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（5）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（6）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（7）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（8）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（9）如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在DetermineReflexivity函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
Reflexivity_Type DetermineReflexivity0609(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
//Add your code here
yourFunction; //调用自定义函数
}
6.10④ 试设计一算法，对某集合A上的一个二元关系R，判断R是否具有对称性或者反对称性。
实现下列函数：
/**
* 判断一个关系是否具有对称性或者反对称性。对一个关系R是否具有对称性或者反对称性，
* 有四种可能：是对称的；是反对称的；；既是对称的也是反对称的；既不是对称的也不是
* 反对称的。
* @param pBinaryRelationR： 卡氏积集合，该集合是一个pA上的二元关系
* @return: 返回一个Symmetry_Type枚举类型值。
* 如果pBinaryRelationSet具有对称性，则返回SYMMETRY;
* 如果pBinaryRelationSet具有反对称性，则返回ANTI_SYMMETRY;
* 如果pBinaryRelationSet既具有对称性，也具有对称性，则返回
* SYMMETRY_AND_ANTI_SYMMETRY;
* 如果pBinaryRelationSet既不具有对称性，也不具有反对称性，则返回
* NOT_SYMMETRY_AND_NOT_ANTI_SYMMETRY;
*/
Symmetry_Type DetermineSymmetry(pCartersianSet pBinaryRelationR)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. Symmetry_Type枚举类型定义：
typedef enum { //对于一个关系是否具有对称性的表示
SYMMETRY, //对称性
ANTI_SYMMETRY, //反对称性
SYMMETRY_AND_ANTI_SYMMETRY, //既具有对称性也具有反对称性
NOT_SYMMETRY_AND_NOT_ANTI_SYMMETRY //既不具有对称性也不具有反对称性
} Symmetry_Type;
5. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
（3）如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（4）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（5）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（6）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（7）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（8）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（9）如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在DetermineSymmetry函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
Symmetry_Type DetermineSymmetry(pCartersianSet pBinaryRelationR)
{
//Add your code here
yourFunction; //调用自定义函数
}
6.11④ 试设计一算法，对某集合A上的一个二元关系R，判断R是否具有传递性。
实现下列函数：
/**
* 判断一个关系是否具有传递性。
* @param pA： 原始集合
* @param pBinaryRelationR： 卡氏积集合，该集合是一个pA上的二元关系
* @return: 如果pBinaryRelationR具有传递性，则返回true，否则返回false
*/
boolean IsTransitive(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. Reflexivity_Type枚举类型定义：
typedef enum {
REFLEXIVITY,
ANTI_REFLEXIVITY,
NOT_REFLEXIVITY_AND_NOT_ANTI_REFLEXIVITY
}Reflexivity_Type;
5. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
（3）如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（4）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（5）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（6）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（7）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（8）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（9）如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在IsTransitive函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
boolean IsTransitive(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
//Add your code here
yourFunction; //调用自定义函数
}
6.12③ 试设计一算法，对某集合A上的一个二元关系R，求R的自反闭包。
实现下列函数：
/**
* 判断一个关系R的自反闭包
* @param pA： 原始集合
* @param pBinaryRelationR： 卡氏积集合，该集合是一个pA上的二元关系
* @return: pBinaryRelationR的自反闭包
*/
pCartersianSet ReflexiveClosure(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. Reflexivity_Type枚举类型定义：
typedef enum {
REFLEXIVITY,
ANTI_REFLEXIVITY,
NOT_REFLEXIVITY_AND_NOT_ANTI_REFLEXIVITY
}Reflexivity_Type;
5. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
（3）如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（4）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（5）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（6）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（7）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（8）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（9）如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在ReflexiveClosure函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pCartersianSet ReflexiveClosure(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
//Add your code here
yourFunction; //调用自定义函数
}
6.13③ 试设计一算法，对某集合A上的一个二元关系R，求R的对称闭包。
在实际计算中，无需给出集合A。
实现下列函数：
/**
* 判断一个关系R的对称闭包
* @param pBinaryRelationR： 卡氏积集合，该集合是一个pA上的二元关系
* @return: pBinaryRelationR的自反闭包
*/
pCartersianSet SymmetricClosure(pCartersianSet pBinaryRelationR)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. Reflexivity_Type枚举类型定义：
typedef enum {
REFLEXIVITY,
ANTI_REFLEXIVITY,
NOT_REFLEXIVITY_AND_NOT_ANTI_REFLEXIVITY
}Reflexivity_Type;
5. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
（3）如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（4）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（5）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（6）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（7）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（8）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（9）如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在SymmetricClosure函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pCartersianSet SymmetricClosure(pCartersianSet pBinaryRelationR)
{
//Add your code here
yourFunction; //调用自定义函数
}
6.14⑤ 试设计一算法，对某集合A上的一个二元关系R，求R的传递闭包。
实现下列函数：
/**
* 判断一个关系R的传递闭包
* @param pA： 原始集合
* @param pBinaryRelationR： 卡氏积集合，该集合是一个pA上的二元关系
* @return: pBinaryRelationR的传递闭包
*/
pCartersianSet TransitiveClosure(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
（3）如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（4）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（5）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（6）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（7）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（8）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（9）如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
（10）在同一个卡氏积集合R上进行复合运算（即求R ο R）时，需要特别注意的问题：在进行R ο R
运算时，必须复制一个R，即copyR，转为求解R X copyR，方可得到正确的结果。这是因为在作业
系统内部封装了一个唯一的当前位置遍历指针，当进行R ο R求解时，会因为当前位置指针同时
在多层嵌套循环中使用而被意外重置。
/** --------------------------------------------------------------------------
* 复制一个卡氏积集合。
* @param pA: 卡氏积集合
* @return: 一个与pA具有相同元素的卡氏积集合
*/
pCartersianSet copyCartersianSet(pCartersianSet pA)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在TransitiveClosure函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pCartersianSet TransitiveClosure(pOriginalSet pA, pOriginalSet pB, pCartersianSet pC)
{
//Add your code here
yourFunction; //调用自定义函数
}
6.15③ 实现Warshall算法，求某关系的传递闭包。
实现下列函数：
/**
* 对某集合A上的一个二元关系，求该关系的传递闭包。该关系使用矩阵表示。
* @param pM：二元关系矩阵
* @return: pM的传递闭包的关系矩阵
*/
pMatrix Warshall(pMatrix pM)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pMatrix为指向一个关系矩阵，该矩阵的元素只有两种取值：0和1。如果a[i][j] == 1，
则表示<i, j> ∈ R.
typedef struct matrix
{
......
......
} matrix, *pMatrix;
2. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
3. 提示与解析：
（1）如何遍历pMatrix关系矩阵？
① pMatrix关系矩阵在逻辑上是二维的。但实质上，在计算机存储实现过程中，任何
多维数组关系都是以一维形式存储。
提供一个outToBuffer函数，按行优先策略将矩阵所有元素输出至一个一维顺序缓
冲区。该缓冲区是可写的。在必要时，运算结果可以写回该缓冲区，然后再将该
缓冲区转换成pMatrix类型的关系矩阵。
/** --------------------------------------------------------------------
* 将矩阵的所有元素输出至一个连续缓冲区中。在该缓冲区中，每个元素都是
* matrixElem类型。
* @param pM: 矩阵
* @return：连续缓冲区的基址。
*/
pMatrixBase outToBuffer(pMatrix pM)
{
......
}
pMatrixBase是一个指针类型，定义如下：
typedef ......* pMatrixBase; //矩阵元素存储区基址
matrixElem类型定义如下
typedef ...... matrixElem; //矩阵元素类型定义
其中......部分的内容是完全相同的。
举例：例如某关系矩阵逻辑上如下所示：
0 1 0 0
1 0 1 0
0 0 0 1
0 1 0 0
则其在一维顺序缓冲区中如下所示：
0100101000010100\0
其中'\0'用于指示该缓冲区中有效区域的结尾，该字符不是关系矩阵的元素之一。
② 如何获取该缓冲区中第一个元素的值？
示例代码：
pMatrixBase pBase;
......
pBase = outToBuffer(pM); //假设关系矩阵pM已存在
则*pMatrixBase表示该缓冲区中第一个元素的值。
但为便于元素之间或者元素与常数的比较操作，提供一个将元素的值转换为int
类型值的函数。
/** -----------------------------------------------------------------
* 将矩阵元素转换成int类型值。
* @param elem: 矩阵中的元素
* @return：矩阵元素对应的int类型值。
*/
int converToInt(matrixElem elem)
{
......
}
③ 如何获取该缓冲区中下一个元素的值？
*(pMatrixBase++)或*(pMatrixBase + 1)
④ 如何进行元素值的计算？必须使用布尔加运算法则，即：
0 + 0 = 0; 0 + 1 = 1; 1 + 0 = 1; 1 + 1 = 1
⑤ 如何将某个值写至该缓冲区中的指定地址处？
/** --------------------------------------------------------------------
* 将矩阵中指定位置的元素赋值。
* @param index: 该缓冲区中的指定地址
* @param value: 值
*/
void putValue(pMatrixBase index, int value)
{
......
}
示例解释：
例如某时刻缓冲区如下所示：
001100\0
↑
index所指向位置
当执行语句：putValue(index, 0);后
缓冲区如下所示：
000100\0
（2）如何获得矩阵的维数？
/** --------------------------------------------------------------------
* 获得一个矩阵的行数或列数。在本题中，行数与列数是相等的。
* @param pM: 矩阵
* @return：矩阵的行数或列数。如果矩阵不存在，则返回0.
*/
int getDim(pMatrix pM)
{
......
}
（3）当计算完毕，所有运算结果已经写入缓冲区，则应当将缓冲区以及必要的参数创建
一个pMatrix关系矩阵，用于保存结果以及返回。
/** --------------------------------------------------------------------
* 创建一个矩阵。
* @param base: 矩阵元素所在的顺序缓冲区的基址
* @param n: 维数
* @return：一个创建好的矩阵。
*/
pMatrix createMatrix(pMatrixBase base, int n)
{
......
}
（4）提供一些打印函数。这类函数可以在程序的适当地方调用，用于打印当前运算结
果。这些打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关
调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用
手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做
好相关处理。
② matrixPrintf函数可以用于打印一个矩阵。
/** ----------------------------------------------------------------------
* 打印一个矩阵。
* @param pM: 矩阵元素
* @param option: 该参数值必须为PUBLIC
*/
void matrixPrintf(pMatrix pM, Option option)
{
......
}
示例代码：
pMatrix pM;
pM = ......;
matrixPrintf(pM, PUBLIC); //该语句被执行时，会打印一个关系矩阵
5. 如果需要自定义新的函数，则该函数必须定义在Warshall函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pMatrix Warshall(pMatrix pM)
{
//Add your code here
yourFunction; //调用自定义函数
}
7.01③ 试设计一算法，对某集合A上的一个二元关系R，判断R是否为等价关系。
实现下列函数：
/**
* 对某集合A上的一个二元关系R，判断R是否为等价关系
* @param pA： 原始集合
* @param pBinaryRelationR：卡氏积集合，该集合是一个pA上的二元关系
* @return: 如果R是A上的等价关系，则返回true；否则返回false
*/
boolean isEquivalentRelation(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
（3）如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（4）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（5）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（6）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（7）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（8）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（9）如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
（10）在同一个卡氏积集合R上进行复合运算（即求R ο R）时，需要特别注意的问题：在进行R ο R
运算时，必须复制一个R，即copyR，转为求解R X copyR，方可得到正确的结果。这是因为在作业
系统内部封装了一个唯一的当前位置遍历指针，当进行R ο R求解时，会因为当前位置指针同时
在多层嵌套循环中使用而被意外重置。
/** --------------------------------------------------------------------------
* 复制一个卡氏积集合。
* @param pA: 卡氏积集合
* @return: 一个与pA具有相同元素的卡氏积集合
*/
pCartersianSet copyCartersianSet(pCartersianSet pA)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在isEquivalentRelation函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
boolean isEquivalentRelation(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
//Add your code here
yourFunction; //调用自定义函数
}
7.02⑤ 试设计一算法，对某集合A上的一个二元关系R，求商集A/R。
实现下列函数：
/**
* 对某集合A上的一个二元关系R，判断R是否为等价关系
* @param pSetA：原始集合
* @param pBinaryRelationR： 卡氏积集合，该集合是一个pA上的二元关系
* @return: 商集A/R。商集中的每一个元素都是等价类集合。是pCompoundSet复合集合
类型；其元素是原始集合，即等价类集合是pOriginalSet类型。
* 注意：在求解过程中，请勿对pSetA和pBinaryRelationR进行任何的加工型操作。
* 即请勿修改该集合的结构，包括增加或删除集合中的元素，或者对
* pSetA和pBinaryRelationR进行赋值操作。
*/
pCompoundSet QuotientSet(pOriginalSet pSetA, pCartersianSet pBinaryRelationR)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. CompoundSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSet 指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef struct CompoundSet
{
......
......
}CompoundSet, *pCompoundSet; //复合集合定义
4. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
5. 提示与解析：
（1）如何访问或加工一个pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
⑤ 对于pOriginalSet原始集合，提供一个插入元素至集合中的基本操作。
/** --------------------------------------------------------------------------
* 将一个元素插入至原始集合中。
* 注意：插入时会检查是否存在重复元素，如果存在，则不插入。
* @param pSet: 集合
* @param pElem: 元素
*/
void elemInsertToOriginalSet(pOriginalSet pSet, pOriginalSetElem pElem)
{
......
}
⑥ 如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
⑤ 如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
⑥ 如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
⑦ 如何将一个序偶插入至卡氏积集合中？
a. 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
b. OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
⑧ isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
⑨ 提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
a. printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
b. CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（3）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（4）如何访问或加工一个pCompoundSet集合？pCompoundSet集合是一个复合集合，它的元
素类型是原始集合，即pOriginalSet类型。
① pCompoundSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCompoundSet集合时，
应当首先使用resetCompoundSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 复合集合
*/
void resetCompoundSet(pCompoundSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 复合集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSet getCurrentCompoundSetElem(pCompoundSet pSet)
{
......
}
③ nextCompoundSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 复合集合
*/
void nextCompoundSetPos(pCompoundSet pSet)
{
......
}
④ isEndOfCompoundSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 复合集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCompoundSet(pCompoundSet pSet)
{
......
}
⑤ 对于pCompoundSet复合集合，提供一个插入元素（即pOriginalSet类型的原始集合）至
复合集合中的基本操作。
/** --------------------------------------------------------------------------
* 将一个元素（即原始集合）插入至复合集合中。
* 注意：插入时会检查是否存在重复元素，如果存在，则不插入。
* @param pCompSet：复合集合
* @param pOriSet：元素（即原始集合），该元素必须已经被创建，而且必须非空。
*/
void originalSetInsertToCompoundSet(pCompoundSet pCompSet, pOriginalSet pOriSet)
{
......
}
如何创建一个pOriginalSet类型的原始集合？
/** --------------------------------------------------------------------------
* 创建一个空的原始集合。
* @return: 一个空的原始集合
*/
pOriginalSet createNullOriginalSet()
{
......
}
⑥ 特别需要注意的是，在插入一个元素（即原始集合）至复合集合中之前，该复合集合必须
已经被创建。在必要时，你需要首先创建一个空的复合集合，然后才可以向该复合集合插入
元素（即原始集合）。
/** --------------------------------------------------------------------------
* 创建一个空的复合集合。
* @return：返回一个空的复合集合
*/
pCompoundSet createNullCompoundSet()
{
......
}
6. 如果需要自定义新的函数，则该函数必须定义在QuotientSet函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pCompoundSet QuotientSet(pOriginalSet pSetA, pCartersianSet pBinaryRelationR)
//Add your code here
yourFunction; //调用自定义函数
}
7.03⑤ 试设计一算法，求某集合A上的模n同余关系。
实现下列函数：
/**
* 对某集合A上的一个二元关系R，判断R是否为等价关系
* @param pSet：原始集合
* @param n： 模
* @return: 集合A上的模n同余关系
* 注意：在求解过程中，请勿对pSetA和pBinaryRelationR进行任何的加工型操作。
* 即请勿修改该集合的结构，包括增加或删除集合中的元素。
*/
pCartersianSet CongruenceRelation(pOriginalSet pSet, int n)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. 提示与解析：
（1）如何访问或加工一个pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
⑤ 对于pOriginalSet原始集合，提供一个插入元素至集合中的基本操作。
/** --------------------------------------------------------------------------
* 将一个元素插入至原始集合中。
* 注意：插入时会检查是否存在重复元素，如果存在，则不插入。
* @param pSet: 集合
* @param pElem: 元素
*/
void elemInsertToOriginalSet(pOriginalSet pSet, pOriginalSetElem pElem)
{
......
}
⑥ 如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
⑦ 在本题中，需要将集合中的元素转换成int类型值，方可进行求余运算。
/** --------------------------------------------------------------------------
* 将元素转换为int类型值。
* @param pElem: 被转换的元素
* @return: pElem对应的int类型值（十进制）。
* 如果pElem不是由'0' ~ '9‘组成，则可能出现难以预料的转换结果。
*/
int originalSetElemToInt(pOriginalSetElem pElem)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
⑤ 如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
⑥ 如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
⑦ 如何将一个序偶插入至卡氏积集合中？
a. 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
b. OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
⑧ isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
⑨ 提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
a. printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
b. CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（3）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（4）在求原始集合A上的卡氏积A X A时，需要特别注意的问题：在进行A X A求解时，必须复制一个A，即
copyA，转为求解A X copyA，方可得到正确的结果。这是因为在作业系统内部封装了一个唯一的当前
位置遍历指针，当进行A X A求解时，会因为当前位置指针同时在多层嵌套循环中使用而被意外重置。
/** --------------------------------------------------------------------------
* 复制一个原始集合。
* @param pA: 原始集合
* @return: 一个与pA具有相同元素的原始集合
*/
pOriginalSet copyOriginalSet(pOriginalSet pA)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在CongruenceRelation函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pCartersianSet CongruenceRelation(pOriginalSet pSet, int n)
{
//Add your code here
yourFunction; //调用自定义函数
}
7.04③ 试设计一算法，对某集合A上的一个二元关系R，判断R是否为偏序关系。
实现下列函数：
/**
* 对某集合A上的一个二元关系R，判断R是否为偏序关系
* @param pA： 原始集合
* @param pBinaryRelationR： 卡氏积集合，该集合是一个pA上的二元关系
* @return: 如果R是A上的偏序关系，则返回true；否则返回false
*/
boolean isPartialOrderRelation(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
typedef struct OrderedCouple
{
......
......
} *pOrderedCouple; // 有序对
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 原始集合
*/
void resetOriginalSet(pOriginalSet pSet)
{
......
}
② getCurrentOriginalSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 原始集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当当前位置指针越界时，则返回NULL。
*/
pOriginalSetElem getCurrentOriginalSetElem(pOriginalSet pSet)
{
......
}
③ nextOriginalSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 原始集合
*/
void nextOriginalSetPos(pOriginalSet pSet)
{
......
}
④ isEndOfOriginalSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 原始集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
① pCartersianSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pCartersianSet集合时，
应当首先重置当前位置指针，使其指向集合的第一个元素。
/** --------------------------------------------------------------------------
* 重置链表中的当前位置指针，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
*/
void resetCartersianSet(pCartersianSet pSet)
{
......
}
② getCurrentCartersianSetElem函数可以获得当前位置指针指向的元素。
/** --------------------------------------------------------------------------
* 获取集合中当前正要访问的元素。
* @param pSet: 卡氏积集合
* @return：正常情况下，返回集合中当前正要访问的元素；如果集合为空，或者
* 当currentPos指针越界时，则返回NULL。
*/
pOrderedCouple getCurrentCartersianSetElem(pCartersianSet pSet)
{
......
}
③ nextCartersianSetPos函数可以令当前位置指针指向下一个元素。
/** --------------------------------------------------------------------------
* 将当前位置指针指向下一个元素。
* @param pSet: 卡氏积集合
*/
void nextCartersianSetPos(pCartersianSet pSet)
{
......
}
④ isEndOfCartersianSet函数用于判断是否已经遍历至集合的最后一个元素。
/** --------------------------------------------------------------------------
* 在对集合的访问过程中，判断是否已经遍历至最后（即最后一个元素已经被访问过）。
* @param pSet: 卡氏积集合
* @return：如果已经遍历到集合的最后，则返回true；否则返回false。
*/
boolean isEndOfCartersianSet(pCartersianSet pSet)
{
......
}
（3）如何判断一个pCartersianSet集合是否为空集？
isNullCartersianSet函数可用于判断一个pCartersianSet集合是否为空集。
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（4）如何将构造一个序偶？
createOrderedCouple函数可以将两个原始集合中的元素构造成一个序偶。
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素，作为序偶的第一元。
* @param second: 原始集合的元素，作为序偶的第二元。
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（5）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（6）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（7）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（8）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（9）如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
（10）在同一个卡氏积集合R上进行复合运算（即求R ο R）时，需要特别注意的问题：在进行R ο R
运算时，必须复制一个R，即copyR，转为求解R X copyR，方可得到正确的结果。这是因为在作业
系统内部封装了一个唯一的当前位置遍历指针，当进行R ο R求解时，会因为当前位置指针同时
在多层嵌套循环中使用而被意外重置。
/** --------------------------------------------------------------------------
* 复制一个卡氏积集合。
* @param pA: 卡氏积集合
* @return: 一个与pA具有相同元素的卡氏积集合
*/
pCartersianSet copyCartersianSetpCartersianSet pA)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在isPartialOrderRelation函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
boolean isPartialOrderRelation(pOriginalSet pA, pCartersianSet pBinaryRelationR)
{
//Add your code here
yourFunction; //调用自定义函数
}
8.01④ 试设计一算法，对于一个从集合A到集合B的二元关系R，判断R是否为函数。
实现下列函数：
/**
* 对于从集合A到集合B的一个二元关系R，判断R是否为函数
* @param pA： 原始集合
* @param pB： 原始集合
* @param pR： 卡氏积集合，该集合是一个从集合A到集合B的二元关系
* @return: 如果R是从集合A到集合B的函数，则返回true；否则返回false
*/
boolean isFunction( pOriginalSet pA,
pOriginalSet pB,
pCartersianSet pR )
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
可以使用迭代器（Iterator）。迭代器是面向对象编程语言类库中经常
使用的概念。但由于本作业程序采用C语言实现，故这里用到的迭代器仅具有“遍历集合中
全部元素”的能力。有关更多迭代器的知识，可以随意百度一下。
你可以自定义一个迭代器，然后令该迭代器从集合的第一个元素开始进行逐个遍历，直至
到达集合末端。当迭代器对最后一个元素遍历完毕后，将会被置为空。
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
pOriginalSet集合的迭代器定义如下：
typedef struct ...... {
......
}*pOriginalSetIterator; // 迭代器的结构体定义
以下是可能会用到的函数
① 重置一个迭代器
/** --------------------------------------------------------------------------
* 重置Iterator，使其指向集合的第一个元素。
* @param pSet: 原始集合
* @param pI: 需要被重置的Iterator
*/
void resetOriginalSetIterator(pOriginalSet pSet, pOriginalSetIterator & pI)
{
......
}
② 令迭代器指向下一个结点
/** --------------------------------------------------------------------------
* 将一个指向某原始集合结点的迭代器，迭代其指向下一个结点；如果无下一个结点，
* 则将该迭代器置为NULL。
* @param pI: 被操作的Iterator
*/
void nextOriginalSetIterator(pOriginalSetIterator &pI)
{
......
}
③ 复制一个迭代器
/** --------------------------------------------------------------------------
* 复制一个Iterator。该函数被调用后，会得到两个状态完全相同的迭代器
* @param pI1: 被复制的Iterator
* @param pI2: 复制后得到的Iterator。
*/
void copyOriginalSetIterator( pOriginalSetIterator pI1, pOriginalSetIterator &pI2)
{
......
}
④ 获得迭代器所指向的元素结点
/** --------------------------------------------------------------------------
* 获取当前Iterator所指向的集合元素。
* @param pI: 当前Iterator
* @return：返回当前Iterator指向的元素；如果Iterator为空，则返回NULL。
*/
pOriginalSetElem getOriginalSetElem(pOriginalSetIterator pI)
{
......
}
⑤ 如何判断某个元素是否属于pOriginalSet集合？
/** --------------------------------------------------------------------------
* 判断一个元素是否位于原始集合内。
* @param pSet: 集合
* @param pElem: 元素
* @return：pElem ∈ pSet，则返回true；否则返回false。
*/
boolean isInOriginalSet(pOriginalSet pSet, pOriginalSetElem pElem)
{
......
}
⑥ 如何判断一个pOriginalSet集合是否为空集？
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 原始集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
在pCartersianSet卡氏积集合集合中同样提供了迭代器。
pOriginalSet集合的迭代器定义如下：
typedef struct ...... {
......
}*pCartersianSetIterator; // 迭代器的结构体定义
以下是可能会用到的函数
① 重置一个迭代器
/** --------------------------------------------------------------------------
* 重置Iterator，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
* @param pI: 需要被重置的Iterator
*/
void resetCartersianSetIterator(pCartersianSet pSet, pCartersianSetIterator &pI)
{
......
}
② 令迭代器指向下一个结点
/** --------------------------------------------------------------------------
* 将一个指向某原始集合结点的迭代器，迭代其指向下一个结点；如果无下一个结点，
* 则将该迭代器置为NULL。
* @param pI: 被操作的Iterator
*/
void nextOriginalSetIterator(pOriginalSetIterator &pI)
{
......
}
③ 复制一个迭代器
/** --------------------------------------------------------------------------
* 复制一个Iterator。该函数被调用后，会得到两个状态完全相同的迭代器
* @param pI1: 被复制的Iterator
* @param pI2: 复制后得到的Iterator。
*/
void copyOriginalSetIterator(pOriginalSetIterator pI1, pOriginalSetIterator &pI2)
{
......
}
④ 获得迭代器所指向的元素结点
/** --------------------------------------------------------------------------
* 获取当前Iterator所指向的集合元素。
* @param pI: 当前Iterator
* @return：返回当前Iterator指向的元素；如果Iterator为空，则返回NULL。
*/
pOrderedCouple getCartersianSetElem(pCartersianSetIterator pI)
{
......
}
⑤ 如何判断一个pCartersianSet集合是否为空集？
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（3）pOrderedCouple是什么？
pOrderedCouple是序偶的结构体定义。在pCartersianSet卡氏积集合中，每一个元素都是
有序对。
typedef struct OrderedCouple {
pOriginalSetElem ......; //第一元
pOriginalSetElem ......; //第二元
} OrderedCouple, *pOrderedCouple; // 有序对
从定义可以看出，序偶中第一元和第二元的定义类型与pOriginalSet原始集合中的元素定义
相同（见getOriginalSetElem函数），都是pOriginalSetElem。
① 如何获得pOrderedCouple的第一元和第二元？
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
② 如何比较两个pOriginalSetElem变量是否相同？
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA == pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
（4）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（5）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（6）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（9）如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在isPartialOrderRelation函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
boolean isFunction( pOriginalSet pA,
pOriginalSet pB,
pCartersianSet pR )
{
//Add your code here
yourFunction; //调用自定义函数
}
8.02③ 判断一个关系是否为函数，如果是函数，则是什么类型：单射、满射、双射、
变换、非单射非满射。
实现下列函数：
/**
* 对于从集合A到集合B的一个二元关系R，判断R是否为函数
* @param pA： 原始集合
* @param pB： 原始集合
* @param pR： 卡氏积集合，该集合是一个从集合A到集合B的二元关系
* @return: Function_Type是一个enum类型。如果：
* pR是不是从集合A到集合B的函数，则返回NOT_FUNTION
* pR是是从集合A到集合B的非单射非满射函数，则返回COMMON_FUNCTION
* pR是是从集合A到集合B的单射且非满射函数，则返回INJECTIVE
* pR是是从集合A到集合B的满射且非单射函数，则返回SURJECTIVE
* pR是是从集合A到集合B的双射函数，则返回BIJECTIVE
* pR是是从集合A到集合B的满射函数，则返回TRANSFORM
*/
Function_Type functionKind( pOriginalSet pA,
pOriginalSet pB,
pCartersianSet pR )
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. Symmetry_Type定义：
typedef enum { //对于一个关系是否为函数、如果是函数，则是何种类型的表示
NOT_FUNTION, //不是函数
COMMON_FUNCTION, //非单射非满射函数
INJECTIVE, //单射非满射函数
SURJECTIVE, //满射非单射函数
BIJECTIVE, //双射函数
TRANSFORM //变换
} Symmetry_Type;
4. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
可以使用迭代器（Iterator）。迭代器是面向对象编程语言类库中经常
使用的概念。但由于本作业程序采用C语言实现，故这里用到的迭代器仅具有“遍历集合中
全部元素”的能力。有关更多迭代器的知识，可以随意百度一下。
你可以自定义一个迭代器，然后令该迭代器从集合的第一个元素开始进行逐个遍历，直至
到达集合末端。当迭代器对最后一个元素遍历完毕后，将会被置为空。
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
pOriginalSet集合的迭代器定义如下：
typedef struct ...... {
......
}*pOriginalSetIterator; // 迭代器的结构体定义
以下是可能会用到的函数
① 重置一个迭代器
/** --------------------------------------------------------------------------
* 重置Iterator，使其指向集合的第一个元素。
* @param pSet: 原始集合
* @param pI: 需要被重置的Iterator
*/
void resetOriginalSetIterator(pOriginalSet pSet, pOriginalSetIterator & pI)
{
......
}
② 令迭代器指向下一个结点
/** --------------------------------------------------------------------------
* 将一个指向某原始集合结点的迭代器，迭代其指向下一个结点；如果无下一个结点，
* 则将该迭代器置为NULL。
* @param pI: 被操作的Iterator
*/
void nextOriginalSetIterator(pOriginalSetIterator &pI)
{
......
}
③ 复制一个迭代器
/** --------------------------------------------------------------------------
* 复制一个Iterator。该函数被调用后，会得到两个状态完全相同的迭代器
* @param pI1: 被复制的Iterator
* @param pI2: 复制后得到的Iterator。
*/
void copyOriginalSetIterator( pOriginalSetIterator pI1, pOriginalSetIterator &pI2)
{
......
}
④ 获得迭代器所指向的元素结点
/** --------------------------------------------------------------------------
* 获取当前Iterator所指向的集合元素。
* @param pI: 当前Iterator
* @return：返回当前Iterator指向的元素；如果Iterator为空，则返回NULL。
*/
pOriginalSetElem getOriginalSetElem(pOriginalSetIterator pI)
{
......
}
⑤ 如何判断某个元素是否属于pOriginalSet集合？
/** --------------------------------------------------------------------------
* 判断一个元素是否位于原始集合内。
* @param pSet: 集合
* @param pElem: 元素
* @return：pElem ∈ pSet，则返回true；否则返回false。
*/
boolean isInOriginalSet(pOriginalSet pSet, pOriginalSetElem pElem)
{
......
}
⑥ 如何判断一个pOriginalSet集合是否为空集？
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 原始集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
在pCartersianSet卡氏积集合集合中同样提供了迭代器。
pOriginalSet集合的迭代器定义如下：
typedef struct ...... {
......
}*pCartersianSetIterator; // 迭代器的结构体定义
以下是可能会用到的函数
① 重置一个迭代器
/** --------------------------------------------------------------------------
* 重置Iterator，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
* @param pI: 需要被重置的Iterator
*/
void resetCartersianSetIterator(pCartersianSet pSet, pCartersianSetIterator &pI)
{
......
}
② 令迭代器指向下一个结点
/** --------------------------------------------------------------------------
* 将一个指向某原始集合结点的迭代器，迭代其指向下一个结点；如果无下一个结点，
* 则将该迭代器置为NULL。
* @param pI: 被操作的Iterator
*/
void nextOriginalSetIterator(pOriginalSetIterator &pI)
{
......
}
③ 复制一个迭代器
/** --------------------------------------------------------------------------
* 复制一个Iterator。该函数被调用后，会得到两个状态完全相同的迭代器
* @param pI1: 被复制的Iterator
* @param pI2: 复制后得到的Iterator。
*/
void copyOriginalSetIterator(pOriginalSetIterator pI1, pOriginalSetIterator &pI2)
{
......
}
④ 获得迭代器所指向的元素结点
/** --------------------------------------------------------------------------
* 获取当前Iterator所指向的集合元素。
* @param pI: 当前Iterator
* @return：返回当前Iterator指向的元素；如果Iterator为空，则返回NULL。
*/
pOrderedCouple getCartersianSetElem(pCartersianSetIterator pI)
{
......
}
⑤ 如何判断一个pCartersianSet集合是否为空集？
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（3）pOrderedCouple是什么？
pOrderedCouple是序偶的结构体定义。在pCartersianSet卡氏积集合中，每一个元素都是
有序对。
typedef struct OrderedCouple {
pOriginalSetElem ......; //第一元
pOriginalSetElem ......; //第二元
} OrderedCouple, *pOrderedCouple; // 有序对
从定义可以看出，序偶中第一元和第二元的定义类型与pOriginalSet原始集合中的元素定义
相同（见getOriginalSetElem函数），都是pOriginalSetElem。
① 如何获得pOrderedCouple的第一元和第二元？
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
② 如何比较两个pOriginalSetElem变量是否相同？
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA == pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
（4）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（5）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（6）如何获得一个序偶的第一元和第二元？序偶的第一元和第二元都是原始集合中的元素，定义
为pOriginalSetElem。getFirstElemOfOrderedCouple函数和getSecondElemOfOrderedCouple
函数可以获得某序偶的第一元和第二元。
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
（9）如何比较两个两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在isPartialOrderRelation函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
Function_Type functionKind( pOriginalSet pA,
pOriginalSet pB,
pCartersianSet pR )
{
//Add your code here
yourFunction; //调用自定义函数
}
8.03② 判断一个关系是否为函数，如果是函数并且该函数存在逆函数，则求出其逆函数。
实现下列函数：
/**
* 对于从集合A到集合B的一个二元关系R，判断R是否为函数
* @param pA： 原始集合
* @param pB： 原始集合
* @param pR： 卡氏积集合，该集合是一个从集合A到集合B的二元关系
* @return: 如果pR是从集合A到集合B的函数且存在逆函数，则求其逆函数：
* 如果pR不是从集合A到集合B的函数且存在逆函数，则返回NULL：
* 特别注意：空函数存不存在逆函数？如果存在，空函数的逆函数是什么？
* 空函数的逆函数是NULL吗？
*/
Function_Type functionKind( pOriginalSet pA,
pOriginalSet pB,
pCartersianSet pR )
{
//Add your code here
}
// --------------------------------------------------------------------------
注解：
1. pCartersianSet为指向一个卡氏积集合结构体的指针类型，集合元素的类型为序偶，
定义为pCouple。至于其具体实现，可以参考下面的伪代码。
typedef struct CartersianSet
{
......
......
}CartersianSet, *pCartersianSet; //卡氏积集合定义
至于集合内各元素的实际存储方式，并不需要关注。
2. pOriginalSet为指向一个原始集合结构体的指针类型，集合元素的类型为简单的元
素（非序偶），定义为pOriginalSetElem指针类型。至于其具体实现，可以参考下
面的伪代码。
typedef ... * pOriginalSetElem;
typedef struct OriginalSet
{
......
......
}OriginalSet, *pOriginalSet; //原始集合定义
至于集合内各元素的实际存储方式，并不需要关注。
3. boolean, TRUE, FALSE等已在作业系统内部定义好，参考源代码为：
typedef ...... boolean;
#define true ......
#define false ......
4. Symmetry_Type定义：
typedef enum { //对于一个关系是否为函数、如果是函数，则是何种类型的表示
NOT_FUNTION, //不是函数
COMMON_FUNCTION, //非单射非满射函数
INJECTIVE, //单射非满射函数
SURJECTIVE, //满射非单射函数
BIJECTIVE, //双射函数
TRANSFORM //变换
} Symmetry_Type;
4. 提示与解析：
（1）如何遍历pOriginalSet原始集合？
可以使用迭代器（Iterator）。迭代器是面向对象编程语言类库中经常
使用的概念。但由于本作业程序采用C语言实现，故这里用到的迭代器仅具有“遍历集合中
全部元素”的能力。有关更多迭代器的知识，可以随意百度一下。
你可以自定义一个迭代器，然后令该迭代器从集合的第一个元素开始进行逐个遍历，直至
到达集合末端。当迭代器对最后一个元素遍历完毕后，将会被置为空。
① pOriginalSet集合中包含了一个当前位置指针（该指针对学生程序不可见，不会给出
其实现定义），指向当前正要访问但未被的元素。当开始遍历一个pOriginalSet集合时，
应当首先使用resetOriginalSet函数重置当前位置指针，使其指向集合的第一个元素。
pOriginalSet集合的迭代器定义如下：
typedef struct ...... {
......
}*pOriginalSetIterator; // 迭代器的结构体定义
以下是可能会用到的函数
① 重置一个迭代器
/** --------------------------------------------------------------------------
* 重置Iterator，使其指向集合的第一个元素。
* @param pSet: 原始集合
* @param pI: 需要被重置的Iterator
*/
void resetOriginalSetIterator(pOriginalSet pSet, pOriginalSetIterator & pI)
{
......
}
② 令迭代器指向下一个结点
/** --------------------------------------------------------------------------
* 将一个指向某原始集合结点的迭代器，迭代其指向下一个结点；如果无下一个结点，
* 则将该迭代器置为NULL。
* @param pI: 被操作的Iterator
*/
void nextOriginalSetIterator(pOriginalSetIterator &pI)
{
......
}
③ 复制一个迭代器
/** --------------------------------------------------------------------------
* 复制一个Iterator。该函数被调用后，会得到两个状态完全相同的迭代器
* @param pI1: 被复制的Iterator
* @param pI2: 复制后得到的Iterator。
*/
void copyOriginalSetIterator( pOriginalSetIterator pI1, pOriginalSetIterator &pI2)
{
......
}
④ 获得迭代器所指向的元素结点
/** --------------------------------------------------------------------------
* 获取当前Iterator所指向的集合元素。
* @param pI: 当前Iterator
* @return：返回当前Iterator指向的元素；如果Iterator为空，则返回NULL。
*/
pOriginalSetElem getOriginalSetElem(pOriginalSetIterator pI)
{
......
}
⑤ 如何判断某个元素是否属于pOriginalSet集合？
/** --------------------------------------------------------------------------
* 判断一个元素是否位于原始集合内。
* @param pSet: 集合
* @param pElem: 元素
* @return：pElem ∈ pSet，则返回true；否则返回false。
*/
boolean isInOriginalSet(pOriginalSet pSet, pOriginalSetElem pElem)
{
......
}
⑥ 如何判断一个pOriginalSet集合是否为空集？
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 原始集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullOriginalSet(pOriginalSet pSet)
{
......
}
（2）如何遍历pCartersianSet卡氏积集合？
在pCartersianSet卡氏积集合集合中同样提供了迭代器。
pOriginalSet集合的迭代器定义如下：
typedef struct ...... {
......
}*pCartersianSetIterator; // 迭代器的结构体定义
以下是可能会用到的函数
① 重置一个迭代器
/** --------------------------------------------------------------------------
* 重置Iterator，使其指向集合的第一个元素。
* @param pSet: 卡氏积集合
* @param pI: 需要被重置的Iterator
*/
void resetCartersianSetIterator(pCartersianSet pSet, pCartersianSetIterator &pI)
{
......
}
② 令迭代器指向下一个结点
/** --------------------------------------------------------------------------
* 将一个指向某原始集合结点的迭代器，迭代其指向下一个结点；如果无下一个结点，
* 则将该迭代器置为NULL。
* @param pI: 被操作的Iterator
*/
void nextOriginalSetIterator(pOriginalSetIterator &pI)
{
......
}
③ 复制一个迭代器
/** --------------------------------------------------------------------------
* 复制一个Iterator。该函数被调用后，会得到两个状态完全相同的迭代器
* @param pI1: 被复制的Iterator
* @param pI2: 复制后得到的Iterator。
*/
void copyOriginalSetIterator(pOriginalSetIterator pI1, pOriginalSetIterator &pI2)
{
......
}
④ 获得迭代器所指向的元素结点
/** --------------------------------------------------------------------------
* 获取当前Iterator所指向的集合元素。
* @param pI: 当前Iterator
* @return：返回当前Iterator指向的元素；如果Iterator为空，则返回NULL。
*/
pOrderedCouple getCartersianSetElem(pCartersianSetIterator pI)
{
......
}
⑤ 如何判断一个pCartersianSet集合是否为空集？
/** --------------------------------------------------------------------------
* 判断原始集合是否为空集。
* @param pSet: 卡氏积集合
* @return：如果pSet是空集，则返回true；否则返回false。
*/
boolean isNullCartersianSet(pCartersianSet pSet)
{
......
}
（3）pOrderedCouple是什么？
pOrderedCouple是序偶的结构体定义。在pCartersianSet卡氏积集合中，每一个元素都是
有序对。
typedef struct OrderedCouple {
pOriginalSetElem ......; //第一元
pOriginalSetElem ......; //第二元
} OrderedCouple, *pOrderedCouple; // 有序对
从定义可以看出，序偶中第一元和第二元的定义类型与pOriginalSet原始集合中的元素定义
相同（见getOriginalSetElem函数），都是pOriginalSetElem。
① 如何获得pOrderedCouple的第一元和第二元？
/** --------------------------------------------------------------------------
* 获取序偶的第一元。
* @param pCouple: 序偶
* @return：返回pCouple的第一元。
*/
pOriginalSetElem getFirstElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
/** --------------------------------------------------------------------------
* 获取序偶的第二元。
* @param pCouple: 序偶
* @return：返回pCouple的第二元。
*/
pOriginalSetElem getSecondElemOfOrderedCouple(pOrderedCouple pCouple)
{
......
}
② 如何创建一个序偶？
/** --------------------------------------------------------------------------
* 创建一个有序对。
* @param first: 原始集合的元素
* @param second: 原始集合的元素
* @return：一个创建好的有序对。
*/
pOrderedCouple createOrderedCouple(pOriginalSetElem first, pOriginalSetElem second)
{
......
}
（4）如何将一个序偶插入至卡氏积集合中？
① 应当首先构造一个空的卡氏积集合。
/** --------------------------------------------------------------------------
* 创建一个空的卡氏积集合。
* @return: 一个空的卡氏积集合
*/
pCartersianSet createNullCartersianSet()
{
......
}
② OrderedCoupleInsertToCartersianSet函数可以将一个序偶插入至一个卡氏积集合中。
/** --------------------------------------------------------------------------
* 将一个有序对插入至卡氏积集合。
* @param pSet: 卡氏积集合
* @param pCouple: 有序对
*/
void OrderedCoupleInsertToCartersianSet(pCartersianSet pSet, pOrderedCouple pCouple)
{
......
}
（5）isInCartersianSet函数可用于判断一个序偶是否属于某卡氏积集合？
/** --------------------------------------------------------------------------
* 判断某序偶元素是否在卡氏积集合内。
* @param pSet: 卡氏积集合
* @param pNode: 序偶元素
* @return：如果pNode在pSet内，则返回true；否则返回false。
*/
boolean isInCartersianSet(pCartersianSet pSet, pOrderedCouple pNode)
{
......
}
（6）提供一些打印函数。这类函数可以在程序的适当地方调用，打印某些变量的值。这些
打印函数仅用于帮助调试，建议在程序调试完毕后，在程序中删除相关调用语句。
① printf函数：即C语言标准库中提供的打印函数，其用法请参考相关C语言使用手册。
注：调用该函数时，并不需要#include "stdio.h"，本作业系统已经在内部做好相关处理。
② CartersianSetPrintf函数可以用于打印一个卡氏积集合。
/** --------------------------------------------------------------------------
* 打印原始一个卡氏积集合。
* @param pSet: 即将被打印的卡氏积集合
* @param option: 必须使用固定常量值PUBLIC。
*/
void CartersianSetPrintf(pCartersianSet pSet, Option option)
{
......
}
示例代码：
pCartersianSet pCSet = ......;
CartersianSetPrintf(pCSet, PUBLIC); //该语句被执行时，会打印出pCSet中所有的序偶元素
（7）如何比较两个原始集合中的元素是否相等？
isEqualOriginalSetElem函数可用于判断两个两个原始集合中的元素是否相等。
/** --------------------------------------------------------------------------
* 判断两个元素是否相等。
* @param pElemA: 原始集合中的元素
* @param pElemB: 原始集合中的元素
* @return：如果pElemA = pElemB，则返回true；否则返回false。
*/
boolean isEqualOriginalSetElem(pOriginalSetElem pElemA, pOriginalSetElem pElemB)
{
......
}
5. 如果需要自定义新的函数，则该函数必须定义在isPartialOrderRelation函数前面，例如：
/**
* 定义自定义的函数
*/
void yourFunction() {
}
pCartersianSet inverseFunction( pOriginalSet pA,
pOriginalSet pB,
pCartersianSet pR )
{
//Add your code here
yourFunction; //调用自定义函数
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment