软件工程算法课程第3章

《软件工程算法课程第3章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter3List,Stacks,andQueueIntroducetheconceptofAbstractDataTypes(ADTS).showhowtoefficientlyperformoperationsonlists.IntroducethestackADTanditsuseinimplementingrecursion.IntroducethequeueADTanditsuseinoperatingsystemsandalgorithmdesign.3.1AbstractDataTypes(ADTS)ADT-----asetofobjectstogether

2、withasetofoperaions.Abstractdatatypesaremathematicalabstractions;nowhereinanADT’sdefinitionisthereanymentionofhowthesetofoperationsisimplemented.3.1AbstractDataTypes(ADTS)2.dataobject---asetofinstancesorvaluesforexample:Boolean={false,true}Digit={0,1,2,3,4,5,6,7,8,9}Letter={A,B,……Z,a,b,……z}N

3、aturalNumber={0,1,2,……}Integer={0,+1,-1,+2,-2,+3,-3,…}String={a,b,……,aa,ab,ac,……}3.1AbstractDataTypes(ADTS)3．datastructureisadataobjecttogetherwiththerelationshipsamongtheinstancesandamongtheindividualelementsthatcomposeaninstanceData_Structure={D,R}D---dataobject，R---asetofrelationshipsofal

4、lthedatamembersinD.3.2TheListADTL=(e1,e2,e3,…,en)listsizeisnifn=0:emptylistifn(finite)>0:e1isthefirstelementenisthelastelementeiprecedesei+13.2TheListADTExample: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.

5、2TheListADTOperations:Createalinearlistdeterminewhetherthelistisemptydeterminethelengthofthelistfindthekthoftheelementsearchforagivenelementdeletethekthelementinsertanewelementjustafterthekth3.2TheListADTADTspecificationofalinearlistAbstractDateTypeLinearList{instancesorderedfinitecollection

6、sofzeroormoreelementsoperationsCreate();Destroy();IsEmpty();Length();Find(k,x);Search(x);Delete(k,x);Insert(k,x);Output(out);}3.2.1.SimpleArrayImplementationofLists1.Useanarraytorepresenttheinstanceofanobject(e1,e2,………en)e1e2e3enelement012n-1MaxSize-1length=neachpositionofthearrayiscalledace

7、lloranodemappingformula:location(i)=i-1O(1)3.2.1.SimpleArrayImplementationofListsClassdefinition:programtemplateclassLinearList{public:LinearList(intMaxListSize=10);~LinearList(){delete[]element;};boolIsEmpty()const{returnlength==0;}intLeng