data structures ch 3

《data structures ch 3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DataStructuresandAlgorithmAnalysisinCCS222Chapter3:AbstractDataTypesDataStructuresandAlgorithmAnalysisinCAbstractDataTypesHowdotheydifferfromnormaldatatypesWhatisalistSinglyLinkedListsDoublyLinkedListsCircularlyLinkedListsStacksQueuesObjectiveReviewUsualDataTypesInteger,Do

2、uble,Boolean,CharYoudonotknowtheimplementationofthese.Therearesomeoperationswhichcanbedonewiththese(add,multiply,read,write,=,==)Programmersjustusetheseoperationswithoutknowingtheirimplementation.AbstractDataTypesImplementthesedatatypesonceintheprogramDescribetheseoperatio

3、nsonceUsetheseoperationsagainandagainwithoutgoingintotheimplementationHowever,thecomplexityoftheseoperationsdependsontheimplementationandshouldnotbeconsideredconstantAnADTmayuseadifferentADTListSequenceofelementsOperationsAddanelementatthebeginning/end/ithpositionDeleteane

4、lementatthebeginning/end/ithpositionAccess(read/change)anelementatthebeginning/end/ithposition.ArrayImplementationListscanbeimplementedasanarrayNeedtoknowthemaximumnumberofelementsinthelistatthestartoftheprogramAdding/DeletinganelementcantakeO(n)operationsifthelisthasnelem

5、ents.Accessing/changinganelementanywheretakesO(1)operationsindependentofnAddinganelementAddingatthebeginning:MoveallelementsonepositionbehindAddatposition1;Incrementthecurrentsizeby1For(j=A[0]+1;j>0;j--)A[j]=A[j-1];A[1]=newelement;A[0]A[0]+1;Normallyfirstposition(A[0])sto

6、resthecurrentsizeofthelistActualnumberofelementscurrsize+1Complexity:O(n)AddingattheEndAddtheelementattheendIncrementcurrentsizeby1;A[A[0]+1]=newelement;A[0]A[0]+1;Complexity:O(1)AddingatkthpositionMoveallelementsonepositionbehind,kthpositiononwards;Addtheelementatthekthp

7、ositionIncrementcurrentsizeby1;For(j=A[0]+1;j>k;j--)A[j]=A[j-1];A[k]=newelement;A[0]A[0]+1;Complexity:O(n-k)DeletinganElementDeletingatthebeginning:Moveallelementsonepositionahead;Decrementthecurrentsizeby1For(j=1;j

8、attheEndDeletetheelementattheendDecrementcurrentsizeby1;A[0]A[0]-1;Complexity:O(1)Deleti