Lecture15

PointersIICProgrammingLanguageOutlinePointersandStructuresDynamicMemoryAllocationLinkedListPointersandStructuresPointerscanpointtovariableswithstructuretypestructstu_types; structstu_type*p=&s;Pleasenotethenameofstructurevariabledosenotcontainitsaddress.PointersandStructuresUsepointerstoreferencethememberofstructurevariables.(*p).nameisthesameasTheoperator->isusedtosimplifytheexpression.p->name

Pleasenote->operatorisonlyusedtoreferencethememberofstructurevariablePointersandStructuresUsestructurepointer,butnotstructurevariableitself,astheargumentoffunctionswillbemoreefficient.Anotheradded-valueisyoucanmodifythevalueofstructurevariablewithinthefunctionastheargumentispointertype.Example1DynamicMemoryAllocationSometimesweneedtoallocatememorydynamicallyduringtheexecutionoftheprogram.Functionmallocisusedhere.

void*malloc(unsignedintsize); (needheaderstdlib.h)mallocreturnstheaddressifallocationissuccessful.ItwillreturnNULLiffailed.DynamicMemoryAllocationPleasenotethereturntypeofmallocfunctionisvoid*,youneedtocastittoanyotherpointertypeasneeded. int*p; p=(int*)malloc(4); //p=(int*)malloc(sizeof(int)); *p=2; free(p);FreeAllocatedMemoryYoumustfreeallthememoryyousetasidedynamicallybeforetheprogramend.Functionfreeisusedhere.

voidfree(void*p);Youcannot,anddonotneedtofreememorythatallocatedbysystem.Example2DynamicMemoryAllocationvoid*calloc(unsignedintn,unsignedints);Functioncallocreturnsapointertomemoryspaceforanarrayofnobjects,eachwithsizeofs,orNULLiftherequestcannotbesatisfied.Theallocatedspacebyfunctioncallocwillbeinitializedtozerobytes.Example3LinkedListLinkedlistisadatastructurethatcontainsnodesastheformofaline.Whylinkedlists?dynamicmemoryallocationeasytoinsertandremovenodeLinkedListAllthenodesofalinkedlistmustbethesametype,normallyisstructuretype.Thestorageforthenodesmaynotbecontinuous,soit’simportanttoknowtheaddressofeachnode.LinkedListdefinitionofnodestructstu{charid[10];charname[20];intage;

structstu*next;};LinkedListid:A001name:Aliceage:20next:0X10id:A002name:Davidage:21next:0X70id:A003name:Tomage:22next:NULL0X400X100X70LinkedListEachnodeholdapointerpointstonextnode.Soit’snotnecessarytorememberalltheaddressesofnodesatonetime,justtorememberthefirstaddressisenough.IMPORTANT:Donotlostthefirstaddress!CreationofLinkedListDeclarethenode(structuretype).Defineonepointertokeeptheaddressofthefirstnode,normallycalledhead.Allocatememoryforfirstnode,andassignitsaddresstohead.Allocatememoryfornextnode,andassignitsaddresstopreviousnode’snextpointer.……CreationofLinkedListExample4Itmaybeeasiertokeepthetailofthelisttoaddthenewnodetotheend.Example5CreationofLinkedListAnotherwaytocreatelinkedlists:usinganextranodetopointtothefirstnode,andusingpointerheadtopointtothisnode,whichiscalledheadernode.Aheadernodeholdsnodatabutservestosatisfytherequirementthateverynodecontainingdatahaveapreviousnodeinthelinkedlist.Thiswillmakeiteasiertoperformsomeoperationsonthelinkedlist.CreateofLinkedListExample6Sometimesitismoreefficienttocreatethelistbyinsertingthenewnodenexttothehead,andlinkedothernodesafterit.Example7ListsOperationscreatealinkedlistreleasealinkedlisttraversealinkedlistinsertanodetoaspecificpositionofalinkedlistremoveaspecificnodefromalinkedlistsortalinkedlistNoticesTocreatealinkedlist,oroperatealinkedlist,youmustdistinguishifthereisaheadernodeornot.AlwaysremembertosetNULLtothepointernextofthelastnodeinthelinkedlist,asNULLwillbeusedtocheckifanodeisthelastnodeornotduringtraversingalinkedlist.NoticesTotraversealinkedlist,pleasemakesureyouvisitallnodesproperly.Somecommonerrorsincludemissingthefirstoneorlastone;exceedingthelastnode;