数据结构英文版课件：Chapter 1 Data structure and Programming Principles

1Chapter1DatastructureandProgrammingPrinciples2ContentsPoints1WhatisDataStructure?2Generalstepsofprocessingproblemsbycomputer.3ProgramDesigninC++.4Exampledemonstration.31WhatisDataStructure?FundamentalTermsDataLayers:Data （数据）：asetofallthesymbolsthatcomputercanmanage.(所有能输入到计算机中并被计算机所识别和处理的符号的总称。)DataElements（数据元素）:数据中的一个个体。acharacter‘+’orastudentwhenitisstoredinacomputer.

DataItem（数据项）:whenthedataelementisarecord,itcanbedividedintodataitems.Example:astudentrecordmaybecombinedbynumber,name,scoreandsoon.4DataStructure:CollectionofrelationalDataElements

LogicalStructure（逻辑结构）theintrinsicrelationsbetweendataelements. Accordingtothedifferenceoftherelation,wecanclassifythemintofourkinds.ListTreeGraphSet5WhatisDataStructure?StorageStructure:（存储结构）PhysicalStructureincomputerContiguousstructureLinkedstructure62ProcessingproblemsbycomputerAlgorithmImplement-ationOutsideRepresentationManagementDemandLogicalStructureBasicOperationStorageStructureQuestionMathematicmodelBuildModelRefine在C++中实现时通常以类来实现数据结构及其上的操作7FundamentalTasks:DefinitionofDataStructure(includinglogicalstructureandbaseoperations);RealizationofDataStructure(includingstoragestructureandbaseoperations);EstimationandSelectionofDataStructure(analysisofalgorithms)AsymptoticTimeComplexity（时间复杂度）AsymptoticSpaceComplexity（空间复杂度）Processingproblemsbycomputer8ProblemsofLargePrograms

1.Problemspecification（需求分析）2.Programorganization3.Choiceofdatastructures4.Algorithmanalysis5.writethewholeprogram6.Debugging7.Testingandverification8.MaintenanceThepatchworkapproachisdoomedtofail.Andwemustalsobecarefultoobserveimportantprinciplesofprogramdesign.93ProgramDesigninC++C++features:DataAbstraction

（数据抽象）Object-orienteddesign（面向对象的设计）Top-downapproachCodereuse

（代码重用）

Refinement,improvement,extensionofCIntroductionofOO(ObjectOriented)Encapsulation

（封装性）Inheritance

（继承性）Polymorphism

（多态性）104Exampledemonstration

——gameoflifeDefinitionIttakesplaceonanunboundedrectangulargridinwhicheachcellcaneitherbeoccupiedbyanorganismornot.Occupiedcellsarecalledalive;unoccupiedcellsarecalleddead.Whichcellsarealiveornotchangesfromgenerationtogenerationaccordingtothenumberofneighboringcellsthatarealive,asfollows:4.1Rulesforthegameoflife11RulesoftheGameoflife

1.Theneighborsofagivencellaretheeightcellsthattouchitvertically,horizontally,ordiagonally.Everycelliseitherlivingordead.(onlytwostates)2.Alivingcellstaysaliveinthenextgenerationifithaseither2or3livingneighbors;itdiesifithas0,1,4,ormorelivingneighbors.(foralivingcell,conditionsofstilllivinganddie)12RulesoftheGameoflife3.Adeadcellbecomesaliveinthenextgenerationifithasexactlythreeneighboringcells,nomoreorfewer,thatarealreadyalive.Allotherdeadcellsremaindeadinthenextgeneration.(foradeadcellwhenthestatewillbechange?)4.Allbirthsanddeathstakeplaceatexactlythesametime.13Aparticulararrangementoflivinganddeadcellsinagridiscalledaconfiguration.Applyingtheprecedingrules,aninitialconfigurationchangestoanotherateachgeneration.configuration144.2ExamplesMoribundexampleByrule2and3,thelivingcellswilldieinthecominggeneration,andnocellswillbecomealive,sotheconfigurationdiesout15StableexampleEachofthelivingcellshasaneighborcountofthree,andhenceremainalive,butthedeadcellsallhaveneighborcountsoftwoorless,andhencenoneofthembecomesalive.Examples--216Alternateexamples:Thetwoconfigurationscontinuetoalternatefromgenerationtogeneration.Examples--317Variety(多样化)

Throughmanygeneration,asimpleinitialconfiguration growintolargeconfigurations, dieout, reachastatewheretheydonotchange Gothrougharepeatingpatterneveryfewgenerations.OurgoalWriteaprogramthatwillshowhowaninitialconfigurationwillchangefromgenerationtogeneration.184.3thesolution:classes,objectsandmethodsSetupaLifeconfigurationasaninitialarrangementoflivinganddeadcells.PrinttheLifeconfiguration.Whiletheuserwantstoseefurthergenerations:UpdatetheconfigurationbyapplyingtherulesoftheLifegame.Printthecurrentconfiguration.19ReviewofC++elementsAclass

collectsdataandthemethodsusedtoaccessorchangethedata.Suchacollectionofdataandmethodsiscalledanobject

belongingtothegivenclass.EveryC++classconsistsofmembers

thatrepresenteithervariables(calleddatamembers)orfunctions(calledmethods

ormemberfunctions).Thememberfunctionsofaclassarenormallyusedtoaccessoralterthedatamembers.Example:FortheLifegame,

Class:LifeclassObject:aconfigurationMethod:initialize(),update(),print()20Byrelyingonitsspecifications,aclientcanuseamethodwithoutneedingtoknowhowthedataareactuallystoredorhowthemethodsareactuallyprogrammed.Thisimportantprogrammingstrategyknownasinformationhiding.Datamembersandmethodsavailabletoaclientarecalledpublic;furtherprivate

variablesandfunctionsmaybeusedintheimplementationoftheclass,butarenotavailabletoaclient.Convention（约定）Methodsofaclassarepublic.Functionsinaclassareprivate.ReviewofC++elements214.4Life:TheMainProgram#include“utility.h”//679#include“life.h“//life类的定义部分intmain()//ProgramtoplayConway'sgameofLife./*Pre:Theusersuppliesaninitialconfigurationoflivingcells.Post:TheprogramprintsasequenceofpicturesshowingthechangesintheconfigurationoflivingcellsaccordingtotherulesforthegameofLife.Uses:TheclassLifeanditsmethodsinitialize(),print(),andupdate().Thefunctionsinstructions(),user_says_yes().*/22{Lifeconfiguration; instructions();

configuration.initialize();configuration.print();cout<<"Continueviewingnewgenerations?"<<endl;while(user_says_yes()){ configuration.update(); configuration.print(); cout<<"Continueviewingnewgenerations?"<<endl;}}23UtilityPackage(p678)

Weshallassembleautilitypackagethatcontainsvariousdeclarationsandfunctionsthatproveusefulinavarietyofprograms,eventhoughthesearenotrelatedtoeachotheraswemightexpectifweputtheminaclass.Forexample,weshallputdeclarationstohelpwitherrorprocessingintheutilitypackage.Ourfirstfunctionfortheutilitypackageobtainsayes-noresponsefromtheuser:booluser_says_yes()Pre:None.Post:Returnstrueiftheuserenters‘y’or‘Y’;returnsfalseiftheuserenters‘n’or‘N’;otherwiserequestsnewresponse24Clients,thatis,userprogramswithaccesstoaparticularclass,candeclareandmanipulateobjectsofthatclass.Forexample:declareaLifeobjectby:Lifeconfiguration;memberselectionoperator

Wecannowapplymethodstoworkwithconfiguration,usingtheC++operator.Forexample,wecanprintoutthedatainconfigurationbywriting:configuration.print();Thespecificationsofamethod,function,orprogramarestatementsofpreciselywhatisdone.Preconditions

statewhatisrequiredbefore;postconditions

statewhathashappenedwhenthemethod,function,orprogramhasfinished.ProgrammingPreceptIncludeprecisespecificationswitheveryprogram,function,andmethodthatyouwrite.OtherC++elements25ProgrammingStyle(自学20)Names（命名）:Guidelinesofnames:seep11-12DocumentationandFormat（文档化和书写格式）Somecommonlyacceptedguidelines:seep13RefinementandModularity（求精和模块化）:Top-downrefinement26Aswewritethemainprogram,wedecideexactlyhowtheworkwillbedividedamongthem.,howtodividethework?自学27DataCategoriesInputparameters--passedbyvalueorbyreference(const)Outputparameters—passedbyreference(suggest)InoutparametersusedforbothinputandoutputLocalvariables—definedinthefunctionandexistonlywhilethefunctionisbeingexecuted.Globalvariablesdangerous,causesideeffect28291.4Coding,TestingandFurtherRefinementCoding（编码）:writinganalgorithminthecorrectsyntaxofacomputerlanguagelikeC++Testing（测试）:runningtheprogramonsampledatachosentofinderrorsFurtherRefinement（进一步细化）:turntothefunctionsnotyetwrittenandrepeatthesesteps30Exampledemonstration

——gameoflifeCoding1.Stubs（占位程序）TocompileeachfunctionandclassseparatelyTocompilethemainprogramcorrectly,theremustbesomethingintheplaceofeachfunctionthatisused,soputinshort,dummyfunctions.——whichnamedstubsthesimpleststubsarethosethatdolittleornothingatall:

voidinstruction(){} booluser_says_yes() {returnfalse;}31Codingofgameoflife2.DefinitionoftheclassLifeconstintmaxrow=20,maxcol=60;//livingcells共有20行，60列classLife{ //存放在*.h文件中的类体声明public: voidinitialize();//初始化livingcells的状态

voidprint();//打印输出当前livingcells的状态

voidupdate();//进行deadliving间的转换private: intgrid[maxrow+2][maxcol+2];//借助两维数组存放living

cells //注意：为处理一致，添加了虚拟的2行2列，放围墙

intneighbor_count(introw,intcol);//统计邻居cell的状态};32Stubexample2:Tocheckiftheclassdefinitioniscorrect,Weshouldsupplythefollowingstubsforitsmethodsinlife.cpp: voidLife::initialize(){} voidLife::print(){} voidLife::update(){}33Instructionsvoidinstructions()/*Pre:None.Post:InstructionsforusingtheLifeprogramhavebeenprinted.*/{cout<<"WelcometoConway’sgameofLife."<<endl;cout<<"Thisgameusesagridofsize" <<maxrow<<"by"<<maxcol<<"inwhicheach"<<endl;cout<<"cellcaneitherbeoccupiedbyanorganismornot."<<endl;cout<<"Theoccupiedcellschangefromgenerationtogeneration"<<endl;cout<<"accordingtohowmanyneighboringcellsarealive."<<endl;}34user_says_yes()

booluser_says_yes(){ intc; boolinitial_response=true; do{//Loopuntilanappropriateinputisreceived. if(initial_response) cout<<"(y,n)?"<<flush; else cout<<"Respondwitheitheryorn:"<<flush; do{//Ignorewhitespace. c=cin.get(); }while(c==‘\n’||c==‘’||c==‘\t’); initial_response=false;}while(c!=‘y‘&&c!=‘Y‘&&c!=‘n‘&&c!=‘N‘);return(c==‘y‘||c==‘Y‘);}35FunctionsandMethodsofclassLife3.Countingneighbors:sentinel（岗哨）(hedge):ALife::neighbor_count(introw,intcol){ inti,j,count=0; for(i=row-1;i<=row+1;i++) for(j=col-1;j<=col+1;j++) count+=grid[i][j];//如果存活，则累加；否则为0 count-=grid[row][col];//去除自己

returncount;}3637FunctionsandMethodsofClassLife4.UpdatingthegridvoidLife::update(){ introw,col,new_grid[maxrow+2][maxcol+2]; for(row=1;row<=maxrow;row++) for(col=1;col<=maxcol;col++) switch(neighbor_count(row,col)){//调用统计函数,按结果分情况

case2:new_grid[row][col]=grid[row][col];break;//不变

case3:new_grid[row][col]=1;break;//激活

default:new_grid[row][col]=0;//dead

} for(row=1;row<=maxrow;row++) for(col=1;col<=maxcol;col++) grid[row][col]=new_grid[row][col];//将临时数组中的数据拷贝回原grid数组}38FunctionsandMethodsofClassLife5.InputandOutput:39FunctionsandMethodsofClassLifeInput——initializevoidLife::initialize(){ introw,col; for(row=0;row<=maxrow+1;row++) for(col=0;col<=maxcol+1;col++) grid[row][col]=0; cout<<“Listthecoordinatesforlivingcells.”<<endl; cout<<“Terminatethelistwiththespecialpair(-1,-1)”<<endl; cin>>row>>col; while(row!=-1||col!=-1){ if(row>=1&&row<=maxrow) if(col>=1&&col<=maxcol)grid[row][col]=1; elsecout<<“Column“<<col<<“isoutofrange.”<<endl; else cout<<“Row“<<row<<“isoutofrange.”<<endl; cin>>row>>col; } }40FunctionsandMethodsofclassLifeOutput——print:voidLife::print(){ introw,col; cout<<“\nThecurrentLifeconfigurationis:“<<endl; for(row=1;row<=maxrow;row++){ for(col=1;col<=maxcol;col++) if(grid[row][col]==1)cout<<“*”; elsecout<<“”; cout<<endl; } cout<<endl; }}41FunctionsandMethodsofClassLife6.Drivers:Driverisashortauxiliaryprogramwhosepurposeistoprovidethenecessaryinputforthefunction,andevaluatetheresult——sothateachfunctioncanbeisolatedandstudiedbyitself.42Example1:driverforneighbor_count():intmain()//driverforneighbor_count()/*Pre:None.Post:Verifiesthatthemethodneighbor_count()ifitreturnsthecorrectvalues.Uses:TheclassLifeanditsmethodinitialize().*/{Lifeconfiguration;configuration.initialize();for(row=1;row<=maxrow;row++){ for(col=1;col<=maxrow;col++) cout<<configuration.neighbor_count(row,col)<<""; cout<<endl;}}43Example2:driverforinitialize()andprint():Sometimestwofunctionscanbeusedtocheckeachother. configuration.initialize(); configuration.print();Bothmethodscanbetestedbyrunningthisdriverandmakingsurethattheconfigurationprintedisthesameasthatgivenasinput.447.Methodsfordebugging:(self-study)1).Structuredwalkthrough2).Tracetoolsandsnapshots3).Scaffolding4).Staticanalyzer45Exampledemonstration

——gameoflife8.Test(self-study)PrinciplesofprogramTesting:Black-BoxMethod（黑盒法）(a)Easyvalues(b)Typical,realisticvalues(c)Extremevalues(d)IllegalvaluesGlass-BoxMethod（白盒法）:TraceallthepathsthroughtheProgram,forasinglesmallmethod,itisanexcellentdebuggingandtestmethodTicking-BoxMethod——Don'tdoanythingJusthopeforthebest!46Action:Inpractice,black-boxtestingisusuallymoreeffectiveinuncoveringerrors.Onereasonisthatmostsubtleprogrammingerrorsoftenoccurnotwithinafunctionbutintheinterfacebetweenfunctions,inmisunderstandingoftheexactconditionsandstandardsofinformationinterchangebetweenfunction.47Exampledemonstration

——gameoflifeProgramMaintenance(self-study)Foralargeandimportprogram,morethanhalftheworkcomesinthemaintenancephase,afterithasbeencompletelydebugged,tested,andputintouse.Firststepofprogrammaintenanceistobeginthecontinuingprocessofreview,analysis,andevaluation.(forsomeusefulquestion,seep34)48Exampledemonstration

——gameoflifeProgramMaintenanceReviewoftheLifeprogramproblemspecification（问题规范）programcorrectness（程序纠错）userinterface（用户接口）modularityandstructure（模块化与结构化）documentation（文档）efficiency（效率）Programrevisionandredevelopment（修订与发布）49PointersandPitfalls

1.Toimproveyourprogram,reviewthelogic.Don'toptimizecodebasedonapooralgorithm.2.Neveroptimizeaprogramuntilitiscorrectandworking.3.Don'toptimizecodeunlessitisabsolutelynecessary.4.Keepyourfunctionsshort;rarelyshouldanyfunctionbemorethanapagelong.5.Besureyouralgorithmiscorrectbeforestartingtocode.6.Verifytheintricatepartsofyouralgorithm.50本章习题P10Exercise1.2(a)(e)(i)P17Exercise1.3E1(a)E9P38Exercise1.5E2P32Programmingprojects1.4P39Programmingprojects1.5p1-p551AlgorithmandprogramDescriptionoftheparticularstepsoftheprocessofaproblem(处理某一问题的步骤的描述)characteristicsFinityCertaintyFeasibilityInputinterfaceOutputinterfaceFormatisflexible，itcanbedescribedbyNaturalLanguage,AdvancedLanguage,andthesyntaxisnotthemostimportantthing,Nothingtodowiththeenvironment52program:Thewholeprocessoftheproblem（用计算机处理问题的全部代码的整体）MaybeInfiniteSyntaxmustbeaccurateCloselylinkedwiththeenvironment53算法简单性能分析与度量算法的性能标准算法性能的事后统计算法性能的事前估计54算法的性能标准正确性(Correctness)

算法应满足具体问题的需求。可读性(Readability)

算法应该容易阅读。以有利于阅读者对程序的理解。高效率效率指的是算法执行的时间和空间利用率。通常这两者与问题的规模有关。健壮性(Robustness)

算法应具有容错处理的功能。当输入非法数据时，算法应对其作出反应，而不应产生莫名其妙的输出结果。Asanend-userofaprogram,itsrunningtime,refertothewall-clocktime.（绝对时间）Itisnotnecessarilyareliablemeansofknowingwhetheraprogramisfastorslow,sincetheremaybeseveralotherfactorsthatcloudtheissue.（绝对时间量并不是衡量一个程序好坏的客观标准）ProgramAandB,wall-clocktime10and5secondsrespectively.SpeedofyourCPU?Otherprogramsrunningatthesametime?Whatisthelanguage?Sameenvironment—tomakefaircomparison.CPU的性能，是否有其他程序在同时运行，比较应该在一个公平的环境下进行55算法性能的事后统计56算法的事前估计算法的事前估计主要包括时间复杂度和空间复杂度的分析：问题的规模：如：矩阵的阶数、图的结点个数、被分类序列的正整数个数等。时间复杂度：算