實(shí)驗(yàn)八泛型程序設(shè)計(jì)

1、實(shí)驗(yàn)八 泛型程序設(shè)計(jì)軟件1502楊成進(jìn) 1513 0 32 3 0一、實(shí)驗(yàn)?zāi)康? 了解鏈表類得定義與實(shí)現(xiàn) ,學(xué)習(xí)其使用方法。2。了解棧類得定義與實(shí)現(xiàn)，學(xué)習(xí)其使用方法。3了解隊(duì)列類得定義與實(shí)現(xiàn)，學(xué)習(xí)其使用方法。4了解C +標(biāo)準(zhǔn)模板庫(kù)STL得使用方法。二、實(shí)驗(yàn)任務(wù)1。 編寫程序lin k .h,實(shí)現(xiàn)教材中例96得鏈表類。在測(cè)試程序Iab9 1.c pp中定義兩個(gè)整 型鏈表A與B,分別插入5個(gè)元素，然后把B中得元素加入 A得尾部。2。 編寫程序q ueu e h，用鏈表實(shí)現(xiàn)隊(duì)列（或棧）類。在測(cè)試程序la b9 2。cpp中定義 一個(gè)整型隊(duì)列（或棧）對(duì)象，插入5個(gè)整數(shù)，壓人隊(duì)列（或棧），再依次取出并顯

2、示出來(lái)。3。使用C+ +標(biāo)準(zhǔn)模板庫(kù)（S TL沖得雙向隊(duì)列類（d eq ue）重新實(shí)現(xiàn)上一小題。三、實(shí)驗(yàn)步驟1 .參照教材C+語(yǔ)言程序設(shè)計(jì)中鏈表類Linkecl I。ist得定義（教材中得例程 9 6 h）,給出其實(shí)現(xiàn)，注意合理使用Nod Ie類（教材中得例程9 3. h）得成員函數(shù)。在測(cè)試程序中定義整型鏈表 A與E，分別插入5個(gè)元素,使用循環(huán)語(yǔ)句顯示鏈表中得元素，然后把 B中得 元素加入 A 得尾部 ，再顯示出來(lái)。2。 隊(duì)列類得特點(diǎn)就就是其元素得操作順序?yàn)橄热胂瘸觯‵IFO ），用上題中得鏈表類實(shí)現(xiàn)隊(duì)列類 ，用鏈表類得成員函數(shù)實(shí)現(xiàn)隊(duì)列得成員函數(shù)，在測(cè)試程序中定義一個(gè)整型隊(duì)列對(duì)象，觀察隊(duì)列類中得

3、元素先入先出得特點(diǎn)。3. 在程序中包含語(yǔ)句#i nc lu de ,使用deq u e類得方法 push_ b ack（）、em p t y （）、po p _front（）完成上一小題得要求。程序名：lab 9 _3、cp p.、四、實(shí)驗(yàn)程序1、#inc lu de l i nk、h int mai n ()?L in ked Li st int A, B ;?f o r( in t i = 0； i 5 ；i+ )?A、Inser t Re a r ( 2 *i +1);? B、In se ft Re a r(2* i + 2 );?A、 Reset()；cout ”鏈表A得元素為：”；w

4、 hile(! A、EndOfL i st ()?dou t A、Data ()v ”;?A、N ex t();co ut en dl;B、Re s e t();?DO ut VV 鏈表B得元素為：；?whi le(! B、En dOfList ()?cout VV B、Data() V”;?B、Next();?cou t e nd l ;endl;cout Ins ertR e ar (BD ata();?3、Next();?、R ese t ();?do ut ”此時(shí)，鏈表A得元素為：”whil e(！ A、E n d Of Lis t ()?Cout v A、Data () ;A、Nex

5、t()；cout endl;#ifndef LINKE DLIST_CLASS#de f i n e L IN KEDL I ST CLASSinclude#i nc lud e using name space std;ifndef NULLconst int NULL =0；endif/ NULL #i nc l ud e 9 3、htemplate classLinkedListprivat e:No d e *f r o nt, *r ear；Nod e 衣 p r evP t r,*c ur rPtr;int size；i nt po s ition ;N o de *G e t N

6、 o d e (co n st T& i t em,Node *ptrNext=NU L L);v o i d FreeNo d e(Node 衣 p);void Copy L ist(co n st Li n kedList T & L );p u blic:Li n kedList ( void) ;Li n ke dL ist(cons t LinkedList&L);L i n k edList(v o id);Link e d List & op era tor= (co n st Li n kedLi s tT & L);i n t ListSi z e(void)con st;i

7、n t ListEmpt y( voi d ) con st;v oid R ese t (i n t p o s = 0);void N ex t (v oid);int EndOfList(vo i d)const ;int Cu rr en tPosit io n(vo id) cons t;void InsertFront (con s t T& i te m);voi d In sertR ear (co nst T& item);void I n sertAt (const T& it em);vo i d In sertAf te r (con st T& it em );T D

8、eleteFront( void);vo i d DeleteAt (vo i d);T& D a ta (void);vo id C l e ar L ist (void);；te mp l a te vcl assTNode v T *Lin k edLi s tvT：:G e tNode (co n st T & item ,N odeT * p t rN ex t )N o de T p；p = new No de (item,p t rN ex t);if ( p = = NULL )cout ”M e mor y a l l o ca t ion f a il ur e!n ;ex

9、 i t( 1 )；ret urn p；templat e v class Tv o i d Li nke dLi s t T : : F r ee No d e (N ode *p)del ete p;tem p la te vo id Li n kedLis t vT : :CopyList(const LinkedList L)int pos;w h ile (p != NULL )Ins er tRe a r(p d at a);p = p NextNode( ) ;if ( po sit i on = = 1)return;prevPtr = N U L L;cu r rPtr =

10、f ront;f o r ( pos = 0; p o s ! = p o sitio n ; p os+ + )pre vPtr = currPtr ;c urrP t r = cu rrPtr N e xtN o de();temp 1 a t e v class TLink ed List : L i nkedList ( vo i d): f ro n t ( N UL L) , rear (NULL ), prevPtr ( N U L L ), cur rPt r ( N UL L), si z e (0) , p os i tio n(-1 )t emp1 ate c lass

11、TL i n ke d L ist v T : :L in k e dL is t (c on st L in kedLi s t v T & L )front = rear = NULL ;pr evP tr = currPtrNULL;siz e0；posi t io n-1；CopyLi s t(L)mp 1 atec l a ss Tvoid L inkedList : C 1e arList( vo i d )Nod eV T *currPos i tion, *n extPos i ti o n;cur rPo sitio n = front;w h il e (c u r r P

12、 o s it i on ! = NUL L)n ex tPosi t ion = cu r rPo s itio n- N ex tNo d e();FreeNode(currPos ition)；c u rrP o s i t i o n = ne x tPositi on ;f ron t = r e a r = N U L L;prevPtr = cur rP tr = NULL;size = 0;pos it ion = -1;template Li n kedL ist V T :L inke dLis t( vo i d)ClearL ist();templa t e Lin k

13、 edL i s t T& Linke d L i st :o p erat or = (c o n st Li nke dL istvT& L)if (thi s = &L)return this;Cl e ar List();Co p yLi s t ( L);ret u r n 衣 t h is;templa t e i n t L i n kedL i st : : L istSize (v oid) co nstr etu rn size;t e mplate v cl as s Tin t L i nk e dL i stv T ： : Li s t E mpty(v o id)

14、c on stre tur n si z e = 0;tem p l ate voi d Li nk edL is t: ：Next( void)if (curr Ptr ！= NULL)prevPtr = c urrPtr;c urrPtr = currPt r -NextNo d e ();p o si t i on TF ;tem p late i nt L in k e d List v T: EndO f List (void ) co nstre t urn c u r rPtr = N ULL;t em p l a te int L i n ke d L ist: : Curre

15、 ntP o siti o n (vo i d) co nstreturn posi ti on;tem pl at e c las s Tvoid Link e d L istv T ： :R e set(i n t p o s)int start Po s;if ( f ro n t = = NULL )ret urn；i f ( pos v 0| | pos size 1)ce r r v Re se t: Inva 1 id list po s i t i on：IIvv pos Nex tN o d e ();prevPtr = f r on t;st a r tP o s= 1 ;

16、f o r(po si tio n = s t artPo s; positio n ! = pos; positio n + +)?pr evP tr = cu rrPtr;currP tr = c u rrPtr N ex tN od e ();t e m pla te T& LinkedListT: :Da t a(vo id)if (size = =0| c ur r Pt r = = NU LL )cerr v Data:i nv alid r e f e ren ce! ” dat a ;template clas s Tv o id Li nk e d List : Inse r

17、 tF ro nt (con st T & i te m)i f (f r ont != NUL L)Reset();InsertAt(item);t e mplate void LinkedListT:InsertRear(const Titem)NodeT *newNo de;p r evP tr = rear;newN od e = GetNode (i t em);if (r ear = NU L L)front = re a r = newNod e;elserear InsertAfter (newNode);rear = newNode；cur r Ptr = r ear；pos

18、iti on = size;Size +;t emp l at e voi d L inked L ist ： :In s e rt At (c o n s t T& it em)Nodev T 衣 new Node;i f (p revPtr = = N U LL)n ewNode = G etNo de(i tem ,f r ont);fro nt = ne wNode;elsenewNo de = GetNode(item);p rev P tr I n se rt Afte r (n ewNo d e);if ( pr e vP tr = r e a r )rea r = newN o

19、 de;position = size ;cur rP tr = n ew Nod e;siz e+;t emp 1 at e v o i d L i n k e dList : Inse r t A f t er (const T& i te m)NodeT * p;p = G e tN od e (it e m);if (fr on t = NUL L)f ro n t = cu rrPt r = r ea r = p ;posi tio n =0;elseif (c u r r Ptr = = N U LL)cu r r Ptr = prevPt r ;curr Pt r I n ser

20、tAft er (p);if (c urrPtr = = r ear )rear = p;po siti on = size;elseposition +;p revPtr = cu rrPtr ;c ur rPtrp;endl;endl；size+；tem plate T L in k edL i stv T : :DeleteFr o nt(voi d )T i t em;Res e t();if (front = N U LL)c e r r vv ” Invai d de 1 etio n! data;Delete A t ();return item；template class T

21、void L in k edList : : Del eteAt (v oid)NodevT *p；i f (cu r rPtr = = N U L L)cerrv Invalid deletion！ ” N e xt N ode()el sep = prevPtr- D el eteAfter ()if (p = = rear)rear = p re vPtr;p osit i on -；cur r Ptr = p- NextN o de ();Fr eeNode( p)；s ize;endi f2、#if n d ef Q UE U E_C L ASS# d e fine Q U EUE_

22、CL AS S#i nclud e using n am espac e std;# i n el u de l in k、h t e m pl ate v cla s s Tcl a ss Qu euepri v ate:Li n kedLi s t q u eueList;p ublic:Queue( void ) ;vo i d Qin ser t( con st T& e It);T Q De lete(v oid)；T Q F r o n t (vo i d);i n t QL en gth (v o id) co n st;in t QEm pty (v o id) con st;

23、voi d QCl ear (voi d);；t empl ate Queu eT :： Queu e( vo id )tem plate cl ass Tint Q ueuev T： QLe ngth( void) cons tret urn queueL i st、L i s t Size ();templa te c las s Tint Queue v T : : Q Empt y( vo i d) co nstreturn queueL i st、L is t Empty();temp 1 ate void Q u e ue : QCIea r (void )qu eu eList、

24、ClearLi s t();t emplat e v class Tvo i d Qu e uev T : QI ns ert(co ns t T& e 1 t)queu eList、I nser tRear(e lt) ;tem p late T Queue : Q De le te (v oid)i f (q ue u e List、L ist Emp ty()end l;cer r C all i ng QDelete fo ran em pty que ue!exit( 1);retur n queu eL i st、 De leteFron t() ;te mp lat e c1as

25、 s TT Q ueue:QFro nt( v o i d )i f(queueList、L is tEmpt y() e nd l;cerr Ca l 1 in g QFro n t for a n emp t y q u eu e!exit(1 ) ;queu eLi st、Re s et();r eturn que u eL is t、D at a();#en di f# if nd ef L I NKED L 1STCLAS S# define L I N K EDLIST CLASS# include # i nc 1 ude vc std lib using n am espa c

26、e std;#ifndef N U LLcon st i nt NULL = 0;#end i f#includ e 9 3、h ”te mplat e c1as s LinkedListp rivate :N o de *fr o nt， r ear;No d e T *pr e vP tr, *cur r Pt r;int si ze;int p o sition;N o d e *GetNode (c onst T& it e m, N o de 衣 ptrNext= N ULL )voi d F r ee No de (Node T衣 p);voi d CopyL ist (con s

27、 t L ink e d L ist v T & L);public：L i nkedL is t( v oi d);L inked L ist (co ns t Lin ke dLi s t & L);LinkedL i s t( void );LinkedList v T & o perato r= (const Li n k e d Lis t & L);int L is t Size( vo id) con st;int List E m p t y (void ) co n st;v oid Reset(int pos = 0) ;void Ne xt(v oid)；i nt End

28、 OfLis t( void ) const;i n t C u rrent P o si t i on (vo i d) con st;v oid In se rtFron t(const T& i tem);void In sertRear (cons t T&item);void In sertAt(co ns t T& item );vo id In sertAfte r (const T & i t em);T D ele t eFr on t ( void);voi d Del e teAt(voi d) ;T& Dat a (vo i d);vo id Cle a rL is t

29、 (v o i d);；templ a te ptrNN o d e *L i nk ed L i stvT： ： G etN ode (c ons t T& ite m, No de * e xt)No de T p;p = n ew Node( it e m, pt rN ex t);i f (p = N ULL )co ut M e mo r y a lloca ti on failure ! n”；exi t (1 );ret urn p;tem plat e class Tv oid Li n k edL i st : Fr e eN o de ( No d e *p)dele t

30、e p;templa te :Co p y L i s t(const Lin k edList T& L )N od edata)p = p Nex t No d e ()i f (p o sition = = -1)return;prevP tr = NU LL ;currPtr = fro nt ;for (p o s = 0; pos != position ;pos+ + )prevP t r = cur r Pt r ;currPt r = cu r rPtrNe x tN od e ();t em pl ate class TLi nked List v T: L i n k e

31、dList (void): fr o nt(NULL ),rea r(N ULL ),prevPt r (NU L L ), c urrP t r (NUL L) , s i z e (0),po si t i o n( 1)tem p late Lin kedListvT :L inke dList(const LinkedLi s t L)f ron t = r e a r = NULL;pr ev Pt r = cu r rPtr = N ULL;size = 0 ;pos ition = 1;C o py List(L ) temp 1 ate voi d Li n k e d L i

32、st v T : Cl e a r List (voi d )No d e 衣 cur rP os i t io n, *n extPo s itio n ;cu r rP ositi on = front ;whi le(c urrP ositi on ！= NUL L )n ext P ositi o n = c u rrP osi t i o n- Nex tNode (); Fre eNod e(currPositi o n ) ；c urr Posi tio n = nextPosit i on;fro n t = r ear = NULL ;prevPt r = currPt r

33、= N ULL ;si ze = 0;p osition= 1;te mpl a te v class TLin ked L is tv T: : L in ke dList(void)ClearLi st();temp1a te LinkedLi s tvT Link ed List: op er at or=co nst Li nke dListvT L)if (this = &L )r e t u r n *this ;Cl ea rLi s t();C opyList ( L);r e t ur n * t h i s;t e mpl a te i nt Lin k e d List

34、: Li s tSiz e (v oid) constreturn size；t e mpla t e cl ass T consti nt Lin k ed Li st : Li s tEmp ty (vo i d)r etu r n si z e = = 0;t emp 1 ate void L i nked L is tT ： :Next( void)i f (currPtr ！= NUL L )p r ev Ptr = currP tr;currPt r = c urr Pt r- NextN o de ();po sit ion +；t e m p la te cl ass Tin

35、t Lin kedLis tv T : : En d OfL i st (vo i d)co n s tr eturn currPtr = NU L L;tem pl a te c l ass Tint L inkedList : Curr entPo s itio n (v o id) constr et urn pos ition ；temp late void LinkedLis t : : Reset (int pos)in t startPos；if (f r o nt = N ULL )return；if (pos v 0 | p o s size 1)endl ;cerr ” R

36、es:et Inval id l i st position:v” Nex t N o de ();prevPt r = fro n t;startPos = 1;f o r ( po s it io n=startPos; p ositi on ! = po s; p o siti on+ +)?prevPtr = currPtr;?cu rrP t r = cu r rPt r N e xtNode ();t emp 1 a t e cla s s TT & L in kedList : Da ta(v oid)if (si z e = 0| currPt r = N ULL)cerr D

37、 ata:in valid refe r ence! data;temp 1 ate void LinkedL i st: : In s ertF r ont (c o ns t T& i t em)i f (fro n t != NULL )Res et( )；InsertAt(item ) ;temp 1a te void L i n k e d List VT :I nsert R e a r(const T& i te m)NodeInsertAfter (n ewN ode )；rea r = newN ode ;curr Ptr = rea r；p osi ti on = s i

38、ze;s ize +;temp1 ate c1a ss Tv oi d Li n kedList I ns e r t A t( c on st T& item)Nod eVT *ne wN o d e;i f (p revPtr = = NU LL )newN od e = G etN ode (i t em, fron t );f ron t = newNode;e 1 senew N o de = Ge t N ode(item);pr evPt r Ins ertAf ter( newNode)；i f (p re vPt r = rear )r ear = newNode；posit

39、i on = size;currPtr = ne wNo d e；s ize +;temp 1 a t e tem)v o id Li nk edL i s t ： :I n se r t Afte r( cons t T&Node p;p = Get No de (i t em);i f (fron t = NU LL)front = c u rrP t r = rear = p;po si t i on =0;elseif (currPt r = NULL )c urrPt r = prevPtr;cur rP tr In sertA ft e r ( p);i f (c u rr P t

40、r = = r e ar)re ar = p；p o s i t ion = size;elsep os i ti on + ;prevP tr = c urrPtr；currPtr = p；size +;temp la te Vc l as s T T Link edL ist T:D e leteFron t(v oid)T item;R e set();if (front = N UL L)ce rr d ata；D e l e te At();re t urn it em;temp l ate v c las s Tvoid Li n kedL i s tvT : De le teA

41、t( vo i d)Nod e *p;if ( cu rr Pt r = NULL)c err Ne xtNo de();e l s ep = prev Ptr D e leteAfter();if (p = rea r)rear = p r ev Ptr;p o si ti on ;cu rrPt r = p NextN o de();FreeN o d e (p );si z e;#end if / LI NKE D L IST_CLASSinclude q ueue、h”int main()Q ueu ev int A ;?for(int i=0;i5；i+)? A、Q Insert(2

42、*i+1 );?cout 隊(duì)列 A 得元素為 : ”；?w h i l e (!A、QEmp t y()?cou t A、QFro nt()vIIA、QD e let e()?3ou t V endl ;4、5、# in elude i o stream# in c l u de a rrayl、h u s in g namespace std;int main()Ar r ay A (1 0);?i nt i, k;?nt S or tT y pe;int SearchNum；cout 請(qǐng)輸入 10 個(gè)整數(shù) V endl；f or (i =0;i10 ;i+ )? cout 輸入第 i+1

43、Ai；?c o u t vv輸入得數(shù)組為：” e n dl;?for(i =0；i10;i+)?cout v Ai v ”;cout endl；cout v Sort Type;sw i tch(Sort T y p e)?c ase 1:? A、Ins e rtionSo r t ();?br e ak ;?sa s e 2:?筮、Se 1 ec t i onSo r t();break;case 3：?A、Bub bl eSo rt();br eak ;default :?cout 輸入錯(cuò)誤，程序退出??；? exit (0)；?cout 排序后得數(shù)組為： en dl；for (i = 0;

44、 i 1 0 ;i+ +)?cout A : i:”；c out endl ；co u t S earc hNum;永=A、SeqSear ch( S earchNum);? f (k 0)個(gè)數(shù)字 v en dl;i ndex Out O fRa n gen er rorcou t 沒(méi)有找到數(shù)字 ” v Searc hN um e n dl;el s e? co ut Search Num 就是第v #i nclu de cstdlib u sing nam espace std;# if ndef N U L Lcon st int NULL = 0 ；end ife n um Err o

45、rT yp ein va lidA rrayS ize,memory Allocati on Err o r,c har * e rro rM sg =I n v al i d ar r ay size, M em or y al 1 oc at i o” Inva lid in de x ：”；t e mplate class A rrayp ri v ate:T* ali s t;int si z e;vo id Er r or( E r r orTy p e err or ,int bad In de x =0)const;public:Array ( int sz =50) ;Arr a y (c ons t Ar r ayv T & A);Array(void) ;A r r ayv T & o per a tor= ( c o n st Ar r ay T & rhs);T & o perator (i nt i);o perator T* (void) const;int