第一次实验题目

1、实验项目1三元组ADT1.1 实验目的本次实验的主要目的是在于帮助读者熟悉抽象数据类型的表示和实现方法。抽象数据类型需要借助固有数据类型来表示和实现，即利用高级程序设计语言中已经存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作，具体实现细节依赖于所用语言的功能。通过本次实验还可帮助学生复习高级语言的使用方法。1.2实验内容问题描述设计实现抽象数据类型“三元组”。每个三元组由任意三个实数的序列构成，基本操作包括：创建一个三元组，取三元组的任意一个分量，置三元组的任意一个分量，求三元组的最大分量，求三元组的最小分量，两个三元组的对应分量相加或相减，给三元组的各分量同乘一个比例因子，显示

2、三元组，销毁三元组等。基本要求实现创建一个三元组，取三元组的任意一个分量，置三元组的任意一个分量，求三元组的最大分量，求三元组的最小分量，显示三元组等基本操作。算法描述template <class Elem> class TriplePrivate: Elem e1; Elem e2 Elem e3;public: Triple(Elem v1, Elem v2, Elem v3) e1=v1; e2=v2; e3=v3; Elem Get(i) 初始条件：三元组已经存在，1i3；操作结果：返回三元组的第i个分量 Bool put(i,e) 初始条件：三元组已经存在，1i3；操作

3、结果：将三元组的第i个分量赋值为e，成功返回true，否则返回false;Elem GetMax()初始条件：三元组已经存在， 操作结果：返回三元组中最大分量值e;Elem GetMin()初始条件：三元组已经存在， 操作结果：返回三元组中最小分量值e;void Output（）初始条件：三元组已经存在， 操作结果：输出三元组中所有分量值;测试数据由学生任意指定。 选作内容实现两个三元组的对应分量相加或相减，给三元组的各分量同乘一个比例因子，销毁三元组等操作。实验项目2复数四则运算2.1 实验目的本次实验与实验项目1为同一类型实验，主要目的是在于帮助读者进一步熟悉抽象数据类型的表示和实现方法。

4、抽象数据类型需要借助固有数据类型来表示和实现，即利用高级程序设计语言中已经存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作，具体实现细节依赖于所用语言的功能。2.2实验内容问题描述设计实现一个可进行复数运算的演示程序。 基本要求实现下列六种基本运算：1） 由输入的实部和虚部生成一个复数；2） 两个复数求和；3） 两个复数求差；4） 两个复数求积；5） 从已知复数中分离出实部；6） 从已知复数中分离出虚部；运算结果以相应的复数或实数的表示形式显示。 算法描述该算法中Elem 为float 或double类型template <class Elem> class Compl

5、exPrivate: Elem reality; Elem falsehoodpublic: Triple(Elem r, Elem f) reality=r; falsehood=f; Complex operate+(const complex &)初始条件：已经存在两个复数；操作结果：将两个复数的实部和虚部分别进行向加得到一个新的复数Complex operate-(const complex &)初始条件：已经存在两个复数；操作结果：将两个复数的实部和虚部分别进行向减得到一个新的复数Complex operate*(const complex &)初始条件：已经

6、存在两个复数；操作结果：按照复数乘法规则将两个复数的实部相乘结果减去两个复数虚部相乘结果为新生成复数的实部；将两个复数的虚部和实部交叉相乘再相加的结果作为新生成复数的虚部。 Elem reality() 初始条件：复数已经存在；操作结果：返回复数的实部;Elem falsehood () 初始条件：复数已经存在；操作结果：返回复数的虚部;void Output（）初始条件：复数已经存在， 操作结果：以复数形式输出复数到屏幕上;测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据，如复数0。实现提示定义复数为两个相互之间存在次序关系的实数构成抽象数据类型，利用实数的操作来实现复数的操作

7、。 选作内容实现复数的其他运算，如：两个复数相除、求共轭。实验项目3基本线性表运算3.1 实验目的（1） 掌握基本线性表顺序存储的类型定义及C+语言实现。（2） 掌握基本线性表链式存储的类型定义及C+语言实现。（3） 掌握基本线性表顺序存储结构中的各种基本操作。（4） 掌握基本线性表链式存储结构中的各种基本操作。3.2实验内容问题描述基本线性表经常进行的运算操作有创建基本线性表、求基本线性表的长度、在基本线性表中查找某个数据元素、在某个位置插入一个新数据元素、在某个线性表中删除某个数据元素以及基本线性表的输出等操作。试编程实现基本线性表的这些基本运算。 基本要求 实现基本线性表的基本运算可以采

8、用链式存储方式实现，也可以采用顺序存储的方式实现，在此给出这两种存储方式的实现方法，学生可任选其一进行具体实现。算法描述1 顺序存储方式templet <class Elem> class AList：public List<Elem>private: int maxSize; int listSize; int fence; Elem* listArray;public:/线性表创建操作实现 AList(int size=DefaultListSize) maxSize=size; listSize=fence=0; listArray=new ElemmaxSize

9、 AList()delete listArray; void clear() delete listArray; listSize=fence=0; listArray=new ElemmaxSize; bool insert(const Elem&); bool append(const Elem&); bool remove(Elem&); void setStart()fence=0;void setEnd()fence=listSize; void prev()if(fence!=0) fence-; void next()if(fence<=listSi

10、ze) fence+ int Length() constreturn listSize; int leftLength() constreturn fence; int rightLength() constreturn listSize- fence; bool setPos(int Pos) if(pos>=0)&&(pos<=listSize)fence=pos; return(pos>=0)&&(pos<=listSize) /线性表中插入操作实现templet <class Elem> bool AList: in

11、sert(const Elem&item) if(listSize=maxSize) return false; for (int i=listSize;i>fence;i-) listArrayi=listArrayi-1;listArrayfence=item; listSize+; return true; /在线性表末尾追加数据操作实现templet <class Elem> bool AList: append(const Elem&item) if(listSize=maxSize)return false; listArraylistSize+=

12、item; return true; /线性表中删除操作实现templet <class Elem> bool AList: remove(Elem&it) if(rightlLenth()=0)return false; it=listArrayfence; for(int i=fence;i<listSize-1;i+) listArrayi=listArrayi+1; listSize-; return true; /线性表中查找操作实现templet <class Elem> bool AList:bool find(Elem k) Elem it

13、; for(L.setStart();L.getValue(it);L.next() if(K=it) return true;/found it return false;/ K not found2 链式存储方式template <class Elem>class LList:public List<Elem> private: Link<Elem>*head; Link<Elem>*tail; Link<Elem>*fence; int leftcnt, rightcnt;/基本线性表的创建操作实现 void init() fe

14、nce=head=tail=new Link<Elem> leftcnt=rightcnt=0; /init void removeall() while(head!=null) fence=head;head=head.next; delete fence; /removeall public: LList(int size=DefaultListSize)init(); LList()removeall(); void clear()removeall(); init(); bool insert(const Elem&); bool append(const Elem

15、&); bool remove(Elem&); void setStart() fence=head;rightcnt+=leftcnt; leftcnt=0; /setStart; void setEnd() fence=tail;leftcnt+=rightcnt;rightcnt=0; /setEnd void prev(); void next() if(fence!=tail)fence=fence->next; rightcnt-; leftcnt+ /next; int leftLength()const return leftcnt; int rightL

16、ength() constreturn rightcnt;bool setPos(int Pos); bool getValue(Elem &it) const if(rightLength()=0) return false; it=fence->next->element; return true; /getValue void print() const;/基本线性表插入操作的实现template <class Elem> bool LList<Elem>:insert(const Elem&item) fence->next=n

17、ew Link<Elem>(item,fence->next); if(tail=fence)tail=fence->next; rightcnt+; return true; /基本线性表末尾追加数据操作的实现template <class Elem> bool LList<Elem>:append(const Elem&item) tail=tail->next=new Link<Elem>(item,null); rightcnt+; return true; /基本线性表删除操作的实现template <c

18、lass Elem> bool LList<Elem>:remove(Elem& it) if(fence->next=NULL) return false; it=fence->next->element; Link<Elem>*Itemp=fence->next; fence->next=Itemp->next; if(tail=Itemp) tail=fence; delete Itemp rightcnt-; return true; template <class Elem> void LList&

19、lt;Elem>:prev() Link<Elem> * temp=head; if (fence=head) return; while(temp->next!=fence) temp=temp->next; fence=temp; leftcnt-; rightcnt+;template <class Elem> bool LList<Elem>:setPos(int pos) if(pos<0)|(pos>(rightcnt+leftcnt) return false; setStart(); for(int i=0;i&

20、lt;pos;i+) next(); return true; template <class Elem> void LList<Elem>:print() const Linl<Elem>*temp=head; cout<<“<”; while(temp!=fence) cout<<temp->next->element<<“ ”; temp=temp->next; /while; cout<<“|”;while(temp->next=NULL) cout<<temp

21、->next->element<<“ ”; temp=temp->next; /while;cout<<“>n”;测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据。实验提示（1） 基本线性表是数据结构中最简单、最常用的数据类型，它是学习其他数据结构类型的基础。因此，虽然基本线性表相对较为简单，但其各种运算内容较多，只有熟练掌握和理解基本线性表的基本内涵才能在解决实际问题的过程中准确运用。（2） 基本线性表的表示与存储是基本线性表进行各种运算的基础，所以，基本线性表中各个数据元素之间的逻辑和存储关系必须要在各种运算中准确体现。不能有任

22、何的思路混淆，也不能有任何的不确定性。选作内容两个线性表的并、交、差等运算的实现。实验项目4基本线性表就地逆置4.1 实验目的进一步掌握基本线性表的各种操作，深入理解线性表的存储方式。4.2实验内容问题描述基本线性表就地逆置是指在基本线性表现有空间的基础上，将基本线性表中的数据元素交换位置排列，排列完之后，新的顺序序列与原来的顺序序列刚好相反。如原来顺序序列“abcdef”，就地逆置后的新顺序序列为“fedcba”。根据基本线性表的链式和顺序两种存储结构分别完成：（1） 顺序结构的就地逆置。（2） 链式结构的就地逆置。 基本要求 充分理解题目要求，在对基本线性表逆置时，必须是在基本线性表原有空

23、间的基础上进行，不能借助临时变量所生成的临时空间，也不能借助其他形式的临时空间。且算法时间复杂度要求为O(n)。 算法描述 针对两种存储结构的基本线性表实现就地逆置的方法有多种，每种存储结构的实现方法选择一种讲解。（1）顺序结构基本线性表就地逆置。首先，创建一个包含若干个结点的基本线性表，由于在基本线性表的顺序存储结构中，数据元素的个数往往会少于所申请的存储单元数，因此，可以利用空闲存储单元中的某一个单元为中间单元，将基本线性表中前后对应位置上的数据元素交换位置，具体方法是将基本线性表的第1个数据元素和最后一个数据元素交换位置，第2个数据元素和倒数第2个数据元素交换位置，.，依次类推，直到所有元素都交换了位置，则就地逆置的过程就完成了。算法简单描述如下：template<class Elem> void Alist<Elem>:reverlist( ) int i; for(i=0; i<listSize/2; i+) listArraylistSize+1=listArrayi;/将第listSize+1号单元作为中间存储单元listArrayi=listArraylistSize-i-1;