欢迎来到天天文库
浏览记录
ID:49816977
大小:916.00 KB
页数:109页
时间:2020-03-03
《数据结构-链表.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、Chapter3LinkedListsDataStructureSoftwareCollegeNortheasternUniversityOverviewLinkedListsProgrammingdetailsCommonErrorDoublyLinkedListsCircularlyLinkedListsexamplesCursorsImplementationofLinkedListsDataStructureSoftwareCollegeNortheasternUniversityVariable-lengtharrays?Directa
2、ccesstoelement(Byindexing)Arraysizeisfixed-length-Toexpandthem,youcreateanew,longerarray,andcopythecontentsoftheoldarrayintothenewarrayThisisusedbyfunctionrealloc()inCThisisslow!LineartimeInsertion/RemovalduetoshiftelementsduetocontiguousstorageinmemoryHalfofthelistneedstobem
3、ovedforeitheroperationsDataStructureSoftwareCollegeNortheasternUniversityVariable-lengtharrays?Solution:-Thelistisnotneedtostorecontiguously.-Attachapointertoeachiteminthearray,whichpointstothenextitem.-providestheabilitytoaddorremovetheitemsanywhereinthelistinconstanttimeThi
4、sisalinkedlistLinkedlistsareunbounded(maximumnumberofitemslimitedonlybymemory)DataStructureSoftwareCollegeNortheasternUniversityTheLinkedListdatastructure[0][1][2]arrayABCArrayHeadABCLinkedlistAndataitemplusitspointeriscalledanodeAnodecontainsdataitemandoneormorelinks.-Thelin
5、kisareferencetoanode.-ThelinkoflastnodeissettoNULLa“head”whichisapointertothefirstnodeinthelinkedlistnodeDataStructureSoftwareCollegeNortheasternUniversityZHAOQIANSUNLIZHOUWUZHENGWANG^H43131NULL3771925DataItemLinksLIQIANSUNWANGWUZHAOZHENGZHOUAddress1713192531374331HHeaderAsim
6、plesingleLinkedListDataStructureSoftwareCollegeNortheasternUniversityMemoryStorageoflinkedlistWecanaccessallnodesthroughpointer“head”HeapDataStructureSoftwareCollegeNortheasternUniversityLinkedlistsEachnodecontainstheaddressofthenextoneinthelist.Wecanaccessthefirstnodethrough
7、pointer“head”twoimportantpointer:-head:thereferencetothefirstnode-tail:thereferencetothelastnodeDataStructureSoftwareCollegeNortheasternUniversityHowtoimplementate?DataStructureSoftwareCollegeNortheasternUniversityDefinitionoftheclassUsingmulticlassClassofNode(ListNode)Classo
8、fListClassofIteratorTypeofDefinitioncompoundinsideDataStructureSoftw
此文档下载收益归作者所有