数据结构课件.ppt

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

1、Chapter3LinkedListsDataStructure1SoftwareCollegeNortheastUniversityDataStructureSoftwareCollegeNortheastUniversityOverviewLinkedListsProgrammingdetailsCommonErrorDoublyLinkedListsCircularlyLinkedListsExamplesCursorsImplementationofLinkedLists2DataStructureSoftwareCollegeNortheastUniver

2、sityVariable-lengtharrays?Directaccesstoelement(Byindexing)Arraysizeisfixed-length-Toexpandthem,youcreateanew,longerarray,andcopythecontentsoftheoldarrayintothenewarrayThisisusedbyfunctionrealloc()inCThisisslow!LineartimeInsertion/RemovalduetoshiftelementsDuetocontiguousstorageinmemory

3、Halfofthelistneedstobemovedforeitheroperations3DataStructureSoftwareCollegeNortheastUniversityVariable-lengtharrays?Solution:-Thelistisnotneedtostorecontiguously.-Attachapointertoeachiteminthearray,whichpointstothenextitem.-providestheabilitytoaddorremovetheitemsanywhereinthelistincons

4、tanttimeThisisalinkedlistLinkedlistsareunbounded(maximumnumberofitemslimitedonlybymemory)4DataStructureSoftwareCollegeNortheastUniversityTheLinkedListdatastructure[0][1][2]arrayABCArrayHeadABCLinkedlistAndataitemplusitspointeriscalledanodeAnodecontainsdataitemandoneormorelinks.-thelink

5、isareferencetoanode.-thelinkoflastnodeissettoNULLa“head”whichisapointertothefirstnodeinthelinkedlistnode5SimpleArrayImplementationofListsObviouslyalloftheseinstructionscanbeimplementedjustbyusinganarray.Evenifthearrayisdynamicallyallocated,anestimateofthemaximumsizeofthelistisrequired.

6、Usuallythisrequiresahighover-estimate,whichwastesconsiderablespace.Thiscouldbeaseriouslimitation,especiallyiftherearemanylistsofunknownsize.DataStructureSoftwareCollegeNortheastUniversity6SimpleArrayImplementationofListsAnarrayimplementationallowsprint_listandfindtobecarriedoutinlinear

7、time,whichisasgoodascanbeexpected,andthefind_kthoperationtakesconstanttime.However,insertionanddeletionareexpensive.DataStructureSoftwareCollegeNortheastUniversity7SimpleArrayImplementationofListsForexample,insertingatposition0(whichamountstomakinganewfirstelement)requiresfirstpushin