Skip to content

Instantly share code, notes, and snippets.

@bcho
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.
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