第一次實驗題目

1、實驗項目1三元組ADT1.1 實驗?zāi)康谋敬螌嶒灥闹饕康氖窃谟趲椭x者熟悉抽象數(shù)據(jù)類型的表示和實現(xiàn)方法。抽象數(shù)據(jù)類型需要借助固有數(shù)據(jù)類型來表示和實現(xiàn)，即利用高級程序設(shè)計語言中已經(jīng)存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實現(xiàn)的操作來組合新的操作，具體實現(xiàn)細(xì)節(jié)依賴于所用語言的功能。通過本次實驗還可幫助學(xué)生復(fù)習(xí)高級語言的使用方法。1.2實驗內(nèi)容問題描述設(shè)計實現(xiàn)抽象數(shù)據(jù)類型“三元組”。每個三元組由任意三個實數(shù)的序列構(gòu)成，基本操作包括：創(chuàng)建一個三元組，取三元組的任意一個分量，置三元組的任意一個分量，求三元組的最大分量，求三元組的最小分量，兩個三元組的對應(yīng)分量相加或相減，給三元組的各分量同乘一個比例因子，顯示

2、三元組，銷毀三元組等。基本要求實現(xiàn)創(chuàng)建一個三元組，取三元組的任意一個分量，置三元組的任意一個分量，求三元組的最大分量，求三元組的最小分量，顯示三元組等基本操作。算法描述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) 初始條件：三元組已經(jīng)存在，1i3；操作結(jié)果：返回三元組的第i個分量 Bool put(i,e) 初始條件：三元組已經(jīng)存在，1i3；操作

3、結(jié)果：將三元組的第i個分量賦值為e，成功返回true，否則返回false;Elem GetMax()初始條件：三元組已經(jīng)存在， 操作結(jié)果：返回三元組中最大分量值e;Elem GetMin()初始條件：三元組已經(jīng)存在， 操作結(jié)果：返回三元組中最小分量值e;void Output（）初始條件：三元組已經(jīng)存在， 操作結(jié)果：輸出三元組中所有分量值;測試數(shù)據(jù)由學(xué)生任意指定。 選作內(nèi)容實現(xiàn)兩個三元組的對應(yīng)分量相加或相減，給三元組的各分量同乘一個比例因子，銷毀三元組等操作。實驗項目2復(fù)數(shù)四則運算2.1 實驗?zāi)康谋敬螌嶒炁c實驗項目1為同一類型實驗，主要目的是在于幫助讀者進(jìn)一步熟悉抽象數(shù)據(jù)類型的表示和實現(xiàn)方法。

4、抽象數(shù)據(jù)類型需要借助固有數(shù)據(jù)類型來表示和實現(xiàn)，即利用高級程序設(shè)計語言中已經(jīng)存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實現(xiàn)的操作來組合新的操作，具體實現(xiàn)細(xì)節(jié)依賴于所用語言的功能。2.2實驗內(nèi)容問題描述設(shè)計實現(xiàn)一個可進(jìn)行復(fù)數(shù)運算的演示程序。 基本要求實現(xiàn)下列六種基本運算：1） 由輸入的實部和虛部生成一個復(fù)數(shù)；2） 兩個復(fù)數(shù)求和；3） 兩個復(fù)數(shù)求差；4） 兩個復(fù)數(shù)求積；5） 從已知復(fù)數(shù)中分離出實部；6） 從已知復(fù)數(shù)中分離出虛部；運算結(jié)果以相應(yīng)的復(fù)數(shù)或?qū)崝?shù)的表示形式顯示。 算法描述該算法中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 &)初始條件：已經(jīng)存在兩個復(fù)數(shù)；操作結(jié)果：將兩個復(fù)數(shù)的實部和虛部分別進(jìn)行向加得到一個新的復(fù)數(shù)Complex operate-(const complex &)初始條件：已經(jīng)存在兩個復(fù)數(shù)；操作結(jié)果：將兩個復(fù)數(shù)的實部和虛部分別進(jìn)行向減得到一個新的復(fù)數(shù)Complex operate*(const complex &)初始條件：已經(jīng)

6、存在兩個復(fù)數(shù)；操作結(jié)果：按照復(fù)數(shù)乘法規(guī)則將兩個復(fù)數(shù)的實部相乘結(jié)果減去兩個復(fù)數(shù)虛部相乘結(jié)果為新生成復(fù)數(shù)的實部；將兩個復(fù)數(shù)的虛部和實部交叉相乘再相加的結(jié)果作為新生成復(fù)數(shù)的虛部。 Elem reality() 初始條件：復(fù)數(shù)已經(jīng)存在；操作結(jié)果：返回復(fù)數(shù)的實部;Elem falsehood () 初始條件：復(fù)數(shù)已經(jīng)存在；操作結(jié)果：返回復(fù)數(shù)的虛部;void Output（）初始條件：復(fù)數(shù)已經(jīng)存在， 操作結(jié)果：以復(fù)數(shù)形式輸出復(fù)數(shù)到屏幕上;測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如復(fù)數(shù)0。實現(xiàn)提示定義復(fù)數(shù)為兩個相互之間存在次序關(guān)系的實數(shù)構(gòu)成抽象數(shù)據(jù)類型，利用實數(shù)的操作來實現(xiàn)復(fù)數(shù)的操作

7、。 選作內(nèi)容實現(xiàn)復(fù)數(shù)的其他運算，如：兩個復(fù)數(shù)相除、求共軛。實驗項目3基本線性表運算3.1 實驗?zāi)康模?） 掌握基本線性表順序存儲的類型定義及C+語言實現(xiàn)。（2） 掌握基本線性表鏈?zhǔn)酱鎯Φ念愋投x及C+語言實現(xiàn)。（3） 掌握基本線性表順序存儲結(jié)構(gòu)中的各種基本操作。（4） 掌握基本線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)中的各種基本操作。3.2實驗內(nèi)容問題描述基本線性表經(jīng)常進(jìn)行的運算操作有創(chuàng)建基本線性表、求基本線性表的長度、在基本線性表中查找某個數(shù)據(jù)元素、在某個位置插入一個新數(shù)據(jù)元素、在某個線性表中刪除某個數(shù)據(jù)元素以及基本線性表的輸出等操作。試編程實現(xiàn)基本線性表的這些基本運算。 基本要求 實現(xiàn)基本線性表的基本運算可以采

8、用鏈?zhǔn)酱鎯Ψ绞綄崿F(xiàn)，也可以采用順序存儲的方式實現(xiàn)，在此給出這兩種存儲方式的實現(xiàn)方法，學(xué)生可任選其一進(jìn)行具體實現(xiàn)。算法描述1 順序存儲方式templet <class Elem> class AList：public List<Elem>private: int maxSize; int listSize; int fence; Elem* listArray;public:/線性表創(chuàng)建操作實現(xiàn) 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) /線性表中插入操作實現(xiàn)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; /在線性表末尾追加數(shù)據(jù)操作實現(xiàn)templet <class Elem> bool AList: append(const Elem&item) if(listSize=maxSize)return false; listArraylistSize+=

12、item; return true; /線性表中刪除操作實現(xiàn)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; /線性表中查找操作實現(xiàn)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 鏈?zhǔn)酱鎯Ψ绞絫emplate <class Elem>class LList:public List<Elem> private: Link<Elem>*head; Link<Elem>*tail; Link<Elem>*fence; int leftcnt, rightcnt;/基本線性表的創(chuàng)建操作實現(xiàn) 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;/基本線性表插入操作的實現(xiàn)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; /基本線性表末尾追加數(shù)據(jù)操作的實現(xiàn)template <class Elem> bool LList<Elem>:append(const Elem&item) tail=tail->next=new Link<Elem>(item,null); rightcnt+; return true; /基本線性表刪除操作的實現(xiàn)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”;測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。實驗提示（1） 基本線性表是數(shù)據(jù)結(jié)構(gòu)中最簡單、最常用的數(shù)據(jù)類型，它是學(xué)習(xí)其他數(shù)據(jù)結(jié)構(gòu)類型的基礎(chǔ)。因此，雖然基本線性表相對較為簡單，但其各種運算內(nèi)容較多，只有熟練掌握和理解基本線性表的基本內(nèi)涵才能在解決實際問題的過程中準(zhǔn)確運用。（2） 基本線性表的表示與存儲是基本線性表進(jìn)行各種運算的基礎(chǔ)，所以，基本線性表中各個數(shù)據(jù)元素之間的邏輯和存儲關(guān)系必須要在各種運算中準(zhǔn)確體現(xiàn)。不能有任

22、何的思路混淆，也不能有任何的不確定性。選作內(nèi)容兩個線性表的并、交、差等運算的實現(xiàn)。實驗項目4基本線性表就地逆置4.1 實驗?zāi)康倪M(jìn)一步掌握基本線性表的各種操作，深入理解線性表的存儲方式。4.2實驗內(nèi)容問題描述基本線性表就地逆置是指在基本線性表現(xiàn)有空間的基礎(chǔ)上，將基本線性表中的數(shù)據(jù)元素交換位置排列，排列完之后，新的順序序列與原來的順序序列剛好相反。如原來順序序列“abcdef”，就地逆置后的新順序序列為“fedcba”。根據(jù)基本線性表的鏈?zhǔn)胶晚樞騼煞N存儲結(jié)構(gòu)分別完成：（1） 順序結(jié)構(gòu)的就地逆置。（2） 鏈?zhǔn)浇Y(jié)構(gòu)的就地逆置。 基本要求 充分理解題目要求，在對基本線性表逆置時，必須是在基本線性表原有空

23、間的基礎(chǔ)上進(jìn)行，不能借助臨時變量所生成的臨時空間，也不能借助其他形式的臨時空間。且算法時間復(fù)雜度要求為O(n)。 算法描述 針對兩種存儲結(jié)構(gòu)的基本線性表實現(xiàn)就地逆置的方法有多種，每種存儲結(jié)構(gòu)的實現(xiàn)方法選擇一種講解。（1）順序結(jié)構(gòu)基本線性表就地逆置。首先，創(chuàng)建一個包含若干個結(jié)點的基本線性表，由于在基本線性表的順序存儲結(jié)構(gòu)中，數(shù)據(jù)元素的個數(shù)往往會少于所申請的存儲單元數(shù)，因此，可以利用空閑存儲單元中的某一個單元為中間單元，將基本線性表中前后對應(yīng)位置上的數(shù)據(jù)元素交換位置，具體方法是將基本線性表的第1個數(shù)據(jù)元素和最后一個數(shù)據(jù)元素交換位置，第2個數(shù)據(jù)元素和倒數(shù)第2個數(shù)據(jù)元素交換位置，.，依次類推，直到所有元素都交換了位置，則就地逆置的過程就完成了。算法簡單描述如下：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;