Data Structure(C++) Slides-ENG 数据结构课件Chapter-2-Linear-List-English-final

202

DataStructuresChapter2LinearList6LogicalStructureofLinearListSequentialStorageofLinearListLinkedStorageofLinearListComparisonofSequentialListandSinglyLinkedListContentsOtherStorageMethodsforLinearListLogicalStructureofLinearList2.12.1WhatIsaLinearList?DataStructuresChapter2LinearListStudentGradeRecordstudentinformationtables,salarytables,foodrankings......StudentIDNameDataStructuresEnglishAdvancedMathematicsDataStructures0101DingYi789687940102LiEr908778900103ZhangSan866786720104SunHong816996880105WangDong74876680UEFAChampionsLeagueRoundof16ResultsHomeTeamAwayTeamFirstLegDateSecondLegDateRealMadridManchesterCity1-22-273-18AtleticoMadridLiverpool1-02-193-12NapoliBarcelona1-12-263-19ChelseaBayernMunich0-32-263-19DortmundParisSaint-Germain2-12-193-12NBArankings,gamecharacters,songs,movies......InformationTableofaGirl’sSuitorsRankNameCategoryOccupationMajor1ZhangSanDreamGuyStudentHighway2LiSiTopStudentStudentInformationEngineering3ZhaoQiRisingStarStudentVehicleEngineering4MaLiuTechGeekStudentElectricalControl5WangWuWeirdUncleBusinesspersonBusinessgossiprankings,lipsticks,handbags,handsomeguys......ChapterExperimentCustomizealinearlistaccordingtoyourowninterests,implementitinbothsequentialstorageandlinkedstorageforms,debugitonthecomputer,andoutputtheresult.Requirements:Completeindependently.Useclassroomlabtimeasmuchaspossible.Definedataelementsusingastructorclass(usingaclasswithaconstructorismoredifficult).Noidenticalsubmissions.DefinitionofLinearListai(1<=i<=n)iscalledadataelementThesubscriptiindicatestheelement’spositionorserialnumberinthelinearlist.“Afinitesequence

ofdataelementswiththesamecharacteristics”Lengthofalinearlist:thenumberofdataelementsinthelinearlistEmptylist:alinearlistwhoselengthiszero（a1,a2,…,ai,…,an）a1a3a4ana2PropertiesofLinearListFiniteness:thenumberofdataelementsinalinearlistisfinite.Consistency:alldataelementsinalinearlisthavethesametype.Sequentiality:anordered-pairrelationship(ai-1,ai)existsbetweenadjacentdataelementsai-1andai.Thatis,ai-1isthepredecessorofai,andaiisthesuccessorofai-1.Exceptforthefirstandlastelements,everyelementhasoneandonlyonepredecessorandonesuccessor.a1hasnopredecessor,andanhasnosuccessor.a1ai-1aiana2AbstractDataTypeofLinearListADT

List

Datamodel:Dataelementshavethesametype,andadjacentelementshave

predecessorandsuccessorrelations.

Basicoperations:InitList:initializethelistandcreateanemptylistDestroyList:destroythelistandfreethestoragespaceitoccupiesLength:findthelengthofthelistGet:takethedataelementwithserialnumberiinthelist;searchbypositionLocate:findtheelementwithvaluexinthelinearlist;searchbyvalueInsert:insertanewelementxatthei-thpositionofthelistdeletion:deletethei-thelementinthelistEmpty:checkwhetherthelistisemptyendADTAbstractDataTypeofLinearListOperationExplanationInitList(&L)Initialisationofthelist,constructinganemptylinearlistL.DestroyList(&L)Destroythelist,freeingthestoragespaceoccupiedbythelinearlistL.Length(L)Findthelengthoflinearlist,returnthenumberofelementsinthelinearlistL.Get(L,i)TakethedataelementwiththeserialnumberiinthelinearlistL.Locate(L,x)FindthelogicalpositionoftheelementwithavalueofxinthelinearlistL;ifsuchanelementdoesnotexist,return0.Insert(&L,i)FindthelogicalpositionoftheelementwithavalueofxinthelinearlistL;ifsuchanelementdoesnotexist,return0.Delete(&L,i)Deletethei-thdataelementofthelinearlistLandreturnitsvalue,thelengthofLminus1.Empty(L)CheckwhetherthelinearlistLisempty,returntrueifitisempty,otherwisereturnfalse.SequentialStorageofLinearList2.2SequentialListSequentialstoragestructureoflinearlistExample:(34,23,67,43)34236743KeystoragepointsUseacontiguousblockofstorageunitsStorethedataelementsofthelinearlistinsequenceThink:Amongwhatyouhavelearned,whatismostsuitableforsequentialstorageofalinearlist?StorageStructureofSequentialList0

...

i-2

i-1

...

n-1

MaxSize-1a1...ai-1ai...anArraylengthLengthofsequentiallist:lengthMaxSize>=lengthLoc(a1)cLoc(ai)=Loc(a1)+Randomaccess:oncethestartingaddressisdetermined,thetimeneededtocomputetheaddressofanyelementisthesame,sothecomputercanaccessadataelementinO(1)time.Loc(ai)?Timecomplexity:O(1)(i-1)×c（a1,

…,ai-1

,ai,…,an）Storagestructure:therepresentationofdataanditslogicalstructureinacomputerAccessstructure:thetimeperformanceofposition-basedsearchonadatastructureAsequentiallistisarandom-accessstoragestructure.Thismeansthatposition-basedsearchonthisstoragestructurehastimeperformanceO(1).StorageStructureofSequentialListSeqList();//Non-parameterconstructorSeqList(Elementa[],intn);//Parameterizedconstructor~SeqList();//Destructor

intgetLength();//Findthelengthofalinearlist

ElementgetItem(inti);//takingthei-thdataelementintlocate(Elementx);//Findthenumberoftheelement inthelinearlistwithvaluexvoidinsert(inti,Elementx);///Inserttheelementwithvalue xatpositioniinthelinearlistElementremove(inti);//Deletethei-thelementofthelinearlistboolempty();//DetermineifthelinearlistisemptyvoidprintList();//Iteratethroughthelinearlist,outputting theelementsinorderbyserialnumberImplementationofSequentialListtemplate<typenameElement>classSeqList{public:......private:Elementdata[MaxSize];intlength;};ConstructionofSequentialListInitListInput:noneFunction:initializethelistandcreateanemptylistOutput:none0

...

MaxSize-1

0SeqList<Element>::SeqList(){length=0;}Non-parameterconstructorInitListInput:dataelementsforcreatingasequentiallistandthenumberofelementsFunction:createasequentiallistoflengthnOutput:noneParameterizedconstructorSeqList<Element>::SeqList(Elementa[],intn){

}

if(n>MaxSize)throw"Illegalparameter";for(inti=0;i<n;i++)data[i]=a[i];length=n;SequentialListL

arraya351224334253512243342ConstructionofSequentialListInsertioninSequentialListinsert()Input:insertionpositionianddataelementxFunction:insertdataelementxatthei-thpositionofthelinearlistOutput:noneThelogicalrelationshipbetweenai-1andaichanges.Sequentialstoragerequiresstoragelocationstoreflectlogicalrelationships.Storagelocationsmustreflectthischange.Beforeinsertion:(a1,…,ai-1,ai,…,an)Afterinsertion:(a1,…,ai-1,x

,ai,…,an)50Example:(30,10,20,40),insert50atpositioni=2.Fulllist:length>=MaxSizeValidinsertionposition:1<=i<=length+1(iistheelementserialnumber)430102040a1a2a3a401234402010505Whencaninsertionnotbeperformed?InsertioninSequentialList1.Ifthelistisfull,throwanoverflowexception.2.Iftheinsertionpositionisinvalid,throwapositionexception.3.Moveeachelementfromthelastelementtothei-thelementonepositionbackward.4.Putelementxatpositioni.5.Increasethelistlengthby1.PseudocodeInsertioninSequentialList

template<classElement>voidSeqList<Element>::insert(inti,Elementx){

if(length>=MaxSize)throw"overflow";

if(i<1||i>length+1)throw"Positionexception";

for(j=length;j>=i;j--)

data[j+1]=data[j];

data[j]=data[j-1];data[i-1]=x;length++;}Timecomplexity?Problemsize:listlengthnBasicstatement:elementbackward-shiftstatementBestcase:O(1)Worstcase:O(n)Averagecase:O(n)InsertioninSequentialList

DeletioninSequentialListremove()Input:positionioftheelementtobedeletedFunction:deletetheelementxatthei-thpositionofthelinearlistOutput:returnthedeletedelementThelogicalrelationshipbetweenai-1andai+1changes.Sequentialstoragerequiresstoragelocationstoreflectlogicalrelationships.Storagelocationsmustreflectthischange.Beforedeletion:(a1,…,ai-1,ai,ai+1,…,an)Afterdeletion:(a1,…,ai-1,ai+1,…,an)Example:(30,10,20,40),deleteelement10atpositioni=2.Emptylist:length==0Validdeletionposition:1<=i<=length(iistheelementserialnumber)430102040a1a2a3a40123440203Whencandeletionnotbeperformed?DeletioninSequentialListPseudocode1.Ifthelistisempty,throwanunderflowexception.2.Ifthedeletionpositionisinvalid,throwapositionexception.3.Takeoutthedeletedelement.4.Movetheelementswithsubscriptsi,i+1,...,n-1tosubscriptsi-1,i,...,n-2.5.Decreasethelistlengthby1andreturnthedeletedelement.DeletioninSequentialListAveragecase:

O(n)Timecomplexity?Bestcase:O(1)Worstcase:O(n)template<classElement>ElementSeqList<Element>::remove(inti){

if(length==0)throw"underflow";

if(i<1||i>length)throw"Positionerror";x=data[i-1];

for(j=i;j<length;j++)data[j-1]=data[j];length--;

returnx;}Problemsize:listlengthnBasicstatement:elementforward-shiftstatementDeletioninSequentialListOtherOperationsofSequentialListCheckwhetheremptyEmptyInput:noneFunction:determinewhetherthelinearlistisemptyOutput:return1ifempty;otherwisereturn0.boolSeqList<Element>::empty(){if(length==0)returntrue;elsereturnfalse;}0

...

i-2

i-1

...

n-1

MaxSize-1a1...ai-1ai...an

nFindthelistlengthLengthInput:noneFunction:outputthelengthofthesequentiallistOutput:lengthofthesequentiallistintSeqList<Element>::getLength(){returnlength;}OtherOperationsofSequentialList0

...

i-2

i-1

...

n-1

MaxSize-1a1...ai-1ai...an

nSearchbypositiongetItemInput:positionioftheelementtobesearchedFunction:takethei-thdataelementinthesequentiallistOutput:valueofthei-thdataelement0

...

i-2

i-1

...

n-1

MaxSize-1a1...ai-1ai...an

nElementSeqList<Element>::getItem(inti){ if(i<1||i>length)throw"Findlocationillegal"; elsereturn

data[i-1];}Timecomplexity?Anicername?RandomaccessOtherOperationsofSequentialListSearchbyvalueOperationinterface:intLocate(Elementx)Example:findtheelementwithvalue12in(35,33,12,24,42),andreturnitsserialnumberinthelist.535a1a2a3a40123442241233a5i=0i=1i=2Notetherelationshipbetweenserialnumberandsubscript.Thereturnedserialnumberinthelistis3.OtherOperationsofSequentialListSearchbyvalueOperationinterface:intLocate(Elementx)Algorithmdescription:intSeqList<Element>::Locate(Elementx){for(i=0;i<length;i++)if(data[i]==x)returni+1;return0;}Timecomplexity?Best:Worst:Average:Howtoindicatenotfound?OtherOperationsofSequentialListAdvantagesandDisadvantagesofSequentialListAdvantages:Randomaccess:anyelementinthelistcanbeaccessedquickly.Noextrastoragespaceisneededtorepresentlogicalrelationshipsamongdataelements.Disadvantages:Insertionanddeletionrequiremovingmanyelements.Thecapacityofthelistisdifficulttodetermineandexpand.Storagespacemaybewasted.Experiment1ProgrammingandimplementationofsequentiallistCustomizealinearlist,storeitasasequentiallist,andimplementbasicoperationssuchasconstruction,search,insertion,anddeletionCompleteitinthefirstlabsessionMaintasks:Programframework:sequentiallistclassandbasicoperations,mainfunction,dataelementsThebookalreadyprovidesthesequentiallistclassandbasic-operationcode;makeminormodificationssuchasvariabledefinitions.Definedataelements(structorclass),andaccordinglymodifythesearch-by-valuecodeasneeded.Writethemainfunction,provideabasic-operationinterface,andinstantiatedataelements.Extension:GiventwosequentiallistsAandBofthesametypewithsomecommonelements,writeafunctionthatstorestheintersectionofAandBintheoriginallistAandstorestheirunioninB.LinkedStorageofLinearList2.3IntroductiontoLinkedListStaticstorageallocationSequentialListCapacitydeterminedinadvanceLinkedListDynamicstorageallocationAllocatespaceatruntimeContiguousnon-contiguousscatteredLinkedlist:thelinkedstoragestructureofalinearlist.InC++,logicalrelationshipsbetweendataelementsareimplementedwithpointers.Storageidea:useasetofarbitrarystorageunitstostorethelinearlist.StorageofSinglyLinkedListStoragestructureofsinglylinkedlistExample:storagediagramof(a1,a2,a3,a4)0200020803000325............a10200a20325a30300a4∧Storagefeatures:1.Thelogicalorderandphysicalorderarenotnecessarilythesame.2.Logicalrelationshipsamongelementsarerepresentedbypointers.StoragestructureofsinglylinkedlistAsinglylinkedlistconsistsofseveralnodes.Eachnodeconsistsofadatafieldandapointerfield.Node:datafield

pointerfield0200020803000325............a10200a20325a30300a4∧nodedatafieldpointerfieldStorageofSinglyLinkedListstoredataelementsstoreapointertothesubsequentnodeNodeofSinglyLinkedListdatanexttemplate<classElement>structNode{Elementdata;

Node<Element>*next;};Howtoallocateanode?s=newNode<Element>;deletes;Howtoreferencethedataelement?s->data;Howtoreferencethepointerfield?s->next;......sNodedatanext*s.data;*s.next;Howtodeleteanode?StorageofSinglyLinkedListHeadpointer:pointstothestorageaddressofthefirstnodeheada1a2an∧non-emptylisthead=nullptremptylistEmptyandnon-emptylistsarenothandleduniformly.1000200036004800............a11000a24800a33600a4∧headTailmarker:thepointerfieldoftheterminalnodeisemptyHeadpointer:pointstothestorageaddressofthefirstnodeHeadnode:anadditionalnodeofthesametypeisplacedbeforethefirstelementnodeheada1a2an∧head∧non-emptylistemptylistTheheadnodesimplifiesboundaryhandling:insertion,deletion,construction,etc.StorageofSinglyLinkedListTailmarker:thepointerfieldoftheterminalnodeisemptysinglylinkedlist-pointerheada1a2an∧p*p*(p->next)Thisnodeisrepresentedby*p,where*pisthenodevariable.The“nodepointedtobypointerp”isreferredtoas“nodep”.SupposepointerppointstoanodeoftypeNode.p->nextHowtorepresentthenextnodeofnodep?ImplementationofSinglyLinkedListtemplate<typenameElement>classLinkList{

public:......

private:Node<Element>*head;};LinkList();LinkList(Elementa[],intn);~LinkList();int

getLength();int

empty();Element

getItem(inti);int

locate(Elementx);void

insert(int

i,Elementx);Element

remove(inti);void

printList();headtemplate<typenameElement>LinkList<Element>::LinkList(){head=newNode<Element>;//createtheheadnodehead->next=nullptr;//setthepointerfieldoftheheadnodetonull}Initialization:whatshouldthenon-parameterconstructordo?Non-parameterconstructorImplementationofSinglyLinkedList∧Checkwhetheremptytemplate<typenameElement>boolLinkList<Element>::empty(){if(head->next==nullptr)returntrue;

elsereturnfalse;}∧headWhatconditionshouldanemptysinglylinkedlistsatisfy?ImplementationofSinglyLinkedListheada1a2an∧ppCoreoperation:movetheworkingpointerforwardHowtomovetheworkingpointerforward?Canp++dothiscorrectly?a1a2pp++p->nextp=p->nextWhatdoestraversalneedtoaccomplish?TraversaloutputImplementationofSinglyLinkedListheada1a2an∧headWhysetaworkingpointer?Whathappensifwescanthesinglylinkedlistbymovingtheheadpointerforward?Beforemodifyinghead:(a1,a2,…,an)Aftermodifyinghead:(a2,…,an)Theheadpointeridentifiesthestartofasinglylinkedlistandisusuallynotmodified.headpointstotheheadnodeImplementationofSinglyLinkedListheada1a2an∧Input:noneFunction:traversethesinglylinkedlistwithprintListOutput:alldataelementsofthesinglylinkedlist1.Initializeworkingpointerp.2.Repeatthefollowingoperationsuntilpointerpisnull:2.1Outputthedatafieldofnodep.2.2Moveworkingpointerpforward.Describethebasictraversalprocessinpseudocode:pImplementationofSinglyLinkedListtemplate<typenameElement>voidLinkList<Element>::printList(){Node<Element>*p=head->next;//initializeworkingpointerp

while(p!=nullptr){cout<<p->data<<"\t";p=p->next;

//moveworkingpointerpforward;notethatitcannotbewrittenasp++}cout<<endl;}heada1a2an∧pHowtoimplementsearchoperations?ImplementationofSinglyLinkedListInsertioninSinglyLinkedListInsert()

Input:insertionpositionianddataelementxFunction:insertdataelementxatthei-thpositionofthelinearlistOutput:nonepxsHowtoimplementthechangeinthelogicalrelationshipamongnodesai-1,xandai?heada1ai-1an∧aiAlgorithmdescription:Cantheorderoftheredstatementsbereversed?Dotheheadandtailofthelistneedspecialhandling?s=newNode;s->data=x;s->next=p->next;p->next=s;pxsheada1ai-1an∧aiBoundarycases:listheadandlisttail?pxspxs∧s->next=p->next;p->next=s;Unlessotherwisespecified,asinglylinkedlisthasaheadnode.InsertioninSinglyLinkedListpxsheada1ai-1anais->next=head;head=s;xspxss->next=p->next;p->next=s;∧Whathappensifthereisnoheadnode?Inconsistentoperationsaddprocessingstepstothealgorithmandeasilycauseerrors!InsertioninSinglyLinkedListDescribetheinsertionalgorithminpseudocode:1.Initializeworkingpointerptopointtotheheadnode.2.Findthe(i-1)-thnodeandmakeppointtoit.3.Ifthesearchfails,theinsertionpositionisinvalid,sothrowaninsertionpositionexception;otherwise,3.1Generateanewnodeswithelementvaluex.3.2Insertthenewnodesafternodep.pxsheada1ai-1an∧aiInsertioninSinglyLinkedListvoidLinkList<Element>::insert(inti,Elementx){Node<Element>*p=head,*s=nullptr;

intcount=0;

while(p!=nullptr&&count<i-1){p=p->next;count++;}

if(p==nullptr)throw"Insertionpositionerror";

else{s=newNode<Element>;s->data=x;

s->next=p->next;p->next=s;}}O(n)O(1)GivenpointerpTimecomplexity?//Initialization//Findthe(i-1)-thnode//The(i-1)-thnodeisnotfoundInsertioninSinglyLinkedListHowtoimplementthechangeinthelogicalrelationshipamongnodesai-1,ai,andai+1

?DeletioninSinglyLinkedListpheada1ai-1an∧aiai+1qq=p->next;x=q->data;pqpqSpecialcaseatthetail:Althoughthenodetobedeleteddoesnotexist,itspredecessordoesexist!Algorithmdescription:remove()Input:positionioftheelementtobedeletedFunction:deletetheelementxatthei-thpositionofthelinearlistOutput:returnthedeletedelementPayattentiontoboundarycases:listheadandlisttail!p->next=q->next;deleteq;pheada1ai-1an∧aiai+1qpqpqDescribethedeletionalgorithminpseudocode:1.Initializeworkingpointerpandcountercount.2.Findthe(i-1)-thnodeandmakeppointtoit.3.Ifpdoesnotexistorphasnosuccessornode,throwadeletionpositionexception;otherwise,3.1temporarilystorethedeletednodeanditselementvalue.3.2Unlinkthesuccessornodeofnodepfromthelinkedlist.3.3Releasethedeletednode.3.4Returnthedeletedelementvalue.DeletioninSinglyLinkedListElementLinkList<Element>::remove(inti){Elementx;intcount=0;Node<Element>*p=head,*q=nullptr;//workingpointerppointstotheheadnode

while(p!=nullptr&&count<i-1)//findthe(i-1)-thnode{p=p->next;count++;}if(p==nullptr||p->next==nullptr)throw"Deletionpositionerror";

else{q=p->next;x=q->data;//temporarilystorethedeletednodep->next=q->next;//unlink

deleteq;returnx;}}DeletioninSinglyLinkedListCreateaSinglyLinkedListwithnElementsParameterizedconstructorLinkList(Ta[],intn)

Idea:firstcreateanemptylinkedlist,theninsertnodesonebyone.HeadinsertionandtailinsertionHeadinsertion:insertanewnodeatthebeginningofthelinkedlist.Eachtime,insertthenodeaftertheheadnode.Tailinsertion:insertanewnodeattheendofthelinkedlist.Eachtime,insertthenodeaftertheterminalnode.LinkList(Elementa[],intn)Input:arrayaandthenumberofelementsnFunction:readelementsfromarrayainsequenceandinsertthemintothelinkedlistOutput:noneheadinsertion

tailinsertionheada[0]sHeadinsertion:insertaftertheheadnodes=new

Node<Element>;s->data=a[i];s->next=head->next;head->next=s;head∧emptylinkedlistStep1:Initializationhead=new

Node<Element>;head->next=nullptr;Step2:Inserta[0]Cantheredlinebe:s->next=NULL?Cantheorderoftheredandbluelinesbereversed?CreateaSinglyLinkedListwithnElementsHeadinsertion:insertaftertheheadnodes=new

Node<Element>;s->data=a[i];s->next=head->next;head->next=s;Stepi+2:Inserta[i]Cantheredlinebe:s->next=NULL?Cantheorderoftheredandbluelinesbereversed?heada[i]a[i-1]a[0]∧a[1]sCreateaSinglyLinkedListwithnElementsCantheredlinebe:s->next=NULL?s=new

Node<Element>;s->data=a[i];s->next=head->next;head->next=s;CreateaSinglyLinkedListwithnElementsexpectedactual

arrayas=new

Node<Element>;s->data=a[i];s->next=head->next;head->next=s;head->next=s;s->next=head->next;Thesetwoexamplesareinaccurate.Whatshouldthecorrectsinglylinkedlistlooklike?Whatfeatureofheadinsertionhaveyoufound?Headinsertioncanreversetheorder.CreateaSinglyLinkedListwithnElementsarrayaexpectedThat’sanonsequituractual

heada[i]a[i-1]a[0]∧a[1]rearAlgorithmdescription:Tailinsertion:insertthenewnodesatthetailofthecurrentlinkedlists=new

Node<Element>;s->data=a[i];s->next=rear->next;rear->next=s;rear=s;shead∧rearemptylinkedlist∧Howtoquicklyfindthelisttail?tailpointerCreateaSinglyLinkedListwithnElementsheada[i]a[i-1]a[0]∧a[1]rearCantheredandbluestatementsimplementtailinsertion?s=new

Node<Element>;s->data=a[i];s->next=rear->next;rear->next=s;rear=s;s∧rear->next=s;rear=s;rear->next=nullptr;s->next=nullptr;rear->next=s;rear=s;CreateaSinglyLinkedListwithnElements~LinkList()Input:noneFunction:deleteallnodesinthesinglylinkedlistonebyoneandreleasestoragespaceOutput:noneDestroytheSinglyLinkedListfirsta1a2an∧aipqAlgorithmdescription:q=p;p=p->next;deleteq;pNote:makesuretheunprocessedpartofthelinkedlistisnotdisconnected.ComparisonbetweenSequentialListandLinkedList2.4ComparisonbetweenSequentialListandLinkedListWhichofthesetwostoragestructuresforlinearlistsisbetter?Howshouldwechooseinapplications?ComparisonofstorageallocationmethodsAsequentiallistusesasequentialstoragestructure;thatis,itusesablockof(

)storageunitswith(

)addressestostoredataelementsofthelinearlist.Logicalrelationshipsamongdataelementsareimplementedthrough(