线性表英文课件.ppt

《线性表英文课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ChapterTwoList2.1ListAfinitesetofn（0）elementswiththesamecharacteristics(a0,a1,a2,a3,……..,an-1)0<=i

2、thelast”element;EveryElementexceptthefirstonehasonlyonepredecessor;EveryElementexceptthelastonehasonlyonesuccessorPreliminariesEmpty–Listcontainsnoelements;Length–Thenumberofelementsstored;Head–Thebeginningofthelist;Tail–Theendofthelist;Sortedlist–Theelementspositioned

3、inascendingorderofvalue;Unsortedlist–havenoparticularrelationshipbetweenelementvaluesandpositions.OperationsontheorderedListFindthelengthofthelist,n;Readthelistfromlefttoright;Retrievethei-thelement,0<=i<=n-1;Storeanewvalueintothei-thposition,0<=i<=n-1;Insertanewelemen

4、tatpositioni,0<=i<=n-1causingelementsnumberedi,i+….ntobecomenumberedi+1,i+2,….,n+1;Deletetheelementatpositioni,0<=i<=n-1causingelementsnumberedi+1,….,ntobecomenumberedi,i+1,….,n-1;classLinearList{//对象:L=(a0,a1,…,an-1)或(),ai浮点数,0≤i

5、Length();//返回该实例的长度voidLeftToRight();//从左到右遍历全部元素floatRetrieve(inti);//返回第i个元素的值voidStore(inti,floatv);//将v的值赋予第i个元素voidInsert(inti,floatv);//将v作为第i个元素插入floatDelete(inti);//删除第i个元素并返回其值};TheADTdefinitionoforderedlist2.2Array-BasedListThemostcommonwaytorepresentanordere

6、dlistisbyanarrayaconsecutivesetmemorylocationsasetofpairs:(Index,value)asequentialmapping(thearrayindexi,thelistelementai)01ii+1n-1a0a1aiai+1an-1LOC(ai+1)=LOC(ai)+LengthLOC(ai+1)=LOC(a1)+Length*iRandomAccessRetrieveandmodifythevaluesofrandomelementsinthelistinaconstant

7、amountoftimeRepresentationofarray-basedlist#definemaxSizeTypedefintT;Typedefstruct{Tdata[maxSize];intn;}SeqList;//静态表示TypedefintT;Typedefstruct{T*data;intmaxSize,n;}SeqList;//动态表示ImplementationofsomeoperationsoflisttemplateLinearList::LinearList(intsz){//构造函

8、数if(sz>0){MaxSize=sz;last=-1;data=newT[MaxSize];if(data==NULL){cerr<<“AllocationError”<