Data Structure(C++) Slides-ENG 数据结构 全套课件 第1-8章 Introduction-English- Sorting-English

DataStructuresChapter1IntroductionCourseNatureBasicConceptsofDataStructureAlgorithmDescriptionAlgorithmAnalysisContentsCourseNature1.11.1BuildingConfidenceintheMajorDataStructuresChapter1IntroductionCommonConcernsofComputerScienceStudentsAsunsetindustry,likesomeformerlypopularmajors,nowindeclineWillbereplacedbyartificialintelligenceRelatedcoursesarealsotaughtinothermajors“ITlaborers”Mid-careercrisisToohardandexhausting;consumingyouthFinance,electricalengineering,accounting,marketing,civilservice1.1LearningContentSolvingpracticalengineeringandscientificproblemswithcomputersDatarepresentation(modelingandstorage):storingdataincomputersDataprocessing(algorithmdesign):processingdataandsolvingproblemsProblemSolvingThreebasicdatastructures—thetoolboxLinearlistTreeGraphSolvingcomplexproblemsbyreusing,recombining,andmodifyingbasicdatastructuresBasicDataStructuresDevelopingbasicabilitiesinalgorithmanalysisanddesignDesignalgorithmsEvaluatealgorithmsImprovealgorithmsAlgorithmDataStructuresChapter1Introduction1.1CourseNature0102030405CoreFoundationProgrammingEssentialsLearningDifficultyLinkingPriorandFutureCoursesFutureCareerDatastructureisoneofthecorecoursesinthecomputersciencecurriculum.AfterlearningC++,manystudentsfeeltheycanpassexamsbutcannotprogram;thiscourseaddressesthatproblem.Prerequisitecourses:AdvancedMathematics,C++,DiscreteMathematicsFollow-upcourses:OperatingSystems,Databases,SoftwareEngineering,etc.EmploymentPostgraduateEntranceExamProfessionalCareerFive-stardifficultyDifficultpointsaredeepDifficultpointsaremanyDataStructuresChapter1Introduction1.1AbilityDevelopment—LecturesLearnandapplycomputerscienceknowledgeandmodelingmethodstoreasonaboutandanalyzerealengineeringproblems.ModelingStorageReasoningAnalysisEngineeringKnowledgeRecognizethatengineeringproblemsincomputingmayhavemultiplesolutions,andcomparealternativesthroughliteraturereviewandresearch.MultiplestoragemethodsMultiplesolutionalgorithmsProblemAnalysisUnderstandtheprinciplesandmethodsofmajoralgorithmsandinformationretrievaltoolsincomputerscience,andrecognizetheirlimitations.ClassicalgorithmsandtoolsEvaluationandimprovementModernToolsAnalyzeandevaluatetheimpactofcomputerengineeringpracticesandsolutionsonsociety,health,safety,law,andculture.ImpactofconstraintsonprojectimplementationUnderstandthesocialresponsibilitiesofcomputingpracticeSocialResponsibilityDataStructuresChapter1Introduction1.1

Fromanengineeringscienceperspective,analyzeinfluencingfactorsforsolutionstocomplexcomputingproblemsthroughliteraturereviewandresearch,anddrawvalidconclusions.AnalyzesolutionsDrawvalidconclusionsProblemAnalysisUnderstandtheconceptsandmeaningofenvironmentalprotectionandsustainabledevelopment,andcorrectlyrecognizetherelationshipbetweencomputerscienceandsustainability.ResourceconsumptionofsolutionsAlgorithmefficiencyEnvironmentalSustainability

Understandindividualrolesinateamandbeabletoorganize,coordinate,andleadteamwork.SolutiondesignTaskdecompositionWorkevaluationIndividualsandTeamsWiththeultimategoalofcultivatinghigh-quality,highlyskilledtalentwithbothintegrityandcompetence,layingafoundationfortraininggreatcraftsmen!DataStructuresChapter1IntroductionAbilityDevelopment—Lectures1.1HowtoAchieveGoodResultsAttendclassescarefully,investtimeandattention,andstudythetextbookandslidesseriously.Makegooduseoflabsessionsandpracticeseriously.DebugcodebyyourselfandrelylessonAI.Formcomputerlabgroupsfreely,5–6studentspergroup.Solveproblemsthroughgroupdiscussion.Ifdebuggingfails,sendittomeorcometomyoffice.Takeassignmentsseriously;identicalsubmissionsarestrictlyforbidden.Assignmentsaredividedintotwotypes:individualassignmentssubmittedonceperchapterOneheuristicassignment:groupdiscussionisencouraged,butcompletionshouldbeindependentHands-onprogrammingabilityisfarmoreimportantthanonlyunderstandingthelogic!DataStructuresChapter1Introduction1.1C++DevelopmentEnvironment0102030405VC6.0CodeblockseEclipseVisualstudioNetneansNotrecommended;incompatiblewithnewoperatingsystemsandflawedinstringoperations.Recommended.Alightweightcompilationsystem,butweaksupportforJava.Recommended.ThedrawbackisthatitislargeandhasweaksupportforJava.Javaenvironment;C++requiresCygwin.Javaenvironment;C++requiresMinGW.DataStructuresChapter1Introduction1.1FirstClassParticipationActivitySelf-studytemplates,UMLclassdiagrams,andUMLactivitydiagramsRequirements:Onestudentpresentseachtopic,andotherstudentsprovidesupplements.Thepresentershouldprepareslidesforabout10minutes.Thepresentationshouldhelpclassmatesunderstandthetopic.Purpose,principles,andusageoftemplatesDefinition,purpose,elements,andbasicdrawingmethodofclassdiagramsDefinition,purpose,elements,andbasicdrawingmethodofactivitydiagramsPleasevolunteerorrecommendaclassmateaspresenter.DataStructuresChapter1IntroductionBasicConcepts1.21.1FoundingFigureofDataStructuresBornin1938;receivedaPh.D.inMathematicsfromCaltechatage25;becameaprofessorofComputerScienceatStanfordUniversityatage30.Atage31,thefirstvolumeoftheclassicTheArtofComputerProgrammingwaspublished.Heplannedsevenvolumesintotal.BythepublicationofVolume3in1973,theworkhadastonishedtheworld;hereceivedtheTuringAwardatage36.Helaterdevotedhimselftoreformingtypesettingtechnology,leadingtotheTeXtypesettingsystemandMETAFONTfontdesignsystem,whichtransformedWesternprinting.In2008,Volume4,CombinatorialAlgorithms,waspublished.“Ifyouthinkyouareareallygoodprogrammer,readVolume1.Ifyoucanreadthewholeset,pleasesendmearésumé.”—BillGatesDonaldKnuthDataStructuresChapter1Introduction1.2UsingComputerstoManageaTeamWhatoperationsorprocessingtasksareneededforthistableinteammanagement?Basedonwhatyouhavelearned,howcanonerowbestoredinacomputer?Whatisthefunctionoftheserialnumber?Canyourownhobbiesorinterestsbedescribedusingasimilartable??No.NameTeamAgeStateThree-pointshotDunkBlockShotBackboard…1MichaelJordanBulls32Normal961009086…2DwyaneWadeHeat23Injury90999290…3IronManBeijing28Normal75959698…4MagicJohnsonLakers27Suspension95978886…5ShaquilleO'NealShanghai25Normal78959597……………………………DataStructuresChapter1Introduction1.2TreeStructure…………..……..………...……?1:Howareelementrelationshipsinatreestructuredifferentfromthoseinatablestructure?2:Howcanagamestatebestoredinacomputer?DataStructuresChapter1Introduction1.2Graph

BeijingNewYorkParisLondonTokyoMexicoBeijing

10982124NewYork109

55108Paris82

397London553

89Tokyo10897

113Mexico12489113

1:Howareelementrelationshipsinagraphstructuredifferentfromthoseinatreestructure?2:Basedonwhatyouhavelearnedsofar,howcananedgebestoredinacomputer??BJNYLONTOKMEXPAR109108113821245597389DataStructuresChapter1Introduction1.2DefinitionofDataStructureAdatastructureisacollectionofdataelementswithstructuralcharacteristics,aswellasthemethodforstoringandorganizingthesedatainacomputer.Dataelement:thebasicunitofdatainacomputer,oftencalledanodeorrecord.Examples:arowinastudentregistrationtable,achessboardstate,oracity.Dataitem:thesmallestindivisibleunitthatconstitutesadataelement.Examples:astudentID,name,andotherattributes.Dataobject:acollectionofdataelementswiththesameproperties.DataStructuresChapter1Introduction1.2ThreeBasicDataStructures…………..……..………...……Adataobjectcontainsseveraldataelements.Adataelementcontainsseveraldataitems.BJNYLONTOKMEXPARNo.NameTeamAgeStateThree-pointshotDunkBlockShotBackboard…1MichaelJordanBulls32Normal961009086…2DwyaneWadeHeat23Injury90999290…3IronManBeijing28Normal75959698…4MagicJohnsonLakers27Suspension95978886…5ShaquilleO'NealShanghai25Normal78959597……………………………DataStructuresChapter1Introduction1.2LogicalStructureandStorageStructureDatastructureincludesthelogicalstructureandstoragestructureofdata.Logicalstructure:theoveralllogicalrelationshipamongdataelements.Linearlists,trees,andgraphsarenamedfromthelogicalperspective.Storagestructure:howdataandtheirlogicalrelationshipsarerepresentedandstoredinsidethecomputer;alsocalledphysicalstructure.Sequentialstorage:continuousmemoryallocation.Linkedstorage:dynamicmemoryallocation.DataStructuresChapter1Introduction1.2LogicalStructureAggregatestructure:theonlyrelationshipamongdataelementsisthattheybelongtothesameset;nootherrelationshipisrequired.Linearstructure:aone-to-onelinearrelationshipexistsamongdataelements.DataStructuresChapter1Introduction1.2Treestructure:one-to-manybranchrelationshipsamongdataelementsformahierarchicalstructure.Graphstructure:many-to-manyarbitraryrelationshipsexistamongdataelements.DataStructuresChapter1IntroductionLogicalStructure1.2StorageStructureSequentialstorage:dataelementsarestoredinagroupofcontiguousstorageunits,andthelogicalrelationshipamongelementsisrepresentedbytheirstoragelocations.……StartaddressExample:(,,)DataStructuresChapter1Introduction1.2Sequentialstorage:dataelementsarestoredinagroupofcontiguousstorageunits,andthelogicalrelationshipamongelementsisrepresentedbytheirstoragelocations.Linkedstorage:dataelementsarestoredinarbitrarystorageunits,andthelogicalrelationshipamongelementsisrepresentedbypointers.0200020803000325…………Example:(,,)02000325∧StorageStructureDataStructuresChapter1Introduction1.2LogicalStructureandStorageStructureThelogicalstructureofdatabelongstotheuserview;itisproblem-orientedandreflectstheinternalorganizationofdata.Thestoragestructureofdatabelongstotheimplementationview;itiscomputer-oriented.Thesamelogicalstructurecanbestoredusingmultiplestoragestructures,anddifferentstoragestructuresoftenleadtodifferentdata-processingefficiency.Understandingtheadvantagesanddisadvantagesofdifferentstoragestructuresandselectingoneaccordingtotheproblemisanimportantpartofthiscourse.DataStructuresChapter1Introduction1.2AccessInterfaceofDataStructuresAccessingadatastructurereferstooperationssuchasreading,modifying,processing,andhandlingdata.Basicoperationsofadatastructure:applicationscanaccessthedatastructurethroughtheseoperations.Accessinterface:thecallingformandspecificationofoperations,suchasparameterlistsandreturntypes.Accessinterfaceofadatastructure:thecompletesetofinterfacesforitsbasicoperations.DataStructuresChapter1Introduction1.2AbstractDataTypeConceptofAbstractDataTypeDataType:asetofvaluesandtheoperationsdefinedonthatset.Examples:integerandrealvariablesinC++.Abstract:extractingessentialfeaturesofaproblemwhileignoringnonessentialdetails.Examples:mapsandcarmodels.AbstractDataType(ADT):adatastructureandthesetofoperationsdefinedonthatstructure.DataStructuresChapter1Introduction1.2ExampleofADTADTname:BasketballPlayerData:describesthestructureofthedataName,age,team,abilities,…Operation:describesthebehaviorofdataOperation1:ConstructionOperation2:DestructionOperation3:ContestOperation4:TransferOperation5:Injured……EndADTDataStructuresChapter1Introduction1.2ADTandC++ClassesADTname:ConnectedAutonomousVehicleData:LinearstructurePosition,speed,acceleration,vehicletype,vehiclelength,sensingequipment,communicationequipment,……Operation:Operation1:ConstructionOperation2:DestructionOperation3:EnvironmentalawarenessOperation4:CommunicationOperation5:Decision-makingOperation6:Execute……EndADTDataStructuresChapter1IntroductionAlgorithmDescription1.31.3BasicConceptofAlgorithmAlgorithm:adescriptionofthestepsforsolvingaspecificproblem;afinitesequenceofinstructions.FivebasicattributesofanalgorithmInput:Analgorithmcanhavezeroormoreinputs.Output:Analgorithmshouldproduceoneormoreoutputs.Finiteness:Analgorithmmustalwaysterminateafterafinitenumberofsteps,andeachstepmustfinishinfinitetime.Definiteness:Eachinstructionmusthaveanexactmeaning,andthesameinputcanonlyproducethesameoutput.Feasibility:Theoperationsdescribedbythealgorithmcanbeimplementedbyexecutingbasicoperationsafinitenumberoftimes.DataStructuresChapter1Introduction1.3WhatIsa“GoodAlgorithm”?01030204ReadabilityThealgorithmiseasytoread,understand,andcommunicate,andconvenienttodebug,modify,andextend.

RobustnessTherobustnessofthealgorithm:itsbehaviorunderabnormalinput.

CorrectnessProducescorrectresultsforvalidinputs.

EfficiencyMinimizesthecomputationalresourcesconsumedbythealgorithm,includingtimeandspace.DataStructuresChapter1Introduction1.3AlgorithmDescription—FlowchartFlowchart:intuitivelydescribesthespecificstepsofanalgorithm.Advantages:intuitiveandeasytounderstand.Disadvantages:insufficientrigorandflexibility;unsuitableforcomplexalgorithmsandobject-orientedlanguages.DataStructuresChapter1Introduction1.3AlgorithmDescription—C++LanguageProgramminglanguage:describesalgorithmsusingaprogramminglanguage.Advantage:executablebyacomputer.Disadvantages:lowabstraction,notconciseenough,andrequiresstronglanguageability.#include<iostream.h>intcommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){cout<<commonFactor(63,54)<<endl;}DataStructuresChapter1Introduction1.3AlgorithmDescription—PseudocodePseudocode:aninformaldescriptionmethodbetweennaturallanguageandprogramminglanguage.Advantages:expressive,abstract,easytounderstand,andsimilartonaturallanguage.Disadvantages:notintuitiveenough;canbeunclearforcomplexalgorithmsandmaycauseambiguity.Basicrules(notstrict):Eachinstructionoccupiesoneline.Useindentationtorepresentbranchandloopstructures.Uselabelstomarkconsecutivestatementsatthesamelevel.Algorithm1.1:BinarySearchInput:arraya,lowerboundbegin,upperboundend,andkeyvaluekeyOutput:storagelocationmor-1Step1:Initializel=begin,h=endStep2:whilel<=h

2.1:m=(l+h)/2;2.2:ifa[m]=keyreturnstoragelocationm2.3:ifa[m]>keysearchthelefthalf,h=m-12.4:elsesearchtherighthalf,l=m+1Step3:Ifnotfound,return-1DataStructuresChapter1Introduction1.3AlgorithmDescription—UMLUnifiedModelingLanguage(UML)UMLisavisuallanguagefordescribing,constructing,anddocumentingsystemartifacts.Purpose:buildsoftwaremodels.Modelinglanguage:providesvocabularyandrulesforcommunication.Visualization:describesmodelsthroughdiagramscomposedofstandardsymbols.Amodelinglanguage,notaprogramminglanguage.Universalstandard:astandardlanguageinthecomputerandsoftwareindustry,alsoappliedinotherfields.DataStructuresChapter1Introduction1.3UMLLanguageStructureClassdiagram:classesandtheirrelationshipsObjectdiagram:objectsandtheirrelationshipsComponentdiagram:

componentsandtheirrelationshipsDeploymentdiagram:

deploymentofcomponentsSequencediagram:emphasizestimeorderCollaborationdiagram:

emphasizesobjectcollaborationStatediagram:statesofaclassActivitydiagram:modelsworkflowsUsecasediagram:capturesrequirementsStructuralBehavioralUseCaseDiagramStaticDiagramsImplementationDiagramsInteractionDiagramsBehaviorDiagramsDataStructuresChapter1Introduction1.3UML2.0UpdatesDataStructuresChapter1IntroductionInteractionDiagram1.3UMLClassDiagramThecoreoftheorganizationalstructureofobject-orientedsystems.Anabstractionofagroupofobjectswiththesameattributes,operations,relationships,andsemantics.IncludesName,Attributes,andOperations.DataStructuresChapter1Introduction1.3UMLActivityDiagramAnactivitydiagramdescribessystembehaviorandshowsthesequenceofactivitiesperformedbyclassesparticipatinginthebehavior.Activitydiagramsemphasizethecontrolflowfromoneactivitytoanotherandrepresentinternalprocessinganddrivingworkflows.Activitydiagramsincludemodelelementssuchasinitialandfinalnodes,activities,branchesandmerges(conditions),andforksandjoins(concurrency).Activitydiagramsareastandardizedindustrylanguageforobject-orientedsoftwaredesign.DataStructuresChapter1Introduction1.3UMLActivityDiagramDataStructuresChapter1IntroductionForkBranchMergeJoinActivityEndActivitydiagramsareobject-oriented,whileflowchartsareprocess-oriented.Activitydiagramscanrepresentconcurrentbehavior;flowchartscannot.Activitydiagramscandescribecomplexalgorithmsthroughdecompositionandnesting.AlgorithmAnalysis1.41.4MethodsofAlgorithmAnalysisImplementthealgorithmandmeasureitstimeandspacecosts.Post-runMeasurement01Disadvantages:

(1)Implementingthealgorithmtakessubstantialtimeandeffort.(2)Testresultsdependonhardware,software,andotherenvironmentalfactors.AlgorithmAnalysis:estimatingthecomputerresourcesrequiredbyanalgorithm,includingtimeandspace.TimeComplexitySpaceComplexityEstimatetheresourcesconsumedbythealgorithmduringthedesignstage.Pre-runAnalysis02DataStructuresChapter1Introduction1.4TimeComplexityofAlgorithmsExecutiontimeofanalgorithm=sumoftheexecutiontimeofeachstatement.Numberofexecutions×timeperexecutionComputerhardware,operatingsystem,andcompilersystemNumberofexecutionsTherefore,algorithmrunningtimeismeasuredbythenumberofexecutionsofthebasicstatement,denotedasT(n).n:problemscaleassysteminput(inputsize)Forthesamealgorithm,alargerproblemsizeleadstolongerrunningtime.Whichfactorisdeterminedbythealgorithm??DataStructuresChapter1Introduction1.4Problemsizen:suchastheorderofamatrix,numberofgraphnodes,numberofpositiveintegers,etc.Iftheprogramconsistsofthesethreestatements,thetotalnumberofexecutionsisT(n)=n²+n+1.Whichtermisthemostimportant??DataStructuresChapter1IntroductionTimeComplexityofAlgorithms

x++;Example1

for(i=1;i<=n;i++)x++;Example2BasicStatement:x++ExecutionCount:n

for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;Example3

1.4AsymptoticComplexityConsiderthemostsignificantfactorsaffectingalgorithmefficiencyandignoresecondaryfactors.EstimateAsnincreases,thefactorwiththegreatestimpactonalgorithmefficiencyis:DataStructuresChapter1Introductionvaluevaluevaluevaluevalue1.4NotationsforAlgorithmAnalysisO(big-oh):upperbound,lessthanorequalto.o(small-oh):upperbound,strictlylessthan.Ω(bigomega):lowerbound,greaterthanorequalto.ω(smallomega):lowerbound,strictlygreaterthan.Big-ONotationTheupperboundofthetimeorspacecostT(n)asproblemsizenincreases.Note:Ocomesfrom“Orderof…”;itisdefinitelynotzero.Definition:ifthereexisttwopositiveconstantscandn₀suchthatT(n)≤c×f(n)foralln≥n₀,thenT(n)=O(f(n)).Thismeansthatforsufficientlylargen,ifthereexistsapositiveconstantcsuchthatT(n)isnogreaterthanc×f(n),thenTisbig-Ooff.DataStructuresChapter1Introduction1.4Big-ONotationIfthereexisttwopositiveconstantscandn₀suchthatT(n)≤c×f(n)foralln≥n₀,thenT(n)=O(f(n)).DefinitionNotes:ForthesameT(n)andf(n),candn₀usuallyhavemultiplepossiblevalues.Weonlystatethatcandn₀exist;wedonotcarehowtoobtainthemorhowtochooseamongpossiblevalues.Theonlyconcernishowtodescribetheorderofalgorithmiccomplexity:thesimplestformoff(n),withasingletermandnoconstant.DataStructuresChapter1Introduction1.4PrinciplesofAlgorithmAnalysisFocusonthemostsignificantfactorscausingchangesincomplexity.Ignoreconstants.

Ignorealllower-orderterms.

DataStructuresChapter1Introduction1.4PrinciplesofAlgorithmAnalysisExample:ifanalgorithmexecutesabasicoperationtimes,thenDropconstants.Ignorelower-orderterms.Theorem:IfA(n)=aₘnᵐ+aₘ₋₁nᵐ⁻¹+…+a₁n+a₀isapolynomialofdegreem,thenA(n)=O(nᵐ).DataStructuresChapter1Introduction1.4ExamplesofAlgorithmAnalysisExamplesofAlgorithmAnalysisExample1:++x;Example2:for(i=0;i<n;i++)++x;Basicstatement:,executions:Basicstatement:,executions:Example3:for(i=0;i<n;i++)for(j=0;j<n;j++)++x;Basicstatement:,executions:DataStructuresChapter1Introduction1.4ExamplesofAlgorithmAnalysisExample4:for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}Basicstatement:Executions:Totalexecutions:Complexity:DataStructuresChapter1IntroductionExamplesofAlgorithmAnalysis1.4Example5:for(i=1;i<=n;++i)for(j=1;j<=i-1;++j){++x;}Basicstatement:Executions:Complexity:ExamplesofAlgorithmAnalysisExamplesofAlgorithmAnalysisDataStructuresChapter1Introduction1.4ExamplesofAlgorithmAnalysisExample6:for(i=1;i<=n;i=2*i) ++x;Basicstatement:Executions:Complexity:LetitbeT(n),thenn=11n=22n=32n=43n=53…n=84…n=1652021222324ExamplesofAlgorithmAnalysisDataStructuresChapter1Introduction1.4BestCase,WorstCase,andAverageCaseExample:SequentialSearch

intFind(intA[],intn){for(i=0;i<n;i++)if(A[i]==k)break;returni; }Ifthetimecostofaproblemdependsoninputdata,thebestcase,worstcase,andaveragecaseneedtobeanalyzed.Best:Worst:Average:ExamplesofAlgorithmAnalysisDataStructuresChapter1Introduction1.4SpaceComplexityMeasuresthestoragespaceconsumedbyanalgorithm;itisalsoafunctionofproblemsizen.Spacecomplexity=temporarystorageallocatedpercall×numberofcalls.Correspondstotimecomplexity.Algorithmexecutiontime=numberofexecutions×timeperexecution.ItcanalsoberepresentedusingBig-Onotation.DataStructuresChapter1IntroductionKeyPointsofThisChapterUnderstandtheconceptofabstractdatatype.Masterdescriptionmethodsusingpseudocode,classdiagrams,andactivitydiagrams.Understandthebasicideasofalgorithmanalysis.Beabletocalculatetimecomplexity.DataStructuresChapter1IntroductionHomeworkforThisChapter1.CompletetheZhihuishutasksandafter-classexercisesindependently.2.Calculatethetimecomplexityofthefollowingprogramsegments.DataStructuresChapter1Introduction(6)Giventheexecutioncountofanalgorithm:T(n)=25T(n/5)+n2,findthealgorithmictimecomplexity.(Googleinterviewquestion,optionalexercise)202

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

ofdataelementswiththesamecharacteristics”Lengthofalinearlist:thenumberofdataelementsinthelinearlistEmptylist:alinearlistwhoselengthiszero（a1,