农夫过河问题的求解.doc

实验报告4
题目：编制一个演示农夫过河问题的求解的程序
班级：生物信息10级（1）姓名：李沙沙 学号：2010446013 完成日期：2012.01

一、需求分析
1．本演示程序中，是解决农夫、狼、羊和白菜过河问题。一个农夫带着一只狼，一只羊和一些菜过河，河边只有一条木船，由于船太小，只能装下农夫和他的一样东西，在无人看管的情况下。狼要吃羊，羊要吃菜，请问农夫如何菜能使三样东西平安过河？

2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令;相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。
3．程序执行的命令包括：
1）构造集合1；2）构造集合2；3）求并集；4）求交集；5）求差集；6）结束。
“构造集合1”和“构造集合2”时，需以字符串的形式键入集合元素。
4．测试数据
（1）Set1=“magazine”，Set2=“paper”，
Set1∪Set2=“aegimnprz”, Set1∩Set2=“ae”,Set1-Set2=“gimnz”;
（2）Set1=“012oper4a5tion89”, Set2=“error data”,
Set1∪Set2=“adeinoprt”, Set1∩Set2=“aeort”, Set1-Set2=“inp”。

二、程序的模块结构
本程序包含四个模块：
1）主程序模块：
void main(){
初始化;
dc{
接受命令;
处理命令;
}while(“命令”＝“退出”);
}
2）集合单元模块――实现集合的抽象数据类型;
3）有序表单元模块――实现有序表的抽象数据类型;
4）结点结构单元模块――定义有序表的结点结构。
有序表单元模块
主程序模块
集合单元模块
结点结构单元模块
各模块之间的调用关系如下：

三、祥细设计
1．元素类型、结点类型和指针类型
typedef char ElemType;//元素类型
typedef struct NodeType {
ElemType data;
NodeType *LinkType; // 结点类型，指针类型
Status MakeNode(LinkType &p, ElemType e)
{
//分配由p指向的数据元素为e、后继为“空”的结点，并返回TRUE，
//若分配失败，则返回FALSE
p=(Link Type)malloc(sixeof(Node Type));
if(!p)return FALSE;
p－>data=e;p－>next=NULL; return TRUE;
}
void freeNode(LinkType &p)
{ //释放p所指结点
}
Link Type Copy(LinkType p)
{
//复制生成和指针p所指结点有同值元素的新结点并返回，
//若分配空间失败，则返回空指针。新结点的指针域为NULL
s=(LinkType)malloc(sizeof(NodeType));
if(!s)return NULL;
s－>data=p－>data; s－>next＝NULL; return s;
}
ElemType Elem(LinkType p)
{
//若指针p!＝NULL，则返回p所指结点的数据元素，否则返回‘#’
}
LinkType SuccNOde(LinkType p)
{
//若指针p!=NULL，则返回指向p所指结点的后继元素的指针，
//否则返回UNLL
}

2．根据有序表的基本操作的特点，有序表采用有序链表实现。链表设头、尾两个指针和表长数据域，并附设头结点，头结点的数据域没有实在意义。
Sypedef struce {
LinkType head, tail; //分别指向线性链表的头结点和尾结点
Int size; //指示链表当前的长度
}OrderedLise; //有序链表类型
有序链表的基本操作设置如下：
bool InitList (OrderedList &L);
//构造一个带头结点的空的有序链表L，并返回TRUE;
//若分配空间失败，则令L.head为NULL，并返回FALSE
void destroyList(OrderedLIst &L);
//销毁有序链表L
bool Listempty(OrderedList L);
//若L不存在或为“空表”，则返回TRUE，否则返回FALSE
int ListLengty(OrderedList L);
//返回链表的长度
Linktype GetelemPos(OrderedList L, int pos);
//若L存在且0<pos<L, size+1，则返回指向第pos个元素的指针，
//否则返回NULL
bool LocateElem(OrderedList L, elemType e, LinkType &q);
//若有序链表L存在且在表中存在元素e，则q指示L中第一个值为e的
//结点的位置，并返回TRUE;否则q指示第一个大于e的元素的前驱的
//位置，并返回FALSE
void Append(OrderedList &L, Linktype s );
//在已存在的有序链表L的末尾插入指针s所指结点
void InsertAfter(OrderedList &L, LinkType q, LinkType s);
//在已存在的有序链表L中q所指示的结点之后插入指针s所指结点
void ListTraverse(LinkType p, status(*visit)(LinkType q));
//从p(P!=NULL)指示的结点开始，依次对每个结点调用函数visit
其中部分操作的伪码算法如下：
BOOL InitList(OrderdeList &L)
{
if(MakeNode(head, ˊˊ)){ //头结点的虚设元素为空格符ˊˊ
L.tail=L.head; L.size=0, return TRUE;
}
else{ L.head=NULL; return FALSe; }
} //InitList

void DestroyList(OrderedList &L)
{
p=L.head;
while (P) {q=SuccNode(P); FreeNOde(q); }
L.head=L.tail=NULL;
} //destroyList

LinkType GetElemPos(OrderedList L, int pos)
{
if(! L.head || pos<1 || pos>L.size) retun NULL;
else if ( pos = = L.size) return L.tail;
else {
p=L.head－>mext; k=1;
while ( p &&k<pos) {p= SuccNode(p); k++;}
return p;
}
} //GetElemPos

status LocateElem(OrderedList L, elemType e, LinkType &p)
{
if (L.head) {
per=L.head; p=pre－>next;
//pre指向*p的前驱，p指向第一个元素结点
while(p && p－>data<e) {pre=p; p=SuccNode(p); }
if (p &&p－>data <e){pre=p; p=SuccNode(p);}
dlse{p=pre; return FALSE;}
}
dlse return FALSE;
} //LocateElem
void Append(OrderedList &L, LinkType s)
{
if(L.head &&s) {
if(L.tail !=L.head) L.tail－>next=s;
else L.head－next=s;
L.tail=s; L.size++;
}
} //Append

void InsertAfter(OrderList &L, LinkType q, LinkType s)
{
if(L.head &&1&&s) {
s－>next=1－>next; q－>next=s;
if(L.tail= =1) L.tail=s;
L.sixe++;
}
} //InsertAfter

void Listtraverse (LinkType p, Status (visit) (LinkType q) )
{
while(p) {visit(p); p=SuccNode(P);}
} //ListTraverse

3．集合类型的基本操作的类C伪码描述如下：
void CreateSet( OrderedSet &T, char *s)
{
//生成由串s中小写字母的构成的集合T，IsLower是小写字母判别函数
if(InitList(T) ) //构成空集T
for (I=1; i<=length(s); I++)
if ( IniList(T) ) //构成空集T
for(I=1; i<=length(s); I++)
if(islower(s[i]) &&! Locateelem(T, s[i], p) )
//过滤重复元素并按字母次序大小插入
if(MakeNode(q, s[i]) ) InsertAfter(T, p, q);
} //CreateSet

void destroySet(OredredSet &T)
{
//销毁集合T的结构
DestroyList(T);
} //destroyList

void Union(OrderedSet &T, OrderedSet S1, OrderedSet S2)
{
//求已建成的集合S1和S2的并集T，即：S1,head!=NuLL且S2,head!=NULL
if(InitList(T) ) {
P1=GetElemPos(S1, 1); P2=GetElemPos(S2,1);
While(p1 && P2) {
c1=Elem(p1); c2=Elem(p2);
if(c1<=c2) {
Append(T, Copy(pq)); p1=SuccNode(p1);
if(c1= =c2) p2=SuccNode(p2);
}
else{Append(T,copy(P2)); p2=SuccNode(pw); }
}
while(p1)
{Append(T,copy(p1)); p1=succNode(p1);}
while(p2)
{Append(T, copy(p2)); P2=succNode(p2); }
}
} //Union

void Intersection(Orderedset &T, OrderedSet S1, OrderedSet S2)
{
//求集合S1格S2的交集T
if(! InitList(T)) T.head=NuLL;
else{
p1=GetElemPos(S1, 1); p2=GetelemPos(S2, 1);
while(p1 &&p2) {
c=Elem(p1); c2=elem(p2);
if(c1<c2)p2=SuccNode(p2);
else { //c1= =c2
Append(T, Copy(p1));
p1=SuccNode(p1); p2=SuccNode(p2);
} //else
} //while
} //else
} //Intersection

void difference(Orderedset &T, OrderedSet S1, OrderedSet S2)
{
//求集合S1和S2的差集T
if(! InitList(T)) T.head=NULL;
else{
p1=getElemPos(S1, 1); p2=getelemPos(S2, 1);
while(p1 &&p2) {
c1=elem(p1); c2=Elem(p2);
if(c1<c2) {Append(T, Copy(p1)); p1=SuccNode(p1); }
dlse if (c1>c2) p2=succNode(p2);
else //c1= =c2
{p1=succNode(p1); p2=SuccNOde(p2); }
} //while
while(p1)
{append(T, Copy(p1)); p1=succNOde(p1); }
} //else
} //difference

void writeSetElem(LinkType p)
{
// 显示集合的一个元素
printf(ˊ,ˊ); Writeelem(Elem(p));
} //writeSetelem

void printSet(OrderedSet T)
{
// 显示集合的全部元素
p=getelemPos(T, 1);
printf(ˊ)ˊ);
} //PrintSet

4．主函数和其他函数的伪码算法
void main( )
{
// 主函数
Initialization( ); //初始化
do{
Readcommand(cmd); //读入一个操作命令符
Interpret(cmd); //解释执行操作命令符
}while(cmd!=ˊqˊ &&cmd != ˊQˊ);
} //mian

void Initialization( )
{
//系统初始化
clrscr( ); //清屏
在屏幕上方显示操作命令清单：MakeSet1--1 MakeSet2--2 Union--u
Intersaction--i difference--d Quit--q;
在屏幕下方显示操作命令提示框;
CreateSet(set1, ″″); Printset(Set1); //构造并显示空集Set1
CreateSet(Set2, ″″) ; PrinSet(Set1); //构造并显示空集Set2
} //Initialization

void readcommand(char cmd)
{
//读入操作命令符
显示健入操作命令的提示信息;
do{cmd=getche( );}
while(cmd ∈[′1′,′2′,′u′,′U′,′i′,′I′,′d′,′D′,′q′,′Q′]));
}

void Inetrpret (char cmd)
{
//解释执行操作命令cmd
switch (cmd) {
case′1′: 显示以串的形式键集合元素的提示信息;
scanf(v); //读入集合元素到串变量v
createSet(Set1, v); PrintSet(Set1); //构造并显示有序集Set1
break;
case′2′：显示以串的形式键入集合元素的提示信息;
scanf(v); //读入集合元素到串变量v
CS肜（Set2, v）; Printset(Set2); //构造并显示有序集Set2
Break;
case′u′, ′U′: Union(set3, Set1, Set2); //求有序集Set1和Set2的并集Set3
Printset(Set3); //显示并集Set3
DestroyList(Set3); // 销毁并集Set3
break;
case′i′,′I′: Intersaction(Set3, Set1, Set2); //求有序集Set1和Set2的交集Set3
PrintSet(Set3);
DestroyLIst(Set3);
break;
case′d′,′D′: Difference(Set3, Set1, Set2); //求集合Set1和Set2的差集
Set3
PrintSet(Set3);
DestroyList(Set3);
}
} //Interpret

5．函数的调用关系图反映了演示程序的层次结构：
DestrotySet CreateSet Union Intersection Difference PrintSet
main
Initialization Read Command Interpret
DestroyLIst LocateElem InsertAfter InitList Append ListTraverse
FreeNode MakeNode writeelem

四、调试分析
1．由于对集合的三种运算的算法推敲不足，在有序链表类型的早期版本未设置尾指针和Append操作，导致算法低效。
2．刚开始时曾忽略了一些变量参数的标识“&”，使调试程序时费时不少。今后应重视确定参数的变量和赋值属性的区分和标识。
3．本程序的模块划分比较合理，且尽可能将指针的操作封装在结点和链表的两个模块中，致使集合模块的调试比较顺利。反之，如此划分的模块并非完全合理，因为在实现集合操作的编码中仍然需要判别指针是否为空。按理，两个链表的并，交和差的操作也应封装在链表的模块中，而在集合的模块中，只要进行相应的应用即可。
4．算法的时空分析
（1）由于有序表采用带头结点的有序单链表，并增设尾指针和表的长度两个标识，各种操作的算法时间复杂度比较合理。InitList, Listempty, Listlength, Append和InsertAfter以及确定链表中第一个结点和之后一个结点的位置都是O（1）的，destroyList，LocateElem和TraverseLIst及确定链表中间结点的位置等则是O（n）的，n为链表长度。
（2）基于有序链表实现的有序集的各种运算和操作的时间复杂度分析如下：
构造有序集算法CreateSet读入n个元素，逐个用Locateelem判定不在当前集合中及确定插入位置后，才用InsertAfetr插入到有序集中，所以时间复杂度是O(n2)。
求并集算法Union利用集合的“有序性”将两个集合的m+n个元素不重复地依次利用Append插入到当前并集的末尾，故可在O(m+n)时间内完成。
可对求交集算法Intersection和求差集算法Difference作类似地分析，它们也是O(m+n)。
销毁集合算法DestroySet和显示集合算法PrintSet都是对每个元素调用一个O(1)的函数，因此都是O(n)的。
除了构造有序集算法CreateSet用一个串变量读入n个元素，需要O(n)的辅助空间外，其余算法使用的辅助空间与元素个数无关，即是O(1)的。
5．本实验作业采用数据抽象的程序设计方法，将程序划分为四个层次结构：元素结点、有序链表、有序集和主控模块，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。

五、测试结果
执行命令′1′：键入magazine后，构造集合Set1:[a,e,g,I,m,n,z]
执行命令′2′：键入paper后，构造集合Set2:[a,e,p,r]
执行命令′u′：构造集合Set1和Set2的并集：[a,e,g,I,m,n,p,r,z]
执行命令′i′：构造集合Set1和Set2的交集：[a,e]
执行命令′d′：构造集合Set1和Set2的差集：[g,I,m,n,z]
执行命令′1′：键入012oper4aytion89后，构造集合Set1:[a,e,I,n,o,p,r,t]
执行命令′2′：键入errordata后，构造集合Set2：[a,d,e,o,r,t]
执行命令′u′：构造集合Set1和Set2的并集：[a,d,e,I,n,o,p,r,t]
执行命令′i′：构造集合Set1和Set2的交集，[a,e,o,r,t]
执行命令′d′：构造集合Set1和Set2的差集：[i,n,p]

六、附录
源程序文件名清单：
Node.H //元素结点实现单元
OrdList.H //有序链表实现单元
OrderSet.H //有序集实现单元
SetDemos.c //主程序