2008级计算机 内部资料,仅供课堂教学使用 Chapter 1 PROGRAMMINg PRINCIPLes P1 1. Introduction: Problems with large programs 2. The Game of Life(a continuing example) (a) Software Engineering 3. Programming style (b) Problem Analysis 4. Coding, testing, and further refinement (c)Requirem ents Specification 5. Program maintenance 7. Pointers and Pitfalls I1. 1]Introduction: Problems with large programs Problems ofLarge Programs P.2-4 1. The patchwork approach 2. Problem specification 3. Program organization 4. Data organization and data structures 5. Algorithm selection and analysis 6. Debugging 7. Testing and verification 9. Highlights of C++ (a) Data abstraction (b) Object-oriented design (c) Reusable code (d) Refinement, improvement, extension of C [1.2 The Game of Life (a continuing example 1. 2. 1 Rules for the game of life p5 1. The neighbors of a given cell are the eight cells that touch it vertically, horizontally, or diagonally Every cell is either living or dead 2. A living cell stays alive in the next generation if it has either 2 or 3 living neighbors, it dies if it has o 4, or more living neighbors 3. A dead cell becomes alive in the next generation if it has exactly three neighboring cells, no more or fewer, that are al ready alive. All other dead cells remain dead in the next generation 4. All births and deaths take place at exactly the same time, so that a dying cell can help to give birth to another, but cannot prevent the death of others by reducing overcrowding, nor can cells being born either pr re or kill cells living in the previous generation 1. 2. 3 Algorithm P7 Set up a Life configuration as an initial arrangement of living and dead cells Print the Life configuration While the user wants to see further generations Update the configuration by applying the rules of the Life game Print the current configuration C++ Classes, Objects, and Methods P7-8 a class collects data and the methods used to access or change the data Such a collection of data and methods is called an object belonging to the given class
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Chapter 1 PROGRAMMING PRINCIPLES P.1 ------------------------------------------------------------------------------------------------------------------------------------------------ 1. Introduction: Problemswith large programs 2. The Game of Life (a continuing example) 3. Programming style 4. Coding, testing, and further refinement 5. Program Maintenance ---------------------------------------------------------------------- 6. Preview (a) Software Engineering (b) Problem Analysis (c) Requirem ents Specification (d) Coding 7. Pointers and Pitfalls 8. References [1.1]Introduction: Problems with large programs Problems ofLargePrograms P.2- 4 1. The patchwork approach 2. Problem specification 3. Program organization 4. Data organization and data structures 5. Algorithm selection and analysis 6. Debugging 7. Testing and verification 8. Maintenance 9. Highlights of C++ (a) Data abstraction (b) Object-oriented design (c) Reusable code (d) Refinement, improvement, extension of C [1.2] The Game of Life (a continuing example) 1.2.1 Rules for the Game of Life P.5 1. The neighbors of a given cell are the eight cells that touch it vertically, horizontally, or diagonally. Every cell is either living or dead. 2. A living cell stays alive in the next generation if it has either 2 or 3 living neighbors; it dies if it has 0, 1, 4, or more living neighbors. 3. A dead cell becomes alive in the next generation if it has exactly three neighboring cells, no more or fewer, that are al ready alive. All other dead cells remain dead in the next generation. 4. All births and deaths take place at exactly the same time, so that a dying cell can help to give birth to another, but cannot prevent the death of others by reducing overcrowding, nor can cells being born either preserve or kill cells living in the previous generation. 1.2.3 Algorithm P.7------------------------------------------------------------------------ Set up a Life configuration as an initial arrangement of living and dead cells. Print the Life configuration. While the user wants to see further generations: Update the configuration by applying the rules of the Life game. Print the current configuration. -------------------------------------------------------------------------------------------------- C++ Classes, Objects, and Methods P.7 - 8 ⚫ A class collects data and the methods used to access or change the data. ⚫ Such a collection of data and methods is called an object belonging to the given class
2008级计算机 据结构课堂教学笔记 内部资料,仅供课堂教 e Every C++ class consists of members that represent either variables(called data members) functions(called methods or member functions). The member functions of a class are normally used to access or alter the data members Example: For the Life game, the class is called Life, and configuration becomes a Life object. We use three methods: initialize() will set up the initial configuration of living and dead cells; print() will print out the current configuration; and update() will make all the changes that occur in moving from one generation to the next e Clients, that is, user programs with access to a particular class, can declare and manipulate objects of that class e The specifications of a method, function, or program are statements of precisely what is done Preconditions state what is required before; Post conditions state what has happened when the method function, or program has finished Programming Precept: Include precise specifications with every program, function, and method that you write. P 9 By relying on its specifications, a client can use a method without needing to know how the data are actually stored or how the methods are actually programmed. This important programming strategy known as information hiding Data members and methods available to a client are called public; further private variables and functions may be used in the implementation of the class, but are not available to a client. nvention: Methods of a class are public Functions in a class are private. P 8 2. 4 Life: The Main Program P.8 xamples oflife Configurations P11 11.3 Programming style 1.3. 1 Guidelines for Choosing Names items P12-13 Programming Precept: Always name your classes, variables, and functions with the greatest care, and explain them thoroughly. P 11 1.3.2 Documentation guidelines 8 items P13-14 Programming Precept: Keep your documentation concise but descriptive. P 13 Programming Precept: The reading time for programs is much more than the writing time Make reading easy to do. P 14 1.3. 3 Refinement and modularity Top-down design and refinement Programming Precept: Dont lose sight of the forest for its trees. P 15 Division of work Programming Precept: Use classes to model the fundamental concepts of the program. P 15 Programming Precept: Each function should do only one task, but do it well. P 15 Programming Precept: Each class or function should hide something. P 16 Categories of Data Input parameters, Output parameters, Inout parameters P16 Local variables. Global variables P17 Programming Precept: Keep your connections simple. Avoid global variables whenever possible P.17 Programming Precept: Never cause side effects if you can avoid it P.1 If you must use global variables as input, document them thoroughly Programming Precept: Keep your input and output as separate functions, so they can be changed easily and can be custom tailored to your computing system. P 25
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 ⚫ Every C++ class consists of members that represent either variables (called data members) or functions (called methods or member functions). The member functions of a class are normally used to access or alter the data members. Example: For the Life game, the class is called Life, and configuration becomes a Life object. We use three methods: initialize( ) will set up the initial configuration of living and dead cells; print( ) will print out the current configuration; and update( ) will make all the changes that occur in moving from one generation to the next. ⚫ Clients, that is, user programs with access to a particular class, can declare and manipulate objects of that class. ⚫ The specifications of a method, function, or program are statements of precisely what is done. Preconditions state what is required before; Postconditions state what has happened when the method, function, or program has finished. Programming Precept: Include precise specifications with every program, function, and method that you write. P.9 ⚫ By relying on its specifications, a client can use a method without needing to know how the data are actually stored or how the methods are actually programmed. This important programming strategy known as information hiding. ⚫ Data members and methods available to a client are called public; further private variables and functions may be used in the implementation of the class, but are not available to a client. Convention: Methods of a class are public. Functions in a class are private. P.8 1.2.4 Life: The Main Program P.8 Examples of Life Configurations P.11 [1.3] Programmingstyle 1.3.1 Guidelines for Choosing Names 7 items P.12-13 Programming Precept: Always name your classes, variables, and functions with the greatest care, and explain them thoroughly. P.11 1.3.2 Documentation Guidelines 8 items P.13-14 Programming Precept: Keep your documentation concise but descriptive. P.13 Programming Precept: The reading time for programs is much more than the writing time. Make reading easy to do. P.14 1.3.3 Refinement and Modularity Top-down design and refinement: Programming Precept: Don’t lose sight of the forest for its trees. P.15 Division of work: Programming Precept: Use classes to model the fundamental concepts of the program. P.15 Programming Precept: Each function should do only one task, but do it well. P.15 Programming Precept: Each class or function should hide something. P.16 Categories of Data Input parameters, Output parameters, Inout parameters P.16 Local variables, Global variables P.17 Programming Precept: Keep your connections simple. Avoid global variables whenever possible. P.17 Programming Precept: Never cause side effects if you can avoid it. P.17 If you must use global variables as input, document them thoroughly. Programming Precept: Keep your input and output as separate functions, so they can be changed easily and can be custom tailored to your computing system. P.25
2008级计算机 内部资料,仅供课堂教学使用 11. 4 Coding, testing, and further refinement Life methods t Life : neighbor count(int row, int col) P 23 void Life : update( P 24 oid instructions( P 25 void life nitialize( )P 26 void life 1. 4.1 Stubs p21 1. 4.2 Definition ofthe class life P.22 4.3 Counting Neighbors P23 1. 4.4 Updating the Grid P24 1. 4.5 Instructions P 25 Output P26 Initialization p 26 Utility package P27 We shall assemble a utility package that contains various declarations and functions that prove useful in a variety of programs, even though these are not related to each other as we might expect if we put them in a class For example, we shall put declarations to help with error processing in the utility package Our first function for the utility package obtains a yes-no response from the user: user says ye Returns true if the user enters'y' or"Y; returns false if the user enters 'n'orN I se uests esponse 1. 4. 6 Drivers P27-28 A driver for a function is an auxiliary program whose purpose is to provide the necessary input for the function. call it. and evaluate the result Debugging and Testing 1. 4.7 Methods for debugging: P28 1. Structured wal kthrougl 2. Trace tools and snapshots 3. Scaffolding 4. Static analyzer 14.8 Programming Precept: The quality of test data is more important than its quantity P29 Programming Precept: Program testing can be used to show the presence of bugs, but never their absenc P.29 Methods for program testing 1. The black-box method P 30 (a) Easy values (b) Typical, realistic values (c) Extreme values (d) Illegal values 2. The glass-box method: Trace all the paths through the program. P 31 3. The ticking-box method: Dont do anything-Just hope for the best! P, 32 Execution Paths P31 [1.5 Program Maintenance 6 items P34-35 Programming Precept: For a large and important program, more than half the work comes in the maintenance phase, after it has been completely debugged, tested, and put into use. P 34 Programming Precept: Be sure you understand your problem completely If you must change its terms, explain exactly what you have done. P 3
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 [1.4] Coding, testing, and further refinement Life Methods int Life :: neighbor count(int row, int col) P.23 void Life :: update( ) P.24 void instructions( ) P.25 void Life :: initialize( ) P.26 void Life :: print( ) P.26 1.4.1 Stubs P.21 1.4.2 Definition of the Class Life P.22 1.4.3 Counting Neighbors P.23 1.4.4 Updating the Grid P.24 1.4.5 Instructions P.25 Output P.26 Initialization P.26 Utility Package P.27 We shall assemble a utility package that contains various declarations and functions that prove useful in a variety of programs, even though these are not related to each other as we might expect if we put them in a class. For example, we shall put declarations to help with error processing in the utility package. Our first function for the utility package obtains a yes-no response from the user: bool user_says_yes( ) Pre: None. Post: Returns true if the user enters ‘y’ or ‘Y’; returns false if the user enters ‘n’ or ‘N’; otherwise requests new response 1.4.6 Drivers P.27 - 28 A driver for a function is an auxiliary program whose purpose is to provide the necessary input for the function, call it, and evaluate the result. Debugging and Testing 1.4.7 Methods for debugging: P.28 1. Structured walkthrough 2. Trace tools and snapshots 3. Scaffolding 4. Static analyzer 1.4.8 Programming Precept: The quality of test data is more important than its quantity. P.29 Programming Precept: Program testing can be used to show the presence of bugs, but never their absence. P.29 Methods for program testing: 1. The black-box method P.30 (a) Easy values (b) Typical, realistic values (c) Extreme values (d) Illegal values 2. The glass-box method: Trace all the paths through the program. P.31 3. The ticking-box method: Don’t do anything—Just hope for the best! P.32 Execution Paths P.31 [1.5] Program Maintenance 6 items P.34 - 35 Programming Precept: For a large and important program, more than half the work comes in the maintenance phase, after it has been completely debugged, tested, and put into use. P.34 Programming Precept: Be sure you understand your problem completely. If you must change its terms, explain exactly what you have done. P.35
2008级计算机 内部资料,仅供课堂教学使用 Programming Precept: Design the user interface with the greatest care possible A programs success depends greatly on its attractiveness and ease of use. P37 gramm ar code unless it is necessary to do so. Do not start to opt until it is complete and correct. Most programs spend 90 percent of their time doing 10 percent of heir instructions. Find this 10 percent, and concentrate your efforts for efficiency there. P 37 Programming Precept: Keep your al gorithms as simple as you can. When in doubt, choose the simple way P.38 Programming Precept: Sometimes postponing problems simplifies their solution P.38 1.6. 1 Software Life Cycle 10 items P.40 1.6. 2 Problem analysis 8 items P40-41 1.6.3 Requirements Specification 4 items P41 1. Functional requirements for the syste d limitations on the syste 4. Documentation requirements The requirements specifications state what the software will do, not how it will be done 6. 4 Precepts on Coding P41-42 Programming Precept: Never code until the specifications are precise and complete Programming Precept: Act in haste and repent at leisure. Program in haste and debug forever Programming Precept: Starting afresh is often easier than patching an old program Programming Precept: Always plan to build a prototype and throw it away You' ll do so whether you plan to or not [1.7 Pointers and Pitfalls 21 items P45-46 Errata p. 18, E5(b), next-to-last line should be"loop2= loopl+ 1 p. 26, line 12: Change"the the"to"the p. 32, E3(e): The first line should read: A function that sorts an array a containing n integers indexed from 0 to n-1
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Programming Precept: Design the user interface with the greatest care possible. A program’s success depends greatly on its attractiveness and ease of use. P.37 Programming Precept: Do not optimize your code unless it is necessary to do so. Do not start to optimize code until it is complete and correct. Most programs spend 90 percent of their time doing 10 percent of their instructions. Find this 10 percent, and concentrate your efforts for efficiency there. P.37 Programming Precept: Keep your algorithms as simple as you can. When in doubt, choose the simple way. P.38 Programming Precept: Sometimes postponing problems simplifies their solution. P.38 [1.6] Preview 1.6.1 Software Life Cycle 10 items P.40 1.6.2 Problem Analysis 8 items P.40 - 41 1.6.3 Requirements Specification 4 items P.41 1. Functional requirements for the system 2. Assumptions and limitations on the system 3. Maintenance requirements 4. Documentation requirements The requirements specifications state what the software will do, not how it will be done. 1.6.4 Precepts on Coding P.41 - 42 Programming Precept: Never code until the specifications are precise and complete. Programming Precept: Act in haste and repent at leisure. Program in haste and debug forever. Programming Precept: Starting afresh is often easier than patching an old program. Programming Precept: Always plan to build a prototype and throw it away. You’ll do so whether you plan to or not. [1.7]Pointers and Pitfalls 21 items P.45 - 46 ------------------------------------------------------------------------------------------------------------------------------- Errata p. 18, E5(b), next-to-last line should be "loop2 = loop1 + 1;" p. 26, line 12: Change "the the" to "the". p. 32, E3(e): The first line should read: A function that sorts an array a containing n integers indexed from 0 to n - 1 -------------------------------------------------------------------------------------------------------------------------------