第7章 从过程抽象到数据抽象

第7章从过程抽象到数据抽象过程抽象是面向过程程序设计的基本手段。过程抽象的结果是函数。函数的好处在于它提供了信息隐藏和重用性，使用函数只需知道其名字和参数形式，而无需了解其实现细节，可以在不同地方多次使用；函数的内部实现可以采用多种方式，但并不会影响函数的使用。数据抽象是面向对象程序设计的基本手段。数据抽象的结果是数据类型。数据类型把数据和其上的操作密切地、逻辑地联系在一起，形成一个整体，实现了更好的信息隐藏和重用性。而且它在思维的抽象层次上较为接近人们通常的思维模式。7．1从过程抽象到数据抽象设有如下的要求：向整数集合的某一子集添加若干元素，从该集合中删除某些元素，判断指定元素是否在该集合中。1．分析与实现在程序中用整数数组表示整数集合：集合（数组）最多含MAXLENGTH个元素，集合当前有count个元素。数据定义如下：intset[MAXLENGTH];unsignedcount;程序中抽象出三个集合上的操作：•添加（Add）•删除（Remove）•判断（Isin）7．1．1集合的实现与使用（1）voidAdd(intelem,int*pset,unsigned&count)这个函数的功能是：添加新元素elem到集合pset。若元素elem不在集合pset中，elem加到pset尾部，集合的元素个数count加1；否则，元素elem已在pset中，结束。函数定义如下：voidAdd(intelem,int*pset,unsigned&count){if(countMAXLENGTH)if(!Isin(elem,pset,count))*(pset+(count)++)=elem;}（2）Remove(intelem,int*pset,unsigned&count)这个函数的功能是：从集合pset中删除元素elem。若元素elem在集合pset中且位于pset[i]，则将pset中最后一个元素pset[count-1]替换pset[i]，集合的元素个数count减1；否则，给出元素不在集合中的提示信息。函数定义如下：voidRemove(intelem,int*pset,unsigned&count){for(unsignedi=0;icount&&*(pset+i)!=elem;i++);if(icount)*(pset+i)=*(pset+(count--)-1);elsecout待删除元素elem不在集合中。endl;}（3）Isin(intelem,int*pset,unsignedcount)这个函数的功能是：判断元素elem是否在集合pset中。从头至尾检查集合pset中的元素，若有元素elem，返回1；否则，返回0。函数定义如下：intIsin(intelem,int*pset,unsignedcount){for(unsignedi=0;icount&&*(pset+i)!=elem;i++);return(icount);}2．完整的源程序#includeiostreamusingnamespacestd;#defineMAXLENGTH100voidAdd(intelem,int*pset,unsigned&count);voidRemove(intelem,int*pset,unsigned&count);intIsin(intelem,int*pset,unsignedcount);intmain(){intset[MAXLENGTH];//集合unsignedcount=0;//集合中当前元素个数intelement,choice;while(1){cout操作选择：endl;cout1--添加元素endl;cout2--删除元素endl;cout3--判断元素endl;cout0--退出endl;cout请输入您的选择：;cinchoice;switch(choice){case1:cout输入待添加元素:;cinelement;Add(element,set,count);break;case2:cout输入待删除元素:;cinelement;Remove(element,set,count);break;case3:cout输入待判断元素:;cinelement;if(Isin(element,set,count))cout元素element在集合中。endl;elsecout元素element不在集合中。endl;}if(choice==0)break;}return0;}intIsin(intelem,int*pset,unsignedcount){for(unsignedi=0;icount&&*(pset+i)!=elem;i++);returnicount;}voidAdd(intelem,int*pset,unsigned&count){if(countMAXLENGTH)if(!Isin(elem,pset,count))*(pset+(count)++)=elem;}voidRemove(intelem,int*pset,unsigned&count){for(unsignedi=0;icount&&*(pset+i)!=elem;i++);if(icount)*(pset+i)=*(pset+(count--)-1);elsecout待删除元素elem不在集合中。endl;}3．讨论针对上面程序的实现，我们来讨论如下两个问题：（1）需求变化，程序改动是否容易？例如，将集合的数据表示改为用链表存储，可不要count，集合的三个函数的实现及它们的使用都得改动。也就是整个程序都得改动，修改不是局部化的。（2）能否重用？函数级重用，其它难以重用。产生如此毛病的原因是上面的程序实现了整数集合这样一种数据结构，并使用这种数据结构，把两者混在一起，过分针对具体问题。实际上，通常需要被重用的是集合，故应该把整数集合实现与应用分开，来做到修改局部化和可重用。1．方案使用结构体类型，将整数集合做成数据类型。structSet{intdata[MAXLENGTH];unsignedcount;};这样每个整数集合是一个结构体变量，需要将成员变量初始化，故提供如下四个函数：voidInitialize(Set*pSet);//集合初始化voidAdd(intelem,Set*pSet);//向集合中添加元素elemvoidRemove(intelem,Set*pSet);//从集合中删除元素elemintIsin(intelem,Set*pSet);//判断元素elem是否在集合中将整数集合的定义放在一个头文件（文件名Set.h）中，将整数集合的实现放在一个文件（文件名为Set.cpp）中，而将集合的应用放在另外的文件（文件名为AppSet.cpp）中，这样将实现和使用分开。要使用整数集合就包含整数集合的头文件，定义一个Set型的变量，重用非常方便。7．1．2将集合的实现与使用分开2．完整的源程序整数集合的定义：//Set.h集合实现为数据类型#defineMAXLENGTH100structSet{intdata[MAXLENGTH];unsignedcount;};voidInitialize(Set*pSet);voidAdd(intelem,Set*pSet);voidRemove(intelem,Set*pSet);intIsin(intelem,Set*pSet);整数集合的函数实现：//Set.cpp#includeSet.h#includeiostream.hvoidInitialize(Set*pSet){pSet-count=0;}voidAdd(intelem,Set*pSet){if(pSet-countMAXLENGTH)if(!Isin(elem,pSet))pSet-data[(pSet-count)++]=elem;}voidRemove(intelem,Set*pSet){for(unsignedi=0;ipSet-count&&pSet-data[i]!=elem;i++);if(ipSet-count)pSet-data[i]=pSet-data[((pSet-count)--)-1];elsecout待删除元素elem不在集合中。endl;}intIsin(intelem,Set*pSet){for(unsignedi=0;ipSet-count&&pSet-data[i]!=elem;i++);returnipSet-count;}使用整数集合的应用程序如下：//AppSet.cpp#includeSet.h#includeiostream.hintmain(){intelement,choice;Sets;/*集合*/Initialize(&s);/*集合中当前元素个数置0*/while(1){cout操作选择：endl;cout1--添加元素endl;cout2--删除元素endl;cout3--判断元素endl;cout0--退出endl;cout请输入您的选择：;cinchoice;switch(choice){case1:cout输入待添加元素:;cinelement;Add(element,&s);break;case2:cout输入待删除元素:;cinelement;Remove(element,&s);break;case3:cout输入待判断元素:;cinelement;if(Isin(element,&s))cout元素element在集合中。endl;elsecout元素element不在集合中。endl;}if(choice==0)break;}return0;}3．讨论在这个程序中，整数集合被实现成数据类型，整数集合的实现与使用分开了。这样，整数集合的实现可以很容易地被重用，而且是模块级的重用。应用程序按整数集合的实现提供的接口（函数原型）来使用整数集合，整数集合的实现的内部细节的改变不影响应用程序，实现了修改局部化。给整数集合的实现者和使用者都带来了方便：实现者可以用多种方式实现集合；使用者无需知道集合实现的内部细节。例如可以用链表来实现集合。7．1．3将集合用链表实现1．方案使用单链表来存储集合元素，链表结点定义为：structNode{intelement;Node*pNodeNext;};集合类型只含链表头，无需结点个数变量count，增加求元素个数的函数Card。structSet{Node*pNodeNext;};2．完整源程序整数集合的定义为：//Set.h整型集合的链表实现#defineMAXLENGTH100structNode{intelement;Node*pNodeNext;};structSet{Node*pNodeHead;};voidInitialize(Set*pSet);voidAdd(intelem,Set*pSet);voidRemove(intelem,Set*pSet);intIsin(intelem,Set*pSet);unsignedCard(Set*pSet);//Set.cpp整数集合的函数实现为：#includeSet.h#includeiostream.hvoidInitialize(Set*pSet){pSet-pNodeHead=NULL;}voidAdd(intelem,Set*pSet){if(Card(pSet)MAXLENGTH)if(!Isin(elem,pSet))if(Node*p=newNode){//生成新结点p