【精品数据结构】linear list

《【精品数据结构】linear list》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter3LinearList3.1Preface1.dataobject---asetofinstancesorvaluesforexample:Boolean={false,true}Digit={0,1,2,3,4,5,6,7,8,9}Letter={A,B,……Z,a,b,……z}NaturalNumber={0,1,2,……}Integer={0,+1,-1,+2,-2,+3,-3,…}String={a,b,……,aa,ab,ac,……}3.1Preface２．datastructureisadataobjecttogetherwiththere

2、lationshipsamongtheinstancesandamongtheindividualelementsthatcomposeaninstanceData_Structure={D,R}D---dataobject，R---asetofrelationshipsofallthedatamembersinD.3.2LinearListL=(e1,e2,e3,…,en)listsizeisnifn=0:emptylistifn>0:e1isthefirst’th(orfront)elementenisthelastelementeiimmediatelypr

3、ecedesei+13.2LinearListExample:Students=(Jack,Jill,Abe,Henry,Mary,…,Judy)Exams=(exam1,exam2,exam3)DaysofWeek=(S,M,T,W,Th,F,Sa)Months=(Jan,Feb,Mar,Apr,…,Nov,Dec)3.2LinearListOperations:Createalinearlistdeterminewhetherthelistisemptydeterminethelengthofthelistfindthekthoftheelementsearc

4、hforagivenelementdeletethekthelementinsertanewelementjustafterthekth3.2LinearListADTspecificationofalinearlistAbstractDateTypeLinearList{instancesorderedfinitecollectionsofzeroormoreelementsoperationsCreate();Destroy();IsEmpty();Length();Find(k,x);Search(x);Delete(k,x);Insert(k,x);Out

5、put(out);}3.3Formula-basedRepresentation1.Useanarraytorepresenttheinstanceofanobject(e1,e2,………en)length=neachpositionofthearrayiscalledacelloranodemappingformula:location(i)=i-1e1e2e3enElement012n-1maxsize-13.3Formula-basedRepresentation2.Classdefinition:program3.1templateclas

6、sLinearList{public:LinearList(intMaxListSize=10);~LinearList(){delete[]element;};boolIsEmpty()const{returnlength==0;}intLength()const(returnlength);boolFind(intk,T&x)const;intSearch(constT&x)const;LinearList&Delete(intk,T&x);LinearList&Insert(intk,constT&x);voidOutput(ostream&ou

7、t)const;private:intlength;intMaxSize;T*element;}3.3Formula-basedRepresentation3.Operations:1)Constructor:templateLinearList::LinearList(intMaxListSize){MaxSize=MaxListSize;element=newT[MaxSize];length=0;}3.3Formula-basedRepresentation2)boolFind(intk,T&x)O(1)thek’thelementin

8、theli