計算機(jī)知識點(diǎn)軟件工程導(dǎo)論chapter09

Chapter9AbstractDataTypes

andAlgorithms（抽象數(shù)據(jù)類型和算法）2ChapterGoalsDefineanabstractdatatypeanddiscussitsroleinalgorithmdevelopmentDistinguishbetweenadatatypeandadatastructureDistinguishbetweenanarray-based（基于數(shù)組）implementationandalinked（鏈?zhǔn)剑﹊mplementationDistinguishbetweenanarrayandalist（列表）3ChapterGoalsDistinguishbetweenanunsorted（未排序的）listandasorted（排序的）listDistinguishbetweenaselection（選擇）sortandabubble（冒泡）sortDescribetheQuicksort（快速）algorithmApplytheselectionsort,thebubblesort,andtheQuicksorttoalistofitemsbyhandApplythebinarysearch（二分搜索）algorithm4ChapterGoalsDistinguishbetweenthebehaviorofastack（棧）andaqueue（隊(duì)列）Drawthebinarysearchtree（二叉檢索樹）thatisbuiltfrominsertingaseriesofitemsDemonstrateyourunderstandingofthealgorithmsinthischapterbyhandsimulating（手動模擬）themwithasequenceofitems5AbstractDataTypesAbstractdatatype（抽象數(shù)據(jù)類型）

Adatatypewhoseproperties(dataandoperations)arespecifiedindependently（獨(dú)立的）ofanyparticularimplementationRememberwhatthemostpowerfultoolthereisformanagingcomplexity（復(fù)雜）?6ThreeViewsofDataApplication(user)level（應(yīng)用層/用戶層）ViewofthedatawithinaparticularproblemViewseesdataobjectsintermsofpropertiesandbehaviors7ThreeViewsofDataLogical(abstract)level（邏輯/抽象層）AbstractviewofthedataandthesetofoperationstomanipulatethemViewseesdataobjectsasgroupsofobjectswithsimilarpropertiesandbehaviors8ThreeViewsofDataImplementationlevel（實(shí)現(xiàn)層）AspecificrepresentationofthestructurethatholdthedataitemsandthecodingoftheoperationsinaprogramminglanguageViewseesthepropertiesrepresentedasspecificdatafieldsandbehaviorsrepresentedasmethodsimplementedincode9ThreeViewsofDataDescribeawordprocessorfromthethreeviews10ThreeViewsofDataCompositedatatype（組合數(shù)據(jù)類型）AdatatypeinwhichanameisgiventoacollectionofdatavalueDatastructures（數(shù)據(jù)結(jié)構(gòu)）

TheimplementationofacompositedatafieldsinanabstractdatatypeContainers（容易）

Objectswholeroleistoholdandmanipulate（操作）otherobjects11LogicalImplementationsTwologicalimplementationsofcontainersArray-based（基于數(shù)組）implementationObjectsinthecontainerarekeptinanarrayLinked-based（鏈?zhǔn)剑﹊mplementationObjectsinthecontainerarenotkeptphysically（物理的）together,buteachitemtellsyouwheretogotogetthenextoneinthestructureDidyoueverplaytreasurehunt,agameinwhicheachcluetoldyouwheretogotogetthenextclue（線索）?12LogicalImplementationsThinkofthecontainerasalistofitemsHerearethelogicaloperationsthatcanbeappliedtolistsAdditem PutanitemintothelistRemoveitem RemoveanitemfromthelistGetnextitem Get(look)atthenextitemmoreitems Aretheremoreitems?13UnsortedandSortedContainersUnsortedcontainerTheitemsinthecontainerarenotorderedinanywaySortedcontainerTheitemsinthecontainerareorderedbythevalueofsomefieldwithintheitems14Array-BasedImplementationsFigure9.1AlistThearraygoesfrom[0]to[MAX-LENGTH-1]Theitemsinthecontainer(thelist)gofrom[0]to[length-1]1]15Array-BasedImplementationsFigure9.2

AnunsortedlistofintegersWhatisthearray?Whatisthelist?16Array-BasedImplementationsFigure9.3

AsortedlistofintegersWhatisthearray?Whatisthelist?17Array-BasedImplementationsHowdoweimplementtheoperations?Additem givenanindex,shiftfollowing itemsdownandstoreitematindexRemoveitem givenanindex,shiftfollowing itemsuponeGetnextitem incrementvalueofindexand returnvalueatthatpositionmoreitems valueofindex<length-118LinkedImplementationLinkedimplementation

AnimplementationbasedontheconceptofanodeNode（節(jié)點(diǎn)）

Aholderfortwopiecesofinformationtheitemthattheuserwantsinthelist(item)apointertothenextnodeinthelist(next)19LinkedImplementationFigure9.4AnatomyofalinkedlistFigure9.4Anatomyofalinkedlist20LinkedImplementationFigure9.5Anunsortedlinkedlist21LinkedImplementationFigure9.6Asortedlinkedlist22LinkedImplementationHowdoweimplementtheoperations?Additem givencurrent,insertanewnode withitemintheinfopartbetween

currentandnext(current)Removeitem givencurrent,remove

next(current)Getnextitem setcurrenttonext(current)moreitems

currentdoesnotcontainnull23LinkedImplementationFigure9.7

Storeanodewithinfoof67aftercurrent24LinkedImplementationFigure9.8Removenodenext(current)25Lists（列表）ListoperationsCreateitself(Initialize)InsertanitemDeleteanitemPrintitselfKnowthenumberofitemsitcontainsGenericdatatype(orclass)Adatatypeorclassinwhichtheoperationsarespecifiedbutthetypeorclassoftheobjectsbeingmanipulatedisnot26UnsortedListsCreate(initialize)

Setlengthto0Insert(item)

Findwheretheitembelongs

Puttheitemthere IncrementlengthRemove(item)

Findtheitem

Removetheitem Decrementlength27UnsortedListsPrint

While(moreitems)

Getnextitem PrintItemInsert(item)

Findwheretheitembelongs

Puttheitemthere IncrementlengthKnowLength

returnlength28SortedListsFromtheapplicationview,howdothesortedanunsortedlistdiffer?Thepositionofwhichalgorithmstepsmustbedifferent?29UnfinishedAlgorithmStepsFindwheretheitemsbelongs(unsorted) ItembelongsatthelengthpositionFindwheretheitemsbelongs(sorted) SettempItemtothefirstitem While(pareTo(tempItem)>0) SettempItemtonextitem ItembelongsattempItemFindtheitem SettempItemtofirstitem While(pareTo(tempItem)notequal0 SettempItemtonextitem30SortingSortingArrangingitemsinacollectionsothatthereisanorderingonone(ormore)ofthefieldsintheitemsSortKey（排序鍵）Thefield(orfields)onwhichtheorderingisbasedSortingalgorithmsAlgorithmsthatordertheitemsinthecollectionbasedonthesortkeyWhyissortingimportant?31SelectionSortGivenalistofnames,puttheminalphabetical（字母）orderFindthenamethatcomesfirstinthealphabet,

andwriteitonasecondsheetofpaperCrossoutthenameofftheoriginallistContinuethiscycleuntilallthenamesontheoriginallisthavebeencrossedoutandwrittenontothesecondlist,atwhichpointthesecondlistcontainsthesameitemsbutinsortedorder（需要兩個列表的空間，原始的和新的）32SelectionSortAslightadjustmenttothismanualapproachdoesawaywiththeneedtoduplicatespaceAsyoucrossanameofftheoriginallist,afreespaceopensupInsteadofwritingthevaluefoundonasecondlist,exchange（交換）itwiththevaluecurrentlyinthepositionwherethecrossed-off（交叉）itemshouldgo33SelectionSortFigure9.9Exampleofaselectionsort(sortedelementsareshaded)34BubbleSortBubbleSortusesthesamestrategy: Findthenextitem PutitintoitsproperplaceButusesadifferentscheme（策略）forfindingthenextitemStartingwiththelastlistelement,comparesuccessivepairs（相鄰對）ofelements,swappingwheneverthebottomelementofthepairissmallerthantheoneaboveit35BubbleSortFigure9.10Exampleofabubblesort36AlgorithmsCanyouwritethealgorithmsfortheselectionsortandthebubblesort?Canyouthinkofawaytomakethebubblesortmoreefficient?37QuicksortFigure9.12OrderingalistusingtheQuicksortalgorithmItiseasiertosortasmallernumberofitems:SortA…F,G…L,M…R,andS…ZandA…Zissorted38Quicksort（快速排序）Quicksort If(thereismorethanoneiteminlist[first]..list[last]) SelectsplitVal

Split（分割）thelistsothat list[first]..list[splitPoint-1]<=splitVal list[splitPoint]=splitVal list[splitPoint+1]..list[last]

>splitVal

Quicksortthelefthalf Quicksorttherighthalf39Quicksort40QuicksortSplit Setlefttofirst+1 Setrighttolast Do Increment（增）leftuntillist[left]>splitValORleft>right Decrement（減）rightuntillist[right]<splitValORleft>right If(left<right) Swap（對調(diào)）list[left]andlist[right] While(left<=right) SetsplitPointtoright Swaplist[first]andlast[right]快速排序41選擇分裂值

設(shè)置lefttofirst+1（第一個+1）

設(shè)置righttolast（最后一個） Do

將left遞增直至list[left]>分裂值ORleft>right

將right遞減直至list[right]<分裂值ORleft>right If(left<right)

對調(diào)list[left]andlist[right] While(left<=right)

設(shè)置分裂點(diǎn)為right

對調(diào)list[first]andlast[right]42QuicksortFigure9.13

Splittingalgorithm快速排序43將左半邊再用同樣的方法排序再對右半邊用同樣的方法排序44BinarySearch

（二分搜索法）Sequentialsearch（順序搜索）

Searchbeginsatthebeginningofthelistandcontinuesuntiltheitemisfoundortheentirelist（整個列表）hasbeensearchedBinarysearch(listmustbesorted)（二分搜索）Searchbeginsatthemiddle（中間）andfindstheitemoreliminates（消除）halfoftheunexamineditems;processisrepeatedonthehalfwheretheitemmightbeSaythatagain…45BinarySearchBooleanBinarySearch(first,last) If(first>last) returnfalse Else Setmiddleto(first+last)/2 SetresulttopareTo(list[middle]) If(resultisequalto0) returntrue Else If(result<0) BinarySearch(first,middle-1) Else BinarySearch(middle+1,last)46BinarySearchFigure9.14Traceofthebinarysearch47BinarySearchTable9.1AverageNumberofComparisonsIsabinarysearchalwaysbetter?48Stacks（棧）Stack

AnabstractdatatypeinwhichaccessesaremadeatonlyoneendLIFO（后進(jìn)先出）,whichstandsforLastInFirstOutTheinsertiscalledPushandthedeleteiscalledPopNamethreeeverydaystructuresthatarestacks49Queues（隊(duì)列）Queue

AnabstractdatatypeinwhichitemsareenteredatoneendandremovedfromtheotherendFIFO（先進(jìn)先出）,forFirstInFirstOutNostandardqueueterminologyEnqueue,Enque,Enq,Enter,andInsert

areusedfortheinsertionoperationDequeue,Deque,Deq,Delete,andRemove

areusedforthedeletionoperation.Namethreeeverydaystructuresthatarequeues50StacksandQueuesFigure9.15

Stackandqueuevisualizedaslinkedstructures51TreesStructuresuchaslists,stacks,andqueuesarelinear（線性的）innature;onlyonerelationshipisbeingmodeledMorecomplexrelationships（復(fù)雜關(guān)系）requiremorecomplexstructures（復(fù)雜結(jié)構(gòu)） Canyounamethreemorecomplex relationships?52TreesBinarytree（二叉樹）Alinkedcontainerwithauniquestartingnodecalledtheroot,inwhicheachnodeiscapableofhavingtwochildnodes,andinwhichauniquepath(seriesofnodes)existsfromtheroottoeveryothernodeApictureisworthathousandswords…53TreesRootnodeNodewithtwochildrenNodewithrightchildLeafnodeNodewithleftchildWhatistheuniquepathtothenodecontaining5?9?7?…54BinarySearchTrees

（二叉檢索樹）Binarysearchtree(BST)Abinarytree(shapeproperty)thathasthe(semantic)propertythatavalueinanynodeisgreaterthanthevalueinanynodeinitsleftsubtreeandlessthanthevalueinanynodeinitsrightsubtree55BinarySearchTreeFigure9.18AbinarysearchtreeEachnodeistherootofasubtreemadeupofitsleftandrightchildrenProvethatthistreeisaBST56BinarySearchTree57BinarySearchTreeBooleanIsThere(current,item) If(currentisnull) returnfalse Else SetresulttopareTo(info(current)) If(resultisequalto0) returntrue Else If(result<0) IsThere(item,left(current)) Else IsThere(item,right(current))58BinarySearchTreeTracethenodespassedasyousearchfor18,8,5,4,9,and15Whatisspecialaboutwhereyouarewhenyoufindnull?59BinarySearchTreeInsert(current,item) If(treeisnull) Putitemintree Else If(pareTo(info(current))<0)